Floyd-Steinberg dithering
- Floyd-Steinberg dithering
Floyd-Steinberg dithering is an image dithering algorithm first published in 1976 by Robert W. Floyd and Louis Steinberg. It is commonly used by image manipulation software, for example when an image is converted into GIF format that is restricted to a maximum of 256 colors.
The algorithm achieves dithering by diffusing the quantization error of a pixel to its neighboring pixels, according to the distribution: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".
In pseudocode: 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 + 128) / 256
ee also
Error diffusion
References
* [http://www.visgraf.impa.br/Courses/ip00/proj/Dithering1/floyd_steinberg_dithering.html 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).
Wikimedia Foundation.
2010.
Look at other dictionaries:
Floyd-Steinberg-Algorithmus — Ein Bild, das mit dem Floyd Steinberg Algorithmus bearbeitet wurde Der Floyd Steinberg Algorithmus ist ein erstmals 1976 von Robert W. Floyd und Louis Steinberg veröffentlichter Dithering Algorithmus. In der Bildbearbeitung findet er häufig… … Deutsch Wikipedia
Steinberg (disambiguation) — Steinberg is a German musical equipment and software company.The name Steinberg (German for mountain of stone ) may also refer to:PeopleMusic*Billy Steinberg, American songwriter *Elliot Easton (born Elliot Steinberg, 1953), American musician… … Wikipedia
Dithering (Bildbearbeitung) — Farbverlauf bei 300 Farben (ohne Dithering) Farbverlauf bei 16 Farben (mit Dithering) Farbverlauf bei 4 Farben (mit Dithering) … Deutsch Wikipedia
dithering — ● ►en n. m. ►GRAPH Technique, et nom de l algorithme qui l implante, consistant à atténuer la mauvaise qualité des images photoréalistes informatiques. Par exemple, un groupe de pixels constitué par un pixel noir suivi de deux blancs sera… … Dictionnaire d'informatique francophone
Dithering — Tramage (informatique) Pour les articles homonymes, voir Tramage. Demande de traduction … Wikipédia en Français
Robert Floyd — Infobox Scientist name = Robert W Floyd image width = caption = birth date = birth date|1936|6|8|mf=y birth place = New York death date = death date and age|2001|9|25|1936|6|8|mf=y death place = residence = citizenship = nationality = American… … Wikipedia
Riemersma dithering — is an image dithering technique that provides a middle ground between ordered dithering and error diffusion. The result is a bit more coarse than error diffusion techniques (such as Floyd Steinberg).When dithering a pixel, the number of… … Wikipedia
Dither — For other uses, see Dither (disambiguation). Provincial definition of to dither from The Rural Economy of Yorkshire: Comprizing the Management of Landed Estates, and the Present Practice of Husbandry in the Agricultural Districts of that County,… … Wikipedia
Rounding — This article is about numerical rounding. For lip rounding in phonetics, see Labialisation. For other uses, see Rounding (disambiguation). Rounding a numerical value means replacing it by another value that is approximately equal but has a… … Wikipedia
Noise shaping — is a technique typically used in digital audio, image, and video processing, usually in combination with dithering, as part of the process of quantization or bit depth reduction of a digital signal. Its purpose is to increase the apparent signal… … Wikipedia
