Image Dither Maker

A screen that can only show black and white seems to have nothing to say about grey. Round every pixel to the nearer of the two and a portrait becomes a silhouette: large flat areas, hard contours, most of the detail gone. Yet the same two colours, placed with a little care, can carry the whole photograph. The trick is called dithering, and it works because the eye does not read single pixels. It reads small neighbourhoods and reports their average.

The word is older than the pixel. One account traces it to mechanical computers carried in wartime aircraft, which worked better in flight than on the ground because vibration kept their sticky parts moving; engineers built the vibration in and named it after an old verb meaning to tremble. The idea has not changed since. A little well-chosen disturbance, added before a value is rounded, stops the rounding from always falling the same way.

My argument here is that dithering is bookkeeping. Every method is a rule for what to do with the difference between the colour a pixel wanted and the colour it got. Methods that keep that account balanced look right from across the room. Methods that lose part of it look different, sometimes on purpose. And all of them go wrong together when the account is kept in the wrong currency.

A threshold that moves

The simplest improvement on plain rounding is to stop using the same threshold everywhere. Compare each pixel against a random number instead of against one half, and a region of forty percent grey comes out with roughly forty percent of its pixels white. The average is right. The picture, though, looks like static, because random numbers clump, and the clumps and gaps are large enough to see. Random dithering was tried at least as early as 1951.

So an honest average is necessary but not sufficient. Where the dots fall matters as much as how many of them there are.

Ordered dithering replaces the random numbers with a small fixed table tiled across the picture. The best known tables are the Bayer matrices, from a 1973 paper by Bryce Bayer. They can be built from a single cell by a recursion that quadruples the table each time, and the 8 x 8 version holds 64 thresholds, each exactly once. Because every threshold is used once, a flat grey that is k sixty-fourths of the way to white switches on exactly k cells of each tile.

That makes the method simple to reason about and very fast: each pixel is decided alone, with no memory of its neighbours. It also means the pattern never moves, so an animation dithered this way does not shimmer, and the repetition helps the file compress. The price is the texture. A Bayer matrix arranges its thresholds so regularly that the result carries an unmistakable crosshatch.

Paying the error forward

Error diffusion keeps a ledger instead. It visits the pixels in order, rounds each to the nearest available colour, and hands the leftover difference to neighbours that have not been visited yet. If several pixels in a row were rounded down, the debt builds until one is pushed up. The best known rule was published in 1976 by Robert Floyd and Louis Steinberg. Its weights are 7, 3, 5, 1 over 16: seven sixteenths to the pixel on the right, then three, five and one sixteenths to the three pixels below. The authors reported finding them by trial and error, wanting a half grey to come out as a checkerboard.

Other kernels followed quickly. Jarvis, Judice and Ninke published a larger one the same year that spreads the error over twelve neighbours in two rows below, in forty-eighths. Tables credited to Stucki, Burkes and Sierra adjust the same idea: Stucki changes the numbers, Burkes drops the bottom row so the divisor becomes 32, and the Sierra family offers three sizes down to a three-neighbour kernel. Two independent open source tables I checked agree on the Burkes and Sierra weights; the Stucki numbers I could confirm from only one of them.

All of these share one property. Their weights add up to the divisor, so every unit of error is passed on to somebody. That is why they hold the local average: in my own measurements on a grey ramp, each of the seven full kernels stayed within about one percentage point of the input when averaged over a strip a few dozen pixels wide.

The Atkinson kernel, designed by Bill Atkinson for an early personal computer with a one-bit screen, breaks the rule deliberately. It sends one eighth of the error to each of six neighbours, so only 6 of 8 parts are passed on and a quarter is simply forgotten. The books no longer balance, and the result shows it. Light greys bleach to plain white and dark greys fill in to solid black, while the midtones gain contrast and a clean, open look. On the same ramp its local average strayed by about ten points. That is a choice, and a popular one, but it should be made knowingly.

Error diffusion has costs of its own. Each pixel depends on the ones before it, so the work cannot be split freely across processors, and a small change in the input can rearrange the dots far downstream, which is why it flickers in animation. It can also leave directional artifacts in flat areas. Reversing the scan direction on alternate rows, called serpentine scanning, reduces them.

Why blue noise looks smooth

Between the rigid table and the wandering ledger sits a third idea: keep the speed and independence of a threshold table, but give it the texture of error diffusion. In graphics, blue noise is the loose name for a pattern with very little energy at low frequencies and no sharp spikes. Low frequencies are the blotches and bands the eye catches first. A pattern without them reads as an even grain.

Robert Ulichney described a way to build such a table in 1993 and called it void and cluster. In outline, a sparse random scatter of points is blurred to find where points crowd together and where gaps open, points are moved from the tightest cluster to the largest void until the scatter is even, and then every cell is ranked by the order in which it would be removed or filled. The ranks become thresholds.

I generated a 64 x 64 table this way for the tool on this page, from a fixed seed, and measured it instead of trusting it. Averaged over rings of equal frequency, its power at the coarsest eighth of the spectrum was about 0.015 percent of what a shuffled table of the same size carries. It also wraps: the contrast between neighbours across the seam matched the contrast inside the tile to within about ten percent.

The currency problem

Here is the mistake almost every quick implementation makes. The numbers in an image file are not amounts of light. They are encoded on the sRGB curve, which spends more of its codes on dark tones. The standard decoding divides small values by 12.92 and raises the others, after an offset of 0.055, to the power 2.4, with the switch at 0.04045.

Work an example. Mid grey 128 is 128/255, or 0.502, as a file value. Decoded, it reflects about 21.6% of the light that white does. A dither that works on the file values sees 0.502 and answers with a pattern that is half white. That pattern reflects half the light: more than twice what was asked for. In the tool’s own readout, Floyd-Steinberg on a flat grey 128 printed 50.1 percent white dots when run on encoded values and 21.4 percent when run in linear light.

So the ledger has to be kept in light. Decode first, diffuse the error or apply the thresholds there, and the dots average to the reflectance of the original. The shortcut is not always ugly, and plenty of familiar dithered pictures were made with it, but it lifts every shadow and flattens the picture. When a dither looks washed out, this is usually why.

The rule that follows is short. Measure a dither in light, not in file values, and judge its texture only after the tones are right.

Where it still earns its place

Dithering did not retire with the one-bit screen. Indexed image formats still hold a short palette, and the PNG format packs such images at one, two or four bits per pixel when the palette is small. A widely used imaging library documents exactly one working dither mode for palette conversion, and it is Floyd-Steinberg. Inkjet printers, which can only place a dot or not, lean on it to reach their colour range.

Electronic paper has brought the problem back to desks and shelves. One family of such displays is described as showing 16 shades of grey, and hobby boards are sold that offer only black, white and a single red or yellow. A photograph sent to one of those panels has to be reduced to its inks first. Some games now choose the look for its own sake.

There are things no method can do. Dithering trades resolution for tone, so it cannot add detail, and fine text or thin lines may fare better with a plain threshold. A dithered picture also has to be shown at a whole-number scale with smoothing turned off, because a browser’s default resizing blurs the dots back into mud. Finally, the palette matters more than the kernel: no arrangement of dots can produce a colour that lies outside the range of the inks.