Implementacja w układzie reprogramowalnym wieloprocesorowego systemu realizującego algorytm RANSAC

• Autorzy: Fularz M. , Kraft M.

Warianty tytułu

EN

FPGA implementation of a multiprocessor system performing the RANSAC algorithm

• Języki publikacji: PL

Abstrakty

PL

W artykule opisano programową, wieloprocesorową realizację algorytmu RANSAC, który umożliwia odporną estymację modelu matematycznego z danych pomiarowych zawierających znaczący odsetek wartości odstających (ang. outliers). System został zaimplementowany w układzie FPGA w oparciu o konfigurowalne soft procesory MicroBlaze. W pracy przedstawiono opis algorytmu RANSAC, sposób jego podziału w celu przetwarzania równoległego, a także proces konfiguracji systemu wieloprocesorowego. Zaprezentowano również przyrost prędkości przetwarzania w zależności od liczby zastosowanych rdzeni procesorowych, porównano te wyniki do realizacji na komputerze klasy PC i przedstawiono zużycie zasobów układu FPGA.

EN

The paper describes a multiprocessor system implementing the RANSAC algorithm [3] which enables robust estimation of a fundamental matrix from a set of image keypoint correspondences containing some amount of outliers. The fundamental matrix encodes the relationship between two views of the same scene. The knowledge of the fundamental matrix enables e.g. the reconstruction of the scene structure. The implemented system is based on three MicroBlaze microprocessors [5] (one master, two slaves) and a dedicated hardware coprocessor connected using fast simplex link (FSL) interfaces [6]. The slave microprocessors perform the task of fundamental matrix computation from point correspondences using singular value decomposition - the so called 8-point algorithm [1, 2] (hypothesis generation). The master processor, along with the connected coprocessor, is responsible for dataflow handling and hypothesis testing using the Sampson error formula (7). The hypothesize and test framework used in RANSAC allows for largely independent task execution. The design is a development of a system described in [5]. The block diagram and dataflow diagram of the proposed solution are given in Figs. 1 and 2, respectively. Tabs. 1 and 2 summarize the use of FPGA resources. With a 100 MHz clock, the designed system is capable of processing the data at the speed which is roughly equivalent to that of the Atom N270 microprocessor clocked at 1,2 GHz. The resulting solution will be targeted at applications for which small size, weight and power consumption are critical. The design is also easily scalable - addition of more slave processors will result in additional increase in the processing speed.

Słowa kluczowe

PL

układy FPGA; sprzętowa implementacja; systemy wieloprocesorowe; RANSAC; macierz fundamentalna

EN

FPGA devices; hardware implementation; multiprocessor systems; RANSAC; fundamental matrix

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2011
• Tom: R. 57, nr 8
• Strony: 914--916
• Opis fizyczny: Bibliogr. 8 poz., schem., tab., wzory

Twórcy

autor

Fularz M.

autor

Kraft M.

• Politechnika Poznańska, Instytut Automatyki i Inżynierii Informatycznej, ul. Piotrowo 3a, 60-965 Poznań,

Bibliografia

• [1] Hartley R., Zissermann A.: Multiple view geometry in computer vision. Cambridge University Press, 2003.
• [2] Cyganek B., Siebert J. P.: An introduction to 3D computer vision techniques and algorithms, Wiley, 2009.
• [3] Fischler M. A., Bolles R. C.: Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography, Communications of the ACM, vol. 24, s. 381-395, 1981.
• [4] Kraft M.: Sprzętowo-programowa realizacja algorytmu RANSAC do estymacji macierzy fundamentalnej. Pomiary Automatyka Kontrola 7/2010, s. 742-744.
• [5] Xilinx Inc.: UG 081 – MicroBlaze Processor Reference Guide, October 2009. http://www.xilinx.com
• [6] Xilinx Inc.: DS. 449 – Fast Simplex Link (FSL) Bus (v2.11b), Data Sheet, June 2009. http://www.xilinx.com
• [7] Tippetts B., Fowers S., Lillywhite K., Lee D. J., Archibald J.: FPGA implementation of a feature detection and tracking algorithm for real-time applications, Advances in VisualComputing. Proceedings Third International Symposium, ISVC 2007. Part I. Lecture Notes in Computer Science vol. 4841. 2007: 682-91 Springer Verlag, Berlin, Germany.
• [8] Martelli S., Marzotto R., Colombari A., Murino V.: FPGA-based robust ellipse estimation for circular road sign detection, Proceedings of the 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops CVPR Workshops. 2010: 8 pp., IEEE Computer Society, Los Alamitos, CA, USA.