Floyd–Steinberg Dithering
   HOME

TheInfoList



OR:

Floyd–Steinberg dithering is an image
dithering Dither is an intentionally applied form of noise used to randomize quantization error, preventing large-scale patterns such as color banding in images. Dither is routinely used in processing of both digital audio and video data, and is often ...
algorithm first published in 1976 by
Robert W. Floyd Robert W. Floyd (born Robert Willoughby Floyd; June 8, 1936 – September 25, 2001) was an American computer scientist. His contributions include the design of the Floyd–Warshall algorithm (independently of Stephen Warshall), which efficientl ...
and Louis Steinberg. It is commonly used by image manipulation software, for example, when converting an image from a Truecolor 24-bit PNG format into a
GIF The Graphics Interchange Format (GIF; or , ) is a Raster graphics, bitmap Image file formats, image format that was developed by a team at the online services provider CompuServe led by American computer scientist Steve Wilhite and released ...
format, which is restricted to a maximum of 256 colors.


Implementation

The algorithm achieves dithering using error diffusion, meaning it pushes (adds) the residual
quantization error Quantization, in mathematics and digital signal processing, is the process of mapping input values from a large set (often a continuous set) to output values in a (countable) smaller set, often with a finite number of elements. Rounding and ...
of a
pixel In digital imaging, a pixel (abbreviated px), pel, or picture element is the smallest addressable element in a Raster graphics, raster image, or the smallest addressable element in a dot matrix display device. In most digital display devices, p ...
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): \begin & & * & \frac & \ldots \\ \ldots & \frac & \frac & \frac & \ldots \\ \end The pixel indicated with a star (*) indicates the pixel currently being scanned, and the blank pixels are the previously-scanned pixels. 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. 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 correct results, all values should be linearized first, rather than operating directly on sRGB values as is common for images stored on computers. In some implementations, the horizontal direction of scan alternates between lines; this is called "serpentine scanning" or
boustrophedon transform In mathematics, the boustrophedon transform is a procedure which maps one sequence to another. The transformed sequence is computed by an "addition" operation, implemented as if filling a triangular array in a boustrophedon (zigzag- or serpentine-l ...
dithering. The algorithm described above is in the following
pseudocode In computer science, pseudocode is a description of the steps in an algorithm using a mix of conventions of programming languages (like assignment operator, conditional operator, loop) with informal, usually self-explanatory, notation of actio ...
. This works for any approximately linear encoding of pixel values, such as 8-bit integers, 16-bit integers or real numbers in the range
, 1 The comma is a punctuation mark that appears in several variants in different languages. Some typefaces render it as a small line, slightly curved or straight, but inclined from the vertical; others give it the appearance of a miniature fille ...
for each ''y'' from top to bottom do for each ''x'' from left to right do oldpixel := pixels 'x''''y''] newpixel := find_closest_palette_color(oldpixel) pixels 'x''''y''] := newpixel quant_error := oldpixel - newpixel pixels 'x'' + 1''y'' ] := pixels 'x'' + 1''y'' ] + quant_error × 7 / 16 pixels 'x'' - 1''y'' + 1] := pixels 'x'' - 1''y'' + 1] + quant_error × 3 / 16 pixels 'x'' ''y'' + 1] := pixels 'x'' ''y'' + 1] + quant_error × 5 / 16 pixels 'x'' + 1''y'' + 1] := pixels 'x'' + 1''y'' + 1] + quant_error × 1 / 16 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: find_closest_palette_color(oldpixel) = round(oldpixel / 255) The pseudocode can result in pixel values exceeding the valid values (such as greater than 255 in 8-bit greyscale images). Such values should ideally be handled by the find_closest_palette_color() function, rather than clipping the intermediate values, since a subsequent error may bring the value back into range. However, if fixed-width integers are used, wrapping of intermediate values would cause inversion of black and white, and so should be avoided. The 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. A
nearest neighbor search Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest (or most similar) to a given point. Closeness is typically expressed in terms of a dissimilarity function: ...
in 3D is frequently used.


See also

* Atkinson dithering, a variant of Floyd–Steinberg dithering designed by Bill Atkinson


References


Floyd–Steinberg Dithering
(Graphics course project, Visgraf lab, Brazil) *R.W. Floyd, L. Steinberg, ''An adaptive algorithm for spatial grey scale''. Proceedings of the Society of Information Display 17, 75–77 (1976). {{DEFAULTSORT:Floyd-Steinberg dithering Image processing Articles with example pseudocode Computer graphics algorithms Articles with example code