Floyd-Steinberg-Algorithmus

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 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 Error-Diffusion-Verfahren, 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  ] + 7 * quant_error / 16
      pixel[x-1][y+1] := pixel[x-1][y+1] + 3 * quant_error / 16
      pixel[x  ][y+1] := pixel[x  ][y+1] + 5 * quant_error / 16
      pixel[x+1][y+1] := pixel[x+1][y+1] + 1 * quant_error / 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 Schachbrett-artiges Muster entsteht. Ein Schwarz-Weiß-Dithering einer zu 50 Prozent grauen Fläche ergäbe demnach ein "richtiges" Schachbrett-Muster.

Siehe auch


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Floyd — ist ein Vorname und Familienname, siehe Floyd (Name) für Etymologie und Namensträger Orte in den Vereinigten Staaten: Floyd (Alabama) Floyd (Arkansas) Floyd (Georgia) Floyd (Iowa) Floyd (Kalifornien) Floyd (Kentucky) Floyd (Louisiana) Floyd… …   Deutsch Wikipedia

  • Robert Floyd — Robert „Bob“ W Floyd (* 8. Juni 1936 in New York City; † 25. September 2001 in Stanford, Kalifornien) war ein amerikanischer Informatiker und Turing Preisträger. Er ließ seinen ursprünglichen zweiten Vornamen auf „W“ ändern, jedoch betonte er oft …   Deutsch Wikipedia

  • Dithering (Bildbearbeitung) — Farbverlauf bei 300 Farben (ohne Dithering) Farbverlauf bei 16 Farben (mit Dithering) Farbverlauf bei 4 Farben (mit Dithering) …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”