INTRODUZIONE 2
I due valori rimanenti vengono ricostruiti tramite interpolazione (algoritmo di
demosaicking), stimando il pixel corrente sulla base dei suoi vicini.
¨ bene specificare che l obiettivo di questa tesi non riguarda l implementazione di un
nuovo algoritmo di codifica, ma consiste in un attenta analisi della natura di questa
tipologia di dati, alla ricerca di relazioni che migliorino l efficienza e l efficacia degli
algoritmi di compressione con perdita d informazione (lossy). Nel capitolo 1, capiremo
come operano questi algoritmi, ponendo particolare attenzione alle caratteristiche degli
algoritmi Jpeg e Jpeg2000. In particolare, vedremo come una buona codifica dipenda
principalmente dalla capacit della trasformata di eliminare la ridondanza statistica nel
segnale e dalla opportuna selezione dei coefficienti da quantizzare. Nel capitolo 2,
confronteremo i metodi di codifica lossy standard con i nuovi metodi basati sull analisi
wavelet, i quali garantiscono una maggiore qualit dell immagine ricostruita. Infatti,
come riscontrato negli ultimi studi, la grande capacit della trasformata wavelet di
compattare l energia del segnale in un numero minimo di coefficienti, permette di
migliorare notevolmente l efficacia della codifica. Caratteristica fondamentale delle
wavelet Ł la capacit di analisi a risoluzione variabile nel tempo e nella frequenza. Tale
propriet consente di analizzare segnali non stazi onari, ben identificandone i punti di
discontinuit . Tali punti corrispondono generalmen te a zone del segnale con grandi
variazioni di intensit e costituiscono la stru ttura geometrica dei dati in cui Ł contenuta
l informazione piø significativa di un segnale (punti di edge o contorno). Questo utile
strumento matematico verr trattato approfonditamen te nella prima parte del capitolo 3,
mentre, nella seconda parte, introdurremo alcune tecniche standard per la localizzazione
di edge. A partire dall algoritmo di Canny riformulato da Mallat, utilizzeremo i massimi
del modulo della trasformata wavelet continua (CWT) per localizzare gli edge nei dati cfa.
Piø precisamente, nel capitolo 4, in corrispondenza dei massimi locali della trasformata
wavelet, determineremo:
la presenza di un edge nella medesima posizione nelle componenti Y e RGB;
le caratteristiche di tali edge mediante lo studio delle variazioni, rispetto alla scala, della
trasformata nel relativo cono di influenza;
le relazioni, in termini di energia, tra le componenti Y G , G-R e G-B secondo il
campionamento del pattern a mosaico;
3 INTRODUZIONE
Una volta stabilita la correlazione tra le componenti di colore in corrispondenza dello
stesso edge lungo le scale, Ł possibile trasmettere, nel processo di codifica, solamente i
coefficienti wavelet di un unica componente di colore e le funzioni che ne descrivono le
relazioni con i coefficienti delle rimanenti componenti. Ci potrebbe garantire una buona
ricostruzione del segnale ed un alto livello di compressione, riducendo i tempi
computazionali e i costi di gestione dei sistemi. A tale scopo, alla fine del capitolo 4
mostriamo un possibile algoritmo che permette di migliorare la codifica dei dati in
termini di rapporto di compressione.
Capitolo 1
Fondamenti di compressione
La compressione di dati Ł una delle applicazioni principali dell elaborazioni dei segnali, in
quanto, sfruttando la correlazione intrinseca tra i campioni del segnale da trasmettere Ł
possibile ridurre la quantit di memoria da occupar e. Nel corso del capitolo, si
descriveranno i metodi standard di compressione e si mostrer come la qualit finale
dell immagine dipenda fortemente dalla riduzione dell errore di ricostruzione.
Caratteristica comune alle varie tecniche di compressione esistenti, Ł l uso di una
trasformazione lineare che decorreli l informazione contenuta nell immagine e
compatti l energia corrispondente in un numero minore di campioni a cui applicare la
quantizzazione.
1.1 Introduzione
Il termine compressione si riferisce al processo di riduzione di quantit di dati necessari a
rappresentare una certa quantit di informazione, a scopo di trasmissione o di archivio.
¨ bene sottolineare come sia i dati quanto le infor mazioni, nonostante costituiscano due
concetti correlati, siano ben distinti. Infatti, quando parliamo di dato ci riferiamo al mezzo
attraverso cui l informazione Ł veicolata, ovvero alla sua rappresentazione. Ci comporta,
che differenti quantit di dati possono essere usa ti per rappresentare la stessa quantit di
informazione. A tale scopo, con la compressione si cerca di rappresentare l informazione
risparmiando spazio lungo il canale di trasmissione e nello stesso tempo, garantirne una
qualit ottimale in output. In alcune applicazioni (mediche, legali, artistiche), il processo di
compressione implica una riduzione dei dati senza perdita di informazione (lossless), in
quanto la qualit dell immagine compressa deve ess ere perfettamente uguale a quella
originale. Non sempre per Ł necessario un approccio simile, basti pensare che in alcuni
casi (cinema, tv, web), la perdita di una certa quantit di informazione Ł in genere
tollerabile, pertanto si utilizzano frequentemente processi di compressione con perdita
(lossy) che garantiscono una maggiore compressione. Queste tecniche sfruttano la
ridondanza dei dati, una caratteristica praticamente riscontrabile in tutti i segnali
audio/video.
5
1.2 RIDONDANZA DEI DATI 6
1.2 Ridondanza dei dati
La ridondanza Ł un entit matematicamente quantificabile:
Definizione 1.1 [1a]
Siano n1 e n2 il numero di bit necessari per rappresentare la stessa informazione in due
differenti set di dati. La ridondanza relativa del primo set rispetto al secondo, Ł definita
come
1
1d
r
R
C
= − (1.1)
Cr rappresenta il rapporto di compressione 1
2
n
n
dei due set di dati. In particolare :
se 2 1n n= , 1rC = e 0dR = , la prima rappresentazione dell informazione non contiene
dati ridondanti rispetto alla seconda;
se 2 1n n<< , rC → ∞ e 1dR → , la prima rappresentazione Ł estremamente ridondante,
il rapporto di compressione pu assumere valori sig nificativi;
se 2 1n n>> , 0rC → e dR → − ∞ , la seconda rappresentazione contiene molti piø dati
della prima, si ha una espansione piuttosto che una compressione dei dati.
Di seguito distingueremo la ridondanza statistica da quella psicovisiva.
1.2.1 Ridondanza statistica
Solitamente i pixel di un immagine sono correlat i e, quindi, statisticamente non
indipendenti. Parliamo in questo caso di ridondanza interpixel: [1a] esiste una forte
correlazione tra pixel vicini che assumono valori di luminosit o colori simili.
La ridondanza dei dati in questi termini viene rilevata sia nel dominio spaziale che in
quello temporale. Nella ridondanza spaziale, detta anche intraframe, la correlazione
statistica tra pixel adiacenti in una singola immagine Ł dovuta principalmente alle relazioni
strutturali-geometriche degli oggetti presenti nell immagine stessa. Quindi, il valore di un
pixel pu essere ragionevolmente previsto se si co noscono i valori dei suoi vicini. La
ridondanza temporale (interframe), invece, si riferisce alla correlazione tra pixel di
fotogrammi consecutivi. Quindi, due immagini della stessa scena hanno caratteristiche
molto simili.
7 CAPITOLO 1. FONDAMENTI DI COMPRESSIONE
Ad ogni modo in questa tesi tratterremo solamente le analisi di immagini statiche; di
conseguenza, Ł bene porre l attenzione sulla correlazione tra componenti di colore nel
dominio spaziale.
La ridondanza nella codifica [1a] dipende dal numero di bit utilizzati per rappresentare
l informazione di colore o di livello di grigio che assume il pixel .
Supponiamo che i livelli di grigio di un immagine siano rappresentati da una variabile
random discreta kr , con ( )r kp r la probabilit di ciascun livello di grigio e ( )kl r il numero
di bit usati per rappresentare il valore kr . Il numero medio di bit avgL richiesto per
rappresentare ogni pixel Ł dato dalla seguente formula [1a]
1
0
( ) ( )
L
avg k r k
k
L l r p r
−
=
= ∑ (1.2)
dove L determina il numero dei livelli di grigio dell immagine.
Il valore avgL , espresso in bit/simbolo, rappresenta la lunghezza media delle stringhe
utilizzate per codificare ciascun livello di grigio.
Pertanto, il numero totale di bit richiesto per codificare un immagine di dimensioni MxN
sar dato da avgM N L⋅ ⋅ . Questo tipo di ridondanza, come vedremo nel paragrafo 1.3,
viene solitamente sfruttata nel codificatore di simbolo, nell ultima fase del processo di
compressione, attraverso l utilizzo di codici a lunghezza variabile (VLC) che cercano di
ridurre il numero di bit necessari per la codifica di un blocco di dati. Su questo principio,
ad esempio, si basa la codifica Huffman1 che assegna stringhe piø corte a simboli piø
probabili e viceversa.
1.2.2 Ridondanza psicovisiva
Il concetto di ridondanza visiva Ł fortemente dipendente dalle caratteristiche del sistema
visivo umano. L occhio umano pu essere visto come un filtro biologico che interpola
meglio il segnale campionato temporalmente in zon e piø scure dell immagine. Quindi,
all aumentare della luminosit , l occhio tende a ri levare sempre meno le caratteristiche
luminose significative, in quanto la sua sensibilit diminuisce [1a][1d].
1
Per ulteriore approfondimento rimandiamo il lettore all appendice A1
1.2 RIDONDANZA DEI DATI 8
Questo comportamento logaritmico dei fotorecettori della retina viene sfruttato nel
processo di codifica: infatti, per evitare falsi contorni, si utilizzano piø bit nelle zone
uniformi e meno bit nelle zone in cui il segnale varia rapidamente. Ad esempio, in
prossimit di edge, proprio perchŁ l occhio umano Ł piø sensibile alle basse frequenze.
Sfruttando questa caratteristica, attraverso una tecnica denominata quantizzazione IGS
(Improved Gray Scale) [1a] , Ł possibile convertire l errore di quantizzazione a bassa
frequenza che causa i falsi contorni, in rumore ad alta frequenza. In questa maniera, i falsi
contorni vengono ridotti il piø possibile, mentre aumenta la granulosit dell immagine
dovuta al rumore alle alte frequenze, che risulta per trascurabile all occhio umano.
Un altra caratteristica del sistema visivo umano, riguarda il ritardo con cui si adatta ai
bruschi cambiamenti di scena: durante questa transizione, infatti, il sistema non Ł sensibile
ai dettagli, di conseguenza pu essere sfruttato benissimo nel processo di codifica.
Queste tecniche, vengono generalmente impiegate negli algoritmi di compressione con
perdita di informazione, in quanto, sfruttando la ridondanza visuale, tali perdite non
influiscono sulla qualit dell immagine compressa.
1.3 Tecniche di codifica con perdita d’informazione
I modelli generali di compressione sfruttano la ridondanza dei dati nel processo di
codifica. Un sistema per la compressione/decompressione di immagini, Ł costituito da due
unit strutturali caratterizzate da un codificator e e da un decodificatore. L immagine di
ingresso f(x,y) Ł elaborata all interno del codificatore, il quale genera un insieme di
simboli del codice che vengono trasmessi lungo il canale, fino all ingresso del
decodificatore che ricostruisce l immagine.
Figura 1.1: Schema di compressione
9 CAPITOLO 1. FONDAMENTI DI COMPRESSIONE
In particolare, il blocco codificatore Ł costituito da un encoder sorgente che riduce la
ridondanza dei dati nell immagine d ingresso, mentr e il codificatore di canale, incrementa
l immunit al rumore del segnale in uscita dal codi ficatore di sorgente [1a].
Lo schema a blocchi in figura 1.2 descrive in dettaglio l encoder: alla fine del processo di
codifica avremo sul canale un segnale privo dei tre tipi di ridondanza.
Il mapper trasforma i dati d ingresso dell immagine in un array di coefficienti che
riducono la ridondanza interpixel, mentre il quantizzatore riduce la ridondanza
psicovisiva presente all uscita dello stadio precedente (ad esempio con la tecnica IGS).
L ultima catena del blocco Ł il codificatore di simbolo, il quale utilizza un codice di
lunghezza variabile o fissa che sfrutta la ridondanza della codifica, assegnando stringhe di
codice piø corte a simboli piø probabili e viceversa. ¨ bene ricordare che nella
compressione reale, le operazioni di mapping e quantizzazione vengono svolte
contemporaneamente in un unico stadio.
Figura 1.2: Codificatore di sorgente
Per quanto riguarda la decodifica, il decodificatore di sorgente contiene solo due blocchi
che rispettivamente compiono le operazioni inverse dei blocchi del codificatore. In figura
1.3, osserviamo inoltre, come non possa esistere un operazione inversa del quantizzatore,
in quanto il processo Ł irreversibile (con perdita dei dati). Infatti, come vedremo, la
quantizzazione modifica il segnale originario approssimandone il valore con uno vicino,
ma non identico.
Figura 1.3: Decodificatore di sorgente
1.3 CODIFICA LOSSY 10
Questo pu comportare fortemente un rischio di perd ita di informazione non ridondante,
che deve essere quantomeno quantificata per determinare la qualit dell immagine
ricostruita. A tale scopo, si utilizzano due criteri di fedelt [1a] che valutano le
informazioni perse e verificano quanto effettivamente l immagine ricostruita Ł fedele
all originale.
Quando la destinazione finale delle immagini Ł il sistema visivo umano, vengono utilizzati
criteri soggettivi basati sull osservazione. In genere, vengono mostrate ad un campione di
osservatori immagini compresse, ricostruite con parametri di codifica variabili.
L obiettivo Ł calcolare una media sulle loro valutazioni, per determinare la qualit
migliore delle immagini testate.
I criteri oggettivi, invece, permettono di quantificare la qualit dell immagine attraverso
determinati parametri. Un parametro di confronto Ł il rapporto di compressione
r
C (def.
1.1) tra il segnale originale e quello codificato: quanto maggiore Ł questo valore tanto
maggiore sar la riduzione del bit-rate del segnale codificato rispetto a quello del segnale
originale. Naturalmente, ci non comporta sempre una qualit ottimale dell immagine
ricostruita, specialmente negli algoritmi con perdita (lossy), dove questo parametro non Ł
sufficiente a caratterizzare le prestazioni di codifica.
In questi casi Ł necessario quantificare la perdita di qualit attraverso delle misure oggettive
sulla distorsione: l errore quadratico medio
rmse (Root-Mean-Square Error), calcola
l errore tra l immagine originale e quella ricostru ita, con M e N rispettivamente il numero
di righe e colonne dell immagine. Piø il valore calcolato Ł basso e piø l immagine
ricostruita Ł fedele all originale.
1
1 1 22
’
0 0
1
( , ) ( , )
M N
rms
x y
e f x y f x yMN
− −
= =
= −
∑ ∑ (1.3)
Il rapporto segnale-rumore SNR ( mean-square signal-to-noise ratio SNRrms ), mette in
relazione la potenza del segnale utile rispetto a quella del rumore introdotto dal
quantizzatore. Tanto piø alto Ł il valore di questo rapporto, migliore sar la qualit dell
immagine ricostruita, (che ricordiamo Ł un approssimazione di quella originale), ci
implica un errore di ricostruzione piø basso possibile.
11 CAPITOLO 1. FONDAMENTI DI COMPRESSIONE
1 1
’ 2
0 0
1 1
2
’
0 0
( , )
( , ) ( , )
M N
x y
rm s M N
x y
f x y
SN R
f x y f x y
− −
= =
− −
= =
=
−
∑ ∑
∑ ∑
(1.4)
Il modello generale di compressione descritto in questa sezione, pu operare sia nel
domino spaziale e sia nel dominio della frequenza. Nella prossima sezione, descriveremo
brevemente il funzionamento del codificatore predittivo, che opera nel dominio spaziale,
per poi passare all approfondimento del codificatore per trasformata.
1.3.1 Codifica predittiva
Gli algoritmi di codifica basati su un operazione di predizione sfruttano la ridondanza
statistica esistente tra i campioni. Generalmente, il predittore esegue una combinazione
lineare dei pixel adiacenti, pesati con dei coefficienti opportuni
k
α , che minimizzano
l errore quadratico medio (
rmse ) tra la predizione
’
nf e il valore reale del pixel
considerato nf . In questa maniera, viene trasmessa solo la differenza tra il campione reale
ed il campione predetto sulla base di quelli precedenti, cioŁ
’
n n ne f f= − , (1.5)
dove il valore predetto Ł generato tramite l equazione ’
1
p
n k n k
k
f fα −
=
= ∑ , con p a
determinare il numero dei valori passati da cons iderare per la predizione.
L equazione precedente ( ’nf ), viene (solitamente) utilizzata nei codificatori predittivi senza
perdita d informazione.
Lo schema a blocchi in figura 1.4 [1a], descrive il modello di riferimento di un
codificatore predittivo lossy (con perdita d informazione). Il primo passo dell algoritmo
( 0)n = , prevede la condizione iniziale ’0 0f f= , da cui, secondo l equazione (1.5),
otteniamo un errore di predizione 0e nullo. Quindi, il campione ricostruito Ł pari a
.
’
0 0 0 0f e f f= + = .
1.3.1 CODIFICA LOSSY PREDITTIVA 12
Nei cicli successivi ( 0)n > , l errore di predizione ( )ne da trasmettere viene quantizzato:
.
n n ne e ε= + , con nε a rappresentare l errore di quantizzazione. In questo caso, la
predizione dei nuovi pixel viene calcolata a partire da quelli adiacenti gi compressi.
Pertanto, dal secondo passo in poi ( 1)n ≥ , poniamo
.
’
1
p
n k n k
k
f fα −
=
= ∑ , (1.6)
da cui ricostruiamo il campione corrente
.
nf da trasmettere all ingresso del predittore,
cioŁ
. .
’
n n nf e f= + , (1.7)
Quindi, in particolare, se 1p = otteniamo
.
’ ’ ’
1 0 0 0 0 0f f e f f f= = + = = ,
. . . .
’ ’ ’
2 1 1 1 1 0 1 0f f e f e f e f= = + = + = + e cos via. Nei calcoli citati abbiamo posto per
semplicit 1, 0k kα = ∀ > nell equazione (1.6). La tabella 1 mostra in dettaglio tutto il
procedimento di calcolo del codificatore 0p∀ > . Come possiamo notare, ad ogni ciclo, il
campione ricostruito dipende dalla somma tra il campione originale e l errore di
quantizzazione introdotto, cioŁ
.
m m mf f ε= + , con m m kε ε −> . Si rimanda il lettore
all appendice A1 per la dimostrazione.
Figura 1.4: Codificatore predittivo lossy
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
