Floyd–Steinberg dithering (1976)

Floyd–Steinberg dithering is a method for turning a grey picture into one made only of black and white dots, by passing the error made at each dot on to the dots next to it. It was published in 1976 by the computer scientists Robert W. Floyd and Louis Steinberg, in a three-page paper titled "An adaptive algorithm for spatial grey scale".¹

The problem

A newspaper printed in black ink on white paper can only put a dot or leave it out, and so can many printers and the pixels of a black-and-white screen. Showing shades of grey with only two colours is called halftoning; dithering is the kind of halftoning made for a fixed grid of pixels.²

The simplest rule is a threshold: every pixel darker than half grey becomes black, the rest white. All the shading is lost, and a lit ball turns into a black crescent, as in the left of the picture above. Ordered dithering compares the pixels with a fixed pattern of thresholds, such as a 4 × 4 Bayer matrix, so mid-greys become regular grids of dots (middle).³ In Lund in the 1970s, Mikael Jern's COLOR program for the Hertz ink-jet plotter also worked with fixed patterns, adjusting "the dot density in a series of 16 steps".⁴ How his colour cubes became prints is told in JAEV's The colour cubes. The drawback of fixed patterns is that the eye sees them, and they distract from the picture.^2, 3

How it works

Floyd and Steinberg visit the pixels one at a time, left to right along a row and row by row from the top.¹ For each pixel:

1. Round it to black or white, whichever is nearer.
2. Work out the error: how much lighter or darker the pixel was than the value it was given. A pixel at 40 per cent grey that is made white has an error of 40 per cent.
3. Add that error, in fixed shares, to four neighbours not yet visited: 7/16 to the pixel on the right, 3/16 to the one below left, 5/16 to the one below and 1/16 to the one below right.¹

The shares add up to 16/16, so no grey is lost: what one pixel could not show is shown by the pixels around it. Where the picture is 40 per cent grey, about 40 per cent of the pixels end up black, scattered rather than in a grid (right of the picture). According to Wikipedia, the weights were chosen so that an area of exactly half grey comes out as a checkerboard.¹

New drawing

Dots for a pen

For a plotter, a dithered picture is a list of places to put the pen down. Kaplan and Bosch, who make line drawings from dots, point out that most dithering tries to hide its pattern, while for art the pattern can be the point: they used deliberately ordered dithering to get maze-like TSP art.² A method that spaces dots evenly instead of on a grid is weighted Voronoi stippling.