Task 5 of 6

Hysteresis: Run It Until Nothing Changes

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.

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

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

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.

All tasks in The Canny Edge Pipeline

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