Digital Signal Processing Reference
In-Depth Information
1:
TraceContour(
x
S
,d
S
,L
C
,I,LM
)
x
S
: start position
d
S
: initial search direction
L
C
: label for this contour
I
: image
LM
:labelmap
11.2
Konturen von Regionen
Algorithmus 11.4
Kombinierte Konturfindung und Re-
gionenmarkierung (
Fortsetzung
). Die
Prozedur
TraceContour
durchlauft
die zum Startpunkt
x
S
gehorigen
Konturpunkte, beginnend mit der
Suchrichtung
d
S
=0(außere Kon-
tur) oder
d
S
= 1 (innere Kontur).
Dabei werden alle Konturpunkte so-
wie benachbarte Hintergrundpunkte
im Label-Array
LM
markiert.
Tra-
ceContour
verwendet
FindNext-
Node()
, um zu einem gegebenen
Punkt
x
c
den nachfolgenden Kon-
turpunkt zu bestimmen (Zeile 10).
Die Funktion
Delta()
dient lediglich
zur Bestimmung der Folgekoordina-
ten in Abhangigkeit von der aktuellen
Suchrichtung
d
.
2:
Create an empty contour
C
3:
(
x
T
,d
)
←
FindNextNode(
x
S
,d
s
,I,LM
)
4:
Append(
C,
x
T
)
add
x
T
to contour
C
5:
x
p
←
x
S
previous
position
x
p
=(
u
p
,v
p
)
6:
x
c
←
x
T
current
position
x
c
=(
u
c
,v
c
)
7:
done ←
(
x
S
=
x
T
)
isolated pixel?
8:
while
(
¬done
)
do
9:
LM
(
u
c
,v
c
)
←
L
C
10:
(
x
n
,d
)
←
FindNextNode(
x
c
,
(
d
+6) mod 8
,I,LM
)
11:
x
p
←
x
c
12:
x
c
←
x
n
13:
done ←
(
x
p
=
x
S
∧
x
c
=
x
T
)
back at starting position?
14:
if
(
¬done
)
then
15:
Append(
C,
x
n
)
add point
x
n
to contour
C
16:
return
C
.
return this contour
17:
FindNextNode(
x
c
,d,I,LM
)
x
c
: original position,
d
: search direction,
I
: image,
LM
:labelmap
18:
for
i ←
0
...
6
do
search in 7 directions
x
←
x
c
+ Delta(
d
)
x
=(
u
,v
)
19:
if
I
(
u
,v
)isa
background
pixel
then
20:
LM
(
u
,v
)
←−
1
21:
mark background as
visited
(
−
1)
22:
d ←
(
d
+1)mod8
found a non-background pixel at
x
23:
else
return
(
x
,d
)
24:
25:
return
(
x
c
,d
).
found no next node, return start position
d
01234567
26:
Delta(
d
)=(
∆x, ∆y
), wobei
∆x
110
−
1
−
1
−
101
∆y
01110
−
1
−
1
−
1
inneren Konturen wird die Java-Container-Klasse
ArrayList
(para-
metrisiert auf den Typ
Node
) verwendet.
•
Die Methode
traceContour()
in Prog. 11.4 durchlauft eine außere
oder innere Kontur, beginnend bei einem Startpunkt
x
S
(
xS
,
yS
).
Dafur wird zunachst die Methode
findNextNode()
aufgerufen, um
den auf
x
T
(
xT
,
yT
) zu bestimmen:
-Fur den Fall, dass kein nachfolgender Punkt gefunden wird,
gilt
x
S
folgenden Konturpunkt
x
T
und es handelt sich um eine Region (Kon-
tur), bestehend aus einem isolierten Pixel. In diesem Fall ist
traceContour()
fertig.
- Andernfalls werden durch wiederholten Aufruf von
findNext-
Node()
die ubrigen Konturpunkte schrittweise durchlaufen, wo-
x
S
=