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

5.3 Template matching

5.3.1 Definition

Template matching is conceptually a simple process. We need to match a template to an
image, where the template is a sub-image that contains the shape we are trying to find.
Accordingly, we centre the template on an image point and count up how many points in
the template match those in the image. The procedure is repeated for the entire image and
the point which led to the best match, the maximum count, is deemed to be the point where
the shape (given by the template) lies within the image.
Consider that we want to find the template of Figure 5.2 (b) in the image of Figure
5.2 (a). The template is first positioned at the origin and then matched with the image to
give a count which reflects how well the template matched that part of the image at that
position. The count of matching pixels is increased by one for each point where the
brightness of the template matches the brightness of the image. This is similar to the
process of template convolution, illustrated earlier in Figure 3.11 . The difference here is
that points in the image are matched with those in the template, and the sum is of the
number of matching points as opposed to the weighted sum of image data. The best match
is when the template is placed at the position where the rectangle is matched to itself.
Obviously, this process can be generalised to find, for example, templates of different size
or orientation . In these cases, we have to try all the templates (at expected rotation and
size) to determine the best match.

(a) Image containing shapes (b) Template of target shape

Figure 5.2 Illustrating template matching

Formally, template matching can be defined as a method of parameter estimation. The
parameters define the position (and pose) of the template. We can define a template as a
discrete function T x , y . This function takes values in a window. That is, the co-ordinates of
the points ( x , y ) ∈ W . For example, for a 2 × 2 template we have that the set of points W

= {(0, 0), (0, 1), (1, 0), (1, 1)}.