Introduzione:
La tesi si basa sull'analisi delle tecnologie di codifica in un particolare metodo di compressione:
la codifica mediante trasformata.
Tale metodo di codifica è basato sul rimuovere la ridondanza spaziale presente in una data
immagine (che sia singola o parte di un video – frame – ) trasformandola dal dominio spaziale a
quello delle frequenze.
Il metodo di codifica preso in esame trae vantaggio dal fatto che l'occhio umano percepisce in modo
minore le alte frequenze rispetto alle basse frequenze in modo da poter tagliare dettagli meno
significativi a livello di percezione visiva.
Ad oggi, quasi tutti i più conosciuti ed utilizzati metodi di codifica utilizzano la DCT (Discrete
Cosine Trasform) ovvero la Trasformata Discreta del Coseno, tuttavia esistono nuovi metodi di
codifica che utilizzano diversi tipi di trasformata e che hanno dato vita ad approcci alternativi.
Lo scopo della tesi è di analizzare nel dettaglio la nuova codifica video H.266, la codifica audio ed i
vari metodi di trasformata utilizzabili, nonché comparare i risultati dei precedenti metodi di codifica
ed i diversi tipi di trasformata utilizzata da ognuno di essi in modo completo e dettagliato.
Come introduzione alle codifiche video, inoltre, verranno esplicati i vari metodi di codifica delle
immagini fisse, con particolare importanza rivolta allo standard lossless PNG ed, infine, verranno
analizzati anche i codec audio.
0) Cenni storici ed importanza della compressione video
La velocità delle connessioni internet è in continuo aumento, così come i bitrate dei network e la
grandezza di Hard Disk, memorie flash e media ottici.
Con il prezzo delle trasmissioni e dell'archiviazione in continua diminuzione, potrebbe non essere
immediatamente chiaro perché la compressione video è tanto necessaria e perché ci sono così tanti
sforzi – ora come in passato – per renderla migliore.
La compressione video ha due importanti benefici: il primo è che rende possibile utilizzare video
digitali nelle trasmissioni e nello storage in ambienti che non sono in grado di supportare video non
compressi, chiamati “raw”.
Ad esempio, per quanto possa essere veloce, la fibra ottica che raggiunge le attuali abitazioni è
ancora insufficiente per poter gestire video non compressi in tempo reale (anche a bassi frame rate –
immagini al secondo – e basse risoluzioni).
Un altro esempio è che sia i DVD che i Bluray Disk sono in grado di contenere solo pochi frame (e
dunque pochi minuti) di un video raw conforme alle qualità ed ai frame rate degli standard televisivi
e sarebbero dunque inutilizzabili senza un'opportuna compressione video.
Il secondo beneficio offerto dalla compressione video è che permette un utilizzo più efficiente delle
risorse di trasmissione e storage.
Un segnale può dunque essere compresso rimuovendo la ridondanza e ci sono due metodi principali
di compressione: il metodo lossless e quello lossy.
Nelle compressioni lossless (prive di perdita) la ridondanza statistica è rimossa in modo che il
segnale originale possa essere perfettamente ricostruito dal decoder.
Sfortunatamente, al momento, i metodi di codifica lossless riescono a comprimere le immagini in
modo insufficiente e, mentre per la codifica delle immagini fisse è molto utilizzata la codifica
lossless, non è possibile affermare la stessa cosa per la codifica video.
I più comuni metodi di compressione video infatti sono basati su compressioni lossy (con perdita),
nelle quali è possibile ottenere grandi benefici in termini di compressione,
al costo però di perdere parte delle informazioni; difatti l'immagine ricostruita dal decoder non sarà
mai identica a quella originale.
L'obiettivo dei codec di codifica video è dunque quello di ottenere il massimo beneficio in termini
di compressione, con la minima distorsione introdotta dal processo di compressione.
Gli algoritmi di compressione video rimuovono la ridondanza temporale, spaziale e/o i domini di
frequenza.
Come prima introduzione, si guardi ora l'immagine sottostante che rappresenta un esempio di un
singolo frame video.
All'interno delle regioni evidenziate (rettangolo di sinistra e destra) è presente una lieve variazione
nel contenuto dell'immagine e, quindi, c'è una ridondanza spaziale significativa.
Si prenda ora in analisi la seconda immagine riportata di seguito.
Questa seconda immagine mostra lo stesso identico frame dopo essere stato processato da un filtro
passa-basso in modo da rimuovere alcuni dei contenuti ad alta frequenza.
L'occhio umano è più sensibile alle basse frequenze e l'immagine è ancora riconoscibile, sebbene
parte delle informazioni sono andate perdute (si pensi alle linee del muro sullo sfondo).
Si prenda ora in esame questa terza immagine che mostra il frame successivo della sequenza video.
La sequenza originale era stata catturata da una videocamera a 25 fps, quindi c'è un piccolo
cambiamento tra i due frame e c'è una chiara ridondanza temporale (la maggior parte dell'immagine
rimane identica tra i frame successivi).
Rimuovendo i diversi tipi di ridondanza (spaziale, delle frequenze e/o temporale), è possibile
comprimere i dati al costo di una perdita di informazioni (distorsione).
Un'ulteriore compressione può essere raggiunta encodando i dati processati utilizzando una codifica
entropica come quella di Huffman.
La compressione video e delle immagini rappresenta da anni un prolifico campo di ricerca e sono
stati sviluppati numerosi sistemi ed algoritmi di compressione e decompressione e sono stati definiti
numerosi standard.
Dopo questa breve introduzione, passiamo adesso ad analizzare le fondamenta sulle quali si basa la
codifica mediante trasformata per poi introdurre i primi standard di codifica delle immagini fisse.
1) Basi della Codifica Tramite Trasformata
La codifica tramite trasformata è uno degli strumenti fondamentali della codifica audio e video che
utilizziamo oggi giorno in quasi ogni settore.
Il suo funzionamento è da ricondurre al processo di riduzione di ridondanza spaziale rappresentando
i pixel nel dominio delle frequenze per poi poter effettuare una riduzione della quantità di dati in
uscita tramite compressione e quantizzazione.
Per poter essere compresso, un segnale deve essere decorellato tramite una trasformata apposita,
ridistribuendo la sua energia ad un piccolo numero di coefficienti,
collocati nella regione delle basse frequenze.
Questi coefficienti possono essere quantizzati in modo da poter eliminare una piccola quantità di
informazioni meno rilevanti senza intaccare la qualità finale dell'immagine una volta ricostruita.
Sebbene il processo di trasformata non comporti una perdita di dati (cioè è “lossless”), il processo
di quantizzazione la comporta e viene dunque detto “lossy” - cioè “con perdita”; si ha così quello
che viene chiamato un “errore di quantizzazione” in quanto non è più possibile accedere ai dati
originali una volta quantizzati.
Ad ogni modo, non è del tutto corretto dire che il processo di trasformata è privo di perdita, poiché,
sebbene lo sia in teoria, in pratica può comportare una limitazione in quanto la sua implementazione
può avere dei limiti numerici dovuti al suo stesso impiego, quali, ad esempio, arrotondamenti e
troncamenti.
Il segnale viene segmentato in blocchi pari, tipicamente da 8x8.
Ogni blocco è poi trasformato individualmente mediante l'operazione di “transformazione dei
macroblocchi”.
Grazie a questo processo basato sui blocchi, è possibile ridurre la complessità totale dei calcoli di
trasformata in quanto risulta molto più facile eseguire i blocchi individualmente rispetto che a
processare tale operazione sull'intera immagine.
Trasformare ogni blocco singolarmente può inoltre catturare le informazioni in modo migliore,
sfruttando la correlazione tra di essi in modo migliore, anche se, in realtà, tale correlazione non è
mai veramente sfruttata a dovere e spesso questo può risultare in errori di riproduzione dovuti alla
ricostruzione finale dell'intera immagine.
Un esempio è dato da un'immagine fortemente quantizzata nella quale è possibile notare artefatti
dovuti a “blocking”, ovvero è possibile notare con facilità i bordi dei vari blocchi.
In altre parole: maggiore è la compressione, più facile sarà vedere tali artefatti.
Dal punto di vista teorico, una trasformata è tenuta a soddisfare alcuni punti fondamentali in modo
da rendere la sua adozione utile al fine pratico.
Il primo dei requisiti fondamentali è la “reversibilità”, ovvero il fatto che il segnale di ingresso
possa essere ricostruito senza errori dal segnale di uscita al quale è stato applicato il calcolo di
trasformata.
Questo è forse il più importante dei requisiti - almeno per quanto riguarda la codifica video - in
quanto per poter visualizzare un'immagine è necessario poter ricreare il segnale di partenza.
Un altro elemento riguarda la riduzione della quantità di dati, ovvero il fatto che la trasformata
debba concentrare il segnale in entrata nel minor numero possibile di coefficienti.
Importante è anche il fatto che la stessa informazione non deve essere ripetuta in coefficienti
diversi, o, se ciò accade, la ripetizione deve essere ridotta al minimo in modo da assicurare
un'efficiente decorrelazione.
Idealmente, possiamo dire che, oltre alle cose sopraelencate, una trasformata debba essere anche il
meno complessa possibile (parlando in termini di operazioni da eseguire) in quanto è logico pensare
che meno calcoli vengono eseguiti, maggiore sarà la sua efficienza a livello di calcolo
computazionale.
1.1) Trasformate Unitarie:
Una trasformata unitaria di un dato vettore x in ingresso è definita da:
Dove B è una matrice unitaria pari ed y è il vettore con i coefficienti di trasformata.
Una matrice pari è unitaria se il suo inverso è uguale al suo trasposto coniugato.
Se una matrice unitaria ha solo valori reali, allora la sua inversa sarà uguale al suo coniugato
e viene definita “matrice ortogonale”.
Ricordo che i vettori colonna ed i vettori riga di una matrice unitaria sono ortogonali
(perpendicolari tra loro) e normalizzati e possono essere definiti come segue:
dove b di k è la k 'esima colonna della matrice unitaria B.
I vettori b di k costituiscono un gruppo di vettori base ortonomali.
I vettori base sono un gruppo di vettori che possono essere combinati linearmente per rappresentare
ogni vettore in un dato spazio vettoriale.
A sua volta, le funzioni base sono un gruppo di funzioni che possono essere combinate linearmente
per rappresentare ogni funzione in un dato spazio di funzione.
In questo caso, la matrice unitaria B rappresenta la trasformata unitaria di funzione base.
Le trasformate unitarie comprendono le caratteristiche sopraelencate tra cui, in primis,
la reversibilità; in questo caso abbiamo che:
Un'altra proprietà di quelle sopraelencate che viene rispettata è quella della riduzione della quantità
di dati tramite i coefficienti ed il fatto di preservare l'energia dell'onda mediante gli stessi:
Le trasformate unitarie, solitamente, sono le più utilizzate negli standard di compressione video.
1.2) Trasformate ad Una Dimensione (monodimensionali):
Considerando x(n) un blocco di N campioni in entrata (dominio spaziale) ed y(k) un gruppo di N
coefficienti di trasformata (dominio delle frequenze), una trasformata monodimensionale è data da:
dove a(k,n) sono le funzioni di trasformata base.
La trasformata inversa usata per ricomporre il segnale originale è invece definita da:
dove b(k,n) sono le funzioni di trasformata base inversa.
Tenendo conto che il primo vettore base tipicamente corrispondente alla frequenza di componente
zero, corrisponde alla funzione costante, allora y(0) è chiamato coefficiente DC, che rappresenta il
principale indicatore della forma d'onda sotto trasformata.
È proprio questo il coefficiente di trasformata più importante dato che è associato alla frequenza più
bassa percepibile.
Tutti gli altri coefficienti, invece, sono chiamati coefficienti AC.
1.3) Trasformate a Due Dimensioni (bidimensionali):
Considerando ora x(m,n) come blocco di campioni NxN a due dimensioni e y(k,l) un gruppo di NxN
coefficienti di trasformata, la trasformata bidimensionale è data da:
La trasformata bidimensionale inversa è invece data da:
a(k,l,m,n) e b(k,l,m,n) sono rispettivamente le funzioni di trasformata bidimensionale e trasformata
bidimensionale inversa.
Ci sono due classi fondamentali di trasformate bidimensionali: le trasformate separabili e le
trasformate non separabili.
Le trasformate non separabili sono calcolate utilizzando semplicemente le N colonne in ingresso da
un capo all'altro per formare una singola colonna di vettori di lunghezza N^2 e solo dopo viene
effettuato il calcolo di trasformata.
Le trasformate separabili sfruttano sia le correlazioni orizzontali che quelle verticali del segnale in
ingresso e, tipicamente, richiedono un'operazione aritmetica N^4.
In una trasformata separabile bidimensionale, entrambe le funzioni di trasformata di base sono
separate in operazioni distinte (orizzontale e verticale):
Con queste due operazioni, una trasformata separabile bidimensionale può essere elaborata in due
fasi indipendenti, eseguite una dopo l'altra.
La prima fase utilizza la funzione base orizzontale ah (l,n),
sfruttando la correlazione orizzontale dei dati.
La seconda fase utilizza invece la funzione di base verticale av (k,m),
sfruttando la correlazione verticale dei dati.
Le trasformate bidimensionali separabili sono implementate come due trasformate
monodimensionali consecutive e sono date da:
In notazione di matrice abbiamo:
Le funzioni di base simmetriche sono funzioni che hanno componenti orizzontali e verticali
simmetriche Av = Ah = A. In questo caso, abbiamo:
La moltiplicazione di due matrici NxN richiede un'operazione matematica di N^3.
Di conseguenza, una trasformata separabile bidimensionale, che ha due moltiplicazioni di matrice,
richiede un'operazione 2N^3 (ricordo che la trasformata non separabile richiede N^4).
Quindi, nel caso in cui si abbia N > 2, è preferibile utilizzare una trasformata bidimensionale.
1.4) Trasformate a Tre Dimensioni (tridimensionali):
Consideriamo adesso x(m,n,p) come un blocco di campioni NxNxN tridimensionale in ingresso.
Tale segnale d'ingresso ha due componenti spaziali ed una componente temporale.
Considerando y(k,l,q) i coefficienti di trasformata, la trasformata tridimensionale è data da:
La trasformata tridimensionale inversa è invece data da:
a(k,l,q,m,n,p) e b(k,l,q,m,n,p) sono rispettivamente le funzioni di trasformata tridimensionale e
trasformata tridimensionale inversa.
Con una trasformata tridimensionale è possibile sfruttare la correlazione tra i dati in tre dimensioni:
due nello spazio ed uno nel tempo.
In particolare, nella codifica video, è possibile rimuovere non solo la ridondanza spaziale,
ma anche la ridondanza temporale!
Ovviamente, utilizzando questo tipo di trasformata, la durata di codifica subirà un significativo
rallentamento, soprattutto su video con un elevato numero di frame.
1.5) Trasformate Direzionali
Una trasformata direzionale è una trasformata che utilizza le informazioni dei bordi presenti in
alcuni dati in entrata per poter sfruttare meglio la correlazione dei gruppi di dati.
Lo scopo di questa trasformata è di aumentare la compressibilità rilevando e rimuovendo la
ridondanza spaziale in modo migliore rispetto alle trasformate non direzionali,
aumentando così il rapporto di compressione rispetto alle stesse.
Le trasformate bidimensionali – come ho detto prima – sono processate individualmente calcolando
due trasformate monodimensionali (una verticale ed una orizzontale).
Tale approccio può risultare molto utile in alcuni casi, ma non è sempre possibile applicarlo
ottenendo il risultato sperato in tutte le situazioni.
Consideriamo il seguente blocco che ha la peculiarità di avere una linea diagonale che divide due
regioni.
In questo caso, una trasformata bidimensionale separabile genererebbe un numero più elevato di
coefficienti non nulli, deteriorando così l'efficienza di compressione della trasformata stessa.
È proprio in questo caso che ci vengono in aiuto le trasformate direzionali.
Le trasformate direzionali sono varie e possono avere approcci e risultati diversi l'una dall'altra a
causa del loro modus operandi.
Ci sono le trasformate direzionali dipendenti dal modo che possono utilizzare diverse funzioni base,
ognuna per un bordo specifico.
Dopo aver analizzato la direzione dei bordi, selezionano quale funzione base utilizzare ed effettuano
una trasformata bidimensionale.
Ci sono le trasformate direzionali a singola dimensione ripetuta.
Nella prima fase, viene eseguita una trasformata monodimensionale sulla direzione del bordo.
Nella seconda fase, viene effettuata una trasformata monodimensionale orizzontale.
Ci sono infine le trasformate direzionali di ordinamento e bidimensionali.
In questo caso, i gruppi di dati in ingresso vengono riordinati a seconda del bordo direzionale.
Dopodiché, viene eseguita una trasformata monodimensionale per le righe e per le colonne,
similmente a quanto accade in un processo di trasformata bidimensionale.
1.6) Analisi del funzionamento di alcune trasformate prese in esame
Dopo una breve introduzione sui tipi di trasformata, procedo ora col prendere in esame le
trasformate più importanti utilizzate per la codifica video.
– Trasformata di Karhunen-Loève
La Trasformata di Karhunen-Loève (KLT) è una trasformata unitaria ortogonale non separabile,
la cui trasformata monodimensionale e la sua inversa monodimensionale per un vettore x sono
definite da:
La matrice Φ rappresenta la funzione di trasformata di Karhunen-Loève di base.
Questa trasformata non ha un insieme di funzioni base predefinite poiché le sue funzioni base sono
dipendenti dal dato di origine e sono determinate nel seguente modo:
Covarianza: la covarianza della matrice Σ è definita come
dove
è il valore dell'i-esimo dato in ingresso nel vettore x.
Autovettori ed Autovalori della covarianza computazionale della matrice: computazione della
matrice Φ degli autovettori della matrice di covarianza Σ
dove Λ è la matrice diagonale di autovalori della matrice di covarianza Σ
dove λm è l'm-esimo autovalore della matrice di covarianza Σ. Le colonne della matrice Φ
corrispondono agli autovettori della matrice di covarianza Σ, rappresentata nelle funzioni di base
della trasformata di Karhunen-Loève.
Questa trasformata è la miglior trasformata possibile in termini di compressione in quanto riesce a
codificare il segnale utilizzando il minor numero di coefficienti possibile.
Ad ogni modo, la trasformata di Karhunen-Loève utilizza delle funzioni di base dipendenti dal dato
di ingresso, il che comporta la continua computazione della matrice di covarianza del segnale in
ingresso, così come la sua memorizzazione e trasmissione.
Non solo, proprio per ottenere una codifica tanto efficiente, la trasformata di Karhunen-Loève
richiede una grande quantità di calcoli per poter determinare le funzioni di base,
il che ne aumenta la complessità.
Proprio a causa della grande quantità di calcoli richiesti, il suo utilizzo nell'ambito della codifica
video è limitato, anche se in passato era stata proposta (e non accettata) per l'H.265 HEVC.
– Trasformata Discreta di Fourier
La Trasformata Discreta di Fourier (DFT) è una trasformata unitaria ed ortogonale che è utilizzata
per scomporre il dato originale nelle sue componenti di seno e coseno.
È una trasformata unitaria bidimensionale e la sua trasformata ed inversa (per un blocco di dati
NxN) sono definite da:
Le funzioni base della trasformata discreta di Fourier corrispondono alle onde di seno e coseno con
frequenze in aumento.
Il primo coefficiente y(0,0) rappresenta i componenti DC.
A differenza di quella di Karhunen-Loève, quella di Fourier è una trasformata separabile e le sue
funzioni di base possono essere rappresentate come prodotti di due trasformate unitarie date da:
Per un vettore di lunghezza N, computare una trasformata di fourier monodimensionale richiede
N^2 operazioni aritmetiche.
Per ridurre la complessità di questa trasformata, spesso viene utilizzata un'implementazione speciale
chiamata “Trasformata Discreta di Fourier Veloce” (FFT).
Utilizzando la FFT al posto della DFT normale, è possibile ridurre le operazioni aritmetiche per la
trasformata monodimensionale ad un semplice NlogN.
La trasformata Discreta di Fourier Veloce è dunque in grado di ridurre significativamente la
complessità della Trasformata Discreta di Fourier normale ed il fatto di poter contare su una
versione “veloce” della stessa è senza dubbio un grande vantaggio rispetto alla trasformata di
Karhunen-Loève.
Ad ogni modo, la FFT ha un grande difetto che è quello di produrre nella codifica dei coefficienti
complessi (cioè con parti reali ed immaginarie) e quindi difficili da gestire, salvare e manipolare.
Viene in aiuto, in questo caso, la DCT cioè la Trasformata Discreta del Coseno (della quale parlerò
di seguito) che utilizza valori reali e non numeri complessi.
– Trasformata Discreta del Coseno
La Trasformata Discreta del Coseno (DCT) è una trasformata unitaria ortogonale concettualmente
simile a quella di Fourier (DFT) ma con il vantaggio di utilizzare solamente numeri reali (e non
complessi come quella di Fourier).
La trasformata bidimensionale per un blocco NxN è definita da:
e la sua inversa è data da:
con
Come per la trasformata Discreta di Fourier, la trasformata Discreta del Coseno può essere
rappresentata come prodotto di due trasformate monodimensionali, visto che è anch'essa una
trasformata separabile.
~ DFT e DCT a confronto
In questo grafico prendo come modello una funzione base da 8x8 sia per la Trasformata Discreta di
Fourier che per la Trasformata Discreta del Coseno, onde evidenziarne il differente funzionamento:
Trasformata Discreta di Fourier (DFT) 8x8 Trasformata Discreta del Coseno (DCT)
Dato che la funzione coseno è reale e pari cos(x) = cos(-x) ed il segnale in ingresso è anch'esso
reale, la trasformata Discreta del Coseno inversa genera una funzione pari periodica in 2N,
considerando N la lunghezza della sequenza del segnale originale.
La trasformata Discreta di Fourier inversa, invece, produce un segnale ricostruito che è periodico in
N.
La trasformata Discreta del Coseno, inoltre, introduce delle discontinuità molto più lievi di quella di
Fourier e gli errori di ricostruzione ai bordi dei blocchi sono più piccoli, di conseguenza gli artefatti
da compressione (blocking) sono meno pesanti di quelli della trasformata Discreta di Fourier.
Dall'illustrazione è facile notare come la DFT sia periodica in N e la DCT sia periodica in 2N.
Il che significa che, nella DFT, ci sono delle discontinuità tra N ed N nei punti di bordo che sono
invece evitate nella DCT.
Per quanto concerne i segnali altamente correlati, la DCT ha dei risultati di codifica molto simili
alla trasformata di Karhunen-Loève.
Ad ogni modo, a differenza di quest'ultima, le funzioni di base della DCT non sono dipendenti dai
dati in ingresso, favorendone così, ancora una volta, l'utilizzo.
La DCT, inoltre, così come la DFT, ha una versione “veloce” chiamata “Trasformata Discreta del
Coseno Veloce”.
La versione “veloce” riduce i calcoli aritmetici per una trasformata monodimensionale per un
vettore di lunghezza N a solo NlogN, esattamente come per la trasformata Discreta di Fourier
Veloce.
Grazie a tutte queste peculiarità, la Trasformata Discreta del Coseno è diventata la trasformata di
riferimento per codifiche come il JPEG, l'H.264 e l'MPEG-2 nel quale la DCT bidimensionale viene
effettuata su blocchi da 8x8 ed in seguito viene effettuata una quantizzazione dei suoi coefficienti.
Per quanto riguarda l'H.264 A VC, però, questi non si serve solamente della DCT, bensì esegue una
“seconda passata” per mezzo di un'altra trasformata: la trasformata di Walsh-Hadamard,
che illustrerò di seguito.
– Trasformata di Walsh-Hadamard
La trasformata di Walsh-Hadamard è una trasformata unitaria ed ortogonale.
È una trasformata separabile e la sua trasformata ed inversa monodimensionali per un vettore x
di lunghezza 2^m sono definite da:
dove la matrice Hm rappresenta la funzione di base della WHT.
La matrice Hm è una matrice di Hadamard da 2^m x 2^m, ovvero una matrice quadrata i cui valori
di ingresso possono essere sia +1 che -1 e le cui righe sono reciprocamente ortogonali ed è data da:
in cui 1 su radice di due è il fattore normalizzante.
La trasformata di Walsh-Hadamard, così come le precedenti due, possiede una sua versione
“veloce”, chiamata “Trasformata di Walsh-Hadamard Veloce”.
Così come per le altre sopraelencate, la versione “veloce” di questa trasformata può ridurre il
numero di operazioni aritmetiche per una trasformata monodimensionale da N^2 a NlogN.
La trasformata di Walsh-Hadamard lavora con matrici puramente reali, contenendo valori di +1 e -
1; così facendo, le operazioni che deve compiere sono limitate a calcoli molto semplici e,
soprattutto per la sua versione “veloce”, è la trasformata col più basso livello di complessità.
Ad ogni modo, proprio per la semplicità dei calcoli che effettua, la sua capacità di compressione è
altrettanto modesta, per questo il suo utilizzo autonomo è pressoché nullo nel campo della codifica
video, ma – come ho detto prima – è molto importante in quanto viene associata alla DCT per poter
ottenere una miglior compressione nel codec H.264 A VC.
– Trasformata Discreta di Wavelet
La trasformata Discreta di Wavelet è una trasformata unitaria, ortogonale e separabile che di solito è
applicata all'intero dato in ingresso e non a dei piccoli blocchi come invece accadeva per le
trasformate viste in precedenza.
La DWT di un segnale in ingresso x è eseguita passandolo attraverso vari filtri.
Per prima cosa, il segnale in entrata è decomposto usando un filtro passa basso, ovvero un filtro che
passa le basse frequenze ed attenua le alte frequenze, dopodiché viene processato da un filtro passa
alto che passa le alte frequenze ed attenua le basse frequenze.
Tale operazione è effettuata utilizzando:
dove ylow and yhigh sono rispettivamente i coefficienti di banda passa basso e passa alto.
I filtri g ed h devono essere in stretto rapporto tra loro per poter dividere il segnale in ingresso in
due bande, formando così un filtro di quadratura a specchio:
dove f è la frequenza.
Tale proprietà assicura che non ci sia alcuna perdita di informazioni durante il processo di
decomposizione.
Con l'operazione di filtraggio passa basso e passa alto, metà delle frequenze del segnale sono
rimosse in entrambe le bande.
In questo modo, è possibile utilizzare il teorema di campionamento:
se una funzione x(f) contiene frequenze che sono più piccole di B hertz, allora è determinata dando
le sue ordinate ad una serie di punti distanziati 1/(2B) secondi.
Metà dei campioni possono essere tagliati e l'output dei due filtri (g ed h) può essere
sotto-campionato per due. Tale operazione è data da:
Dopo questo processo, la maggior parte dell'energia è generalmente concentrata nella banda passa
basso.
Per poter aumentare la frequenza di risoluzione in questa banda, possono essere eseguite più
decomposizioni, ripetendo l'operazione di sopra.
Per un segnale in ingresso monodimensionale, le applicazioni successive dei filtri sull'output passa
basso risultano in una scomposizione dinamica, ovvero il numero di coefficienti per ogni nuova
banda bassa è metà del numero della scomposizione precedente.
Per un segnale in ingresso bidimensionale, il numero dei coefficienti di ogni nuova banda bassa è
un quarto del numero della scomposizione precedente.
La trasformata Discreta di Wavelet ha la peculiarità di possedere coefficienti in grado di ricostruire
varie risoluzioni spaziali.
Così come per le altre trasformate sopraelencate, la trasformata Discreta di Wavelet ha la sua
versione “veloce” chiamata “Trasformata Discreta di Wavelet Veloce” e può eseguire una
trasformata monodimensionale per un vettore di lunghezza N in sole N operazioni aritmetiche.
Tra i pregi della Trasformata Discreta di Wavelet ci sono l'assenza di blocking come artefatto da
compressione (questo perché viene applicata all'intera immagine e non a blocchi), sfrutta la
correlazione di tutti i blocchi vicini (visto che viene applicata a tutta l'immagine) consentendo alti
livelli di compressione ed ha una decomposizione dinamica ed è quindi possibile aumentare o
diminuire la risoluzione spaziale dei dati recuperati semplicemente aumentando o diminuendo il
numero dei coefficienti decodificati.
L'unico problema è che processare l'intera immagine assieme invece di dividerla in blocchi richiede
un alto carico computazionale dal punto di vista dei calcoli.
La trasformata Discreta di Wavelet è utilizzata nello Standard JPEG 2000 di cui parlerò di seguito.
2) Utilizzo delle Trasformate nei codec di codifica immagini
Al fine di esplicare l'utilizzo dei metodi di codifica all'interno dei codec video, è preferibile
affrontare prima il loro impiego nei codec di codifica di immagini statiche in quanto più semplici.
Inoltre, in questo capitolo viene rappresentato passo per passo l'utilizzo dei metodi di trasformata
visti sopra in un contesto reale e di utilizzo pratico.
2.1) Lo Standard JPEG
Lo standard JPEG utilizza due tipi di codifica: lossy (con perdita) e lossless (privo di perdita); nel
secondo caso, inoltre, non viene effettuata una codifica tramite trasformata.
È doveroso dire, comunque, che la codifica lossless è molto meno efficiente in termini di
compressione rispetto a quella lossy che, però, comporta la perdita di una parte di informazione.
Non solo, non è sempre detto che il metodo di compressione lossless riesca sempre a ridurre la
dimensione finale del file e potrebbero esserci casi in cui questo risulta essere addirittura più grande
del file di partenza!
In tale caso, quindi, è preferibile optare per lasciare il file originale invariato al posto di tenere
quello processato dalla codifica lossless.
Generalmente, il metodo più utilizzato è quello lossy ed è proprio questo a cui darò più importanza.
La trasformata utilizzata dal JPEG nella codifica lossy è la trasformata discreta del coseno
bidimensionale, unitaria, ortogonale e separabile ed è data da:
dove y(k,l) è il coefficiente alle coordinate (k,l) e x(m,n) è il valore di ingresso (di chroma –
componente del colore – e luma – immagine in bianco e nero in sé per sé) alle coordinate (m,n).
Il JPEG utilizza dunque la Trasformata Discreta del Coseno per la sua implementazione e procede
nella codifica nel seguente modo:
1) L'immagine originale viene divisa in blocchi da 8x8.
2) Ogni blocco da 8x8 viene trasformato utilizzando un'operazione di trasformata Discreta del
Coseno bidimensionale (cioè, rappresentandolo in un'opportuna base dello spazio
vettoriale); il risultato è dato da 8x8 coefficienti (quindi 64) creati dalla DCT stessa.
3) Tutti i 64 coefficienti creati dalla DCT sono poi quantizzati utilizzando una specifica matrice
di quantizzazione.
4) I coefficienti DCT quantizzati vengono organizzati in una sequenza monodimensionale a
“zig zag”.
Grazie a questa particolare sequenza, l'encoder incontrerà tutti i coefficienti DCT non nulli
del blocco il più velocemente possibile.
Non solo, dato che tale ordine corrisponde (molto approssimativamente) ad una lista
ordinata dei coefficienti di percezione visiva, il suo impiego fa sì che i coefficienti più
importanti dal punto di vista visivo siano sempre trasmessi prima di quelli meno importanti.
Dopodiché, il JPEG crea una coppia (run, level) per ogni coefficiente.
Il “run” è la quantità di coefficienti DCT nulli che precedono i veri coefficienti che vengono
codificati nella sequenza a “zig zag”.
Il “level” è la grandezza quantizzata dei coefficienti per essere codificati.
Il “run” ed il numero di bit utilizzati per codificare il “level” sono poi codificati utilizzando
la codifica di Huffman ed il “level” è codificato utilizzando il VLI (Variable Length Integer).
Per sfruttare meglio la correlazione spaziale, i coefficienti DC di ogni blocco sono codificati
come la differenza dei blocchi DC precedente e successivo.
Il processo di decodifica altro non è che l'inverso di quello di codifica: il decoder entropico
decodifica la sequenza a “zig zag” dei coefficienti DCT quantizzati e, dopo averli de-quantizzati,
vengono ri-trasformati in blocchi da 8x8.
Le matrici di quantizzazione non sono standardizzate, bensì il JPEG suggerisce una matrice di
quantizzazione utilizzando i valori corrispondenti alle minime differenze percettive di ogni
coefficiente DCT.
Questa matrice di quantizzazione di base può essere utilizzata per generare matrici di
quantizzazione di qualità più bassa semplicemente moltiplicando la matrice di partenza con un certo
coefficiente di quantizzazione intero.
I processi di quantizzazione sono prevalentemente bassi per le basse frequenze
ed alti per le alte frequenze.
In questo modo, il noise di quantizzazione è concentrato nelle frequenze di percezione visiva
minore ed è molto importante in quanto sfrutta l'irrilevanza di segnale, ovvero evita di trasmettere
informazioni di immagine che non hanno importanza a livello percettivo.
Infine, la matrice di quantizzazione (se utilizzata) deve essere trasmessa.
Chiaramente, più la quantizzazione è marcata, più il rapporto di compressione aumenterà e più la
qualità dell'immagine finale ricostruita ne sarà affetta.
È facilmente possibile percepire come l'immagine di sinistra, processata con una forte
quantizzazione JPEG, al costo di avere una codifica maggiore (e quindi occupare meno spazio)
introduca anche dei vistosi artefatti da compressione quali ad esempio il blocking, il blur (sfocatura)