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

is delivered as the result. The match for each position is stored in the array. After computing
all the matches, the minimum element in the array defines the position where most pixels
in the template matched those in the image. As such, the minimum is deemed to be the co-
ordinates of the point where the template's shape is most likely to lie within the original
image. It is possible to implement a version of template matching without the accumulator
array, by storing the location of the minimum alone. This will give the same result though
it requires little storage. However, this implementation will provide a result that cannot
support later image interpretation that might require knowledge of more than just the best
match.
The results of applying the template matching procedure are illustrated in Figure 5.4 .
This example shows the accumulator arrays for matching the images shown in Figure
5.2 (a), 5.3 (a) and 5.3 (b) with their respective templates. The dark points in each image are
at the co-ordinates of the origin of the position where the template best matched the image
(the minimum). Note that there is a border where the template has not been matched to the
image data. At these border points, the template extended beyond the image data, so no
matching has been performed. This is the same border as experienced with template
convolution, Section 3.4.1. We can observe that a better minimum is obtained, Figure
5.4 (c), from the edge images of Figure 5.3 . This is because for grey level and binary
images, there is some match when the template is not exactly in the best position.

(a) For the grey level image (b) For the binary image (c) For the edge image

Figure 5.4 Accumulator arrays from template matching

Most applications require further degrees of freedom such as rotation (orientation),
scale (size), or perspective deformations. Rotation can be handled by rotating the template,
or by using polar co-ordinates; scale invariance can be achieved using templates of differing
size. Having more parameters of interest implies that the accumulator space becomes
larger; its dimensions increase by one for each extra parameter of interest. Position -
invariant template matching, as considered here, implies a 2D parameter space, whereas
the extension to scale and position invariant template matching requires a 3D parameter
space.
The computational cost of template matching is large . If the template is square and of
size m × m and is matched to an image of size N × N then since the m 2 pixels are matched
at all image points (except for the border) the computational cost is O ( N 2 m 2 ). This is the
cost for position invariant template matching. Any further parameters of interest increase
the computational cost in proportion to the number of values of the extra parameters. This