Template Matching

Template matching finds where a small reference image, the template, appears in a larger image. It slides the template over every candidate position, scores how well the template agrees with the image patch under it, and reports the position with the best score. It is the most direct way to locate a known pattern: a part on a conveyor in industrial visual inspection, a patch from the previous frame in a tracker, a block from a reference frame in block matching, or a marker in a calibration image. Its scores are the similarity and distance measures applied to image patches, and correlation with an unflipped template is the cross-correlation form of convolution. This article covers template search in general: the measures as used for search, how they relate, how normalized cross-correlation is computed fast, how template size and texture set the accuracy of the answer, and what the method cannot handle.

Problem

Given an image $I$ and a template $T$ of $h \times w$ pixels, find the translation $(u, v)$ at which the patch of $I$ whose top-left corner is at $(u, v)$ looks most like $T$ , and decide whether that best match is good enough to count as a detection. The template is usually cut from another image of the same object, so the problem assumes that the object appears in $I$ with about the same size, orientation and shape. When several copies may be present, every local maximum of the score above a threshold counts, usually after non-maximum suppression.

Inputs and Outputs

Input: an image $I$ of $H \times W$ pixels (or a search window around a predicted position), a template $T$ of $h \times w$ pixels with $h \le H$ and $w \le W$ , a score, and optionally a mask that selects or weights template pixels.
Output: a score map $R$ of $(H - h + 1) \times (W - w + 1)$ values, one per position at which the template fits entirely inside the image, and the position of its best value (or of every peak above a threshold). OpenCV’s matchTemplate and scikit-image’s match_template both return this map with entries indexed by the template’s top-left corner; scikit-image’s pad_input=True pads the image so the map has the image’s size and is indexed by the template’s centre.

Intuition

Lay the template on the image like a transparency and slide it around. Where the template sits on the right place, every template pixel lies over an image pixel of the same brightness, and the differences are small. Everywhere else, the differences are as large as the image’s contrast allows. Summing the squared or absolute differences over the template gives a distance that is zero at a perfect match.

Two practical difficulties shape everything else. The first is brightness: if the target is lit more strongly in the image than in the template, every difference grows, and a raw distance can prefer some other patch. Subtracting each patch’s mean and dividing by its spread before comparing removes a gain and an offset; this is normalized cross-correlation. The second is geometry: the comparison is pixel by pixel at fixed offsets, so anything that moves pixels relative to one another, rotation, scaling, perspective or deformation, lowers the score of the true position, and more so the larger the template.

Algorithm

Choose the score: a distance to minimize (SSD, SAD) or a similarity to maximize (cross-correlation, NCC).
Optionally preprocess: convert to grey levels or keep channels, smooth to suppress noise, or build an image pyramid for a coarse-to-fine search.
For every candidate position $(u, v)$ (exhaustive search), or for a subset chosen by a search strategy, compute the score between $T$ and the patch $I(u{:}u{+}h,\, v{:}v{+}w)$ .
Take the best position. For several targets, take local maxima above a threshold and suppress neighbours.
Optionally refine to sub-pixel precision by fitting a function to the scores around the best integer position, or by gradient-based alignment started there.
Accept or reject the match by its score. For NCC the score has a fixed range, so one threshold works across images; for SSD and SAD the threshold depends on the template’s size and contrast.

Mathematical Formulation

Write the template’s pixels as $T(x, y)$ for $0 \le x < h$ , $0 \le y < w$ , and the image patch at position $(u, v)$ as $I(u + x, v + y)$ . Sums run over the template’s pixels.

Distances and correlation

\mathrm{SSD}(u, v) = \sum_{x, y} \big[ I(u + x, v + y) - T(x, y) \big]^2, \qquad \mathrm{SAD}(u, v) = \sum_{x, y} \big| I(u + x, v + y) - T(x, y) \big| .

Expanding the square splits the SSD into three terms:

\mathrm{SSD}(u, v) = \underbrace{\sum_{x, y} I(u + x, v + y)^2}_{E_I(u, v)} \; - \; 2 \underbrace{\sum_{x, y} I(u + x, v + y)\, T(x, y)}_{C(u, v)} \; + \; \underbrace{\sum_{x, y} T(x, y)^2}_{E_T} .

$C$ is the cross-correlation of image and template: the template is not flipped, which is the difference between correlation and convolution. $E_T$ is a constant, and if the local image energy $E_I(u, v)$ were constant too, minimizing SSD and maximizing $C$ would pick the same position; Lewis (1995) motivates correlation for template matching by exactly this expansion. When $E_I$ varies, they part ways. Lewis gives the failure case: the correlation between the template and an exactly matching region can be smaller than its correlation with a bright spot, since $C$ grows with the patch’s brightness, and the range of $C$ depends on the template’s size and amplitudes. The SSD does not have this problem; it penalizes a bright patch through $E_I$ .

Minimizing the SSD is the maximum-likelihood estimate of the position when the image equals the shifted template plus independent Gaussian noise, and minimizing the SAD is the maximum-likelihood estimate under Laplace noise; the maximum likelihood estimation article derives both and compares them under several noise models.

Normalized cross-correlation

The correlation coefficient removes the mean of the template and of each patch and divides by their lengths:

\gamma(u, v) = \frac{\sum_{x, y} \big[ I(u + x, v + y) - \bar{I}_{u, v} \big] \big[ T(x, y) - \bar{T} \big]} {\sqrt{\sum_{x, y} \big[ I(u + x, v + y) - \bar{I}_{u, v} \big]^2 \; \sum_{x, y} \big[ T(x, y) - \bar{T} \big]^2}} ,

where $\bar{T}$ is the template’s mean and $\bar{I}_{u, v}$ the mean of the patch under it. Lewis (1995) calls $\gamma$ normalized cross-correlation; it is also called zero-mean NCC (ZNCC). It is the cosine of the angle between the mean-subtracted patch and template, lies in $[-1, 1]$ , equals 1 exactly when the patch is a positive gain times the template plus an offset, and is undefined when the patch or the template has no variance.

Names differ between sources and libraries, so the formula matters more than the name:

OpenCV mode	Score	Best match
`TM_SQDIFF`	SSD	minimum
`TM_SQDIFF_NORMED`	SSD divided by $\sqrt{E_T\, E_I(u, v)}$	minimum
`TM_CCORR`	$C$	maximum
`TM_CCORR_NORMED`	$C / \sqrt{E_T\, E_I(u, v)}$ , no mean subtraction	maximum
`TM_CCOEFF`	numerator of $\gamma$	maximum
`TM_CCOEFF_NORMED`	$\gamma$	maximum

The formulas are those documented in OpenCV 4.10.0’s imgproc.hpp. For colour images, OpenCV sums the numerator and each sum in the denominator over all channels, with a separate mean per channel, and returns a single-channel map. An optional mask restricts the sums to selected template pixels or weights them. scikit-image’s match_template computes $\gamma$ , the TM_CCOEFF_NORMED score. The two libraries treat a patch or template without variance differently: in the 4.10.0 source, OpenCV fills the whole map with 1 when the template is flat under TM_CCOEFF_NORMED, and scikit-image 0.25.2 sets the score to 0 wherever the denominator does not exceed machine epsilon.

Fast computation

Computed directly, every score costs $hw$ operations per position. Lewis (1995) counts, for a template of $N^2$ pixels and a search window of $M^2$ , about $N^2 (M - N + 1)^2$ multiplications and as many additions for the numerator of $\gamma$ . Since the numerator is a correlation, the convolution theorem gives it through the Fourier transform as $\mathcal{F}^{-1}\{\mathcal{F}(I)\, \mathcal{F}^*(T')\}$ , with $T' = T - \bar{T}$ ; because $T'$ sums to zero, the patch mean drops out of the numerator. Lewis gives the transform method’s cost as $12 M^2 \log_2 M$ real multiplications (the conference version and the expanded version differ in the count of additions), notes that the direct method is faster when $M$ is much larger than $N$ , and that the transform method gains as $N$ approaches $M$ and as both grow.

The denominator was the obstacle to doing all of this in the frequency domain: it needs the patch’s mean and energy at every position. Lewis’s contribution was to take them from running-sum tables of $I$ and $I^2$ ,

s(u, v) = I(u, v) + s(u - 1, v) + s(u, v - 1) - s(u - 1, v - 1),

and the same for $I^2$ , so that the sum over any $h \times w$ window is four table look-ups. The conference version credits this use of a running sum to Crow’s (1984) summed-area tables for texture mapping, and the expanded version notes that the technique has been used independently in several fields; it is the integral image that Haar-like features are computed with. The expanded version of the paper adds a numerical caution: the running sums are marginally stable recursions, and Lewis recommends large-integer rather than floating-point arithmetic for them.

Both libraries follow this scheme. scikit-image’s match_template computes the correlation with SciPy’s fftconvolve and the window sums by cumulative sums. OpenCV’s CPU path computes the correlation with a block-wise DFT (or with Intel IPP routines in builds that include them) and then normalizes it with integral images in double precision. The same window sums turn the SSD into $E_I - 2C + E_T$ at the cost of one correlation.

Lewis reports the effect on feature tracking for the visual effects of Forrest Gump (1994). Re-tracking two sequences with identical templates and search windows took 15 hours with direct NCC and 1.7 hours with the transform method for 896 frames, and 14.3 hours against 57 minutes for 490 frames, including a sub-pixel search at the best whole-pixel match. The two versions of the paper describe the machine differently (a workstation of about 60 SPECmarks in the conference version, a 100 MHz R4000 processor in the expanded one) for the same timings.

Localization accuracy

How precisely can the peak be located? Consider the model in which the image is the template shifted by $(u_0, v_0)$ plus independent Gaussian noise of standard deviation $\sigma_n$ . The Fisher information for the shift is the sum, over the template, of the outer product of its gradients divided by $\sigma_n^2$ , so the Cramér–Rao bound for an unbiased estimate is (our derivation)

\operatorname{Var}(\hat{u}) \ge \frac{\sigma_n^2}{\sum_{x, y} T_x^2}, \qquad \operatorname{Var}(\hat{v}) \ge \frac{\sigma_n^2}{\sum_{x, y} T_y^2}

when the gradients along the two axes are uncorrelated. The $2 \times 2$ matrix of summed gradient products is the structure tensor of the Harris corner detector, summed over the template (our observation): a template that is good to detect as a corner is good to localize. The same quantity sets the shape of the score map. For a texture whose autocorrelation is $\rho(d) = e^{-d^2/(4 s^2)}$ and whose variance is 1, the expected squared derivative is $-\rho''(0) = 1/(2 s^2)$ , so the bound’s standard deviation per axis is about $\sigma_n s \sqrt{2} / N$ for an $N \times N$ template (our derivation). A sharp autocorrelation peak (small $s$ ) and a large template both give precise positions. As a prediction of the actual error, the bound is a small-noise approximation: once the noise is large compared with the peak’s curvature, the maximum can jump to another peak and the error grows far beyond it.

Parameters

Score. SSD or SAD when brightness is the same in template and image (frame-to-frame tracking, video coding); NCC when gain or offset may change. NCC costs more and is unstable on flat patches, where it divides by almost zero.
Template size. A larger template contains more structure and averages more noise, so it localizes better and gives fewer false peaks; Lewis (1995) notes that larger features are less affected by film grain and motion blur, and that feature tracking for film used search windows of $50^2$ pixels and more. A larger template also suffers more from rotation, scale change and deformation, and is more likely to include background (see the example).
Template content. Textured templates give narrow, well-localized peaks; smooth templates give broad peaks, which tolerate small geometric changes but locate poorly. Uniform or one-dimensional templates (a straight edge) have no unique peak along the uniform direction, the aperture problem of optical flow.
Search range. The window searched around a predicted position; the cost grows with its area, and a target outside it cannot be found.
Acceptance threshold. On NCC, a score threshold expresses how similar the patch must be; on SSD it depends on the template’s size and contrast.
Pre-filtering. Smoothing reduces noise and widens the peak; high-pass filtering reduces slow brightness changes, which Lewis notes is hard to tune: a low cutoff leaves energy variations, a high one removes useful structure.

Complexity

For an $H \times W$ image and an $h \times w$ template, the direct method costs $O(HWhw)$ , with SSD, SAD and NCC all in this class. With the FFT, the correlation costs $O(HW \log(HW))$ independently of the template size, and the window sums for the normalization or the SSD’s $E_I$ term cost $O(HW)$ from integral images. OpenCV splits the image into blocks a few template sizes wide and transforms each, which keeps the transforms small. The SAD has no such shortcut, since the absolute value does not expand into correlations (our reasoning), and is computed directly; video coders, which use it, prune the search instead (see block matching). Memory is $O(HW)$ for the score map and the tables.

Implementation

The script below runs three experiments on synthetic textures, so the true positions are known exactly. Each texture is white Gaussian noise filtered with a Gaussian of standard deviation $s$ pixels and rescaled to zero mean and unit standard deviation; its autocorrelation is close to $e^{-d^2/(4 s^2)}$ at distance $d$ .

SSD, correlation and NCC. A $21 \times 21$ template is cut at $(40, 40)$ from a $160 \times 160$ pattern of $\pm 1$ values, the sign of a texture with $s = 2$ . Because every pixel squares to 1, the local energy $E_I$ is the same at every position. A second image triples the contrast in rows and columns 90 to 149 (the slice 90:150), away from the target. The code computes SSD, correlation and NCC directly, checks the expansion $\mathrm{SSD} = E_I - 2C + E_T$ with $E_I$ from an integral image, and compares the hand-written NCC with scikit-image’s match_template.
Rotation. A texture with $s = 2$ is rotated counter-clockwise about the template centre by 0 to 45° (cubic interpolation), and square templates of 9, 17, 33 and 65 pixels cut from the unrotated texture are matched by NCC within $\pm 16$ pixels. Each NCC value at the true position is printed beside a prediction: a pixel at radius $r$ from the centre moves by $d = 2 r \sin(\theta / 2)$ , so the expected correlation is the mean of $e^{-d^2/(4 s^2)}$ over the template’s pixels. A star marks cases where the NCC maximum lies more than 1 pixel from the truth.
Localization under noise. Templates of 17 and 33 pixels are cut from textures with $s = 1, 2, 4, 8$ and matched within $\pm 8$ pixels after white noise of standard deviation 0.5 or 1.0 is added to the search image (and with no noise). Each cell has 200 trials, and positions more than 2 pixels off count as failures and are left out of the errors. The integer peak is refined with a parabola through three scores on each axis (the refinement the block matching article compares with others). The table gives the full width at half maximum of the template’s NCC profile along $x$ (“ACF FWHM”, from a $\pm 40$ pixel strip of the noise-free texture), the RMS error of the integer and of the refined position, and the Cramér–Rao estimate $\sigma_n \sqrt{1/\sum T_x^2 + 1/\sum T_y^2}$ with central-difference gradients (“CR est.”). The column “sigma” is the texture’s filter width $s$ .

Positions are (row, column) of the template’s top-left corner in the first part and offsets within the search window in the others, where the truth is at the window’s centre. It uses Python 3.13 (the f-string with nested double quotes needs 3.12 or later), NumPy 2.3.5, SciPy 1.16.3 and scikit-image 0.25.2, sets the threading libraries to one thread, and runs in about a second; two runs gave identical output.

import os
os.environ["OMP_NUM_THREADS"] = "1"          # one BLAS/FFT thread: reproducible sums
os.environ["OPENBLAS_NUM_THREADS"] = "1"
os.environ["MKL_NUM_THREADS"] = "1"
import numpy as np
import scipy
import skimage
from scipy import ndimage
from skimage.feature import match_template
from skimage.transform import rotate

def texture(seed, s, size=256):
    """Gaussian-filtered white noise (filter sigma s px), zero mean, unit std.
    Its autocorrelation is close to exp(-d^2 / (4 s^2)) at distance d."""
    g = ndimage.gaussian_filter(np.random.default_rng(seed).standard_normal((size, size)), s)
    return (g - g.mean()) / g.std()

def box_sum(a, h, w):
    """Sum of a over every h x w window (valid positions), via an integral image."""
    c = np.pad(a, ((1, 0), (1, 0))).cumsum(0).cumsum(1)
    return c[h:, w:] - c[:-h, w:] - c[h:, :-w] + c[:-h, :-w]

def scores(f, t):
    """Raw cross-correlation C, SSD and zero-mean NCC of template t at every valid
    top-left position of image f (direct sums, no FFT)."""
    h, w = t.shape
    win = np.lib.stride_tricks.sliding_window_view(f, (h, w))
    C = np.einsum("ijkl,kl->ij", win, t)
    ssd = ((win - t) ** 2).sum(axis=(2, 3))
    wz = win - win.mean(axis=(2, 3), keepdims=True)
    tz = t - t.mean()
    ncc = np.einsum("ijkl,kl->ij", wz, tz) / np.sqrt((wz ** 2).sum(axis=(2, 3)) * (tz ** 2).sum())
    return C, ssd, ncc

print("NumPy", np.__version__, "SciPy", scipy.__version__, "scikit-image", skimage.__version__)

# ---- Part 1: SSD, correlation and NCC on a +-1 pattern and on one with a high-contrast region
f = np.sign(texture(0, 2.0, 160))             # binary pattern: f**2 == 1 everywhere
t0 = (40, 40); n = 21
t = f[t0[0]:t0[0] + n, t0[1]:t0[1] + n].copy()
print("\nPart 1: 21 x 21 template cut at", t0, "from a 160 x 160 pattern of +-1 values")
for name, img in [("+-1 pattern", f), ("contrast x3 in rows/cols 90-150", f.copy())]:
    if name.startswith("contrast"):
        img[90:150, 90:150] *= 3.0            # a region of three times the contrast, away from the target
    C, ssd, ncc = scores(img, t)
    energy = box_sum(img ** 2, n, n)          # local image energy under the template
    ident = np.abs(ssd - (energy - 2 * C + (t ** 2).sum())).max()
    sk = np.abs(ncc - match_template(img, t)).max()
    loc = lambda a: tuple(int(v) for v in np.unravel_index(np.argmax(a), a.shape))
    print(f"  {name}: |SSD - (E_f - 2C + E_t)| max {ident:.1e}; local energy range "
          f"{energy.min():.0f}-{energy.max():.0f}; std of SSD + 2C {np.std(ssd + 2 * C):.1e}")
    print(f"    best position: SSD {loc(-ssd)}  correlation {loc(C)}  NCC {loc(ncc)}  "
          f"(truth {t0}); hand NCC vs match_template max diff {sk:.1e}")

# ---- Part 2: NCC under rotation of the target, for four template sizes
s, R = 2.0, 16
scene = texture(1, s, 256)
cy = cx = 128                                  # rotation centre = template centre
angles = [0, 2, 5, 10, 20, 30, 45]
sizes = [9, 17, 33, 65]
rotated = {a: rotate(scene, a, center=(cx, cy), order=3, mode="reflect", preserve_range=True)
           for a in angles}
print(f"\nPart 2: texture with filter sigma {s} px rotated about the template centre;"
      f" NCC at the true position (predicted from the autocorrelation in brackets),"
      f" * = NCC maximum within +-{R} px is more than 1 px from the truth")
print("size  " + "".join(f"{str(a) + ' deg':>15s}" for a in angles))
for N in sizes:
    h = N // 2
    tpl = scene[cy - h:cy + h + 1, cx - h:cx + h + 1]
    yy, xx = np.mgrid[-h:h + 1, -h:h + 1]
    r = np.hypot(yy, xx)
    row = []
    for a in angles:
        img = rotated[a][cy - h - R:cy + h + R + 1, cx - h - R:cx + h + R + 1]
        m = match_template(img, tpl)
        at_truth = m[R, R]
        py, px = np.unravel_index(np.argmax(m), m.shape)
        lost = max(abs(py - R), abs(px - R)) > 1
        d = 2 * r * np.sin(np.radians(a) / 2)                  # displacement of each pixel
        pred = np.exp(-d ** 2 / (4 * s ** 2)).mean()
        row.append(f"{at_truth:6.3f} ({pred:.3f}){'*' if lost else ' '}")
    print(f"{N:4d}  " + "".join(f"{c:>15s}" for c in row))

# ---- Part 3: localization error under noise against the autocorrelation width
print("\nPart 3: target at a known integer position, white noise added to the search image,"
      " 200 trials per cell; errors in px")
print(f"{'sigma':>5s} {'size':>4s} {'ACF FWHM':>8s} {'noise':>5s} {'fail':>5s} "
      f"{'RMS int':>8s} {'RMS sub':>8s} {"CR est.":>7s}")
R = 8
for s in [1.0, 2.0, 4.0, 8.0]:
    sc = texture(2, s, 256)
    for N in [17, 33]:
        h = N // 2
        tpl = sc[128 - h:128 + h + 1, 128 - h:128 + h + 1]
        clean = sc[128 - h - R:128 + h + R + 1, 128 - h - R:128 + h + R + 1]
        wide = sc[128 - h:128 + h + 1, 128 - h - 40:128 + h + 41]
        acf = match_template(wide, tpl)[0, :]                   # NCC profile along x through the peak (+-40 px)
        above = np.where(acf >= 0.5)[0]                         # full width at half maximum, linear interpolation
        lo, hi = above.min(), above.max()
        left = lo - (acf[lo] - 0.5) / (acf[lo] - acf[lo - 1])
        right = hi + (acf[hi] - 0.5) / (acf[hi] - acf[hi + 1])
        gy, gx = np.gradient(tpl)
        for sn in [0.0, 0.5, 1.0]:
            rng = np.random.default_rng(3)
            trials = 1 if sn == 0 else 200
            e_int, e_sub, fails = [], [], 0
            for _ in range(trials):
                m = match_template(clean + sn * rng.standard_normal(clean.shape), tpl)
                py, px = np.unravel_index(np.argmax(m), m.shape)
                if max(abs(py - R), abs(px - R)) > 2:
                    fails += 1
                    continue
                sub = []
                for (a, b, c), p in [((m[py - 1, px], m[py, px], m[py + 1, px]), py),
                                     ((m[py, px - 1], m[py, px], m[py, px + 1]), px)]:
                    den = a - 2 * b + c                         # parabola through three samples
                    sub.append(p + (0.5 * (a - c) / den if den < 0 else 0.0))
                e_int.append(np.hypot(py - R, px - R))
                e_sub.append(np.hypot(sub[0] - R, sub[1] - R))
            crlb = sn * np.sqrt(1 / (gx ** 2).sum() + 1 / (gy ** 2).sum())
            rms = lambda e: np.sqrt(np.mean(np.square(e))) if e else float("nan")
            print(f"{s:5.0f} {N:4d} {right - left:8.2f} {sn:5.1f} {fails:5d} "
                  f"{rms(e_int):8.3f} {rms(e_sub):8.3f} {crlb:7.3f}")

NumPy 2.3.5 SciPy 1.16.3 scikit-image 0.25.2

Part 1: 21 x 21 template cut at (40, 40) from a 160 x 160 pattern of +-1 values
  +-1 pattern: |SSD - (E_f - 2C + E_t)| max 0.0e+00; local energy range 441-441; std of SSD + 2C 0.0e+00
    best position: SSD (40, 40)  correlation (40, 40)  NCC (40, 40)  (truth (40, 40)); hand NCC vs match_template max diff 3.3e-16
  contrast x3 in rows/cols 90-150: |SSD - (E_f - 2C + E_t)| max 0.0e+00; local energy range 441-3969; std of SSD + 2C 1.2e+03
    best position: SSD (40, 40)  correlation (98, 115)  NCC (40, 40)  (truth (40, 40)); hand NCC vs match_template max diff 3.9e-16

Part 2: texture with filter sigma 2.0 px rotated about the template centre; NCC at the true position (predicted from the autocorrelation in brackets), * = NCC maximum within +-16 px is more than 1 px from the truth
size            0 deg          2 deg          5 deg         10 deg         20 deg         30 deg         45 deg
   9   1.000 (1.000)  0.998 (0.999)  0.987 (0.994)  0.941 (0.975)  0.707 (0.906)  0.289 (0.807)*-0.219 (0.641)*
  17   1.000 (1.000)  0.996 (0.996)  0.971 (0.978)  0.890 (0.914)  0.627 (0.714)  0.346 (0.503)* 0.078 (0.285)*
  33   1.000 (1.000)  0.987 (0.986)  0.925 (0.919)  0.741 (0.725)  0.367 (0.351)* 0.173 (0.171)*-0.025 (0.079)*
  65   1.000 (1.000)  0.953 (0.948)  0.749 (0.731)  0.384 (0.357)  0.175 (0.099)* 0.148 (0.044)* 0.013 (0.020)*

Part 3: target at a known integer position, white noise added to the search image, 200 trials per cell; errors in px
sigma size ACF FWHM noise  fail  RMS int  RMS sub CR est.
    1   17     3.38   0.0     0    0.000    0.014   0.000
    1   17     3.38   0.5     0    0.000    0.062   0.074
    1   17     3.38   1.0     0    0.000    0.125   0.148
    1   33     3.33   0.0     0    0.000    0.005   0.000
    1   33     3.33   0.5     0    0.000    0.028   0.041
    1   33     3.33   1.0     0    0.000    0.056   0.081
    2   17     6.06   0.0     0    0.000    0.042   0.000
    2   17     6.06   0.5     0    0.000    0.207   0.123
    2   17     6.06   1.0     0    0.574    0.483   0.246
    2   33     6.61   0.0     0    0.000    0.013   0.000
    2   33     6.61   0.5     0    0.000    0.072   0.071
    2   33     6.61   1.0     0    0.000    0.146   0.142
    4   17    10.98   0.0     0    0.000    0.100   0.000
    4   17    10.98   0.5     0    0.775    0.633   0.179
    4   17    10.98   1.0     0    1.487    1.429   0.358
    4   33    11.71   0.0     0    0.000    0.028   0.000
    4   33    11.71   0.5     0    0.000    0.174   0.116
    4   33    11.71   1.0     0    0.400    0.407   0.232
    8   17    12.23   0.0     0    0.000    0.120   0.000
    8   17    12.23   0.5    12    1.769    1.734   0.447
    8   17    12.23   1.0    97    1.933    1.943   0.894
    8   33    15.94   0.0     0    0.000    0.017   0.000
    8   33    15.94   0.5     0    1.037    0.979   0.198
    8   33    15.94   1.0    42    1.874    1.888   0.395

Energy and the choice of score. On the $\pm 1$ pattern the local energy is 441 at every position, $\mathrm{SSD} + 2C$ is constant, and the three scores rank every position identically, as the expansion predicts. Tripling the contrast in one region raises the local energy there up to $9 \times 441$ , and the correlation’s maximum moves into that region, to $(98, 115)$ , while the SSD and NCC still find the target. This is Lewis’s bright-spot failure: a high-contrast patch that resembles the template only by chance outscores the exact match because $C$ scales with the patch. The expansion holds exactly in both images, and the integral-image sums and the FFT-based library agree with the direct sums to rounding error.

Rotation. At 0° every template scores 1, and the score at the true position then falls with the angle, faster the larger the template: at 10° it is 0.94 for the 9-pixel template and 0.38 for the 65-pixel one. This order holds at every angle up to 20°; at 30° and 45°, where every template has lost its peak, it no longer does (at 30° the 9-pixel template scores 0.29 against 0.35 for the 17-pixel one). The prediction explains why. A pixel at radius $r$ moves by about $r\theta$ , and once that motion is comparable with the texture’s correlation length, the pixel no longer correlates with its counterpart; in the printed values, doubling the template roughly halves the angle the match tolerates (0.37 at 20° for 33 pixels, 0.38 at 10° for 65). The peak is lost (another position scores higher) from 30° for the 9- and 17-pixel templates and from 20° for the 33- and 65-pixel ones. The hypothesis that the measured values track the prediction held only in part. They agree to within 0.03 for the 33- and 65-pixel templates up to 10°, and for the 33-pixel template up to 30°, but for the 9- and 17-pixel templates at 20° and beyond the prediction is far above the measurement (0.807 against 0.289 at 30° for 9 pixels), it is 0.10 above the measurement for the 33-pixel template at 45°, and for the 65-pixel template at 20° and 30° the measurement lies above the prediction (0.148 against 0.044 at 30°). In our reading, which the example does not test, the prediction is an average over textures, while a small template contains only a few correlation lengths of one texture, so its value under rotation depends on that particular patch, and the subtraction of each window’s mean adds a further change the prediction ignores.

Localization against peak width. Without noise, the integer peak is exact in every case; the parabola then adds a small error of its own (up to 0.12 pixels), because the score map of a finite random patch is not exactly symmetric about its peak. With noise, the refined error grows with the texture’s correlation length and falls with the template’s size, as the bound’s $\sigma_n s \sqrt{2} / N$ suggests: at $\sigma_n = 0.5$ it rises from 0.03 pixels ( $s = 1$ , 33 pixels) to about 1 pixel ( $s = 8$ , 33 pixels), and the 17-pixel template is worse than the 33-pixel one in every noisy cell. Gross failures appear only for the widest texture, $s = 8$ , and most for the smaller template (97 of 200 at $\sigma_n = 1$ ). The hypothesis that the refined error lies near the Cramér–Rao estimate held only in part. It holds for $s = 2$ with the 33-pixel template, where the two agree to within 0.004 pixels. At $s = 1$ the printed errors fall below the estimate in all four noisy cells. In our reading, which the example does not test, two things contribute: the true position is an integer, and a parabola fitted around an integer peak pulls its estimates toward the integer, so the estimate is biased in a direction that favours this example; and central differences underestimate the gradients of so fine a texture, which inflates the estimate. In every other noisy cell the errors exceed the estimate: by about a factor of 1.5 to 2 for $s = 2$ with 17 pixels and $s = 4$ with 33 pixels, and by a factor of 3.5 to 5 where the peak is wide compared with the template ( $s = 4$ with 17 pixels, $s = 8$ with either size; the exception, a factor of 2.2 for $s = 8$ with 17 pixels at $\sigma_n = 1$ , excludes the 97 failed trials). There the integer peak itself moves, and the small-noise approximation no longer applies.

The printed peak widths are narrower than the texture’s autocorrelation, whose full width at half maximum is $4 s \sqrt{\ln 2} \approx 3.33\, s$ , that is 26.6 pixels for $s = 8$ against the printed 12.2 and 15.9. This follows from the code’s construction: NCC subtracts each window’s mean, which removes the slow variations that a window cannot contain and that make the texture’s own autocorrelation wide, and it does so more for the smaller window. For $s = 1$ and $s = 2$ the windows are many correlation lengths wide, and the widths are close to $3.33\, s$ .

Taken together, the experiments show the trade-off that sets template size and content. A narrow peak (fine texture, large template) gives a precise position but a match that rotation, scaling or deformation destroys quickly; a wide peak tolerates small geometric changes but locates poorly and, with small templates, fails under noise. The expanded version of Lewis’s paper makes the related point that small or textured templates give error surfaces with narrow extrema, which limits how far a gradient-based search can track.

Properties and Behavior

Exhaustive and global. Over its search window, exhaustive matching finds the best-scoring position without an initial guess, unlike gradient-based alignment such as Lucas–Kanade, which needs a start within its basin of convergence. In the expanded version of his paper, Lewis contrasts this with gradient-descent search, which succeeds only when the motion between frames is smaller than the basin around the error minimum, and notes that cross-correlation can track a feature that moves by a significant fraction of its own size, a motion that could put an active contour outside its basin of convergence.
Invariances. SSD and SAD are invariant to nothing but translation. NCC is in addition invariant to a positive gain and an offset of the patch’s grey levels, and TM_CCORR_NORMED to a gain only. None is invariant to rotation, scale or perspective; the expanded version of Lewis’s paper names these as the reasons NCC is not an ideal approach to feature tracking.
Score map shape. The peak’s width follows the template’s autocorrelation, and its sharpness along each axis follows the template’s gradients along that axis, as derived above. An edge template gives a ridge rather than a peak; a periodic pattern (bricks, text, a grid) gives several similar peaks, which, the expanded version of Lewis’s paper notes, can mislead a pruned search such as SSDA (below).
Sub-pixel precision. Fitting a parabola or other function to the scores around the integer peak gives sub-pixel positions, possibly with a bias toward integer positions (see the example); the block matching article compares such refinements, and gradient-based alignment started from the integer peak is the other common option.
Confidence. In our reading, the best NCC value and the gap between the best and second-best peaks indicate how reliable a match is: a high best value with a close second peak suggests a repeated pattern.

Limitations

Geometric change. Rotation, scaling, perspective and non-rigid deformation lower the true peak quickly, and faster for larger templates (example, part 2).
Background inside the template. A rectangular template cut around an object also contains background. When the object moves against a different background, those pixels disagree, and Dekel et al. (2015) point out that measuring similarity over all pixels then leads to false detections. A mask helps when the object’s outline is known.
Occlusion. Every pixel counts equally, so an occluded part adds error at the true position; in our reasoning SSD suffers most, since the squared errors of the occluded pixels dominate its sum.
Illumination. NCC removes a global gain and offset of the patch, but not shading that varies across the patch, shadows or specular highlights.
Flat and repetitive content. A template without texture has no well-defined peak and makes NCC unstable; a repetitive one has several.
Cost. An exhaustive search over a large image, several scales and several rotations multiplies the work of one correlation by the number of templates.

Variants

Faster search

Pruned and early-terminating search. The sequential similarity detection algorithm (SSDA) of Barnea and Silverman (1972), as the expanded version of Lewis’s paper describes it, computes the correlation sum at each position in random order, uses the partial sum as an estimate of whether the position is near a maximum, and abandons the position when the estimate suggests a poor match. It is simple and fast but does not guarantee the best position, and it has parameters that must be set (the number of terms in the estimate and the termination threshold).
Coarse-to-fine search. Matching on a reduced image pyramid first and refining at full resolution narrows the search (coarse-to-fine estimation). Lewis notes that this needs images with enough low-frequency content to guide the first stages, which features such as a few small spots on a plain surface lack.
Gradient-based alignment. Lucas–Kanade minimizes the SSD by Gauss–Newton steps from a starting position, and extends to affine warps and homographies; it is precise and cheap but local.
Phase correlation. Normalizing the cross-power spectrum to unit magnitude turns the correlation into an impulse at the shift, for whole images that differ by a translation; it is described under image registration and the Fourier transform. The expanded version of Lewis’s paper notes that it weights all frequency components equally, including insignificant ones.

Geometric extensions

Template banks. Matching rotated and scaled copies of the template, or the template against a pyramid, covers rotation and scale at a cost proportional to the number of copies; sliding-window detection applies a template, or a classifier, at every position and scale in this way.
Affine template matching. FasT-Match (Korman, Reichman, Tsur and Avidan, 2013) searches over all 2D affine transformations and minimizes the SAD. The authors prove that the transformations can be sampled with a density that depends on the image’s smoothness, estimate the SAD of each sampled transformation from a small random sample of pixels, and accelerate the search with branch-and-bound, giving a result within an additive error of the global optimum. They list as limitations that it does not reach sub-pixel accuracy, that it can fail on highly textured images, where its guarantees do not hold, and that it weighs background pixels as heavily as foreground in sparse images such as diagrams and text.
Whole-image registration estimates one global transformation between two images, often with the same scores or, across modalities, with mutual information, as the image registration article describes.

Robust similarity

Best-Buddies Similarity (BBS). Dekel, Oron, Rubinstein, Avidan and Freeman (2015) break template and window into small patches described by colour and position, and count the pairs that are mutual nearest neighbours, which are found mostly on the object rather than on the changed background. On 105 template–image pairs that they sampled from 35 annotated tracking videos (a template from frame $f$ , the target image at frame $f + 20$ ), the area under the success curve of bounding-box overlap, using the global maximum, was 0.55 for BBS against 0.47 for NCC, 0.49 for SAD and 0.43 for SSD (their Fig. 7a).
Deformable Diversity Similarity (DDIS). Talmi, Mechrez and Zelnik-Manor (2017) score a window by the diversity of its points’ nearest-neighbour matches in the template and explicitly account for the deformation those matches imply; unlike BBS, the measure needs only one-directional nearest neighbours, which they describe as cheaper to compute. On a benchmark of template–image pairs from tracking videos at frame gaps of 25, 50 and 100, they report higher areas under the success curve than BBS, SSD, SAD and NCC with colour features and with deep features. Their text gives 270, 270 and 254 pairs for the three gaps, and their Fig. 6 caption 270 pairs.

Learned templates

Siamese trackers learn an embedding offline and match the target’s embedding against a search region by cross-correlation, a learned form of template matching; Siamese tracking covers them. Matching learned local descriptors at keypoints instead of whole templates is feature matching, which handles rotation, scale and partial occlusion at the cost of needing distinctive keypoints.