Template Matching Score

mediumFREEBrief HistoryPattern RecognitionCV: Introduction to Computer Vision

Implement a template matching technique to compute the similarity between a given template and an image patch. This task involves calculating a score that measures the degree of similarity between the two.

Template matching is a fundamental concept in computer vision that involves locating a smaller image, called the template, within a larger image. The Sum of Squared Differences (SSD) is a widely used metric for this purpose, which calculates the sum of the squared differences between corresponding pixel values in the template and the image patch. This metric is based on the idea that a lower SSD value indicates a better match between the template and the image patch.

To compute the SSD, follow these steps:

Iterate over each pixel in the template and the corresponding pixel in the image patch.
Calculate the difference between the pixel values.
Square the difference.
Sum up the squared differences.

SSD = \sum_{i,j}(I_{i,j} - T_{i,j})^2

This technique is widely used in object recognition systems.

Example

Input

ssd_score([[1,2],[3,4]], [[1,2],[3,4]])

Output

Reasoning

Inputs: template and patch are both $2 \times 2$ grids of pixel intensities, and here they hold the same values: $T = I = \begin{bmatrix}1 & 2\\3 & 4\end{bmatrix}$ .
Pixel-by-pixel differences: pair each template pixel with the patch pixel at the same position, row $i$ and column $j$ : $1-1,\ 2-2,\ 3-3,\ 4-4$ , so all four differences $I_{ij} - T_{ij}$ are $0$ .
Square and add: $SSD = 0^2 + 0^2 + 0^2 + 0^2 = 0$ , which matches the output 0. The result is a single whole number because the pixels are integers.
Why squaring matters: if the patch were one brighter everywhere ( $\begin{bmatrix}2 & 3\\4 & 5\end{bmatrix}$ ), every difference would be $+1$ (e.g. $2-1$ ) and the SSD would be $4 \times 1 = 4$ . One darker everywhere gives differences of $-1$ and also an SSD of $4$ , because squaring drops the sign so negative differences can't cancel positive ones.
Notice: SSD is never negative and reaches $0$ only when the two grids match exactly, which is why a lower score means a better match.

Constraints

Template and patch have the same dimensions
Return the SSD value

More from CV: Introduction to Computer Vision

Sparse Matrix Operations for Imagesmedium Multi-Scale Feature Pyramidhard Implement Prewitt Edge Detectorhard Connected Components Labelinghard K-Means Color Quantizationmedium

Concept primer

Template matching compares a small image patch (the template $T$ ) against regions of a larger image $I$ to find where they are most similar. One classic similarity (really, dissimilarity) measure is the Sum of Squared Differences (SSD): you subtract template pixel values from image patch pixel values, square them, and sum over all pixels. A lower SSD indicates that the patch is more similar to the template.

Conceptually, SSD is just the squared Euclidean distance between two equal-sized arrays of pixel intensities: if we vectorize both $I$ and $T$ , SSD is $\|$ \mathbf{I} $-$ \mathbf{T} $\|_2^2$ . Because squared differences penalize larger mismatches more heavily, SSD is sensitive to noise and lighting changes, but it is simple, fast, and historically important in early computer vision.

1. Background Knowledge

Aligned shapes and sizes SSD requires the template and the image patch to have the same width and height. The sum is taken over all corresponding pixel positions $(i,j)$ , so the patch you compare must be a crop from the image that matches the template size exactly.
Pixel-wise operations For each pixel location $(i,j)$ inside the template region:

SSD = \sum_{i,j} (I_{i,j} - T_{i,j})^2

This is a straightforward elementwise computation: subtract, square, then sum.

Interpretation of the SSD value
If $I_{i,j} = T_{i,j}$ for all pixels, then $SSD = 0$ (perfect match).
Larger SSD means more difference between patch and template. In full template matching over an image, you would compute this SSD at many positions and choose the minimum.

2. Algorithm / Approach Pattern

For a single template–patch SSD (as in this problem):

Ensure same dimensions for $I$ and $T$ (given by the problem).
Loop over all pixel indices $(i,j)$ .
Compute the difference $d = I_{i,j} - T_{i,j}$ .
Square it: $d^2$ .
Accumulate into a running sum.
Return the final sum as the SSD score.

In more general template matching, you would:

Slide the template over the image.
At each valid top-left position, compute SSD between $T$ and the corresponding image patch.
Record the SSD for each position and then pick the position with the smallest SSD.

3. Step-by-Step Strategy (Implementation Outline)

Assume you are given:

A 2D array image of size H x W (or just the patch).
A 2D array template of the same size as the patch (for this problem, usually the same size as image).

Steps:

Initialize accumulator

ssd = 0

Iterate over all pixels

Use two nested loops over rows and columns:

for i in range(height):
for j in range(width):
diff = image[i][j] - template[i][j]
ssd += diff * diff

Return/print the result

The final ssd variable is the Sum of Squared Differences.

If the problem uses 1D arrays (flattened input), the idea is identical:

ssd = 0
for k in range(n_pixels):
 diff = image_flat[k] - template_flat[k]
 ssd += diff * diff

4. Common Pitfalls

Mismatched dimensions Forgetting to ensure that you loop over the common height and width of both inputs (or relying on incorrect dimensions) can cause index errors or wrong answers.
Integer overflow (in some languages) If pixel values and the accumulator are int with limited range, diff * diff can overflow for big images or large differences. Use a larger integer type (e.g., 64-bit) or floating-point for ssd.
Forgetting to square Using abs(I - T) instead of (I - T)**2 computes Sum of Absolute Differences (SAD), not SSD.
Not resetting accumulator In broader template-matching tasks, you must reset ssd = 0 for each new patch; otherwise, you accumulate across patches.

5. Time & Space Complexity

For computing SSD between one template and one equally sized image patch:

Let the template (and patch) size be $h \times w$ , with $N = h \cdot w$ pixels.

Time Complexity

You perform a constant amount of work per pixel (subtract, square, add).
Total: $O(h \cdot w) = O(N)$ .

Space Complexity

You only need a few scalar variables (loop indices, diff, ssd) beyond the input arrays.
Total: $O(1)$ extra space, assuming inputs are given and not counted.

solution.py

Python 3.13

Test results