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). Alternativ können Sie auch Bildabschnitte (mit bspw. Paint) markieren und als vorgefertige Masken in den Programm-Code laden.
   
   Ü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 Graph Cut Inferenz. Dabei können Sie ruhig vorgefertigte Packages verwenden, da max-flow von Grund auf zu implementieren ziemlich aufwändig sein kann.
   
   Hinweise:
   • 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 kleines \(\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.