Digital Signal Processing Reference
In-Depth Information
Fall ist ein Objekt eine Gruppe von aneinander angrenzenden Vorder-
grundpixeln bzw. eine
verbundene binare Bildregion
.
11
Regionen in Binarbildern
11.1 Au
nden von Bildregionen
Bei der Suche nach binaren Bildregionen sind die zunachst wichtigsten
Aufgaben, herauszufinden, welche Pixel zu welcher Region gehoren, wie
viele Regionen im Bild existieren und wo sich diese Regionen befinden.
Diese Schritte werden ublicherweise in
einem
Prozess durchgefuhrt, der
als
”
Regionenmarkierung“ (
region labeling
oder auch
region coloring
)be-
zeichnet wird. Dabei werden zueinander benachbarte Pixel schrittweise
zu Regionen zusammengefugt und allen Pixeln innerhalb einer Region
eindeutige Identifikationsnummern (
”
labels“) zugeordnet. Im Folgenden
beschreiben wir zwei Varianten dieser Idee: Die erste Variante (Regio-
nenmarkierung durch
flood filling
)fullt, ausgehend von einem gegebenen
Startpunkt, jeweils eine einzige Region in alle Richtungen. Bei der zwei-
ten Methode (
sequentielle Regionenmarkierung
) wird im Gegensatz dazu
das Bild von oben nach unten durchlaufen und alle Regionen auf einmal
markiert. In Abschn. 11.2.2 beschreiben wir noch ein drittes Verfahren,
das die Regionenmarkierung mit dem Au
nden von Konturen kombi-
niert.
Unabhangig vom gewahlten Ansatz mussen wir auch - durch Wahl
der 4er- oder 8er-Nachbarschaft (Abb. 10.5) - fixieren, unter welchen
Bedingungen zwei Pixel miteinander
”
verbunden“ sind, denn die beiden
Arten der Nachbarschaft fuhren i. Allg. zu unterschiedlichen Ergebnissen.
Fur die Regionenmarkierung nehmen wir an, dass das zunachst binare
Ausgangsbild
I
(
u, v
) die Werte 0 (Hintergrund) und 1 (Vordergrund)
enthalt und alle weiteren Werte fur Markierungen, d. h. zur Nummerie-
rung der Regionen, genutzt werden konnen:
⎧
⎨
0
Hintergrundpixel (
background
)
I
(
u, v
)=
1
Vordergrundpixel (
foreground
)
⎩
2
,
3
,...
Regionenmarkierung (
label
)
11.1.1 Regionenmarkierung durch
Flood Filling
Der grundlegende Algorithmus fur die Regionenmarkierung durch
Flood
Filling
ist einfach: Zuerst wird im Bild ein noch unmarkiertes Vorder-
grundpixel gesucht, von dem aus der Rest der zugehorigen Region
”
gefullt“ wird. Dazu werden, ausgehend von diesem Startpixel, alle
zusammenhangenden Pixel der Region besucht und markiert, ahnlich
einer Flutwelle (
flood
), die sich uber die Region ausbreitet. Fur die Rea-
lisierung der Fulloperation gibt es verschiedene Methoden, die sich vor
allem dadurch unterscheiden, wie die noch zu besuchenden Pixelkoordi-
naten verwaltet werden. Wir beschreiben nachfolgend drei Realisierun-
gen der FloodFill()-Prozedur: eine rekursive Version, eine iterative
Depth-first
- und eine iterative
Breadth-first
- Version:
