Quantizzazione vettoriale ottimizzata per immagini CFA

Un algoritmo di compressione che agisca direttamente sui dati in formato Bayer Pattern Ł
utile in quanto permette un piø agevole trasferimento degli stessi al decodificatore,
rimandandone l interpolazione alla fase finale di decodifica. Inoltre, poichØ i dati cos 
compressi sono soggetti ad ulteriori elaborazioni, la perdita di informazione in questa fase
deve essere minimizzata, anche al costo di un bit-rate maggiore.
Il metodo di compressione descritto in questa tesi Ł ideato per operare su un flusso di dati in
formato Bayer Pattern da codificare mediante quantizzazione vettoriale.
La quantizzazione vettoriale Ł una tecnica di compressione lossy che approssima i dati
contenuti nell immagine mediante l uso di un insieme di campioni chiamato codebook.
Normalmente, l immagine viene letta in blocchi di pixel contigui rappresentabili come vettori
a piø dimensioni e approssimati da un vettore del codebook. Per una normale immagine RGB
(Red Green Blue), ciascun piano di colore Ł sottoposto ad una quantizzazione indipendente.
Per un flusso di dati in formato Bayer Pattern, Ł piø conveniente quantizzare blocchi di pixel
con lo stesso colore.
La ridotta dimensione del codebook determina una compressione dell immagine perchØ il
numero di bit necessari per rappresentare gli elementi del nuovo alfabeto risulta diminuito.
La differenza di valore tra un blocco dell immagine e il vettore usato per rappresentarlo viene
detta errore di quantizzazione e costituisce la causa del degrado dell immagine compressa.
Per limitare al massimo l errore di quantizzazione e la sua percezione dal sistema visivo
umano, occorre scegliere un codebook con un numero sufficiente di campioni. Inoltre, la
concentrazione dei campioni dovrebbe essere maggiore nelle aree dell immagine dove
l errore Ł piø frequente e meglio percepito.
Gli algoritmi di quantizzazione vettoriale piø diffusi individuano il codebook i cui elementi
approssimano meglio i vettori che formano l immagine al fine di mantenere l errore di
quantizzazione al di sotto di una soglia di tolleranza. Questo procedimento che garantisce
l ottimalit  dei campioni usati per la quantizzazione, Ł computazionalmente complesso e
quindi difficilmente integrabile su un sistema reale. Un ulteriore aspetto da considerare nella
progettazione di un quantizzatore vettoriale Ł che il modello matematico non sempre coincide
con il modello percettivo. Una valutazione prettamente matematica dell errore di
quantizzazione potrebbe quindi non rispecchiare il modo in cui lo stesso errore viene
percepito dal sistema visivo.
L obiettivo che si Ł voluto perseguire con il presente lavoro Ł stato individuare un codebook
pseudo ottimale per due categorie di immagini: naturali e di testo.
Un sistema simile presuppone l esistenza di un classificatore automatico per le immagini di
tipo testo [2] in grado di scegliere il codebook piø adatto ad ogni specifico caso.
Un alternativa, potrebbe essere la visualizzazione di una anteprima dell immagine non ancora
decodificata per dare all osservatore la possibilit  di valutare la soluzione di quantizzazione
piø idonea.
1.1 Entropia e modelli di sorgente
Ogni processo che genera informazione pu  essere visto come una sorgente che emette una
sequenza di simboli scelti in un alfabeto finito. Questa idea del tutto generale Ł applicabile
anche alle immagini digitali e si pu  pertanto pensare di utilizzare la teoria dell informazione
per misurare la quantit  d'informazione associata ad una generica immagine. Tale quantit 
rappresenter  un limite massimo per la compressione lossless.
La forma piø semplice di sorgente d informazione Ł la sorgente discreta senza memoria
(DMS). Essa prevede un alfabeto sorgente con un numero finito di simboli, ciascuno dei quali
pu  essere emesso senza dipendere da nessuno dei simboli precedenti.
Per caratterizzare completamente una sorgente di questo tipo, oltre all alfabeto, si devono
conoscere le probabilit  di emissione dei simboli:
{ }
n
sssS ,...,,
21
= alfabeto sorgente
)(),...,(),(
21 n
spspsp probabilit  dei simboli
Per determinare la quantit  d informazione generata dalla sorgente, si introduce la funzione
entropia (o incertezza) che Ł cos  definita:
)(log)()(
1
2 i
n
i
i
spspSH


=
−= (1.1)
Nel caso di una sorgente senza memoria che emette periodicamente un simbolo s
i
 con
probabilit  p(s
i
) la formula (1.1) Ł massima nel caso di equiprobabilit  dei simboli e decresce
con l'aumentare della differenza tra le p(s
i
). Quando la sorgente emette un solo simbolo s
1
 con
probabilit  p(s
1
) = 1, l'entropia vale zero. Tutto ci  rispecchia l idea intuitiva di contenuto
informativo.
Nel rumore bianco, l entropia Ł massima perchØ in ogni istante il valore emesso Ł un dato
informativo a sØ stante, scorrelato da tutti gli altri.
Per il primo teorema di Shannon, il numero minimo n di bit necessari per codificare ogni
simbolo Ł:
Capitolo I
Compressione di immagini digitali
1)()( +≤≤ SHnSH (1.2)
La (1.2) indica che il numero minimo di bit occorrenti per interpretare senza equivoci ogni bit
della sorgente Ł compreso tra l entropia e il piø piccolo numero intero maggiore dell entropia.
Questo limite teorico rappresenta il minimo bit-rate raggiungibile da qualsiasi metodo di
compressione lossless.
Prestazioni migliori possono essere raggiunte utilizzando una nuova sorgente estensione della
sorgente originale che raggruppi alcuni simboli per formare delle parole. Assegnando codici
piø brevi alle parole piø frequenti si ottiene:
N
SH
N
n
SH
SNHSH
N
1
)()(
)()(
+≤≤
=
(1.3)
dove n rappresenta il numero di simboli generati dalla sorgente originale ed N Ł la lunghezza
di una parola nella sorgente estensione.
La relazione (1.3) mostra che un N abbastanza grande permette di raggiungere un fattore di
compressione vicino all entropia.
Le sorgenti DMS sono troppo restrittive in molte applicazioni reali. In generale, una parte di
messaggio pu  influenzare pesantemente le probabilit  d emissione del simbolo successivo.
In questi casi, si parla di sorgente con memoria modellabile mediante una sorgente di
Markov.
In una sorgente di Markov di ordine m, la probabilit  di occorrenza di un simbolo s
i
 dipende
da un numero m finito di uscite precedenti  (m = 0 Ł il caso di una sorgente senza memoria).
Per tutte le coppie di simboli (i, j) in un dato alfabeto S, una sorgente Markoviana del primo
ordine (m = 1) richiede la conoscenza delle probabilit  condizionate )|( jip  di uscita del
simbolo i data l uscita del simbolo j.
Una sorgente si dice ergodica quando le probabilit  di uscita dei vari simboli rimangono
stazionarie, ovvero costanti nel tempo. Generalmente, le immagini non sono sorgenti
ergodiche ma possono essere approssimate come tali.
Quindi, la probabilit  di uscita di un simbolo Ł condizionata dallo stato raggiunto dalla
sorgente Markoviana dopo l uscita di m simboli precedenti.
Una sorgente Markoviana del primo ordine pu  trovarsi in n stati diversi, uno per ogni
simbolo dell'alfabeto. In generale, una sorgente Markoviana di ordine m pu  trovarsi in n
m
possibili stati.
L entropia di una sorgente Markoviana Ł quantificabile mediante la funzione:


=
−=
n
i
jmjijmjijmjj
ssspssspsssSH
1
12121
),...,|(log),...,|(),...,,|( (1.4)
L entropia espressa dalla (1.4) Ł inferiore a quella della (1.1) perchØ una sorgente con
memoria riduce il contenuto di informazione.
Per una sorgente Markoviana estesa ad una sorgente con gruppi di simboli, l entropia Ł
espressa come nella (1.3) e la (1.2) diventa:
ξ+≤≤ )()( SH
N
n
SH (1.5)
con ξ piccolo a piacere a patto di aumentare l estensione della sorgente.
1.2 Stima dell entropia
Un problema molto comune Ł quello di determinare quanto si possa comprimere una data
immagine senza perdere informazione. La risposta teorica a questa domanda Ł fornita dal
primo teorema di Shannon (o della codifica senza rumore) che fissa come limite minimo del
bit-rate l entropia dell immagine stessa. Dunque, occorre determinare tale grandezza.
Un approccio abbastanza intuitivo per stimare l entropia Ł l utilizzo di modelli per
caratterizzare la sorgente e cercare l entropia sulla base del modello appropriato. Un
modellamento accurato Ł essenziale in ogni schema di compressione poichØ i limiti delle
performance sono fissati dall entropia calcolata secondo quel modello. L efficienza di un
modello dipende da quanto accuratamente esso Ł in grado di prevedere le probabilit  dei
simboli. Nelle informazione di tipo  naturale  come le immagini, i modelli piø complessi
sono capaci di descrivere la struttura corrente della sorgente offrendo basse entropie ed
elevate compressioni.
Un altro approccio per stimare l entropia Ł quello di segmentare l immagine in blocchi di
dimensione N ed utilizzare la frequenza delle occorrenze di ogni blocco per misurarne le
probabilit . Sfortunatamente, la convergenza dell entropia stimata verso il valore reale Ł lenta
e richiede l uso di grossi valori di N allo scopo di ridurre il numero di combinazioni.
Per verificare l impatto del modello di sorgente sul valore dell entropia, si consideri una
sorgente ergodica S, come l alfabeto di una lingua parlata costituito da 22 simboli.
Nell ipotesi che la sorgente S sia senza memoria e con simboli equiprobabili, l entropia vale:
459.422log)(
2
==SH
Per rendere il modello piø reale, si pu  considerare una sorgente senza memoria con una
stima della probabilit  di ogni lettera ottenuta leggendo un brano (il risultato dell esperimento
dipende dal testo e dal lettore).  Cos  facendo, si ha:
97.3)( =SH
Un altro modello potrebbe essere una sorgente Markoviana di ordine uno con la stima di tutte
le possibili 22*22 probabilit  condizionate. In questa ipotesi:
27.3)( =SH
L entropia tende ad abbassarsi man mano che il contenuto di informazione della sorgente
viene trasferito sul modello adoperato.
Si pu  anche pensare di cambiare totalmente approccio nel tentativo di calcolare l entropia
della lingua parlata. L idea, dovuta a Shannon, Ł quella di cancellare alcune lettere a caso da
un testo. Quindi, si contano i tentativi che occorre fare per indovinare quali lettere mancano e
si fa ripetere l esperimento ad un certo numero di persone. Si Ł concluso che per la lingua
parlata si ha:
3.1)(6.0 << SH
Per la lingua parlata, l entropia non Ł assoluta, ma cambia a seconda della persona che scrive
o che legge.
Per applicare l approccio di Shannon alle immagini, si prenda un immagine di 128 x 128
pixel a 16 livelli di colore e si cancellino alcuni punti. Quindi, viene chiesto ad un osservatore
di ripristinare i livelli dei pixel originali attraverso un computer. L osservatore utilizzer  una
palette con vari livelli di grigio per indovinare il valore mancante su ciascun pixel. Un
indicatore segnala all osservatore le scelte sbagliate affinchØ non possa ripetere gli errori.
L esperimento viene ripetuto 100 volte e viene disegnato un istogramma del numero delle
risposte corrette. Mediante l utilizzo dei limiti dell entropia dovuti a Shannon il risultato di
questo esperimento su 14 immagini ha evidenziato una ridondanza variabile tra il 46% e il
74%. Tuttavia, questo risultato Ł meno attendibile rispetto all esempio del testo perchØ
l occhio umano tende ad integrare le zone omogenee. L esperienza indica un risultato attorno
al 50%.
1.3 Teoria della distorsione
In molti casi pratici, un certo degrado irreversibile dell immagine pu  essere tollerato. Il
livello di degrado Ł solitamente controllato dall utente attraverso l impostazione di un
opportuno insieme di parametri.
Di particolare rilevanza rimane comunque la determinazione del minimo bit-rate necessario
per mantenere il degrado sotto un certo livello. Di questo problema si occupa una branca della
teoria dell informazione conosciuta come teoria della distorsione. La teoria della distorsione
stabilisce dei limiti teorici per le prestazioni delle compressioni lossy nel rispetto di opportuni
criteri di fedelt . I parametri fondamentali di valutazione sono:
D distorsione (in genere errore quadratico medio)
R bit-rate della codifica
La funzione R(D) in figura 1.1 esprime il bit-rate raggiungibile in presenza di una data
distorsione D, e soddisfa le seguenti condizioni:
• Per ogni dato livello di distorsione D Ł possibile trovare uno schema di codifica con un
bit-rate arbitrariamente vicino a R(D) e distorsione media arbitrariamente vicina a D;
• ¨ impossibile trovare un codice che raggiunga una riproduzione con distorsione D (o
migliore) ad una rate al di sotto di R(D).
Fig. 1.1   Funzione rate-distorsion.
Si evince cioŁ che esiste un limite teorico per la codifica con perdita. Il minimo bit-rate
richiesto per una compressione libera da distorsioni Ł il valore che R assume in D = 0  ed Ł
minore o uguale all entropia della sorgente a seconda di come viene misurata la distorsione.
Per caratterizzare la funzione R(D) occorrono un modello e un criterio di distorsione. Il
problema diventa trattabile matematicamente se la sorgente Ł modellabile come una DMS e la
misura di distorsione Ł context free ed ha forma semplice. Una misura context free implica
che la distorsione Ł funzione del valore originale e del suo valore riprodotto e non dipende
dagli altri termini nella sequenza e dalla loro riproduzione.
Si definisce root mean square error (RMSE) la quantit :
RMSE
N
f i j f i j
i
N
i
N
= −
==



1
2
2
11
[ ( , )


( , )] (1.6)
che rappresenta una misura della differenza tra gli 
2
N  valori ),( jif  della sorgente e le loro
riproduzioni ),(
 
jif .
Per una sorgente con valore massimo 255, si definisce rapporto segnale di picco rumore
(PSNR   Peak Signal to Noise Ratio) il numero:






=
RMSE
PSNR
255
log10
10
(1.7)
Un altra misura di distorsione basata sulla differenza tra il segnale e la sua riproduzione Ł il
rapporto segnale rumore (SNR   Signal to Noise Ratio):
[ ]














−
=






= =
= =
N
i
N
j
N
i
N
j
jifjif
jif
SNR
1 1
2
1 1
2
10
),(
 
),(
),(
log10 (1.8)
Queste quantit  che si esprimono in dB (decibel) rappresentano una misura puntuale della
distorsione. L obiettivo di un qualunque metodo di compressione lossy Ł quello di
minimizzare RMSE o, equivalentemente, massimizzare PSNR ed SNR.
1.4 Tecniche di compressione: un overview
Il primo teorema di Shannon fornisce una stima del limite teorico di compressione senza
rivelare alcun dettaglio su come raggiungerlo.
Per ottenere un buon fattore di compressione, Ł necessario rappresentare i simboli della
sorgente attraverso degli opportuni codici binari. Limiteremo il nostro interesse ai codici
unicamente decifrabili (che non sono prefissi di altri codici) ed istantanei (che permettono
la decodifica senza dovere aspettare le prossime parole di codice).
Due tecniche di codifica molto note sono quella di Shannon - Fano e quella di Huffman. La
lunghezza media di un codice nella codifica di Shannon Fano non Ł in generale ottima e vale
)(log
2 i
sp− . La codifica di Huffman, al contrario, offre sempre il risultato migliore.
1.4.1 Codifica di Huffman
La codifica di Huffman Ł uno standard ISO [43] per la compressione di immagini come
sequenza di livelli di grigio.
Questo metodo statistico di compressione Ł basato sulla constatazione che, di norma,
l istogramma dei livelli di grigio non Ł completamente piatto.
Quando l istogramma dell immagine Ł piatto, il metodo di codifica piø adatto consiste
nell assegnazione di un codice binario della stessa lunghezza a tutti i pixel. PoichØ ogni valore
Ł ugualmente probabile, assegnare lo stesso numero di bit a tutti i pixel rende semplice la
codifica dell immagine.
Una immagine VGA con 640 x 480 pixel a 16 livelli di colore richiede
4 x 640 x 480 = 150 Kb di memoria.
Tuttavia, se Ł noto che su 16 livelli di colore, quattro vengono usati nel 60% dei pixel, altri
quattro nel 30% dei casi e i rimanenti nel 10% dei casi, allora si potrebbe per esempio usare il
seguente sistema di codifica:
Per i quattro colori piø frequenti:
000
001
010
011
Per i successivi quattro colori:
1000
1001
1010
1011
Per i rimanenti colori:
11000
11001
11010
11011
11100
11101
11110
11111
Questo significa che la lunghezza dell immagine originale (150 Kb) diventa:
[ ]
Kb
xx
xxxxx
25.131
4806405.3
480640)5.02.18.1(
480640)51.0()43.0()36.0(
=++
=++
=++
La lunghezza media di un valore Ł stata ridotta da 4 a 3.5 bit, nonostante alcuni pixel usino un
valore a 5 bit.
Pu  essere dimostrato che per codificare M livelli di grigio rispettivamente con probabilit 
110
,...,,
−M
ppp , il numero di bit richiesti Ł almeno pari a:


−
=
−
1
0
log
M
i
ii
pp
Formalmente, l algoritmo di Huffman Ł composto dai seguenti passi:
1. Ordinare i livelli di grigio in base alla loro frequenza di uso (probabilit  di occorrenza).
2. Combinare i due livelli di grigio meno usati in un gruppo con frequenza pari alla somma
delle frequenze dei due livelli e riordinare i livelli di grigio.
3. Iterare il passo 2. finchØ non rimangono due soli livelli di grigio.
4. Allocare uno 0 per il primo livello di grigio e un 1 per l altro, poi tornare indietro nei
raggruppamenti precedenti in modo che se un gruppo con codice  ccc  Ł ottenuto
combinandone altri due, il codice del primo sottogruppo Ł  ccc0  e quello del secondo Ł
 ccc1 .
Esempio:
la tabella 1.1 mostra come funziona questo metodo su un sistema di nove livelli. Il
risultato Ł:
Livello Codice
0 100000
1 10001
2 101
3 001
4 11
5 01
6 000
7 1001
8 100001
Lo spazio di memorizzazione Ł ridotto da 19000 x 3 = 57000 bits a 51910 bits.
In questo caso, il risparmio non Ł grande, ma se i livelli di grigio fossero 256 e l istogramma
fosse distante dal livellamento, allora il risparmio sarebbe notevole.
Esistono altri sistemi di codifica statistica, come i B-codes, ma la lunghezza media dei loro
codici Ł maggiore di quella del codice di Huffman.
La codifica di Huffman non Ł comunque esente da problemi: la sua efficienza viene a
decrescere in presenza di una sorgente Markoviana a N stati differenti.
T
a
b
e
l
l
a
 
1
.
1
16
Con una sorgente come questa, si dovrebbero infatti costruire N tabelle di Huffman (una per
ogni stato), essendo in generale la probabilit  condizionata per i simboli successivi differente
per ogni stato. Inoltre, l algoritmo risulta poco adattabile a cambiamenti nella statistica della
sorgente.
In ogni caso, la statistica dell informazione da comprimere non Ł nota a priori: occorrono
compressori universali dalle buone prestazioni e con un comportamento omogeneo al variare
della struttura dell informazione.
1.4.2 Codifica Run-Length
La maggior parte dei metodi di compressione delle immagini sono basati sulla constatazione
che i pixel adiacenti dell immagine tendono ad avere lo stesso valore. Una tipica immagine,
rappresentata come una bitmap dei valori assunti dai pixel, Ł quella mostrata in figura 1.2.
Fig. 1.2   Una immagine come matrice di valori
Gli stessi valori della matrice possono essere rappresentati come una sequenza:
1 2 1 1 1 1 1 3 4 4 4 4 1 1 3 3 3 5 1 1 1 1 3 3
Per ridurre lo spazio richiesto dall immagine, specialmente se vi sono molti pixel adiacenti
con lo stesso valore, si adotta la codifica run length (RLE   Run Length Encoding). In questo
metodo, la bitmap viene letta in sequenza per individuare le successioni o run di pixel
consecutivi con lo stesso valore.
Ogni run individuato viene codificato attraverso una coppia di valori in cui la prima
componente Ł il numero di valori ripetuti e la seconda componente Ł il valore della sequenza.