Digital Signal Processing Reference
In-Depth Information
1:
ChamferMatch (
I,R
)
I
: binary image of size
w
I
× h
I
R
: binary template of size
w
R
× h
R
17.2
Vergleich von
Binarbildern
Algorithmus 17.2
Chamfer Matching
- Berechnung der
Match-Funktion. Gegeben sind ein
binares Binarbild
I
und ein binares
Template
R
. Im ersten Schritt wird
die Distanztransformation
D
fur das
Bild
I
berechnet (s. Alg. 17.1). An-
schließend wird fur jede Position
des Templates
R
die entsprechende
Summe der Werte in der Distanzver-
teilung ermittelt. Die Ergebnisse wer-
den in der zweidimensionalen Match-
Funktion
Q
abgelegt und zuruckgege-
ben.
2:
Step 1 - initialize:
3:
D ←
DistanceTransform(
I
)
Alg. 17.1
4:
K ←
number of foreground pixels in
R
5:
Set up a
match map Q
of size (
w
I
−w
R
+1)
×
(
h
I
−h
R
+1)
6:
Step 2 - compute match function:
7:
for
r ←
0
...
(
w
I
−w
R
)
do
set origin of template to (
r, s
)
8:
for
s ←
0
...
(
h
I
−h
R
)
do
9:
Evaluate match for template positioned at (
r, s
):
10:
q ←
0
11:
for
i ←
0
...
(
w
R
−
1)
do
12:
for
j ←
0
...
(
h
R
−
1)
do
13:
if
R
(
i, j
)=1
then
foreground pixel in template
14:
q ← q
+
D
(
r
+
i, s
+
j
)
15:
Q
(
r, s
)
← q/K
16:
return
Q
Der gesamte Ablauf zur Berechnung der Match-Funktion
Q
ist in Alg.
17.2 zusammengefasst. Wenn an einer Position alle Vordergrundpixel des
Templates
R
eine Entsprechung im Bild
I
finden, dann ist die Summe der
Distanzwerte null und es liegt eine perfekte Ubereinstimmung (
match
)
vor. Je mehr Vordergrundpixel des Templates Distanzwerte in
D
”
vorfin-
den“, die großer als null sind, umso hoher wird die Summe der Distanzen
Q
bzw. umso schlechter die Ubereinstimmung. Die beste Ubereinstim-
mung ergibt sich dort, wo
Q
ein Minimum aufweist, d. h.
p
opt
=(
r
opt
,s
opt
) = argmin
(
r,s
)
Q
(
r, s
)
.
(17.21)
Das Beispiel in Abb. 17.10 demonstriert den Unterschied zwi-
schen dem direkten Bildvergleich und
Chamfer Matching
anhand des
Binarbilds aus Abb. 17.7. Wie deutlich zu erkennen ist, erscheint die
Match-Funktion des Chamfer-Verfahrens wesentlich glatter und weist
nur wenige, klar ausgepragte lokale Maxima auf. Dies ermoglicht das
effektive Au
nden der Stellen optimaler Ubereinstimmung mittels ein-
facher, lokaler Suchmethoden und ist damit ein wichtiger Vorteil. Abb.
17.11 zeigt ein weiteres Beispiel mit Kreisen und Quadraten, wobei
die Kreise verschiedene Durchmesser aufweisen. Das verwendete Tem-
plate besteht aus dem Kreis mittlerer Große. Wie das Beispiel zeigt,
toleriert Chamfer Matching auch geringfugige Großenabweichungen zwi-
schen dem Bild und dem Vergleichsmuster und erzeugt auch in diesem
Fall eine relativ glatte Match-Funktion mit deutlichen Spitzenwerten.
Chamfer Matching ist zwar kein
”
silver bullet“, funktioniert aber un-
ter eingeschrankten Bedingungen und in passenden Anwendungen durch-
