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.
New to trading precision for detail? Start here
With few colours available, rounding each pixel to the nearest one produces flat bands where a gradient should be. The error is small per pixel and it repeats, so the eye finds it immediately.
The alternative is to keep the error rather than discard it. Round a pixel, work out how far off you were, and add that amount to the neighbours you have not drawn yet. The same total error is still there, spread and broken up, and the eye averages it back into the shade that was wanted.
A grid of dots on a clock
A screen is a grid of coloured dots, redrawn from top to bottom on a fixed beat. Everything drawn on it is a decision about which dots and what colour, made before the beat arrives.
The clock is the part that makes this hard. It does not wait, and it does not care whether the drawing was finished, so a picture that took too long is shown half-done. Most of the machines in this topic exist because of that deadline rather than because of the picture.
The machine for this idea on its own is Eight Sprites, if you would rather press it than read about it.
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
The date is 1976 because that is the paper we can read, and it was presented in 1975
Floyd and Steinberg gave this at the Society for Information Display’s 1975 International Symposium; the journal version, the one cited above and the one this page works from, is Proceedings of the SID 17(2), 1976, pages 75-77. The 1975 digest is two pages and it is not online in any form we could reach. Not archive.org, not HathiTrust’s catalogue, not the SID’s own library. Two issued US patents cite it independently and are how we know it exists and where it sat. US 8,289,233 lists it among its references as “SID 75 Digest, 1975, pp. 36 to 37”, and US 5,757,516 spells the venue out: “Society for Information Display 1975 Symposium Digest of Technical Papers, 1975, 36”. So the pill says 1976 for the same reason every date here does: it is the earliest document this page has actually read. The literature is not consistent about it, and the tell is worth seeing. Ostromoukhov’s SIGGRAPH 2001 paper opens with “Since its introduction in 1975 by Floyd and Steinberg” and then cites the 1976 paper in its bibliography. One piece of work, two dates, and which one you meet depends on whether the writer had the talk in mind or the paper.
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 a good deal of software does, image editors and printer drivers included; how much of it is not something anybody here has counted. 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.
- US Patent 8,289,233, which cites An Adaptive Algorithm For Spatial Gray Scale to the SID 75 Digest, 1975, pages 36 to 37. The Digest itself is not online; this is the citation the page relies on for the 1975 presentation.
- US Patent 5,757,516, which names the venue in full: the “Society for Information Display 1975 Symposium Digest of Technical Papers”, page 36. A second, independent citation of a document neither patent’s authors expected anyone to have to take on trust.
- Victor Ostromoukhov, A Simple and Efficient Error-Diffusion Algorithm, SIGGRAPH 2001. Its prose dates the algorithm to 1975 and its bibliography cites the 1976 paper, which is how one piece of work comes to carry two dates.
- 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.