Floyd-Steinberg algorithm
The Floyd-Steinberg dithering is a first time in 1976 by Robert W. Floyd and Louis Steinberg published dithering algorithm . It is often used in image processing to reduce the color depth of an image (for example when saving a GIF file) without completely losing the original color impression.
The algorithm works according to the error diffusion method , i.e. H. the error that occurs during quantization (the difference between the initial value and the quantized value) of each pixel is distributed to the surrounding pixels according to a fixed scheme. As a result, the algorithm achieves a better level of detail than the ordered dither method with a rigid mask. The error of each pixel P is proportionally distributed to the surrounding pixels according to the following scheme:
| P | 7 ⁄ 16 | |
| 3 ⁄ 16 | 5 ⁄ 16 | 1 ⁄ 16 |
With this distribution, the algorithm can process the entire input in a single pass without a separate buffer. Pixels that have already been processed are not changed, while pixels that are still to be processed are influenced according to the quantization errors that occur.
Formulated 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 ] + 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 several pixels which are exactly in the middle between the two closest colors of the target palette, a checkerboard-like pattern is created. A black and white dithering of a 50 percent gray area would result in a real checkerboard pattern.