Auffinden und Markieren von Regionen in einem Binärbild

INHALTSVERZEICHNIS

Kurzfassung

Abstract

1 ERSTE SCHRITTE
1.1 Aufgabenstellung
1.2 Lösungsansatz
1.3 Denkarbeit

2 UMSETZUNG
2.1 Initialisierung
2.2 Erster Durchlauf
2.3 Zweiter Durchlauf
2.4 Zählen der Regionen

3 ERGEBNISSE
3.1 Testbilder
3.2 ...und was das Programm daraus macht

4 ZUSAMMENFASSUNG
4.1 Probleme
4.2 Zusammenfassung
4.3 Arbeitsaufteilung

ANHANG: SourceCode

KURZFASSUNG

Das von uns erstellte Programm ist ein Plug-In für das auf Java basierende Bildbearbeitungsprogramm ImageJ. Das Plugin mit dem Titel „regionLabelling“ identifiziert Regionen in einem Binärbild und markiert diese. Das heißt, dass z.B. weiße zusammenhängende Flächen in einem Bild erkannt und mit Grauwerten eingefärbt werden. Dazu sind zwei Durchläufe durch das Bild notwendig. Der erste Durchlauf erkennt einzelne Flächen, die in unserem Programm durch “Labels” repräsentiert werden. Dabei wird auch zeitgleich gespeichert, welche einzelnen Labels zusammenstoßen und so eine Region bilden. In einem zweiten Durchlauf werden unter Berücksichtigung eben dieser Informationen die einzelnen Labels zu Regionen zusammengefasst und entsprechend eingefärbt. Am Ende des Programmes werden noch die insgesamt im Bild vorkommenden Regionen gezählt und ausgegeben.

ABSTRACT

Our work consisted of programming a plugin for the known image processing tool “ImageJ”. The program named “regionLabelling” should scan a binary image, which contains only black and white pixels, and trace continuous coherent regions. To visualise the detection, our plugin should color the different regions in different colors and count the regions. To realise this requirements, it was necessary to program two pass-throughs that scanned the image. The first run should distribute new labels and continue labels where adjacent labels are existent. In this first pass-through our program also saves information about colliding labels in a so-called fusion table. Labels “collide” when two label values come in touch at a specific pixel position. In a second run, our program combines coherent regions by using information from the actual pixel’s label value and the appropriate entry in the fusion table. In this part of the plugin, the effective regions in the image are colored in several different grayscales. Finally, our program counts the regions in the image and shows the calculated number.

1 ERSTE SCHRITTE

1.1 Aufgabenstellung

Zu schreiben war ein PlugIn für das Bildbearbeitungstool ImageJ, das auf Java basierende PlugIns unterstützt. Das Programm sollte die einfache Funktionalität besitzen, ein binäres, das heißt rein aus schwarzen und weißen Bildpunkten bestehendes, Bild zu scannen und alle zusammenhängenden weißen Regionen in diesem Bild zu zählen und zu visualisieren. Zur einfachen Sichtbarkeit der unterschiedlichen Regionen war die Anforderung, alle Regionen durch homogene Graustufen zu ersetzen. Die graphische Ausgabe des Programmes sollte sich auf das Ausgeben der Anzahl der gefundenen Regionen sowie das eingefärbte Originalbild beschränken.

Vermutete Probleme waren bereits zu Beginn die Wahl der richtigen Datenstrukturen im Programm sowie ein geeignetes Verfahren, um komplexere Regionen korrekt zu erkennen.

1.2 Lösungsansatz

Die uns zur Verfügung gestellten Unterlagen [Sonka, Hlavac, Boyle, Image Processing, Analysis and Machine Vision] halfen uns bei der Erstellung eines ersten Lösungsansatzes und einer Realisierungsidee. In der Literatur besteht der Algorithmus aus einem zweimaligen Durchlaufen des zu verarbeitenden Bildes, das Pixel für Pixel vorgenommen wird. Im ersten Durchlauf werden neue Teilflächen erkannt, indem ein Filter zur Erkennung von bereits gesetzten Teilflächen eingesetzt wird. Jeder eigenen Teilfläche wird ein spezifischer Wert zugewiesen, der dann im zweiten Durchlauf zur Berechnung des effektiv sichtbaren Grauwertes herangezogen wird.

Um neue Teilflächen richtig setzen zu können, beziehungsweise, falls das entsprechende Pixel an ein vorhandenes Label angrenzt, das besagte Label fortzusetzen, das heißt der neuen Teilfläche den Wert der angrenzenden Teilfläche zuzuweisen, verwendet der Referenzalgorithmus einen Filter, der die Pixel links und oberhalb des aktuellen Pixels betrachtet und deren Labelwerte ermittelt. Stößt der Filter dabei auf einen Wert für ein Label, so wird dem aktuellen Pixel derselbe Labelwert zugewiesen, andernfalls ein neuer Wert angelegt. Dieser Algorithmus funktioniert bereits sehr gut bei einfachen Bildern, die keine komplexen Regionen enthalten oder verschachtelte Anordnungen von Regionen aufweisen.

Abbildung in dieser Leseprobe nicht enthalten

Bei Bildern, die jedoch komplexere Formen aufweisen, stößt dieser Algorithmus jedoch an seine Grenzen. Der verwendete Filter meldet in so einem Fall an Stellen, an denen sich zwei Labels berühren, dass hier zwei erkannte Regionen zusammenstoßen, die eigentlich nur eine einzige Region ergeben müssten. Solche Fälle treten relativ schnell auf, einfache Beispiele sind Regionen in Form eines „U“ oder auch eines gespiegelten „E“.

Abbildung in dieser Leseprobe nicht enthalten

Die in der Literatur ersichtliche weitere Vorgehensweise beschäftigt sich mit dem Erkennen dieser sogenannten „Kollisionen“, die bei Zusammenstoßen zweier bereits vergebener Labels auftreten. Anschließend werden die Werte der beiden Labels in eine geeignete Datenstruktur gespeichert. In weiterer Folge werden die Labels in einem zweiten Durchlauf des Bildes unter Berücksichtigung der gespeicherten Kollisionen in separate Regionen umgewandelt und diese entsprechend eingefärbt. Leider hält sich das zur Verfügung stehende Paper in den Punkten, die eigentlich für das erfolgreiche Funktionieren des Programmes maßgeblich sind, recht kurz, sodass Denkarbeit gefragt war.

1.3 Denkarbeit

Recht schnell wurde uns klar, dass die Knackpunkte in der Wahl einer geeigneten Datenstruktur zum Speichern der Kollisionen und in der Zuweisung der Farbwerte und Vereinigung der Regionen im zweiten Durchlauf lagen. Erste Anforderungen an die Datenstruktur waren eine dynamische Erweiterbarkeit, da ja das Programm zur Kompilierungszeit noch keine Informationen über die Anzahl der vorkommenden Regionen und damit auch der zu speichernden Kollisionen hat und damit die verwendete Struktur bei Mehrung der Regionen auch demgemäß eine größere Anzahl von Kollisionen speichern muss.

Da unser Ziel war, das Programm möglichst effizient zu programmieren, war unser Bestreben, den Source-Code so kurz wie möglich zu halten und einfach zu strukturieren, damit eine genügend hohe Performance erzielt werden konnte. Daher hielten wir es für maßgeblich, dass im ersten Durchlauf des Bildes sowohl die Vergabe der Labelwerte, als auch zeitgleich das Erkennen und Speichern von auftretenden Kollisionen erfolgte. Im zweiten Durchlauf wollten wir uns auf das Vereinigen (Fusionieren) der zusammengehörigen Labels beschränken.

Unser erster Ansatz war, die zwei zusammenstoßenden Labelwerte zu ermitteln und diese in ein zweidimensionales Integer-Array zu speichern, wobei an die jeweilige Stelle des Arrays in der ersten Spalte der finale Wert, in der zweiten Spalte der zuzuweisende Wert geschrieben werden sollte. Daher implementierten wir diese Idee so, dass bei einer auftretenden Kollision der höhere der beiden vorhandenen Labelwerte in die erste Spalte, der niedrigere in die zweite Spalte gespeichert wurde. Dem fraglichen Pixel wurde der Labelwert des höheren vorhandenen Labels zugewiesen. Im zweiten Durchlauf sollte dann einfach für jeden Pixel überprüft werden, ob er in der zweiten Spalte des Fusionierungs- Arrays auftaucht und ihm dann den Endwert der Region zuzuweisen. Im ersten Ansatz bedeutete übrigens „Wert“ so viel wie „Grauwert“, das heißt wir speicherten die Nummern der Labels und Regionen direkt als Grauwerte in des Bild hinein, wodurch sich jedoch Probleme beim Verarbeiten von Bildern mit mehr als 255 Labels ergaben.

Die erste Idee für unsere Datenstruktur zur Speicherung der Kollisionen beschreibt sich also wie folgt:

Abbildung in dieser Leseprobe nicht enthalten

Daraus ergibt sich also, dass der Wert 1 im zweiten Durchlauf auf den Wert 3 umgeschrieben wird und an anderer Stelle der Wert 2 ebenfalls dem Wert 3 zugeordnet wird. Damit werden also die Labels 1 und 2 dem Label 3 zugeordnet, wodurch diese drei Labels vereinigt werden und zusammen eine geschlossene Region ergeben. Anschließend wandeln Labels mit dem Wert 3 sich auf den Wert 4, womit die eben erzeugte Region wieder einer anderen zugeordnet wird. Der Algorithmus durchläuft das gesamte Array und erzeugt am Ende einige wenige Regionen.

Diese Idee funktioniert, wie sich in der Umsetzung gezeigt hat, im Prinzip bestens - das einzige Problem, das auftritt, ist das folgende:

Abbildung in dieser Leseprobe nicht enthalten

Der Algorithmus stößt hierbei auf mehrere zusammenstoßende Regionen. Gemäß unserer Implementierung wird ein Fusionierungs-Array erzeugt, das die zu verschmelzenden Labels enthält. Die Vereinigung im zweiten Durchlauf geht so vor sich, dass anfangs Pixel mit dem

Abbildung in dieser Leseprobe nicht enthalten

Label 1 auf das Label 2 umgespeichert werden. Anschließend werden alle Labels mit dem Wert 3 dem Wert 4 zugewiesen. An der letzten Stelle des Arrays versucht das Programm, alle Labels mit dem Wert 1 ebenfalls auf den Wert 4 zu legen. Dies fruchtet jedoch nicht, da ja bereits im ersten Schritt das Pixel mit dem Labelwert 1 auf den Wert 2 gespeichert wurde, d.h. der Wert 1 „verlorengegangen“ ist. Daher geht der Zusammenhang zwischen dem Label 1 und dem Label 4 verloren und das Bild wird wie oben aufgezeigt eingefärbt.

Anfangs waren wir der Meinung, dieses Problem könne durch geschicktes Sortieren unseres zweidimensionalen Arrays gelöst werden, wir konnten diesen Denkansatz jedoch nicht zu einem funktionierenden Ende führen, weshalb wir uns schließlich auf die Implementierung einer anderen Datenstruktur konzentrierten.

2 UMSETZUNG

2.1 Initialisierung

Wie bereits erwähnt, wurden im ersten Ansatz von uns die Labelwerte in der Form vergeben, dass wir sie direkt als Grauwerte in das vorhandene Bild speicherten, was natürlich zu Problemen führte, wenn es das Bild erforderlich machte, mehr als 255 verschiedene Labels zu vergeben, was leider recht früh der Fall war.

Daher erstellen wir in der finalen Implementierung als erstes ein neues Integer-Array mit der Länge des aus dem ImageProcessor gewonnenen, die einzelnen Pixel und ihre Farbwerte repräsentierenden, Byte-Arrays, das fortan zur Speicherung der Labelwerte für das entsprechende Pixel dient. Dieses neue Array betitelten wir mit labels und speicherten darin die entsprechenden Grauwerte der Pixel.

Als Datenstruktur für die Kollisionen dient ein eigenes Array mit einer fixen Größe von 8192 und dem Namen fusionTable. Dieses Array ist mit den Werten von 0 bis 8192 vorbelegt.

2.2 Erster Durchlauf

Abbildung in dieser Leseprobe nicht enthalten

Das Flussdiagramm zeigt den weiteren Ablauf des Programmes. Im Prinzip funktioniert es wie unser erster Lösungsansatz, mit dem Unterschied, dass nicht einfach stur pro neuer Kollision ein Eintrag in den fusionTable vorgenommen wird. Vielmehr wird überprüft, ob dem Label, dem ein weiterer Labelwert angehängt werden soll, bereits eine Fusion zugeordnet ist. Anschließend werden alle Zeilen, in der fusionTable, an deren Stelle der alte zugeordnete Wert steht, in den neuen min-Wert umgeschrieben, wodurch sich das vorher beschriebene Problem löst.

[...]