Editing Template matching (section)

==Template-based matching explained using cross correlation or sum of absolute differences==

A basic method of template matching sometimes called "Linear Spatial Filtering" uses an image patch (i.e., the "template image" or "filter mask") tailored to a specific [[Feature (computer vision)|feature]] of search images to detect.{{citation needed|date=May 2020}} This technique can be easily performed on grey images or [[Edge detection|edge]] images, where the additional variable of color is either not present or not relevant. [[Cross correlation]] techniques compare the similarities of the search and template images. Their outputs should be highest at places where the image structure matches the template structure, i.e., where large search image values get multiplied by large template image values.

This method is normally implemented by first picking out a part of a search image to use as a template. Let <math>S(x,y)</math> represent the value of a search image pixel, where <math>(x,y)</math> represents the coordinates of the [[pixel]] in the search image. For simplicity, assume pixel values are scalar, as in a [[Grayscale images|greyscale image]]. Similarly, let <math display="inline">T(x_t,y_t)</math> represent the value of a template pixel, where <math display="inline">(x_t,y_t)</math> represents the coordinates of the pixel in the template 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. More formally, if <math>(0,0)</math> is the center (or origin) of the template image, then the cross correlation <math>T\star S</math> at each point <math>(x,y)</math> in the search image can be computed as:<math display="block">(T\star S)(x,y) = \sum_{(x_t,y_t)\in T} T(x_t,y_t) \cdot S(x_t+x, y_t+y)</math>For convenience, <math>T</math> denotes both the pixel values of the template image as well as its [[Domain of a function|domain]], the bounds of the template. Note that all possible positions of the template with respect to the search image are considered. Since cross correlation values are greatest when the values of the search and template pixels align, the best matching position <math>(x_m,y_m)</math> corresponds to the maximum value of <math>T\star S</math> over <math>S</math>.

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. To formulate this, let <math>I_S(x_s,y_s)</math> and <math>I_T(x_t,y_t)</math> denote the [[Luminous intensity|light intensity]] of pixels in the search and template images with coordinates <math>(x_s,y_s)</math> and <math>(x_t,y_t)</math>, respectively. Then by moving the center (or origin) of the template to a point <math>(x,y)</math> in the search image, as before, the sum of [[absolute difference|absolute differences]] between the template and search pixel intensities at that point is:'''<math display="block"> SAD(x, y) = \sum_{(x_t,y_t)\in T} \left\vert I_T(x_t,y_t) - I_S(x_t+x,y_t+y) \right\vert </math>'''With this measure, the ''lowest'' SAD gives the best position for the template, rather than the greatest as with cross correlation. SAD tends to be relatively simple to implement and understand, but it also tends to be relatively slow to execute. A simple [[C++]] implementation of SAD template matching is given below.