Zrandomizowana transformata Hough'a (RHT) w strukturze FPGA

• Autorzy: Kapruziak M.

Warianty tytułu

EN

Randomized Hough Transform in FPGA

• Języki publikacji: PL

Abstrakty

PL

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.

Słowa kluczowe

PL

RHT; FPGA; Randomized Hough Transform

EN

RHT; FPGA; Randomized Hough Transform

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2009
• Tom: R. 55, nr 8
• Strony: 624--626
• Opis fizyczny: Bibliogr. 4 poz., rys., wzory

Twórcy

autor

Kapruziak M.

• Zachodniopomorski Uniwersytet Technologiczny,

Bibliografia

• [1] L. Xu, E. Oja, P. Kultanen: A New curie detection metod: Randomized Hough Transform (RHT), Pattern Recognition Letters 11, 1990, pp. 331-338.
• [2] H. Illingworth, J. Kittler: The adaptive Hough transform, IEEE Transactions on Pattern Analysis and Machine Intelligence 1987.
• [3] M. Delalandre, B. Simon, S. Guillas, J. M. Ogier, K. Bertet: Stright Line Detection based on the Hough Transform a System and its Performance Evaluation, Draft, 2006.
• [4] Ch. Linpeng, Z. Guoliang, J. Guangming, T. Qi: A new algorithm for line detection based on the Randomized Hough Transform, The Eighth International Conference on Electronic Measurement and Instruments, ICEMI’2007.