Dithering
A palette too small for a picture forces every pixel to the nearest tone it has, and the difference is thrown away. Error diffusion does not throw it away: it hands it to the pixels that have not been decided yet, in fixed proportions, so that a patch which should average halfway between two tones does. The claim worth checking is not that it looks better. It is that nothing is lost — the error removed equals the error handed on plus the error that spills off the edge — and that is arithmetic, so this page adds it up.
A ramp, two tones, and the error moved rather than lost
1 A gradient, and a palette too small to hold it
A left-to-right ramp, and a palette with nothing in the middle of it.
2 (0, 255)
32 by 16 pixels, left to right from 0 to 255, and a palette of 2: 0, 255. Most of the ramp is not in it.
2 Round each pixel to the nearest available tone and keep the error
Round every pixel to the nearest tone and throw the difference away. This is the best possible answer per pixel and the worst one per patch.
Mean error 61.7 per pixel, and the ramp has become 2 bands with hard edges. No pixel could have done better on its own; that is what makes the banding unavoidable this way.
3 Push that error into the neighbours, in the proportions Floyd and Steinberg chose
Now keep the error and push it into the neighbours, in the proportions Floyd and Steinberg chose.
| neighbour | share |
|---|---|
| the pixel to the right | 7 of 16 |
| below and to the left | 3 of 16 |
| directly below | 5 of 16 |
| below and to the right | 1 of 16 |
Mean error 80.9 per pixel, which is worse than 61.7. The bands are gone anyway, because the error is still in the picture rather than discarded — moved sideways into pixels that had not been decided yet.
4 The error removed and the error distributed, added up and compared
The books balance: what came off the pixels, and where it went.
- net error removed (signed)
- -2091.628913816516
- net handed to neighbours
- -1581.628913816514
- net spilled off the edges
- -510.000000000003
- unaccounted for
- 0 (to twelve decimal places)
- worst four-by-four patch, flat
- 111.0
- worst four-by-four patch, dithered
- 18.5
Every unit taken off a pixel was handed to a neighbour or spilled off an edge, and the three signed totals balance to twelve decimal places. The trade is underneath them: per pixel dithering is worse (80.9 against 61.7), and over a 4 by 4 patch it is 6.0 times better (18.5 against 111.0).
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| every unit of error removed is handed to a neighbour or spills off the edge, to within 9.1e-13 | yes | -2091.629 removed, -1581.629 handed on, -510.000 spilled at the edges |
| the four shares are 7, 3, 5 and 1 sixteenths, which add to 16 | yes | they are a fraction of the error, so they have to sum to one |
| no pixel is closer to the original than flat rounding leaves it, and 122 of 512 are further: 80.9 against 61.7 mean absolute error | yes | that is the price. Flat rounding puts each pixel as close as the palette allows and is the best possible per-pixel answer; dithering deliberately takes a worse one to pay off a neighbour |
| over every four-by-four patch the dithered average is out by at most 18.5, against 111.0 flat | yes | this is the thing dithering is for, and it is the measurement that shows it |
What is real here, and what is not
Every value here is linear, and a display is not
The arithmetic works on values from nought to two hundred and fifty-five treated as if they were light, and they are not: a display applies a transfer function, so an eight-bit value of 128 is about a fifth of the light of 255 rather than half. Error diffusion done in gamma-encoded values is a different algorithm with a different answer, and it is what most implementations actually do. This page does the linear one and says so rather than quietly being either.
Individual pixels get worse, and that is the trade
Flat rounding puts every pixel as close to the original as the palette allows, which is the best per-pixel answer available. Dithering deliberately takes a worse one to pay off a neighbour, and the page measures both: mean absolute error per pixel rises, worst error over a four-by-four patch falls by a large factor. Anything that presents dithering as free is measuring only the half that flatters it.
Error that reaches an edge is counted, not dropped
The rightmost column and the bottom row have nowhere to push part of their error. Many implementations silently discard it. This one adds it to a spilled total and prints it, because the conservation claim is only true if the thing that escapes is named.
The three totals are signed, and one of them is negative
Rounding pushes a pixel up as often as it pushes it down, so the error taken off the picture is a signed sum and comes out negative here: the palette's tones are not evenly placed under this ramp. Conservation is a statement about that signed sum, which is the only version that can be true — if the totals were absolute values they would not balance and the page would be claiming something false with a bigger number.
Sources
- R. W. Floyd and L. Steinberg, An Adaptive Algorithm for Spatial Greyscale, Proceedings of the SID 17(2), 1976, pages 75-77.
- The ICC's own registry entry for sRGB, which carries the transfer function of IEC 61966-2-1. Why arithmetic on encoded values is not arithmetic on light.
- Logical Art, the studio this belongs to.