Digital Signal Processing Reference
In-Depth Information
d
y
9.2
Hough-Transformation
L
12
Abbildung 9.5
Zusammenhang zwischen Bildraum
und Parameterraum. Die Parameter-
werte fur alle moglichen Geraden
durch den Bildpunkt
p
i
=(
x
i
,y
i
)
im Bildraum (a) liegen im Parame-
terraum (b) auf einer Geraden
M
i
.
Umgekehrt entspricht jeder Punkt
q
j
=(
k
j
,d
j
) im Parameterraum ei-
ner Geraden
L
j
im Bildraum. Der
Schnittpunkt der zwei Geraden
M
1
,
M
2
an der Stelle
q
12
=(
k
12
,d
12
)
im Parameterraum zeigt an, dass im
Bildraum eine Gerade
L
12
mit zwei
Punkten und den Parametern
k
12
und
d
12
p
2
=(
x
2
,y
2
)
M
2
:
d
=
−x
2
k
+
y
2
p
1
=(
x
1
,y
1
)
q
12
=(
k
12
,d
12
)
M
1
:
d
=
−x
1
k
+
y
1
k
x
(a)
x/y
-Bildraum
(b)
k/d
-Parameterraum
verlauft. Je mehr Geraden
M
i
sich an einem Punkt im Parameterraum
schneiden, umso mehr Bildpunkte liegen daher auf der entsprechenden
Geraden im Bildraum! Allgemein ausgedruckt heißt das:
existiert.
Wenn sich
N
GeradenaneinerPosition(
k
,d
)im
Parameter-
raum
schneiden, dann liegen auf der entsprechenden Geraden
y
=
k
x
+
d
im
Bildraum
insgesamt
N
Bildpunkte.
9.2.2 Akkumulator-Array
Das Ziel, die dominanten Bildgeraden zu finden, ist daher gleichbedeu-
tend mit dem Au
nden jener Koordinaten im Parameterraum, an de-
nen sich viele Parametergeraden schneiden. Genau das ist die Inten-
tion der HT. Um die HT zu berechnen, benotigen wir zunachst eine
diskrete Darstellung des kontinuierlichen Parameterraums mit entspre-
chender Schrittweite fur die Koordinaten
k
und
d
. Um die Anzahl der
Uberschneidungen im Parameterraum zu berechnen, wird jede Parame-
tergerade
M
i
additiv in dieses
”
Akkumulator-Array“ gezeichnet, indem
jede durchlaufene Zelle um den Wert 1 erhoht wird (Abb. 9.6).
9.2.3 Eine bessere Geradenparametrisierung
Leider ist die Geradenreprasentation in Gl. 9.1 in der Praxis nicht wirk-
lich brauchbar, denn es gilt
k
=
fur vertikale Geraden. Eine bessere
Losung ist die so genannte
Hesse'sche Normalform
(HNF) der Geraden-
gleichung
∞
x
·
cos(
θ
)+
y
·
sin(
θ
)=
r,
(9.6)
die keine derartigen Singularitaten aufweist und außerdem eine lineare
Quantisierung ihrer Parameter, des Winkels
θ
und des Radius
r
,ermog-
licht (s. Abb. 9.7). Mit der HNF-Parametrisierung hat der Parameter-
raum die Koordinaten
θ, r
und jedem Bildpunkt
p
i
=(
x
i
,y
i
)entspricht
darin die Relation