# Normalize It

*Task 3 of 5 · [Template Matching](https://gpu.rocks/learn/template-matching-f57b4bed.md) · GPU.js Learn*

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**:

```js
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:

```js
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.)

## Figures

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

## Goal

**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:

```js
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

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

## Starter code

```js
// Same 7,921 threads. A score that brightness cannot move.
const gpu = new GPU({ mode });

const ncc = gpu.createKernel(function (scene, patch) {
  const x = this.thread.x;
  const y = this.thread.y;
  let sumW = 0;
  let sumW2 = 0;
  let sumT = 0;
  let sumT2 = 0;
  let sumWT = 0;
  // TODO: one pass over the 8×8 window, filling all five accumulators.

  // TODO: assemble cov, varW and varT with the two identities, then
  // return cov / Math.sqrt(varW * varT).
  return 0;
}, {
  output: [89, 89],
  constants: { size: 8, count: 64 },
});

function bestMatch(map) {
  let best = map[0][0];
  let bx = 0;
  let by = 0;
  for (let y = 0; y < map.length; y++) {
    for (let x = 0; x < map[y].length; x++) {
      // TODO: NCC is a similarity — keep the LARGER score, not the smaller.
      if (map[y][x] < best) {
        best = map[y][x];
        bx = x;
        by = y;
      }
    }
  }
  return { x: bx, y: by, score: best };
}

const map = await ncc(brightScene, patch);
const hit = bestMatch(map);
console.log('best match at x =', hit.x, ' y =', hit.y, ' score =', hit.score);
```

---

Interactive version: https://gpu.rocks/learn/template-matching-f57b4bed/3

[Previous task](https://gpu.rocks/learn/template-matching-f57b4bed/2.md) · [Next task](https://gpu.rocks/learn/template-matching-f57b4bed/4.md)