Digital Signal Processing Reference
In-Depth Information
Datenstruktur in der
Breadth-first
-Variante (C) verwenden wir die Java-
Klasse
LinkedList
2
mit den Methoden
addFirst()
,
removeLast()
und
isEmpty()
(Prog.11.1, Zeile 23). Beide Container-Klassen sind durch die
Angabe
<Node>
auf den Objekttyp
Node
parametrisiert, d. h. sie konnen
nur Objekte dieses Typs aufnehmen.
3
Abb. 11.2 illustriert den Ablauf der Regionenmarkierung in beiden
Varianten anhand eines konkreten Beispiels mit einer Region, wobei der
Startpunkt (
”
seed point“) - der normalerweise am Rand der Kontur
liegt - willkurlich im Inneren der Region gewahlt wurde. Deutlich ist zu
sehen, dass die
Depth-first
-Methode zunachst entlang
einer
Richtung (in
diesem Fall horizontal nach links) bis zum Ende der Region vorgeht und
erst dann die ubrigen Richtungen berucksichtigt. Im Gegensatz dazu
breitet sich die Markierung bei der
Breadth-first
-Methode annahernd
gleichformig, d. h. Schicht um Schicht, in alle Richtungen aus.
Generell ist der Speicherbedarf bei der
Breadth-first
-Variante des
Flood-fill
-Verfahrens deutlich niedriger als bei der
Depth-first
-Variante.
Fur das Beispiel in Abb. 11.2 mit der in Prog. 11.1 gezeigten Implemen-
tierung erreicht die Große des
Stacks
in der
Depth-first
-Variante 28.822
Elemente, wahrend die
Queue
der
Breadth-first
-Variante nur maximal
438 Knoten aufnehmen muss.
11
Regionen in Binarbildern
11.1.2 Sequentielle Regionenmarkierung
Die sequentielle Regionenmarkierung ist eine klassische, nicht rekursive
Technik, die in der Literatur auch als
”
region labeling“ bekannt ist.
Der Algorithmus besteht im Wesentlichen aus zwei Schritten: (1) ei-
ner vorlaufigen Markierung der Bildregionen und (2) der Auflosung von
mehrfachen Markierungen innerhalb derselben Region. Das Verfahren ist
(vor allem im 2. Schritt) relativ komplex, aber wegen seines moderaten
Speicherbedarfs durchaus verbreitet, bietet in der Praxis allerdings ge-
genuber einfacheren Methoden kaum Vorteile. Der gesamte Ablauf ist in
Alg. 11.2 dargestellt.
Schritt 1: Vorlaufige Markierung
Im ersten Schritt des
”
region labeling“ wird das Bild sequentiell von links
oben nach rechts unten durchlaufen und dabei jedes Vordergrundpixel
mit einer vorlaufigen Markierung versehen. Je nach Definition der Nach-
barschaftsbeziehung werden dabei fur jedes Pixel (
u, v
) die Umgebungen
N
2
N
1
×
N
2
N
3
N
4
N
1
×
N
4
(
u, v
)=
oder
N
8
(
u, v
)=
2
Die Klasse
LinkedList
ist Teil des
Java Collection Frameworks
(s. auch
Anhang 2.2).
3
Generische Typen und die damit verbundene Moglichkeit zur Parametrisie-
rung von Klassen gibt es erst seit Java 5 (1.5).
