Information Technology Reference
In-Depth Information
11.2 Randomized Hough Transform
The Hough transform method has the advantage that it is robust to noise when
applied to detect a geometric shape in inputted 2D/3D data. However, the com-
putational cost and required memory size are very large. To cope with this
problem, a method called randomized Hough transform has been introduced [
6
,
9
].
In the original Hough transform method, each point on the input image is
transformed into a Hough parameter space, which is why there are so many points
for voting. However, Randomized HT votes for geometrical parameters which are
calculated by selecting several points randomly. Figure
11.1
shows the difference
between RHT and HT in case of detection of 3D spatial planes.
Ax
þ
By
þ
Cz
þ
D ¼ 0
ð
11
:
1
Þ
RHT selects three points randomly for detecting a plane, and the plane
parameters (A, B, C, D), which represent a plane calculated from the three points,
is voted into the Hough parameter space. If the three points denoted by (x1, y1, z1)
(x2, y2, z2), and (x3, y3, z3) are set on a plane, parameters A, B, C, D can be
represented by Eq. (
11.2
).
1
y1
z1
x11z1
x21z2
x31z3
A ¼
1
y2
z2
B ¼
1
y3
z3
ð
11
:
2
Þ
x1
y11
x1
y1
z1
D ¼
C ¼
x2
y21
x2
y2
z2
x3
y31
x3
y3
z3
The parameters A, B, C, D are difficult to define in a limited range because they
can have fractional values. We need to change this to a spherical coordinate
system. Figure
11.2
shows the spherical coordinate system, where q is the distance
between a plane and the origin, u is the angle with respect to the x-axis, and h is
the angle with respect to the z-axis. We can define the range of parameters in the
changed coordinate system:
q
0
0
h
p
0
u
2p
ð
11
:
3
Þ
where q
;
u
;
hcan be obtained by Eq. (
11.4
), where x, y, z is a point in the Cartesian
coordinate system and they are denoted by x = A/D, y = B/D, z = C/D.
q ¼
;
p
z
q
y
x
h ¼ cos
1
u ¼ tan
1
x
2
þ
y
2
þ
z
2
ð
11
:
4
Þ
;
Search WWH ::
Custom Search