Farbbilder - Digitale Bildverarbeitung - page 287

b) jeden der ursprunglichen Farbwerte C i durch einen der neuen Farb-
vektoren C j zu ersetzen,
wobei n meist vorgegeben ist und die resultierende Abweichung ge-
genuber dem Originalbild moglichst gering sein soll. Dies ist allerdings
ein kombinatorisches Optimierungsproblem mit einem ziemlich großen
Suchraum, der durch die Zahl der moglichen Farbvektoren und Farbzu-
ordnungen bestimmt ist. Im Allgemeinen kommt daher die Suche nach
einem globalen Optimum aus Zeitgrunden nicht in Frage und alle nach-
folgend beschriebenen Verfahren berechnen lediglich ein ” lokales“ Opti-
mum.

12 Farbbilder

Populosity-Algorithmus

Der Populosity-Algorithmus 24 [35] verwendet die n haufigsten Farbwerte
eines Bilds als reprasentative Farbvektoren C . Das Verfahren ist einfach

zu implementieren und wird daher haufig verwendet. Die Ermittlung der
n haufigsten Farbwerte ist uber die in Abschn. 12.4.1 gezeigte Methode
moglich. Die ursprunglichen Farbwerte C i werden dem jeweils nachstlie-
genden Reprasentanten in C zugeordnet, also jenem quantisierten Farb-

wert mit dem geringsten Abstand im 3D-Farbraum.
Das Verfahren arbeitet allerdings nur dann zufrieden stellend, solange
die Farbwerte des Bilds nicht uber einen großen Bereich verstreut sind.
Durch vorherige Gruppierung ahnlicher Farben in großere Zellen (durch
skalare Quantisierung) ist eine gewisse Verbesserung moglich. Allerdings
gehen seltenere Farben - die fur den Bildinhalt aber wichtig sein konnen
- immer dann verloren, wenn sie nicht zu einer der n haufigsten Farben
ahnlich sind.

Median-Cut-Algoritmus

Der Median-Cut-Algorithmus [35] gilt als klassisches Verfahren zur Far-
bquantisierung und ist in vielen Programmen (u. a. auch in ImageJ) im-
plementiert. Wie im Populosity-Algorithmus wird zunachst ein Histo-
gramm der ursprunglichen Farbverteilung berechnet, allerdings mit ei-
ner reduzierten Zahl von Histogrammzellen, z. B. 32

32. Dieser
Histogrammwurfel wird anschließend rekursiv in immer kleinere Quader
zerteilt, bis die erforderliche Anzahl von Farben ( n ) erreicht ist. In je-
dem Schritt wird jener Quader ausgewahlt, der zu diesem Zeitpunkt die
meisten Bildpunkte enthalt. Die Teilung des Quaders erfolgt quer zur
langsten seiner drei Achsen, sodass in den restlichen Halften gleich viele
Bildpunkte verbleiben, also am Medianpunkt entlang dieser Achse (Abb.
12.30).

× 32 ×

24 Manchmal auch als ” Popularity“-Algorithmus bezeichnet.