Tecniche di codifica a doppia scansione

  
 
 i 
Prefazione  
 
 La presente tesi di laurea è stata sviluppata presso il Laboratorio Video della 
“Fondazione Ugo Bordoni”. 
 Si ringrazia la FUB per aver fornito i mezzi tecnici necessari al suo svolgimento. 
 Si ringrazia, inoltre, tutto il personale che ha messo a disposizione la propria cortese 
e preziosa collaborazione e, in particolar modo, l‟Ing. L. Capodiferro, il Prof. A. Neri ed 
il Prof. G. Jacovitti senza i quali il presente lavoro di tesi non sarebbe stato realizzato. 
 
 
 
 
 
 
 
 
 
 
 
  
 
 ii 
Sommario 
 
In questo lavoro di tesi verrà presentato un sistema innovativo per la codifica di 
immagini fisse, utile soprattutto in quelle applicazioni che richiedono un elevato tasso di 
compressione. 
Verranno presentati i risultati relativi ad immagini di test, per mostrare l‟efficacia 
degli algoritmi ed il raggiungimento degli obiettivi proposti. 
Nel primo capitolo sarà descritta la base teorica del lavoro, introducendo un 
operatore matematico noto come Trasformata Wavelet, e verrà posta particolare 
attenzione alla sua capacità di  rilevare importanti caratteristiche delle immagini quali 
bordi, incroci di linee, vertici. 
Nel capitolo successivo verrano presentati alcuni standard di riferimento sia per la 
codifica di immagini fisse che per la compressione delle sequenze video. Si farà 
riferimento ad essi  sia come termine di confronto con il sistema realizzato, sia  perché 
utilizzati nell‟implementazione dell‟ algoritmo proposto.  
Nel capitolo terzo si descriverà una tecnica innovativa per la ricostruzione 
dell‟immagine a partire dai relativi Piani Wavelet campionati secondo una griglia 
uniforme: le caratteristiche di invarianza alla traslazione e alla rotazione delle  Wavelet 
Circolari Armoniche di Laguerre Gauss, rendono di fatto questa trasformata, la prima 
candidata per una Codifica a Doppia Scansione. 
Nel capitolo conclusivo si analizzeranno nel dettaglio le tecniche utilizzate per la 
realizzazione del sistema di codifica proposto e si mostreranno i risultati conseguiti, 
mettendoli a confronto con quelli ottenibili attraverso una codifica standard. 
 
 
Gli algoritmi proposti sono stati implementati in linguaggio ANSI C++, in ambiente 
UNIX-Solaris su calcolatori SUN Ultra SPARC II. 
 
Introduzione  
  
 
5 
Introduzione 
 
Negli ultimi anni la comunicazione ha assunto un ruolo centrale sia nel mondo 
economico che nella vita quotidiana. La crescente diffusione di Internet ha aperto la 
strada alla multimedialità e all'interattività sottolineando l'importanza della 
comunicazione visiva. In questo contesto, le immagini digitali hanno assunto un ruolo 
principe ed hanno un numero sempre crescente di applicazioni. Si pensi, ad esempio, 
alla diffusione che le fotocamere digitali e gli apparati mobili hanno avuto negli ultimi 
anni.  
Oggi la terza generazione di sistemi cellulari che in Europa  è denominata UMTS 
(Universal Mobile Telecommunication System)  è presentata come la soluzione 
definitiva, come il mezzo ultimo per trasmettere immagini,suoni, voce, con rapidità e 
con grande qualità. 
Il sistema UMTS si pone quindi come elemento di convergenza tra il mondo delle 
telecomunicazioni e le altre tecnologie dell'informazione, attraverso la saldatura tra i 
due grandi successi degli ultimi anni: la telefonia mobile ed Internet. 
Le immagini digitali richiedono però una elevata capacità di memoria e una elevata 
larghezza di banda per la loro trasmissione. Poichè, non sempre la trasmissione avviene 
su canali a banda larga, nell'intento di superare l'ostacolo dell'alto tempo di 
trasmissione, si rende necessaria la preventiva compressione dell'immagine. 
Il requisito fondamentale richiesto ad uno standard per il trattamento di immagini 
digitali diviene, quindi, una qualità adeguata anche a bassi bit-rate. 
Le immagini, non opportunamente codificate, richiedono infatti un cospicuo 
impiego di risorse, sia in termini di memoria in un calcolatore che di larghezza di banda 
in un canale i trasmissione. 
Per ridurre il numero di bit necessari a rappresentare un'immagine, sono state 
studiate varie tecniche di compressione, molte delle quali con perdita di informazione.  
Il principio su cui si basa la compressione dei dati è l'eliminazione della ridondanza 
contenuta nell'informazione. L'obiettivo è rappresentare un segnale utilizzando il minor 
Introduzione  
  
 
6 
numero possibile di simboli, in accordo a determinati vincoli di qualità sul segnale 
ricostruito.  
Una buona compressione può essere ottenuta con tecniche  lossless (senza perdita), 
in cui i dati decodificati restituiscono una copia esatta di quelli originali.  
Rilassando questo vincolo di qualità e permettendo che i dati ricostruiti differiscano 
da quelli originali entro una certa soglia di errore, i dati possono essere compressi con 
efficienza crescente all'aumentare della tolleranza sull'errore nel segnale ricostruito. 
Poiché è necessario eliminare parte dei dati, il problema che si pone nella 
compressione lossy (con perdita) è quello di discriminare l'informazione essenziale da 
quella meno importante, al fine di poter scartare i dati meno utili alla ricostruzione 
fedele dei dati originali, per ottenere, a parità di dimensione dei dati compressi,  la 
migliore qualità possibile. 
Quando trattiamo segnali visivi, nella valutazione dell'errore è opportuno scegliere 
una misura che rifletta le caratteristiche del sistema percettivo dell'osservatore.  
In altre parole, la misura della distorsione deve essere consistente con ciò che 
l'osservatore è in grado di percepire. Tutto ciò che non può essere "catturato" dall' 
osservatore può essere rimosso senza rischi. Infatti, poiché l'utente non è in grado di 
percepire l'errore commesso eliminando tale informazione, dal suo punto di vista il 
segnale originale e quello "ripulito" sono indistinguibili.  
 
  Nella presente tesi di laurea viene proposta una procedura originale per la codifica 
di immagini digitali e, in generale, per il miglioramento dell‟aspetto complessivo di 
immagini compresse ad elevati bit-rate. La procedura, applicabile sia ad immagini 
monocromatiche (rappresentate mediante scala di grigi) che a colori, si basa sul 
principio innovativo della “Doppia Scansione”. 
Immediate applicazioni della procedura si hanno in tutti i campi in cui si vuole 
operare a compressioni medio alte,  dalle fotocamre digitali alla distribuzione su 
internet.  In realtà le sue possibili applicazioni riguardano anche tutti gli altri strumenti 
di acquisizione o riproduzione delle immagini come scanner, fotocopiatrici e stampanti. 
Introduzione  
  
 
7 
 In ambito scientifico possiamo pensare invece ad applicazioni in cui si vuole 
preservare la qualità soprattutto lungo i bordi: ad esempio immagini aeree per la 
topografia o il controllo del territorio. 
 
Capitolo 1 Rappresentazione nel dominio Wavelet 
 
 
8 
 
CAPITOLO 1 
Rappresentazione nel dominio Wavelet 
 
La citazione dei meccanismi della visione naturale è abbastanza frequente nel 
mondo dell‟elaborazione delle immagini: da un lato il ricorso ad analogie con modelli di 
percezione è stato utile in problemi che riguardano la qualità di presentazione a fruitori 
umani (ad esempio nello studio di procedimenti di compressione), dall‟altro l‟utilizzo di 
questa metodologia non appare altrettanto scontato nel momento in cui si considerano 
problemi di analisi o interpretazione automatica del contenuto delle immagini. 
Tra i sistemi visivi delle diverse specie animali, quello dell‟uomo è considerato un 
ottimo sistema di elaborazione visuale, e quindi gli studi nell‟ambito delle elaborazione 
delle immagini non possono prescindere dalle conoscenze ad esso relative: tra quelle 
più consolidate attorno la visione dei mammiferi va sicuramente annoverata la 
rappresentazione a risoluzione differenziata.  
Il modello multicanale è stato utilizzato per spiegare molti processi biologici di 
basso livello: in particolare molti studi hanno evidenziato come l‟immagine retinica si 
possa pensare decomposta in canali di diversa frequenza orientati spazialmente. 
L‟occhio umano può essere visto come un insieme di filtri passa-banda di uguale 
larghezza, indipendenti ed aventi selettività spaziale. 
Il concetto di canali multifrequenziali viene applicato nel campo dell‟elaborazione 
delle immagini sotto  il nome di analisi multirisoluzione. 
Nel considerare proprio questo tipo di decomposizione, faremo riferimento alla 
trasformata Wavelet, ovvero uno strumento matematico che negli ultimi anni si è 
diffuso moltissimo per la sua notevole adattabilità a tecniche di compressione e 
codifica, rilevazione dei bordi, strutture e tessiture nelle immagini. 
Capitolo 1 Rappresentazione nel dominio Wavelet 
 
 
9 
Appartenendo alla categoria delle trasformate, essa permette di decomporre un 
segnale in una combinazione lineare di particolari funzioni, che nel nostro caso, avranno 
la peculiarità di essere oscillanti e localizzate nello spazio (o nel tempo). 
Con questo tipo di decomposizione è possibile ottenere una rappresentazione 
intermedia spazio-frequenza,che permetta di conoscere il contenuto spettrale in una 
particolare zona del segnale d‟interesse. 
Tale regione definisce proprio la risoluzione con la quale studiamo la nostra 
immagine e affinché l‟analisi sia completa, è necessario variare la finestra spaziale, 
ovvero disporre di più di una risoluzione. 
Il presente capitolo intende esporre in maniera esauriente e compiuta i punti 
precedentemente appena accennati, e descrivere più nel dettaglio la particolare classe di 
trasformate Wavelet utilizzate in questo lavoro di tesi,ovvero le Wavelet circolari 
armoniche di Laguerre-Gauss.  
 
1.1 Analisi multirisoluzione 
Nell‟ambito dell‟elaborazione delle immagini si definisce risoluzione, la dimensione 
della finestra spaziale all‟interno della quale è possibile osservare un cambiamento 
(nella forma degli oggetti in un‟immagine o più in generale nell‟andamento di un 
segnale): questo concetto è di fondamentale importanza in quanto il contenuto 
informativo di un‟immagine non può essere estratto analizzando soltanto i valori 
puntuali dell‟intensità,ma è bensì necessario considerarne le variazioni locali in un 
intorno di larghezza predefinita. 
Le dimensioni dell‟intorno in cui queste variazioni vengono calcolate, deve essere 
però adattato alle caratteristiche dell‟oggetto che vogliamo studiare: generalmente, le 
strutture di interesse hanno dimensioni molto diverse, per cui non è possibile definire a 
priori una risoluzione ottimale alla quale analizzare un‟immagine. Una decomposizione 
multirisoluzione, invece, permette di ottenere un‟interpretazione indipendente dalle 
dimensioni. 
Capitolo 1 Rappresentazione nel dominio Wavelet 
 
 
10 
Questa considerazione suggerisce di utilizzare risoluzioni diverse, adatte alla 
particolare struttura in esame: data una sequenza di risoluzioni crescenti 
Zjjr   )( , i 
dettagli di un‟immagine alla risoluzione rj sono definiti come la differenza di 
informazione tra la sua approssimazione alla risoluzione rj e quella alla risoluzione 
minore rj-1. 
Una rappresentazione multirisoluzione risulta essere indipendente dalle dimensioni 
se i parametri di risoluzione variano esponenzialmente [1]. In molti casi per 
semplificare la complessità computazionale degli algoritmi si sceglie 
j
jr 2  , ottenendo 
così quella che viene detta una scala diadica di risoluzioni. 
La decomposizione a multirisoluzione  stabilisce quindi un semplice modello 
gerarchico per rappresentare ed interpretare l‟informazione visiva: a basse risoluzioni si 
mette in risalto il contesto dell‟immagine, mentre man mano che le si incrementa  
vengono individuate le caratteristiche particolari. 
Facendo un esempio, consideriamo l‟immagine di una superficie costiera ripresa da 
satellite: a bassa risoluzione si può distinguere solo la forma della costa ma, se la si 
incrementa, vengono messi in evidenza i rilievi della regione; aumentandola 
ulteriormente si riescono a distinguere diversi tipi di vegetazione locale. 
Formalizzando quanto introdotto, sia 
jA2  l‟operatore che approssima un segnale alla 
risoluzione 2j. Si suppone di analizzare segnali f(x) misurabili e ad energia finita, ossia: 
)()( 2 RL  xf . L‟operatore 
jA2  è lineare e corrisponde ad una proiezione ortogonale di 
f(x) in un particolare spazio vettoriale 
)(22 RLV   j , che può essere interpretato come 
l‟insieme di tutte le possibili approssimazioni alla risoluzione 2j delle funzioni in L2(R). 
Calcolando l‟approssimazione di f(x) alla risoluzione 2j, si ha una certa perdita di 
informazione. 
Comunque, se la risoluzione tende a  φ   il segnale approssimato dovrebbe 
convergere al segnale originale mentre, se la risoluzione tende a zero, il segnale 
approssimato dovrebbe contenere sempre meno informazione e convergere a zero. Ogni 
Capitolo 1 Rappresentazione nel dominio Wavelet 
 
 
11 
insieme di spazi vettoriali 
ZV   jj )( 2  che soddisfi queste condizioni viene detto 
approssimazione multirisoluzione di L2(R). 
A questo punto, per caratterizzare numericamente l‟operatore 
jA2  dobbiamo trovare 
una base ortonormale di 
j2V . Si dimostra [1] che una tale base può essere definita 
dilatando e traslando una singola funzione. 
In particolare esiste ed è unica una funzione )()( 2 RL  x Ι , detta funzione scalante, 
tale che, posto 
)2(2)(2 xx jjj  ΙΙ    con Z  j , allora: 
     Z       njj nxj )2(2 2Ι  (1.1) 
è una base ortonormale di 
j2V . 
L‟approssimazione del segnale f(x) alla risoluzione 2j, 
)(2 xfA j , può quindi essere 
rappresentata dall‟insieme di prodotti scalari: 
     Z       njd nuuffA jj )2(),( 22  Ι (1.2) 
fAdj2  è detta approssimazione discreta di f(x) alla risoluzione 2
j
. 
 
1.2 Trasformata di Gabor o trasformata finestrata di Fourier 
E‟ ben noto come un qualsiasi segnale, che per comodità  di rappresentazione 
consideriamo monodimensionale, ad esempio f(t), possa essere rappresentato mediante 
una somma pesata di funzioni base: 
 
)()( tctf i
i
i )  ƒ  (1.3) 
Tali funzioni dipendono dalla particolare trasformazione utilizzata e, tutta l‟ 
informazione relativa al segnale è contenuta nei pesi, ovvero nei coefficienti della 
trasformazione stessa: ad esempio vengono utilizzate delle funzioni trigonometriche 
complesse nel caso della trasformata di Fourier, delle trigonometriche reali nel caso 
della DCT, etc. 
Capitolo 1 Rappresentazione nel dominio Wavelet 
 
 
12 
Il problema relativo a questo tipo di trasformazioni, è quello di far uso di funzioni 
non locali nel dominio spaziale o temporale:in questo modo tutte le componenti del 
dominio trasformato sono necessarie per ottenere l‟informazione sul segnale in un punto 
o istante stabilito, così come è necessario tutto il segnale per avere informazione su una 
frequenza specifica. 
Dunque, proprio la trasformata di Fourier, che nel recente passato è stata il 
principale strumento per l‟analisi delle singolarità dei segnali, sebbene produca una 
descrizione del contenuto armonico di un segnale in tutto il suo dominio, ben 
evidenziando le sue caratteristiche di regolarità, non è però adatta per determinare la 
posizione e la distribuzione spaziale delle singolarità. 
Rifacendoci alla formulazione del principio di indeterminazione di Heisenberg per 
l‟elaborazione dei segnali, che afferma l‟impossibilità di conoscere una frequenza e la 
sua posizione precisa nel dominio spaziale o temporale, ovvero 21 τ ∋ ∋ Ζt , possiamo 
dire che la risoluzione temporale e la risoluzione frequenziale non possono essere rese 
arbitrariamente piccole allo stesso tempo. 
Tutto questo non è limitante per segnali stazionari poiché permette di rilevare 
perfettamente fenomeni che avvengono nel dominio della frequenza, ma è poco adatto a 
segnali non stazionari poiché non discrimina i fenomeni nel tempo. 
Per ovviare a questo tipo di problema, l‟idea è quella di inserire una dipendenza dal 
tempo moltiplicando per una finestra che trasla in tale dominio: a tal fine, nel 1946, 
Gabor ideò una variante della trasformata di Fourier, capace di analizzare solo una 
porzione del segnale alla volta (windowing del segnale). 
La Trasformata finestrata di Fourier, nel punto Ω alla frequenza  Ζ , è definita come: 
 
dtetgtfGf tj ≥ φφ      Ζ Ω Ω Ζ )()(),(  (1.4)  
Questa definizione fu introdotta da Gabor che indicò la finestra g(t) come una 
funzione Gaussiana; in seguito essa venne estesa a funzioni g(t) di qualsiasi tipo. 
Capitolo 1 Rappresentazione nel dominio Wavelet 
 
 
13 
In generale g(t) deve essere una funzione reale pari e l‟energia della sua trasformata 
di Fourier  concentrata intorno alle sue basse frequenze: può quindi essere interpretata 
come la risposta impulsiva di un filtro passabasso. 
La trasformata di Fourier finestrata, anche detta Short Time Fourier Transform 
(STFT) trasforma un segnale 1-D f(t) in una funzione 2-D del tempo e della frequenza, 
ove  Ω  rappresenta la posizione di applicazione della finestra, che nella sua forma più 
semplice è rappresentata da un rettangolo di altezza unitaria. 
 
 
Figura  1.1:  Windowing del segnale f(t) 
 
Una finestra larga può consentire l‟analisi di una regione ampia del segnale, con 
un‟accuratezza spesso sufficiente per quanto riguarda la risoluzione frequenziale, 
mentre una finestra stretta può consentire l‟analisi di una piccola porzione del segnale, 
con accuratezza legata alla risoluzione dei dettagli: lo svantaggio di questo approccio è 
che, una volta scelta la dimensione della finestra, essa rimane la stessa per tutte le 
frequenze. 
E‟ però sicuramente preferibile un approccio più flessibile, che consenta di variare 
la dimensione della finestra in modo da destinare la precisione maggiore o al tempo o 
alla frequenza. 
Capitolo 1 Rappresentazione nel dominio Wavelet 
 
 
14 
1.3 Dalla STFT alla CWT 
Come già esposto nel paragrafo precedente, la STFT ha l‟inconveniente di effettuare 
la moltiplicazione per una finestra temporale, e ciò equivale a fare una convoluzione in 
frequenza, ovvero alterare lo spettro del segnale originario. Per diminuire tale effetto 
occorrerebbe ridurre la banda 
f ∋  relativa alla finestra, ma ciò comporterebbe una 
diminuzione della precisione: due eventi separati nel tempo da meno di t ∋ , non 
sarebbero più discriminabili. 
Si arriva così a definire la Trasformata Wavelet continua, introdotta da Morlet e 
Grossmann ed esprimibile come la decomposizione di un segnale in una famiglia di 
funzioni che sono traslazione e dilatazione di un‟unica funzione )()( 2 RLx    < ), con  
)(2 RL spazio vettoriale delle funzioni f(x) misurabili. 
E‟ così possibile utilizzare intervalli di tempo lunghi laddove si desiderano 
informazioni più precise a bassa frequenza, ed intervalli più brevi se l‟obbiettivo è una 
maggiore precisione alle alte frequenze: questo approccio rende le Wavelet 
particolarmente adatte all‟analisi delle caratteristiche locali di un‟ immagine. 
In questo tipo di analisi si fa perciò uso di funzioni base,  ⊥ i < , che sono versioni 
scalate e traslate di uno stesso prototipo  < , detto Wavelet madre. 
Lo scaling è effettuato moltiplicando l‟argomento della funzione per un fattore di 
scala mentre la traslazione è ottenuta considerando tutti i possibili valori iniziali delle 
finestre di analisi. 
Le varie funzioni Wavelet possono perciò essere definite tramite la seguente 
relazione: 
         2,11 Ruauxaa ÷≠• ♦♥♣   <  (1.5) 
ove s rappresenta il parametro di scala, mentre u quello di traslazione. 
La trasformata Wavelet di una generica funzione f(x) si può allora scrivere: 
           dxxxfdxuxaaxfuaWf au )(11),( **  ≥ ≥  φφ  φφ < ÷≠• ♦♥♣   <  (1.6)