Image Processing Reference
In-Depth Information
well separated. However, this increases the probability that the points do not belong to the
same ellipse, thus generating background noise in the accumulator.
(a) Accumulators for Figure 5.10(a)
(b) Accumulators for Figure 5.10(b)
Figure 5.20
Parameter space reduction for the Hough transform for ellipses
5.5
Generalised Hough transform (GHT)
Many shapes are far more complex than lines, circles or ellipses. It is often possible to
partition a complex shape into several geometric primitives, but this can lead to a highly
complex data structure. In general it is more convenient to extract the whole shape. This
has motivated the development of techniques that can find
arbitrary
shapes using the
evidence-gathering procedure of the HT. These techniques again give results equivalent to
those delivered by matched template filtering, but with the computational advantage of the
evidence gathering approach. An early approach offered only limited capability for arbitrary
shapes (Merlin, 1975). The full mapping is called the
Generalised HT
(GHT) (Ballard,
1981) and can be used to locate arbitrary shapes with unknown
position
,
size
and
orientation
.
The GHT can be formally defined by considering the duality of a curve. One possible
implementation can be based on the discrete representation given by tabular functions.
These two aspects are explained in the following two sections.
5.5.1
Formal definition of the GHT
The formal analysis of the HT provides the route for generalising it to arbitrary shapes. We
can start by generalising the definitions in Equation 5.41. In this way a model shape can be
defined by a curve
()
1
0
+ ( )
0
() =
x
y
1
(5.71)
For a circle, for example, we have that
x
(
) =
r
cos(
) and
y
(
) =
r
sin(
). Any shape can
be represented by following a more complex definition of
x
(
) and
y
(
).
