Mapping stereo matching algorithms to hardware

Abstract

Stereo Vision verwendet zwei Kameras, welche die Umgebung aus verschiedenen Blickwinkeln betrachten. Die resultierende Verschiebung der Objekte im Bild, welche Disparität genannt wird, korreliert mit dem Abstand der Objekte zur Kamera und ermoglicht die Berechnung eines dreidimensionalen Tiefenbildes mittels Triangulation.<br />Das Kernelement eines Stereo Vision Systems, der Stereo Matching Algorithmus, hat eine hohe Komplexität. Glücklicherweise hat sich herausgestellt, dass achenbasierte Algorithmen besonders geeignet für Hardware-Implementierungen sind, wodurch sie in Embedded Stereo Vision Systemen mit einer hohen Bildwiederholrate implementiert werden konnen.<br />In Robotikanwendungen ist es wahrscheinlich, dass Stereo Vision Systeme in wechselnder Umgebung arbeiten. Im Gegensatz zu Software-Implementierungen, konnen Hardwarebasierte ihr Verhalten jedoch nicht leicht ändern, ohne Teile ihrer Ressourcen zu deaktivieren.<br />In dieser Arbeit wird eine neue Methode präsentiert, mittels derer die Blockgröße, die Disparitatsweite und die Bildwiederholrate wahrend des Betriebs umgestellt werden können. Diese Methode ist nicht nur für FPGAs sondern auch für ASICs geeignet, da sie ohne dynamische Rekon guration auskommt, wodurch sie optimal für Echtzeitimplementierungen geeignet ist.<br />Des Weiteren werden Methoden für die Verbesserung der Genauigkeit von Echtzeitalgorithmen prasentiert. Diese beinhalten nicht nur die Erweiterung bestehender Algorithmen auf eine verbesserte Robustheit gegenuber Bildrauschen, sondern auch die Vorstellung eines neuen hochgenauen Echtzeitalgorithmus, welcher fur die Implementierung in Hardwarebasierten System besonders geeignet ist.<br />Dieser Algorithmus ist auf eine hohe Genauigkeit in nicht abgeschatteten Bildbereichen fokussiert, also alle Bereiche in denen eine Objektkorrespondenz berechnet werden kann.<br />Die Evaluierung des Algorithmus mittels des Middlebury Stereo Ranking zeigt, dass die Resultate in dieser Disziplin eine Genauigkeit erzielen, die bis dato eine reine Domäne der nicht echtzeitfähigen Algorithmen war.<br />

Stereo vision uses two cameras side by side and extracts the displacement of the objects caused by the cameras' dierent viewpoints. The displacement, called disparity, is directly correlated to the distance of the objects. This way a three-dimensional depth map can be computed.<br />The core element of a stereo vision system, the stereo matching algorithm, has a high computational complexity. Fortunately, area-based algorithms proved to be very suitable for solutions using hardware-based parallel processing, enabling the implementation of real-time embedded stereo vision systems with high frame rates.<br />In robotic applications, embedded stereo vision systems are likely to operate in an environment that is subject to repeated changes. However, in contrast to software-based implementations, hardware-based solutions cannot easily change their behavior without deactivating parts of their resources. Therefore, a novel technique to adapt block size, disparity range and frame rate for hardware implementations of area-based stereo matching algorithms is proposed. This technique is suitable for FPGAs as well as ASICs, i.e., it comes along without dynamic recon guration, enabling its implementation on real-time systems with short deadlines.<br />Furthermore, novel approaches on how the accuracy of real-time algorithms can be improved are presented in this work. These approaches are not limited to the extension of existing algorithms for enhanced noise robustness, but also includes the presentation of a novel highly accurate real-time stereo matching algorithm that achieves an accuracy that until now was achievable with non-real time algorithms only, while still being apt to hardware-based solutions.<br />This novel stereo matching algorithm is targeted at a high accuracy in non-occluded regions, i.e. all image areas where a stereo correspondence can be found. The evaluation of this algorithm using the Middlebury Stereo Ranking, at a maximum deviation of half a pixel, shows, that by the time this work was performed, it is the only real-time algorithm that is capable of challenging state of the art non real-time algorithms.