# Let the Histogram Pick the Number

*Task 2 of 6 · [Thresholding & Morphology](https://gpu.rocks/learn/thresholding-and-morphology-670eaafa.md) · GPU.js Learn*

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

```js
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

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

```js
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`.

```js
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.

## Starter code

```js
// 256 candidate thresholds, 256 threads, one histogram sweep each.
const gpu = new GPU({ mode });

const between = gpu.createKernel(function (tones) {
  const t = this.thread.x;
  let w0 = 0;
  let s0 = 0;
  let w1 = 0;
  let s1 = 0;
  // TODO: sweep all this.constants.bins bins. Bins 0…t (inclusive) go into
  // w0/s0, the rest into w1/s1. Then return p0 * p1 * (mu0 - mu1)²,
  // and 0 if either class turned out to be empty.
  return 0;
}, {
  output: [256],
  constants: { bins: 256 },
});

const scores = await between(tones);

// The argmax is one tiny reduction — plain JavaScript is the right tool here.
let best = 0;
for (let t = 1; t < 256; t++) {
  if (scores[t] > scores[best]) best = t;
}
console.log('Otsu threshold: bin', best);
console.log('as a grey level:', (best / 255).toFixed(3));
```

---

Interactive version: https://gpu.rocks/learn/thresholding-and-morphology-670eaafa/2

[Previous task](https://gpu.rocks/learn/thresholding-and-morphology-670eaafa/1.md) · [Next task](https://gpu.rocks/learn/thresholding-and-morphology-670eaafa/3.md)