Compresie de celule de culoare - Color Cell Compression

Color Cell Compression este un algoritm de compresie a imaginilor cu pierderi dezvoltat de Campbell și colab., În 1986, care poate fi considerat un precursor timpuriu al algoritmilor moderni de compresie a texturii, precum S3 Texture Compression și Adaptive Scalable Texture Compression . Este strâns legat de Block Truncation Coding , un alt algoritm de compresie a imaginilor cu pierderi, care precedă compresia celulei de culoare, prin aceea că folosește luminanța dominantă a unui bloc de pixeli pentru a partiția pixelii menționați în două culori reprezentative. Diferența principală între codarea trunchierii blocului și compresia celulelor de culoare este că prima a fost concepută pentru a comprima imaginile în tonuri de gri, iar cea de-a doua a fost concepută pentru a comprima imaginile color. De asemenea, Codarea trunchierii blocurilor necesită calcularea abaterii standard a culorilor pixelilor dintr-un bloc pentru a comprima o imagine, în timp ce Compresia celulelor color nu utilizează abaterea standard. Ambii algoritmi, totuși, pot comprima o imagine până la 2 biți pe pixel.

Un prim-plan al unei mandrine, cu diferite culori reprezentate
Imagine originală color necomprimată pe 24 de biți pe pixel
Imagine comprimată a imaginii de test standard Mandrill de mai sus
Imagine comprimată CCC, dar folosind doar cuantizarea culorilor de 24 de biți până la 15 biți, combinată cu o hartă de biți de luminanță pentru 2.875 biți pe pixel (fără paletă / tabel de căutare)
Vezi legenda
Implementare în 256 de palete / tabel de căutare a algoritmului CCC la 2 biți pe pixel cu paleta construită folosind clusterizarea K-means
Vezi legenda
Rezultatul ieșirii imaginii de test standard Mandrill comprimată cu algoritmul CCC la 2 biți pe pixel cu o paletă de 256 intrări / tabel de căutare generat folosind un algoritm naiv de histogramă de culoare pe 15 biți

Algoritm

Comprimare

Algoritmul de compresie a celulei de culoare procesează o imagine în opt pași, deși unul dintre pași (pasul # 6) este opțional. Aici se presupune că intrarea este o imagine de 24 biți / pixeli, așa cum se presupune în articolul original al jurnalului, deși ar putea fi utilizate alte adâncimi de biți .

  1. Pentru fiecare octet RGB de 8 biți triplu conținut în fiecare valoare de culoare de 24 de biți din imaginea de intrare, luminanța NTSC este calculată folosind următoarea formulă:
  2. Imaginea este acum împărțită în blocuri de 4 pixeli cu blocuri de 4 pixeli și media aritmetică a luminanței fiecărui pixel din bloc este utilizată pentru a selecta o valoare de luminanță reprezentativă.
  3. Fiecare bloc de pixeli este apoi împărțit în două grupuri. Un grup este format din pixeli în blocul curent, unde luminanța fiecărui pixel este mai mare sau egală cu luminozitatea reprezentativă pentru blocul curent. Al doilea grup de pixeli este format din pixeli în blocul curent, unde luminanța fiecărui pixel este mai mică decât luminozitatea reprezentativă pentru blocul curent. Dacă un pixel din blocul curent aparține unui anumit grup este determinat de o valoare binară "0" sau de o valoare "1" într-un alt bitmap separat, cu 16 intrări .
  4. Două culori reprezentative pe 24 de biți sunt acum selectate pentru fiecare bloc de pixeli, calculând două mijloace aritmetice. Prima medie aritmetică este media aritmetică a tuturor pixelilor care aparțin primului grup de pixeli unde luminanța fiecărui pixel este un „1” în harta de biți de luminanță. A doua culoare reprezentativă pe 24 de biți este selectată în mod similar, luând media aritmetică a tuturor pixelilor de culoare pe 24 de biți din al doilea grup în care fiecare pixel corespunde unui "0" în harta de biți de luminanță.
  5. Bitmap-ul luminanței este stocat într-o locație temporară și apoi cele două culori reprezentative de 24 de biți pentru blocul curent sunt adăugate bitmap-ului. În această etapă, imaginea a fost comprimată într-un bitmap de 16 intrări, cu două valori binare de 24 de biți adăugate. Dimensiunea totală a blocului comprimat este acum de 16 biți pentru bitmap de luminanță și două cantități binare de 24 de biți pentru fiecare culoare reprezentativă, obținând o dimensiune totală de 64 de biți, care, atunci când este împărțită la 16 (numărul de pixeli din bloc ), produce 4 adică 4 biți pe pixel.
  6. Fiecare bloc comprimat de pixeli este modificat prin trunchierea fiecăreia dintre cele două culori reprezentative de 24 de biți la 15 biți. Acest pas este opțional, iar algoritmul se poate termina în acest moment, dacă se dorește, deoarece blocurile comprimate în această etapă au o dimensiune totală de biți, care, atunci când este împărțit la 16, produce 2.875 biți pe pixel. Dacă se efectuează acest pas, atunci valorile de culoare trunchiate pe 15 biți pot fi utilizate în pasul următor pentru a crea o histogramă mai mică. De asemenea, deoarece fiecare vector de culoare binară pe 15 biți este probabil stocat într-un cuvânt pe 16 biți, atunci bitul 16 poate fi utilizat pentru a îmbunătăți calitatea imaginii specificând care dintre cele două tabele de căutare ar trebui să fie utilizate.
  7. Se creează o histogramă a tuturor culorilor pe 24 de biți din imaginea color originală pe 24 de biți sau a vectorilor de culoare trunchiată pe 15 biți. Într-o implementare naivă, histograma este consultată pentru a alege 256 dintre culorile cele mai frecvent utilizate, care sunt apoi introduse într-o matrice de 256 de intrări, unde fiecare intrare constă din trei octeți cu o valoare a culorii de 24 de biți pe pixel. Metoda histogramei de selectare a culorilor cele mai potrivite pentru imaginea de culoare originală pe 24 de biți pe pixel poate fi în schimb înlocuită cu un algoritm de clasă de cuantificare vectorială, cum ar fi algoritmul de tăiere mediană sau gruparea K-mijloace, care de obicei dă rezultate mai bune.
  8. Pasul final constă în luarea blocului curent de pixeli și determinarea culorii pe 24 de biți pe pixel din tabelul de căutare cu 256 de intrări care se potrivește cel mai bine cu cele două culori reprezentative pentru fiecare bloc. Cei doi indici de 8 biți care indică culorile din tabelul de căutare sunt acum adăugați la harta de biți de luminanță de 16 biți. Aceasta produce o dimensiune totală comprimată de biți, care, atunci când este împărțită la 16, produce 2 biți pe pixel.

Decompresie

Decompresia este foarte ușoară și simplă. Pentru a reconstrui fiecare bloc comprimat de 4 pixeli cu 4 pixeli, este consultată harta de biți de luminanță pe 16 biți pentru fiecare bloc. În funcție de faptul dacă un element al bitmap-ului este 1 sau 0, este selectat unul dintre cei doi indici de 8 biți din tabelul de căutare și apoi dereferențiat și se recuperează valoarea corespunzătoare a culorii de 24 de biți pe pixel.


Performanță și calitate a imaginii

În ciuda mecanismului său foarte simplu, algoritmul dă rezultate surprinzător de bune la imaginile fotografice și are avantajul de a fi foarte rapid de decodat cu hardware limitat. Deși a fost mult depășit în raportul de compresie prin metode de codificare ulterioare bloc-transformare, cum ar fi JPEG , are avantajul unei decompresii foarte simple și a accesului rapid aleatoriu la imaginea comprimată.

Vezi si

Referințe