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.
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
Explanation
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.
Explore the dry run
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 |
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.