Normalized Cross-Correlation

mediumFREEObject TrackingTrackingCV: Motion Estimation

You are given a template and an image patch and need to compute their normalized cross-correlation (NCC).

NCC measures similarity between a template and a patch, normalized for brightness and contrast:

$NCC = \frac{\sum_i (T_i - \bar{T})(P_i - \bar{P})}{\sqrt{\sum_i (T_i - \bar{T})^2 \cdot \sum_i (P_i - \bar{P})^2}}$

Where:

$T_i$ are template pixel values, $\bar{T}$ is template mean
$P_i$ are patch pixel values, $\bar{P}$ is patch mean

NCC ranges from -1 (inverse correlation) to +1 (perfect match).

Example

Input

template = [[1, 2], [3, 4]]
patch = [[1, 2], [3, 4]]

Output

1.0

Reasoning

Inputs: template and patch are both $2 \times 2$ grids of pixel intensities, here identical: $1, 2, 3, 4$ . Only corresponding positions are compared, so treat each grid as four paired values $(T_i, P_i)$ .
Means: $\bar{T} = \bar{P} = \frac{1+2+3+4}{4} = 2.5$ . Subtracting them removes overall brightness, leaving deviations $-1.5, -0.5, 0.5, 1.5$ for both grids.
Numerator: the deviations multiply pairwise to $2.25, 0.25, 0.25, 2.25$ , which add up to $5$ .
Denominator: each grid's squared deviations also sum to $5$ , so the scale is $\sqrt{5 \cdot 5} = 5$ .
Output: $\frac{5}{5}$ gives 1.0, a perfect match.
Notice: NCC ignores brightness and contrast. A patch of $12, 14, 16, 18$ (that is, $2T + 10$ ) still scores $1.0$ . Reversing the order to $4, 3, 2, 1$ flips every product's sign and scores $-1.0$ . A flat grid has zero spread, so the score falls back to $0.0$ by definition.

Constraints

template and patch are 2D arrays of same size
Return NCC score rounded to 4 decimal places
If either has zero variance, return 0.0

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

Concept primer

You want to build intuition for how to compute NCC between a template and a patch, not just plug in the formula. Below is the minimal theory + implementation strategy you need.

1. Background Knowledge

Normalized cross-correlation (NCC) is a similarity measure between two signals or images that is invariant to linear changes in brightness and contrast.

Plain cross-correlation computes $\sum_i T_i P_i$ which is large when bright pixels in the template align with bright pixels in the patch.
But if the patch is uniformly brighter (e.g., all intensities +50), plain correlation changes, even though the pattern is the same.

NCC fixes this by zero-centering and scaling both vectors before comparing:

Subtract the mean: $T_i - \bar{T}$ , $P_i - \bar{P}$ → remove overall brightness.
Divide by their standard deviations → remove overall contrast/scale.
The numerator becomes a dot product of two zero-mean vectors, and the denominator is the product of their norms, turning it into a cosine similarity:

NCC = \cos \theta = \frac{\langle T - \bar{T},\, P - \bar{P} \rangle}{\|T - \bar{T}\| \; \|P - \bar{P}\|}

So NCC is just the cosine of the angle between two normalized intensity vectors, bounded in $[-1, 1]$ .

2. Algorithm / Approach

At a high level, to compute NCC for a given template and patch:

Treat the template and patch as two arrays of the same size.
Compute their means.
Compute their zero-mean versions: subtract the mean from each pixel.
Compute:

Numerator: sum of elementwise products of zero-mean values.
Denominator: product of the square roots of the sums of squared zero-mean values.

Divide numerator by denominator, handling the special case where the denominator is zero.

In more “pattern” terms, this is a vector normalization + dot product pattern:

Normalize each array to zero mean and unit norm.
NCC is simply their dot product.

3. Step-by-Step Strategy

Assume you get template and patch as 2D NumPy-like arrays of the same shape.

Flatten (optional, conceptually helpful)

You can treat them as 1D vectors:

T = template.flatten()
P = patch.flatten()

Compute means

T_mean = mean(T)
P_mean = mean(P)

Zero-mean the data

T_zm = T - T_mean
P_zm = P - P_mean

Compute numerator (cross term)

numerator = sum(T_zm * P_zm)

Compute denominator (norms)

T_norm_sq = sum(T_zm * T_zm)
P_norm_sq = sum(P_zm * P_zm)
denominator = sqrt(T_norm_sq * P_norm_sq)

Handle degenerate cases

If denominator == 0, it means at least one of the vectors is constant (all pixels same after mean subtraction ⇒ all zero). NCC is undefined; you can:
Return 0.0 (often used in practice), or
Define it per problem statement.

Compute NCC

if denominator == 0:
ncc = 0.0 # or per spec
else:
ncc = numerator / denominator

The final scalar ncc is your answer.

4. Common Pitfalls

Mismatched shapes: NCC only makes sense if template and patch are the same size. Make sure shapes match before computing.
Integer overflow / integer division:
Do all calculations in floating point (e.g., float32 or float64), not uint8.
In languages like Python/C++ beware of integer division and overflow in sums of squares.
Denominator zero:
Happens when the template or patch has zero variance (all pixels equal).
You must explicitly check and handle this; otherwise you’ll get NaNs or crashes.
Incorrect normalization:
Do not forget to subtract the mean from each image before computing sums of squares and product.
Do not divide by the sum of squares itself—must use the square root of sums of squares.
Mixing up indices:
Ensure you’re summing over all pixels consistently and not, e.g., accidentally normalizing across rows only.

5. Time & Space Complexity

Let $N$ be the number of pixels in the template/patch (e.g., $N = H \times W$ ):

Time complexity:
Each step (mean, zero-centering, sums, numerator) is a single pass over $N$ elements.
Overall: $O(N)$ .
Space complexity:
If you store zero-mean versions as new arrays, extra space is $O(N)$ .
You can do it in-place (overwrite) to keep extra space to $O(1)$ , beyond the input arrays.

This is all you need to reason about and implement NCC correctly for a single template–patch pair.

solution.py

Python 3.13

Test results