Task 3 of 5

Normalize It

The fix is to stop comparing brightness and start comparing shape. Subtract each window's own mean, subtract the template's mean, and divide by how much each of them varies. What survives is normalized cross-correlation:

cov  = sum( (wᵢ − w̄) · (tᵢ − t̄) )
varW = sum( (wᵢ − w̄)² )
varT = sum( (tᵢ − t̄)² )

NCC  = cov / sqrt(varW · varT)

Subtracting the means removes anything added to the light; dividing by the spreads removes anything the light was multiplied by. The result is bounded: +1 is a perfect match, 0 is no relationship at all, and −1 is a perfect anti-match — the same shape with its lights and darks swapped. That bound is a gift, because a score that leaves −1…1 is proof the arithmetic is wrong.

Written that way it looks like three passes over the window: one to find the means, one for the spreads, one for the product. It is not. Every one of those three quantities is a sum over the same 64 pixels the thread is already reading, and two schoolbook identities turn all three into plain running totals:

cov  = sumWT − sumW · sumT / n
varW = sumW2 − sumW · sumW / n
varT = sumT2 − sumT · sumT / n

So the thread keeps five accumulators — sumW, sumW2, sumT, sumT2, sumWT — fills them in one pass, and assembles the score after the loop. Five running totals, one divide, no mean subtracted from anything explicitly. (A window with no variation at all would put a zero in that denominator; production code adds a tiny epsilon for it. Nothing in this scene is flat, so the plain formula is safe here.)

same scene, same patch, two scores — only one of them is looking at the shape

Goal: build the 89×89 NCC map over brightScene and log the winning position and its score. The match snaps back to where the patch really is.

Requirements

Accumulate sumW, sumW2, sumT, sumT2 and sumWT in one pass over the window
Assemble cov, varW and varT with the identities above
Return cov / Math.sqrt(varW * varT) — a square root of the product, not the product
NCC is a similarity, so bestMatch() has to keep the largest score

Hint 1 — five accumulators, one loop

Declare all five before the loops and add to each one inside:

const w = scene[y + j][x + i];
const t = patch[j][i];
sumW += w;
sumW2 += w * w;
sumT += t;
sumT2 += t * t;
sumWT += w * t;

Hint 2 — assembling the score

const n = this.constants.count;
const cov = sumWT - (sumW * sumT) / n;
const varW = sumW2 - (sumW * sumW) / n;
const varT = sumT2 - (sumT * sumT) / n;
return cov / Math.sqrt(varW * varT);

— note that varW and varT here are the sums of squared deviations, not the sums divided by n. Dividing both by n would cancel out of the ratio anyway, so there is no point paying for it.

Hint 3 — the other half of the change

Task 1's bestMatch kept the smallest score, because SSD was a distance. NCC is a similarity: if (map[y][x] > best), starting from -Infinity. Leave it as a minimum and this map will hand you its most spectacularly wrong position instead of its right one.

Same idea elsewhere

Normalising before you compare is one of the most portable ideas in computing. It is TM_CCOEFF_NORMED in OpenCV and nppiCrossCorrValid_NormLevel in CUDA's NPP; it is cosine similarity over centred vectors in every retrieval system; it is the Pearson correlation in statistics; and it is exactly what a batch-norm or layer-norm layer does inside a neural network, for exactly the same reason — so that what comes next responds to structure instead of to scale.

All tasks in Template Matching

This page is an interactive exercise — the editor, the GPU runner and your saved progress need JavaScript. The text above is the full brief.