# Payoff: Present or Absent?

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

Everything so far, pointed at a real question. `brightScene` hides an
8×8 patch; `patch` is that patch. `rotatedPatch` is the same eight
by eight values turned a quarter turn — identical mean, identical spread, identical
histogram, and **nowhere in the scene**. Find the one; refuse the other.

The kernel is finished (it is task 4's, unchanged). What is left is the part that
catches people twice: reading an answer off a score map.

**Take the maximum.** NCC is a similarity, so its best is its largest.
SSD was a distance, so its best was its smallest. The convention is inverted between the
two measures, and reaching for the wrong one does not give you a slightly worse answer —
it gives you the map's most emphatically *wrong* position.

**The coordinates are the window's top-left corner.** Cell (x, y) scored
the window that starts at (x, y) and runs 8 pixels right and down. That corner is the
answer. The centre is `(x + 4, y + 4)` if that is what you want — just be sure
you know which one you are reporting, because the score map is 89 wide where the scene is
96, and quietly mixing the two coordinate systems is how a detector ends up drawing boxes
in the wrong place.

And then the honest part. A search over 7,921 positions *always* returns a
winner — the best score is a best score whether or not anything is there. What turns
matching into **detection** is a **threshold**: a line below
which "the best I found" means "nothing". Here the patch that is present scores 1.000 and
the one that is absent tops out near 0.47, so 0.9 separates them with room to spare. That
number is not universal — it depends on the noise, on the template, and on how much
deformation you are willing to forgive — and calibrating it against data whose answers you
already know is most of the work in building a real detector.

## Goal

**Goal:** report where `patch` is, report that
`rotatedPatch` is not there, and let `THRESHOLD` be what decides.

## Requirements

- Score both templates against `brightScene` with the same kernel
- Finish `bestMatch`: scan for the **largest** score and return the window's top-left corner
- `console.log` the position found for `patch`, and the best score each template managed
- For each template, `console.log` whether its best score clears `THRESHOLD` — one `true`, one `false`

## Hint 1 — the scan

Start from `-Infinity` and keep the larger:

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

`bx` and `by` are already the corner — no offset to add.

## Hint 2 — the verdict

`prepare()` hands the kernel what task 4 built, so each report is
three lines:

```js
const map = await ncc(brightScene, t.centered, t.norm);
const hit = bestMatch(map);
console.log(label, hit.x, hit.y, hit.score,
  hit.score >= THRESHOLD);
```

## Same idea elsewhere

Thresholding a similarity map is the last mile of nearly every classical
detector — Viola-Jones cascades, ORB and SIFT keypoint matching with Lowe's ratio test,
stereo correspondence rejecting low-confidence disparities — and it survives into modern
ones as the confidence score on every bounding box a neural network emits. The score tells
you which position is most like the template; only a threshold tells you whether the
template is there at all.

## Starter code

```js
// The finished matcher. Two templates: one is in the scene, one is not.
const gpu = new GPU({ mode });

const THRESHOLD = 0.9;

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;
  for (let j = 0; j < this.constants.size; j++) {
    for (let i = 0; i < this.constants.size; i++) {
      const w = scene[y + j][x + i];
      sumW += w;
      sumW2 += w * w;
      sumWC += w * 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 },
});

// Task 4, packaged: any template in, the two numbers the kernel wants out.
function prepare(template) {
  let sum = 0;
  for (let j = 0; j < 8; j++) {
    for (let i = 0; i < 8; i++) sum += template[j][i];
  }
  const mean = sum / 64;
  const centered = [];
  let normSq = 0;
  for (let j = 0; j < 8; j++) {
    const row = [];
    for (let i = 0; i < 8; i++) {
      const c = template[j][i] - mean;
      row.push(c);
      normSq += c * c;
    }
    centered.push(row);
  }
  return { centered: centered, norm: Math.sqrt(normSq) };
}

function bestMatch(map) {
  // TODO: scan the whole map for its LARGEST score, and return the (x, y)
  // it came from — that (x, y) is the window's top-left corner.
  return { x: 0, y: 0, score: map[0][0] };
}

async function report(label, template) {
  const t = prepare(template);
  const hit = bestMatch(await ncc(brightScene, t.centered, t.norm));
  // TODO: log the label, the position, the score, and whether the score
  // clears THRESHOLD.
}

await report('patch:        ', patch);
await report('rotatedPatch: ', rotatedPatch);
```

---

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

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