Graustufendarstellung

(nach Bungartz et al. 1996)

Sinnvolle Anzahl von Graustufen:

Darstellung der Intensitätsstufen:

• auf Hardwareseite mehrere Intensitäten pro Pixel

oder

• Halbtonverfahren:

Einteilung des Bildschirms in Makropixel
Wahrnehmung fasst nahe zusammenliegende Pixel-Werte zu Graustufe zusammen

Beispiel: 2 x 2 - Halbtonmatrix

3 x 3:

Wahl der Matrix ist nicht beliebig:

• (a) Vermeidung optischer Artefakte (Linienmuster)
• (b) hardwareabhängig: Vermeidung des Setzens benachbarter Pixel

Vermeidung regelmäßiger Muster:

• Wechsel zwischen mehreren Halbtonmatrizen
• Zufallsauswahl der gesetzten Pixel

Verfahren der Halbtonsimulation auch für Ausgabegeräte mit mehr als 2 darstellbaren Intensitätsstufen anwendbar
z.B. bei 4 Intensitätsstufen 0-3:

Dither-Verfahren:

Intensitätswert wird nicht für Makro-Pixel berechnet, sondern für jedes einzelne Pixel. Darstellung in Abhängigkeit von der Position in einer Dither-Matrix (deren Kopien periodisch den Bildschirm überdecken).

for (y=0; y < rows; y++)
{
for (x=0; x < columns; x++)
{
i = x mod n; j = y mod n;
if (intensity(x, y) > dither[i, j])
set_pixel(x, y, 1);
}
}

Einträge in der Dither-Matrix = Schwellenwerte für die Bildschirmpixel

Wahl der Dither-Matrix:
Vermeidung artifizieller Muster in Bereichen konstanter Intensität
Beispiele:

(aus Rauber 1993)

Vorteil gegenüber Halbton:
bei Vergrößerung von n erhöht sich Anzahl der darstellbaren Graustufen ohne merkliche Änderung der räumlichen Auflösung
(bis zu Schwellenwert für n: bei Auflösung 1024 x 1024 ca. n = 10 bis 16).

Fehlerverteilungsverfahren:

Grundidee: Bei Darstellung des Intensitätswerts in einem Pixel, für den nur diskrete Intensitätswerte möglich sind, wird bei Rundung auf den nächstgelegenen möglichen Wert ein Fehler gemacht. Man versucht, diesen Fehler in den Nachbarpixeln auszugleichen.
Verschiedene Varianten: unterscheiden sich in Reihenfolge der Pixel und Auswahl der Pixel für die Fehler-(ausgleichs-) Verteilung.
Floyd-Steinberg-Verfahren: 3 benachbarte Pixel, Zickzack-Abarbeitung.

Vorteil:

• Verf. liefert oft gute Ergebnisse (besser als Halbton u. Dither)

Nachteile:

• sequentiell
• in ungünstigen Fällen Akkumulation des Fehlers, "Geisterbilder"

Vermeidung dieser Nachteile:

Fehlerdiffusions-Verfahren

Wahl der Diffusionsmatrix:
möglichst wenige Einträge, die keinen oder nur einen Nachbarn mit größerem Eintrag haben (weil dort der Fehler gar nicht oder nur an 1 Nachbarn verteilt werden kann).

Beispiele für Diffusionsmatrizen:

Diffusionsverf. besonders bei Druckeranwendungen dem Dithering und dem Fehlerverteilungsverf. überlegen.
Parallelisierbar, keine Geisterbilder.

Auswahl der Farbschattierungen (Helligkeitsstufen) für die Grundfarben R, G, B:

• logarithmische Wahrnehmungsskala ähnlich wie bei Graustufen
• zusätzlich Gamma-Korrektur des Bildschirms zu beachten (Nichtlinearität in Luminanzantwort des Bildschirm-Phosphors)

Belegung der Farbtabelle (Color Lookup Table):

Ziel: möglichst gute Annäherung der Farben des darzustellenden Bildes durch die Farben in der Tabelle

uniforme Quantisierung
(vgl. Kap. 3)

feste Zuordnung unabh. vom Bild, 3 Bit für Rotstufe, 3 Bit für Grünstufe, 2 Bit für Blaustufe
Standardbelegung der Tabelle bei wenigen darzustellenden Farben, z.B. bei grafischen Benutzungsoberflächen

Popularitätsalgorithmus

Belegung der Farbtabelle mit den 256 häufigsten Farbwerten des darzustellenden Bildes
Für im Bild auftretenden Farbwert wird der nächstliegende Farbwert der Tabelle verwendet

Farbabstände:

• euklidische Metrik im RGB-System

zur Vermeidung der Wurzelberechnung häufig stattdessen:

• Manhattan-Metrik

Einsparen der aufwändigen Minimumsuche für die Abstände: Merken bereits aufgetretener Farbwerte und ihrer zugeordneten Tabelleneinträge in weiterer Tabelle.

Nachteil des Popularitätsalgorithmus:
farbliche Details in kleinen Bildbereichen können völlig falsch dargestellt werden!
Vermeidung:

Median-Schnitt-Algorithmus

unterteilt den RGB-Einheitswürfel sukzessive in Teilquader (Schnitte parallel zu Koordinatenebenen)
1. bestimme kleinsten Teilquader des Würfels, der alle Pixel des Bildes enthält
2. teile diesen so, dass in beiden Hälften (etwa) gleichviele Pixel enthalten sind ("Median-Schnitt")
3. kontrahiere beide Teilquader auf ihre Extremkoordinaten (vgl. Schritt 1)
4. wende hierauf wieder Schritt 2 an...
bis 256 Quader erzeugt sind oder kein Quader mehr geteilt werden kann
- berechne dann für jeden Teilquader Mischfarbe durch gewichtete Mittelwertbildung der enthaltenen Pixel-Werte
diese Farbe wird in die Farbtabelle eingetragen
Bildschirm-Darstellung: jedes Pixel erhält Farbwert des Quaders, in dem es liegt
Datenstruktur: BSP-Baum (binary space partitioning)
Bestimmung eines konkreten Tabellen-Wertes zu einem Farbwert des Bildes durch top-down-Lauf durch den BSP-Baum.

Vorteil: sehr gute Farbdarstellung
- noch weiter verbesserbar durch nachträgl. Anwendung des Floyd-Steinberg-Fehlerverteilungsverfahrens

Nachteil: hoher Speicherplatzbedarf, hohe Laufzeit
(alle Pixel werden im BSP-Baum gespeichert)

"Kompromisslösung": Octree-Quantisierung

regelmäßige rekursive Unterteilung des RGB-Würfels in 8 gleichgroße Unter-Würfel
- Aufbau des Octrees, bis jeder Teilwürfel nur noch 1 Pixel enthält
- Reduktion von den Blättern her (Mittelwertbildung für je 8 Tochter-Würfel), bis der Octree genau 256 Blattknoten hat
(Aufbau und Reduktion können speicherplatzsparend auch verschränkt werden)

Antialiasing

Aliasing (Aliasierung):
Sammelbez. für Verfremdungseffekte, die durch die Rasterkonvertierung stetiger Objekte entstehen

• Lattenzaun-Problem: Objekt mit regelmäßigem, periodischem Aufbau ist nicht verträglich mit der Rasterung

• Moiree-Effekte bei Objekte mit regelmäßiger Textur, Schraffierung etc.: Vortäuschen großflächiger Muster
• dünne Objekte werden "verschluckt" oder verfremdet

Theoretische Grundlage für Aliasing-Probleme:

Signaltheorie

In der Fourieranalyse wird jede Funktion f als Überlagerung von trigonometrischen Funktionen (sin und cos) mit verschiedenen Frequenzen dargestellt.

Antialiasing-Techniken:

• Prefiltering (Vorfilter-Techniken): Vermeidung des Aliasing vor der Bildschirmdarstellung durch geeignete Bildmanipulation
• Postfiltering (Nachfiltern): Abschwächung des Aliasing durch Nachbehandlung des bereits gerasterten Bildes
• Modifikation der Zeichenalgorithmen

oder: heuristische Techniken
2 Techniken, die häufig für Linien angewandt werden:

1.

• Zeichnen in doppelter Auflösung
• anschließende Verdopplung
• anschließende Zuordnung eines Grauwertes je nach Bedeckungsgrad der 4x4-Makropixel (die den echten Pixeln entsprechen)

Ergebnis: "verschmierte" Linie, die in der Wahrnehmung aber "glatter" erscheint
Qualität: ca. entspr. doppelter Bildauflösung

Gegenüberstellung der Rasterdarstellung einer Linie
(a) ohne Anti-Aliasing
(b) mit Anti-Aliasing
(c) mit doppelter Auflösung, ohne Anti-Aliasing:

2.
Area Sampling:

• Modellierung der Linie als rechteckiger Bereich

Weighted area sampling

den Pixeln werden überlappende Kreisscheiben zugeordnet:

Pixel P, Kreisscheibe K_P, überdeckter Flächenteil A_P

Effiziente Implementation:
Algorithmus von Gupta und Sproull
Anstelle der Integralberechnung werden die Intensitätswerte in Abhängigkeit von d für 24 Werte von d (d = i/16, i=0;...;23) in einer Tabelle gespeichert. d kann beim Zeichnen inkrementell berechnet werden (vgl. Bresenham-Algorithmus).

Abhängigkeit der Intensität vom Abstand d.
Links: d = 0, Mitte: d = 0,75, rechts: d = 1,0.

Postfiltering-Techniken
(am häufigsten angewandte Antialiasing-Techniken)

Supersampling

Rasterung mit höherer Auflösung als der Bildschirm (Faktor 2 oder 4)
Intensitätswert eines Bildschirmpixels als Mittelwert der zugehörigen (4 oder 16) Pixel im errechneten Rasterbild
d.h.: Anwendung eines 2x2- oder 4x4-Filters auf das Rasterbild

ungewichteter Filter

Filter mit stärkerer Gewichtung des mittleren Pixelblocks

Nachteile:

• Schwäche des Supersamplings bei Bildern mit dünnen Linien

Ergebnis des Supersamplings einer Linie mit 4 x 4-Filter mit gleichmäßiger Gewichtsverteilung. Die resultierenden Bildschirmpixel zeigen nur 1/4 der max. Intensität und sind ebenso gestuft wie das Original.

• hoher Rechenzeit- und Speicherplatzaufwand

Abhilfe: adaptives Supersampling. Gröbere Rasterung in Bereichen konstanter Intensität.

Filter-Methode (ohne Supersampling)

Es wird mit der Auflösung des Bildschirms gearbeitet. Die endgültige Darstellung wird durch gewichtete Mittelung der Intensitäten benachbarter Pixel erzeugt:
"Verschmieren" der Intensitäten der Pixel.

3 x 3 - Filter:

Für höhere Bildschirm-Auflösungen: 5 x 5 - Filter

(hier: Bartlett-Filter):

Die Summe der Gewichtsfaktoren ergibt 1.
Der Filter wird "über die Pixel des Rasterbildes geschoben".
Vor der Anwendung: Replikation der Randzeilen und -spalten.