prev up inhalt next


5.4 Kompression durch bildbezogene Farbtabelle

Zunächst wird für jede Farbe die Häufigkeit ihres Auftretens ermittelt. Ggf. muß ``vorquantisiert'' werden von 24 Bit auf 15 Bit (je 5 Bit für Rot, Grün, Blau); hierdurch erhält das Histogramm maximal 32768 Einträge. Sei d (a,b) der Abstand zweier Farbtupel a,b , z.B.

Optimaler Algorithmus
Gegeben sei eine Menge F von beobachteten Farben. Gesucht ist eine Menge M von Repräsentanten, so daß der Ausdruck

minimiert wird, d.h., $\Delta$ ist der maximale Abstand, den eine Farbe zu ihrem nächsten Repräsentanten hat.

Da die exakte Bestimmung von M eine exponentielle Laufzeit verursacht, begnügt man sich mit einer Näherungslösung.

Popularity-Algorithmus (1978)
Wähle die K häufigsten Farben. Nachteil: Selten vorkommende Farben werden schlecht repräsentiert.

Diversity-Algorithmus ( xv , John Bradley, 1989)
Initialisiere M mit der häufigsten Farbe.

for i := 2 to K do
   erweitere M um die Farbe des Histogramms,
   die zu allen Farben aus M den groessten Abstand hat
end

Median-Cut (Heckbert, MIT 1980)

Initialisiere RGB-Wuerfel mit Haeufigkeiten der beobachteten Farbtupel
Initialisiere Wurzel des Schnittbaums mit Gesamtzahl der Pixel

While noch_nicht_genuegend_Blaetter do

   Waehle Blatt mit der groessten Pixelzahl
   Bestimme umschliessende Box
   Bestimme Achse mit groesstem Wertebereich
   Durchlaufe Box laengs dieser Achse
   Teile am Median in zwei Haelften
   Trage Haelften als Soehne ein
end
Fuer jedes Blatt waehle den Mittelwert aller in ihm liegenden Farben.


Beispiel für die Anwendung des Median-Cut-Algorithmus. Zur einfachen Darstellung ist der Farbbaum zweidimensional gewählt. Gezeigt wird die Verteilung der Farbtupel aus dem Bereich [0...15] × [0...15] in einem Bild mit 10 × 10 = 100 Pixeln. Eingetragen sind an der Position x/y die Häufigkeit des Farbtupels x,y . Schnittlinien sind gestrichelt, umschließende Boxen durchgezogen gezeichnet.


Schnittbaum nach Anwendung des Median-Cut-Algorithmus. Die Knoten sind markiert mit der Anzahl der noch zu quantisierenden Pixel, an den Kanten ist vermerkt, ob es sich um einen Links/Rechts- oder um einen Oben/Unten-Schnitt handelt.

Floyd-Steinberg-Dithering (1975)
Der bei Verwendung einer Farbtabelle verursachte Fehler beim Quantisieren eines Pixels wird auf die Nachbarpixel verteilt (bevor diese quantisiert werden).

for (i = 0; i < M; i++)
for (j = 0; j < N; j++)
{
   x = f[i][j];   /* hole Original-Farbe */
   k = p(x);      /* finde naechsten Repraesentant */
   q[i][j] = k;   /* zeichne quantisiertes Pixel */
   e = d(x, k);   /* bestimme Fehlerabstand */
   f [i][j + 1]     = f[i][j + 1]     + e * 3.0/8.0;
   f [i + 1][j]     = f[i + 1][j]     + e * 3.0/8.0;
   f [i + 1][j + 1] = f[i + 1][j + 1] + e * 1.0/4.0;
}



24 Bit pro Pixel,
16 Mill. Farben

8 Bit pro Pixel,
256 Farben



4 Bit pro Pixel,
16 Farben

2 Bit pro Pixel,
4 Farben



Original und quantisierte Versionen einer 14 × 14 Ausschnittvergrößerung, erstellt von einem 814 × 517 True-Color-Bild. Die Zahl der Farben bezieht sich jeweils auf das Gesamtbild. Verwendet wurde der Median-Cut-Algorithmus mit anschließendem Floyd-Steinberg-Dithering.


prev up inhalt next