Task 4 of 5

Hoist What Never Changes

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.

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:

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

Hint 1 — centring the template

Two passes over 64 values, in ordinary JavaScript:

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

All tasks in Template Matching

  1. Score Every Position at Once
  2. The Score That Lies
  3. Normalize It
  4. Hoist What Never Changes
  5. Payoff: Present or Absent?

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