Zwei Augen, eine Frage

Halten Sie einen Finger auf Armeslänge vor sich und betrachten Sie ihn, während Sie erst das eine, dann das andere Auge schließen. Der Finger springt seitlich gegen den Hintergrund. Bringen Sie ihn näher, und der Sprung wird größer. Dieser Sprung — die Uneinigkeit Ihrer beiden Augen darüber, wo etwas ist — ist der gesamte Rohstoff der Tiefenwahrnehmung.

Ein Computer sieht genauso, sofern er zwei Kameras wenige Zentimeter voneinander entfernt hat. Die Kameras sind so ausgerichtet, dass jeder Punkt der realen Welt in beiden Bildern in derselben horizontalen Zeile landet; er verschiebt sich immer nur nach links oder rechts. Diese horizontale Verschiebung heißt Disparität. Nahe Dinge verschieben sich stark, ferne kaum, und der Zusammenhang ist einfach: Die Tiefe ist proportional zum Kehrwert der Disparität. Rekonstruieren Sie die Disparität an jedem Pixel, und Sie haben die Form der Szene rekonstruiert.

Damit fällt die ganze Aufgabe auf eine einzige, immer wiederholte Frage zusammen: Wie weit muss ich für dieses Pixel im linken Bild schieben, um seinen Zwilling im rechten Bild zu finden? Die möglichen Verschiebungen — 0, 1, 2, … bis zu einem Maximum — sind die Labels. Für jedes Pixel ein Label zu wählen, ist das Labeling-Problem im Herzen dieser Publikation.

Wie erkennt ein Pixel seinen Zwilling?

Indem es seine Nachbarschaft betrachtet. Wir nehmen einen kleinen Ausschnitt um das linke Pixel, schieben ihn über die möglichen Positionen im rechten Bild und messen bei jeder Verschiebung, wie verschieden die beiden Ausschnitte sind — wir summieren die quadrierten Helligkeitsunterschiede. Die Verschiebung, bei der die Ausschnitte am besten passen (niedrigste Kosten), ist unsere Antwort. Diese Zahl pro Pixel und pro Label sind die Datenkosten: wie sehr es „wehtut“, einem bestimmten Pixel eine bestimmte Disparität zuzuweisen.

Ziehen Sie herum, und Ihnen fallen zwei Regime auf. Auf den strukturierten Flächen hat die Kostenkurve ein scharfes, eindeutiges Minimum — der Ausschnitt passt an genau eine Stelle. Parken Sie die Marke aber auf der glatten, nahezu gleichförmigen Region oben, wird die Kurve flach: Dutzende Verschiebungen passen fast gleich gut. Die Daten haben keine Meinung. Wenn Sie dann trotzdem den tiefsten Punkt wählen, raten Sie im Grunde.

Das ist der Riss, der durch das ganze Problem läuft. Für jedes Pixel unabhängig das kostengünstigste Label zu wählen, ergibt eine klare Antwort dort, wo das Bild reich an Struktur ist, und reines Rauschen dort, wo es das nicht ist. Um es besser zu machen, müssen die Pixel aufhören, allein zu entscheiden — und genau dort setzt das nächste Kapitel an.

Das Tauziehen

Lässt man jedes Pixel sein eigenes Lieblingslabel wählen, erhält man eine Tiefenkarte, die aussieht wie Fernsehrauschen — im Mittel richtig, überall dort falsch, wo es zählt. Die Abhilfe kommt aus einer Tatsache über die Welt: Reale Oberflächen sind überwiegend glatt. Ihr Schreibtisch ändert seine Tiefe nicht alle Millimeter. Benachbarte Pixel gehören fast immer zusammen.

Also fügen wir eine zweite Kostenart hinzu, die in die Gegenrichtung zieht. Jedes Mal, wenn zwei benachbarte Pixel verschiedene Labels erhalten, verlangen wir eine feste Strafe — nennen wir sie λ. Es spielt keine Rolle, ob sich die Labels um eins oder um zwanzig unterscheiden; jede Uneinigkeit kostet denselben pauschalen Betrag. (Diese Regel „alle Uneinigkeiten sind gleich“ macht daraus das Potts-Modell, entlehnt aus der statistischen Physik.) Die Gesamtkosten eines Labelings sind dann die Summe zweier konkurrierender Kräfte:

Jetzt entscheidet kein Pixel mehr allein. Dreht man λ hoch, muss das Labeling für Uneinigkeit zahlen, sodass es das Rauschen bereinigt, indem selbstsichere Nachbarn verrauschte überstimmen. Dreht man zu weit hoch, beginnt es echte Details zu tilgen und kleine Objekte in ihre Umgebung einzuebnen, weil ihr Erhalt zu viele Randstrafen kostet. Irgendwo dazwischen liegt der Sweet Spot.

Achten Sie auf die karmesinroten Linien — sie markieren jedes Nachbarpaar, das uneinig ist, also genau dort, wo die Glattheitskosten anfallen. Bei λ = 0 ist die Karte von ihnen durchzogen, und der Fehler ist hoch. Schieben Sie λ nach oben: Das Rauschen löst sich auf, das Karmesin wird dünner, und der Fehler fällt auf sein Minimum. Schieben Sie weiter, und sehen Sie zu, wie der Fehler wieder steigt, während die kleine helle Region ganz verschluckt wird. Die Fehler-über-λ-Kurve hat ein klares Tal — eine Vorschau auf ein Diagramm, dem wir am Ende wiederbegegnen, gezeichnet aus den echten Experimenten.

Hier ist der Haken, der daraus ein Forschungsproblem macht statt einer Hausaufgabe. Das Labeling zu finden, das diese Energie wirklich minimiert — den echten Grund der Landschaft —, ist NP-schwer, sobald man drei oder mehr Labels hat. Das Spielzeug oben tut nur mit einer schnellen lokalen Heuristik so, als ob. Um es richtig und schnell zu machen, brauchen wir ein schärferes Werkzeug.

Ein Schnitt ist eine Antwort

Das vorige Kapitel endete an einer Wand: Die Energie zu minimieren ist NP-schwer, sobald es drei oder mehr Labels gibt. Doch in diesem schweren Problem verbirgt sich ein viel leichteres — und es erweist sich als das nützlichste Werkzeug des ganzen Feldes. Gehen Sie auf nur zwei Labels herunter, und das Unmögliche wird nicht nur lösbar, sondern schnell.

Stellen Sie sich die einfachste Version der Aufgabe vor: Jedes Pixel ist entweder Objekt oder Hintergrund. Jedes Pixel hat Datenkosten für jede Wahl (dunkle Pixel wären lieber Hintergrund, helle lieber Objekt), und Nachbarn zahlen weiterhin die Potts-Strafe, wenn sie uneinig sind. Wir wollen die günstigste Aufteilung. Es gibt 2^{(Anzahl der Pixel)} mögliche Aufteilungen — astronomisch viele — und dennoch finden wir die allerbeste im Handumdrehen. Hier ist der Kniff, der das möglich macht.

Verwandeln Sie das Bild in ein Rohrleitungsnetz

Bauen Sie einen Graphen. Fügen Sie zwei besondere Knoten hinzu: eine Quelle für „Hintergrund“ und eine Senke für „Objekt“. Verbinden Sie jedes Pixel mit beiden, mit Rohrdurchmessern gleich seinen zwei Datenkosten. Verbinden Sie dann benachbarte Pixel untereinander mit Rohren der Weite λ. Und nun stellen Sie eine Frage, die unverwandt klingt: Was ist die billigste Menge von Rohren, die man durchtrennen könnte, um die Quelle vollständig von der Senke zu trennen?

Dieser minimale Schnitt ist die Antwort. Jedes Pixel landet auf der Quellenseite oder der Senkenseite — und diese Partition ist ein Labeling. Die Kosten des Schnitts sind exakt die Energie dieses Labelings: durchtrennte Datenrohre sind die Datenkosten, die Sie zahlen, und jedes durchtrennte Nachbarrohr ist eine uneinige Grenze. Der billigste Schnitt ist also das Labeling niedrigster Energie, und ein jahrhundertealtes Resultat (Max-Flow gleich Min-Cut) erlaubt uns, ihn in Polynomialzeit zu finden.

Schieben Sie λ von null hoch. Bei null folgt der Schnitt einfach der Vorliebe jedes einzelnen Pixels, und die Grenze ist zerfranst und jagt jedem Rauschfleck hinterher. Erhöhen Sie λ, und die Grenze zahlt für Länge, sodass sie sich enger um das echte Objekt legt und das Rauschen überstimmt wird — dasselbe Tauziehen wie zuvor, nun aber exakt gelöst. Die Zahl, die dabei ausgegeben wird, ist nicht die beste Schätzung einer Heuristik; sie ist beweisbar das globale Minimum. Es gibt keine bessere Aufteilung.

Zwei Labels sind also ein gelöstes Problem. Der Haken ist natürlich, dass Stereo sechzig hat. Der Schnitt kann nur eine Grenze zwischen zwei Regionen ziehen, und echte Tiefenkarten haben viele. Der naheliegende Zug — und der, den das Feld gegangen ist — besteht darin, diese Zwei-Label-Superkraft als wiederholten Zug einzusetzen: immer wieder zu fragen „Sollte irgendeines dieser Pixel zu Label α wechseln?“ und einen Min-Cut entscheiden zu lassen. Das ist α-Expansion. Die nächsten beiden Kapitel gehen mit demselben Werkzeug einen anderen, schärferen Weg.

Antworten umsonst

Hier ist ein Gedanke, der zu schön klingt, um wahr zu sein. Das vollständige Problem ist NP-schwer — aber was, wenn Sie, bevor Sie den teuren Löser bezahlen, das korrekte Label für die meisten Pixel beweisen könnten, allein mit den billigen Zwei-Label-Schnitten aus dem letzten Kapitel? Nicht raten. Beweisen. Und was, wenn „die meisten“ achtzig oder neunzig Prozent des Bildes hieße?

Genau das leistet Persistenz — auch partielle Optimalität genannt. Die Idee, die auf Ivan Kovtun zurückgeht, ist entwaffnend einfach. Wählen Sie ein Label, sagen wir „Disparität 7“, und stellen Sie dem ganzen Bild eine einzige binäre Frage: Label 7 oder alles außer 7? Das ist ein Zwei-Label-Problem, ein Min-Cut beantwortet es also exakt. Die Pixel, die der Schnitt der „7“ zuweist, kommen mit einer Garantie: Es existiert ein globales Optimum des vollständigen Problems, in dem diese Pixel wirklich 7 sind.

Sie sind persistent. Sie können sie festschreiben und nie wieder anschauen. Stellen Sie diese binäre Frage einmal pro Label, und Sie schälen jedes Mal ein zertifiziertes Stück der optimalen Lösung heraus — für den Preis von je einem Max-Flow.

Gehen Sie es Schritt für Schritt durch. Jeder Klick führt einen Hilfsschnitt aus und friert die Pixel ein, die er beweisen kann, indem er sie einfärbt. Nach allen sechs ist das Grau nahezu verschwunden: Der weit überwiegende Teil des Bildes ist gelöst und als optimal zertifiziert, während nur ein hartnäckiger Rest — die wirklich mehrdeutigen Pixel, überwiegend entlang der Objektkanten — an den teuren Löser übergeben wird. Genau darum geht es: das NP-schwere Problem zu verkleinern, bevor man je dafür bezahlt.

Und das ist kein Effekt im Spielzeugmaßstab. Auf dem üblichen Middlebury-Stereo-Benchmark reichte der Anteil, den die Methode kostenlos zertifiziert, von etwa 50 % bis 93 % des Bildes (die Balken oben sind die tatsächlichen Zahlen der Publikation). Die teure zweite Phase muss dann nur noch lösen, was übrig bleibt — und deshalb ist die gesamte Pipeline am Ende rund zehnmal schneller als der bisherige Stand der Technik. Diese Laufzeiten sehen wir im letzten Kapitel.

Doch etwas ist hier noch verschwenderisch. Wir haben einen Schnitt pro Label ausgeführt — sechzig Schnitte für ein Stereo-Problem mit sechzig Disparitäten. Der zentrale Beitrag der Publikation besteht in der Einsicht, dass man keine sechzig braucht. Man braucht ungefähr sechs. Das ist das nächste Kapitel.

Von k Schnitten zu log k

Das vorige Kapitel brauchte einen Min-Cut pro Label. Das ist der verschwenderische Teil, und ihn zu beheben ist das Herz der Publikation. Die Lösung ist eine Idee, die Sie täglich verwenden, ohne sie zu benennen: Um eine Zahl zwischen 1 und 60 zu finden, prüfen Sie nicht alle sechzig — Sie fragen „höher oder tiefer?“ und halbieren jedes Mal den Bereich. Binäre Suche. Der Kniff besteht darin, diese Suche für alle Pixel gleichzeitig durchzuführen, wobei bei jedem Schritt ein einziger Min-Cut über das ganze Bild entscheidet.

Legen Sie die möglichen Labels als Blätter eines balancierten Binärbaums aus. Die Wurzel hält den ganzen Bereich; ihre zwei Kinder teilen ihn in Hälften; deren Kinder teilen erneut, und so weiter hinunter bis zu einzelnen Labels. Nun gehen Sie den Baum Ebene für Ebene hinab. Auf jeder Ebene wird dem gesamten Bild eine einzige binäre Frage gestellt — Liegt dein Label in der unteren Hälfte deines aktuellen Bereichs oder in der oberen? —, und weil das ein Zwei-Label-Problem ist, beantwortet ein Min-Cut sie exakt für alle Pixel gleichzeitig. Jede Antwort halbiert den Bereich jedes Pixels.

Halbieren Sie sechzehn Labels viermal, und Sie sind bei einem. Die Tiefenkarte löst sich aus einer flachen Leere in grobe Bänder auf, dann in feinere, dann in volle Detailschärfe — in vier Schnitten statt sechzehn.

Die Rechnung ist die Pointe. Kovtuns ursprüngliche Methode brauchte k Max-Flows; diese braucht die Tiefe des Baums, also etwa log₂ k. Die Schnitte einer Ebene wirken auf disjunkte Pixelmengen — jedes Pixel steckt in genau einem Teilproblem —, sodass eine ganze Ebene nicht mehr kostet als ein einziger Max-Flow auf dem Originalbild. Sechzehn Labels: vier Schnitte. Sechzig Labels: sieben. Je größer die Labelmenge, desto größer der Gewinn — und genau deshalb zählt es für Stereo, wo k groß ist.

Das ist der Beitrag in einem Satz: dieselbe zertifizierte Antwort, die Kovtun in k Max-Flows liefert, gewonnen in ⌈1 + log₂ k⌉ davon. Kombinieren Sie ihn mit der Persistenz des letzten Kapitels — den größten Teil des Bildes umsonst beschriften, in logarithmisch wenigen Schnitten, dann den kleinen Rest einem schnellen Löser übergeben —, und Sie haben die gesamte Pipeline. Das Schlusskapitel zeigt, was das an tatsächlicher Laufzeit einbringt, und ein Ergebnis, das uns wirklich überrascht hat.

Die Auszahlung

Theorie ist nur begrenzt viel wert; die Frage, die eine Praktikerin stellt, lautet „wie schnell und wie gut?“. Also haben wir es auf dem üblichen Prüfstand für dieses Problem laufen lassen — dem Middlebury-Stereo-Benchmark —, gegen die schnellste publizierte Methode für dieselbe Aufgabe. Das kam zurück.

Die erste Phase — den größten Teil des Bildes umsonst zu beschriften, in logarithmisch wenigen Schnitten — läuft rund zehnmal schneller als der bisherige Stand der Technik („Reduce“). Selbst die vollständige Pipeline, die anschließend den nicht persistenten Rest mit einem schnellen Löser bereinigt, bleibt komfortabel vorn. Bei den leichten Bildern, wo fast alles zertifiziert ist, ist das Ganze in ein paar hundert Millisekunden fertig.

Geschwindigkeit war aber erwartbar. Das Ergebnis, das uns wirklich überrascht hat, betraf die Qualität. Schauen Sie sich die tatsächlichen Disparitätskarten an — wechseln Sie zwischen dem billigen zertifizierten Labeling und der vollständigen Optimierung:

Interaktiv · zwischen billigem und vollem Ergebnis wechseln

Kovtun — zertifiziert, billig Vollständige Optimierung Grundwahrheit

Showing: Kovtun’s certified labeling

Sie sind kaum zu unterscheiden. Und als wir den Fehler gegen die Grundwahrheit maßen, war das billige Kovtun-Labeling in der Mehrzahl der Fälle genauer als die vollständige α-Expansions-Lösung — obwohl α-Expansion eine niedrigere Energie erreicht. Das klingt paradox, bis man sich erinnert, was Energie ist: ein Modell der Welt, nicht die Welt selbst. Die Energie auf ihr absolutes Minimum zu treiben, optimiert das Modell härter — und mit ihm dessen kleine Verzerrungen. Die zertifizierten Pixel sind genau jene, bei denen die Daten von vornherein sicher waren — der Teil, den wir beweisen können, ist also zugleich der Teil, der am häufigsten stimmt.

Die praktische Lesart ist befreiend: Für ein zeitkritisches System — einen Roboter, eine Kamera, irgendetwas mit einer Frist — können Sie nach der billigen Phase aufhören und ein Labeling ausliefern, das schnell und, auf diesen Benchmarks, oft besser ist. Das teure globale Optimum ist optional.

Warum eine Stereo-Publikation in ein KI-Portfolio gehört

Diese Arbeit ist älter als die Deep-Learning-Ära, und Stereo-Tiefe ist heute weitgehend ein gelerntes Problem. Ich behalte sie hier für das, was sie darüber zeigt, wie ich denke — und das ist nicht veraltet. Drei Gewohnheiten ziehen sich durch sie und durch alles, was ich seither gebaut habe. Erstens: die Struktur finden, die ein schweres Problem leicht macht — die ganze Publikation dreht sich um die Beobachtung, dass in einem k-wertigen Labeling eine binäre Suche steckt. Zweitens: Garantien verdienen, statt auf sie zu hoffen — Persistenz ist ein Beweis, keine Heuristik, und zu wissen, welche Ausgaben zertifiziert sind, ist genau die kalibrierte Zuversicht, um die sich moderne ML-Systeme immer noch bemühen. Drittens: den Abstand zwischen Zielfunktion und Ziel respektieren — die Überraschung in dieser Publikation ist eine kleine, freundliche Fassung der Reward-Hacking- und Überoptimierungsprobleme, die heute viel an der Front der KI-Arbeit ausmachen.

Schnellere Algorithmen, beweisbare Teilantworten und ein gesundes Misstrauen gegenüber der Zielfunktion, die man minimiert: Das ist ein Werkzeugkasten, und er lässt sich übertragen. Wenn Ihr Team an Problemen arbeitet, bei denen diese Instinkte helfen würden, spreche ich gern darüber.