ImageConverter
zur Verfügung.
Diese Programmieraufgabe besteht aus zwei Teilen. Sie implementieren:
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:
public static UndirectedGraph readAndPrepareSegmentation(String filename);
(zum Einlesen der Bilder)public static void writeSegmentsColored(String filename, UndirectedGraph graph);
(zur Ausgabe der segmentierten Bilder)public static UndirectedGraph readAndPrepareLivewire(String filename);
(zum Einlesen der Bilder)public static void writeMarkedPath(String inputName, String outputName, UndirectedGraph graph, Node s, Node t);
(um die ermittelte Kante in einem Bild einzuzeichnen)
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.
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.
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); }
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:
ImageConverter
wird dieser Vorverarbeitungsschritt bereits durchgeführt. Die Kanten des Objektes im Bildgraphen haben daher relativ geringes Gewicht.
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.
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); }
LinkedList
) implementieren die Methode addAll()
standardmäßig durch iterierten Aufruf von add()
und haben damit lineare Laufzeit.
Diese Datenstrukturen sind daher für die effiziente Implementierung der Union-Find Datenstruktur nicht geeignet.
double
), auch wenn die ursprünglichen Kantengewichte ganzzahlig sind.
ImageConverter
wird dieser Vorverarbeitungsschritt bereits durchgeführt.
Um die abschließende Segmentierung zu visualisieren, wird in der Klasse ImageConverter
am Ende jeder gefundenen Komponente eine andere Farbe zugeordnet.
Jedes Pixel des Bildes wird anschließend in der Farbe seines enstprechenden Knotens eingefärbt.