Normalized Cross-Correlation

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:

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

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

5. 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.

1. Flatten (optional, conceptually helpful)

• You can treat them as 1D vectors:

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

2. Compute means

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

3. Zero-mean the data

T_zm = T - T_mean
P_zm = P - P_mean

4. Compute numerator (cross term)

numerator = sum(T_zm * P_zm)

5. 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)

6. 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.

7. 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.