Digital Signal Processing Reference
In-Depth Information
9.3
Implementierung der
Hough-Transformation
x/y
-Bildraum
θ/r
-Parameterraum
y
r
c
Abbildung 9.8
Bildraum und Parameterraum fur die
HNF-Parametrisierung.
c
b
b
a
a
−x
x
0
θ
d
e
d
e
π
2
−r
0
π
−y
(a)
(b)
Algorithmus 9.1
Einfacher Hough-Algorithmus fur Ge-
raden. Dieser liefert eine Liste der
Parameter (
θ, r
)fur die
K
stark-
sten Geraden im binaren Kantenbild
I
(
u, v
).
1:
HoughLines(
I
)
2:
Set up a two-dimensional array
Acc
[
θ, r
] of counters, initialize to 0
3:
Let (
u
c
,v
c
) be the center coordinates of the image
I
4:
for
all image coordinates (
u, v
)
do
5:
if
I
(
u, v
)isanedgepoint
then
6:
(
x, y
)
←
(
u−u
c
,v−v
c
)
relative coordinate to center
7:
for
θ
i
=0
...π
do
8:
r
i
=
x
cos(
θ
i
)+
y
sin(
θ
i
)
9:
Increment
Acc
[
θ
i
,r
i
]
10:
MaxLines ←
FindMaxLines(
Acc ,K
)
11:
return the list of parameter pairs (
θ
j
,r
j
)for
K
strongest lines
12:
return
MaxLines
.
wie nachfolgend beschrieben, das Akkumulator-Array nach maximalen
Eintragen durchsucht und ein Vektor von Parameterwerten fur die
K
starksten Geraden
MaxLines
=
(
θ
1
,r
1
)
,
(
θ
2
,r
2
)
, ...
(
θ
K
,r
K
)
wird zuruckgegeben.
9.3.1 Fullen des Akkumulator-Arrays
Eine direkte Implementierung des ersten Teils von Alg.9.1 zeigt Prog.9.1,
bestehend aus einer einzigen Java-Klasse
LinearHT
. Das Akkumulator-
Array (
houghArray
) ist als zweidimensionales
int
-Array definiert. Aus
dem ursprunglichen Bild
imp
wird die HT durch Erzeugen einer neuen
Instanz der Klasse
LinearHT
berechnet, d. h.
LinearHT HT = new LinearHT(imp, 256, 256);
Die letzten beiden Parameter (256, 256) spezifizieren die Anzahl der
diskreten Schritte fur den Winkel
θ
und den Radius
r
.
imp
wird als