Aufgabe: Bildsegmentierung mit einem Hidden Markov Model

(Deutsch: „verdecktes Markowmodell“)

Problemstellung:
Die Aufgabe besteht darin ein Bild in Vordergrund und Hintergrund zu segmentieren.
Formell möchten wir allen Pixeln eines von zwei Labeln zuweisen und nutzen dazu statistische Evidenz dafür die Zuweisung durchzuführen.
Dazu Modellieren wir ein Markov Random Field (MRF) bei dem die Observablen den Pixelfarben jedes Pixels entsprechen:

• Jedes Pixel des Bildes enspricht zwei Zufallsvariablen:
  • der latenten Variable \(x_i\in\{0,1\}\), die Vordergrund von Hintergrund unterscheidet
  • die Pixelfarbe \(y_i \in [0,1]^3\), die wir direkt beobachten können
• Wir nehmen an, dass die Labels ein MRF bilden, bei dem die Farben den beobachtbaren Datenterm darstellen:
  • Das Label-MRF ist dabei ein paarweises MRF, bei dem die vier benachbarten Pixel (wie in der Vorlesung dargestellt) verbunden sind.
  • Sei \(\phi(x_i|y_i)\) der Datenterm, d.h. die Likelihood der Label gegeben die Pixelfarbe. Das Ziel ist es \(\phi\) aus den Daten zu ermitteln bzw. zu lernen.
  • Sei \(\psi(x_i,x_j)\) ein Regularisierungsterm für alle zwei Paare beliebige benachbarter Pixel \(x_i\) und \(x_j\).
    Wir definieren diesen als simples Potential der Form \[ \psi(x_i,x_j) = \left\{\begin{matrix} 1,& \text{falls} & x_i = x_j \\ \lambda & \text{sonst} & \end{matrix}\right., \] wobei \(0 < \lambda < 1\) (fest aber beliebig).
    
    Dieser Term bestraft alle Pixel, deren Label sich unterscheidet. Mit anderen Worten möchten wir harte Kanten beibehalten.
• Die Wahrscheinlichtkeitsverteilung der Segmentierung ist insgesamt durch \[ p(x_1,\dots,x_n) = \frac{1}{Z} \prod_{i=1}^n \phi(x_i) \prod_{j\in N(i)} \psi(x_i,x_j), \] gegeben, wobei \(N(i)\) die Indizes der Nachbarn des Pixels \(x_i\) darstellt.

Aufgaben:
Das Problem, eine Maximum-a-posteriori-Zuordnung der Label \(x_1,\dots x_n \in \{0,1\}\) zu finden ist ein submodulares Problem und kann beispielsweise durch den Graph Cut (oder auch min-cut/max-flow) Algorithmus exakt gelöst werden (siehe VL). Wir nutzen diesen nun, um eine Bildsegmentierungs-Pipeline zu bauen.

1. Als erstes benötigen wir einen geeigneten Datenterm. Für einfache Bilder können wir Vorder- und Hintergrundverteilungen lernen, indem wir einfach eine 3D-Gaußverteilhung an die Farben fitten (also wie in vorherigen Aufgaben die Mittelwerte und Kovarianzen der gesampelten Pixeln berechnen). Die übliche Benutzerinteraktion besteht darin den Nutzer zu bitten einige Bildabschnitte zu markieren, um Hintergrund- & Vordergrund-Farbmuster anzugeben (siehe etwa Abbildung 2(e) in dem oben verlinkten Paper zu GrabCut).
   
   Übrigens: Das System, dass im GrabCut-Paper vorgestellt wird nutzt Gaußsche Mischmodelle (engl. gaussian mixture model), die für komplexe Bildinhalte besser geeignet sind. Eine leichter zu implementierende Alternative verwendet eine Dichte-Rekonstruktion im 3D-Raum aus einigen wenigen Farb-Samples (z.B. durch Filtern mit einem Gauß, oder durch Berechnung der \(k\)-nächsten Nachbarn gewichtet durch \(1/r^3\) als Dichte für jeden gesampelten Punkt, wobei \(r\) den Abstand des betrachteten Punktes zu seinen \(k\)-ten nächsten Nachbarn darstellt (adaptive Glättung).
2. Wir können nun inferieren: Als erstes, nehmen wir den Datenterm und bestimmen die Lösung durch pixelweise Vergleiche der Wahrscheinlichtkeitsdichten. Im Grunde kann hier ein Schwellwert benutzt werden, nur dass zwei Verteilungen verglichen werden. Das Ergebnis sollte ziemlich verrauscht sein.
3. Implementieren Sie nun eines der beiden in der Vorlesung vorgestellten Verfahren: Loop Belief Propagation oder Graph Cut Inferenz (optional beides). Bei der Graph Cut-variante können sie ruhig vorgefertigte Packages verwenden, da max-flow von Grund auf zu implementieren ziemlich aufwändig sein kann.
   
   Hinweise:
   • Loop BP: Starten Sie damit BP zu implementieren und setzen Sie die Startverteilung (Erstschätzung, siehe etwa Folie 20 in der VL S08) im Modell auf das Ergebnis aus Aufgabenteil 2.
     Für einen Forward- und Backwardpass müsste das Modell zyklenfrei sein, ist es jedoch nicht im Falle von Bildern. Wir lösen dies, indem wir einfach ignorieren, dass es Zykel gibt. Konkret bedeutet das, dass wir den Algorithmus entweder Spalten- oder Zeilenweise oder sogar in zufällige Richtungen propagieren. (Hier kann erneutes Ausführen das Ergebnis verbessern).
   • Graph Cut: Graph Cut funktioniert nur im Spezialfall, dass wir eine binäre Segmentierung lösen möchten. Die Kanten zum \(1\) bzw. \(0\) Knoten sind hierbei gerade wieder die Wahrscheinlichtkeiten aus Aufgabenteil 2. Die Kanten zwischen den Knoten reduzieren sich im Fall von Graph Cut nur auf den Fall, dass das Labeling unterschiedlich ist, mit anderen Worten haben alle paarweisen Nachbarn das Kantengewicht \(\lambda\).
4. Zuletzt verbessern wir das Ergebnis ein weiteres Mal, indem wir die Kanten explizit in das MRF einbeziehen: Gewichten Sie den Parameter \(\lambda\) mit der Größe der localen Farb-Gradienten. Dies ist ein paarweiser Term; man kann die Differenzen oder einen Duchschnitt der lokalen Gradienten verwenden. Scharfe kanten haben so eine niedrige Strafe (also ein hohes \(\lambda\)). Ein geeigneter Ansatz ist, die neg-log-Wahrscheinlichtkeiten (nicht die Wahrscheinlichtkeiten selbst) auf \(\exp(-\sigma{-2} \cdot ||\nabla x_i||^2)\) zu setzen. So haben scharfe Gradienten wenig Einfluss beim Graph Cut.

Die Implementierung der gesamten Pipeline mit Graph Cut und einem guten Datenterm sollte State-of-the-Art-Ergebnisse liefern, bei denen minimale Benutzerinteraktion bereits zu überzeugenden Segmentierungen führt. Siehe das GrabCut-Paper für ein ganzes System, das auf dieser Idee aufbaut und durch die Verwendung eines guten Datenterms eine noch einfachere Benutzeroberfläche vorschlägt.