Floyd-Steinberg dithering

Floyd-Steinberg dithering is an image dithering algorithm first published in 1976 by Robert W. Floyd and Louis Steinberg. It reduces an image to a small palette, for example when a 24-bit truecolor picture is converted to a GIF limited to 256 colors, by error diffusion: each pixel is rounded to the nearest available color and the rounding error is pushed onto neighboring pixels that have not yet been processed, using the weights 7/16, 3/16, 5/16 and 1/16. The image is scanned left to right and top to bottom, so when several pixels have been rounded down the next pixel becomes more likely to be rounded up, and the average error stays close to zero. The weights were found by trial and error, guided by the wish that a region of density 0.5 come out as a checkerboard pattern. Results are best when pixel values are linearized first rather than worked on directly as sRGB values, and some implementations alternate the scan direction between lines, which is called serpentine scanning.