Zmodyfikowana zrandomizowana transformata Hougha w strukturze FPGA

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.

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.