Thought Toys · Strategy & computation · Exhibit 120
A newspaper press can put a dot of ink on the paper or leave it blank. That is the whole palette: no grey, not one shade. And yet a newspaper photograph has hundreds of greys in it. The trick is not in the dot. It is in what you do with the amount you were wrong by when you rounded — throw it away and you get bands, hand it to the neighbours and you get a photograph.
The same picture, in one bit of ink per pixel ● ink laid down ● the darkness that was asked for
—
—
On the left is a picture with as many greys as you like. On the right is the same picture after every pixel has been forced to one of two values: ink, or no ink. Nothing else is available.
Start by dragging the first slider to zero. Now each pixel is simply rounded to whichever of black and white it is nearer — the obvious thing to do, and it is a disaster. The picture becomes a handful of flat regions with hard edges between them, because every pixel in a wide band of similar tones rounds the same way. All the shading is gone, and it is gone because it was thrown away one pixel at a time: each rounding discarded up to half a unit of darkness and never accounted for it.
Now drag the slider back up. The rule is only this: after rounding a pixel, take the amount you were wrong by and add it to the neighbours you have not visited yet — seven sixteenths to the pixel on the right, and three, five and one sixteenth to the three below. Nothing is discarded. A pixel that was rounded down to white makes the pixels after it slightly darker, so one of them will round to black to make up for it.
Watch the strip underneath while you drag. It compares, column by column, the ink actually laid down against the darkness the original asked for. At zero it is a staircase: whole regions of the picture are getting far too much ink or none. At full strength the two traces lie on top of one another. The count of black dots in any patch is the darkness of that patch, and the eye, which averages over a small neighbourhood without being asked, reads that density as a shade of grey.
So the greys are real but they are not anywhere. No pixel is grey. The grey is a property of a region, and error diffusion is a machine for getting the regional totals right while having only two values to spend.
One last thing to find, with the second slider. Flatten the picture all the way to a uniform fifty percent grey. The speckle stops being speckle and snaps into a perfect checkerboard — every pixel the opposite of all four of its neighbours. That is the algorithm's most famous quirk, and it is not a fault: at exactly half grey, the checkerboard is the finest halftone this grid can physically hold.
The rule, exactly. Visit the pixels in reading order, alternating direction each row. At each one, add in the error already handed to it, round to black or white, and pass the difference on with these weights:
● 7/16 3/16 5/16 1/16The four weights sum to exactly one, which is the whole reason the picture keeps its darkness: the error is only ever moved, never created or destroyed. Robert Floyd and Louis Steinberg published it in 1976. The only error that genuinely disappears is the small amount pushed off the edges of the picture.
The slider scales how much of the error is passed on, so 0% is exactly plain rounding — not almost, exactly: the two produce identical pixels — and 100% is Floyd–Steinberg.
The comparison on this page is against plain rounding, because that is what the slider turns off. It is not a claim to be the best halftone available. Ordered dithering — comparing each pixel against a fixed repeating matrix — also keeps the local density honest. It trades differently: an obvious repeating pattern, in exchange for a scan that can be done in any order, or all at once.
Verified in node before this page existed
(improve/verify/120-error-diffusion.js, 22 checks):
Also in Strategy & computation: Sorting algorithms →