Floyd-Steinberg Dithering

Classical Algorithm - Developed Algorithms

This technique generates the best results of any classical method here, and is naturally the slowest.  In fact, there are many variants of this technique as well, and the better they get, the slower they are.

The Floyd-Steinberg dithering algorithm is based on error dispersion. The error dispersion technique is very simple to describe: for each point in the image, first find the closest color available.  Calculate the difference between the value in the image and the color you have.  Now divide up these error values and distribute them over the neighboring pixels which you have not visited yet.  When you get to these later pixels, just add the errors distributed from the earlier ones, clip the values to the allowed range if needed, then continue as above.

If you are dithering a grayscale image for output to a black-and-white device, the "find closest color" is just a simple thresholding operation.  In color, it involves matching the input color to the closest available hardware color, which can be difficult depending on the hardware palette.

There are many ways to distribute the errors and many ways to scan the image, but I will deal here with only a few.  The two basic ways to scan the image are with a normal left-to-right, top-to-bottom raster, or with an alternating left-to-right then right-to-left raster.  The latter method generally produces fewer artifacts and can be used with all the error diffusion patterns discussed below.

The different ways of dividing up the error can be expressed as patterns (called filters, for reasons too boring to go into here).

                  X   7            This is the Floyd and Steinberg

             3   5   1            error diffusion filter.

In this filter, the X represents the pixel you are currently scanning, and the numbers (called weights, for equally boring reasons) represent the proportion of the error distributed to the pixel in that position.  Here, the pixel immediately to the right gets 7/16 of the error (the divisor is 16 because the weights add to 16), the pixel directly below gets 5/16 of the error, and the diagonally adjacent pixels get 3/16 and 1/16.  When scanning a line right-to-left, this pattern is reversed.  This pattern was chosen carefully so that it would produce a checkerboard pattern in areas with intensity of 1/2 (or 128 in our image).  It is also fairly easy to calculate when the division by 16 is replaced by shifts.

Exemplifying: