Task 2 of 6

Let the Histogram Pick the Number

Picking 0.49 by hand was a cheat. Otsu's method reads the number off the data instead: try every cut, keep the one whose two sides are furthest apart.

"Furthest apart" has a precise meaning — the between-class variance. Cut the tone histogram at bin t; let p0 and p1 be the fraction of pixels on each side and mu0, mu1 their mean bin numbers. Then

score(t) = p0 * p1 * (mu0 - mu1) * (mu0 - mu1)

and the winner is the t that maximises it. tones is the 256-bin tone histogram of an evenly lit scene — the same one-thread-per-bin build Histograms & Binning finishes on, handed over here rather than counted again.

The parallel shape is the good part: 256 candidate thresholds, 256 threads, each sweeping all 256 bins for itself. 65,536 reads that happen at once, and then a single tiny argmax over the answers. (Task 3 is the reminder that Otsu picks the best possible single number, and that on a badly lit frame the best possible single number is still not good enough.)

Goal: one thread per candidate threshold — return the between-class variance of the cut at t = this.thread.x, with class 0 being bins 0…t inclusive.

Requirements

Output [256]: one thread per candidate threshold, t = this.thread.x
Sweep all this.constants.bins bins, accumulating each class's count and its count-weighted bin sum
Class 0 is bins 0…t inclusive — a bin equal to t belongs below the cut
Return p0 * p1 * (mu0 - mu1)², or 0 when either class is empty

Hint 1 — one thread, one candidate

Thread t owns exactly one question: what if I cut here? It reads the whole histogram to answer it, which is fine — 256 reads is nothing, and all 256 threads are doing it at the same time.

Hint 2 — four running totals

One pass, four accumulators: the count and the bin-weighted sum on each side.

for (let i = 0; i < this.constants.bins; i++) {
  if (i <= t) {
    w0 += tones[i];
    s0 += i * tones[i];
  } else {
    w1 += tones[i];
    s1 += i * tones[i];
  }
}

The class means are then s0 / w0 and s1 / w1.

Hint 3 — the empty class

At t = 0 class 0 may hold no pixels at all, and s0 / w0 is then 0 / 0 — a NaN that poisons the whole comparison. Guard it: a cut with an empty side separates nothing, so its score is 0.

if (w0 === 0 || w1 === 0) return 0;

Same idea elsewhere

This is the classic "try every candidate in parallel, reduce afterwards" shape: one CUDA thread per hypothesis, one WGSL invocation per bin, one Metal thread per candidate. OpenCV's THRESH_OTSU runs the same arithmetic serially over 256 bins because on a CPU that is already free — on a GPU it is free and it fuses into whatever pass produced the histogram.

All tasks in Thresholding & Morphology

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