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?
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.zip