Dithering: Unterschied zwischen den Versionen

Aktuelle Version vom 31. Juli 2010, 15:55 Uhr

Hinweis: Diesem Artikel sollten folgende Bilder beigefügt werden: (Mehr Informationen/weitere Artikel)
Für die unterschiedlichen Verfahren ein Bild bitte.

Übersicht

Dithering wird verwendet um mit wenigen Farben viele Farben zu simulieren. In den Printmedien wird Dithering häufig auch als Halftoning bezeichnet und verwendet. Hierbei werden schwarze und weisse Bildpunkte so angeordnet, dass man den Eindruck eines Graustufen-Bildes erhält. Nachteil an der Sache ist, das meistens die Auflösung reduziert wird.

Dithering und OpenGL

Der verwendete Dithering-Algorithmus ist abhängig von der OpenGL-Implementierung. Allerdings kann ein guter Dithering-Algorithmus die Bildqualität auf Displays mit kleiner Farbzahl stark erhöhen. Dithering ist standardmässig eingeschaltet und kann mit glEnable bzw. glDisable und dem Parameter GL_DITHER kontrolliert werden. Bei hoher Farbzahl ist Dithering nicht zwingend erforderlich und kann aus Perfomance-Gründen abgeschaltet werden.

Technischer Hintergrund

Aus Gründen der Übersichtlichkeit wird Dithering anhand von 256 Graustufen erläutert. Um Dithering auf Farbe anzuwenden, werden die vorgestellten Techniken auf jeden Farbkanal angewandt.

Naive Ansätze

Down Scaling

Wiki-Logo mit Downscaling

Im einfachsten Ansatz wird für jeden Pixel eine Entscheidung getroffen, welchen Wert er zugewiesen bekommt. Das heißt die Originalfarben werden gleichmäßig auf die reduzierte Palette aufgeteilt. Bei einer Reduktion auf Schwarz und Weiss werden z.B. Pixel mit einem Grauwert >= 128 auf Weisse Pixel und alle anderen Pixel auf Schwarz abgebildet.

Random Decision

Eine deutliche Verbesserung erzielt man wenn die Entscheidung nicht über den Wert des Pixels getroffen wird, sondern dieser Wert als Wahrscheinlichkeit betrachtet wird ob ein Pixel gesetzt wird oder nicht. So wird ein Pixel mit einem Wert von 152 mit der Wahrscheinlichkeit 152/256 durch einen weissen Pixel ersetzt. Die harten Kanten zwischen Weiss und Schwarz werden durch diese Weise zwar ersetzt, aber es ist ein ziemlich guter Zufallszahlen-Generator erforderlich um akzeptable Ergebnisse zu erhalten.

Filling Patterns

Filling Patterns sind reguläre Muster, die dazu verwendet werden eine gewisse Anzahl an Graustufen abzubilden. Mit einem nxn Muster ist es möglich n*n+1 verschiedene Graustufen darzustellen. Als Beispiel die Muster für ein 2x2 (5 Graustufen) Muster.

Hierbei sollte man versuchen die Pixel so irregulär wie möglich zu verteilen, da sonst sichtbare Artefakte (horizontale/vertikale) Linien in den Bilder entstehen. Das Muster wird auf einen gleichgrossen Bereich von Pixeln im Bild gelegt. Man berechnet den Mittelwert der Pixel unter dem Muster und entscheided dann, welches Muster anstelle der nxn Pixel verwendet wird.

Dither Matrizen

Dither Matrizen sind eine Weiterentwicklung von Filling Patterns. Eine Dither-Matrix der Grösse nxn wird mit den Werten von [0..n*n-1] gefüllt und bewirkt eine Reduktion der Graustufen auf nxn+1. Im Unterschied zu Filling Patterns werden hier allerdings die einzelnen Pixel stärker berücksichtigt. Je nach Art des Musters in dem die Werte in der Matrix verteilt werden spricht man von Clustered-Dot Dithering (Laserdrucker, Printmedien, etc.) oder Dispersed Dot Dithering.

Je nach Ausgabemedium werden unterschiedliche Verfahren angewendet. Hat das Ausgabemedium eine höhere Auflösung als das Eingabebild, so werden die Dither-Matrizen auf jeden Pixel angewandt. Für jeden Pixel wird ein Wert berechnet, der im Wertebereich [0..n*n-1] liegt und in der Matrix werden alle Elemente < dieses Wertes angeschaltet. Eine weit verbreitete Methode zur Berechnung des Wertes ist der Modulo-Operator (C mod n*n - wobei C die aktuelle Pixelfarbe ist). Bei niedrigerer Auflösung wird das gleiche Verfahren wie bei Filling Patterns angewandt, was die Auflösung allerdings drastisch reduziert. Die Verteilung der Werte in der Matrix ist übrigens beliebig. Man sollte aber beachten das reguläre Muster zu sichtbaren Artefakten im Ausgabe-Bild führen.

Floyd-Steinberg Error Diffusion

Das Wiki-Logo mit Floyd-Steinberg Dithering vereinfacht.

Das Floyd-Steinberg Dithering arbeitet nach dem Error Diffusion Verfahren. Der Algorithmus sucht in der Farbpalette nach der bestmöglichen Farbe, die in den aktuellen Farbwert hineinpasst. Der Farbwert aus der Palette darf nicht größer sein als die eigentliche Farbe. Die Abweichung des Paletteneintrages zur ursprünglichen Farbe (auch Fehler genannt) wird nach einem festen Schema auf die umliegenden Pixel verteilt. Dadurch wird bewerkstelligt, dass das resultierende Bild, vom Pixeldurchschnitt her, so nah wie möglich an dem Original liegt.

Um die Entstehung von zu gleichmäßige Mustern zu verhindern wird abwechselnd je eine Zeile von Links und eine von Rechts verarbeitet.

Literatur

• OpenGL Superbible, 3rd. Edition, Wright & Lipchak, SAMS
• Computer Graphics - Principles and Practice, Second Edition in C, Foley & van Dam & Feiner & Hughes, Addison Wesley
• Skript zur Vorlesung Computer Graphics I, 1st Edit. 3rd Rev., Kobbelt & Sar-Dessai, Lehrstuhl für Informatik 8 - RWTH Aachen
• Périphériques de tracé, d'affichage et d'impression 2-D, Notes de cours, Hersch, Laboratoire de Systèmes Périphériques - EPFL