Floyd–Steinberg dithering

The Floyd -Steinberg algorithm is a first time published in 1976 by ​​Robert W. Floyd and Louis Steinberg dithering algorithm. In image processing, he often finds use in order to reduce the color depth of an image ( for example, when saving a GIF file ) without completely losing the original color impression.

The algorithm operates on the error diffusion method, that is, which occurs in the quantization error (the difference between baseline and quantized value ) of each pixel is distributed according to a fixed scheme of the surrounding pixels. Thus, the algorithm achieved a higher degree of detail than Ordered dither method with a rigid mask. The error of each pixel P is distributed pro rata according to the following scheme of the surrounding pixels:

With this distribution of the algorithm can be used without separate processing the entire input buffer in a single pass. Already processed pixels are not changed, while still be processed pixels are affected according to the quantization errors that occur.

In pseudocode formulated:

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 ] quant_error * 7/16        pixel [x -1] [y 1 ]: = pixel [x -1] [y 1 ] quant_error * 3/16        pixel [ x] [y 1 ]: = pixel [ x] [y 1 ] quant_error * 5/16        pixel [x 1] [y 1 ]: = pixel [x 1] [y 1 ] quant_error * 1/16 The diffusion coefficients have the property that in the case of a plurality of pixels that are exactly in the middle between the two colors of the nearest target range, a chessboard -like pattern. A black and white dithering a gray area to 50 percent would, therefore, a "real" checkerboard pattern.