Programmieraufgabe 3 -- Bildverarbeitung

In dieser Programmieraufgabe wird die Anwendung von Graphalgorithmen in der Bildverarbeitung behandelt. Diese Aufgabe muss in Dreierteams bis zum 21.06. um 13:00 Uhr bearbeitet werden. Sie müssen sich nicht um die Umwandlung von Bildern in Graphen kümmern - dafür steht Ihnen die Klasse ImageConverter zur Verfügung.

Diese Programmieraufgabe besteht aus zwei Teilen. Sie implementieren:

  1. den Algorithmus von Dijkstra zur Kantenerkennung bei einer „Livewire Segmentation“.
  2. den Segmentierungsalgorithmus von Felzenszwalb und Huttenlocher, welcher auf minimalen Spannbäumen basiert.
Die vorgegebenen Dateien können wie üblich auf Artemis gefunden werden.

Vorgegebene Dateien und Datenstrukturen

ImageConverter.java

Die Klasse ImageConverter wandelt Bilder in ungerichtete, gewichtete Graphen um. Die Umwandlung ist wie folgt implementiert. Ein Graustufenbild mit der Auflösung \( X \times Y \) ist eine rechteckig angeordnete Menge von Pixeln, wobei jedem Pixel \( (x, y) \in \{0, \dots, X-1\} \times \{0, \dots, Y-1\} \) eine ganzzahlige Intensität \( I (x, y) \in \{0, 255\} \) zugeordnet wird. Dabei repräsentiert die Intensität \( 0 \) die Farbe schwarz und die Intensität \( 255 \) die Farbe weiß. Ein Graustufenbild wird folgendermaßen als Graph interpretiert: Jedem Pixel des Bilds wird ein Knoten im Graph zugeordnet. Für jeden Pixel \( (x, y) \) enthält der Graph bis zu acht Kanten zu den Knoten benachbarter Pixel; dabei sind die Nachbarn von \( (x, y) \) die Pixel \( (x+1,y) \), \( (x+1,y+1) \), \( (x,y+1) \), \( (x-1,y+1) \), \( (x-1,y) \), \( (x-1,y-1) \), \( (x,y-1) \) und \( (x+1,y-1) \), sofern diese jeweils existieren. Das Gewicht einer Kante entspricht dem Intensitätsunterschied der Pixel der Endpunkte der Kante. Repräsentiert beispielsweise der Knoten \( u \) den Pixel \( (x_u, y_u) \) und der Knoten \( v \) den Pixel \( (x_v, y_v) \), dann hätte eine Kante \( e \) zwischen \( u \) und \( v \) das Gewicht \( w (e) = | I (x_u, y_u) - I (x_v, y_v) | \). Die Klasse ImageConverter führt für jede Aufgabe noch Vor- bzw. Nachbearbeitungsschritte auf den Bildern durch. Details dazu finden Sie im letzten Beschreibungsabschnitt der jeweiligen Aufgabe.

Ihnen stehen folgende Methoden zur Verfügung:

Die Graph-Datenstruktur ist vorgegeben. Sie können und sollen diese jedoch anpassen und erweitern! Die Datenstruktur repräsentiert einen ungerichteten, gewichteten Graphen. Wenn Sie auf die Knoten oder Kanten zugreifen, erhalten Sie ein Objekt vom Typ List<Node> bzw. List<Edge>. Dabei handelt es sich um eine generische Implementierung einer Liste aus dem Java Collections Framework. In den spitzen Klammern hinter dem Typ List ist also der Datentyp eingetragen, welcher in dieser Liste gespeichert ist (entsprechend: Node bzw. Edge). Da List das Interface Iterator implementiert, können Sie mit einer For-Each-Schleife einfach über alle Elemente der Liste iterieren, ohne Indizes verwenden zu müssen. Zum Beispiel kann List für den Datentyp Edge folgendermaßen verwendet:

List<Edge> edges = myGraph.getEdges();
for (Edge e : edges) {
	// do something with e
}

UndirectedGraph.java

Diese Klasse beinhaltet und verwaltet Knoten und Kanten. Beim Einlesen eines Bildes durch die Klasse ImageConverter erhalten Sie ein Objekt dieses Typs.

Node.java

Diese Klasse repräsentiert einen Knoten. Jeder Knoten speichert in einer Liste Verweise auf seine inzidenten Kanten. Das heißt eine Kante ist nicht nur in der Klasse UndirectedGraph verlinkt, sondern auch von ihren beiden Endpunkten.

Da jeder Knoten auch ein Pixel des Bildes repräsentiert, werden auch die \(x\)- und die \(y\)-Koordinate des Pixels im Knoten gespeichert. Beide Werte werden durch die Klasse ImageConverter eingetragen und sind für die Implementierung der Algorithmen nicht relevant. Allerdings werden sie benötigt, um das Bild am Ende wieder rekonstruieren zu können.

Edge.java

Diese Klasse repräsentiert eine gewichtete Kante. Eine Kante speichert Verweise auf ihre beiden Endpunkte, die intern mit \(u\) und \(v\) bezeichnet werden.

Verweist ein Knotens \(x\) auf die Kante \(e\) zu einem Nachbarknoten \(y\), so ist nicht festgelegt, ob auf den Nachbarknoten \(y\) von \(x\) in \(e.u\) oder \(e.v\) verwiesen wird. Es müssen die Referenzen zu den Knoten verglichen werden, um zwischen dem Verweis auf \(x\) selbst und dem Verweis auf \(y\) unterscheiden zu können. Nutzen sie dazu die Methode getOtherEndpoint, welche Ihnen den richtigen Nachbarknoten zurück liefert.

Teilaufgabe A: Kantenerkennung

Motivation

Bei der Kantenerkennung ist das Ziel, Grenzen („Kanten“) zwischen Objekten im Bild zu finden. Moderne Bildbearbeitungsprogramme bieten oft ein magnetisches Auswahlwerkzeug an (in GIMP: „Magnetische Schere“). Damit lassen sich relativ einfach einzelne Objekte vom Hintergrund separieren. Eine spezielle Variante dieser Werkzeuge wird als „Livewire Segmentation“ bezeichnet. Dabei wird ein Startpixel auf einer Objektkante ausgewählt und dann der Mauszeiger um das Objekt herumgeführt. Die Software ermittelt dann selbstständig die Kante zwischen dem Mauszeiger und dem Startpixel. Aus algorithmischer Sicht kann dies meist zufriedenstellend mit der Berechnung des kürzesten Wegs im Bildgraph umgesetzt werden. Im Jahr 1995 publizierten Mortensen und Barrett den „Intelligent Scissors“ Algorithmus, der nach diesem Prinzip arbeitet. Dabei nutzten sie eine leicht abgeänderte Version von Dijktras Algorithmus zur Berechnung der kürzesten Wege.

Implementierung

Das Einlesen und Umwandeln des Bildes in einen ungerichteten, gewichteten Graphen übernimmt wieder die Klasse ImageConverter. Sie erhalten den Bildgraphen sowie zwei Knoten (\(s\) und \(t\)) des Graphen, welche den Startpixel und die Position des Mauszeigers im Bild repräsentieren. Ermitteln Sie daraus die Objektkante zwischen diesen Punkten. Implementieren Sie dazu Dijktras Algorithmus mit einer effizienten Priority Queue, um für die beiden vorgegebene Knoten \(s\) und \(t\) den kürzesten Weg von \(s\) nach \(t\) im Bildgraph zu berechnen. Nach der Berechnung soll jeder Knoten auf dem kürzesten Weg seinen Vorgänger auf diesem Weg in der Variable prev gespeichert haben (wie bereits in der Node Klasse vorgesehen). Implementieren Sie den Algorithmus bitte in der Klasse LiveWireSegmentation, welche sich im Package EdgeDetection befindet. Zumindest folgende muss vorhanden sein:

public class LiveWireSegmentation {
	/**
		* Performs the segmentation algorithm of Mortensen and Barrett on an undirected, weighted graph.
		* @param g the graph
		* @param s start node
		* @return graph including a shortest paths from s that can be traversed via the prev variable of each node
		*/
	public static UndirectedGraph MBShortestPath(UndirectedGraph g, Node s);
}

Beispiel

Eingabebild
Eingabebild
Segmentierung
Kantenerkennung ausgehend von Knoten \(s= (204, 282)\). Visualisiert wird der kürzeste Pfad zu Knoten \( (374, 476) \) in rot. Eventuell müssen Sie etwas in das Bild zoomen um den Pfad zu erkennen

Priority-Queue

Um Dijktras Algorithmus effizient zu implementieren benötigen Sie eine Priority-Queue. Allerdings besitzt die Implementierung der Java-API keine Decrease-Key“ Funktionalität. Daher haben wir für Sie in der Klasse PriorityQueue eine entsprechende Datenstruktur vorimplementiert. Diese Datenstruktur verfügt über insert, decreaseKey und extractMin Methoden und sie dürfen diese als Black-Box verwenden. Falls Sie möchten, können Sie aber die Queue auch selbst implementieren. Achten Sie jedoch darauf die asymptotische Laufzeit nicht zu verschlechtern!

Hinweise:

Teilaufgabe B: Bildsegmentierung

Motivation

Segmentierung ist eine typische Problemstellung in der digitalen Bildverarbeitung mit dem Ziel der Erkennung inhaltlich zusammenhängender Regionen eines Bildes. Ende der 1990er Jahre haben Felzenszwalb und Huttenlocher einen Algorithmus zur Bildsegmentierung entwickelt, der ähnlich funktioniert wie der Algorithmus von Kruskal zur Berechnung des minimalen Spannbaums.

Implementierung

Im Segmentierungsalgorithmus werden zusammenhängende Komponenten des Graphen identifiziert. Für jede bereits gefundene Komponente \( C \) ist die interne Differenz definiert als \( Int (C) = \max_{e \in MST (C, E)} w (e) \), also als das maximale Gewicht einer Kante des minimalen Spannbaums der Komponente. Für zwei Komponenten \( C_1 \) und \( C_2 \) ist die minimale interne Differenz definiert als \( MInt (C_1, C_2) = \min (Int (C_1) + \tau (C_1), Int (C_2) + \tau (C_2)) \). Dabei ist \( \tau \) eine Schwellwertfunktion, die definiert ist als \( \tau (C) = k / |C| \), wobei \( k \) ein Parameter des Algorithmus ist und \( |C| \) die Anzahl der Knoten der Komponente. Als Faustregel kann \( k = X + Y \) verwendet werden. Der folgende Pseudocode illustriert den Segmentierungsalgorithmus:

Sortiere die Kanten des Graphs aufsteigend nach Gewicht und sei \( e_1, e_2, \dots, e_m \) die resultierende Sortierung
Erstelle eine Komponente \( C_v = \{ v \} \)für jeden Knoten \( v \)
for q = 1 to m
	Bestimme die Endpunkte \( u \) und \( v \) der Kante \( e_i \) und die Komponenten \( C_u \) und \( C_v \) von \( u \) bzw. \( v \)
	if \( u \) und \( v \) befinden sich in unterschiedlichen Komponenten
		if \( w (e_i) \leq MInt (C_u, C_v) \)
			Vereinige die Komponenten \( C_u \) und \( C_v \)
		end if
	end if
end for

Der Segmentierungsalgorithmus von Felzenszwalb und Huttenlocher unterscheidet sich also insofern vom Algorithmus von Kruskal, dass Komponenten nur dann zusammengefügt werden, wenn eine zusätzliche Bedingung erfüllt ist. Aufgrund dieser Funktionsweise bilden jene Kanten, deren Endpunkte in einer Komponente vereinigt wurden einen minimalen Spannbaum der Komponente.

Programmieren Sie eine effiziente Implementierung des Algorithmus von Felzenszwalb und Huttenlocher mit Laufzeit \( O ((m + n) \log n) \) für Graphen mit \( n \) Knoten und \( m \) Kanten. Führen Sie die Vereinigung von Komponenten mit einer Union-Find Datenstruktur durch. Die entsprechende Klasse zur Implementierung dieser Datenstruktur heißt Component, ist im Unterpacket Segmentation bereits angelegt, und muss noch von Ihnen implementiert werden. Jeder Knoten speichert seine Zugehörigkeit zu einer Komponente als Referenz auf ein Objekte der Klasse Component in der Variable component (wie bereits in der Node Klasse vorgesehen). Diese Referenz ersetzt den Verweis auf den Repräsentant, welcher im Ansatz der VO verwendet wurde, und muss beim Vereinigen von zwei Komponenten aktualisiert werden. Achten Sie außerdem darauf, dass die Bestimmung von \( MInt (C_u, C_v) \) effizient durchgeführt wird. Für die initiale Sortierung der Kanten dürfen Sie entweder die Methode List.sort() aus der Java-API verwenden oder auf auf Ihre Implementierung von MergeSort aus der ersten Programmieraufgabe zurückgreifen. Implementieren Sie den Algorithmus bitte in der Klasse ImageSegmentation, zu finden im im Packet Segmentation. Zumindest die folgende Methode soll vorhanden sein:

public class ImageSegmentation {
	/**
	 * Performs the segmentation algorithm of Felzenszwalb and Huttenlocher on an undirected, weighted graph.
	 * @param g the graph
	 * @param k parameter of the algorithm
	 * @return graph whose nodes reference respective components
	 */
	public static UndirectedGraph FHSegmentation(UndirectedGraph g, int k);
}

Hinweise

Beispiel

Eingabebild
Eingabebild
Segmentierung
Segmentiertes Bild mit Parameter \( k=1000 \)