Floyd–Steinberg dithering

The algorithm achieves dithering using error diffusion, meaning it pushes (adds) the residual quantization error of a pixel onto its neighboring pixels, to be dealt with later.

It spreads the debt out according to the distribution (shown as a map of the neighboring pixels):

The algorithm scans the image from left to right, top to bottom, quantizing pixel values one by one.

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.

When converting greyscale pixel values from a high to a low bit depth (e.g. 8-bit greyscale to 1-bit black-and-white), find_closest_palette_color() may perform just a simple rounding, for example: The pseudocode can result in pixel values exceeding the valid values (such as greater than 255 in 8-bit greyscale images).

However, if fixed-width integers are used, wrapping of intermediate values would cause inversion of black and white, and so should be avoided.

The find_closest_palette_color() implementation is nontrivial for a palette that is not evenly distributed, however small inaccuracies in selecting the correct palette color have minimal visual impact due to error being propagated to future pixels.