Wykonanie pełnej transformaty Hougha wymaga dużej mocy obliczeniowej. Moc obliczeniową można zredukować wybierając losowo tylko niektóre próbki do przetwarzania. Algorytm taki nosi nazwę RHT. Klasycznie, ze względu na intensywne wykorzystanie dynamicznych struktur danych oraz dużą liczbę warunkowo wykonywanych funkcji, zadanie RHT nie implementuje się dobrze w strukturze FPGA. Autor proponuje modyfikację tego algorytmu, tak aby efektywnie można było wykonać taka implementacje. W artykule przedstawiono propozycję struktury procesora dedykowanej dla struktury FPGA i realizującego algorytm RHT.
EN
Original Hough Transform requires much computational power to calculate parameter space and select proper maxima in that space. Computational power can be reduced by randomly selecting only a subset of points for processing. An algorithm constructed that way is called the RHT (Randomized Hough Transform). Originally, because of intensive use of dynamic memory structures and high number of conditionally executed functions, the RHT algorithm does not fit well in FPGA. The author tries to modify that algorithm in order to be able to implement it efficiently in static FPGA structures. It is achieved by means of rejecting the parameter space, using a line list instead and selecting lines from that list to be paired, extended or checked. Pairing is a procedure of connecting two lines and is a vital part at the initial stage. The extending procedure tries to search if there are more points at left or right side of a line which might extend that line. The checking procedure confirms existence of a line and potentially eliminates it from further processing (when long enough or too short). Having linearly addressed the line list with random selection of lines inside allows not to use dynamic memory structures and improves its FPGA implementation significantly. The FPGA implemented structure of a processor for the proposed algorithm is presented in the paper.
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.
EN
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.