Template matching

It can be used for quality control in manufacturing,[2] navigation of mobile robots,[3] or edge detection in images.

[4] The main challenges in a template matching task are detection of occlusion, when a sought-after object is partly hidden in an image; detection of non-rigid transformations, when an object is distorted or imaged from different angles; sensitivity to illumination and background changes; background clutter; and scale changes.

[5] The feature-based approach to template matching relies on the extraction of image features, such as shapes, textures, and colors, that match the target image or frame.

This approach is usually achieved using neural networks and deep-learning classifiers such as VGG, AlexNet, and ResNet.

[citation needed]Convolutional neural networks (CNNs), which many modern classifiers are based on, process an image by passing it through different hidden layers, producing a vector at each layer with classification information about the image.

Feature extraction using deep neural networks, like CNNs, has proven extremely effective has become the standard in state-of-the-art template matching algorithms.

Since template-based matching may require sampling of a large number of data points, it is often desirable to reduce the number of sampling points by reducing the resolution of search and template images by the same factor before performing the operation on the resultant downsized images.

This pre-processing method creates a multi-scale, or pyramid, representation of images, providing a reduced search window of data points within a search image so that the template does not have to be compared with every viable data point.

In instances where the template may not provide a direct match, it may be useful to implement eigenspaces to create templates that detail the matching object under a number of different conditions, such as varying perspectives, illuminations, color contrasts, or object poses.

In these cases, it is unreasonable to provide a multitude of templates to cover each possible occlusion.

[11] In these cases, one possible solution is to divide the template image into multiple sub-images and perform matching on each subdivision.

Template matching is a central tool in computational anatomy (CA).

In this field, a deformable template model is used to model the space of human anatomies and their orbits under the group of diffeomorphisms, functions which smoothly deform an object.

Template matching algorithms in CA have come to be called large deformation diffeomorphic metric mappings (LDDMMs).

Cross correlation techniques compare the similarities of the search and template images.

This method is normally implemented by first picking out a part of a search image to use as a template.

For simplicity, assume pixel values are scalar, as in a greyscale image.

To apply the filter, simply move the center (or origin) of the template image over each point in the search image and calculate the sum of products, similar to a dot product, between the pixel values in the search and template images over the whole area spanned by the template.

Note that all possible positions of the template with respect to the search image are considered.

Another way to handle translation problems on images using template matching is to compare the intensities of the pixels, using the sum of absolute differences (SAD) measure.

denote the light intensity of pixels in the search and template images with coordinates

With this measure, the lowest SAD gives the best position for the template, rather than the greatest as with cross correlation.

[14] These lower resolution images can then be searched for the template (with a similarly reduced resolution), in order to yield possible start positions for searching at the larger scales.

The larger images can then be searched in a small window around the start position to find the best template location.

Other methods can handle problems such as translation, scale, image rotation and even all affine transformations.

It is also possible to improve the accuracy of the matching method by hybridizing the feature-based and template-based approaches.

Other methods which are similar include 'Stereo matching', 'Image registration' and 'Scale-invariant feature transform'.

Systems have been developed and used in the past to count the number of faces that walk across part of a bridge within a certain amount of time.

Other systems include automated calcified nodule detection within digital chest X-rays.

[19] Recently, this method was implemented in geostatistical simulation which could provide a fast algorithm.