Sprzętowo-programowa realizacja algorytmu RANSAC do estymacji macierzy fundamentalnej

W artykule opisano hybrydową, sprzętowo-programową realizację algorytmu RANSAC, umożliwiającego odporną estymację modelu matematycznego z danych pomiarowych zawierających znaczący odsetek wartości odstających (ang. outliers). Zaimplementowany system, oparty o mikroprocesor Microblaze wraz z dedykowanymi procesorami sprzętowymi, wykorzystywany jest do estymacji macierzy fundamentalnej. W macierzy tej zakodowany jest związek pomiędzy dwoma obrazami tej samej sceny, a jej znajomość umożliwia m. in. rekonstrukcję struktury sceny. Praca zawiera krótki opis algorytmu RANSAC, opis realizacji algorytmu w układzie FPGA, oraz podsumowanie użytych do implementacji zasobów. Przeprowadzono również porównanie szybkości działania implementacji programowej oraz sprzętowo-programowej algorytmu na procesorze Microblaze, oraz implementacji programowej na komputerze PC wyposażonym w energooszczędny procesor.

The paper describes hybrid, hardware/software implementation of RANSAC algorithm, enabling the robust mathematical model estimation from measurement data containing a significant amount of outliers. The implemented system, based on the Microblaze microprocessor along with a dedicated hardware coprocessor, performs the task of fundamental matrix estimation. The matrix encodes the relationship between two views of the same scene. This enables e.g. the reconstruction of the scene structure. The system (implemented in a Virtex 5 PFGA) is capable of working with a clock speed of 100MHz. Applying the hardware coprocessor cuts the overall algorithm execution time by approximately half. The part of the algorithm that was chosen for hardware implementation (checking the consistency of measurement data with the computed model) is sped up 50 times when compared to software implementation. The resource usage is kept low by using a custom 23-bit floating point representation (see Fig. 2). Table 1 presents the summary of resources used for implementation. Fig. 1 outlines the system architecture, while Figs. 3 and 4 present the detailed coprocessor structure. The 8-point algorithm based model generation is harder to translate into hardware, because it relies on singular value decomposition for finding least-squares solution of a linear system of equations [1][2]. The future work will therefore be focused on this subject, and on integration of the described system with the processor for image feature detection [3], description and matching. The resulting solution will be targeted at applications, in which small size, weight and power consumption are critical.