1
1.8 Algoritmi di compressione
per dati, voce e immagini
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
2
1.8.1 Considerazioni generali
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
1
3
Alcuni compressori di comune impiego
Per i dati:
zip, rar
Per la voce:
DPCM, LPC, RPE-LPC-LTP (nel GSM)
Per l’audio (musica):
MP3
Per le immagini:
JPEG
Per il video:
MPEG, H263, H264
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
4
Codifica di Huffman
Esprime il carattere più frequente nella maniera più breve possibile
È il più efficiente codice senza prefissi se le frequenze di simboli
effettive corrispondono a quelle usate per creare il codice
Migliora la precedente alla codifica di Shannon-Fano costruendo un
albero ascendente anziché uno discendente
Le frequenze usate possono essere pre-calcolate, o possono essere le
frequenze trovate nel testo da comprimere (codifica adattiva)
In tal caso occorre registrare la tabella di frequenza insieme al testo
compresso; ci sono trucchi per registrare queste tabelle efficientemente
Usata a complemento di altri compressori come PKZIP ed i suoi
successori ZIP e WinRar e codec multimediali quali JPEG ed MP3
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
2
5
Compressione statistica e strutturale
La compressione è una “codificazione” dei dati da trasmettere:
di tipo statistico, sfruttando le diverse “frequenze di emissione” dei
bit o di gruppi di bit (“simboli”)
di tipo strutturale, sfruttando le caratteristiche di emissione della
sorgente di informazione (per voce e immagini, non per dati).
La compressione di tipo strutturale viene sempre seguita da una
compressione statistica
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
6
Compressione lossy e lossless
Compressione senza perdita, detta lossless: la compressione e la
decompressione non danno luogo a perdita di informazione, ovvero i
dati di partenza vengono ricostruiti con esattezza
La compressione lossless è tipica per i dati
Compressione con perdita, detta lossy: la ricostruzione non è perfetta,
l’informazione viene ricostruita con maggiore o minore
approssimazione a seconda dell’applicazione
La compressione lossy è tipica per applicazioni voce, immagini e video
a qualità non elevata (telefonia e videotelefonia cellulare,
telesorveglianza, etc.)
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
3
7
1.8.2 Codifica RLE (Run-Length encoding)
e Lempel-Ziv-Welch (LZW)
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
8
Codifica RLE (Run-Length encoding)
Di tipo lossless, cerca nei dati da comprimere una serie di elementi uguali
e la sostituisce con un solo elemento, quindi un carattere speciale e infine
il numero di volte che esso va ripetuto
ESEMPIO: Immagine con la prima riga formata da cento pixel bianchi:
RLE memorizza il primo pixel bianco poi mette il carattere speciale e poi
memorizza il numero 100 occupa 3 locazioni anziché 100
Il carattere speciale è definito diversamente da ogni implementazione
dell'algoritmo, e distingue un elemento normale da uno compresso
RLE funziona bene per immagini con pochi colori molto uniformi, ovvero
in serie di dati che abbiano molte ripetizioni al loro interno (files con
lunghe sequenze dove lo stesso byte viene ripetuto)
Elevata velocità di decompressione, è utilizzato per immagini bitmap
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
4
9
Compressione di immagini fax
“bit-map” di punti (“pixels”, picture elements) bianchi e neri
⇒ matrice di 0 e 1
parola di codice “speciale” per le linee bianche (tutti 0), molto
frequenti
per le altre linee, vengono codificate le lunghezze delle sequenze di
0 e di 1 (run-length coding)
codificazione (statistica) delle differenze dei “run” rispetto alla linea
precedente (G2) od alle 3 linee precedenti (G4)
È una compressione che sfrutta la struttura dell’immagine fax
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
10
Cenni sulla codifica Lempel-Ziv-Welch (LZW)
compressore adattivo: durante la codifica si ricava un modello della
sorgente, che poi evolve attraverso l’analisi della sequenza da
comprimere
La maggior parte delle tecniche di compressione adattive si basano sui
lavori di Ziv e Lempel del 1977 e del 1978 (algoritmi LZ77 e LZ78)
Viene creato un dizionario delle stringhe di simboli ricorrenti nel file dove
ad ogni nuovo termine viene accoppiata in modo esclusivo un'unica
stringa
Esiste un dizionario di partenza (i 256 simboli del codice ASCII) che
viene incrementato con l'aggiunta di tutte le stringhe ricorrenti nel file che
siano maggiori di un carattere
Nel file compresso viene memorizzato un codice breve che rappresenta
la stringa inserita nel dizionario così creato
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
5
11
Cenni sulla codifica Lempel-Ziv-Welch (LZW)
Esiste un insieme di regole non ambigue per la codifica del dizionario,
che permette al sistema di decompressione di generare un dizionario
identico a quello di partenza ricostruzione senza errori
Il risparmio di spazio in un file compresso con LZW dipende dal fatto
che il numero di bit necessari a codificare il "termine" che rappresenta
una stringa nel dizionario è inferiore al numero di bit necessari a
scrivere nel file non compresso tutti i caratteri che compongono la
stringa
Quanto più numerose e lunghe sono le stringhe che è possibile inserire
nel dizionario, tanto maggiore sarà la compressione del file
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
Algoritmo LZ-77
12
LZ-77: algoritmo non distruttivo, risultato delle modifiche apportate nel
1984 da Terry Welch agli algoritmi di Ziv e Lempel
Inizialmente non è noto alcun modello per la sorgente ma solamente
l’alfabeto A ed una codifica dei suoi simboli
ci si svincola dal concetto di sorgente
si sfruttano le caratteristiche di sequenza X di simboli individuate
durante la compressione
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
6
Algoritmo LZ-77
13
la codifica avviene con una finestra scorrevole composta da:
-
search buffer, con la parte di X appena codificata
-
look-ahead buffer, con il successivo segmento da codificare
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
14
1.8.3 Compressione dei segnali audio (musica e voce)
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
7
15
Compressione dei segnali audio (musica e voce)
Nella compressione dei segnali musicali si sfruttano le limitazioni della
destinazione (l’apparato uditivo), per es., la differente sensibilità alle
frequenze diverse
Nella compressione della voce si sfruttano anche le limitazioni
strutturali della sorgente (l’apparato vocale), per es. lo “spettro” di
frequenze emesse
Codificatori waveform: la forma d’onda ricostruita deve essere il più
possibile simile a quella originale
Codificatori model-based: utilizza i parametri del modello di
produzione vocale
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
16
Produzione del segnale vocale - 1
L’aria esce dai polmoni
Le corde vocali sono rilassate
oppure tese (⇒ vibrazione)
Il velo palatino è alzato o abbassato
(⇒ accoppiamento della cavità
nasale con la cavità orale)
Narici
Cavità nasale
Velo palatino
Labbra
Lingua
Polmoni
Cavità orale
Glottide
(corde vocali)
La cavità orale assume una opportuna forma (muovendo labbra e
lingua), generando un flusso turbolento e caotico.
messaggio linguistico = successione di fomeni
segnale vocale = successione di suoni
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
8
17
Produzione del segnale vocale – 2
Suoni sordi: le corde vocali sono aperte, il suono è determinato dalla
costrizione del tratto vocale, il segnale vocale è di tipo rumoroso
→ suoni labiali, dentali,…; Fricative,occlusive,…
Suoni sonori: le corde vocali sono tese e vibrano al passaggio
dell’aria, il segnale vocale presenta impulsi a struttura pseudoperiodica, con periodo detto pitch → vocali,…
Suoni misti: sono presenti entrambi le sorgenti
Esempio:
x(t )
t
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
18
Spettro a breve termine – 1
t
“C”
“A”
Intervallo di “stazionarietà”
T ≅ 20 msec
“S”
εx(f )
Spettro di energia su di
un intervallo T
⇒ analisi spettrale su intervalli
di 20 msec
5
10
f ( KHz )
No componenti alle frequenze intorno allo 0 (continua)
Energia concentrata fino a 4-5 KHz, frequenze maggiori danno tono e
timbro
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
9
19
Spettro a breve termine – 2
Il segnale vocale non è stazionario
Per uno stesso suono, può essere considerato stazionario per durate
di circa 10-30 msec → Spettro di energia a breve termine
Suoni sonori:
– spettro a righe,
– di tipo passa-basso
f
Suoni sordi:
– spettro continuo
Formanti =
Frequenze
di risonanza
(date dai poli)
Frequenza di pitch = (periodo di
pitch) -1
f
Lo spettro di fase conta poco, perché l’orecchio ne è poco sensibile
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
20
Spettro a breve termine - 3
Modello di generazione:
t
suono
sordo
Filtro
con poli
t
Periodo di pitch
segnale
vocale
suono
sonoro
Attraversamento del cavo vocale = Filtro che sagoma lo spettro
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
10
21
Generalità sui codificatori vocali – 1
I codificatori sono apparati che trasformano un segnale analogico in
un segnale numerico
I codificatori di forme d’onda digitalizzano di un generico segnale
analogico e non solamente il segnale vocale
Di questa categoria fanno parte i codificatori PCM (con bit-rate di
64kbps) e ADPCM (con bit-rate di 32kbps e qualità analoga al PCM)
I codificatori vocali veri e propri non si occupano semplicemente di
trasmettere una forma d’onda digitalizzata, ma sfruttano i
meccanismi con i quali la voce viene generata
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
22
Generalità sui codificatori vocali – 2
I codificatori vocali si basano su modelli della voce che consentono
di realizzare circuiti di sintesi del segnale vocale, in grado di
emulare l’apparato vocale umano
Sono perciò molto più complessi, introducono un ritardo che può
essere abbastanza consistente, ma consentono di ridurre
drasticamente il bit-rate
Il codificatore vocale utilizzato nel sistema GSM, avente qualità di
riproduzione analoga al codificatore PCM, viene definito codificatore
ibrido, in quanto utilizza sia i principi dei codificatori di forme d’onda
sia quelli dei codificatori vocali
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
11
23
Compressione della voce: il DPCM – 1
Nella compressione dei segnali musicali si sfruttano le limitazioni della
destinazione (l’apparato uditivo), per es.la differente sensibilità alle
frequenze diverse
Nel PCM (Pulse Code Modulation) il segnale analogico x(t) viene
campionato e rappresentato dalla sequenza dei suoi campioni x(nT)
quantizzati con un certo numero di bit a campione
Nel PCM Differenziale (DPCM) anziché quantizzare e trasmettere il
campione attuale x(nT) si quantizza e trasmette la differenza tra esso e
il campione precedente :
r(nT) = x(nT) – x((n-1)T)
⇒ numeri “piccoli”, rappresentabili con pochi bit
Codificare e trasmettere numeri piccoli, come si fa nel DPCM, “costa”
meno bit rispetto al PCM, a parità di accuratezza
L’ipotesi è che il segnale evolve lentamente da campione a campione
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
24
Compressione della voce: il DPCM – 2
Codificare e trasmettere numeri piccoli, come si fa nel DPCM,
“costa” meno bit rispetto al PCM, a parità di accuratezza
L’ipotesi è che il segnale evolve lentamente da campione all’altro
Esempio:
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
12
25
Compressione della voce: il DPCM - 3
Però così si accumulano gli errori di quantizzazione:
Soluzione: codificare la differenza tra x(nT) e la sua ricostruzione:
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
26
Codifica LPC (Linear Prediction Coding) – 1
Nella codifica LPC si calcola la predizione x’(nT) del campione attuale
x(nT) come combinazione lineare di un certo numero N di campioni
x((n-1)T),…,x((n-N)T) che lo precedono:
x’(nT) = a(1) x((n-1)T) + a(2) x((n-2)T) +…+ a(N) x((n-N)T)
dove gli a(k) sono i coefficienti di predizione
Si calcola la differenza r(nT) = x(nT) – x’(nT) (residuo di predizione)
r(nT) presenta ampiezze “piccole”, rappresentabili con pochi bit (a
parità di accuratezza)
r(nT) viene quantizzata e trasmessa (o memorizzata)
La sequenza x(nT) viene ricostruita da x(0) e dalla sequenza r(nT)
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
13
27
Codifica LPC (Linear Prediction Coding) - 2
Esempio: Predizione lineare di x(nT) “a tre passi”
x’(nT) = a(1) x((n-1)T) + a(2) x((n-2)T) + a(3) x((n-3)T)
x’(nT)
x((n-1)T)
x((n-3)T)
•
•
x((n-2)T)
Predizione
lineare
a 3 passi
•
•
•
“predizione” DPCM
•
(n-5)T (n-4)T(n-3)T (n-2)T (n-1)T nT
t
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
28
Codifica LPC (Linear Prediction Coding) – 3
Si vuole che il residuo r(n) sia piccolo, ad esempio minimizzando
l’energia:
E = ∑ r (n ) =∑ (x(n ) − x' ' (n ))
2
2
n
n
p


= ∑  x(n ) − ∑ a(k )x(n − k )
n 
k =1

La soluzione che minimizza l’energia
2
E è costituita dalle Equazioni
di Yule-Walker, che forniscono i coefficienti di predizione a(k).
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
14
29
Codifica LPC (Linear Prediction Coding) – 4
Dai coefficienti a(k) e dal residuo r(n), la sequenza x(n) è ricostruibile
esattamente come:
p
x(n ) = ∑ a(k )x(n − k ) + r (n )
(filtro IIR)
k =1
x(n)
r(n)
Analisi
Sintesi
(FIR)
x(n)
(IIR)
a(k), k=1,…,p
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
30
Codifica LPC (Linear Prediction Coding) – 5
In pratica, la sequenza x(n) viene analizzata su tratti brevi (10-30
msec) per calcolare gli a(k)
Gli a(k) vengono quantizzati e trasmessi
Viene calcolata r(n), con gli a(k) quantizzati
Viene quantizzata e trasmessa r(n)
Il ricevitore ricostruisce x(n) (a meno della quantizzazione e di errori di
canale) da a(k) e da r(n)
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
15
31
Codifica LPC (Linear Prediction Coding) - 6
Schema completo:
x(n)
Filtro di
analisi
Ritardo
r(n)
Q[r(n)]
Q
Canale
Analisi
Lp
a(k)
Q
Q[a(k)]
Filtro di
sintesi
Q[r(n)]
~
x (n
)
Canale
Q[a(k)]
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
32
Codifica LPC (Linear Prediction Coding) – 7
In alcuni schemi LPC usati in pratica, per risparmiare bits non si
trasmette la r(n), ma una sua versione approssimata (quantizzata)
a partire da questa, il ricevitore genera una opportuna sequenza di
eccitazione r’(n)
~
x(n)
Filtro di
analisi
LP
Approx.
a(k)
…
Eccitaz.
Filtro di x (n )
sintesi
…
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
16
33
Codificatore vocale RPE-LTP-LPC usato nel GSM
Filtro
di
analisi
Prex(n) proc
LP
ak
r(n)
l(n)
Q
Q-1
)
RPE
Q-1
Q
Tx,3
Tx,2
Codebook adattativo
Tx,1
s (n
s^(n)
D,G
Q
LPC
(Linear Predictive Coder)
smooth
LTP
LTP
search
a’k
~
s(n)
LTP
(Long Term Predictor)
r’(n)
+
s’(n)
Q-1
RPE
(Regular Pulse Excited)
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
Compressione della voce: Proprietà Psico-acustiche
100
Sound
Level
(dB)
34
Audible
80
60
40
20
Inaudible
0
0.02 0.05 0.1 0.2 0.5 1
2
5 10 20
Frequency
(kHz)
La soglia di udibilità dell’orecchio umano non è costante su tutto lo spettro
udibile, ma presenta un andamento variabile (particolare sensibilità alle
frequenze proprie del parlato)
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
17
Compressione della voce: Fenomeni di Masking
100
Sound
Level
(dB)
35
Audible
80
Masking tone
60
40
20
Masked tone
Inaudible
0
0.02 0.05 0.1 0.2 0.5 1
2
5 10 20
Frequency
(kHz)
La presenza di un tono ad una certa frequenza modifica l’andamento
della soglia di udibilità nelle frequenze contigue
Larghezza degli intervalli di mascheramento variabile con la frequenza
– 100 Hz (basse frequenze)
– 4 kHz (alte frequenze)
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
36
La codifica audio MP3 (MPEG Layer-3)
codifica audio di tipo percettivo che analizza il segnale ed applica
dei modelli psico-acustici
soglia minima udibile per l'orecchio umano: non lineare, ed ha un
picco tra 2kHz e 5kHz
1. Tramite filtri numerici, il segnale audio (0-48 kHz) viene diviso in 32
sottobande
2. Per ciascuna banda si calcola la soglia di mascheramento causata
dalle bande attigue: se la potenza è sotto la soglia, quella banda non
viene considerata
3. Altrimenti, si calcola il numero di bit/campione necessario affinchè il
rumore di quantizzazione sia sotto la soglia di mascheramento
4. Il flusso di bit così generato viene codificato secondo Huffman
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
18
37
1.8.4 Compressione di immagini
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
Trasformata di funzioni 2D
La trasformata di Fourier si generalizza a funzioni 2D
F (ω1 , ω2 ) =
f ( x, y ) =
∞
∫ ∫
∞
−∞ −∞
∞
∫ ∫
∞
−∞ −∞
f ( x , y ) e − j 2π ( ω1 x+ω2 y ) dxdy
F (ω1 , ω 2 ) e j 2π ( ω1 x+ω2 y ) d ω1d ω 2
Se la funzione 2D è discreta:
F(u, v) =
1 M −1 N−1
f (x, y)e− j 2 π (ux/M +vy/M )
∑
∑
MN 0 0
M −1 N−1
f (x, y) = ∑ ∑ F(u, v)ej 2 π (ux/M +vy/M )
0
0
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
19
Trasformata e spettri di alcune funzioni 2D
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
Una scena di una costruzione umana
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
20
Discrete Cosine Transform (DCT)



α (u) = 



1
per u = 0
N
2
per u = 1,..N −1
N
N−1 N−1
 ( 2x +1)uπ ) 
 ( 2y+1)vπ ) 
C(u, v) = α (u)α (v)∑ ∑ f (x, y)cos 
 cos 

2N
2N




0
0
N−1 N−1
 ( 2x +1)uπ ) 
 ( 2y+1)vπ ) 
f (x, y) = ∑ ∑α (u)α (v)C(u, v)cos 
 cos 

2N
2N




0
0
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
Lossy Image Compression (JPEG)
Le funzioni base coseno
in blocchi di 8x8
elementi (pixel)
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
21
Come interviene DCT in JPEG
E’ una variante della trasformata discreta di Fourier
– Numeri reali
– Implementazione veloce
Dimensione dei blocchi
– Blocchi piccoli
• Più veloce
• Esistono correlazioni tra pixel vicini
– Blocchi grandi
• Compressione migliore nelle regioni a bassa frequenza
(smooth)
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
DCT in JPEG
Il primo coefficiente B(0,0) è chiamato DC (componente continua) e
rappresenta l’intensità media nel blocco 8x8
basse
frequenze
Alte frequenze
orizzontali
Alte frequenze
verticali
Alte frequenze
oblique
Zig-zag scanning: si parte dalla componente continua (in alto a sinistra)
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
22
Compressione di immagini con DCT
La DCT permette la compressione perchè concentra la maggior parte
dell’informazione nelle basse frequenze
Si perde informazione poco importante (alte frequenze) tagliando i
coefficienti C(u,v) in basso a destra
Il codificatore computa l’inversa DCT – IDCT
Tabella di quantizzazione:
3
5
7
9
5
7
9
11 13 15 17 19
11 13 15 17
7
9
11 13 15 17 19 21
9
11 13 15 17 19 21 23
11
13 15 17 19 21 23 25
13
15 17 19 21 23 25 27
15
17 19 21 23 25 27 29
17
19 21 23 25 27 29 31
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
Confronto tra due fattori di compressione JPEG
89k
12k
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
23
47
La codifica JPEG per le immagini
Immagine a toni di grigio: matrice di numeri corrispondenti alla
luminosità dei pixels
Compressione JPEG (Joint Picture Expert Group): è di tipo strutturale,
sfrutta le limitazioni del sistema visivo umano
Per ogni blocco 8x8 pixel nell’immagine:
1.Si calcola la trasformata DCT (Discrete Cosine Transform)
bidimensionale
2.i coefficienti DCT di minore ampiezza vengono eliminati, i rimanenti
vengono quantizzati ed immagazzinati in un vettore e codificati con
la tecnica RLE (Run Lenght Encoding)
3.Il risultato della codifica RLE viene a sua volta codificato secondo
Huffmann
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
La codifica JPEG per le immagini
48
Decompressione:
si ricevono i coefficienti DCT quantizzati e codificati
si decodifica il codice di Huffman, ottenendo i coefficienti DCT
assunti nulli i coefficienti DCT non trasmessi, si calcola la DCT inversa
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
24
49
1.8.5 Compressione di sequenze video
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
Struttura del video in ingresso: GOB, MB
50
Il video in ingresso è costituito da una sequenza di quadri
Ciascun quadro (o frame) è diviso in blocchi da 8x8 pixel
Ciascun pixel è caratterizzato da un valore di luminanza (L) e due di
crominanza U,V
Le crominanze sono sottocampionate (4:1:1 o 4:2:0 o 4:2:2); ad
esempio, nel 4:1:1 ad un blocco 8x8 di luminanza (L) sono associati 2
blocchi 4x4 pixel per U e V
4 blocchi di luminanza e
gli associati blocchi U,V,
formano un macroblocco (MB)
Una fila di macroblocchi forma
un Group of Pictures (GOB)
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
25
La DCT (Discrete Cosine Transform)
51
Viene applicata su base blocco (es.8x8 pixel):
0 ≤ m, n ≤ 7
per 1 ≤ m, n ≤
7
Bi, j è il valore del pixel in posizione (i, j) nel blocco corrente,
Cm,n è il coefficiente del blocco trasformato.
Trasformata DCT inversa (IDCT):
0 ≤ i, j ≤ 7
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
52
La codifica video: i modi INTRA- e INTER-frame
Il codificatore utilizza la predizione Inter-frame (per ridurre la
ridondanza temporale) e la codifica a trasformata Intra-frame (per
ridurre la ridondanza spaziale)
Il modo INTRA (I) non
prevede predizione interquadro
predizione
predizione
Il modo INTER (P) esegue
predizione tra quadri
consecutivi, con eventuale
moto-compensazione
I
P
P
P
I
P
P
P
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
26
53
Codifica dei quadri INTRA - 1
Nella codifica INTRA viene rimossa solo la ridondanza spaziale,
esattamente come se fosse un’immagine fissa:
1. viene calcolata la trasformata DCT (Discrete Cosine Transform)
bidimensionale di ogni blocco 8x8
2. i coefficienti DCT vengono ordinati con una scansione a zig-zag,
eliminando quelli di minore ampiezza
3. i coefficienti rimanenti vengono quantizzati
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
54
Codifica dei quadri INTRA - 2
4. si codifica RLE (Run Lenght Encoding): ogni componente non nulla del
vettore ottenuto dopo zig-zag, viene codificata con una tripletta (LAST,
RUN, LEVEL)
5. ogni tripletta viene codificata secondo una tabella di Huffmann
6. In totale un blocco 8x8 viene codificato da 8 bit della componente
continua (DC), più i bit che rappresentano le parole VLC della codifica
entropica
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
27
Codifica dei quadri INTER
55
La codifica INTER si basa sulla eliminazione della ridondanza
temporale presente nella sequenza video
due quadri consecutivi sono altamente correlati ovvero sono in larga
parte quasi identici, tranne che nei cambi di scena
Viene codificata la differenza tra il quadro originale e la sua predizione
ottenuta tramite motocompensazione
La codifica INTER è composta da due
operazioni fondamentali: stima del
movimento (ME, Motion Estimation)
e motocompensazione (MC, Motion
Compensation)
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
La motocompensazione
56
Il quadro motocompensato viene generato a partire da blocchi
rettangolari estratti da un quadro di riferimento precedente e individuati
dai vettori di spostamento (MV, Motion Vector)
La motocompensazione
avviene solitamente a
Frame consecutivi e frame residuo:
livello di MB, assumendo
che ciascun pixel di un
MB compia la stessa
traslazione
Per ogni MB viene
stimato un vettore di
spostamento a due
componenti
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
28
Motocompensazione “block matching” - 1
57
Tipico algoritmo di motostima: block-matching, dove il vettore MV è
ottenuto misurando la discordanza fra il macroblocco corrente ed i
macroblocchi del quadro di riferimento
Funzione di costo SAD (Sum of Absolute Differences):
• Bi,j (k, l) è il pixel in posizione (k, l) entro un MB nella posizione
(i, j) del quadro corrente
• B(i - MVx),(j - MVy) (k, l) è il pixel in posizione (k, l) entro un MB
candidato nella posizione (i, j) traslata del vettore (MVx, MVy) di
un quadro di riferimento
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
Motocompensazione “block matching” - 2
58
Algoritmi di ricerca del macroblocco con SAD minima (“best-match”):
ricerca esaustiva, semplice ed accurata ma onerosa
computazionalmente
ricerca limitata non solo all’area di ricerca scelta, ma anche ad un
ristretto numero di locazioni della finestra di osservazione,
opportunamente selezionate
-> riduzione del costo computazionale, stima meno accurata dello
spostamento
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
29
Codificatori video
59
H263 richiede basse risorse di calcolo ed è usato in applicazioni
embedded quali videotelefoni (H323 ,H324), videoconferenza,
videofonini mobili (videocall UMTS, video streaming GPRS)
H264 è il sistema emergente che garantisce una grande scalabilità di
prestazioni da 10Kbit fino ai contesti Mpeg2 (10 Mbit e oltre);
prevede efficienti tecniche di recupero degli errori di trasmissione
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
60
Codificatori video
MPEG-1 (dal 1992): principalmente un formato di archiviazione, nato
per immagazzinare su CD-ROM filmati di qualità VHS
Viene applicato in contesti quali il Video-CD, precursore del DVD
Bit rate ottimale attorno a 1.152 Mbps
MPEG-2 (dal 1994): ideato per il broadcasting digitale televisivo, è
anche conosciuto come codifica DVD; il bit-rate ideale è tra 4 e 9
Mbps
MPEG-4 Sviluppato specialmente per il Web e per le apparecchiature
mobili, fornisce ottime prestazioni già a 32Kbit/sec, prevede tecniche
di recupero dell’errore praticamente perfette
R. Cusani, Teoria dell’Informazione e Codici, Roma, Ottobre 2015
30