Task 1 of 5

Score Every Position at Once

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.

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

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

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

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

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.

All tasks in Template Matching

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