Digital Signal Processing Reference
In-Depth Information
1:
SequentialLabeling(
I
)
I
: binary image (0 =
background
,1=
foreground
)
11
Regionen in Binarbildern
Algorithmus 11.2
Sequentielle Regionenmarkierung.
Das binare Eingangsbild
I
enthalt
die Werte
I
(
u, v
)=0fur Hin-
tergrundpixel und
I
(
u, v
)=1
fur Vordergrundpixel (Regionen).
Die resultierenden Markierun-
gen haben die Werte 2
...m−
1.
2:
Pass 1 - Assign Initial Labels:
3:
Initialize
m ←
2 (the value of the next label to be assigned).
4:
Create an empty set
C
to hold the collisions:
C←{}
.
5:
for
v ←
0
...H−
1
do
H
= height of image
I
6:
for
u ←
0
...W−
1
do
W
= width of image
I
7:
if
I
(
u, v
)=1
then
do one of:
8:
if
all neighbors are background pixels (all
n
i
=0)
then
9:
I
(
u, v
)
← m
.
10:
m ← m
+1.
11:
else if
exactly
one
of the neighbors has a label value
n
k
>
1
then
12:
set
I
(
u, v
)
←
n
k
13:
else if
several
neighbors have label values
n
j
>
1
then
14:
Select one of them as the new label:
I
(
u, v
)
← k ∈{n
j
}
.
15:
for
all other neighbors with label values
n
i
>
1and
n
i
=
k
do
16:
register the pair
n
i
,k
as a label collision:
C←C∪{n
i
,k}
.
Remark:
The image
I
now contains label values 0
,
2
,...m−
1.
17:
Pass 2 - Resolve Label Collisions:
18:
Let
L
=
{
2
,
3
,...m−
1
}
be the set of preliminary region labels.
19:
Create a partitioning of
L
as a
vector of sets
, one set for each label
value:
R←
[
R
2
,R
3
,...,R
m−
1
]=[
{
2
}, {
3
}, {
4
},...,{m−
1
}
], so
R
i
=
{i}
for all
i ∈L
.
20:
for all
collisions
a, b∈C
do
21:
Find in
R
the sets
R
a
,
R
b
containing the labels
a
,
b
,resp.:
R
a
←
the set which currently contains label
a
R
b
←
the set which currently contains label
b
22:
if
R
a
=
R
b
(
a
and
b
are contained in different sets)
then
23:
Merge sets
R
a
and
R
b
by moving all elements of
R
b
to
R
a
:
R
a
←R
a
∪R
b
R
b
←{}
Remark:
All equivalent label values (i.e., all labels of pixels in the
same region) are now contained in the same sets within
R
.
24:
Pass 3: Relabel the Image:
25:
Iterate through all image pixels (
u, v
):
26:
if
I
(
u, v
)
>
1
then
27:
Find the set
R
i
in
R
which contains label
I
(
u, v
).
28:
Choose one unique, representative element
k
from the set
R
i
(e.g., the minimum value,
k ←
min(
S
)).
29:
Replace the image label:
I
(
u, v
)
← k
.
30:
return
the labeled image
I
.
