Metodi di compressione Jpeg e Jpeg2000 per immagini fisse

  5
visivo, che si indica pure con il termine di irrilevanza. Essa concerne quella parte di 
informazione che può essere rimossa senza conseguenze evidenti dal punto di vista 
percettivo. La rimozione della irrilevanza è irreversibile. 
Le tecniche di compressione dei dati digitali si possono classificare in due grandi 
categorie a seconda che puntino a ridurre la ridondanza oppure la irrilevanza presenti 
sul segnale. Nel primo caso si parla di tecniche di compressione senza perdita (di 
informazione) o non distruttive o lossless, nel secondo di tecniche con perdita o 
distruttive o lossy. 
1.2.1 Compressione senza perdita 
Con le tecniche di compressione senza perdita è possibile riottenere una 
rappresentazione che è numericamente uguale all’ originale. 
Siccome la qualità dei dati ricostruiti è elevata, il fattore di compressione raggiungibile 
con tali metodi non è molto alto, in genere si ottengono rapporti di 2:1. 
Tra le più comuni tecniche senza perdite abbiamo queste che seguono. 
- Codifica entropica, che sfrutta le statistiche relative ai dati. La più usata di queste 
codifiche è il codice di Huffman, con cui si cerca di rappresentare i valori più probabili 
con simboli di lunghezza minima ed utilizzare simboli di lunghezza maggiore per i valori 
meno frequenti. 
- Codifica run-lenght, che mira a rappresentare con pochi bit sequenze costituite dalla 
ripetizione del medesimo valore. Se si incontra un valore u con n occorrenze 
successive, si rappresenta la sequenza con la coppia (u,n). 
- Codifica predittiva, che si basa sulla alta correlazione dei dati spazialmente o 
temporalmente adiacenti. Essa consiste nel predire il valore di un dato da codificare 
sulla base di dati già trasmessi. Se la predizione è fatta bene l’entropia (informazione 
media) dell’errore di predizione è minore rispetto a quella dei dati originari e questo 
comporta un risparmio di bit nella fase di codifica. 
- Codifica a trasformate, in cui anziché considerare i dati nel loro dominio originario, 
temporale e/o spaziale, si effettua una trasformazione lineare di blocchi di dati. Con tale 
trasformazione si ha una ridistribuzione della energia all’interno dei dati senza alterarli, 
cercando di avere quelle proprietà di correlazione e ripetizione che permettono un 
  6
migliore rendimento dei metodi prima esaminati. Tra le trasformate maggiormente 
utilizzate vi è la trasformata discreta di Fourier (Discrete Fourier Transform, DFT), la 
trasformata discreta coseno (Discrete Cosine Transform, DCT) e la trasformata discreta 
wavelet (Discrete Wavelet Transform, DWT). 
1.2.2 Compressione con perdita 
L’utilizzazione delle tecniche con perdita implica una certa approssimazione dei dati 
originari. 
La perdita di qualità che ne deriva è ripagata dagli alti fattori di compressione, da 20-
200:1 fino ad arrivare perfino a 1000:1. Per questo, sempre più frequentemente, queste 
tecniche sono preferite a quelle senza perdite. 
In particolare, risulta evidente la necessità di usare per la visualizzazione di immagini su 
Internet, soggetta alla lentezza della connessione via modem, i formati lossy, proprio in 
relazione a queste loro superiori capacità di compressione. 
La più importante delle tecniche con perdita è certo la quantizzazione. Essa può 
riguardarsi come una funzione suriettiva ma non iniettiva che viene applicata ai dati. Si 
realizza dividendo il dominio in un certo numero di sottoinsiemi ed assegnando ad 
ognuno un valore, detto di quantizzazione. A seconda della dimensione del dominio si 
parla di quantizzazione scalare (dimensione unitaria) o vettoriale. 
1.3 Ridondanza relativa e rapporto di compressione 
Come abbiamo visto, la ridondanza dei dati (intesa qui in senso lato, statistica o 
soggettiva che sia) è un elemento essenziale per la compressione. Non si tratta di un 
concetto astratto, ma di una entità matematicamente quantificabile. 
Infatti, detti 
n
1
 e 
n
2
 il numero di bit necessari a rappresentare la stessa informazione in 
due differenti set di dati, la ridondanza relativa del primo data set rispetto al secondo è 
definita come: 
,
1
1
R
D
C
R −= dove 
R
C  è il rapporto di compressione, definito come 
2
1
n
n
C
R
= ,  
e questo nome si giustifica se la seconda rappresentazione è compressa. 
  7
Se 
21
nn = ,   1=
R
C e 0=
D
R : la prima rappresentazione dell’informazione non contiene 
dati ridondanti (rispetto alla seconda) 
Se 
2
n <<
1
n ,  ∞→
R
C  e 1→
D
R : la prima rappresentazione è estremamente ridondante, 
il rapporto di compressione può assumere valori significativi 
Se 
2
n >>
1
n ,  0→
R
C  e −∞→
D
R  : la seconda rappresentazione contiene molti più dati 
della prima, si ha una espansione piuttosto che una compressione dei dati 
In generale, si ha pertanto: 0 <
R
C <∞  e   ∞− <
D
R <1. In pratica, un rapporto di 
compressione pari a 10 significa che la ridondanza è 0.9, cioè che il 90% dei dati della 
prima rappresentazione può essere rimosso. 
1.4 Gli standard 
Ma le tecniche di compressione, da sole, non sono sufficienti. Viste le numerose 
metodologie di compressione delle immagini, per ridurre il costo di codificatori e 
decodificatori permettendo anche l’integrazione tra apparecchiature di produttori 
differenti, si è reso necessario da parte dell’ISO (International Organization for 
Standardization) stabilire degli standard a livello mondiale. 
La sigla JPEG identifica una commissione di esperti denominata Joint Photographic 
Expert Group, formata nel 1986 in collaborazione con l’ITU (International 
Telecommunication Union)
∗
 appunto con lo scopo di stabilire uno standard di 
compressione per le immagini a tono continuo, cioè di tipo fotografico, sia a colori che in 
bianco e nero. 
Il lavoro di questa commissione congiunta ha portato alla definizione di una complessa 
serie di algoritmi, approvata come standard ISO nell’Agosto del 1990 e 
successivamente divenuta la raccomandazione T.81 ( 9/92 ) dell’International 
Telecommunication Union. 
Il JPEG è dunque uno standard industriale e non va confuso con il formato di file JPG, 
che rappresenta di volta in volta, a seconda della casa di software che lo implementa, 
un sottoinsieme variabile e non sempre universalmente compatibile dello standard di 
riferimento. 
                                                          
∗
 Nota: la parola joint nella sigla JPEG si riferisce appunto alla collaborazione tra ISO e ITU 
  8
Il successo dello standard di compressione JPEG si può desumere dalle cifre: è stato 
calcolato che l’80% circa delle immagini presenti su Internet siano file JPG. 
Tuttavia esiste già il successore designato di questo fortunato standard: si tratta di un 
algoritmo che va sotto il nome di JPEG2000 e che si prevede sarà ufficializzato come 
standard ISO/ITU entro l’anno 2001. 
Scopo di questo lavoro è di dare una descrizione di questi due standard di 
compressione per le immagini fisse ed effettuare una analisi comparativa volta ad 
evidenziare i vantaggi del JPEG2000 rispetto allo standard più anziano. 
 
  9
2     Lo standard JPEG
∗
 
2.1 Introduzione 
Lo standard definito dal comitato JPEG è il primo standard internazionale di 
compressione delle immagini fisse
∗∗
, a colori od a livello di grigio, purché a tono 
continuo (quindi non bi-livello né con pochi colori o livelli: in questi casi la compressione 
è poco efficiente); esso ha lo scopo di essere il più generico possibile. 
Il JPEG è relativo a metodi di compressione sia di tipo con perdita che di tipo senza 
perdita. 
Gli algoritmi con perdita di informazione sono di gran lunga i più importanti e si basano 
su di uno schema di codifica della trasformata discreta coseno. In aggiunta, per venire 
incontro alle esigenze delle applicazioni in cui non possono essere tollerate perdite di 
informazioni (per esempio, le immagini mediche), è stato definito uno schema di 
codifica senza perdita, basato essenzialmente su un algoritmo predittivo. 
In definitiva, il JPEG definisce quattro differenti modi di compressione: sequenziale 
basato sulla DCT, progressivo basato sulla DCT, senza perdita e gerarchico. 
2.2 Il modo sequenziale basato sulla DCT 
In questo ambito sono a loro volta definiti più processi di compressione, dal cosiddetto 
sistema baseline, il più diffuso, al cosiddetto sistema esteso, mediante opportuna 
combinazione di alcuni parametri i cui valori sono selezionabili nel codificatore. 
Nel caso più generale, sono possibili cinque combinazioni, secondo lo schema 
seguente: 
                                                          
∗
 Nota: si usa la sigla JPEG sia per indicare il comitato ISO Joint Photographic Expert Group, sia per indicare lo 
standard da esso proposto. 
∗∗
 Nota: anche se in questo lavoro considereremo lo standard JPEG come relativo alla compressione delle immagini 
fisse, come d'altronde viene inteso dall’ISO, è interessante tuttavia notare che esso viene pure di fatto utilizzato 
come metodo di compressione delle immagini in movimento della classe “intraframe”, per la quale ogni immagine è 
considerata statica e codificata indipendentemente dalle altre (precedenti o future). 
  10
 
                    
                                                                              Fig. 2.1 
 
La sigla bpp in figura sta per “bit per pixel”. 
Una applicazione od un dispositivo è compatibile con lo standard JPEG se include 
almeno il supporto per il sistema baseline: di fatto, quest’ultimo è l’unico previsto dalla 
maggior parte delle implementazioni del JPEG. 
I 12 bit per campione, difatti, si giustificano in applicazioni molto specifiche, quali per 
esempio la radiografia digitale e, più in generale, i dati utilizzati nel medical imaging. E’ 
da ricordare inoltre che la variante della codifica aritmetica specificata dal JPEG è 
brevettata da IBM, AT&T e Mitsubishi, per cui non esistono implementazioni 
significative che prevedano questa forma di codifica entropica, in quanto sarebbero 
soggette al pagamento di royalties. In più, la codifica aritmetica presenta una maggiore 
complessità (sul concetto di complessità torneremo più avanti) che la rende inadatta per 
le implementazioni hardware a più alta velocità. 
Per tutte le suddette ragioni, sarà essenzialmente l’algoritmo baseline di compressione 
quello di cui andremo a trattare nelle pagine che seguono.   
2.2.1  Lettura del file sorgente 
Nell’algoritmo baseline, come negli altri metodi sequenziali basatesi sulla DCT, i dati 
letti dal file sorgente vengono rappresentati, se M e N sono la dimensione orizzontale e 
verticale in pixel dell’immagine, come matrici di dimensioni (M,N) per immagini a livello 
di grigio oppure tre matrici di dimensione (M,N) per immagini a colori. 
L’algoritmo non supporta la rappresentazione di tipo “colormapped” per le immagini a 
colori, che quindi vanno trasformate nella rappresentazione RGB, acronimo che sta per 
Red, Green, Blue, rispettivamente rosso, verde e blu. 
  11
La DCT verrà applicata a blocchi 8x8 completi quindi, se M o N, cioè la dimensione 
dell’immagine, non è multipla di 8 bisogna aggiungere delle copie dell’ultima riga o 
dell’ultima colonna alla matrice dell’immagine, sino a che la dimensione della nuova 
matrice non diventi un multiplo di 8 (vd. fig.2.2). 
                                    
                                                                         Fig. 2.2                   
 
Questa operazione fa in modo che la tonalità o la luminosità base del blocco 8x8 non 
vari in modo sostanziale dopo la applicazione della DCT, fatto che invece può accadere 
se gli elementi mancanti per completare un blocco 8x8 vengono inizializzati con zero, 
cioè l’equivalente di un riempimento di nero. 
Nella fase di decodifica bisognerà tenere conto di questi pixel di riempimento aggiunti 
ed eliminarli tenendo conto della dimensione originale della immagine. 
2.2.2 Trasformazione dello spazio cromatico 
A causa delle particolari caratteristiche dell’occhio umano, molto più sensibile alle 
variazioni di luminosità che alle variazioni cromatiche, è opportuno trasformare la 
modalità RGB in modalità YUV o, meglio, in quella YCbCr. 
Il sistema YUV scompone l’informazione relativa a ciascun pixel in una componente di 
luminanza, che definisce il grado di luminosità nella scala da nero a bianco (la lettera 
“Y” della sigla YUV) ed in due componenti relative alla crominanza, che definisce il 
colore in base al rapporto tra due assi, uno che va dal blu al giallo (la lettera “U”) e 
  12
l’altro che va dal rosso al verde (la lettera “V”). Il modello YCbCr è una variante del 
modello YUV, studiata in modo da evitare che le componenti di crominanza diventino 
negative. 
Eseguire la trasformazione dallo spazio cromatico RGB a quello YCbCr non è 
indispensabile, ma il farlo consente di ottenere una maggiore compressione JPEG. 
Quando, infatti, le successive trasformazioni matematiche che si applicano alla 
immagine trovano l’ informazione nettamente suddivisa nella componente di luminosità 
e nelle due di colore, possono procedere alla eliminazione di molte informazioni relative 
al colore senza intaccare quelle relative alla luminosità, più importanti per la visione 
umana, e senza causare, in tal modo, danni visibili al contenuto della immagine. 
Ciò non è possibile invece nella stessa misura quando gli algoritmi di compressione si 
applicano a valori RGB, che presentano la informazione relativa al colore e quella 
relativa alla luminosità fuse insieme (per le immagini in scala di grigio la conversione 
non ha senso, in quanto la informazione sulla luminosità è già disponibile in partenza). 
Per il cambiamento di spazio cromatico da RGB a YCbCr si debbono usare le seguenti 
formule che vengono applicate alle matrici distinte R,G e B: 
0.299 0.587 0.114
0.1687 0.3313 0.5
0.5 0.4187 0.0813
YRGB
Cb R G B
Cr R G B
=++
⎧
⎪
=− − +
⎨
⎪
=− −
⎩
 
Questa trasformazione introduce degli errori di arrotondamento che però sono 
ininfluenti rispetto alla quantità di errore introdotta con la applicazione dell’algoritmo 
JPEG. 
2.2.3 Riduzione delle matrici delle componenti cromatiche 
La riduzione delle matrici delle componenti cromatiche attraverso la media dei pixel 
vicini è l’operazione opzionale, di cui alcuni software di grafica consentono 
l’impostazione, che consegue alla trasformazione dello spazio cromatico. 
La componente relativa alla luminosità resta invariata, mentre le due componenti 
cromatiche possono venire ridotte 2:1 orizzontalmente e 2:1 oppure 1:1 (nessuna 
modifica) verticalmente. Questa operazione riduce la quantità di informazione di metà o 
di un terzo, numericamente indica una grande perdita di dati ma, per la maggior parte 
  13
delle immagini, non ne influenza in modo significativo la qualità percettiva, questo in 
quanto l’occhio umano non è sensibile a piccole variazioni cromatiche. 
Il fatto che questa operazione non si applica alle immagini a toni di grigio ci spiega 
perché queste siano , in generale, meno comprimibili di quelle a colori. 
2.2.4 Shift dell’immagine. Codifica con DCT diretta e decodifica con DCT inversa 
I procedimenti di codifica e decodifica basati sullo uso della DCT possono essere 
rappresentati sinteticamente dagli schemi a blocchi rappresentati nelle fig.2.3 e 2.4 
rispettivamente. 
 
                      
                                   Fig.2.3: schema a blocchi del codificatore basato sulla DCT 
 
                      
                                    Fig. 2.4: schema a blocchi del decodificatore basato sulla DCT 
 
Su tutte le matrici delle immagine sorgente, siano esse RGB oppure YCbCr, si applica 
uno shift: i campioni della immagine in ingresso, che presentano valori nell’intervallo 
[0,2 1]
p
−  con p numero di bit, vengono in pratica traslati della quantità 
1
2
p−
− . Il range di 
valori possibili per i suddetti campioni diventa 
11
[2 ,2 1]
pp−−
− − , nel caso particolare del 
sistema baseline si ha quindi un range 
77
[2,2 1]− −  cioè [ 128,127]− . 
Si dividono dunque le matrici in blocchi 8x8 a cui si applica la trasformata coseno diretta 
  14
FDCT (Forward Discrete Cosine Transform) al fine di trasformare i dati shiftati nel 
dominio della frequenza. All’uscita del decodificatore la trasformata coseno inversa 
IDCT (Inverse Discrete Cosine Transform) restituirà blocchi 8x8 di campioni con cui si 
formerà l’immagine ricostruita, tanto più differente dalla immagine sorgente quanto 
maggiore sarà stata la compressione con perdita.  
La FDCT è definita dalla espressione: 
77
00
1(21)(21)
(,) () () (, )cos cos
4 66
xy
x vyu
Fuv CuCv f xy
π π
==
⎡ ⎤
++
=
⎢ ⎥
⎣ ⎦
∑∑
         dove 
1
0
()
2
1
per k
Ck
negli altri casi
⎧
=
⎪
=
⎨
⎪
⎩
 
La IDCT è definita dalle 
77
00
1(21)(21)
(, ) () () (,)cos cos
4 66
uv
x uyv
fxy CuCv Fuv
π π
==
++⎡ ⎤
=
⎢ ⎥
⎣ ⎦
∑∑
         dove 
1
0
() 2
1
per k
Ck
negli altri casi
⎧
=
⎪
=
⎨
⎪
⎩
 
 
Intuitivamente la FDCT può essere vista come un analizzatore armonico, allo stesso 
modo in cui la IDCT può riguardarsi come un sintetizzatore armonico. Il segnale in 
ingresso viene decomposto dalla FDCT in 64 segnali base ortogonali, ognuno dei quali 
è rappresentato da una coppia di frequenze spaziali (u,v). I valori F(u,v) così calcolati 
sono chiamati in generale coefficienti DCT; il termine F(0,0) è detto DC perché 
rappresenta una media dei campioni del blocco, mentre i restanti 63 sono detti AC. 
Solitamente i valori dei campioni della immagine variano lentamente lungo le due 
direzioni, orizzontale e verticale, portando ad uno spettro in frequenza concentrato 
attorno alle basse frequenze. Questo fenomeno è alla base della tecnica di 
compressione basata sulla FDCT ed è importante il fatto che, di norma, per una 
immagine molti dei coefficienti spettrali risultano nulli o vicini allo zero, quindi non 
necessitano di essere codificati.