# Hysteresis: Run It Until Nothing Changes

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

Stage 4 left a pile of undecided pixels. Hysteresis decides them with one rule:
a weak pixel lives if it is **connected to a strong one** — touching it, or
touching something that is. That "or" is the whole problem. Connectivity is
*transitive*, and a GPU kernel can only see one step out.

So you run the kernel again. One pass promotes every weak pixel that touches a strong
one; the second pass promotes the ones that touch those; a chain of length *n*
takes *n* passes to light up end to end. On this task's map that is
**28 passes** — and you cannot know that in advance. The propagation is done
when a pass changes nothing, which you can only find out by reading the result back and
looking. Here that readback is free, because these kernels are not pipelined yet and every
pass comes home to JavaScript anyway. Task 6 is where that stops being true, and where the
honest cost of "iterate until stable" shows up.

Worth knowing: plenty of real-time implementations do not iterate at all. They run
**one** pass — a weak pixel survives if any of its eight neighbours is strong
— and ship it. It under-connects long faint chains, and for a 60 fps video filter that is
a bargain: a fixed, known cost per frame instead of a data-dependent loop nobody can
budget for.

## Figures

- **the front moves one pixel per pass, and nobody knows how many passes that is** — A strong pixel beside a chain of weak ones. Each pass promotes exactly one more weak cell, so the strong front advances one pixel at a time until the chain is complete. A separate group of weak pixels touching nothing strong is never promoted, and is dropped.

## Goal

**Goal:** write the propagation kernel, then run it in a loop until a
pass changes nothing, logging how many passes that took.

## Requirements

- A strong cell (`> 0.75`) stays `1`; a gone cell (`< 0.25`) stays `0`
- A weak cell becomes `1` if any of its **8** neighbours is strong, else stays `0.5`
- Loop until `unchanged(next, state)`, then log `console.log('settled after', passes, 'passes')`
- Count every call to `grow`, including the last one — the one that told you to stop

## Hint 1 — no early return inside the loop

Scan the 3×3 neighbourhood and set a flag rather than returning from inside
the loops — it compiles the same on every backend and reads better:

```js
let strongNear = 0;
for (let dy = -1; dy <= 1; dy++) {
  for (let dx = -1; dx <= 1; dx++) {
    // clamp sy, sx into 0…this.constants.last, then:
    if (state[sy][sx] > 0.75) {
      strongNear = 1;
    }
  }
}
```

The centre cell is included in that scan, and it is harmless: this branch only runs
when the centre is weak, so it can never mark itself.

## Hint 2 — the loop

```js
let state = classified;
let passes = 0;
for (let i = 0; i < 40; i++) {
  const next = await grow(state);
  passes++;
  state = next;
  if (unchanged(next, state)) break;
}
```

— except that assignment above happens too early to compare anything. Take
`next`, count it, compare it against the *previous*
`state`, and only then replace it.

## Hint 3 — why 40

The `for` is a safety rail, not the plan: the `break`
is what actually stops the loop, and 40 is simply more passes than a 64×64 map could
ever need. Leaving a bound on a loop you expect to break out of is cheap insurance
against a kernel that never settles.

## Same idea elsewhere

"Iterate a local rule until the global answer stops changing" is label propagation,
and it is how connected components are computed on GPUs everywhere — CUDA's
`cuGraph`, ROCm's rocPRIM-based labelers, every union-find-on-GPU paper. The
expensive part is always the same: the termination test. CUDA can keep a device-side
"changed" flag and read back four bytes per iteration; WebGPU can write it to a storage
buffer and feed it to an indirect dispatch. gpu.js has neither, so the choice is stark —
pay a full readback per pass to ask, or pick a fixed count and accept whatever it gets you.
Task 6 picks the second.

## Starter code

```js
// Stage 5 of Canny: a weak edge lives if it is connected to a strong one.
const gpu = new GPU({ mode });

// One propagation pass.
const grow = gpu.createKernel(function (state) {
  const x = this.thread.x;
  const y = this.thread.y;
  const v = state[y][x];
  if (v > 0.75) {
    return 1; // already strong
  }
  if (v < 0.25) {
    return 0; // already gone
  }
  // TODO: this cell is weak. Scan its 8 neighbours (clamp sy and sx into
  // 0…this.constants.last); return 1 if any of them is strong, else 0.5.
  return 0.5;
}, {
  output: [64, 64],
  constants: { last: 63 },
});

// Weak pixels that never found a strong friend do not make the cut.
const finish = gpu.createKernel(function (state) {
  if (state[this.thread.y][this.thread.x] > 0.75) {
    return 1;
  }
  return 0;
}, { output: [64, 64] });

// Plain JavaScript: did this pass change anything at all?
function unchanged(a, b) {
  for (let y = 0; y < a.length; y++) {
    for (let x = 0; x < a[y].length; x++) {
      if (a[y][x] !== b[y][x]) return false;
    }
  }
  return true;
}

// TODO: one pass is not hysteresis. A weak pixel three steps from a strong one
// needs three passes to hear about it — keep going until a pass changes nothing.
let state = await grow(classified);
const passes = 1;

console.log('settled after', passes, 'passes');

const edges = await finish(state);
let count = 0;
for (let y = 0; y < 64; y++) {
  for (let x = 0; x < 64; x++) count += edges[y][x];
}
console.log('edge pixels:', count);
```

---

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

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