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

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.

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.