Rounding With a Debt to Pay Forward

ditheringgraphicsartwoodworkingdesign

A marquetry artist doesn’t have a paint mixer. They have a drawer: maybe walnut, a bit of maple, a warm cherry, one precious scrap of bog oak. Four tones, and a whole photograph’s worth of shading to suggest. So they cheat the eye — a fleck of dark grain here, a lighter sliver there — and from across the room your brain smooths the discrete patches back into a continuous curve of shadow.

Computing hit the same wall and named the way out error diffusion. When Robert Floyd and Louis Steinberg published their dithering scheme in 1976, screens and printers had exactly the veneer-drawer problem: a handful of ink dots or brightness levels, and images that wanted thousands. Their fix is almost stubborn in its simplicity. Round each pixel to the nearest tone you actually own, measure how wrong that was, and shove the leftover error onto the neighbours so they lean the other way to compensate.

Walk a single row of greys with a three-tone “veneer palette” of {0, 128, 255}:

palette = [0, 128, 255]
nearest = fn v -> Enum.min_by(palette, &abs(&1 - v)) end
row = [90, 100, 110, 120, 130, 140, 150, 160]

{out, _} =
  Enum.map_reduce(row, 0, fn px, err ->
    target = px + err
    q = nearest.(target)
    {q, target - q}
  end)

IO.inspect(out)
# => [128, 0, 128, 128, 128, 128, 255, 128]

The error term is memory. Each pixel inherits how badly the previous one got rounded and pays the debt down the line, so a run of hundred-ish greys doesn’t all snap flat to 128 — it dips to 0 and spikes to 255 just often enough that the running average tracks the true gradient.

Bash does the identical accounting with integers and a nested nearest-tone loop, just louder:

#!/usr/bin/env bash
palette=(0 128 255)
row=(90 100 110 120 130 140 150 160)
err=0
for px in "${row[@]}"; do
  t=$((px + err)); best=0; bd=99999
  for p in "${palette[@]}"; do
    d=$(( t>p ? t-p : p-t ))
    (( d < bd )) && { bd=$d; best=$p; }
  done
  printf '%d ' "$best"; err=$(( t - best ))
done; echo   # 128 0 128 128 128 128 255 128

Marquetry runs the same trick in two dimensions, with a bonus axis Floyd and Steinberg never had: grain direction. The same walnut reads darker across the grain than along it, so rotating a piece mints new tones out of one board. The palette stays tiny; the arithmetic of spreading the shortfall around does the rest.