# Non-Maximum Suppression

*Task 3 of 6 · [The Canny Edge Pipeline](https://gpu.rocks/learn/canny-edges-6901c51a.md) · GPU.js Learn*

Stage 2 leaves edges several pixels thick: a gradient does not switch on at one
column, it ramps across the whole slope. Canny's third stage is what makes the output an
**edge map** rather than a heat map — and it is the stage everyone gets
wrong.

The rule: a pixel survives only if it is a local maximum **along its own gradient
direction**. Not along the edge — *across* it. The gradient points the way
the brightness climbs, which is perpendicular to the edge itself, and walking one step
each way along that direction is walking off the ridge on both sides. If the pixel is the
top of that little ridge, it stays; if either neighbour is above it, it is on the slope,
and it goes to zero.

Two steps, then. **Quantise** the angle to one of four axes — the only
neighbours you have are the eight around you, so the gradient's direction can only be
answered to 45° — and then **compare** against the two neighbours on that
axis. Quantising has one trap in it: `atan2` returns −π…π, but an axis has no
sense of forwards. −45° and +135° are the same axis, so an angle below zero has to be
wrapped up by 180° first. Skip the wrap and one of your four buckets is never selected at
all — on this task's own map, that is 570 of the 1,049 gradient pixels quietly landing in
the wrong bucket.

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

- **the two neighbours that matter are across the edge, not along it** — A patch of gradient magnitudes holding a three-pixel-wide ridge. The pixel under test is compared with the two neighbours lying along its gradient direction, which crosses the ridge; the edge itself runs at right angles to that. On the right, the three-wide band becomes a one-pixel line.

## Goal

**Goal:** keep `mag[y][x]` when it is at least as large as
both of its neighbours along the quantised gradient direction, and return `0`
otherwise.

## Requirements

- Wrap a negative angle by `+ Math.PI` before quantising — 180° and 0° are the same axis
- Quantise into four buckets at 22.5°, 67.5°, 112.5°: an `(ax, ay)` step of `(1,0)`, `(1,1)`, `(0,1)` or `(-1,1)`
- Compare against `mag[y + ay][x + ax]` and `mag[y - ay][x - ax]` — the GRADIENT axis, not the edge
- Survivors keep their magnitude; everything else is `0`, borders included

## Hint 1 — which neighbours belong to which bucket

Take the angle to degrees after wrapping, so it lies in 0…180, and read off
the axis:

```js
  0° ± 22.5   →  (ax, ay) = ( 1, 0)   left  ↔ right
 45° ± 22.5   →  (ax, ay) = ( 1, 1)   ↖ ↘
 90° ± 22.5   →  (ax, ay) = ( 0, 1)   up    ↕ down
135° ± 22.5   →  (ax, ay) = (-1, 1)   ↗ ↙
```

Start with `(1, 0)` and let the last bucket fall out of the
`else`: 0° and 180° share it.

## Hint 2 — the shape of the body

```js
let a = dir[y][x];
if (a < 0) a += Math.PI;
const deg = a * 180 / Math.PI;
let ax = 1;
let ay = 0;
if (deg >= 22.5 && deg < 67.5) { ax = 1; ay = 1; }
else if (deg >= 67.5 && deg < 112.5) { ax = 0; ay = 1; }
else if (deg >= 112.5 && deg < 157.5) { ax = -1; ay = 1; }
```

## Hint 3 — the comparison

```js
const m = mag[y][x];
if (m >= mag[y + ay][x + ax] && m >= mag[y - ay][x - ax]) {
  return m;
}
return 0;
```

`>=`, not `>`: on a perfectly symmetric edge the two
middle pixels tie, and `>` would erase both and leave a hole where the
edge was. The border check has already returned, so these indexes are in bounds.

## Same idea elsewhere

The name is borrowed all over vision: object detectors run "NMS" over overlapping
boxes with exactly this argument — keep the local maximum, drop everything it explains.
On the GPU the pattern is a pure gather, one thread per pixel with no coordination, which
is why NVIDIA's VPI, OpenCV's `cudaimgproc` and every WebGPU implementation
fuse it into a single compute pass. The awkward part on real hardware is the branch: four
buckets means four different neighbour pairs, and a warp whose threads disagree runs all
four paths — which is why some implementations interpolate along the true angle instead of
quantising, trading arithmetic for branch uniformity.

## Starter code

```js
// Stage 3 of Canny: thin the ridges down to one pixel.
const gpu = new GPU({ mode });

const suppress = gpu.createKernel(function (mag, dir) {
  const x = this.thread.x;
  const y = this.thread.y;
  if (x === 0 || y === 0 || x === this.constants.last || y === this.constants.last) {
    return 0;
  }
  // TODO 1: wrap dir[y][x] up by Math.PI when it is negative, and turn it
  //         into degrees so it lies in 0…180.
  // TODO 2: pick the (ax, ay) step for its bucket — (1,0), (1,1), (0,1), (-1,1).
  // TODO 3: keep mag[y][x] only if it is >= BOTH mag[y + ay][x + ax]
  //         and mag[y - ay][x - ax]. Otherwise return 0.
  return mag[y][x];
}, {
  output: [64, 64],
  constants: { last: 63 },
});

const thin = await suppress(mag, dir);

let before = 0;
let after = 0;
for (let y = 0; y < 64; y++) {
  for (let x = 0; x < 64; x++) {
    if (mag[y][x] > 0) before++;
    if (thin[y][x] > 0) after++;
  }
}
console.log('pixels with a gradient:', before, ' still standing after suppression:', after);
```

---

Interactive version: https://gpu.rocks/learn/canny-edges-6901c51a/3

[Previous task](https://gpu.rocks/learn/canny-edges-6901c51a/2.md) · [Next task](https://gpu.rocks/learn/canny-edges-6901c51a/4.md)