Example of a 24-bit RGB image dithered to 3-bit RGB using Floyd-Steinberg dithering

Floyd–Steinberg dithering is an image dithering algorithm first published in 1976 by Robert W. Floyd

Robert Floyd

Robert W Floyd was an eminent computer scientist.His contributions include the design of the Floyd–Warshall algorithm , which efficiently finds all shortest paths in a graph, Floyd's cycle-finding algorithm for detecting cycles in a sequence, and his work on parsing...

 and Louis Steinberg. It is commonly used by image manipulation software, for example when an image is converted into GIF

GIF

The Graphics Interchange Format is a bitmap image format that was introduced by CompuServe in 1987 and has since come into widespread usage on the World Wide Web due to its wide support and portability....

 format that is restricted to a maximum of 256 colors.

The algorithm achieves dithering by diffusing the quantization error

Quantization error

In analog-to-digital conversion, the difference between the actual analog value and quantized digital value is called quantization error or quantization distortion. This error is either due to rounding or truncation...

 of a pixel

Pixel

In digital imaging, a pixel, or pel, is a single point in a raster image, or the smallest addressable screen element in a display device; it is the smallest unit of picture that can be represented or controlled....

 to its neighboring pixels, according to the distribution
The Element indicated with a star (*) indicates the pixel currently being scanned.
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 some implementations, the horizontal direction of scan alternates between lines; this is called "serpentine scanning" or boustrophedon

Boustrophedon

Boustrophedon , is a type of bi-directional text, mostly seen in ancient manuscripts and other inscriptions. Every other line of writing is flipped or reversed, with reversed letters. Rather than going left-to-right as in modern English, or right-to-left as in Arabic and Hebrew, alternate lines in...

ic dithering.

In pseudocode

Pseudocode

In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...

:
for each y from top to bottom
for each x from left to right
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 in between the nearest available colors, the dithered result is a checkerboard pattern. For example 50% grey data could be dithered as a black-and-white checkerboard pattern. For optimal dithering, the counting of quantization errors should be in sufficient accuracy to prevent rounding errors from affecting the result.

For example, to convert 16 bit to 8 bit find_closest_palette_color may perform just a simple action
find_closest_palette_color(oldpixel) = oldpixel / 256

External links

• PTRANS Stand-alone ANSI-C programming language implementation.