Template matching with sum of squared differences
Find where a small pattern occurs in an image by sliding it over every position and scoring the match.
On this page
Nested loops and dictionaries.
- Find where a small pattern occurs in an image by sliding it over every position and scoring the match.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
Template matching looks for a known small image, the template, inside a larger image. It slides the template over every position where it fits and computes a score that says how well the pixels agree. The position with the best score is the match.
The simplest score is the sum of squared differences (SSD): the sum, over all template pixels, of (image − template)². A perfect match scores 0 and larger values mean worse matches, so the best position has the minimum SSD. Other scores include the sum of absolute differences and normalized cross-correlation. The normalized form subtracts the mean and divides by the standard deviation of each patch, so it still works when the overall brightness or contrast of the scene differs from the template.
In the example, a 3 × 2 template cut from the image is found at row 2, column 3 with a score of 0. The template could fit in 4 × 5 = 20 positions, and every other position has a larger score. Template matching is easy to understand and exact on clean images, but it fails when the object changes size, rotation, or appearance. For those cases, systems use feature descriptors such as SIFT or ORB, or learned detectors based on convolutional neural networks.
Code example
image = [
[10, 10, 10, 10, 10, 10],
[10, 10, 10, 10, 10, 10],
[10, 10, 10, 80, 90, 10],
[10, 10, 10, 70, 200, 10],
[10, 10, 10, 60, 50, 10],
[10, 10, 10, 10, 10, 10],
]
template = [[80, 90], [70, 200], [60, 50]]
def ssd_map(image, template):
th, tw = len(template), len(template[0])
scores = {}
for r in range(len(image) - th + 1):
for c in range(len(image[0]) - tw + 1):
scores[(r, c)] = sum((image[r + i][c + j] - template[i][j]) ** 2 for i in range(th) for j in range(tw))
return scores
scores = ssd_map(image, template)
best = min(scores, key=scores.get)
print(best, scores[best])
print(sorted(scores.values())[1] > 0)
print(len(scores))(2, 3) 0 True 20
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
image = [ [10, 10, 10, 10, 10, 10], [10, 10, 10, 10, 10, 10], [10, 10, 10, 80, 90, 10], [10, 10, 10, 70, 200, 10], [10, 10, 10, 60, 50, 10], [10, 10, 10, 10, 10, 10],]template = [[80, 90], [70, 200], [60, 50]] def ssd_map(image, template): th, tw = len(template), len(template[0]) scores = {} for r in range(len(image) - th + 1): for c in range(len(image[0]) - tw + 1): scores[(r, c)] = sum((image[r + i][c + j] - template[i][j]) ** 2 for i in range(th) for j in range(tw)) return scores scores = ssd_map(image, template)best = min(scores, key=scores.get)print(best, scores[best])print(sorted(scores.values())[1] > 0)print(len(scores))Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| The template can only be placed where it fits entirely inside the image: 4 vertical positions. | — | — | |
| At each position, add up the squared pixel differences between the template and the image patch. | — | — | |
| Lower SSD is better, so the best match is the position with the minimum score. | — | — | |
| The template appears at row 2, column 3, with a perfect score of 0. | — | (2, 3) 0 | |
| There are 4 × 5 = 20 candidate positions in total. | — | (2, 3) 0 True 20 |
Behind the scenes
How Python processes this code
Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.
Cost and common mistakes
O((H − th + 1)·(W − tw + 1)·th·tw) time: here 20 positions of 6 pixels each.
- SSD is sensitive to brightness changes. Use normalized cross-correlation when lighting varies.
- Template matching does not handle scale or rotation changes. Match several resized versions, or use feature-based methods.
- Scoring every position costs O(H·W·th·tw). Large images need FFT-based correlation or image pyramids to be fast.
Try it yourself
What would the best score be if the template's last pixel were 55 instead of 50 in the image?
Reveal answer and reasoning
The best position stays (2, 3) but its score becomes (50 − 55)² = 25 instead of 0, because exactly one pixel now differs by 5.