Compressione object-based del segnale video mediante trasformata Wavelet

CAPITOLO 1. CODIFICA VIDEO 2
memorizzazione che per la trasmissione. Per poter passare ai sistemi digitali si e´
dovuto aspettare che la tecnologia e le conoscenze permettessero di ridurre tale
mole di dati senza perdere informazione, o comunque perdendone poca. Un altro
aspetto molto importante per l’introduzione dei sistemi digitali e´ stato lo sviluppo
di sistemi di trasmissione in grado di trattare moli di dati piu´ grandi, ma di questo
aspetto non si parlera´ in questo testo, in quanto ci si focalizza, principalmente, sul
problema della riduzione dei dati.
Dalle considerazioni fatte scaturisce la necessita´ di trovare un metodo per ri-
durre la quantita´ di informazione da trasmettere e/o memorizzare. Per poter com-
primere la sequenza video bisogna sfruttare le caratteristiche del segnale. Prima
fra tutte la ridondanza temporale: ogni frame e´ legata statisticamente alle frame
che la precedono e a quelle che la seguono (ad esempio, oggetti simili possono
essere presenti in piu´ frame anche se non necessariamente nella stessa posizio-
ne). Bisogna inoltre sfruttare la ridondanza spaziale, poiche` anche i pixel che
compongono la frame sono statisticamente legati fra loro. Un altro aspetto molto
interessante che puo´ essere sfruttato per ridurre ulteriormente i dati e´ l’incapacita´
dell’occhio umano di apprezzare tutti i dettagli: sia in termini spaziali (ad esem-
pio i contorni degli oggetti) che in termini temporali (ad esempio per i movimenti
troppo rapidi). Per quanto riguarda il colore, poi, l’occhio umano e´ piu´ sensibile
alla luminosita´ dell’immagine (luminanza) che non all’informazione di colore.
1.2 Compressione
Si definisce compressione video la riduzione del bit-rate del segnale video digita-
le. Per poter ridurre tale bit-rate si distinguono tecniche lossless che, sfruttando la
ridondanza spaziale e temporale, compattano senza perdere informazione e tec-
niche lossy che, al contrario, perdono informazione cercando di eliminare quei
dettagli a cui l’occhio umano e´ meno sensibile.
1.2.1 Tecniche di Compressione Lossless
La teoria dell’informazione fornisce le basi per le tecniche di compressione los-
sless. Nella teoria dell’informazione si definiscono dei simboli Xi3, che sono gli
elementi da trasmettere o memorizzare. L’insieme di simboli, che la sorgente
puo´ generare, viene detto alfabeto di sorgente. Si definisce ei l’evento corrispon-
dente all’emissione del simbolo xi a cui si associa la probabilita´ pi. Si definisce
e` pari a 106, e non a 1048576 = 220 bit al secondo.
3Nel caso di codifica video gli elementi potrebbero essere i singoli pixel, o gruppi di pixel o
parte dei bit che rappresentano il valore di luminanza del pixel stesso.
CAPITOLO 1. CODIFICA VIDEO 3
autoinformazione o piu´ semplicemente informazione associata all’evento ei:
I(ei) , log
1
pi
(1.1)
Dalla definizione si nota che piu´ un evento e´ probabile, meno informazioni e´ con-
tenuta in esso; ad esempio, un evento certo non da´ alcuna informazione. Dalla
definizione di autoinformazione discende il concetto di entropia di un simbolo di
sorgente H(X):
H(X) ,
N∑
i=1
pi · log
1
pi
(1.2)
che e´ l’informazione media associata all’emissione di un simbolo. Il concetto
di entropia associata ad un simbolo e´ estendibile a blocchi di simboli X (n) =
(X1, X2, ..., Xn)4:
H(X(n)) ,
∑
x(n)∈Xn
p(X(n)) · log 1
p(X(n)) =
∑
x(n)∈Xn
−p(x(n)) log p(x(n)) (1.3)
Per sorgenti stazionarie si definisce, infine, il tasso entropico della sorgente:
H(S) = lim
n→∞
1
n
H(X(n)) (1.4)
Il tasso entropico ha un’importanza molto rilevante nella teoria dell’informazione.
Ad esso, infatti, e´ legato il primo teorema di Shannon, secondo cui possiamo
codificare una sequenza di simboli senza perdita d’informazione purche` il tasso di
codifica sia superiore al tasso entropico della sorgente. Per avvicinarsi a tale limite
inferiore, in particolare, conviene codificare congiuntamente blocchi di simboli
molto lunghi.
La Teoria dell’Informazione mostra che la migliore codifica che si puo´ ottene-
re e´ quella che associa a ciascun blocco una parola codice di lunghezza pari alla
sua autoinformazione. In genere si associano parole codice piu´ corte ai blocchi
piu´ probabili e parole codice piu´ lunghe ai blocchi meno probabili.
Codifica Run Length
Una delle tecniche piu´ semplici che si puo´ pensare per ridurre il bit-rate e´ la co-
difica Run Length. Spesso nelle sequenze di dati (specialmente nelle immagini)
4
In una diversa rappresentazione il simbolo del nuovo insieme e´ uguale ad un blocco di simboli
del vecchio insieme.
CAPITOLO 1. CODIFICA VIDEO 4
alcuni valori si ripetono piu´ volte in successione. La tecnica Run Length sfrut-
ta questa ridondanza associando alla sequenza di n simboli uguali il valore del
simbolo stesso seguito da un contatore che indica quante volte questo simbolo e´
ripetuto. Tale tecnica e´ molto semplice ma non sempre conviene utilizzarla dato
che per ogni simbolo trasmesso (o memorizzato) si trasmette anche il suo contato-
re. Tale contatore viene rappresentato con un certo numero di bit. Piu´ il numero di
bit utilizzati per la rappresentazione del contatore e´ alto e piu´ si riesce a codificare
sequenze molto lunghe con pochi bit, ma allo stesso tempo si sprecano bit per
sequenze corte. Per i motivi sopraccennati tale tecnica non sempre e´ conveniente,
tranne in quei casi in cui si presentano sequenze molto lunghe e frequenti.
La codifica di Huffman
La tecnica precedente ha come suo principale vantaggio la semplicita´ e, inol-
tre, non richiede che la sorgente sia stazionaria. Ma anche quando si conosco-
no perfettamente le statistiche del segnale5, non si ottengono prestazioni elevate.
Prestazioni ottime si raggiungono con la codifica di Huffman 6.
In una generica tecnica di codifica si ”sostituisce” ogni simbolo o gruppo di
simboli che si vuole trasmettere con una particolare sequenza di bit detta parola
codice. Per poter sfruttare al meglio la ridondanza del segnale da compattare, le
parole codice devono essere di lunghezza variabile. Naturalmente, in questo caso,
ci si pone il problema di come distinguere parole codice di lunghezza diversa in
ricezione. L’idea piu´ semplice e´ quella di utilizzare dei simboli di punteggiatura
per separare le parole codice. In questo modo, pero´, si sprecano risorse in quanto
e´ necessario un simbolo particolare per rappresentare il simbolo di punteggiatura;
inoltre, anche i simboli di punteggiatura devono essere inseriti nei dati compattati,
riducendo l’efficienza della tecnica. Molto piu´ utile risulta l’utilizzo di codici a
prefisso, che sono quei codici che non necessitano di punteggiatura in quanto non
producono ambiguita´ in fase di decodifica: ogni parola codice non e´ prefisso per
nessun’altra. Ad esempio il codice 1, 01, 001, 0001 e´ un codice a prefisso.
La codifica di Huffman e´ una tecnica di codifica a prefisso, che associa parole
codice piu´ corte a simboli piu´ probabili. La descrizione della tecnica sara´ piu´
chiara con un piccolo esempio. Consideriamo i simboli in Tabella 1.1 con le
relative probabilita´.
L’algoritmo prevede che gli n simboli vengano messi in ordine di probabilita´
decrescente (come si puo´ vedere nella Tabella 1.1). A partire dalla tabella ori-
ginaria si costruisce una nuova tabella di n − 1 simboli: i primi n − 2 simboli
sono i simboli della tabella precedente con probabilita´ piu´ alta, e l’(n− 1)-esimo
5
Ipotesi irrealizzabile nella pratica anche se, in alcuni casi, le statistiche calcolate in maniera
approssimata si avvicinano molto alla realta´.
6Si ipotizza di avere una sorgente stazionaria.
CAPITOLO 1. CODIFICA VIDEO 5
Simboli Probabilita´
A 0.5
B 0.25
C 0.125
D 0.0625
E 0.0625
Tabella 1.1: Esempio della codifica di Huffman: alfabeto d’ingresso.
simbolo e´ un nuovo simbolo nato dall’unione degli ultimi due simboli, quelli a
probabilita´ piu´ bassa. Questo nuovo simbolo avra´ una probabilita´ pari alla somma
delle probabilita´ dei due simboli eliminati.
Si ottiene, nell’esempio considerato, la Tabella 1.2.
Simboli Probabilita´
A 0.5
B 0.25
C 0.125
DE 0.125
Tabella 1.2: Esempio della codifica di Huffman: tabella al primo passo.
Ripetendo il ragionamento n− 1 volte si arriva ad una tabella costituita da un
unico simbolo con probabilita´ 1. In questo modo si costruisce l’albero in Figura
1.1.
Nella figura, su ciascun ramo dell’albero, e´ presente un bit. Tali bit vengono
utilizzati per determinare la parola codice associata a ciascun simbolo. Il principio
e´ il seguente: si parte dalla radice (il nodo con probabilita´ 1) dell’albero e si
”leggono” i bit sul percorso che porta al simbolo da codificare.
Si costruisce, in questo modo, la Tabella 1.3.
Per mostrare la grande efficienza di tale algoritmo si calcola l’entropia dell’al-
fabeto d’ingresso e la si confronta con la lunghezza media7 definita come:
L ,
n∑
i=1
p(xi) · li (1.5)
7La lunghezza media per la Teoria dell’Informazione e´ la media della lunghezza l(xi) delle
parole codice xi pesate con le loro rispettive probabilita´ p(xi).
CAPITOLO 1. CODIFICA VIDEO 6
A
B
-
0.25
0.5
0.5
0.25
0.125
0.625
0.625
7
-
0
-
-
7
0.125
0
0
1
3
7
1
0
1
1
1
C
D
E
Figura 1.1: Esempio dell’algoritmo di Huffman.
Simboli Probabilita´ Parole codice
A 0.5 1
B 0.25 01
C 0.125 001
D 0.0625 0001
E 0.0625 0000
Tabella 1.3: Esempio della codifica di Huffman: parole codice.
Avendo considerato una sorgente in cui tutte le probabilita´ sono potenze di 2
si ottiene una lunghezza media di codifica pari all’entropia di sorgente.
L =
n∑
i=1
p(xi) · li = −
n∑
i=1
p(xi) · log(p(xi)) = 1.875
In generale, sebbene la tecnica di Huffman sia ottima, la lunghezza media di
codifica puo´ essere significativamente maggiore dell’entropia. Per ottenere pre-
stazioni migliori e´ sufficiente considerare gruppi di simboli e applicare la tecnica
sopra descritta. Per poter adoperare la codifica di Huffman, pero´, bisogna cono-
scere perfettamente le probabilita´ dell’alfabeto di sorgente, cosa che spesso non e´
realizzabile.
La codifica aritmetica
Il principale svantaggio della codifica di Huffman e´ la sua complessita´. Si e´ gia´
accennato al fatto che il limite inferiore rappresentato dal tasso entropico, in ge-
CAPITOLO 1. CODIFICA VIDEO 7
nerale viene raggiunto solo asintoticamente all’aumentare di n. Dalla particolare
struttura dell’algoritmo di Huffman si deduce che la complessita´ computazionale
cresce esponenzialmente con il numero di simboli da codificare congiuntamente.
Questa particolare caratteristica, unita all’elevata sensibilita´ dell’algoritmo alla
perfetta conoscenza delle probabilita´ dei simboli di sorgente porta, in molti casi,
a preferire una tecnica alternativa. Una di queste (la piu´ usata nell’ambito della
compressione di immagini o sequenze video) e´ la codifica aritmetica. Essa ha
come suo principale vantaggio una bassa complessita´ computazionale.
Si considera un segmento di lunghezza unitaria e lo si suddivide in un numero
di segmenti pari al numero di simboli dell’alfabeto di sorgente. Ogni segmento si
avra´ una lunghezza li pari alla probabilita´ del simbolo a cui e´ associato. In ma-
niera simile, ciascun segmento si e´ ulteriormente suddiviso in segmenti si,j la cui
lunghezza relativa li/j = li,jli e´ pari alla probabilita´ del simbolo xj (secondo simbo-
lo trasmesso) condizionata al simbolo che lo precede xi: Pr(xj/xi). Si ripete tale
ragionamento un numero di volte pari alla lunghezza N del blocco da codificare
(vedi Figura 1.2). Si puo´ dimostrare che se si individua il centro del segmento
a cui e´ associato il blocco da codificare e si trasmette la sua rappresentazione in
binario con una precisione tale da rendere univoca l’individuazione del segmento
a cui appartiene, si riescono a raggiungere prestazioni asintoticamente ottime. La
complessita´ di questo algoritmo cresce linearmente con la lunghezza del blocco
da codificare. Infatti, e´ sufficiente suddividere ulteriormente ciascun segmento
per passare dalla codifica di blocchi di lunghezza N alla codifica di blocchi di
lunghezza N + 1. Nella codifica di Huffman, invece, per passare da blocchi di
lunghezza N a blocchi di lunghezza N + 1 si deve ripetere tutto l’algoritmo da
capo per ricostruire un nuovo albero. Un altro punto di forza di questo algoritmo
e´ la minor sensibilita´ agli errori di stima delle probabilita´ dei simboli di sorgente.
A B C D
A B C D
A B C D
Figura 1.2: Codifica Aritmetica.
CAPITOLO 1. CODIFICA VIDEO 8
Codifica di Lempel-Ziv-Welch
La maggior parte degli algoritmi di codifica presuppone la conoscenza a priori
delle statistiche del segnale da codificare. In alcuni casi e´ prevista una fase ini-
ziale di stima delle probabilita´. Quando, invece, si vogliono codificare dei dati di
cui non si conoscono le statistiche (o comunque non si vogliono stimare), si usano
degli algoritmi di codifica universale come l’algoritmo di codifica di Lempel-Ziv-
Welch. Questo algoritmo prevede la costruzione di una tabella di sequenze tipiche
che si modifica in maniera adattativa. Inizialmente in questa tabella sono inserite
solo le parole codice 0 in posizione 0 ed 1 in posizione 1. Ad ogni passo si con-
sidera un gruppo di bit e si verifica se tale sequenza e´ presente nella tabella: se e´
presente si aggiunge il bit successivo da codificare al gruppo di bit considerato e
si verifica se anche questa nuova sequenza e´ presente in tabella. La ricerca prose-
gue finche´ non si presenta una sequenza non appartenente alla tabella. In questo
caso si codifica la sequenza immediatamente precedente con l’indice della tabella
corrispondente e si aggiunge la nuova sequenza nella prima locazione libera della
tabella. Inoltre, ogni volta che viene inserita una nuova sequenza di lunghezza
n + 1 si controlla se nella tabella e´ presente anche l’altra sequenza di lunghezza
n + 1 che differisce soltanto per l’ultimo bit. In caso positivo si elimina dalla
tabella la sequenza di lunghezza n che e´ prefisso delle due sequenze considerate,
lasciando libera la sua posizione8.
Questo algoritmo presenta notevoli vantaggi:
1. Si adatta alla particolare sorgente di dati che si intende codificare
2. Non prevede la trasmissione a priori di alcun vocabolario di parole codice
in quanto la tabella in decodifica viene costruita in maniera molto simile al
processo di codifica
3. Si dimostra che l’algoritmo e´ asintoticamente ottimo
1.2.2 Tecniche di Compressione Lossy
Nelle tecniche di compressione lossy si accetta una limitata perdita d’informazio-
ne allo scopo di migliorare le prestazioni di codifica. Di conseguenza una tecnica
di compressione lossy va analizzata in maniera differente in funzione del partico-
lare ambito in cui ci si trova. La linea guida e´, ovviamente, perdere informazioni
poco ”importanti”, come ad esempio particolari che l’occhio umano non riesce ad
apprezzare.
8Non avrebbe senso codificare tale sequenza: si puo´ codificare una sequenza piu´ lunga con lo
stesso numero di bit.
CAPITOLO 1. CODIFICA VIDEO 9
Di conseguenza per poter confrontare le prestazioni di una tecnica di compres-
sione lossy con un’altra, non e´ piu´ sufficiente il solo rapporto di compressione, ma
bisogna confrontare anche quanta informazione si perde9. Sono quindi necessari
dei parametri di qualita´. Un primo parametro molto usato e´ l’errore quadratico
medio (Mean Square Error):
MSE , E[(X − Xˆ)2] (1.6)
che in ipotesi di ergodicita´ diventa
MSE , E[(X − Xˆ)2] = 1
n
n−1∑
i=0
(xi − xˆi)2 = εˆ2 (1.7)
dove x rappresenta il segnale originale e xˆ il segnale ottenuto dopo il processo di
compressione e decompressione. Naturalmente il solo MSE non e´ spesso signifi-
cativo in quanto un errore puo´ avere peso diverso a seconda dell’ambito in cui ci
si trova. Ad esempio e´ ovvio che un errore commesso su di una foto amatoriale
non ha la stessa importanza di un errore commesso su una radiografia; inoltre,
anche nello stesso ambito l’entita´ assoluta dell’errore non ha molto senso se non
viene confrontata col valore del segnale di partenza. Non conta l’errore assolu-
to ma l’errore relativo. In molti casi ha, quindi, piu´ senso utilizzare il rapporto
segnale-rumore SNR:
SNR , 10 log10
E[X2]
E[(X − Xˆ)2]
= 10 log10
E[X2]
ε2
(1.8)
In realta´ anche quest’ultimo parametro non e´ molto significativo: solo la sen-
sibilita´ dell’utilizzatore fornisce il vero parametro di qualita´. Purtroppo, dato
che tale sensibilita´ non e´ facile da modellizzare con un’equazione matematica,
in letteratura vengono utilizzati i parametri precedenti o eventualmente delle loro
varianti.
Quantizzazione scalare
Il cuore di qualunque operazione di compressione e´ la quantizzazione. Con quan-
tizzazione si intende quel processo che trasforma un insieme di partenza piu´ gran-
de (sia esso continuo o discreto), in un insieme discreto di dimensioni piu´ piccole.
La corrispondenza e´ fatta in maniera tale da suddividere l’insieme di partenza in
9La perdita d’informazione, se si sta parlando di compressione d’immagine, si traduce in un
peggioramento della qualita´ dell’immagine codificata.
CAPITOLO 1. CODIFICA VIDEO 10
tanti sottoinsiemi e far corrispondere ad ognuno di questi sottoinsieme un solo
elemento nell’insieme di arrivo.
La prima tecnica di quantizzazione qui descritta e´ la quantizzazione scala-
re, Q, che ad ogni elemento x appartenente all’insieme < fa corrispondere un
elemento yi appartenente ad un sottoinsieme C di R detto codebook:
Q : x ∈ < −→ yi ∈ C ⊂ R (1.9)
Si definisce Regione di decisione quel sottoinsieme Ri ⊂ < tale che ∀x ∈
Ri : Q(x) = yi. Le regioni sono tali da verificare le seguenti proprieta´:
N⋃
i=1
Ri = < e Ri
⋂
Rj = ∅ con i 6= j (1.10)
Si definisce, inoltre, il tasso di codifica R:
R , log2N (1.11)
dove N e´ il numero di elementi yi ∈ C. Oltre al tasso di codifica per poter
descrivere completamente una tecnica di codifica lossy se ne deve valutare la
distorsione
D , E[(X −Q(X))2] =
∫ ∞
−∞
(x−Q(x))fX(x)dx (1.12)
dove fX(x) e´ la densita´ di probabilita´ di x.
Una quantizzazione viene detta regolare se verifica le seguente proprieta´:
• Ri e´ un intervallo di estremi xi−1, xi: Ri = (xi−1, xi)
• yi ∈ (xi−1, xi)
L’esempio piu´ semplice di quantizzazione regolare e´ la quantizzazione uniforme,
nella quale le Ri, anche dette celle di quantizzazione, sono tutti intervalli di di-
mensioni uguali (eccetto per la prima e l’ultima cella10.). Inoltre, i livelli di resti-
tuzione yi
11 coincidono con il centro di ciascun intervallo. Di conseguenza, se si
fa eccezione per le due celle estreme, l’errore massimo che si puo´ ottenere e´ pari
alla semidimensione cella. In seguito a quanto detto precedentemente, si potrebbe
pensare che la migliore soluzione si ottiene diminuendo le dimensioni dell’inter-
vallo. Tale soluzione, pero´, risulta errata in quanto oltre all’errore granulare12
10x0 = −∞ e xN = ∞
11Fanno eccezione y1 e yn che appartengono ad intervalli di dimensione infinita.
12L’errore che si commette approssimando l’elemento appartenente ad un certa cella Ri (di
dimensioni finite) con il livello di restituzione yi.
CAPITOLO 1. CODIFICA VIDEO 11
esiste un altro errore detto di sovraccarico che si commette nel primo e nell’ulti-
mo intervallo13. Considerare, quindi, l’errore massimo non ha senso. Molto piu´
significativa e´ la misura della distorsione che nel caso di quantizzazione uniforme
e´ definita come:
D ,
∫ ∞
−∞
(x−Q(x))fx(x)dx =
N∑
i=1
∫
Ri
(yi − x)2fx(x)dx (1.13)
Data la sua semplicita´ la quantizzazione uniforme presenta un’ampia diffusio-
ne, anche se non e´ sempre la soluzione migliore che si possa trovare.
Quantizzazione Predittiva
Una tecnica molto usata quando i simboli trasmessi sono sufficientemente cor-
relati tra loro e´ la tecnica di quantizzazione predittiva. L’idea di base e´ molto
semplice: qualunque tecnica di quantizzazione migliora le sue prestazioni se la-
vora su un range piu´ piccolo. Si cerca allora di restringere tale range quantizzando
non direttamente il simbolo x, ma piuttosto la differenza fra esso e la sua predi-
zione x˜. E´ facile verificare che, se i simboli da codificare sono sufficientemente
correlati tra loro ed il predittore e´ accuratamente progettato, la distribuzione di
x− x˜ e´ piu´ concentrata rispetto a quella di x.
Lo schema utilizzato da questa tecnica e´ molto semplice, come mostrato in
Figura 1.3.
-
Predittore
- Quantizzatore
- 6
- -enxn
xˆn
-eˆn +
Predittore
6˜ˆxn
-
ff
xˆn
ff+
?
˜ˆxn
TRASMETTITORE RICEVITORE
Figura 1.3: Schema a blocchi di un quantizzatore predittivo.
Si noti che il ricevitore deve usare necessariamente i simboli quantizzati xˆn per
effettuare la predizione e quindi, per sincronizzare le operazioni, lo stesso deve
fare il trasmettitore. In questa maniera sia il predittore in trasmissione che quello
in ricezione lavorano sugli stessi dati e quindi forniscono la stessa predizione.
13Se tali intervalli sono non limitati l’errore di overflow massimo e´ pari a∞.
CAPITOLO 1. CODIFICA VIDEO 12
Quantizzazione Vettoriale
Il caso piu´ generale di quantizzazione e´ la quantizzazione vettoriale. Per questa
tecnica non si analizza il singolo simbolo, ma gruppi di simboli. Questa tecnica
puo´ essere interpretata anche come un’estensione naturale della quantizzazione
scalare. In una quantizzazione scalare viene considerato un singolo simbolo alla
volta; tale simbolo apparterra´ ad una cella sottoinsieme di un spazio monodimen-
sionale (intervallo (a, b)), e verra´ approssimato con un valore opportunamente
scelto in base alla cella di appartenenza. Nella quantizzazione vettoriale i simboli
x considerati, che sono il raggruppamento di n simboli consecutivi x, assumono
valori in un insieme di uno spazio n-dimensionale. Anche in questo caso il sim-
bolo x viene approssimato con un opportuno valore14. La scelta del valore con
cui approssimare il simbolo X dipende dalla sua posizione, e piu´ precisamente
dipende dalla sua appartenenza ad una regione di decisione15. Anche la quantiz-
zazione vettoriale puo´ essere regolare se verifica le proprieta´ 1.2.2 estese al caso
n-dimensionale:
• Ri e´ una regione connessa
• yi ∈ Ri
Non avendo piu´ i vincoli strutturali della quantizzazione scalare le prestazioni
ottenute saranno in generale migliori.
L’esempio in Figura 1.4 mostra l’efficacia di una quantizzazione vettoriale
rispetto ad una scalare.
Nel disegno e´ rappresentata su un piano la densita´ di probabilita´ di due simboli
consecutivi che si suppone uniforme nella zona in grigio. Nella figura a sinistra
viene usata una quantizzazione scalare uniforme applicata prima su un simbolo e
poi sul successivo mentre nella figura a destra viene applicata una quantizzazione
vettoriale direttamente sui due simboli. Come si puo´ notare l’azione combinata
della quantizzazione scalare applicata a due simboli consecutivi fa si che si distin-
guano 64 celle di cui solo 32 realmente utilizzate mentre con la quantizzazione
vettoriale il numero di celle individuate e´ 32 (solo quelle necessarie). A parita´ di
dimensione della cella (cioe´ a parita´ di distorsione) per la quantizzazione scalare
14Viene ancora associata una parola codice, solo che, questa volta, fa riferimento ad un vettore
appartenente allo spazio n-dimensionale considerato.
15
Il concetto di regione di decisione Ri nella quantizzazione vettoriale e´ l’estensione della
regione di decisioneRi della tecnica scalare e cioe` un sottoinsieme di <n tale che:
N⋃
i=1
Ri = <n e Ri
⋂
Rj = ∅ con i 6= j
CAPITOLO 1. CODIFICA VIDEO 13
6
-
6
-
Quantizzazione scalare Quantizzazione vettoriale
X2 X2
X1 X1
Distribuzione di probabilita´ di una coppia di simboli consecutivi
Figura 1.4: Esempio di Quantizzazione Vettoriale.
sono necessari 3 bit per simbolo e cioe` 6 bit per coppia di simboli, mentre per
la quantizzazione vettoriale sono sufficienti soltanto 5 bit: abbiamo sfruttato la
maggiore liberta´ strutturale. Allo stesso modo, utilizzando lo stesso numero di bit
per la quantizzazione vettoriale, la distorsione risultera´ inferiore rispetto a quella
ottenuta con la quantizzazione scalare.
Da questa breve descrizione si possono mettere in evidenza due aspetti im-
portanti. Il primo e´ che una qualunque tecnica di compressione e´ soltanto un
caso particolare di quantizzazione vettoriale16. Inoltre, si intuisce che, cosı´ come
nel caso della codifica lossless, piu´ aumenta il numero di simboli codificati con-
giuntamente e migliori saranno, in generale, le prestazioni. La soluzione ottima
andrebbe quindi ricercata in una opportuna quantizzazione vettoriale.
Un algoritmo che permette di ricavare una quantizzazione vettoriale che si
avvicina molto all’ottimo e´ algoritmo di Lloyd Max.
1.2.3 Trasformate
Anche se l’approccio precedente risulta teoricamente ottimo, data la sua comples-
sita´ non viene quasi mai utilizzato.
Una tecnica che presenta buone prestazioni a basso costo computazionale e´ la
compressione mediante trasformata. La descrizione di questa tecnica sara´ piu´
chiara con un semplice esempio. Si suppone di avere una coppia di variabili
16Ad esempio la quantizzazione scalare uniforme puo´ essere vista come una quantizzazione
vettoriale dove le regioni di decisioni sono ipercubi n-dimensionali (vedi esempio in Figura 1.4).
CAPITOLO 1. CODIFICA VIDEO 14
aleatorie X1 e X2 con densita´ di probabilita´ congiunta uniforme in una regione
rettangolare come mostrato in Figura 1.5.
6
-
X1
X2
Figura 1.5: Distribuzione congiunta di due simboli successivi.
La soluzione ottima si otterrebbe quantizzando vettorialmente la coppia (X1,X2)
e quindi disponendo le parole codice opportunamente nella regione d’interesse.
Risultati simili, pero´, si possono ottenere anche cambiando la base di rappresen-
tazione, e cioe` ruotando gli assi di riferimento del piano di 45.
-
6
-
6
Quantizzazione scalare classica Quantizzazione scalare con trasformata
X1
X2
X1
X2
Figura 1.6: Confronto fra quantizzazione classica e con trasformata.
Nella nuova rappresentazione si quantizzano scalarmente le due componenti,
dedicando piu´ risorse alla componente trasformata con distribuzione piu´ estesa
(cioe` con varianza maggiore).
CAPITOLO 1. CODIFICA VIDEO 15
Spesso, il risultato che si ottiene e´ esattamente lo stesso che si otterrebbe con
una quantizzazione vettoriale, ma con una notevole riduzione di complessita´. Lo
schema di quantizzazione mediante trasformata e´ mostrato in Figura 1.7.
A
-
-
Q1
Qn
-
-
A−1
x xˆ
z1
zn
zˆ1
zˆn
Figura 1.7: Schema a blocchi.
Il segnale da comprimere viene ordinato in un vettore e trasformato mediante
moltiplicazione matriciale con la matrice di trasformazioneA. Le componenti del
vettore cosı´ trasformato vengono quantizzate separatamente e in maniera differen-
te, dedicando piu´ bit alle componenti con maggiore energia, mentre a quelle con
minore energia si dedicano poche o nessuna risorsa.
Tra le possibili trasformate realizzabili, la scelta si limita a quelle unitarie, in
modo che l’errore di quantizzazione commesso sul vettore trasformato y e´ uguale
a quello commesso sul vettore di origine x:
||y − yˆ||2 = (y − yˆ)T (y − yˆ)
= [A(x− xˆ)]T [A(x− xˆ)]
= (x− xˆ)TATA(x− xˆ)
= ||x− xˆ||2 (1.14)
Riassumendo la scelta della trasformata va fatta in modo che essa:
• sia unitaria (in modo da conservare l’errore di quantizzazione);
• decorreli le componenti (per poter utilizzare la quantizzazione scalare inve-
ce di quella vettoriale senza grosse perdite);
• compatti l’energia in poche componenti a cui dedicare la maggior parte
delle risorse.
Va detto che una trasformata lineare non e´ in grado di eliminare tutta la di-
pendenza presente tra due o piu´ componenti ma soltanto la semplice correla-
zione lineare. Cio´ nonostante in molti casi la tecnica di compressione mediante
trasformata fornisce buone prestazioni.