# Score Every Position at Once

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

Template matching asks the simplest question in object finding: **where in
this picture is that patch?** Slide the patch over every position it could occupy,
score how well it fits at each one, and keep the best. That sounds like a loop, and on a
GPU it is the exact opposite of a loop — every candidate position is scored from data
alone, with no reference to any other position. One thread per position, all 7,921 of
them at once.

The obvious score is the **sum of squared differences**. Line the 8×8
template up with its top-left corner at (x, y), subtract it from the scene pixel by pixel,
square each difference so a positive cannot cancel a negative, and add them up. Zero is a
perfect match; bigger is worse.

```js
d   = scene[y + j][x + i] − patch[j][i]
SSD = sum of d² over the 8×8 window
```

One thing to settle before you write a line: **the score map is smaller than the
scene**. A window whose corner sits at column 89 would need columns 89…96, and this
scene stops at 95. The last legal corner is 88, so there are 96 − 8 + 1 = **89**
positions along each axis, and the map is 89×89. `scene` here is a luminance
map — one number per pixel, the kind a grayscale pass hands you — but it is indexed like
any other image.

**Array layout in gpu.js**
Image data comes in row-major: `image[y][x]` is the pixel in row *y*,
column *x*, and each pixel is an `[r, g, b, a]` array with channels from
0 to 1. Mind the inversion that catches everyone — sizes are given width-first
(`output: [width, height]`), but indexing runs row-first, so this thread's own
pixel is `image[this.thread.y][this.thread.x]`. Swap those two and you read the
transpose of your image. Three-dimensional data follows the same rule:
`output: [w, h, d]` is indexed `[z][y][x]`.

## Figures

- **one thread per position — and a map that comes out smaller than the scene**

## Goal

**Goal:** build the 89×89 SSD score map for `patch` over
`scene`, and log the position of the best match.

## Requirements

- Set `output` to the number of candidate positions — `96 − 8 + 1` per axis, not 96
- Sum over the whole template with a double loop bounded by `this.constants.size`
- Square every difference: `const d = …; sum += d * d;`
- `console.log` the position `bestMatch()` returns

## Hint 1 — which window is mine?

Thread (x, y) owns the window whose *top-left corner* is at
`scene[y][x]`. Its pixels are `scene[y + j][x + i]` for
`j` and `i` from 0 to 7 — and those same `j`,
`i` index the template as `patch[j][i]`. No clamping is needed
anywhere: the output shape already guarantees every read is in bounds.

## Hint 2 — the loop body

```js
const d = scene[y + j][x + i] - patch[j][i];
sum += d * d;
```

— two statements, inside two nested `for` loops that both run to
`this.constants.size`.

## Hint 3 — the whole kernel

```js
const x = this.thread.x;
const y = this.thread.y;
let sum = 0;
for (let j = 0; j < this.constants.size; j++) {
  for (let i = 0; i < this.constants.size; i++) {
    const d = scene[y + j][x + i] - patch[j][i];
    sum += d * d;
  }
}
return sum;
```

— and `output: [89, 89]`.

## Same idea elsewhere

This is OpenCV's `matchTemplate` and NVIDIA NPP's
`nppiSQRDistanceNorm`, and it is one of the friendliest workloads a GPU ever
sees: no communication between threads, no atomics, perfectly regular reads, and
neighbouring threads reading overlapping windows straight out of cache. A WGSL compute
shader or a CUDA 2D block does it with the same two nested loops.

## Starter code

```js
// One thread per candidate position. 89 × 89 = 7,921 of them.
const gpu = new GPU({ mode });

const ssd = gpu.createKernel(function (scene, patch) {
  const x = this.thread.x;
  const y = this.thread.y;
  // TODO: sum (scene[y + j][x + i] - patch[j][i])² over the whole
  // this.constants.size × this.constants.size template.
  return 0;
}, {
  // TODO: 88 is wrong. How many top-left corners actually fit?
  output: [88, 88],
  constants: { size: 8 },
});

// Scanning 7,921 scores in JavaScript is not the lesson here — Reductions and
// Top-K Selection do exactly this on the GPU, in parallel, and properly.
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 map = await ssd(scene, 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/1

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