Farbbilder - Digitale Bildverarbeitung - page 288

12.5 Farbquantisierung

Abbildung 12.30
Median-Cut-Algorithmus. Der RGB-
Farbraum wird schrittweise in immer
kleinere Quader quer zu einer der
Farbachsen geteilt.

1. Schnitt 2. Schnitt 3. Schnitt

Das Ergebnis am Ende dieses rekursiven Teilungsvorgangs sind n
Quader im Farbraum, die idealerweise jeweils dieselbe Zahl von Bild-
punkten enthalten. Als letzten Schritt wird fur jeden Quader ein reprasen-
tativer Farbvektor (z. B. der arithmetische Mittelwert der enthaltenen
Farbpunkte) berechnet und alle zugehorigen Bildpunkte durch diesen
Farbwert ersetzt.
Der Vorteil dieser Methode ist, dass Farbregionen mit hoher Dichte
in viele kleinere Zellen zerlegt werden und dadurch die resultierenden
Farbfehler gering sind. In Bereichen des Farbraums mit niedriger Dichte
konnen jedoch relativ große Quader und somit auch große Farbabwei-
chungen entstehen.

Octree-Algorithmus

Ahnlich wie der Median-Cut-Algorithmus basiert auch dieses Verfahren
auf der Partitionierung des dreidimensionalen Farbraums in Zellen un-
terschiedlicher Große. Der Octree-Algorithmus [28] verwendet allerdings
eine hierarchische Struktur, in der jeder Quader im 3D-Raum wiederum
aus 8 Teilquadern bestehen kann. Diese Partitionierung wird als Baum-
struktur (Octree) reprasentiert, in der jeder Knoten einem Quader ent-
spricht, der wieder Ausgangspunkt fur bis zu 8 weitere Knoten sein kann.
Jedem Knoten ist also ein Teil des Farbraums zugeordnet, der sich auf
einer bestimmten Baumtiefe d (bei einem 3

× 8-Bit-RGB-Bild auf Tiefe

d = 8) auf einen einzelnen Farbwert reduziert.
Zur Verarbeitung eines RGB-Vollfarbenbilds werden die Bildpunkte
sequentiell durchlaufen und dabei der zugehorige Quantisierungsbaum
dynamisch aufgebaut. Der Farbwert jedes Bildpixels wird in den Quan-
tisierungsbaum eingefugt, wobei die Anzahl der Endknoten auf K (ubli-
cherweise K = 256) beschrankt ist. Beim Einfugen eines neuen Farbwerts
C i kann einer von zwei Fallen auftreten:
1. Wenn die Anzahl der Knoten noch geringer ist als K und kein pas-
sender Knoten fur den Farbwert C i existiert, dann wird ein neuer
Knoten fur C i angelegt.
2. Wenn die Anzahl der Knoten bereits K betragt und die Farbe C i
noch nicht reprasentiert ist, dann werden bestehende Farbknoten auf
der hochsten Baumtiefe (sie reprasentieren nahe aneinander liegende
Farben) zu einem gemeinsamen Knoten reduziert.