Real-time stereo matching for embedded systems in robotic applications

Abstract

Zur dreidimensionalen Datenerfassung mit Stereo Vision wird eine Szene von zwei digitalen Kameras erfasst. Hierfür werden die Kameras parallel zueinander auf einer Basis montiert. Jeder sichtbare Punkt der Szene wird auf die Bildebene beider Kameras projiziert. Die Projektionen korrespondieren miteinander und das Pixelpaar kann zur Rekonstruktion der dreidimensionalen Position des Szenenpunktes verwendet werden. Der horizontale Versatz eines korrespondierenden Pixelpaars ist die Disparität und ist indirekt proportional zur Tiefe des projizierten Punktes. Die Hauptaufgabe von Stereo Vision Systemen ist, diese Korrespondenzen zu finden oder, in anderen Worten, das Korrespondenzproblem zu lösen. Ein gefundenes Pixelpaar wird Match genannt. In dieser Arbeit stellen wir uns der Herausforderung von echtzeitfähigem Stereomatching, das den Anforderungen von Anwendungen in der Robotik genügen soll. Dazu gehört, neben hoher Rechengeschwindigkeit, auch die Möglichkeit einer eingebetteten Realisierung. Solche eingebetteten Systeme haben beschränkte Ressourcen, vor allem bei dem Speicher und der Rechenleistung, und erlauben deshalb keinen Einsatz von den meisten technisch ausgefeilten und anspruchsvollen Stereomatching-Algorithmen. Aus diesem Grund evaluierten wir die Stärken und Schwächen der bekannten Methoden und fanden eine passende Lösung in einem Census-basierten Verfahren. Gezielte Änderungen und Erweiterungen sowie die Optimierung des bekannten Verfahrens machen die Census Transformation echtzeitfähig und ermöglichen die Realisierung auf eingebetteten Systemen, ohne dass dedizierte Hardware, wie eigens hierfür erzeugte Halbleiterchips, verwendet werden müssen. Wir verwenden, im Gegensatz zur klassischen Census Transformation, ein spärlich besetztes Census-Fenster, das bei gleich bleibender Matchingqualität eine nahezu doppelt so schnelle Verarbeitung ermöglicht. Dies ist auf die Tatsache zurückzuführen, dass sich große, spärlich besetzte, Census-Fenster besser eignen als kleine vollständig besetzte Fenster. Diesen Sachverhalt zeigen wir durch Experimente mit unterschiedlichen Fenstergrößen. Neben dem Algorithmus stellen wir das komplette Stereo Vision System, mit einer genauen Evaluierung der Ergebnisse, vor. Das System ist robust, lässt sich leicht parametrisieren und ist für den Einsatz im Anwendungsfeld der Robotik flexibel und skalierbar. Außerdem präsentieren wir eine detaillierte Analyse der Laufzeiten von hochoptimierten Realisierungen des Algorithmus auf unterschiedlichen kommerziell erhältlichen Plattformen wie einem Personalcomputer (PC), einem digitalen Signalprozessor (DSP) und einer Grafikkarte (GPU). Dabei erreichen wir mit unserem Algorithmus eine Bildwiederholungsrate von bis zu 75 Bildern in der Sekunde für eine Auflösung von 640x480 mit 50 Disparitätsstufen. Zur Evaluierung der Matchingqualität verwenden wir die Middlebury Stereo Datenbank, in der unser Algorithmus Rang 73 von 104 Einträgen in der Haupttabelle und Rang 23, wenn subpixel Genauigkeit vorausgesetzt ist, erreicht. Zu guter Letzt vergleichen wir unseren Algorithmus mit dem bekannten Stereomatching Algorithmus Sum of Absolute Differences (SAD) und einer modifizierten Form des Algorithmus Semi-Global Matching, sowohl mit Middlebury Datensätzen als auch mit Aufnahmen aus dem Anwendungsfeld und zeigen eine klare Verbesserung der Ergebnisse mit unserem Ansatz.<br />

In 3D perception with stereo vision two digital cameras are used to capture a target scene. A canonical stereo setup is used where the cameras are mounted in parallel onto a common, mechanically rigid structure. Each scene point visible in both images is projected onto the image planes of both cameras. Thus, the projections correspond to each other and can further be used to reconstruct the 3D position of the scene point. The horizontal displacement is the disparity which is inversely proportional to the depth of the projected point. The main task of a stereo vision system is to find these correspondences or, in other words, to solve the correspondence problem. A corresponding pixel pair is called a match. In this thesis, we tackle the challenge of fast stereo matching for robotic applications and embedded systems. Motivated by the fact that limited resources, e.g. memory and processing power, and most importantly real-time capability on robot platforms do not permit the use of most existing sophisticated stereo matching approaches, we evaluated the strengths and weaknesses of different matching approaches and found a well-suited solution in a Census-based stereo matching approach. We adapt and optimize our algorithm in a way that the well-known Census transform can be used in embedded real-time systems without the need of dedicated hardware such as application-specific integrated circuits (ASIC) or field programmable gate arrays (FPGA). In contrast to the classic Census transform we use a sparse Census mask which halves the processing time with nearly unchanged matching quality. This is due to the fact that large sparse Census masks perform better than small dense masks with the same processing effort. We show the evidence of this assumption with the results of experiments with different mask sizes. Beside the algorithm we also present the complete stereo matching system as well as the detailed analysis and evaluation of the results. The system is robust, easy to parameterize and offers high flexibility in the target application field. Furthermore, we give a detailed performance analysis of the algorithm for optimized reference implementations on various commercial off-the-shelf platforms, e.g. a personal computer, a digital signal processor, and a graphics processing unit, where our algorithm achieves a frame rate of up to 75 fps for 640x480 images and 50 allowed disparities. We compare the matching quality and processing time of our approach to other algorithms on the Middlebury stereo evaluation website where it achieves rank 73 out of 104 submissions in the main ranking and rank 23 if subpixel accuracy is presumed. Additionally, we evaluate the algorithm by comparing the results with a fast and well-known sum of absolute differences algorithm and a modified version of semi-global matching using several Middlebury datasets and real-world scenarios, which shows the enhanced performance of our algorithm.