Feature extraction by shape matching - Feature Extraction and Image Processing - page 174

particular, it has been used to extract lines , circles and ellipses (or conic sections). In the
case of lines, its mathematical definition is equivalent to the Radon transform (Deans,
1981). The HT was introduced by Hough (Hough, 1962) and then used to find bubble
tracks rather than shapes in images. However, Rosenfeld noted its potential advantages as
an image processing algorithm (Rosenfeld, 1969). The HT was thus implemented to find
lines in images (Duda, 1972) and it has been extended greatly, since it has many advantages
and many potential routes for improvement. Its prime advantage is that it can deliver the
same result as that for template matching, but faster (Princen, 1992), (Sklansky, 1978)
(Stockman, 1977). This is achieved by a reformulation of the template matching process,
based on an evidence gathering approach where the evidence is the votes cast in an
accumulator array. The HT implementation defines a mapping from the image points into
an accumulator space (Hough space). The mapping is achieved in a computationally efficient
manner, based on the function that describes the target shape. This mapping requires much
less computational resources than template matching. However, it still requires significant
storage and high computational requirements. These problems are addressed later, since
they give focus for the continuing development of the HT. However, the fact that the HT
is equivalent to template matching has given sufficient impetus for the technique to be
amongst the most popular of all existing shape extraction techniques.

5.4.2 Lines

We will first consider finding lines in an image. In a Cartesian parameterisation, collinear
points in an image with co-ordinates ( x , y ) are related by their slope m and an intercept c
according to:
y = mx + c (5.24)

This equation can be written in homogeneous form as
Ay + Bx + 1 = 0 (5.25)
where A = -1/ c and B = m / c . Thus, a line is defined by giving a pair of values ( A , B ).
However, we can observe a symmetry in the definition in Equation 5.25. This equation is
symmetric since a pair of co-ordinates ( x , y ) also defines a line in the space with parameters
( A , B ). That is, Equation 5.25 can be seen as the equation of a line for fixed co-ordinates
( x , y ) or as the equation of a line for fixed parameters ( A , B ). Thus, pairs can be used to
define points and lines simultaneously (Aguado, 2000a). The HT gathers evidence of the
point ( A , B ) by considering that all the points ( x , y ) define the same line in the space ( A ,
B ). That is, if the set of collinear points {( x i , y i )} defines the line ( A , B ), then
Ay i + Bx i + 1 = 0 (5.26)
This equation can be seen as a system of equations and it can simply be rewritten in terms
of the Cartesian parameterisation as
c = - x i m + y i (5.27)
Thus, to determine the line we must find the values of the parameters ( m , c ) (or ( A , B ) in
homogeneous form) that satisfy Equation 5.27 (or 5.26, respectively). However, we must
notice that the system is generally overdetermined. That is, we have more equations that
unknowns. Thus, we must find the solution that comes close to satisfying all the equations