Zrandomizowana transformata Hougha (RHT) w strukturze FPGA

W artykule przedstawiona jest modyfikacja algorytmu RHT w celu efektywnego wykorzystania jej w strukturze FPGA. Głównym problemem implementacji RHT w FPGA jest duża i dynamicznie zorganizowana pamięć parametrów. Autor proponuje alternatywne rozwiązanie organizacji tej pamięci. Postuluje się, że pamięć parametrów i punktów aktywnych mogłaby być wspólna i niezorganizowana. Zadanie organizacji można przerzucić na proces losowy. Tak zmodyfikowany algorytm można skutecznie zaimplementować w układzie FPGA.

The paper presents modification of a randomized Hough transform (RHT) for efficient implementation in FPGA. The RHT has one significant advantage in comparison with the Hough Transform (HT) - much shorter processing time. It results from the fact that two points constitute together precisely one line (1), not the whole family of them (HT). Therefore only one accumulation has to be done in the parameter space for a single pair of points. The main problem of RHT implementation is a large and dynamic memory structure required for the parameter space. The author proposes an alternative solution. It is suggested that the parameters and active points memory could be kept in the same unorganized memory unit. Organization of the parameter space might be ensured afterwards by a random process, the same used for selecting two points to be put together into a single line. The problem of voting for "non-existing" lines (Fig. 1), common for algorithms in [1] and [3], is solved by connecting lines together (Fig. 2). The algorithm for such a transform has been proposed (Fig. 3) and implemented in FPGA (Figs. 5, 6, 7). It has resulted in a small and compact memory required in case of implementing the RHT. Moreover, the memory size is treated here as a parameter for implementation, allowing to trade the range of lines to be processed simultaneously and the efficiency of memory utilization. It works well even with a little memory supporting only tens or hundreds lines.