|Example of a 24-bit RGB image dithered to 3-bit RGB using Floyd–Steinberg dithering|
Floyd–Steinberg dithering is an image dithering algorithm first published in 1976 by Robert W. Floyd and Louis Steinberg. It is commonly used by image manipulation software, for example when an image is converted into GIF format that is restricted to a maximum of 256 colors.
The Element indicated with a star (*) indicates the pixel currently being scanned. The algorithm scans the image from left to right, top to bottom, quantizing pixel values one by one. Each time the quantization error is transferred to the neighboring pixels, while not affecting the pixels that already have been quantized. Hence, if a number of pixels have been rounded downwards, it becomes more likely that the next pixel is rounded upwards, such that on average, the quantization error is close to zero.
In some implementations, the horizontal direction of scan alternates between lines; this is called "serpentine scanning" or boustrophedonic dithering.
for each y from top to bottom for each x from left to right oldpixel := pixel[x][y] newpixel := find_closest_palette_color(oldpixel) pixel[x][y] := newpixel quant_error := oldpixel - newpixel pixel[x+1][y] := pixel[x+1][y] + 7/16 * quant_error pixel[x-1][y+1] := pixel[x-1][y+1] + 3/16 * quant_error pixel[x][y+1] := pixel[x][y+1] + 5/16 * quant_error pixel[x+1][y+1] := pixel[x+1][y+1] + 1/16 * quant_error
The diffusion coefficients have the property that if the original pixel values are exactly halfway in between the nearest available colors, the dithered result is a checkerboard pattern. For example 50% grey data could be dithered as a black-and-white checkerboard pattern. For optimal dithering, the counting of quantization errors should be in sufficient accuracy to prevent rounding errors from affecting the result.
For example, to convert 16 bit to 8 bit
find_closest_palette_color() may perform just a simple rounding
find_closest_palette_color(oldpixel) = oldpixel / 256 * 256
 See also
- Floyd–Steinberg Dithering (Graphics course project, Visgraf lab, Brazil)
- R.W. Floyd, L. Steinberg, An adaptive algorithm for spatial grey scale. Proceedings of the Society of Information Display 17, 75–77 (1976).
- PTRANS Stand-alone ANSI-C programming language implementation.