Farbzellenkomprimierung - Color Cell Compression
Die Farbzellenkomprimierung ist ein verlustbehafteter Bildkomprimierungsalgorithmus , der 1986 von Campbell et al. Entwickelt wurde und als früher Vorläufer moderner Texturkomprimierungsalgorithmen wie S3 Texture Compression und Adaptive Scalable Texture Compression angesehen werden kann . Es ist eng verwandt mit Blockabkürzungscodierung , eine andere verlustbehaftete Bildkompressionsalgorithmus, der Farbzelle Compression früher in, dass sie die dominante verwendet Luminanz eines Blocks von Pixeln zu Partition die Pixel in zwei repräsentativen Farben. Der Hauptunterschied zwischen Block Truncation Coding und Farbzellenkomprimierung besteht darin, dass erstere zum Komprimieren von Graustufenbildern und letztere zum Komprimieren von Farbbildern entwickelt wurden. Außerdem erfordert die Blockabschneidungscodierung, dass die Standardabweichung der Farben von Pixeln in einem Block berechnet wird, um ein Bild zu komprimieren, während die Farbzellenkomprimierung nicht die Standardabweichung verwendet. Beide Algorithmen können jedoch ein Bild auf effektiv 2 Bit pro Pixel komprimieren.
Algorithmus
Kompression
Der Algorithmus zur Komprimierung von Farbzellen verarbeitet ein Bild in acht Schritten, obwohl einer der Schritte (Schritt 6) optional ist. Hier wird angenommen, dass die Eingabe ein 24-Bit / Pixel-Bild ist, wie im ursprünglichen Zeitschriftenartikel angenommen, obwohl andere Bittiefen verwendet werden könnten.
- Für jedes 8-Bit-RGB-Oktett-Tripel, das in jedem 24-Bit-Farbwert im Eingabebild enthalten ist, wird die NTSC- Luminanz nach der folgenden Formel berechnet:
- Das Bild wird nun in 4-Pixel- durch 4-Pixel-Blöcke unterteilt, und das arithmetische Mittel der Luminanz jedes Pixels in dem Block wird verwendet, um einen repräsentativen Luminanzwert auszuwählen.
- Jeder Pixelblock wird dann in zwei Gruppen unterteilt. Eine Gruppe besteht aus Pixeln im aktuellen Block, wobei die Luminanz jedes Pixels größer oder gleich der repräsentativen Luminanz für den aktuellen Block ist. Die zweite Gruppe von Pixeln besteht aus Pixeln im aktuellen Block, wobei die Luminanz jedes Pixels geringer ist als die repräsentative Luminanz für den aktuellen Block. Ob ein Pixel im aktuellen Block zu einer bestimmten Gruppe gehört, wird durch eine binäre "0" oder einen "1" -Wert in einer anderen separaten Bitmap mit 16 Einträgen bestimmt .
- Zwei repräsentative 24-Bit-Farben werden nun für jeden Pixelblock ausgewählt, indem zwei arithmetische Mittel berechnet werden. Das erste arithmetische Mittel ist das arithmetische Mittel aller Pixel, die zur ersten Gruppe von Pixeln gehören, wobei die Luminanz jedes Pixels eine "1" in der Luminanzbitmap ist. Die zweite repräsentative 24-Bit-Farbe wird auf ähnliche Weise ausgewählt, indem das arithmetische Mittel aller 24-Bit-Farbpixel in der zweiten Gruppe genommen wird, wobei jedes Pixel einer "0" in der Luminanzbitmap entspricht.
- Die Luminanz-Bitmap wird an einem temporären Ort gespeichert, und dann werden die zwei repräsentativen 24-Bit-Farben für den aktuellen Block an die Bitmap angehängt. Zu diesem Zeitpunkt wurde das Bild in eine Bitmap mit 16 Einträgen mit zwei angehängten 24-Bit-Binärwerten komprimiert. Die Gesamtgröße des komprimierten Blocks beträgt jetzt 16 Bit für die Luminanzbitmap und zwei 24-Bit-Binärgrößen für jede repräsentative Farbe, was eine Gesamtgröße von 64 Bit ergibt, die, geteilt durch 16 (die Anzahl der Pixel im Block) ) ergibt 4 dh 4 Bits pro Pixel.
- Jeder komprimierte Block von Pixeln ist , modifiziert durch Abschneiden jeder der beiden 24-Bit repräsentativen Farben zu 15 Bits. Dieser Schritt ist optional, und der Algorithmus kann bei Bedarf an diesem Punkt beendet werden, da die komprimierten Blöcke in diesem Stadium eine Gesamtgröße von Bits haben, die, wenn sie durch 16 geteilt werden, 2,875 Bits pro Pixel ergeben. Wenn dieser Schritt ausgeführt wird, können die 15-Bit-Farbkürzungswerte im nächsten Schritt verwendet werden, um ein kleineres Histogramm zu erstellen. Da jeder 15-Bit-Binärfarbvektor vermutlich in einem 16-Bit-Wort gespeichert ist, kann das 16. Bit verwendet werden, um die Bildqualität zu verbessern, indem angegeben wird, welche von zwei Nachschlagetabellen verwendet werden soll.
- Ein Histogramm aller 24-Bit-Farben im ursprünglichen 24-Bit-Farbbild oder der abgeschnittenen 15-Bit-Farbvektoren wird erstellt. In einer naiven Implementierung wird das Histogramm herangezogen, um 256 der am häufigsten verwendeten Farben auszuwählen, die dann in ein Array mit 256 Einträgen eingefügt werden, wobei jeder Eintrag aus drei Oktetten eines Farbwerts von 24 Bit pro Pixel besteht. Das Histogrammverfahren zum Auswählen der am besten geeigneten Farben für das ursprüngliche 24-Bit-Farbbild pro Pixel kann stattdessen durch einen Vektorquantisierungsklassenalgorithmus wie den Medianschnittalgorithmus oder das K-Mittel-Clustering ersetzt werden, das normalerweise bessere Ergebnisse liefert.
- Der letzte Schritt besteht darin, den aktuellen Pixelblock zu nehmen und zu bestimmen, welche 24-Bit-Farbe pro Pixel in der Nachschlagetabelle mit 256 Einträgen den beiden repräsentativen Farben für jeden Block am ehesten entspricht. Die beiden 8-Bit-Indizes, die auf Farben in der Nachschlagetabelle zeigen, werden jetzt an die 16-Bit-Luminanz-Bitmap angehängt. Dies ergibt eine komprimierte Gesamtgröße von Bits, die, wenn sie durch 16 geteilt werden, 2 Bits pro Pixel ergibt.
- Für jedes 8-Bit-RGB-Oktett-Tripel, das in jedem 24-Bit-Farbwert im Eingabebild enthalten ist, wird die NTSC- Luminanz nach der folgenden Formel berechnet:
Dekompression
Die Dekomprimierung ist sehr einfach und unkompliziert. Um jeden komprimierten 4-Pixel-mal-4-Pixel-Block zu rekonstruieren, wird die 16-Bit-Luminanz-Bitmap für jeden Block herangezogen. Abhängig davon, ob ein Element der Bitmap 1 oder 0 ist, wird einer der beiden 8-Bit-Indizes in der Nachschlagetabelle ausgewählt und dann dereferenziert, und der entsprechende Farbwert von 24 Bit pro Pixel wird abgerufen.
Leistung und Bildqualität
Trotz seines sehr einfachen Mechanismus liefert der Algorithmus überraschend gute Ergebnisse bei fotografischen Bildern und hat den Vorteil, dass er mit begrenzter Hardware sehr schnell decodiert werden kann. Obwohl das Komprimierungsverhältnis durch spätere Blocktransformationscodierungsverfahren wie JPEG weit übertroffen wurde , hat es den Vorteil einer sehr einfachen Dekomprimierung und eines schnellen zufälligen Zugriffs auf das komprimierte Bild.
