Quelltext der Seite Floyd-Steinberg-Algorithmus

[[Datei:Michelangelo's David - Floyd-Steinberg.png|mini|Schwarz-Weiß-Bild, das mit dem Floyd-Steinberg-Algorithmus bearbeitet wurde]]

Der '''Floyd-Steinberg-Algorithmus''' ist ein erstmals 1976 von [[Robert Floyd|Robert W. Floyd]] und [[Louis Steinberg]] veröffentlichter [[Dithering (Bildbearbeitung)|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.&nbsp;h. der bei der [[Quantisierung (Signalverarbeitung)|Quantisierung]] auftretende Fehler (die Differenz zwischen Ausgangswert und quantisiertem Wert) eines jeden [[Pixel]]s 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:

{| class="wikitable"
|-
|
| class="hintergrundfarbe6" | P
|{{Bruch|7|16}}
|-
|{{Bruch|3|16}}
|{{Bruch|5|16}}
|{{Bruch|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&nbsp;Prozent grauen Fläche ergäbe demnach ein richtiges Schachbrett-Muster.
{{Mehrere Bilder|Breite=200
|Bild1=Dithering example undithered.png
|Bild2=Dithering example undithered 16color.png
|Bild3=Dithering example dithered 16color.png
|Fußzeile=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.
}}

== Siehe auch ==
* [[Dithering (Bildbearbeitung)]]


[[Kategorie:Algorithmus (Computergrafik)]]