Segmentation-based stereo and motion with occlusions

Abstract

In einem Shape-from-Stereo-Ansatz werden zwei Bilder aus leicht unterschiedlichen Perspektiven aufgenommen. Die Aufgabe eines Stereoalgorithmus ist es dann, korrespondierende Pixel in beiden Bildern zu identifizieren, welche Projektionen des gleichen Punktes in der Szene darstellen. In einem Standard-Stereo-Setup ist es bekannt, dass korrespondierende Punkte auf derselben horizontalen Scanlinie zu finden sind, sodass das Korrespondenzproblem auf eine eindimensionale Suche beschränkt werden kann. Der Offset zwischen den X-Koordinaten im linken und dem rechten Bild wird dann als Disparität bezeichnet, und diese Disparität ist invers proportional zum Tiefenwert eines Punktes. Die Zuordnung eines Pixels zu seiner korrekten Disparität stellt jedoch ein fundamentales Problem des Maschinellen Sehens dar. Obwohl umfassende Literatur vorhanden ist, liefern herkömmliche Methoden schlechte Ergebnisse in gewissen Bildbereichen. So versagt der Korrespondenzfindungsprozess oft aufgrund des Nichtvorhandenseins von Bildmerkmalen, die zum eindeutigen Auffinden der gesuchten Pixelkorrespondenz im anderen Bild nötig wären (untexturierte Regionen).<br />Darüber hinaus sind die Korrespondenzen mancher Pixel im anderen Bild verdeckt. Da Verdeckungen vor allem in der Nähe von Disparitätsunstetigkeiten auftreten, ist es besonders schwierig Objektgrenzen präzise zu rekonstruieren. Eine große Anzahl von Stereoalgorithmen scheitert in diesem Sinne, da sie die Tatsache, dass Verdeckungen vorhanden sind, einfach ignorieren.<br />In dieser Arbeit präsentieren wir zwei neue Stereoalgorithmen, welche die inhärenten Schwierigkeiten in der Stereokorrespondenzbildung mittels einer Zerteilung des Referenzbildes in Segmente gleichartiger Farbe bewältigen. Unsere Annahme ist, dass die Disparität innerhalb eines derartigen Segmentes kontinuierlich variiert, während Disparitätsunstetigkeiten mit den Segmentgrenzen zusammenfallen. Beide Algorithmen repräsentieren die Disparitäten anhand von Layern und modellieren das Stereoproblem in zwei Schritten. Im ersten (Layer Extraction) Schritt beantworten wir die Frage: Was sind jene ebenen Oberflächen (wir bezeichnen diese als Layer), die in der Szene dominant vorhanden sind? Diese Layer werden durch das Clustern anfänglicher Disparitätssegmente gefunden. Im zweiten (Layer Assignment) Schritt beschäftigen wir uns mit der schwierigeren Frage: Welche Teile des Bildes sollen welchem Layer zugeordnet werden und wo treten Verdeckungen auf? Für den ersten Algorithmus dieser Arbeit entwickeln wir eine neuartige Kostenfunktion, welche die Qualität einer Zuordnung von Segmenten zu Layern mittels einer Bildwarpingoperation misst. Wir zeigen, dass diese Warpingoperation auch dazu verwendet werden kann, um Verdeckungen in beiden Bildern zu erkennen. Ein gieriger Algorithmus wird dann zur Optimierung dieser Kostenfunktion verwendet. Dieser Optimierungsalgorithmus ist vom Rechenaufwand her effizient, läuft jedoch Gefahr, in einem lokalen Optimum stecken zu bleiben. Um diese Schwäche zu bewältigen, beschreiben wir einen zweiten Algorithmus zum Lösen des Layer Assignment-Problems, welcher von einer kürzlich publizierten, robusten Optimierungstechnik Verwendung macht, nämlich Graph-Cuts. Die Neuheit unseres Ansatzes liegt darin, dass wir zeigen, wie segmentierungsbasiertes Stereo in einem Graph-Cut-Ansatz formuliert werden kann, sodass Verdeckungen explizit modelliert werden. Beide Methoden werden dann auf das nahe verwandte Problem der Berechnung des optischen Flusses (oder Bewegungsberechnung) erweitert. Im Unterschied zu Stereo ist der Verschiebungsvektor in diesem Problem ein zweidimensionaler.<br />In unseren Experimenten demonstrieren wir, dass unsere Methoden Resultate von guter Qualität generieren, vor allem in Regionen mit schwacher Textur und nahe an Disparitäts-/Bewegungsunstetigkeiten.<br />Darüber hinaus erzielen die vorgestellten Stereoalgorithmen exzellente Ergebnisse auf der Middlebury-Stereoevaluierungswebseite.<br />

Given two images recorded from slightly different perspectives, a shape-from-stereo approach identifies corresponding points in both images that are projections of the same point in the scene. In a standard stereo setup, such corresponding pixels are known to lie on the same horizontal scanline, so that this correspondence problem is reduced to a one-dimensional search task. The offset between x-coordinates in the left and right images is then referred to as disparity, and a pixel's disparity is inversely proportional to the pixel's depth.<br />However, assigning each point to its correct disparity is a fundamental problem in computer vision. Although there is a large body of literature, common stereo methods still show poor performance in some image areas. Firstly, matching often fails in the absence of discriminative image features that can be uniquely matched in the other view (untextured regions). Secondly, some pixels' matching points are occluded in the second image. Since occlusions occur at disparity discontinuities, it is specifically challenging to precisely outline object boundaries. A large number of stereo algorithms fail in this respect, since the fact that there are occlusions is simply ignored.<br />In this thesis, we propose two novel stereo algorithms that tackle the inherent problems in stereo matching by dividing the reference image into segments of homogeneous colour. We assume that disparity inside such segments varies smoothly, while disparity discontinuities coincide with the segment borders. Both algorithms make use of a layered representation and model the stereo task as a two step problem. In the first (layer extraction) step, we answer the question: What are the dominant disparity planes (which we refer to as layers) likely to occur in the scene? These layers are extracted by clustering a set of initial disparity segments. In the second (layer assignment) step, we then focus on the more difficult question: Which part of the image is covered by which layer and where do occlusions occur? For the first algorithm presented in this thesis, we develop a novel global cost function that measures the goodness of an assignment of segments to layers by image warping. We show that image warping can as well be used to detect the occlusions in both images. This cost function is then optimized by a greedy algorithm, which is computationally efficient, but can get trapped in a local optimum. In order to overcome this weakness, we present a second algorithm for the layer assignment task that makes use of a recent robust optimization scheme, namely graph-cuts. The novelty of this approach lies in that we show how segmentation-based stereo matching can be formulated in a graph-cut approach with explicitly modelling occlusions. Both methods are then extended to the closely related optical flow (or motion) problem. As opposed to stereo, the displacement vector for this problem is a two-dimensional one.<br />In the experimental results, we demonstrate that our methods produce good-quality results, especially in regions of low texture and close to disparity/motion boundaries. Moreover, our stereo algorithms show excellent results on the Middlebury stereo evaluation website.