Compressione cella colore - Color Cell Compression

Color Cell Compression è un algoritmo di compressione delle immagini con perdita sviluppato da Campbell et al., Nel 1986, che può essere considerato un precursore dei moderni algoritmi di compressione delle texture, come S3 Texture Compression e Adaptive Scalable Texture Compression . È strettamente correlato al Block Truncation Coding , un altro algoritmo di compressione delle immagini con perdita, che precede la compressione delle celle di colore, in quanto utilizza la luminanza dominante di un blocco di pixel per partizionare detti pixel in due colori rappresentativi. La differenza principale tra Block Truncation Coding e Color Cell Compression è che la prima è stata progettata per comprimere le immagini in scala di grigi e la seconda è stata progettata per comprimere le immagini a colori. Inoltre, Block Truncation Coding richiede che la deviazione standard dei colori dei pixel in un blocco venga calcolata per comprimere un'immagine, mentre Color Cell Compression non utilizza la deviazione standard. Entrambi gli algoritmi, tuttavia, possono comprimere un'immagine fino a 2 bit per pixel.

Un primo piano di un mandrillo, con vari colori raffigurati
Immagine a colori originale non compressa a 24 bit per pixel
Immagine compressa dell'immagine di prova standard Mandrill sopra
Immagine compressa CCC, ma utilizzando solo la quantizzazione del colore da 24 bit a 15 bit combinata con una bitmap di luminanza per 2.875 bit per pixel (senza tavolozza / tabella di ricerca)
Vedi didascalia
Tavolozza a 256 voci / implementazione della tabella di ricerca dell'algoritmo CCC a 2 bit per pixel con la tavolozza costruita utilizzando il clustering K-means
Vedi didascalia
Risultato dell'output dell'immagine di prova standard Mandrill compressa con l'algoritmo CCC a 2 bit per pixel con una tavolozza / tabella di ricerca a 256 voci generata utilizzando un algoritmo di istogramma colore a 15 bit naïve

Algoritmo

Compressione

L'algoritmo di compressione della cella a colori elabora un'immagine in otto passaggi, sebbene uno dei passaggi (passaggio n. 6) sia facoltativo. Si presume qui che l'ingresso sia un'immagine a 24 bit / pixel, come ipotizzato nell'articolo originale del giornale, sebbene possano essere utilizzate altre profondità di bit .

  1. Per ogni triplo ottetto RGB a 8 bit contenuto in ogni valore di colore a 24 bit nell'immagine in ingresso, la luminanza NTSC viene calcolata utilizzando la seguente formula:
  2. L'immagine è ora suddivisa in blocchi da 4 pixel per 4 pixel e la media aritmetica della luminanza di ciascun pixel nel blocco viene utilizzata per selezionare un valore di luminanza rappresentativo.
  3. Ogni blocco di pixel viene quindi diviso in due gruppi. Un gruppo è costituito da pixel nel blocco corrente in cui la luminanza di ogni pixel è maggiore o uguale alla luminanza rappresentativa per il blocco corrente. Il secondo gruppo di pixel è costituito da pixel nel blocco corrente in cui la luminanza di ogni pixel è inferiore alla luminanza rappresentativa per il blocco corrente. Se un pixel nel blocco corrente appartiene a un certo gruppo è determinato da uno "0" binario o da un valore "1" in un'altra bitmap a 16 voci separata .
  4. Due colori rappresentativi a 24 bit vengono ora selezionati per ciascun blocco di pixel calcolando due medie aritmetiche. La prima media aritmetica è la media aritmetica di tutti i pixel appartenenti al primo gruppo di pixel in cui la luminanza di ogni pixel è un "1" nella bitmap di luminanza. Il secondo colore rappresentativo a 24 bit viene selezionato in modo simile, prendendo la media aritmetica di tutti i pixel di colore a 24 bit nel secondo gruppo in cui ogni pixel corrisponde a uno "0" nella bitmap di luminanza.
  5. La bitmap di luminanza viene memorizzata in una posizione temporanea e quindi i due colori rappresentativi a 24 bit per il blocco corrente vengono aggiunti alla bitmap. In questa fase, l'immagine è stata compressa in una bitmap a 16 voci con due valori binari a 24 bit aggiunti. La dimensione totale del blocco compresso è ora di 16 bit per la bitmap di luminanza e due quantità binarie a 24 bit per ogni colore rappresentativo, producendo una dimensione totale di 64 bit, che, se divisa per 16 (il numero di pixel nel blocco ), restituisce 4, ovvero 4 bit per pixel.
  6. Ogni blocco di pixel compresso viene modificato troncando ciascuno dei due colori rappresentativi a 24 bit a 15 bit. Questo passaggio è facoltativo e l'algoritmo può terminare a questo punto, se lo si desidera, poiché i blocchi compressi in questa fase hanno una dimensione totale di bit, che, se divisa per 16, produce 2.875 bit per pixel. Se viene eseguito questo passaggio, i valori di colore troncati a 15 bit possono essere utilizzati nel passaggio successivo per creare un istogramma più piccolo. Inoltre, poiché ogni vettore binario a colori a 15 bit è presumibilmente memorizzato in una parola a 16 bit, il sedicesimo bit può essere utilizzato per migliorare la qualità dell'immagine specificando quale delle due tabelle di ricerca deve essere utilizzata.
  7. Viene creato un istogramma di tutti i colori a 24 bit nell'immagine a colori a 24 bit originale o dei vettori di colore a 15 bit troncati. In un'implementazione ingenua, l'istogramma viene consultato per scegliere 256 dei colori usati più di frequente che vengono poi inseriti in un array di 256 voci, dove ogni voce è composta da tre ottetti di un valore di colore di 24 bit per pixel. Il metodo dell'istogramma per selezionare i colori più appropriati per l'immagine a colori originale a 24 bit per pixel può invece essere sostituito da un algoritmo di classe di quantizzazione vettoriale come l' algoritmo di taglio mediano o il clustering K-means che di solito produce risultati migliori.
  8. Il passaggio finale consiste nel prendere il blocco di pixel corrente e determinare quale colore a 24 bit per pixel nella tabella di ricerca a 256 voci corrisponde maggiormente ai due colori rappresentativi per ciascun blocco. I due indici a 8 bit che puntano ai colori nella tabella di ricerca vengono ora aggiunti alla bitmap di luminanza a 16 bit. Ciò produce una dimensione compressa totale di bit, che, se divisa per 16, restituisce 2 bit per pixel.

Decompressione

La decompressione è molto facile e diretta. Per ricostruire ogni blocco compresso di 4 pixel per 4 pixel, viene consultata la bitmap di luminanza a 16 bit per ogni blocco. A seconda che un elemento della bitmap sia 1 o 0, uno dei due indici a 8 bit nella tabella di ricerca viene selezionato e quindi dereferenziato e viene recuperato il valore di colore a 24 bit per pixel corrispondente.


Prestazioni e qualità dell'immagine

Nonostante il suo meccanismo molto semplice, l'algoritmo produce risultati sorprendentemente buoni sulle immagini fotografiche e ha il vantaggio di essere molto veloce da decodificare con hardware limitato. Sebbene sia ampiamente superato nel rapporto di compressione dai successivi metodi di codifica a trasformazione di blocchi come JPEG , ha il vantaggio di una decompressione molto semplice e di un accesso casuale veloce nell'immagine compressa.

Guarda anche

Riferimenti