title: Performance analysis of a stereo matching implementation in OpenCL
Creators: name: Rotheneder, Stephan
Publisher: name: TU Wien
Year: 2018
Subjects: subject: Stereo matching
subject: Code parallelization
subject: Multiple platforms

description: Einer der ersten Schritte des Prozesses, welcher 3D-Information aus 2D-Bildern berechnet, ist der des Stereo Matching. Um einen 3D-Punkt aus übereinstimmenden 2D-Features zu triangulieren, muss deren Abstand in Pixel, die sogenannte Disparität, berechnet werden. Mit der berechneten Disparität pro Pixel und einem projektiven Kameramodell, können 3D-Daten für den Großteil eines Bildes berechnet werden. Die Berechnung von 3D-Szeneninformation findet Anwendung in Bereichen der Hinderniserkennungs- und Kollisionsvermeidungssysteme der Automobilindustrie und pick-and-place- oder Mensch-Roboter-Kollaboration-Systeme (MRK-Systeme) in der Roboterindustrie. Da Zeit ein wichtiger Faktor in den meisten dieser Anwendungen ist, hat das Thema Echtzeit-Stereo-Matching an Wichtigkeit gewonnen, während Qualitäts- und Genauigkeitsaspekte ihren Stellenwert beibehalten haben. Benchmarks wie der KITTI- oder Middlebury Benchmark stellen Test-Stereodaten und Ground Truth für die Evaluierung von Matching-Algorithmen zur Verfügung. Diese werden genutzt, um verschiedene Algorithmen, bezüglich Genauigkeit, Flächendeckung and Laufzeit miteinander zu vergleichen. Allerdings liegt eine Schwäche im Hinblick auf die Messbarkeit der Recheneffizienz vor, da die Laufzeit- und Echtzeit-Fähigkeiten von verglichenen Stereo-Matching Algorithmen stark von der verwendeten Hardware abhängen. Das Hauptaugenmerk dieser Arbeit liegt auf der Untersuchung der Möglichkeiten von Echtzeit-Stereo-Matching unter den mit der verwendeten Hardware verbundenen Einschränkungen. In Hinblick auf diesen Aspekt wurde ein Stereo-Matching Algorithmus in OpenCL implementiert, um die Laufzeit eines einzelnen Algorithmus auf verschiedenen Geräten evaluieren zu können. Mit diesen Laufzeitdaten besprechen wir die Beschränkungen von Laufzeitmessungen bezüglich variierender Rechenleistung und stellen eine Methode zum Vergleich der Laufzeitkomplexität verschiedener Algorithmen, basierend auf den hardwareabhängigen Laufzeitmessungen des Middlebury Benchmarks, vor. Ausgehend hiervon, stellen wir eine Methode zur Abschätzung der Echtzeit-Möglichkeiten eines Algorithmus bei festgelegter Problemgröße auf gegebenen Geräten, mit vom Hersteller bestimmter oder gemessener Rechenleistung, vor. Abschließend argumentieren wir, dass die Problemgröße, die Rechenleistung des Gerätes und die Laufzeitkomplexität des Algorithmus direkt mit der Matching-Rate, welche in Frames pro Sekunde (FPS) angegeben ist, zusammenhängen.
description: Stereo matching is one of the first steps in the process of calculating 3D information from two 2D images. To triangulate a 3D point from two corresponding 2D features, the displacement in pixels, or the so-called disparity, must be estimated. From the estimated per-pixel disparity, using a projective camera model, 3D data for large portions of an image may be calculated. The 3D scene information can be used in applications ranging from obstacle detection and collision avoidance systems in the automotive industry to pick-and-place or human safety systems in the robotics industry. As time is an important factor in most of these applications, the subject of real-time stereo matching has gained importance while quality and accuracy aspects retain their importance. Benchmarks such as the KITTI Benchmark or the Middlebury Benchmark aim at providing stereo test data as well as ground truth to evaluate different matching algorithms against each other with regard to accuracy, coverage and runtime. However, they fall short in measuring the computational efficiency as the reported runtime as well as the real-time capability of the listed stereo matching algorithms are highly hardware dependent. In this thesis we explore the possibilities of real-time stereo matching and the constraints imposed by the used hardware. Therefore, we implemented a stereo matching algorithm in Open Computation Language (OpenCL) in order to evaluate the runtime of a specific algorithm on multiple devices. Using this runtime data, we discuss the limitations of runtime measurements with respect to varying computational power. Further, we suggest a method to compare the efficiency of various algorithms based on the reported runtime and hardware data, which is provided by the Middlebury Benchmark. This enables us to estimate the real-time capability of a given algorithm with a known problem space size on an arbitrary device with a manufacturer specified or measured performance figure. Finally, we observe that the problem space size, the device performance figure and the algorithm’s runtime complexity directly correlate with the matching rate given in Frames per Second (FPS).