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

These equations do not depend on the other parameter ρ and they provide alternative
mappings to gather evidence. That is, they decompose the parametric space, such that the
two parameters θ and ρ are now independent . The use of edge direction information
constitutes the base of the line extraction method presented by O'Gorman and Clowes
(O'Gorman, 1976). The use of pairs of points can be related to the definition of the
randomised Hough transform (Xu, 1990). Obviously, the number of feature points considered
corresponds to all the combinations of points that form pairs. By using statistical techniques,
it is possible to reduce the space of points in order to consider a representative sample of
the elements. That is, a subset which provides enough information to obtain the parameters
with predefined and small estimation errors.
Code 5.7 shows the implementation of the parameter space decomposition for the HT
for lines. The slope of the line is computed by considering a pair of points. Pairs of points
are restricted to a neighbourhood of 5 by 5 pixels. The implementation of Equation 5.40
gives values between - 90° and 90° . Since our accumulators only can store positive values,

then we add 90° to all values. In order to compute ρ we use Equation 5.28 given the value

of θ computed by Equation 5.40.
Figure 5.15 shows the accumulators for the two parameters θ and ρ as obtained by the
implementation of Code 5.7 for the images in Figure 5.7 (a) and Figure 5.7 (b). The
accumulators are now one dimensional as in Figure 5.15 (a) and show a clear peak. The
peak in the first accumulator is close to 135° . Thus, by subtracting the 90° introduced to
make all values positive, we find that the slope of the line θ = - 45° . The peaks in the
accumulators in Figure 5.15 (b) define two lines with similar slopes. The peak in the first
accumulator represents the value of θ , whilst the two peaks in the second accumulator
represent the location of the two lines. In general, when implementing parameter space
decomposition it is necessary to follow a two step process. First, it is necessary to gather
data in one accumulator and search for the maximum. Second, the location of the maximum
value is used as a parameter value to gather data of the remaining accumulator.

5.4.5.2 Parameter space reduction for circles
In the case of lines the relationship between local information computed from an image
and the inclusion of a group of points (pairs) is in an alternative analytical description
which will be readily established. For more complex primitives, it is possible to include
several geometric relationships. These relationships are not defined for an arbitrary set of
points but include angular constraints that define relative positions between them. In general,
we can consider different geometric properties of the circle to decompose the parameter
space. This has motivated the development of many methods of parameter space
decomposition (Aguado, 1996b). An important geometric relationship is given by the
geometry of the second directional derivatives. This relationship can be obtained by
considering that Equation 5.31 defines a position vector function. That is,

() 1

0 + ( ) 0

ω θ () = x y

1

(5.41)

where

x (θ ) = x 0 + r cos(θ ) y (θ ) = y 0 + r sin (θ ) (5.42)
In this definition, we have included the parameter of the curve as an argument in order to
highlight the fact that the function defines a vector for each value of θ . The end-points of