Ringraziamenti
Ci vorrebbe una di quelle frasi introspettive di Nietzesche oppure una di quelle
ad eetto pronunciate da un personaggio storico famoso per rompere il ghiaccio
ma non è nelle mie corde.
Ho sempre visto la ne lontana e, senza accorgermene, l'ho raggiunta.
Ho il traguardo ad un passo, deciso ad attraversarlo per iniziare un nuovo
capitolo della mia vita ma prima è doveroso uno sguardo indietro per ricalcare i
passi fatti, ricordare e ringraziare le persone che hanno percorso con me anche
solo un breve periodo della mia vita universitaria.
Il mio primo ringraziamento è rivolto a mia mamma, mio papà, mia sorella
e a Jimmy che mi hanno sostenuto, a loro modo, anche economicamente, in
tutto il mio percorso universitario. Grazie e mi saprò sdebitare.
Un altro ringraziamento importante è per Alessia che ha sempre creduto in
me dal momento in cui ci siamo conosciuti e non ha mai dubitato sulla mia
riuscita nale. Insieme alla Ale ringrazio anche la sua famiglia per il sostegno
che mi hanno sempre dato.
Ringrazio i miei amici, quelli con i quali ho condiviso gioie e dolori anche
durante gli anni di università; un grazie a Opa, Il Leo, Il Pigo, Cosci e lo Iava.
Un grazie anche a tutte le altre persone che mi hanno sempre sostenuto in
questi anni di studio.
Ringrazio l'Università di Pisa per avermi dato la possibilità di conoscere
compagni di corso fantastici con alcuni dei quali è nata anche una bella amicizia
come quella con Dino, Giovanni, Il Batta, Andrea Orazzini, Saverio Pellegrini,
Luca Rimediotti, Elia Giusti, Luca Volpi, Riccardo Bortolato, Alessandro Petri,
e molti altri.
Ringrazio il mio Tutor aziendale Pierluigi Caputo che mi ha seguito ed
aiu-tato nella realizzazione della tesi e un grazie a tutte le persone del reparto M
dell'Oto Melara per la cordialità e la disponibilità che mi hanno dimostrato nei
6 mesi di stage.
Un ringraziamento speciale a mia zia Tommasina, allo zio Franco e ai gli
Giuseppe e MariaTeresa che mi hanno sostenuto ed aiutato in un momento
particolare della mia vita.
Ringrazio anche i miei nonni che, anche se lontani, mi hanno sempre fatto
sentire il loro sostegno.
Abstract
Lo sviluppo di sistemi che gestiscono e manipolano segnali video è in continuo
aumento. Molti di questi sistemi richiedono velocità di elaborazione e bassa
latenza, per questo vengono preferite piattaforme hardware programmabili come
FPGA invece di CPU general purpose. Questo perché si possono realizzare
applicazioni su FPGA in cui tutte le risorse sono ottimizzate per un processo.
In questo lavoro di tesi è stata realizzata un'applicazione speci ca su FPGA
per la manipolazione di un formato video speci co. Nel dettaglio l'obbiettivo
raggiunto era di realizzare una compressore video che avesse una latenza minore
di 2 ms, che mantenesse una buona qualità del video e che producesse un segnale
solido ai disturbi. Il formato del video da comprimere è un PAL YCbCr 4:2:2
interlacciato 8 bit per campione con un bitrate pari a 21 MB/s.
Il progetto è stato realizzato in linguaggio VHDL utilizzando il software di
Altera Quartus II per la programmazione e per le simulazioni ModelSim.
Il processo di compressione scelto per realizzare l'applicazione, tra le varie
tecniche esistenti, è il Motion JPEG. Questa tecnica eettua una
compressio-ne JPEG su ogni fotogramma del video. In questo modo si ottengono basse
latenze, vista la limitata attività computazionale richiesta dalla compressione
JPEG. In più ogni fotogramma è elaborato indipendentemente degli altri,
que-sto porta ad una maggiore robustezza ai disturbi in trasmissione perché limita
la propagazione dell'errore alla singola immagine in cui avviene.
Di contro un video Motion JPEG ha un bitrate più elevato rispetto ad
uno standard MPEG, valori che però sono compatibili con le caratteristiche
di trasmissione hardware della scheda di elaborazione video su cui è presente la
FPGA.
Il segnale video analogico proviene da una telecamera PAL ed è digitalizzato
da un decoder video prima di arrivare sui pin della FPGA.
Nel processo Motion JPEG le componenti del video sono suddivise in
ma-3
trici 8x8, ognuna della quali viene sottoposta a compressione. Sfruttando
que-sta caratteristica, occorre memorizzare solamente 8 righe del video per iniziare
l'elaborazione. Questo aspetto aiuta a mantenere bassa la latenza.
In questa versione del progetto è stato scelto di agire solamente sulle matrici
8x8 della componente Y del video, cioè di comprimere il video come se fosse in
bianco e nero.
Il sistema realizzato è composto da 2 macro blocchi:
lo Stadio d'Ingresso che si occupa di ordinare in matrici 8x8 i campioni
provenienti dal decoder e di inviarle una ad una al modulo che le comprime.
il Compressore che implementa il processo JPEG su ogni matrice 8x8.
Come detto precedentemente, occorre memorizzate 8 righe del video (costituite
da 90 matrici della componente Y) per iniziare la compressione. Iniziata la
compressione delle 8 righe appena memorizzate, lo Stadio d'Ingresso si occupa di
memorizzare le successive 8 righe, le quali verranno compresse nito il processo
sulle prime.
La frequenza di clock del sistema è stata scelta in modo che il tempo di
compressione di 8 righe sia minore del tempo di memorizzazione delle 8 righe
successive.
L'intero sistema è stato testato con il simulatore ModelSim ricreando diverse
condizioni di funzionamento. I risultati dei test funzionali sono stati positivi.
Per testare sicamente il sistema è stato utilizzato un tool fornito da Altera,
SignalTap, con il quale si possono visualizzare segnali e registri interni al sistema
altrimenti impossibili da raggiungere sicamente. Il test eettuato consiste nel
comprimere un fotogramma memorizzato sulla FPGA e di valutarne la qualità.
Con SignalTap sono stati prelevati i risultati della compressione del Frame e
decompressi con Matlab. L'immagine risultato della compressione è stata
con-frontata sia con l'immagine originale che con la stessa immagine ma compressa
da Matlab.
Per i fotogrammi compressi con il sistema è stata valutata una qualità che
è pari ad una compressione JPEG del 50% ed un fattore di compressione che
varia intorno a 1:10.
Per valutare il bitrate del sistema realizzato è stato compresso il usso video
proveniente dalla telecamera PAL ed è risultato intorno a 8 Mbit/s.
La stima della latenza massima è stata valuta in ≈ 1ms ed è relativa ad
8 righe, più precisamente è il tempo massimo che intercorre tra il primo pixel
della prima riga in ingresso e l'ultimo pixel compresso dell'ottava riga in uscita.
Il sistema realizzato più essere utilizzato in trasmissioni video per limitare
la banda occupata e in cui è richiesta una bassa latenza.
Ogni fotogramma compresso è facilmente accessibile e quindi il sistema è
adatto ad applicazioni di analisi e di editing.
L'adozione di una serie di scelte peculiari all'interno del progetto è
giusti -cata dal fatto che nelle speci che non è richiesto che il formato del video
com-presso sia compatibile con quello di un qualsiasi produttore, in quanto anche la
decodi ca è pensata per essere realizzata su FPGA con un sistema custom.
In ambito militare, questo compressore può essere utile in sistemi di tiro,
in cui l'arma da fuoco si trova distante dalla postazione di mira e quindi il
video viene compresso e trasmesso velocemente via cavo mantenendo una buona
qualità.
Un'altra applicazione realizzabile con il sistema oggetto della tesi è quella di
poter criptare, oltre che comprimere, il video così da evitare sni ng.
Indice
1 Il segnale video
10
1.1 Caratteristiche del segnale video . . . 11
1.2 Il segnale video digitale . . . 15
1.2.1 Il passaggio al video digitale . . . 15
1.2.2 Spazi di colore . . . 18
1.2.3 Formati YCbCr e il sottocampionamento . . . 19
1.2.4 Struttura del segnale video digitale. . . 20
2 La compressione video digitale
25
2.1 Standard di compressione . . . 26
2.2 Parametri di qualità . . . 28
3 Tecniche di compressione
30
3.1 JPEG . . . 30
3.1.1 Color Trasform . . . 33
3.1.2 Image partition . . . 33
3.1.3 DCT . . . 33
3.1.4 Quantization and Zig Zag ordering . . . 36
3.1.5 Entropy coding . . . 37
3.2 Motion-JPEG . . . 43
3.3 MPEG . . . 44
4 Obbiettivo della tesi e scelte progettuali
51
5 Descrizione del sistema
53
5.1 Stadio d'ingresso . . . 55
5.1.1 Campionamento . . . 55
5.1.2 Ordinamento e Ram OnChip . . . 56
7
5.2 Compressore . . . 58
5.2.1 Blocco conta indirizzo Pixel . . . 59
5.2.2 Sottrazione per 128 . . . 59
5.2.3 Blocco DCT . . . 59
5.2.4 Quantizzatore e scansione a Zig-Zag . . . 62
5.2.5 RLE . . . 62
5.2.6 Human . . . 63
5.3 Scelta della frequenza del sistema . . . 65
6 Test eettuati
67
6.1 Test funzionali . . . 67
6.2 Test sici su FPGA . . . 68
6.2.1 Compressione di un Frame . . . 68
6.2.2 Test con SignalTap . . . 72
6.2.3 Bitrate del sistema . . . 75
6.2.4 Stima della latenza . . . 75
7 Conclusioni
76
A Tabelle
78
Introduzione
Elaborare segnali video con sistemi basati su tecnologia FPGA si sta molto
sviluppando in questi ultimi anni.
Sistemi di riconoscimento oggetti, sistemi di inseguimento di targhet, sistemi
di assistenza al parcheggio di automobili, sistemi di compressione video, ecc...
sono solo alcune applicazioni che processano segnali video e che possono essere
realizzati su FPGA.
In questa tesi mi sono occupato di realizzare un sistema che eettui una
compressione video per un formato video PAL implementando la tecnica Motion
JPEG. La scelta di utilizzare l'algoritmo M-JPEG è stata guidata dalle speci che
di latenza, solidità e qualità del video del progetto da realizzare.
Dopo un lungo studio sui vari standard esistenti, descritti dettagliatamente
nei Capitoli 2 e 3, ho eettuato dei confronti tra di loro ed il M-JPEG è risultato
il più consono per le speci che. Nel Capitolo 4 sono esposti le argomentazioni
più importanti che hanno portato alla scelta della Motion JPEG.
La FPGA utilizzata è una Cyclone V GXBC7D6F31C7 ed il sistema è stato
scritto in linguaggio VHDL.
Le varie IP realizzate sono singolarmente descritte nel Capitolo 5. Queste
sono state tutte testate con ModelSim per veri care che il funzionamento sia
quello desiderato.
I test del sistema su FPGA, descritti nel Capitolo 6, hanno dato buoni
risultati e hanno provato il corretto funzionamento del sistema. In più sono
anche visibili alcune immagini che mostrano la qualità dei Frame compressi dal
sistema.
Capitolo 1
Il segnale video
I segnali video sono la sola via per trasferire informazioni visive da un punto ad
un altro. Queste informazioni posso provenire da un DVD player, da una canale
di trasmissione broadcast, da un sistema satellitare, da Internet o da qualsiasi
altra sorgente. Inevitabilmente le informazioni video devono essere trasmesse
da un dispositivo ad un altro come per esempio da un satellite ad un set-top box
oppure da un DVD player ad una televisione. La trasmissione potrebbe avvenire
anche all'interno di un sistema tra più chip. Tutto questo signi ca che il segnale
video è utilizzato in molti sistemi e quindi deve soddisfare diversi requisiti.
Fino a qualche anno fà la maggior parte delle apparecchiature video erano
progettare principalmente per gestire segnali video analogici. Il video digitale
era con nato ad applicazioni professionali come video editing.
La maggior parte dei dispositivi video ora utilizza segnali video digitali a
causa della diminuzione dei costi avvenuta degli ultimi anni. Questo ha portato
a sviluppare DVD player, set-box digitali, televisione digitale, e la capacità di
trasmettere segnali video attraverso la rete.
Inizialmente il segnale video conteneva solo informazioni sulla scala di
gri-gio (in bianco e nero). In seguito fù sviluppato il modo di trasmettere anche
informazioni di colore usando la tecnica RGB (red, green, blue). Questa
tec-nica però occupava più di 3 volte la banda utilizzata dal segnale in bianco e
nero. In alternativa fù sviluppato la trasmissione Y, R-Y e G-Y formata da un
solo segnale, invece di tre, che occupava la stessa banda del segnale in scala di
grigi. Il segnale video così strutturato è chiamato Video Composto (Composite
video signal) ed è la base degli standard video NTSC, PAL e SECAM tuttora
utilizzati. Le componenti R-Y e G-Y sono chiamate componenti di crominanza.
I primi a trasmettere a colori furono gli americani con il sistema NTSC. Gli
altri due standard, il SECAM per la Francia ed il PAL per il resto dell'Europa,
sono stati derivati dalla NTSC con piccoli miglioramenti. Il PAL è nato nei
laboratori della Telefunken ed è in uso dal 1967. Il SECAM, anche lui usato dal
1967 è stato adottato con varianti dall'USSR, alcuni paesi dell'est e dall'Algeria.
Una variante del segnale video analogico Y, R-Y e G-Y utilizzata
comune-mente ora dai prodotti di consumo che trattano segnali video è la YPbPr. Il
principale vantaggio è quello di riuscire a trasferire video ad alta de nizione.
1.1 Caratteristiche del segnale video
Un segnale analogico descrive l'andamento nel tempo di una grandezza sica
che può assumere in niti valori in un certo intervallo.
Nell'ambito del segnale video è del tutto indierente da questo punto di
vista considerare l'andamento dell'intensità luminosa di un'immagine oppure
l'andamento della tensione o della corrente in uscita da un apparato trasduttore
(in pratica: una videocamera). Piuttosto con il video nasce la complicazione
che, l'informazione acquisita, ha una duplice natura spaziale e temporale in
quanto una scena è uno spazio tridimensionale in cui si muovono degli oggetti
mentre un segnale elettrico, che varia nel tempo, è una successione continua e
monodimensionale di valori.
Per superare questa di coltà innanzitutto si passa da uno spazio
tridimen-sionale alla sua proiezione bidimentridimen-sionale su di un piano. Questo passaggio è
la medesima azione che svolge il nostro cervello. Successivamente l'immagine
bidimensionale viene scandita in maniera continua dall'alto verso il basso e da
sinistra verso destra percorrendo una traiettoria simile a quella della scrittura
su di una pagina. Supponendo di avere immagini in bianco e nero, si
ottie-ne in questo modo l'andamento dell'intensità luminosa su tutta l'immagiottie-ne e
questa informazione, assieme al numero di linee per immagine e alla larghezza
della linea, è su ciente per ricostruire l'immagine nel ricevitore. In ne si
ripe-te tale operazione su di un certo numero di immagini otripe-tenuripe-te fotografando la
scena diverse decine di volte al secondo, si rende così l'impressione del
movi-mento similmente a quanto avviene con i fotogrammi nel cinema e con i cartoni
animati.
Figura 1.1: Progressione temporale delle immagini
Le immagini che compongono il segnale video possono avere diverso aspetto. Di
solito sono rettangolari con un rapporto fra larghezza ed altezza pari a 4/3 (4:3)
oppure 16/9 (16:9). Questo deriva sia dal fatto che il campo visivo umano è più
esteso in larghezza che in altezza.
Continuità delle immagini.
Le immagini vengono costruite sullo schermo del televisore mediante un
proce-dimento sequenziale (detto scanning process o scansione) studiato in modo da
creare un'illusione di continuità fra le varie immagini. In realtà sullo schermo,
ad ogni istante, è presente solo una piccola parte di una immagine: il sistema
visivo umano ha però una persistenza tale per cui lo stimolo luminoso resta
presente per circa 1/16 di secondo dopo la scomparsa dello stimolo sico. E'
quindi su ciente che vi siano più di sedici immagini al secondo per permettere
l'illusione della continuità.
Nel sistema PAL vi sono 25 immagini complete al secondo (30 nell'NTSC),
costruite riga per riga dal sistema di scansione. Gli schermi da PC arrivano
anche a 70-90 immagini al secondo.
Esistono delle informazioni speciali utili a sincronizzare il dispositivo che
riceve i video con il video stesso. Questi segnali sono 3: uno è il vertical sync,
che serve ad indicare l'inizio di una nuova immagine, un altro segnale speciale è
horizontal sync, che indica invece l'inizio di ogni riga che compone l'immagine.
Il terzo segnale è il eld sync che divide l'intera immagine in due parti ed indica
il passaggio da una metà all'altra (nei video interallacciati distingua il primo
dal secondo eld).
Questi segnali speciali posso essere trasferiti in tre modi diversi:
1. Trasmessi separatamente.
2. Trasmessi insieme, combinazione tra i due segnali.
3. Trasmessi Embedded, all'interno del segnale video.
Numero di linee per scansione.
La stima del numero di linee necessarie per una buona visione del segnale
televisivo può essere fatta ssando una distanza minima dell'osservatore dallo
schermo pari a quattro volte l'altezza dello stesso. Considerando che l'occhio
risolve particolari che distano fra loro non meno di 1/60 di grado, un semplice
calcolo indica in circa 860 il numero di linee necessario per uguagliare il potere
di risoluzione del sistema visivo. In pratica, anche a causa del fatto che le
immagini sono presentate in rapida successione, sono su cienti fra 500 e 600
linee per raggiungere una risoluzione accettabile.
Interallacciato e Progressivo.
La scansione di singole immagini, riga per riga dalla prima all'ultima è detta
tecnica progressiva o non- interallacciata. La scansione avviene da sinistra a
destra e dall'altro verso il basso a partire dall'angolo in alto a sinistra.
La tecnica di interlacciamento fu introdotta nei primi anni di televisione
per ridurre le informazioni inviate di ogni immagine e aumentare il refresh dello
schermo così da ridurre lo sfarfallio dovuto ai fosfori del tubo catodico. In questo
modo le informazioni trasferite vengono dimezzate perché dall'immagine intera
si ricavano due semi immagini (semi quadri), una composta solo da righe pari
e l'altra da righe dispari. Questi due semi-quadri vengono inviati uno alla volta
alternativamente dimezzando così la bande del segnale trasmesso.
Il video interallacciato oggi è utilizzato ancora in molte trasmissioni
broad-cast e con display LCD anche se sore di un altro tipo di sfarfallio intrinseco
della tecnica di interlacciamento. In questo caso il problema deriva dal fatto che
le righe scansionate sullo schermo non sono consecutive ma, come già detto,
al-terne causando uno sfarfallio visibile sui bordi degli oggetti. Il video progressivo
è, per esempio, utilizzato nei display dei PC, con i quali si riesce ad avere una
Figura 1.2: A sinistra scansione progressiva A destra scansione interallacciata.
risoluzione maggiore in verticale; in più non sore del problema visivo descritto
sopra appunto perché le righe sono scansionate con ordine continuo.
In base ai parametri descritti, ma non solo, possiamo descrivere diverse
de nizioni del segnale video:
DEFINIZIONE STANDARD: il video è di solito formato da 480 o 576
righe attive interallacciate ed è comunemente chiamato 480i e 576i. In
display a pixel ssi (non a tubo catodico) e con dimensioni geometriche
4:3 la risoluzione in de nizione standard è di 720x480i oppure 720x576i.
DEFINIZIONE MAGGIORE: Le righe attive sono sempre 480 o 576 ma
in questo caso vengono scansionate in modo progressivo (480p o 576p).
Con schermi a pixel ssi con proporzioni 4:3 si hanno risoluzioni 720x480p
e 720x576p, mentre con proporzioni 16:9 le risoluzioni sono 960x480p o
960x576p. Come si può notare la dierenza tra la de nizione standard e
quella maggiore è la scansione, la prima interallacciata e l'altra progressiva.
ALTA DEFINIZIONE: Solitamente un video è de nito in alta de nizione
quando ha 720 righe progressive oppure quando ha 1080 righe
interallac-ciate. L'alta de nizione utilizza una proporzione geometrica di 16:9 e con
display a pixel ssi raggiunge risoluzioni di 1280x720p o 1920x1080i.
La FULL HD ha 1080 righe progressive con una risoluzione di 1920x1080.
1.2 Il segnale video digitale
1.2.1 Il passaggio al video digitale
Se partendo da un segnale analogico si vanno a vedere i valori (detti
campio-ni) assunti dalla grandezza ad intervalli regolari di tempo (detto periodo di
campionamento) e si rappresentano tali valori mediante numeri binari, allora la
sequenza di `0' e `1' che si ottiene è il segnale digitale corrispondente.
In Figura 1.3 e 1.4 sono mostrati un segnale video PAL e un NTSC analogici
composti che verranno campionati e trasformati in uno stream digitale. La
frequenza di campionamento è decisa in base alle caratteristiche del video.
60 Hz =⇒
indica che la sequenza video è composta da 30 frame al secondo (60
eld al secondo se interallacciato)
f
linea= 15.750 KHz =⇒ T
linea≈ 63.5 µS
Figura 1.3: Segnale video NTSC, 525 righe totali, 60 Hz
50 Hz =⇒
indica che la sequenza video è composta da 25 frame al secondo (50
eld al secondo se interallacciato)
f
linea= 15.625 KHz =⇒ T
linea≈ 64 µS
Figura 1.4: Segnale video PAL, 624 righe totali, 50Hz
a tubo catodico perché è il periodo durante il quale il pennello elettronico ritorna
ad inizio riga.
Lo standard ITU-R BT.601 ha de nito la frequenza di campionamento
della luminanza pari a 13.5 MHz e dei segnali di colore a una frequenza
dimez-zata, pari a 6,75 MHz per il video SD. Al ne di consentire un determinato
livello di compatibilità tra diversi sistemi digitali, il valore 13.5 MHz è stato
scelto perché un multiplo intero delle frequenze dei sistemi televisivi a 525 e 625
linee.
Siccome i valori numerici hanno una precisione limitata, legata al numero
di bit usati, essi non possono rappresentare tutti i valori assunti dal segnale
analogico e questi vengono perciò arrotondati o quantizzati. Inoltre anche
la scelta del periodo di campionamento incide sulla fedeltà con cui può essere
riprodotto il segnale originale. Tuttavia, sia l'errore di quantizzazione sia quello
dovuto al campionamento possono essere controllati e, se necessario, resi
tra-scurabili rispetto all'errore comunque introdotto dallo strumento analogico che
fornisce il segnale originale.
In compenso, un segnale convertito in digitale acquista una straordinaria
resistenza al rumore introdotto dal sistema attraverso cui esso passa. Se
infat-ti ad un segnale analogico viene aggiunta una pur piccola quaninfat-tità di rumore
esso non può più essere riportato esattamente alla condizione originale perché
i valori assunti dalla grandezza interessata sono tutti possibili e non si riesce
quindi a distinguere il segnale vero dal rumore addizionale; inoltre un
ampli- catore usato per compensare l'attenuazione del canale trasmissivo ampli ca
indiscriminatamente anche il rumore e ne introduce del nuovo dovuto alle
pro-prie imperfezioni. In questo modo il rumore si accumula durante la trasmissione
del segnale no a livelli potenzialmente inaccettabili. Al contrario, il ristretto
e ben de nito insieme di valori che può assumere un segnale digitale permette
di distinguere facilmente il rumore purché questo non sia troppo intenso. Se
poi il rumore fosse tale da trasformare un valore in un altro altrettanto lecito,
allora è ancora possibile rivelare e correggere questi errori tramite opportune
tecniche, denominate in generale, codici di rilevazione e correzione degli errori
(CRC, codici di parità, ecc. ). Ciò rende possibile trasmettere un segnale video
di elevata qualità con relativa facilità e a costi potenzialmente minori rispetto
al caso analogico, dove la qualità si ottiene a costi nettamente più alti.
La proprietà dei segnali digitali di essere rigenerati esattamente senza
in-troduzione di rumore implica anche che un segnale video digitale può essere
duplicato senza perdita di qualità, elemento molto importante in applicazioni
da studio di registrazione e nell'editing delle sequenze.
Il video digitale si presta inoltre ad essere manipolato per mezzo di calcolatori
e può quindi venire usato per la produzione di eetti speciali. La capacità
di manipolare il video digitale ha raggiunto ormai un livello così avanzato che
sequenze di azioni reali possono essere fuse apparentemente senza nessuno stacco
visivo con immagini generate dal computer. Tuttavia un segnale digitale occupa
più banda di quello analogico da cui deriva ed in un certo senso è questo il
prezzo della sua quasi totale immunità al rumore: da qui nasce l'esigenza di
utilizzare tecniche di compressione. Se il segnale audio digitale può ancora
essere ospitato senza compressione su supporti ottici, quello video occupa troppo
spazio e persino i più capaci hard disk oggi disponibili potrebbero solo contenere
lmati di pochi minuti.
1.2.2 Spazi di colore
Com'è noto ogni immagine che compone il usso video può essere vista come
una matrice bidimensionale di picture element detti anche pixel. Ogni pixel
rappresenta il valore (inteso in senso lato) codi cato in maniera digitale
dell'im-magine in quel punto. Se il video, e quindi le immagini che lo compongono, è in
bianco e nero il valore del pixel dà una misura dell'intensità del grigio in quel
punto. Se invece si tratta di una sequenza a colori, un solo valore è insu ciente
a descrivere un pixel.
Uno spazio di colore è la combinazione di un modello di colore e di una
appropriata funzione di mappatura di questo modello.
Un modello di colore, infatti, è un modello matematico che descrive un
mo-do per rappresentare i colori come combinazioni di numeri, tipicamente tre o
quattro valori detti componenti di colore. Questo modello è una
rappre-sentazione astratta, per questo viene perfezionato da speci che regole adatte
all'utilizzo creando uno spazio di colore.
La più nota rappresentazione delle immagini a colori in formato digitale
associa tre valori ad ogni pixel, basandosi sul fatto che tutti i colori possono
essere ottenuti con un opportuna miscela di tre colori di base.Come colori di
base sono stati scelti il rosso, il verde e il blu e perciò tale rappresentazione viene
chiamata RGB (Red, Green, Blue) ed è uno spazio di colore. Di conseguenza
ad ogni pixel sono associati tre campioni ed i loro valori danno il peso delle
componenti di colore rosso, verde, blu.
Figura 1.5: Spazio di colore RGB
Figura 1.6: Range dei valori delle componenti dello spazio RGB
1.2.3 Formati YCbCr e il sottocampionamento
Un altro modello di colore è YCbCr. Esso è composto da una componente (Y)
che indica la luminosità del pixel e due componenti di crominanza (Cb e Cr) che
indicano il colore. Esiste una relazione matematica precisa tra RGB e YCbCr
che è descritta nella Figura 1.7. Il range di valori che le componenti del nuovo
spazio di colore possono assumere è minore rispetto a RGB, Figura 1.8.
Lo spazio di colore YCbCr può avere vari formati in base al numero di
campioni associato ad ogni pixel. I formati posso essere 4:4:4 , 4:2:2, 4:1:1 e
4:2:0. Il formato 4:4:4 indica che ogni pixel è rappresentato da tre compioni,
una di luminosità Y e sue di colore Cb e Cr. Ogni campione è composta da 8 o
10 bit quindi per ogni pixel ci sono 24 o 30 bit (come per RGB).
Figura 1.7: Conversione tra RGB è YCbCr. A sinistra SD video, a destra HD
video.
Figura 1.8: Range delle componenti del formato YCbCr
Quando occorre diminuire le dimensioni del video si provvede a sotto
cam-pionare realizzando un formato che associa meno campioni ad ogni pixel.
Un esempio è il formato 4:2:2 che associa ad ogni pixel un campione Y
mentre i campioni Cb e Cr sono relativi a due pixel. Così facendo per ogni pixel
abbiamo 16 o 20 bit, in base al numero di bit dei singoli campioni.
Figura 1.9: Esempi di sottocampionamento
1.2.4 Struttura del segnale video digitale.
Ogni standard video ha una sua struttura del usso digitale che dipende da
molti fattori tra i quali :
numero di frame al secondo.
video progressivo o interallacciato.
numero di righe per frame.
spazio di colore.
sotto campionamento.
ecc. . . ..
Le raccomandazioni ITU de niscono i parametri fondamentali per rappresentare
le immagini, quali la struttura e la frequenza di campionamento, il numero di
quadri al secondo e il numero di righe che costituiscono ciascuna immagine.
Inizialmente le raccomandazioni, come la BT.601, non si occupano di
de -nire le modalità e le caratteristiche elettriche necessarie per interfacciare i vari
apparati perché il segnale più diuso era quello analogico e le connessioni erano
eseguite con la presta SCART. La raccomandazione ITU-R BT.656 incluse
anche le speci che tecniche che riguardano l'interfacciamento di tipo digitale, in
particolare sono de nite le interfacce sia parallele che seriali.
Questa raccomandazione fù sviluppata per trasmissioni di video digitale
YCbCr in con gurazione 4:2:2 con risoluzioni 720 x 480 (525 righe totali e
60Hz) e 720 x 576 (625 righe totali e 50Hz). L'interfaccia parallela è composta
con campioni da 8 o 10 bit multiplati che vengono trasmessi ad una frequenza
di 27MHz, quindi con un periodo per campione pari a 37.037nS.
Figura 1.11: Flusso video PAL digitale di una riga attiva 8 bit (625 righe)
Nella Figure 1.10 e 1.11 sono mostrate le composizioni del video digitale PAL
e NTSC. Come si nota le informazioni sui segnali di sincronizzazione H, L e F
sono contenuti del segnale (Embedded), precisamente sono indicati dai codici
SAV (Start of active video) e EAV (End of active video).
I due codici sono formati da 4 parola da 8 o 10 bit ognuna (in base ai bit
per campione) e sono strutturati come da tabella in Figura 1.12.
Figura 1.12: Struttura SAV ed EAV
Dalla tabella si può notare che le informazioni sui segnali di sincronismo
sono contenuti nella word XY di cui i bit hanno il seguente signi cato:
F=0 indica il eld 1, F=1 indica il eld 2.
V=1 indica il blancking verticale.
H=0 indica SAV, H=1 indica EAV
P3 = V⊕ H
P2 = F ⊕ H
P1 = F ⊕ V
P0 = F ⊕ V ⊕ H
L'intero frame di un sistema video interallacciato 525/60 e 625/50 è illustrato
in Figura 1.13 e Figura 1.14.
Figura 1.13: Frame NTSC 525i
La Figura 1.15 mostra la temporizzazione di una riga attiva di un video PAL
YCbCr 4:2:2 in uscita da un decoder.
Capitolo 2
La compressione video
digitale
Ormai da anni il video digitale ha sostituito quello analogico e questo grazie
all'elettronica che ha saputo gestire sempre meglio lo stream del video digitale.
Con il passare del tempo la qualità del video digitale è aumentata e con essa
anche le informazioni contenute, incrementando così la mole di dati da dover
gestire.
Nella progettazione di un sistema che deve gestire uno o più ussi video,
uno dei primi problemi che il progettista deve arontare è l'immagazzinamento
o la trasmissione a distanza dello stream video. Questa problematica
riguar-da le grandi dimensioni di questi segnali video, si pensi al problema di dover
trasmettere un lmato video digitale con dimensione 720×576 (standard PAL).
Studiamo l'esempio in cui lo stream è composto da 8 bit per campione e con 3
componenti di colore (R, G, B); ogni frame è composto da 720 × 576 = 414720
pixel, la frequenza delle immagini è 25frame/s quindi, moltiplicando il numero
dei pixel per le tre componenti e per gli 8 bit a campione, tutto moltiplicato per
25 f rame/s
si ricava la banda necessaria per la trasmissione di quello stream,
248832000 bit/s ≈ 250 M bit/s.
Il video digitale trattato nella tesi è un formato PAL 4:2:2 YCbCr con 8
bit per campione, per trasmetterlo senza alcuna compressione occorrerebbe una
banda di
(720 × 576)
luminance|
{z
}
+ 2 × (360 × 576)
color|
{z
}
× 8 bit × 25 f rame/s =
165888000 bit/s ≈ 166 M bit/s.
25
I canali di telecomunicazione hanno un'intrinseca limitatezza in termini di
capacità di trasportare dati: un risparmio di banda comporta quindi
inevita-bilmente una diminuzione dei costi nel realizzare i sistemi. Per questo motivo
numerosi gruppi di ricerca sia nel mondo dell'industria sia in quello accademico
hanno sviluppato, e sviluppano ancora, algoritmi per ridurre la mole di dati dei
ussi video.
2.1 Standard di compressione
Due grandi gruppi hanno contribuito nel tempo a realizzare i vari standard
ri-guardanti le compressioni video e sono il Video Coding Experts Group
dall'ITU-T e il Moving Picture Expert Group dall'ISO/IEC. Questi due gruppi,
collabo-rando anche tra loro, hanno realizzato i seguenti standard di compressione:
H-261=⇒Fu il primo standard di codi ca video ed è stato la base di tutti
gli altri che sono stati realizzati in seguito(1, 2, H-263,
Mpeg-4, Mpeg-7). Retti cato nel 1990 e si riferisce alla parte di compressione
video per le videoconferenze su linee ISDN.
MPEG-1=⇒Il nome sta per Moving Picture Experts Group ed è uno
standard di compressione audio e video introdotto nel 1992. MPEG-1 è
stato il primo codec video MPEG ad essere diuso. Questo standard è
stato studiato principalmente per applicazioni video su CD-ROM e quindi
con un bitrare massimo di 1.5 Mbit/s. Per ottenere questo risultato la
risoluzione video è stata limitata a 352 × 288 pixel per i sistemi con
fre-quenza di quadro di 25 Hz e di 352 × 240 per quelli a 30 Hz.
Lo standard è diviso in tre parti che de niscono, oltre il tipo di
compres-sione video, quella audio ed il sistema di multiplexing cioè la tecnica
di fusione dei due ussi audio e video in un unico usso in modo da
po-ter essere correttamente riprodotti contemporaneamente. L'MPEG-1 è lo
standard utilizzato nei VideoCD il quale fornisce una qualità video simile
a quello delle cassette VHS.
MPEG-2=⇒Nel 1994 il Moving Pictures Experts Group ha rilasciato lo
standard MPEG-2 inizialmente pensato per le trasmissioni televisive con
bitrate no a 10 Mbit/s. Successivamente lo standard venne ampliato per
utilizzarlo nel sistema TV ad alta de nizione HDTV raggiungendo alte
risoluzioni ( no a 1920 × 1080) ed utilizzabile sia con sequenza
progres-siva che interallacciata con un bitrate di 2-40 Mbit/s. L'MPEG-2 e
sta-to adottasta-to dall'ITU-T per le telecomunicazioni con la raccomandazione
H.262.
H-263 =⇒Lo standard H-263 è stato sviluppato da ITU-T Video
Co-ding Expert Group nel 1995 per applicazioni riguardanti video conferenze
real-time. Inizialmente era caratterizzato da un basso bitrare,
tipicamen-te da 20 a 30 Kbit/s, quindi occorrevano di alti livelli di compressione
ma questa limitazioni fù superata in seguito. L'e cienza raggiunta dal
complesso degli algoritmi di compressione portati da H-263, ne fanno un
valido strumento in varie aree applicative. Questa comprendono oltre alla
videoconferenza la videotelefonia, lo streaming si Internet, la telemedicina,
i sistemi di sorveglianza e molti altri ancora.
MPEG-4 =⇒Terminato nel 1999 ha portato a miglioramenti
dell'e -cienza della codi ca, alla de nizione di nuovi algoritmi per bassi bitrate e
all'introduzione della compressione orientata agli oggetti.
Lo standard MPEG-4 è stato concepito per applicazioni multimediali
estre-mamente dierenziate dal punto di vista dei dati stessi (audio, video,
im-magini sse), della natura delle sorgenti di dati (naturali o sintetiche), della
architettura di comunicazione (punto-punto, ecc..) e dalle funzionalità
ri-chieste (post-elaborazione avanzata, editing e manipolazione, robustezza
agli errori).
Alcune delle aree in cui è risultato particolarmente utile lo standard sono:
Distribuzione di dati a qualità televisiva, con avanzata interattività
dell'utente.
Comunicazioni multimediali per utenti mobili.
Produzione di dati multimediali con elevata essibilità rispetto al
contenuto.
Giochi e applicazioni di intrattenimento basate su dati naturali e
sintetici.
Video Streaming su Internet.
MPEG-7 o H-264 (MPEG-4 Parte10/AVC) =⇒Nel 2003 Moving
Picture Expert Group con ITU-T Video Coding Experts Group hanno
sviluppato lo standard MPEG-4 AVC (advanced video coding )
chiama-to anche H.264. Nel 2012 i due team rilasciarono la prima versione dello
standard High E ciency Video Coding (HEVC), il successore della H-264.
Lo standard MPEG più recente è utilizzato per la codi ca video per
HD-DVD e per i Blue-ray HD-DVD.
É praticamente lo standard video più utilizzato al mondo perché un
codi- catore che supporta lo standard H-264 è in grado di ridurre le dimensioni
dei le video digitali di oltre 80% rispetto al formato Motion JPEG e
no al 50% rispetto allo standard MPEG-4, senza però compromessi in
termini di qualità delle immagini. Ciò signi ca che, per la gestione dei le
video, è necessario meno spazio per la memorizzazione e meno larghezza
di banda, ovvero che è possibile ottenere immagini di qualità più elevata
a parità di velocità di trasmissione in bit.
2.2 Parametri di qualità
Per quanti care la qualità di un processo di conversione si utilizzano i seguenti
parametri:
1. Il Bit-rate, cioè il numero di bit necessari a riprodurre un secondo di
informazione digitale(video o audio) o il bit/pixel che indica il numero
medio di bit con cui ogni pixel dell'immagine è codi cato (tra 0.2 a 1.5).
2. Il Rapporto di compressione o Tasso di compressione.
R
compr=
N umero bit originario
N.bit f ile compresso
Il tasso di compressione può anche essere espresso come:
(a) rapporto fra il rate (bit/s) dell'informazione originaria e il
Bit-rate dell'informazione compressa.
(b) rapporto fra il numero di campioni al secondo (samples/s)
dell'infor-mazione originaria e il numero di campioni al secondo
dell'informa-zione compressa.
3. La qualità di una immagine che è passata attraverso un processo di
com-pressione e decomcom-pressione deve essere giudicata anche soggettivamente.
4. La misura dell'errore più utilizzata è l'errore quadratico medio o la
sua radice quadrata, RMS.
i(x, y) =
immagine di input NxN pixel
d(x, y) =
immagine compressa e decompressa, NxN pixel
e(x, y) = d(x, y) − i(x, y)
E
2=
1
N
N −1X
x=0 N −1X
y=0e
2(x, y) =
1
N
N −1X
x=0 N −1X
y=0[d(x, y) − i(x, y)]
25. L'errore dierenza tra l'immagine originale e la trasformata è rumore, si
può misurare l'errore come rapporto segnale rumore SNR.
P SN R
=
max potenza segnale
E
2= 20 log
10(
(255)
2E
2Capitolo 3
Tecniche di compressione
Le rappresentazioni digitali delle immagini, delle sequenze video e dell'audio
possiedono una considerevole ridondanza statistica di valori. All'interno
del-le immagini o del singolo fotogramma esistono deldel-le ridondanze che vengono
sfruttare nella compressione:
Ridondanza statistica: si sfrutta nella compressione dati sfruttando le
proprietà statistiche dei dati stessi.
Ridondanza spaziale: si riferisce a diversi piani colore o bande spettrali.
Ridondanza spettrale: relativa a diversi piani colore o bande spettrali.
Ridondanza temporale: correlazione fra frames adiacenti in una
suc-cessione di immagini (sono in applicazioni video).
In più c'è da tenere in considerazione che dal punto di vista precettivo molte
informazioni sono irrilevanti. Équindi possibile sfruttare tutte le ridondanze e
irrilevanze per ridurre la quantità di dati. Le tecniche di compressione operano
proprio in questi senso.
3.1 JPEG
L'acronimo JPEG identi ca il comitato Joint Photographic Expert Group
dell'ente nominativo internazionale ISO/CCITT che ha creato lo standard
omo-nimo.
All'aumentare (da sinistra a destra) del tasso di compressione, si ha una
di-minuzione della qualità e la comparsa di alterazioni come la quadrettatura o
blocking, la sfocatura (blurring o blur) e il fenomeno del Gibbs (ringing).
Figura 3.1: Immagine JPEG a diversi livelli di compressione.
JPEG è fondamentalmente lo standard internazionale (approvato ne 1992)
per la compressione di immagini sse a tono continuo, sia a livelli di grigio, sia
a colori.
Il valore del rapporto di compressione di JPEG non è sso, ma è
determinabi-le dall'utente (con programmi di visualizzazione a foto ritocco, come Photoshop,
Adobe e ACSee, ACD System) e può arrivare no a 50:1.
Con un rapporto di compressione di 15:1 non si altera visibilmente la qualità
dell'immagine originaria. JPEG riesce a comprimere una foto a colori con un
tasso di compressione di 20:1.
JPEG memorizza le immagini a colori con 24 colori per pixel, cui
corrispon-dono 2
24= 16, 8
milioni di colori.
Il formato JPEG è adatto alla codi ca/compressioni di fotogra e, quadri
naturalistici e immagini con molte sfumature di colore, mentre non rende bene
i fumetti, i disegni (linee sottili in contrasto con lo sfondo), i caratteri e, in
generale le immagini con pochi colori distribuiti ciascuno su una grossa area.
La compressione attuata da JPEG sfrutta la scarsa sensibilità dell'occhio
umano alle piccole variazioni di colore (in confronto alle variazioni di
lumino-sità), per cui, in presenza di due pixel di colore quasi uguale, ne conserva uno
solo. Sfrutta inoltre il fatto che l'occhio umano è in grado di rilevare bene le
pic-cole dierenze di luminosità su una super cie relativamente grande,ma è meno
sensibile a variazioni di luminosità in aree di dimensioni ridotte.
Tipo lossless, senza perdita d'informazione e quindi reversibile.
Tipo lossy, cioè con perdita d'informazione e quindi irreversibile. Detto
anche Algoritmo Baseline è basato sull'operatore matematico detto
Trasformata Discreta del Coseno (DCT).
Nel corso degli anni lo standard JPEG è stato modi cato e migliorato
diven-tando standard JPEG 2000 il quale usa un diverso modello matematico, cioè
DWT (Discrete Wavelet Trasform). Con questo standard le immagini vengono
compresse in modo più e ciente con minima perdita di qualità e sparisce anche
il degrado dovuto dai blocchi quadrettati caratteristica dello standard JPEG.
Lo standard prevede 4 diversi modes of operation ma non è richiesto che i
software li implementino tutti:
1. Sequential DCT-based
2. Progressive DCT-based
3. Lossless
4. Hierarchical
Il procedimento utilizzato più comunemente è il Sequantial DCT-based, il
quale è composto dai seguenti passaggi:
Color Trasform (RGB 7−→YCbCr);
Image partition;
DCT;
Quantization;
DC Coe cient Encoding;
Zig-Zag ordering of AC Coe cients;
Entropy Coding;
Figura 3.2: Sequanzial DCT-based
3.1.1 Color Trasform
Come già espresso in precedenza l'occhio umano è più sensibile alla luminosità
rispetto che al colore e per questo motivo con la compressione JPEG viene
scartato quasi il 75% delle informazioni sulla crominanza. Viene infatti fatto un
sotto-campionamento passando da RGB a YCbCr 4:2:2 oppure 4:2:0.
3.1.2 Image partition
L'immagine da comprimere viene suddivisa in blocchi da 8 × 8 pixel ed i valori
di ogni blocco vengono traslati passando da valori interi senza segno compresi
nel range [0, 2
n]
a valori interi con segno nel range −2
n−1, 2
n−1− 1
, con n=8.
3.1.3 DCT
Questa operazione matematica permette di passare dalla rappresentazione dei
pixel nello spazio ad una rappresentazione equivalente espressa in termini di
frequenza. Questa descrizione è analoga a quella di un suono composto da
sinusoidi (armoniche) di diversa ampiezza, la cui somma genera un'onda di forma
Figura 3.3: Image partition
qualsiasi. Nel caso dell'immagine si lavora su una funzione bidimensionale, che
viene vista come somma di onde in direzione orizzontale e verticale.
Le onde a bassa frequenza rendono conto dell'andamento generale della
lu-minosità dell'immagine, mentre quelle ad alta frequenza codi cano i dettagli e il
disturbo introdotto dall'elettronica dei dispositivi di acquisizione. Dal
momen-to che le immagini fomomen-togra che hanno generalmente un andamenmomen-to continuo, la
rappresentazione nel dominio delle frequenza è costituita da una matrice
qua-drata di valori, dei quali soltanto quelli corrispondenti alle frequenza più
bas-se, raggruppati nell'angolo in altro a sinistra, sono signi cativi, mentre quelli
corrispondenti alle frequenze più elevate hanno valore molto basso.
Esistono vari tipi di trasformate: Fourier, Coseno, Hadamard,
Karhumen-Loeve, ecc... ma i gruppi standardizzati JPEG e MPEG hanno optato per la
Trasformata Discreta del Coseno che provvede alla compressione
spazia-le, essendo capace di rivelare le variazioni di informazione tra un'area e
quel-la contigua trascurando le ripetizioni, e inoltre, essa rappresenta un ottimo
compromesso complessità-prestazioni.
La complessità dell'algoritmo di calcolo della DCT cresce tuttavia molto
rapidamente con le dimensioni dell'immagine. Per questo motivo DCT non
viene applicata all'intera immagine, ma su piccoli blocchi di 8x8 pixel, nei quali
viene scomposta ciascuna componente.
La DCT permette la trasformazione di un blocco 8x8 pixel dell'immagine in
un insieme di 8x8 numeri, detti coe cienti DCT, che descrivono il contenuto di
Figura 3.4: Peso dei contenuto spettrali
frequenza (alte e basse) di tale blocco. L'elemento DCT(0,0) è il valore medio
del blocco (coe ciente DC). Gli altri elementi dicono quanto potere spettrale è
presente a ciascuna frequenza spaziale.
Il calcolo dei coe cienti DCT viene fatto applicando la seguente formula:
F (u, v)
=
1
4
C(u)C(v)
7X
i=0 7X
j=0f (i, y) cos
(2i + 1)uπ
16
cos
(2j + 1)uπ
16
con u=0...7 v=0...7 e C(x) =
1 √ 2se x = 0
1 altrimenti
Con f(i,j) si indica il valore in posizione (i,j) del blocco 8x8 di partenza
mentre con F(u,v) si indica il coe ciente DCT della matrice delle frequenze.
Per la decodi ca, invece, si utilizza la seguente formula:
f (i, j)
=
1
4
7X
u=0 7X
v=0C(u)C(v)F (u, v) cos
(2i + 1)uπ
16
cos
(2j + 1)uπ
16
La DCT di per sé non crea nessuna compressione, infatti, se il decoder
esegue l'operazione inversa, la IDCT, si riottiene il blocco 8x8 pixel senza aver
guadagnato nulla. Per memorizzare i dati degli 8x8 pixel mi occorrono 64 byte
e lo stesso me ne servono per memorizzare i 64 coe cienti della DCT.
Il vantaggio della DCT è quello di aver trasportato i valori signi cativi in
alto a sinistra della matrice e valori quasi tutti uguali a destra.
Figura 3.5: Blocco 8x8 che viene trasformato dal DCT
3.1.4 Quantization and Zig Zag ordering
JPEG prevede una quantizzazione scalare uniforme sulla base di tabelle di
quan-tizzazione che, per ciascuno dei 64 coe cienti della DCT viene speci cato il
pas-so di quantizzazione. Tali tabelle non fanno parte dello standard e pas-sono frutto
di una sperimentazione alla ricerca della migliore qualità soggettiva.
Questa operazione consiste nel fare delle divisioni tra i coe cienti della DCT
e gli elementi della tabella di quantizzazione, l'eetto della divisione è quello di
arrotondare i valori prodotti dalla DCT, portando a zero quelli prossimi allo
zero. Così facendo si smorzano le alte frequenze e si arrotondano con maggiore
precisione le frequenze basse. Le tabelle consigliate dallo standard sono una per
la luminanza e una per la crominanza.
Senza considerare la DCT, la quantizzazione è la prima operazione lossy e
le perdite di informazioni sono dovute a gli arrotondamenti, più è alto il fattore
di quantizzazione più è alto il deterioramento dell'informazione.
IN CODIFICA =⇒F (u, v)
=
round
f (u, v)
Q(u, v)
IN DECODIFICA =⇒f (i, j) ∼
= Q(i, j) • F (i, j)
La quantizzazione ha creato una nuova matrice 8x8 di dati i quali vengono
prelevati in ordina a Zig-Zag per creare un vettore di 64 elementi come in Figura
Figura 3.6: a) Tabella di quantizzazione per la luminanza.b) Tabella di
quantizzazione per la crominanza.
Figura 3.7: Zig-Zag ordering
3.7.
Il motivo per cui si ordinano gli elementi della matrice a zig-zag è
sem-plicemente perché, così facendo, si ottiene un vettore in cui i valori, dal primo
all'ultimo, sono in ordine crescente con la frequenza spaziale. Così facendo,
con-seguenza anche della quantizzazione, si ottengono molti zeri conseguitivi alle alte
frequenze spaziali.
3.1.5 Entropy coding
Una sorgente informatica può essere per sua natura di tipo discreto, come ne
caso di un documento scritto, o di tipo continuo, come nel caso di un segnale
analogico. In base a considerazioni di tipo statistico, la sorgente può essere
ca-ratterizzata da una grandezza, l'Entropia, che indica il tasso di indica il tasso
di informazione (in bit/s) intrinseco per i messaggi prodotti della sorgente. Lo
scopo della codi ca di sorgente è quello di individuare rappresentazioni
alterna-tive per le informazioni prodotte dalla sorgente, in modo da ridurre la quantità
di bit/s necessari alla trasmissione a valori quanto più possibile prossimi a quelli
indicati dall'Entropia, sfruttando le caratteristiche della sorgente e del processo
di codi ca.
La proposta del JPEG speci ca due metodi di codi ca entropica: la codi ca
di Human (approccio Baseline) e la codi ca aritmetica (Lempel-zif-Welsh
Algorithm LZW). Sebbene la codi ca aritmetica ora spesso migliori risultati,
è poco usata poiché coperta da copyright IBM, AT&T e Mitsubishi.
L'algoritmo Human è utilizzato per ottenere una rappresentazione più
com-patta dei dati; esso utilizza frequenze statistiche con cui un simbolo compare
in una sequenza. I simbolo che compaiono più frequentemente vengono
rap-presentati con sequenze di bit corte, quelli meno frequenti con sequenza più
lunghe.
Prima di eettuare la codi ca Human il vettore di 64 elementi viene
sot-toposto all'algoritmo Run-lenght Encoding, storicamente il primo algoritmo
di compressione inventato per le immagini. Più precisamente solo i 63 elementi
corrispondenti alle componenti AC vengono sottoposte a questo algoritmo.
Il primo elemento (DC) viene codi cato con molta più precisione con un
l'al-goritmo DCPM. Questo sistema modi ca il coe ciente DC dal valore assoluto
ad un valore relativo dipendente dal coe ciente DC del blocco precedente. Ad
esempio, se i coe cienti DC di due blocchi adiacenti sono 227 e 205, il secondo
diventerà -22. I blocchi adiacenti solitamente hanno un elevato grado di
corre-lazione, così la codi ca del coe ciente DC come dierenza del DC precedente
tipicamente produce un piccolissimo numero. Il DPCM riduce così gli artefatti
(blocking artifacts) quando l'immagine viene ricostruita.
L'algoritmo Run-lenght Encoding codi ca i 63 elementi AC eliminando le
lunghe serie di zeri presenti all'interno del vettore come nell'esempio seguente:
V ettore
=
15
DC
, 0, −2, −1, −1, −1, 0, , 0, −1, 0, 0, 0, ..., 0
RLE
⇓
⇓
⇓
⇓
⇓
(1, −2), (0, −1), (0, −1), (0, −1), (2, −1), EOB
EOB (End of Block) è uno speciale codice che indica una lunga serie di zeri
che completano il vettore no in fondo, questo speciale codice è indicato nella
codi ca RLE dal simbolo (0, 0). Un altro codice speciale è il (15, 0) il quale
viene utilizzato quanto, tra due elementi diversi da zero presenti nel vettore, è
presente una serie di 16 zeri conseguitivi.
L'ultima codi ca entropica applicata ai dati è la classica codi ca a lunghezza
di codice variabile, Human. La codi ca consente trasformare dei simboli
in sequenza di bit grazie alle tabelle di codi ca Human. Per eettuare la
conversione, i dati creati dall'algoritmo RLE devono essere ordinati realizzando
2 simboli, Simbolo-1 e Simbolo-2. Questi 2 simboli solo composti come segue:
Coe cienti DC:
Simbolo-1=⇒(Size)
Simbolo-2=⇒(Ampiezza)
Coe cienti AC:
Simbolo-1=⇒(Runlenght, Size)
Simbolo-2=⇒(Ampiezza)
Con:
Ampiezza = valore del coe ciente
Size = numero di bit per visualizzare il valore assoluto dell'Ampiezza
Runlenght = numero di zeri che precedono il coe ciente
esempio:
Hp : coef f icente DC del blocco precedente = 12
15, 0, −2, −1, −1, −1, 0, , 0, −1, 0, 0, 0, ..., 0
DC
i= DC
i− DC
i−1= 15 − 12 = 3 =⇒
simbolo−12
size simbolo−23
ampiezzaAC
1=⇒
simbolo−11
runlenght, 2
size simbolo−2−2
ampiezzaAC
2=⇒
0
runlenght, 1
size−1
ampiezzaAC
3=⇒
0
runlenght, 1
size−1
ampiezzaAC
4=⇒
0
runlenght, 1
size−1
ampiezzaAC
5=⇒
2
runlenght, 1
size−1
ampiezzaEOB =⇒ (0, 0)
A tutte le occorrenza di Simbolo-1 viene associato un codice Human che
è distinto a seconda che Simbolo-1 codi chi un elemento AC o DC, infatti si
usano due tabelle di Human separate per le due classi di elementi. Questo
codice è formato da una sequenza di bit di lunghezza variabile a seconda della
Figura 3.8: Tabelle Human per coe cienti DC
frequenza dell'elemento. A questa sequenza si aggiunge la codi ca del Simbolo-2
che verrà convertito in un numero binario con un numero di cifre espresso dal
valore Size nel Simbolo-1. Le tabelle di Figura 3.8 sono utilizzate per
codi ca-re i coe cienti DC di luminanza e di crominanza, più pcodi ca-recisamente codi cano
il Simbolo-1 dei coe cienti DC. Il valore SIZE nel Simbolo-1 corrisponde
al-la colonna CATEGORY delle tabelle in gura, ad ogni SIZE corrisponde una
codi ca Human diversa (CODEWORD). Le tabelle di codi ca Human che
riguardano i coe cienti AC sono riportati in appendice.
Il Simbolo-2, cioè l'Ampiezza, viene convertito rispettando una tabella
pre-disposta per la conversione Human relativa alle ampiezze. Figura 3.9.
An-che in questa tabella la colonna CATEGORY corrisponde al SIZE espresso nel
Simbolo-1, la colonna VALUES è il valore dell'Ampiezza contenuto in Simbolo-2
e l'ultima colonna indica la stringa di bit in cui Simbolo-2 deve essere convertito.
L'esempio precedente convertito con Human riguarda i valori di luminanza
e diventerà:
Figura 3.9: Tabella per la codi ca Human per la ampiezze di tutti i coe cienti
Coe
simbolo-1 simbolo-2
DC
(2),(3)
011
11
AC
1(1,2)(-2)
11011
01
AC
2(0,1),(-1)
00
0
AC
3(0,1),(-1)
00
0
AC
4(0,1),(-1)
00
0
AC
5(2,1),(-1)
11100
0
EOB
(0,0)
1010
In conclusione la matrice 8x8 di pixel sottoposta alla compressione JPEG è
diventata il seguente stream di bit:
011
...
11
...
11011
...
01
...
00
...
0
...
00
...
0
...
00
...
0
...
11100
...
0
...
1010
in cui i puntini verticali sono stati inseriti solamente per rendere più
com-prensibile la serie di bit.
Sulla stringa di bit così ottenuta, che rappresenta la codi ca di Human dei
dati dell'immagine, bisogna applicare un'ultima operazione detta Byte
Stuf- ng. Si suddivide la sequenza di bit in byte, scandendo tutta la stringa byte
per byte. Se la stringa di bit non è divisibile per otto si avrà un byte incompleto
che dovrà essere completato con una sequenza di uno.
Dal risultato nale di nota che i 512 bit dei 64 pixel della matrice 8x8 (64×8
bit per pixel = 512 bit), compressi sono diventati 31 bit e quindi possiamo
calcolare alcuni parametri:
R
compressione=
512 bit31 bit≈ 17
bit pixel
=⇒
31 bit
64 pixel
