Floyd-Steinberg-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Dithering example undithered.png
Dithering example undithered 16color.png
Dithering example dithered 16color.png


Originalbild (links) konvertiert in 16 Farben: einmal ohne (mitte) und mit Floyd-Steinberg-Dithering (rechts). Siehe insbesondere die Farbverläufe am Hals und den Ohren.
Schwarz-Weiß-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 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 716
316 516 116

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.

Siehe auch