Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 46 ยท Segmentation and Shapes

Template Matching

Find a small patch inside a larger image with a sliding window. Compare SSD and normalized cross-correlation, speed it up with the FFT, and see its limits.

Sometimes you already know what you are looking for. A logo that always appears on a form, a screw head on a circuit board, a button icon in a screenshot, the same tile in a game. You have a small picture of it, the template, and you want to know where it sits in a larger image. Template matching answers that by sliding the template over every position and scoring how well it fits.

It is one of the simplest ideas in computer vision, and it teaches several lasting lessons: how a score map works, why raw differences are fragile, why normalizing matters, and why the same job can be done much faster in the frequency domain. It also fails in instructive ways when the object rotates or changes size, which is exactly why the feature methods in Keypoint Descriptors and Matching exist.

The sliding window and the score map

Let the scene be an array I of size H x W and the template an array T of size h x w. Place the template with its top-left corner at (r, c). The window of the scene under it is I[r:r+h, c:c+w]. Compute one number that says how similar the window is to the template. Do that for every valid (r, c) and you get a score map.

How many positions are there? The template must stay inside the image, so r runs from 0 to H - h and c from 0 to W - w. The score map is therefore (H - h + 1) x (W - w + 1). The location of the best score is your answer.

flowchart LR
    A["Scene I<br/>(H x W)"] --> C["Slide window<br/>to every (r, c)"]
    B["Template T<br/>(h x w)"] --> C
    C --> D["Score at each position"]
    D --> E["Score map<br/>(H-h+1) x (W-w+1)"]
    E --> F["argmax or argmin<br/>= best location"]

A score map has one value per template position; its best value is the match.

Sum of squared differences

The most direct score is the sum of squared differences (SSD): subtract the template from the window, square every difference and add them up. A perfect match gives 0, and larger numbers mean worse fits.

Python SSD: slide and score

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The score map is 24 by 44, as the formula (30 - 7 + 1) x (50 - 7 + 1) predicts. The pattern was found at exactly the row and column where we hid it. The best SSD, about 4,258, comes only from the small noise we added to the copy, while a typical window scores around 680,000, so the match stands out by a factor of more than a hundred.

np.unravel_index is the standard trick for turning the flat index returned by argmin into a (row, column) pair. The loops are slow in pure Python but crystal clear. Faster versions come below.

Why SSD is fragile

SSD compares absolute brightness. It is happiest when the window has the same numbers as the template, not when it has the same pattern. If the lighting changes, or the camera exposes the scene differently, the genuine object no longer has the same numbers, and a plain bright or flat region can score better than the object.

Normalized cross-correlation (NCC) fixes this. For each window it subtracts the window's mean and the template's mean (so overall brightness no longer matters) and divides by the product of their lengths (so contrast no longer matters):

TEXT
NCC = sum((W - mean(W)) * (T - mean(T))) / sqrt(sum((W - mean(W))^2) * sum((T - mean(T))^2))

The result lies between -1 and 1. A value of 1 means the window equals the template up to a brightness offset and a positive contrast factor (a * T + b with a > 0); 0 means no linear relationship; -1 means a perfect negative. This is the same quantity as the correlation coefficient in statistics.

The next example compares both scores on a normal scene and on a badly underexposed copy (10 percent brightness) that also contains a flat gray patch, like a gray wall.

Python SSD versus normalized correlation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both methods find the object in the normal scene. In the underexposed scene SSD (negated here so that "larger is better" for both) jumps to the flat gray patch at row 6, column 5. A flat patch with a medium brightness is a good average guess for any template, and when the real object has been dimmed to a tenth of its brightness, the flat patch has a smaller squared error. NCC is unaffected: it still reports position (14, 31) with a score of 0.997, because dimming is a pure scaling of the pattern.

Notice also the guard if denom > 0. A perfectly flat window has zero variance and NCC would divide by zero; the usual safe answer is a score of 0. In real code you add a tiny constant to the denominator.

Note: Library functions expose the same choices under names such as "squared difference", "correlation" and "correlation coefficient", each with a normalized variant. The "zero-mean normalized" version is what we called NCC here, and it is the one to choose when lighting may vary.

Speeding it up with the FFT

The loop version does h * w multiplications for each of about H * W positions. For a 1920 by 1080 frame and a 100 by 100 template that is on the order of 20 billion operations. Two observations help.

First, the sum in SSD expands: sum((W - T)^2) = sum(W^2) - 2 * sum(W * T) + sum(T^2). The last term is a constant. The middle term is a cross-correlation of the scene with the template, which you met in Convolution and Correlation. The first term is a sliding sum of squared pixels, which a box filter computes.

Second, convolution can be computed with the Fast Fourier Transform: transform both arrays, multiply, transform back. That costs roughly H * W * log(H * W) operations, independent of the template size. Correlation is convolution with the template flipped in both directions, so scipy.signal.fftconvolve(image, template[::-1, ::-1], mode="valid") gives the same numbers as the double loop.

Python Same answer, far fewer operations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two implementations agree to floating-point precision. The direct method needs 422,280 multiplications for this tiny scene; the FFT estimate is about 58,000 operations, and the gap widens quickly as the template grows. The ncc_fft function shows how to normalize without any loops: the window sums sum(W) and sum(W^2) come from correlating with an all-ones array, and the variance of every window follows as sum(W^2) - sum(W)^2 / n. Because we cut the template out of the scene itself, the best score is exactly 1.0 at row 20, column 41, where we cut it.

Do not assume the FFT is always faster. For very small templates the direct approach (or scipy.ndimage.correlate) wins, because the FFT has overhead and large padded arrays. Libraries pick a method for you; the sensible rule is "small template: direct; large template: FFT".

Limits: scale, rotation and everything else

Template matching compares pixels at fixed positions, so it only tolerates what the score tolerates. NCC handles brightness and contrast. It does not handle:

  • Rotation. Turn the object and the pixel grid no longer lines up with the template.
  • Scale. A closer or farther object covers a different number of pixels.
  • Perspective, deformation and occlusion. Viewing angle changes shape; partial hiding corrupts the window.
  • Clutter and repeated patterns. Several near-identical objects produce several peaks, and a plain background with texture similar to the template produces false peaks.

Here is how the best NCC score drops when we match a template cut from an unrotated, unscaled "L" shape against rotated and scaled versions of the same shape:

Python How fast the score falls

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The unchanged shape scores 0.994, but a 10 degree rotation already drops the score to 0.810, a 45 degree rotation to 0.456, and scaling by 0.7 or 1.3 gives 0.646 and 0.749. There is no single threshold that accepts the true object under every pose while rejecting look-alikes.

The classic workarounds are brute force: match many rotated and scaled copies of the template and keep the best (a multi-scale search, as in Image Pyramids and Scale Space), or match on edges or gradients instead of raw intensities. Both multiply the cost. When the pose varies a lot, it is better to detect keypoints and compare descriptors, or to train a detector (see Object Detection Basics).

flowchart TB
    A["Same lighting, same pose?"] -->|"yes"| B["SSD is enough"]
    A -->|"lighting varies"| C["Use zero-mean NCC"]
    C --> D["Scale or rotation varies?"]
    D -->|"a little"| E["Match several template copies"]
    D -->|"a lot"| F["Keypoints and descriptors,<br/>or a trained detector"]

Pick the simplest matcher that tolerates the variation your images really contain.

When template matching is the right tool, it is hard to beat for simplicity: fixed cameras, user-interface automation, industrial parts on a jig, tracking a patch between consecutive video frames and aligning two images that differ by a small shift.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A scene is 100 x 80 pixels and the template is 10 x 8. What is the shape of the full score map?

    The template can start at rows 0 to 90 and columns 0 to 72, giving (100 - 10 + 1) x (80 - 8 + 1) = 91 x 73 positions.
  2. 2. Why did SSD pick the wrong location in the underexposed scene while NCC stayed correct?

    When the object is dimmed, its numbers no longer equal the template's numbers, so a flat patch can have a lower squared error. NCC subtracts means and divides by the contrast, so scaling by a positive factor leaves the score at the top.
  3. 3. What does an NCC score of exactly -1 tell you?

    NCC is a correlation coefficient. 1 means a positive linear relationship, -1 a perfectly inverted pattern, and 0 no linear relationship. Absence of similarity usually shows up near 0, not -1.
  4. 4. How do you compute the cross-correlation of a scene with a template using fftconvolve?

    Convolution flips its kernel, while correlation does not. Flipping the template in both axes cancels the flip, so the result equals the sliding-window correlation.
  5. 5. Which situation is a poor fit for plain template matching?

    Pixel-wise matching breaks when pose, scale or viewpoint change a lot. Fixed icons, fixed jigs and small frame-to-frame shifts are its sweet spot.

Summary

  • Template matching slides a small template over the scene, scores each position, and takes the best location; the score map has size (H-h+1) x (W-w+1).
  • SSD is simple but depends on absolute brightness. Zero-mean normalized cross-correlation (NCC) ignores brightness and contrast and lies between -1 and 1.
  • Guard against division by zero on flat windows.
  • Correlation can be computed with the FFT (fftconvolve with a flipped template), and window sums for normalization come from correlating with an array of ones. Small templates are fine with direct loops.
  • Rotation, scale, perspective and occlusion lower the score quickly; handle them with multi-scale search, edge-based matching, feature descriptors or learned detectors.

Next, move from raw pixels to features that machine learning models can use: Hand-Crafted Features and HOG.