Floyd-Steinberg-Algorithmus
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 Einsatz, um die Farbtiefe eines Bildes zu verringern (zum Beispiel beim Abspeichern einer GIF-Datei) ohne dabei den ursprünglichen Farbeindruck vollständig zu verlieren.
Der Algorithmus arbeitet nach dem Fehlerdiffusionsverfahren (error diffusion), d. h. der bei der Quantisierung auftretende Fehler (die Differenz zwischen Ausgangswert und quantisiertem Wert) eines jeden Pixels wird nach einem festen Schema auf die umliegenden Pixel verteilt. Dadurch erreicht der Algorithmus eine bessere Detailgenauigkeit als Ordered-Dither-Verfahren mit einer starren Maske. Der Fehler jedes Pixels P wird anteilig nach dem folgenden Schema auf die umliegenden Pixel verteilt:
| P | 7⁄16 | |
| 3⁄16 | 5⁄16 | 1⁄16 |
Mit dieser Verteilung kann der Algorithmus ohne separaten Puffer die gesamte Eingabe in einem einzigen Durchlauf abarbeiten. Bereits verarbeitete Pixel werden nicht geändert, während noch abzuarbeitende Pixel entsprechend den auftretenden Quantisierungsfehlern beeinflusst werden.
In Pseudocode formuliert:
for each y
for each x
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 ] + quant_error * 7 / 16
pixel[x-1][y+1] := pixel[x-1][y+1] + quant_error * 3 / 16
pixel[x ][y+1] := pixel[x ][y+1] + quant_error * 5 / 16
pixel[x+1][y+1] := pixel[x+1][y+1] + quant_error * 1 / 16
Die Diffusionskoeffizienten haben die Eigenschaft, dass im Falle mehrerer Pixel, die genau in der Mitte zwischen den zwei nächstgelegenen Farben der Zielpalette liegen, ein schachbrettartiges Muster entsteht. Ein Schwarz-Weiß-Dithering einer zu 50 Prozent grauen Fläche ergäbe demnach ein richtiges Schachbrett-Muster.
