# Hoist What Never Changes

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

Look again at what those 7,921 threads just did. Two of the five running totals —
`sumT` and `sumT2` — depend only on the template. Every thread
walked the same 64 template values, arrived at the same two numbers, used them once and
threw them away. That is 7,920 calculations too many.

So do it once, in JavaScript, before the kernel runs — and do it in the shape the
kernel actually wants: the template with its mean already subtracted, plus the length of
that centred template.

```js
patchMean = (sum of patch) / 64
patchCentered[j][i]
          = patch[j][i] − patchMean
patchNorm = sqrt(sum of patchCentered²)
```

That simplifies the numerator too. Once the centred values sum to zero,
`sum((wᵢ − w̄) · cᵢ)` equals `sum(wᵢ · cᵢ)` — the window's own mean
cancels itself out and never has to be subtracted from anything. The thread drops from
five accumulators to three and from two square roots to one:

```js
varW = sumW2 − sumW · sumW / n
NCC  = sumWC / ( sqrt(varW) · patchNorm )
```

Press **Benchmark** before and after and watch the difference. Hoisting
loop-invariant work out of a loop is the oldest optimisation there is; what makes it worth
a task is that a GPU multiplies the saving by the thread count, so the same three lines
buy far more here than they would in a `for` loop.

There is a bigger version of this idea that this module deliberately does *not*
build. `sumW` and `sumW2` can also be precomputed — for the entire
scene, once — as **integral images** (summed-area tables): a table where each
cell holds the sum of everything above and to the left of it, so any rectangle's total
costs four lookups and three subtractions no matter how large the rectangle is. That is
genuinely how large-template matching is done at scale. It is also a two-dimensional
prefix sum, which is a module of its own — Prefix Sums (Scan) builds the one-dimensional
version — and at 8×8 those four lookups would replace 64 reads this thread is making
anyway. The win arrives when the template is 64×64, and so does the module.

## Goal

**Goal:** compute the template's statistics once in JavaScript, pass
them in, and get the same NCC map from a kernel that does strictly less work per thread.

## Requirements

- Compute `patchMean`, `patchCentered` and `patchNorm` in plain JavaScript, outside the kernel
- The kernel takes exactly three arguments — `(scene, centered, norm)`
- Keep three accumulators: `sumW`, `sumW2` and `sumWC`
- Same answer as before — log the winning position and its score

## Hint 1 — centring the template

Two passes over 64 values, in ordinary JavaScript:

```js
let sum = 0;
for (let j = 0; j < 8; j++) {
  for (let i = 0; i < 8; i++) sum += patch[j][i];
}
const patchMean = sum / 64;
```

then build `patchCentered` as `patch[j][i] - patchMean`, accumulating
the squares into `patchNorm` as you go — and take the square root at the
end.

## Hint 2 — the shorter loop body

```js
const w = scene[y + j][x + i];
sumW += w;
sumW2 += w * w;
sumWC += w * centered[j][i];
```

— no `sumT`, no `sumT2`, and nothing to subtract from
`sumWC`.

## Hint 3 — the return

```js
const varW = sumW2 - (sumW * sumW) / this.constants.count;
return sumWC / (Math.sqrt(varW) * norm);
```

— `norm` is a plain number argument; gpu.js is perfectly happy passing
scalars alongside arrays.

## Same idea elsewhere

Every mature matcher does this. OpenCV precomputes the template's sum and
sum-of-squares once inside `matchTemplate`; cuDNN and MIOpen hoist per-filter
constants out of every convolution launch; CUDA programmers park exactly this kind of
small, read-only, uniformly-accessed data in `__constant__` memory, and WGSL
puts it in a uniform buffer. The rule is the same everywhere: anything that does not vary
with the thread index does not belong inside the thread.

## Starter code

```js
// The template's statistics are the same at all 7,921 positions.
// Compute them once, here, and hand the kernel the finished numbers.
const gpu = new GPU({ mode });

// TODO: the template's mean; the template with that mean subtracted;
// and the length of the centred template.
const patchMean = 0;
const patchCentered = patch;
const patchNorm = 1;

const ncc = gpu.createKernel(function (scene, centered, norm) {
  const x = this.thread.x;
  const y = this.thread.y;
  let sumW = 0;
  let sumW2 = 0;
  let sumWC = 0;
  // TODO: one pass over the window — the window's sum, its sum of squares,
  // and its dot product with centered[j][i].

  const varW = sumW2 - (sumW * sumW) / this.constants.count;
  return sumWC / (Math.sqrt(varW) * norm);
}, {
  output: [89, 89],
  constants: { size: 8, count: 64 },
});

function bestMatch(map) {
  let best = -Infinity;
  let bx = 0;
  let by = 0;
  for (let y = 0; y < map.length; y++) {
    for (let x = 0; x < map[y].length; x++) {
      if (map[y][x] > best) {
        best = map[y][x];
        bx = x;
        by = y;
      }
    }
  }
  return { x: bx, y: by, score: best };
}

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

---

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

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