Digital Signal Processing Reference
In-Depth Information
1:
RegionLabeling(
I
)
I
: binary image (0 =
background
,1=
foreground
)
11.1
Auffinden von
Bildregionen
2:
Initialize
m ←
2 (the value of the next label to be assigned).
Algorithmus 11.1
Regionenmarkierung durch
Flood
Filling
.Dasbinare Eingangsbild
I
enthalt die Werte 0 fur Hintergrund-
pixel und 1 fur Vordergrundpixel. Es
werden noch unmarkierte Vorder-
grundpixel gesucht, von denen aus
die zugehorige Region gefullt wird.
Die
FloodFill
()-Prozedur ist in drei
verschiedenen Varianten ausgefuhrt:
rekursiv
,
depth-first
und
breadth-first
.
3:
Iterate over all image coordinates
u, v
.
4:
if
I
(
u, v
)=1
then
5:
FloodFill(
I,u,v,m
)
useanyofthe3versionsbelow
6:
m ← m
+1.
7:
return
.
8:
FloodFill(
I,u,v,label
)
Recursive Version
9:
if
coordinate
u, v
is within image boundaries
and
I
(
u, v
)=1
then
10:
Set
I
(
u, v
)
← label
11:
FloodFill(
I,u
+1
,v,label
)
12:
FloodFill(
I,u,v
+1
, label
)
13:
FloodFill(
I,u,v−
1
, label
)
14:
FloodFill(
I,u−
1
,v,label
)
15:
return
.
16:
FloodFill(
I,u,v,label
)
Depth-First Version
17:
Create an empty stack
S
18:
Put the seed coordinate
u, v
onto the stack: Push(
S, u, v
)
19:
while
S
is not empty
do
20:
Get the next coordinate from the top of the stack:
x, y←
Pop(
S
)
21:
if
coordinate (
x, y
) is within image boundaries
and
I
(
x, y
)=1
then
22:
Set
I
(
x, y
)
← label
23:
Push(
S, x
+1
,y
)
24:
Push(
S, x, y
+1
)
25:
Push(
S, x, y−
1
)
26:
Push(
S, x−
1
,y
)
27:
return
.
28:
FloodFill(
I,u,v,label
)
Breadth-First Version
29:
Create an empty queue
Q
30:
Insert the seed coordinate
u, v
into the queue: Enqueue(
Q,
(
u, v
))
31:
while
Q
is not empty
do
32:
Get the next coordinate from the front of the queue:
x, y
←
Dequeue(
Q
)
33:
if
coordinate
x, y
is within image boundaries
and
I
(
x, y
)=1
then
34:
Set
I
(
x, y
)
← label
35:
Enqueue(
Q, x
+1
,y
)
36:
Enqueue(
Q, x, y
+1
)
37:
Enqueue(
Q, x, y−
1
)
38:
Enqueue(
Q, x−
1
,y
)
39:
return
.
