2.1 Clustering: Bildsegmentierung

Beschreibe das Problem der Bildsegmentierung!

Wie sieht der Bild-Graph zu einem Bild aus?

Wie lässt sich das Bildsegmentierungsproblem formal mit Graphen beschreiben?

Wie lässt sich das Bildsegmentierungsproblem formal mit Graphen beschreiben, wenn zu jedem Pixel $u$ zusätzlich Wahrscheinlichkeiten $a(u)$ und $b(u)$ vorliegen, dass $u$ zum Vorder- bzw. Hintergrund gehört?

Wie lässt sich das erste Segmentierungsproblem (Modell 1) lösen?

Erinnerung:

Eingabe: Ungerichteter Graph $G=(V,E,w)$ mit Kantengewichten $w(e) \geq 0, e\in E$
Aufgabe: Bestimme einen Schnitt $(A,B)$ von $G$ mit minimalen Kosten $w(A,B)$

Wie lässt sich das zweite Segmentierungsproblem (Modell 2) lösen?

Erinnerung:

Eingabe: Ungerichteter Graph $G=(V,E,a,b,w)$ mit Knotengewichten $a(v)\geq 0$ und $b(v)\geq 0, v\in V$ sowie Kantengewichten $w(e) \geq 0, e\in E$
Aufgabe: Bestimme einen Schnitt $(A,B)$ von $G$ mit maximaler Qualität $q(A,B)= a(A) + b(B) - w(A,B)$

Sei $G=(V,E,w)$ mit Kantengewichten $w(e)\geq 0, e\in E$ und $A\subseteq V$.
Wie ist der am stärksten mit $A$ verbundene Knoten definiert?

Sei $G=(V,E,w)$ mit Kantengewichten $w(e)\geq 0, e\in E$ und $s,t\in V$.
Wie ist der Graph $G'$ definiert, den man aus $G$ durch Verschmelzen der Knoten $s$ und $t$ erhält?

Wie läuft der Algorithmus von Stoer und Wagner auf $G=(V,E,w)$ ab?

 TODO