Floyd-Steinberg dithering

From Wikipedia, the free encyclopedia

Floyd-Steinberg 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 algorithm achieves dithering by diffusing the quantization error of a pixel to its neighboring pixels, according to the distribution

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 pseudocode:

for each y
   for each x
      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 inbetween the nearest available colors, the dithered result is a checkerboard patter. For example 50% grey data could be dithered as a black-and-white checkerboard pattern.

[edit] References

• 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).