Tecniche di compressione di immagini di contorni nel dominio wavelet

  
 
 
 
© Pietro Gallina  - 13 - 
L’utente può interagire con questi oggetti riposizionandoli all’interno del filmato oppure 
selezionandoli per accedere a dei nuovi contenuti multimediali (attraverso dei link attivi). 
Anche lo standard MPEG-7 prevede una codifica efficiente degli oggetti per raggiungere i 
seguenti obiettivi: ricercare delle informazioni (retrieval), esplorare i contenuti (browsing) e 
selezionare le informazioni da mantenere (filtering).  
In alcune applicazioni moderne, come nel caso delle videoconferenze oppure della 
compressione a bassi bitrate, è tollerata una perdita d’informazione, per assicurare minori 
ritardi di trasmissione oppure un migliore rapporto di compressione. Bisogna quindi 
distinguere 2 famiglie fondamentali: le tecniche lossless, che mantengono inalterata 
l’informazione da codificare, e le tecniche lossy, che eliminano i dettagli più trascurabili 
garantendo comunque una qualità percettivamente accettabile.  
Un ulteriore aspetto importante è la decodifica progressiva e cioè la possibilità di aggiungere 
gradualmente i dettagli in base ai bit giunti in ricezione. Le informazioni vengono incluse 
nel bitstream in base alla loro significatività. Questa proprietà è particolarmente utile nelle 
applicazioni a basso ritardo, che devono poter decodificare l’informazione, anche solo 
parzialmente, pur nell’eventualità che le condizioni della rete di trasmissione non 
consentano di rispettare le tempistiche prefissate. 
 
1.2 Obiettivi del metodo proposto 
Gli obiettivi del metodo di codifica dei contorni proposto in questo lavoro di tesi sono: 
 
1. codifica sia di tipo lossy, che lossless  
2. conservazione del contenuto semantico, anche ad elevati rapporti di compressione 
3. decodifica progressiva. 
 
I contorni vengono compressi impiegando la scomposizione nel dominio wavelet, che 
permette di analizzare un segnale efficientemente a vari livelli di risoluzione. 
In figura 1 viene mostrato il quadro sinottico del progetto. In primo luogo si determinano i 
contorni dell’immagine assegnata con delle metodologie standard; questo passaggio non è 
sempre presente perché i contorni possono derivare da delle operazioni di segmentazione. I 
  
 
 
 
© Pietro Gallina  - 14 - 
punti di contorno vengono collegati in un’unica sequenza che ne specifica le ascisse e le 
ordinate. La sequenza ottenuta viene trasformata nel dominio wavelet e codificata con 
l’algoritmo SPHIT (Set Partitioning in Hierarchical Trees). Infine si assemblano tutte le 
informazioni in una stringa binaria costituita da un header e dall’output di SPHIT.  
 
 
figura 1 - quadro sinottico del metodo proposto 
In fase di decodifica i passaggi precedenti vengono eseguiti a ritroso, fino alla derivazione 
dei contorni decodificati. 
In generale vengono distinti 2 casi:  
 
1. mappe di contorni generiche, con un numero arbitrario di segmenti di contorno non 
necessariamente connessi 
2. contorni di oggetti, contenenti il profilo (rappresentato solitamente da una linea 
chiusa) di alcuni semplici elementi. 
 
In figura 2 viene mostrato un esempio di mappa di contorni generica, mentre in figura 3 
sono riportati i profili di 2 semplici “oggetti” (i.e. 2 bambini che giocano). 
 
 
figura 2 - mappa di contorni generica 
  
 
 
 
© Pietro Gallina  - 15 - 
 
 
figura 3 - mappa di contorni di oggetti 
Nell’affrontare i 2 casi verranno adottate delle strategie di compressione differenti. 
 
1.3 Organizzazione della tesi 
Nel II capitolo vengono presentate le più importanti tecniche di compressione dei contorni 
riportate in letteratura scientifica. Il III capitolo è dedicato alla descrizione della codifica nel 
dominio wavelet ed all’algoritmo SPHIT.  
Dal IV al VI capitolo vengono spiegati i vari passaggi della tecnica di compressione 
proposta: il IV capitolo è dedicato alla descrizione ed alla valutazione delle tecniche di 
rilevazione dei contorni; nel V capitolo vengono spiegati i metodi per collegare i punti di 
contorno in un’unica sequenza; il VI capitolo è dedicato alla scomposizione wavelet ed alla 
codifica con SPHIT. Nel VII capitolo il metodo proposto viene confrontato con delle altre 
tecniche per la compressione dei punti di contorno. Infine nell’ultimo capitolo verranno 
tratte le conclusioni dell’intero lavoro di tesi di laurea. 
 
  
 
 
 
© Pietro Gallina  - 16 - 
1.4 Note tecniche 
Tutte le simulazioni sono state fatte impiegando Matlab® 6.5, ad eccezione di alcuni test 
sulla codifica wavelet dove è stato utilizzato il sofwtare VCDemo, sviluppato 
dall’Information and Communication Theory Group della Delft University of Technology. 
Tutte le immagini di test originali sono riportate in appendice. 
  
 
 
 
© Pietro Gallina  - 17 - 
 
 
 
 
 
CAPITOLO  2 Tecniche di compressione dei contorni 
In questo capitolo vengono presentate le più importanti tecniche per la compressione dei 
contorni, sia in ambito lossy che lossless.  
In generale si possono distinguere 2 famiglie:  
 
1. tecniche che interpretano i contorni come una mappa binaria di pixel (bitmap-based) 
2. tecniche che considerano i contorni come delle sequenze di punti logicamente 
connessi (contour-based). 
 
I metodi appartenenti alla seconda famiglia (come la tecnica descritta in questa tesi, i chain 
code, i descrittori di Fourier, ecc…) sono solitamente più efficienti e garantiscono una 
compressione lossy percettivamente meno fastidiosa. In figura 4 viene mostrata 
un’immagine codificata al medesimo bitrate con un metodo bitmap-based (che in decodifica 
interpola i pixel mancanti con quelli adiacenti) ed uno contour-based. L’immagine 
compressa con quest’ultimo approccio è percettivamente più gradevole rispetto a quella 
codificata con il metodo bitmap-based, che invece introduce degli artefatti fastidiosi. Lo 
svantaggio delle tecniche contour-based  è dato dalla maggiore complessità. 
 
Capitolo 
  
 
 
 
© Pietro Gallina  - 18 - 
 
figura 4 - codifica lossy con un metodo bitmap-based (a sinistra) ed uno contour-based   
 
2.1 Chain code  
I chain code ([1], [2], [3]) sono dei metodi contour-based, che vennero originariamente 
proposti nel 1961 da Freeman ([4]). L’idea fondamentale è quella di inseguire il contorno di 
un oggetto e di codificare progressivamente la direzione da seguire. Ad ogni spezzone di 
contorno disgiunto dagli altri vengono associate le coordinate del punto iniziale, per 
localizzare nello spazio il tratto codificato. Le direzioni ammesse sono solitamente limitate, 
in modo da incrementare l’efficienza di codifica. In figura 5 vengono mostrate alcune delle 
convenzioni adottate più frequentemente: 
 
1. nel caso della 4-connectivity si può procedere solo orizzontalmente oppure 
verticalmente  
2. nel caso della 8-connectivity è consentito procedere sia in obliquo, che in orizzontale 
ed in verticale 
3. nel caso della 6-connectivity gli spostamenti sono definiti fra i bordi dei pixel e non 
fra i baricentri degli stessi (come avviene invece nei 2 casi precedenti). 
 
Quest’ultima è una rappresentazione più naturale, ma è più complessa da realizzare rispetto 
agli altri approcci. 
  
 
 
 
© Pietro Gallina  - 19 - 
 
figura 5 - da sinistra: 4-connectivity, 8-connectivity e 6-connectivity 
 
 
figura 6 - esempio di contorno (a sinistra) ed associazione dei simboli alle direzioni 
In figura 6 viene mostrato un esempio di contorno a cui è associato il chain code seguente 
(secondo la 4-connectivity riportata nella medesima figura): 
2, 1, 1, 2, 1, 3, 1, 3, 4, 4 
In questo caso sono necessari 2 bit per descrivere ogni punto di contorno.  
Sono state proposte numerose varianti dei chain code di Freeman: chain code differenziali 
che sfruttano la dipendenza statistica fra 2 direzioni adiacenti, chain code che prevedono una 
semplificazione dei contorni per migliorare l’efficienza di codifica, chain code che adattano 
dinamicamente l’associazione dei simboli alle direzioni, ecc…  
In [5] si dimostra come i chain code consentano di ottenere una codifica lossless con 
mediamente 1.2 bit/punto di contorno nel caso della 4-connectivity e 1.4 bit/punto di contorno nel caso 
  
 
 
 
© Pietro Gallina  - 20 - 
della 8-connectivity; a questi bitrate bisogna inoltre aggiungere il costo per l’inizializzazione 
di tutti i segmenti di contorno. Pertanto i chain code comprimo in maniera estremamente 
efficiente; hanno tuttavia lo svantaggio che sono sensibili ad eventuali errori introdotti dal 
canale di trasmissione. 
 
2.2 Descrittori di Fourier 
I descrittori di Fourier ([1], [2]) sono un metodo contour-based ed infatti interpretano i punti 
di contorno come una sequenza di numeri complessi: 
 )()()( kyikxks ⋅+= , con 1,...,1,0 −= Nk  
dove )(kx  è la sequenza delle ascisse di tutti i punti di contorno ed )(ky  la sequenza delle 
rispettive ordinate. Se )(ks è periodica di periodo N  (i.e. la linea formata dai punti di 
contorno è chiusa), allora i descrittori di Fourier coincidono con i coefficienti della DFT 
(Discrete Fourier Transform) di )(ks : 
 ∑
−
=
−⋅=ℑ
1
0
)
2
exp()(
1
)(
N
k N
fk
iks
N
f
p
, con 1,...,1,0 −= Nf  
La serie dei coefficienti può essere troncata ai primi elementi, che sono tipicamente quelli 
più significativi. 
I descrittori di Fourier hanno le seguenti proprietà: 
 
1. una traslazione dei contorni corrisponde ad un variazione del coefficiente in 0=f  
2. una rotazione di una angolo J  equivale ad una moltiplicazione dei coefficienti 
trasformati per )exp( J⋅i  
3. un cambio di scala comporta la moltiplicazione dei descrittori per i medesimi fattori 
di scala 
4. modificando il punto iniziale della sequenza non si altera il modulo dei coefficienti, 
ma solamente la fase. 
 
Queste proprietà sono particolarmente utili nell’ambito del riconoscimento di forme note, 
che è il campo in cui i descrittori di Fourier vengono prevalentemente impiegati. Viceversa 
  
 
 
 
© Pietro Gallina  - 21 - 
questi descrittori non sono competitivi per comprimere i contorni di immagini naturali ed 
infatti richiedono in media 3 bit/punto di contorno nel caso lossless. 
 
2.3 Metodo Baseline-Based  
Il metodo Baseline-Based ([6]) è un’evoluzione dei chain code ma, a differenza di questi 
ultimi, consente una compressione di tipo lossy.  
I contorni da codificare vengono posizionati in un sistema di coordinate, tale per cui la 
proiezione degli stessi contorni sull’asse delle ascisse (detta “baseline”) sia la più lunga 
possibile. In figura 7 viene riportato il sistema di riferimento adottato per una generica linea 
di contorno. 
 
 
figura 7 - baseline di un generico contorno (punti numerati) 
Il contorno viene percorso in senso orario e si codificano, in maniera differenziale, le 
distanze dei punti dalla baseline. In corrispondenza di un cambio di direzione (i.e. non viene 
  
 
 
 
© Pietro Gallina  - 22 - 
più proseguita la direzione data dai punti precedenti) si segnala all’interno del bitstream un 
“turning point”. I punti di contorno possono essere decimati di un fattore 2, 4, 8 oppure 16, 
in modo da ridurre il bitrate (a condizione che l’errore di ricostruzione non ecceda una soglia 
prefissata). In fase di decodifica i valori mancanti vengono linearmente interpolati dai 
campioni rimanenti. Per minimizzare l’errore di ricostruzione i punti di contorno possono 
essere spostati di ±1 pixel verticalmente oppure orizzontalmente. Nel caso della codifica 
lossless questa tecnica corrisponde intrinsecamente ad un chain code e quindi riesce ad 
eguagliarne le prestazioni. Per ridurre il bitrate le distanze dalla baseline ed i turning point 
vengono codificati entropicamente.  
La tecnica Baseline-Based assicura un ottima efficienza di codifica e, per questo motivo, è 
stata presa in considerazione nella fase di standardizzazione di MPEG-4. Tuttavia è stata 
scartata a causa dell’elevata complessità dell’hardware del CODEC (la coppia costituita dal 
codificatore e dal decodificatore). 
 
2.4 Metodo Vertex-Based  
Questo metodo segue l’approccio contour-based e consente una codifica di tipo lossy ([1]). 
L’obiettivo è di creare una linea poligonale, che approssimi al meglio il contorno da 
codificare. Nel bitstream vengono incluse unicamente le posizioni dei vertici della linea, che 
sono stati stabilite dal codificatore. 
L’algoritmo prevede innanzitutto di individuare l’asse più lungo dell’oggetto da codificare 
(in figura 8 il tratto AB ); le estremità dell’asse rappresentano i vertici iniziali. Quindi, per 
ognuno dei segmenti che compongono il poligono (inizialmente sono solo 2), vengono 
ripetute iterativamente le seguenti operazioni: 
 
1. si calcola l’errore massimo )(max kd , fra il k-esimo segmento ed il contorno originale 
2. se ∗≥ maxmax )( dkd  (dove 
∗
maxd  corrisponde ad una soglia prefissata) si inserisce un 
nuovo vertice in corrispondenza dell’intersezione fra l’asse del punto del segmento 
che ha causato l’errore massimo ed il contorno originale, in modo da dividere in 2 
parti lo stesso k-esimo segmento