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

In general, we are interested in matching the model shape against a shape in an image.
However, the shape in the image has a different location, orientation and scale. Originally
the GHT defines a scale parameter in the x and y directions, but due to computational
complexity and practical relevance the use of a single scale has become much more popular.
Analogous to Equation 5.33, we can define the image shape by considering translation,
rotation and change of scale. Thus, the shape in the image can be defined as
ω (θ , b , λ , ρ ) = b + λ R (ρ )υ (θ ) (5.72)
where b = ( x 0 , y 0 ) is the translation vector λ is a scale factor and R (ρ ) is a rotation matrix
(as in Equation 5.31). Here we have included explicitly the parameters of the transformation
as arguments, but to simplify the notation they will be omitted later. The shape of ω (θ , b ,
λ , ρ ) depends on four parameters. Two parameters define the location b , plus the rotation
and scale. It is important to notice that s does not define a free parameter, but only traces
the curve.
In order to define a mapping for the HT we can follow the approach used to obtain
Equation 5.35. Thus, the location of the shape is given by
b = ω (θ ) - λ R (ρ )υ (θ ) (5.73)
Given a shape ω (θ ) and a set of parameters b , λ and ρ , this equation defines the location
of the shape. However, we do not know the shape ω (θ ) (since it depends on the parameters
that we are looking for), but we only have a point in the curve. If we call ω i = (ω

xi , ω yi ) the

point in the image, then
b = ω i - λ R (ρ )υ (θ ) (5.74)
defines a system with four unknowns and with as many equations as points in the image.
In order to find the solution we can gather evidence by using a four-dimensional accumulator
space. For each potential value of b , λ and ρ , we trace a point spread function by considering
all the values of θ . That is, all the points in the curve υ (θ ).
In the GHT the gathering process is performed by adding an extra constraint to the
system that allows us to match points in the image with points in the model shape. This
constraint is based on gradient direction information and can be explained as follows. We
said that ideally we would like to use Equation 5.73 to gather evidence. For that we need
to know the shape ω (θ ) and the model υ (θ ), but we only know the discrete points ω i and
we have supposed that these are the same as the shape, i.e. that ω (θ ) = ω i . Based on this
assumption, we then consider all the potential points in the model shape, υ (θ ). However,
this is not necessary since we only need the point in the model, υ (θ ), that corresponds to
the point in the shape, ω (θ ). We cannot know the point in the shape, υ (θ ), but we can
compute some properties from the model and from the image. Then, we can check whether
these properties are similar at the point in the model and at a point in the image. If they are
indeed similar , then the points might correspond : if they do we can gather evidence of the
parameters of the shape. The GHT considers as feature the gradient direction at the point.
We can generalise Equation 5.45 and Equation 5.46 to define the gradient direction at a
point in the arbitrary model. Thus,

y
x

()
() and

ˆ

-1

() = ( ) = tan ( ( )) (5.75)

Thus Equation 5.73 is true only if the gradient direction at a point in the image matches the
rotated gradient direction at a point in the (rotated) model, that is