Farbreduktion: Der Median-Cut-Algorithmus
In der April-Ausgabe 1993 hatte ich mich bereits zum Thema Farbreduktion ausgelassen. Damals erklärte ich den Floyd-Steinberg-Algorithmus, mit dem Farbfehler über das gesamte Bild verteilt und so ausgeglichen werden. Nun wäre es natürlich sinnvoll, diese Farbfehler von vornherein möglichst gering zu halten, indem man die Farbpalette an das darzustellende Bild anpaßt. Genau hier setzt der Median-Cut-Algorithmus an.
Ein True-Color-Bild wird niemals 16 Millionen Farben benutzen. Es wäre zwar bei einem großen Bild (mind. 4096 x 4096) möglich, doch können wir bei einem natürlichen Bild davon ausgehen, daß es sich auf einige wenige Farben beschränkt. Wenn wir ein Bild von einem Gesicht haben, werden da z.B. nicht sonderlich viele Grüntöne enthalten sein -zumindest nicht, wenn sich der Besitzer des Gesichts einigermaßen gut gefühlt hat. Nach dieser Überlegung sollte es also möglich sein, die wichtigsten Farben herauszusuchen - oder -suchen zu lassen. Wie erkläre ich aber jetzt dem Computer, welche Farben für die Darstellung eines Bildes wichtig sind?
RGB-Histogramm
Zunächst sollten wir mal eine Häufigkeitsverteilung der im Bild vorkommen-denFarben ermitteln. Eine derartige Häufigkeitsverteilung nennt man Histogramm. Eiie Farbe setzt sich aus den Komponenten Rot, Grün und Blau zusammen. Die i Vitensität der einzelnen Grundfarben, also Mischungsverhältnis, bestimmt die resilierende Farbe (z.B. für Gelb: 100% 1994nteil, 100% Grünanteil und O% Blau-Anteil).
Drei bestimmende Komponenten für eine Farbe, das kommt einem doch besannt vor. Wenn man sich das geometrisch vorstellt, wird ein Punkt (die Farbe) von drei Achsen bestimmt, nämlich Rot (x- Achse), Grün (y-Achse) und Blau (z-Achse). Die Farbe entspricht also einem Punkt in einem dreidimensionalen Raum. Man spricht deshalb auch von dem Farbraum oder RGB-Würfel (s. Bild 1).
Bei einem 24-Bit-True-Color-Bild steht für die Intensität der Grundfarben je ein Byte zur Verfügung. Die Intensität läßt sich also in einem Bereich von 0 bis 255 einstellen. Um die Farben zu zählen, legen wir uns ein dreidimensionales Array an, bei dem die Position im Array dem Mischverhältnis der Farbe entspricht. Da wir evtl. recht viele Punkte zählen müssen, ist jeder Eintrag in diesem Array vom Typ LONG. Wenn man jetzt den Speicherbedarf für ein solches Array berechnet, kommt man auf 64 Megabyte. Das ist ein bißchen zuviel. Wenn wir aber für jede Grundfarbe nur 5 Bit, also Werte von 0 bis 31, zulassen, kommen wir auf 128 Kilobyte. Das ist machbar, und der Qualitätsverlust ist nicht besonders groß.
Quantität ist nicht gleich Qualität
So, jetzt wissen wir, welche Farben in dem Bild am häufigsten vorkommen. Nun könnte man ja einfach die Farben ihrer Häufigkeit nach sortieren und die Farben, die am meisten vorkommen, setzen. Wie die vorsichtige Formulierung schon ahnen läßt, ist das nicht der Weisheit letzter Schluß. Warum nicht?
Nehmen wir wieder unser Beispiel von dem Bild eines Gesichts. Es wird eine hohe Häufigkeit von Orangetönen haben. Vermutlich werden die Orangetöne so weit dominieren, daß die häufigsten Farben sich nicht sonderlich unterscheiden werden. Wir haben also, sagen wir mal, 16 fein abgestufte Orangetöne, mit denen wir die samtweiche Haut in allen Details darstellen können. Nun hat aber gerade dieses Gesicht ganz markante grüne Augen. Da Augen aber nicht so groß sind, der Grünanteil des Gesamtbildes also sehr gering ist, haben wir nur die Orangetöne, um sie darzustellen. Die Augen verlieren ihre Farbe. Wie man also sieht, sind die häufigsten Farben nicht zwingend die wichtigsten. Doch wie bringen wir dem Computer unser Ästhetikempfinden nahe?
Median-Cut
Die Idee ist, den RGB-Würfel in so viele Quader zu unterteilen, wie Farben zur Verfügung stehen. Bei der Bestimmung dieser Quader sollen die Häufigkeit und die Entfernung der Farben voneinander, also die Ähnlichkeit der Farben, eine Rolle spielen. Damit müßte man dann eine recht gleichmäßige Verteilung der Farben erreichen können, und unsere grünen Augen kämen auch zu ihrem Recht. Doch nun zur Praxis:
Zunächst muß die Häufigkeitsverteilung der Farben des Bildes, also das Histogramm, ermittelt werden. Das haben wir ja bereits gemacht. Dann wird der RGB-Würfel auf die tatsächlich vorkommenden Extrema geschrumpft. Man kann sich das etwa so vorstellen wie die Müllpresse in Krieg der Sterne". Die Wände des Würfels wandern so lange nach innen, bis sie im Histogramm auf eine Farbe stoßen. Dadurch erhält man den kleinstmöglichen RGB-Quader, der alle vorkommenden Farben enthält. Wir haben also schon einmal unnötigen Ballast abgeworfen, den wir zur Farbermittlung nicht brauchen.
Dann suchen wir nach der längsten vorkommenden Kante. Ich habe dies deshalb so allgemein formuliert, weil wir später mehrere RGB-Quader haben werden und alle Kanten in die Suche einbezogen werden. An dieser Kante wird nun der Quader in zwei Teile geteilt. Da wir die längste Kante nehmen, erfüllt dieser Schritt die Forderung nach der Berücksichtigung des Farbabstandes. Wir erreichen damit, daß nachher nicht eine Farbe ein zu breites Spektrum abdecken muß - die Verteilung wird ausgewogen. Die Teilung soll so geschehen, daß beide Teile etwa gleich viele Punkte enthalten. Dadurch, daß nicht in der Kantenmitte geteilt wird, sondern die Farbhäufigkeit berücksichtigt wird, erreichen wir eine feinere Unterteilung der häufigeren Farben. Die Pfirsichhaut bleibt also eine Pfirsichhaut.
Diese beiden Teilquader werden jetzt wieder auf ihre Extrema geschrumpft, und die Prozedur fängt wieder von vorne an. So erhalten wir pro Durchgang einen neuen RGB-Quader. Dies wiederholt sich, bis man so viele Quader hat, wie einem Farben zur Verfügung stehen. Der ursprüngliche RGB-Würfel ist jetzt unter Berücksichtigung der Häufigkeiten und der Farb-abstände in so viele Teilquader segmen-tiert, wie uns Farben zur Verfügung stehen, und das ist genau das, was wir erreichen wollten. Jetzt müssen aus den Teilquadern nur noch die Farben ermittelt werden. Hierzu werden die in dem Quader vorkommenden Farben gemäß ihrer Häufigkeit gemittelt. Hier haben wir nochmals eine Berücksichtigung der Farbhäufigkeit. Nun sollte der Darstellung nichts mehr im Wege stehen.
Das Programm...
... ist in Pure C 1.1 geschrieben, sollte sich aber ohne Probleme auf andere ANSI-C-Compiler übertragen lassen. Zunächst ermittelt das Programm das Histogramm des Bildes. Hierzu werden die je acht Bit pro Farbanteil auf höchstens fünf Bit reduziert. Da es ziemlich unsinnig ist, eine Einstellungsmöglichkeit für 32768 Farben zu suchen, wenn die Hardware nur z.B. 4096 Einstellungen unterstützt, wird zunächst das Auflösungsvermögen der Farbpalette ermittelt. Daraus resultieren dann die tatsächlichen Dimensionen des Histogramms. (Auf einem STE wären also die Dimensionen je 4 Bit für Rot, Grün und Blau.) Ein erfreulicher Effekt hiervon ist, daß das Programm auch auf dem ST recht schnell läuft, da die zu bearbeitende Datenmenge gering gehalten wird.
Dann folgt auch schon der eigentliche Median-Cut-Algorithmus. Dieser wird von der Funktion median_cut durchgeführt. Die Parameter hierbei sind:
vdi_handle
das Handle der VDI-Workstation
colors
Anzahl der zur Verfügung stehenden Farben
hist[]
Zeiger auf das Histogramm
col_tbl[]
Hier steht nach dem Aufruf die ermittelte Farbpalette. Die Größe des
Arrays muß colors * 3 Worte sein. Sollten die Farben gesetzt werden,
entsprechen die Positionen der Farben in dem Array dem korrespondierenden
VDI-Farbindex. Für nicht gesetzte Farben steht dann eine -1 in Rot-, Grün-
und Blauanteil.
basis
Hier steht das Wertesystem, auf das sich die Einträge in col_tbl beziehen
sollen. Dies wäre z.B. 1000 für VDI (0-1000) oder 255 (0-255) für die
meisten anderen Formate.
flag
Steht hier der Wert 1 (SET_COLORS), so werden die ermittelten Farben
gleich in der aktuellen Farbpalette gesetzt. Hierzu findet ein Vergleich
mit den bisher eingestellten Farben statt, so daß die Änderungen möglichst
gering ausfallen. Steht hier eine 2 (SET_HIST), so werden die
eingestellten Farben zusätzlich im Histogramm gesetzt. Der Vorteil hierbei
ist, daß beim Zeichnen des Bildes die für den RGB-Wert entsprechenden
Farben aus diesem Array ausgelesen werden können und nicht immer neu
berechnet werden müssen.
Tel 1 block 1
paljn[]
In diesem Array stehen die Werte zur Beschaffenheit der Farbpalette. Das Array wird intern zur Berechnung der Farben benötigt. Zurück gibt die Funktion die Anzahl der eingestellten Farben oder FALSE im Fehlerfall.
Was in dem Programm auffällt, ist vielleicht die Tatsache, daß ich die überflüssigen Bits der RGB-Werte nicht einfach mit einer Shift-Operation ausblende, sondern recht umständlich mit Integer- divisionen und -multiplikationen die neuen RGB-Werte berechne. Dies geschieht, damit der Rundungsfehler bei der Berechnung der Farben möglichst gering bleibt.
Schlußbemerkungen
Das Anpassen der Farbpalette mit dem Median-Cut-Algorithmus ist in Kombination mit dem Floyd-Steinberg-Algorith-mus eine Methode der Farbreduktion, die sehr befriedigende Ergebnisse erzielt. Wenn man die beiden Algorithmen miteinander kombiniert, sollte man allerdings das True-Color-Bild auf nicht weniger als 5 Bit pro Grundfarbe reduzieren, damit bei der Weiterverarbeitung mit dem Floyd-Steinberg-Algorithmus keine allzu gravierenden Rundungsfehler bei der Farbfehlerverteilung auftreten.
Die Darstellung mit diesen beiden Algorithmen ist recht zeitaufwendig und sollte deshalb nur zur endgültigen Umwandlung benutzt werden. Ansonsten müßten die beiden Algorithmen nach jeder Veränderung des Bildes neu angewandt werden. Wichtig ist hierbei auch, daß ein so berechnetes Bild sich nicht ohne erheblichen Informationsverlust in ein True-Color-Bild zurückwandeln läßt. Das entstandene Bild ist also kein Ersatz für das Original.
med_cut.zipThomas Schutt