Tesi specialistica
Facoltà di Scienze MM.FF.NN
Corso di laurea in Informatica
Relatore:
Chr.mo prof.
Bruno Carpentieri.
Candidato:
Giuseppe Delle Donne
Mat.:0521000575.
<< Laboratorio specialistico di Compressione Dati >>
Compressione
Lossless
Di immagini Iperspettrali
22/07/2010
2
Compressione Dati – 1
 La definizione banale di compressione dati è appunto
ridurre la rappresentazione in memoria di un dato:
 Ridurre lo spazio necessario per la memorizzazione;
 Ridurre utilizzo di banda per inviare un dato.
 Con le tecnologie disponibili oggi potrebbe sembrare
inutile parlare di compressione:
 Dispositivi mobili poco potenti;
 Sempre maggiori richieste da parte degli utenti.
22/07/2010
3
Compressione Dati – 2
 La definizione moderna di compressione dati è:
“Ricavare dai dati originali un nuovo modello associato e una
distribuzione di probabilità dei simboli del modello”
 Il modello T e la distribuzione ∏ saranno l’input di un
Codificatore Entropico il quale in base alla
distribuzione restituisce la massima compressione
possibile in termini di Entropia.
:) ∏
Modellazione
22/07/2010
Codificatore
Entropico
4
Compressione
Lossless
Di immagini Iperspettrali
22/07/2010
5
Lossless e Lossy a confronto
 La compressione Lossless è un tipo di compressione che
riforma il dato originale esattamente com’era in partenza.
 Al contrario la compressione Lossy (con perdita di
informazione ) o Near Lossless (con perdita di
informazione
contenuta in un range dato), non
ricostruiscono il dato originale.
Compressione
Decompressione
22/07/2010
6
Compressione
Lossless
Di immagini Iperspettrali
22/07/2010
7
Immagini iperspettrali
 La definizione :
 Immagine multidimensionale in cui sono raccolte ed
elaborate tutte le informazioni provenienti da tutto lo
spettro elettromagnetico dell'oggetto osservato.
i,j
X1
…
…
XN
22/07/2010
8
Lo spettro elettromagnetico
 Lo spettro elettromagnetico è l'intervallo di tutte le
possibili frequenze delle radiazioni (onde
elettromagnetiche).
 Con la vista riusciamo a percepire lunghezze d'onda
comprese tra i 380 e i 760 nanometri (nm) a cui diamo
il nome di luce visibile.
22/07/2010
9
Impronta digitale degli oggetti
 L'osservazione dello spettro della luce riflessa degli oggetti
ha mostrato che ognuno di loro "lascia" un'univoca
"fingerprints" su tutto lo spettro elettromagnetico.
 Le fingerprints sono conosciute come le firme spettrali e
consentono l'identificazione dei diversi tipi di materiali che
compongono l'oggetto sotto osservazione.
 Ad esempio: con la firma spettrale del petrolio è possibile aiutare i mineralogisti a
trovare nuovi pozzi di petrolio.
22/07/2010
10
Applicazione delle immagini
iperspettrali
 Il telerilevamento iperspettrale è usato in una vasta gamma di applicazioni
reali.
 Originariamente usate in:
 ambito militare
 applicazioni minerarie
 geologia
 Oggi usate anche in:
 ecologia
 sorveglianza
 l'archeologia
 ricerca storica
 Tuttavia, questa tecnologia è sempre più a disposizione del pubblico, quindi
inizia ad essere utilizzata in una vasta varietà di modi realizzando applicazioni
in ogni campo della scienza.
22/07/2010
11
AVIRIS -
Airborne Visible/Infrared Imaging Spectrometer
Caratteristiche:
 La risoluzione spaziale copre un'area di
20x20 metri per pixel
 La luce riflessa è suddivisa in 224 bande
contigue, ognuna di esse ampia 10nm
 L'intervallo dello spettro va da 400-2500nm
 Le componenti spettrali sono acquisite con
un ADC (Analog-to-Digital Converter) a 12
bit
 Gli elementi dello spettro, dopo aver
effettuato la calibrazione e le dovute
correzioni geometriche, sono rappresentati
con una precisione di 16 bits
22/07/2010
12
Correlazione Spaziale e Spettrale
 Per comprimere le immagini iperspettrali sfruttiamo la
correlazione spaziale e spettrale.
 Correlazione spaziale:
 In pixel adiacenti c’è tendenza ad avere materiali
comuni.
 Correlazione spettrale:
 Si intende, nelle immagini iperspettrali, la capacità
tramite la quale una banda può essere interamente o
parzialmente predetta dalle bande precedenti.
22/07/2010
13
L’algoritmo SLSQ - Spectral
oriented Least SQuares
 È l’attuale stato dell’arte;
 È un algoritmo a basso costo computazionale.
 Si basa sulla predizione lineare.
 Suddivide i contesti in due tipi:
 Intra-band: dove applica la predizione lineare;
 Inter-band: dove applica una predizione lineare
ottimizzata in 3d (Spectral oriented Least SQuares–
SLSQ).
22/07/2010
14
SLSQ: i predittori – 1
SLSQ abbatte la correlazione spaziale e spettrale usando
due predittori:
1. Per il contesto intra-band usa un predittore lineare
ispirato a quello usato in JPEG-LS:
22/07/2010
15
SLSQ: i predittori – 2
2. Per le restanti bande usa SLSQ, il quale calcola un
predittore lineare ottimo tenendo in considerazione
un contesto 3D:
22/07/2010
16
Il nostro lavoro
 Il lavoro della tesi è diviso essenzialmente in tre parti:
1.
2.
3.
22/07/2010
Implementare l’algoritmo originale ( di Francesco
Rizzo, Bruno Carpentieri, Giovanni Motta, eJames A.
Storer);
Verificare il gap fra le implementazioni;
Scovare un’approccio per migliorare la compressione.
17
Implementazione
 L’algoritmo è stato implementato in c++ raggiungendo un
valore finale medio di compressione del 3.04.
 L’algoritmo è stato implementato risolvendo una serie di
problemi non descritti dall’articolo che presenta SLSQ:
 Verifica della soluzione di un sistema lineare di equazioni;
 Verifica del gap fra la versione risolutiva col sistema lineare e
con equazione singola (ponendo N=1);
 Gestione dei valori ai bordi dell’immagine, quindi non c’era
possibilità di ottenere un corretto intorno 3d;
 Gestione della memorizzazione dei dati per il compressore
entropico.
22/07/2010
18
Verificare il gap fra le
implementazioni
 Il Gap finale fra l’implementazione corrente e quella
dell’articolo è di un fattore di 0,07 circa.
 La causa è da ricercarsi ovviamente nelle differenze
dell’implementazione e nella scelta del codificatore
entropico finale.
22/07/2010
19
Migliorare la compressione
 Per migliorare la compressione si è osservato che fra
loro le bande hanno un’alta correlazione, ma ci sono
alcune che sono completamente scorrelate fra loro;
 L’articolo originale suggerisce di verificare banda per
banda l’effettiva compressione raggiunta dai due
Predittori (LP e SLSQ);
 Invece utilizzando il coefficiente di correlazione di
Pearson si è verificato che si può raggiungere la stessa
compressione e in alcuni casi superarla.
22/07/2010
20
Il coefficiente di Pearson
 Date due variabili statistiche X e Y:
 Il coefficiente assume valori compresi tra -1 e 1;
 Se ρxy > 0 le variabili x e y si dicono direttamente
correlate, oppure correlate positivamente, nel
dettaglio:
 Se 0,3 > ρxy > 0
 Se 0,7 >ρxy > 0,3
 Se ρxy > 0,7
22/07/2010
, correlazione debole;
, correlazione moderata;
, correlazione forte.
21
Conclusioni
 I limiti maggiori di questo algoritmo sono due:
 Poco Fault Tolerant;
 Debole a valori poco omogenei;
 Sviluppi futuri:
 Aumentare la precisione del coefficiente di Pearson
scovando le effettive somiglianze fra le bande
permettendo al compressore di essere sempre più
preciso e dunque performante.
22/07/2010
22