📘

Template Matching Best Location

Implement a template matching algorithm to find the best location of a given template within a search image using Normalized Cross-Correlation (NCC). This involves sliding the template across the search region and computing similarity at each position.

The concept of template matching is crucial in object tracking, as it enables the location of an object to be determined between frames. The NCC measure is used to quantify the similarity between the template and the search image at each position, providing a score that indicates the degree of match.

Here are the steps to follow:

Slide the template across the search image, considering each possible position.
At each position, extract the corresponding patch from the search image.
Compute the NCC between the template and the extracted patch.

NCC = \frac{\sum_{i=1}^{n}(t_i - \bar{t})(p_i - \bar{p})}{\sqrt{\sum_{i=1}^{n}(t_i - \bar{t})^2 \sum_{i=1}^{n}(p_i - \bar{p})^2}}

This technique is widely used in video surveillance systems to track objects across frames.

Example:

Input:

image = [[0,0,0,0],
        [0,1,2,0],
        [0,3,4,0],
        [0,0,0,0]]
template = [[1,2],[3,4]]

Output:

(1, 1)

Reasoning:

Sliding template across valid positions:

Position (0,0): patch=[[0,0],[0,1]] → NCC with [[1,2],[3,4]] = low
Position (0,1): patch=[[0,0],[1,2]] → partial match
Position (0,2): patch=[[0,0],[2,0]] → low
Position (1,0): patch=[[0,1],[0,3]] → partial match
Position (1,1): patch=[[1,2],[3,4]] → EXACT MATCH, NCC = 1.0
Position (1,2): patch=[[2,0],[4,0]] → partial match
Position (2,0): patch=[[0,3],[0,0]] → low
Position (2,1): patch=[[3,4],[0,0]] → partial match
Position (2,2): patch=[[4,0],[0,0]] → low

Best match at (1,1) with NCC = 1.0

Constraints:

image: 2D search region (larger than template)
template: 2D template to find
Return best (row, col) location (top-left corner of match)
If multiple positions tie, return the first one found

More from CV: Motion Estimation

Hungarian Algorithm for MOTHard Rolling Shutter CorrectionHard Horn-Schunck Global Optical FlowMedium Intersection over Union (IoU) for TrackingMedium Bilinear Flow WarpingHard

You want to slide a template over a search image and use Normalized Cross-Correlation (NCC) to find the location with the highest similarity score. That location is your “best match” and is used for tracking where the object moved between frames.

1. Background Knowledge (Key Concepts)

Template matching

You have:
A search image (e.g., current video frame).
A template patch (e.g., object appearance from previous frame).
You slide the template over all valid positions in the search image and compute a similarity score at each position.
The position with the maximum similarity is taken as the object’s new location.

Cross-correlation vs normalized cross-correlation

Plain cross-correlation computes how similar two patches are by summing pixel-wise products: $\text{corr} = \sum_{x,y} I(x,y)\,T(x,y)$
This is sensitive to overall brightness and contrast.
Normalized cross-correlation (NCC) fixes this by subtracting means and dividing by standard deviations: $\text{NCC} = \frac{\sum (I - \mu_I)(T - \mu_T)}{\sqrt{\sum (I - \mu_I)^2}\,\sqrt{\sum (T - \mu_T)^2}}$
NCC values are typically in $[-1, 1]$ :
1: perfect match (up to linear intensity scaling).
0: no linear correlation.
-1: perfect negative correlation.

Why NCC in tracking

In tracking, lighting and contrast can change between frames.
NCC is robust to global changes in brightness/contrast (as long as the structure of the template remains similar), making it a standard choice for template-based tracking.

2. Algorithm / General Approach

High-level algorithm pattern:

For every valid (row, col) position where the template fits inside the search image:
Extract the corresponding image patch of the same size as the template.
Compute the NCC score between the template and this patch.
Track the maximum NCC value and its location.
Return the location with the highest NCC as the best match.

This is an exhaustive sliding-window search with NCC as the similarity measure.

3. Step-by-Step Strategy to Implement

Assume grayscale 2D arrays img and tpl:

Get dimensions

H, W = img.shape
h, w = tpl.shape

Precompute template statistics

Mean and standard deviation:

mu_T = tpl.mean()
sigma_T = tpl.std()

Optionally precompute tpl_centered = tpl - mu_T.

Loop over all valid positions

Valid top-left corners:
row from 0 to H - h
col from 0 to W - w
For each (row, col):

Extract patch:

patch = img[row:row+h, col:col+w]

Compute patch mean and std:

mu_I = patch.mean()
sigma_I = patch.std()

Compute numerator (covariance-like term):

num = ((patch - mu_I) * (tpl - mu_T)).sum()

Compute denominator:

denom = (sigma_I * sigma_T * h * w) # depending on exact formula, factor h*w may be inside num/denom

If denom is zero (flat region), define NCC as 0 (or skip).
Compute NCC:

ncc = num / denom

If ncc is greater than current best, update:

if ncc > best_ncc:
best_ncc = ncc
best_pos = (row, col)

👑

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

🔒

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.