Regionen in Binarbildern - Digitale Bildverarbeitung - page 192

A. Rekursive Regionenmarkierung: Die rekursive Version (Alg.
11.1, Zeile 8) benutzt zur Verwaltung der noch zu besuchenden Bild-
koordinaten keine expliziten Datenstrukturen, sondern verwendet
dazu die lokalen Variablen der rekursiven Prozedur. 1 Durch die Nach-
barschaftsbeziehung zwischen den Bildelementen ergibt sich eine
Baumstruktur, deren Wurzel der Startpunkt innerhalb der Region
bildet. Die Rekursion entspricht einem Tiefendurchlauf ( depth-first
traversal ) [19, 32] dieses Baums und fuhrt zu einem sehr einfachen
Programmcode, allerdings ist die Rekursionstiefe proportional zur
Große der Region und daher der Stack-Speicher rasch erschopft. Die
Methode ist deshalb nur fur sehr kleine Bilder anwendbar.
B. Iteratives Flood Filling ( depth-first ): Jede rekursive Prozedur
kann mithilfe eines eigenen Stacks auch iterativ implementiert wer-
den (Alg. 11.1, Zeile 16). Der Stack dient dabei zur Verwaltung der
noch ” offenen“ (d. h. noch nicht bearbeiteten) Elemente. Wie in der
rekursiven Version (A) wird der Baum von Bildelementen im Depth-
first -Modus durchlaufen. Durch den eigenen, dedizierten Stack (der
dynamisch im so genannten Heap-Memory angelegt wird) ist die
Tiefe des Baums nicht mehr durch die Große des Aufruf-Stacks be-
schrankt.
C. Iteratives Flood Filling ( breadth-first ): Ausgehend vom Start-
punkt werden in dieser Version die jeweils angrenzenden Pixel schicht-
weise, ahnlich einer Wellenfront expandiert (Alg. 11.1, Zeile 28). Als
Datenstruktur fur die Verwaltung der noch unbearbeiteten Pixel-
koordinaten wird (anstelle des Stacks) eine Queue (Warteschlange)
verwendet. Ansonsten ist das Verfahren identisch zu Version B.

11 Regionen in Binarbildern

Java-Implementierung

Die rekursive Version (A) des Algorithmus ist in Java praktisch 1:1 umzu-
setzen. Allerdings erlaubt ein normales Java-Laufzeitsystem nicht mehr
als ungefahr 10.000 rekursive Aufrufe der FloodFill()-Prozedur (Alg.
11.1, Zeile 8), bevor der Speicherplatz des Aufruf-Stacks erschopft ist.
Das reicht nur fur relativ kleine Bilder mit weniger als ca. 200 × 200
Pixel.
Prog. 11.1 zeigt die vollstandige Java-Implementierung beider Vari-
anten der iterativen FloodFill()-Prozedur. Zunachst wird in Zeile 1
eine neue Java-Klasse Node zur Reprasentation einzelner Pixelkoordina-
ten definiert.
Zur Implementierung des Stacks in der iterativen Depth-first -Version
(B) verwenden wir als Datenstruktur die Java-Klasse Stack (Prog.
11.1, Zeile 8), ein Container fur beliebige Java-Objekte. Fur die Queue -

1 Fur lokale Variablen wird in Java (oder auch in C und C++) bei jedem
Prozeduraufruf der entsprechende Speicherplatz dynamisch im so genannten
Stack Memory angelegt.