Università degli Studi di SalernoFacoltà di Scienze MM.FF.NN.Corso di laurea magistrale in InformaticaCorso di Compressione Dati in Sistemi MultimedialiUno studio empirico sulla parametrizzazione dell'algoritmo SLSQ per la compressione di

immagini iperspettrali

Dario Di Nucci - Fabio Palomba - Stefano Ricchiuti - Michele Tufano Università degli Studi di Salerno

84084 Fisciano (SA)d.dinucci, f.palomba3, s.ricchiuti, m.tufano10@studenti.unisa.it

Matricola: 0522500103, 157, 107, 173

Coordinatori del progettoProf. Bruno CarpentieriDott. Raffaele Pizzolante

PartecipantiDario Di Nucci 0522500103Fabio Palomba 0522500157

Stefano Ricchiuti 0522500107Michele Tufano 0522500173

1

Revision HistoryData Versione Descrizione Autori

31/05/2013 0.8 Introduzione, obiettivi eorganizzazione del progetto;

Dario Di NucciFabio Palomba

Stefano RicchiutiMichele Tufano

03/06/2013 0.9 Related works, analisi delproblema e definizione

dell’algoritmo SLSQ

Dario Di NucciFabio Palomba

Stefano RicchiutiMichele Tufano

04/06/2013 0.9.1 Descrizione del processo diapplicazione della modifica

richiesta

Dario Di NucciFabio Palomba

Stefano RicchiutiMichele Tufano

05/06/2013 1.0 Aggiunta dei capitoli 4 e 5 Dario Di NucciFabio Palomba

Stefano RicchiutiMichele Tufano

06/06/2013 1.0.1 Aggiunta della conclusioni edegli sviluppi futuri

Dario Di NucciFabio Palomba

Stefano RicchiutiMichele Tufano

08/06/2013 1.1 Aggiunta dell’abstract,revisione documento

Dario Di NucciFabio Palomba

Stefano RicchiutiMichele Tufano

09/06/2013 1.2 Aggiunta appendice revisione echiusura documento

Dario Di NucciFabio Palomba

Stefano RicchiutiMichele Tufano

2

IndiceAbstract 61. Introduzione 8

1.1 Le immagini spettrali ed iperspettrali 81.2 La raccolta dei dati: il telerilevamento 91.3 Le immagini AVIRIS 11

2. Related works 153. L’algoritmo SLSQ 17

3.1 Struttura di SLSQ 183.2 Una panoramica sui codificatori entropici 20

3.2.1 AC Coding 203.2.2 PAQ8 21

4. Parametrizzare SLSQ 224.1 Analisi del problema 234.2 Processo di applicazione della modifica richiesta 24

4.2.1 Assicurarsi che l’algoritmo modificato non cambi il suo comportamentoesterno 244.2.2 Ambiente di sviluppo utilizzato 264.2.3 Fase di Impact Analysis 274.2.4 Modifica dell’algoritmo di SLSQ 294.2.5 Testing dell’algoritmo 31

4.2.5.1 Ambiente di test 314.2.5.2 Problemi riscontrati 31

4.2.6 Trattare le matrici mal condizionate 324.2.6.1 Utilizzo del preprocessing 32

3

4.2.6.2 Utilizzo di una threshold 324.2.7 Modifiche all’algoritmo dopo la fase di testing 344.2.8 Confronto del risultato ottenuto con la configurazione di default 35

5. Sperimentazione dell’algoritmo 375.1 Configurazioni da testare 375.2 Descrizione del test set 415.3 Ambiente di test 435.4 Descrizione dei test 44

5.4.1 Preprocessing 445.4.2 Threshold 445.4.3 Confronto tra Preprocessing e Threshold 445.4.4 Confronto tra AC e PAQ8p 45

5.5 Risultati ottenuti 475.5.1 Preprocessing 475.5.2 Threshold 515.5.3 Confronto tra Preprocessing e Threshold 535.5.4 PAQ8p 55

6. Uso di informazioni storiche 566.1 Perché utilizzare informazioni storiche 566.2 Definizione dell’euristica per l’utilizzo di informazioni storiche 576.3 Parametrizzare la scelta del numero di errori da considerare e del pesoda assegnare a ciascuno di essi 586.4 Descrizione del test set 606.5 Confronto con SLSQ parametrizzato 61

7. Conclusioni e sviluppi futuri 648. Riferimenti 69A. APPENDICE - Sintesi risultati dei test 71

4

A.1 Preprocessing - Dataset 1 - Prime scene 72A.2 Threshold - Dataset 1 - Prime scene 73A.3 Errors Adjustment - Dataset 1 - Prime scene 74A.4 Thresold - Dataset 1 - Tutte le scene 75A.5 Threshold - Dataset 2 - Tutte le scene 76A.6 Errors Adjustment - Dataset 2 - Tutte le scene 77

5

AbstractSpectral Oriented Least SQuares (SLSQ) è un algoritmo per la compressione di immagini iperspettrali lossless a basso costo computazionale che utilizza la predizione lineare nel dominio spettrale. Precedentemente, l’algoritmo è stato implementato utilizzando una configurazione che consiste nell’utilizzo di una sola banda precedente e di quattro pixel per la predizione del pixel che si sta analizzando nella banda corrente. La prima parte di questo lavoro è consistita nell’ampliamento dell’implementazione dell’algoritmo parametrizzando il numero di bande e il numero di pixel da considerare nel calcolo delle predizioni. Nell’ambito della realizzazione della modifica è stato risolto anche il problema dell’eventuale mal condizionamento della matrice utilizzata nella risoluzione del sistema lineare necessario al processo di predizione, che causava errori rilevanti nei risultati ottenuti. Sono state modellate due diverse soluzioni: la prima che utilizza una fase di preprocessing, nella quale si individuano il valore massimo ed il valore minimo dei pixel dell’immagine per controllare le diverse predizioni, la seconda invece nella quale si utilizza una soglia α per il controllo della predizione.Una volta terminata la fase di parametrizzazione, sono stati effettuati due diversi studi empirici. Il primo volto ad individuare il miglior metodo di risoluzione del problema del mal condizionamento delle matrici, nel quale sono state confrontate le diverse implementazioni su un dataset di cinque immagini iperspettrali. Nel secondo studio l’algoritmo SLSQ parametrizzato è stato confrontato, su un dataset di dodici immagini iperspettrali, con una versione di SLSQ che utilizza le informazioni storiche per migliorare le predizioni, ovvero utilizza le informazioni sugli errori di predizione precedentemente individuati per controllare la predizione corrente.I risultati mostrano come l’algoritmo SLSQ parametrizzato con l’opzione di utilizzo di una threshold per il problema del mal condizionamento delle matrici sia non solo più efficiente

6

dell’algoritmo SLSQ parametrizzato con l’opzione di utilizzo di una fase di preprocessing per il problema del mal condizionamento delle matrici, ma si comporti in maniera nettamente migliore alla versione di SLSQ che utilizza le informazioni storiche.

7

1. Introduzione1.1 Le immagini spettrali ed iperspettraliLe immagini Iperspettrali sono una raccolta ed elaborazione di tutte le informazioni proveniente dallo spettro elettromagnetico dell'oggetto osservato.Differentemente da come si comporta l'occhio umano, il quale è stimolato solo dalla luce visibile, cioè le lunghezze d'onda comprese tra i 380 e i 760 nanometri (nm) , con le immagini Iperspettrali riveliamo le frequenze dei raggi ultravioletti e infrarossi. Esse sono molto più simili agli occhi dei "mantis shrimp" (gamberetti che assomigliano alla mantide), i quali oltre a vedere la luce visibile riescono a vedere altrettanto bene anche gli ultravioletti fino agli infrarossi. La capacità Iperspettrale, presenti in questi animaletti, li abilita a riconoscere differenti tipi di coralli, prede e predatori, i quali apparirebbero all'occhio umano come dello stesso colore e quindi indistinguibili.Da quest'osservazione, l'uomo è stato tentato e ha costruito dei sensori in grado di riprodurre la capacità Iperspettrale in modo da poter raccogliere ed elaborare tali informazioni, con l'intento di poter realizzare applicazioni nel campo dell'agricoltura, mineralogia, fisica e sorveglianza.Questi sensori, attraverso l'osservazione dell'oggetto, sono in grado di acquisire una vasta porzione dello spettro elettromagnetico. L'osservazione degli oggetti ha mostrato che ognuno di loro "lascia" un'univoca "fingerprints" (impronta digitale) su tutto lo spettro elettromagnetico. Queste 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.

8

1.2 La raccolta dei dati: il telerilevamentoL'acquisizione delle immagini multi-banda, multispettrale o iperspettrali avviene attraverso il telerilevamento (remote sensing), che viene definito come una misura della superficie terrestre effettuata mediante un sensore posto su un aeromobile o un satellite. Questi sistemi di telerilevamento forniscono oggi un supporto irrinunciabile per diverse applicazioni quali:

Osservazione delle risorse non rinnovabili; Meteorologia; Sorveglianza militare; Topografia.

Bisogna sottolineare che a seconda delle applicazioni cambiano i parametri di risoluzione spaziale, spettrale e temporale richiesti. Ad esempio, in campo meteorologico, c'è la necessità di una copertura ripetitiva e frequente (alta risoluzione temporale) con una risoluzione spaziale del telerilevamento relativamente bassa. In topografia, invece, è desiderabile la più alta risoluzione spaziale possibile, mentre non è necessaria un'alta frequenza di copertura; in campo militare oltre ai requisiti di alta risoluzione sia spaziale che temporale c'è anche la necessità di acquisire le immagini velocemente. Per quanto riguarda la risoluzione spettrale, requisito molto importante per la geologia e il monitoraggio ambientale, si passa dai sistemi multispettrali a più bassa risoluzione, come i Landsat Thematic Mapper (TM), con 7 bande spettrali, ai sistemi iperspettrali AVIRIS (Advanced Visible /InfraRed Imaging Spectrometer), dotati di sensori capaci di raggiungere risoluzioni spettrali notevolmente superiori. Il principio fisico che si trova dietro l’acquisizione remota è quello secondo il quale il livello di energia di ogni fotone di una radiazione elettromagnetica determina la sua lunghezza d’onda, così che ogni radiazione

9

elettromagnetica può essere descritta in termini della quantità di fotoni per ciascuna lunghezza d’onda. Quindi la precisione dei sensori che vengono utilizzati per la rilevazione determinano la risoluzione delle immagini acquisite. Per risoluzione intendiamo la dimensione di ogni pixel che compone l'immagine, le cui dimensioni vanno da un massimo di 10m a un minimo di 10cm. Un ruolo molto importante in una buona rilevazione di un oggetto è dato sicuramente anche dalla riflessione dello stesso, ovvero dalla sua capacità a riflettere la luce. La struttura molecolare di un oggetto determina la sua capacità di riflessione, in questo modo analizzando lo spettro della luce riflessa a diverse lunghezze d’onda è possibile riconoscere i materiali che compongono l’oggetto osservato. Studi hanno dimostrato che solo alcuni oggetti si riflettono a determinate lunghezze d'onda, ecco perchè possiamo parlare di “fingerprints”, ovvero di impronta digitale dell'oggetto osservato. Oggi, ad esempio, il telerilevamento permette di identificare con assoluta certezza il petrolio dato che esso si riflette ad una specifica lunghezza d'onda.

Tipicamente quando parliamo di sensori spettrali possiamo riferirci a due tipologie: multispettrali e iperspettrali. Entrambi sono impiegati per la misurazione di bande a diverse lunghezze d'onda.Nel caso di rilevazioni multispettrali le bande riscontrate vanno da quattro a una dozzina non contigue, infatti vengono scelte solo quelle ritenute ottimali, mentre nel caso di rilevazioni iperspettrali parleremo di dozzine e centinaia di bande contigue, capaci proprio per questo motivo di contenere più informazioni, rappresentando così il miglior modo per raccogliere i dati.

10

1.3 Le immagini AVIRISA partire dagli anni '80 il Dott. Alexander F.H. Goetz ed i suoi colleghi del NASA-JPL avviarono una rivoluzione nel telerilevamento sviluppando un nuovo potente strumento detto AVIRIS (Airborne Visible-Infra Red Imaging Spectrometer), il quale fu il primo sensore a realizzare immagini della superficie terrestre con 224 bande spettrali. Questo strumento sfruttava le nuove tecnologie allora appena nate per trasferire ad una piattaforma aerea l’analisi spettrale che già si faceva a terra. Ciò comportava la capacità di rilevare curve iperspettrali anche con l’osservazione dall’alto, e quindi di rilevare dettagliatamente i materiali presenti sulla superficie. Le immagini acquisite dallo spettrometro della NASA AVIRIS (Airborne Visible/Infrared Imaging Spectrometer ) vengono utilizzate per caratterizzare la superficie terrestre ed in particolare, per gli studi di oceanografia, scienze ambientali, neve idrologia, geologia, vulcanologia del suolo e gestione del territorio, studi atmosferici, l'agricoltura. Applicazioni in fase di sviluppo comprendono la valutazione e il monitoraggio dei rischi ambientali, come i rifiuti tossici, fuoriuscite di petrolio, e inquinamento delle acque dell'aria e della terra. Infatti grazie a questi sensori è possibile, ad esempio, analizzare i fumi di scarico che fuoriescono dalle ciminiere delle fabbriche e stabilire sia i materiali usati nel processo produttivo sia l’eventuale presenza di sostanze tossiche. Mentre nel campo dell'agricoltura è possibile analizzare la salute dei campi di frumento.Le immagini rilevate sono comprese in un intervallo dello spettro elettromagnetico che comprende la luce visibile e quella prossima all'infrarosso. I dati così costituiti formano un cubo iperspettrale , dove ogni pixel copre un area di circa 20x20 metri e la luce riflessa è scomposta in 224 bande contigue, ognuna ampia 10nm, nell’intervallo 400 – 2.500nm. L’unità di misura delle suddette immagini è la scena, un cubo di dati della dimensione di 512 righe per 614

11

colonne per 224 bande salvati come intero senza segno nel formato Big Endian, per un totale di 140 Megabyte; un’acquisizione tipica consiste di 3 o più scene. Il formato Big Endian è usato dai calcolatori per immagazzinare i dati di dimensione superiore al byte . La memorizzazione inizia dal byte più significativo fino ad arrivare a quello meno significativo. E' utilizzato maggiormente dalla Motorola e dai protocolli usati in internet. Un esempio di cubo iperspettrale ci è dato dalla seguente figura:

il dato è stato acquisito da AVIRIS il 20 agosto del 1992 con un ER-2 della NASA che sorvolava il porto di “Moffet Field”, in California (U.S.A), all'estremità meridionale di San Francisco. La parte superiore, che è rappresentata mediante falsi colori per evidenziare meglio le acque, ci riporta la superficie del porto della città ed è possibile notare anche l'aeroporto di Moffet Field. I lati del cubo mostrano tutti i 224 canali spettrali, dove distinguiamo nella regione alta, costituita

12

dai colori giallo rosso e bianco, (lunghezza d'onda di 400 nanometri) la parte visibile dello spettro, mentre nella regione bassa dove i colori prevalenti sono il nero il blu e il viola (lunghezza d'onda 2.500 nanometri), notiamo la parte dell'infrarosso.I file di un'immagine AVIRIS sono tutti contenuti in un archivio “tar.gz”, che contiene i “Flight line”, ovvero i file di calibrazione, descrizione e correzione, usati per l'acquisizione dell'immagine, e i file “scena” che rappresentano i dati veri e propri dei quali è possibile distinguere i dati di riflettanza (.rfl) e quelli di radianza (.img).

Il file “scena”, quindi conterrà tutti i valori dello spettro che verranno salvati facendo variare più velocemente la banda, seguito dalla colonna ed infine dalla riga. Quindi il primo byte del campione di riga r, colonna c e banda b si trova in posizione pos =2 (b+224 (c + 614 r)), dove abbiamo supposto che r, c, b e pos partano da zero.

13

Il problema è nell'acquisizione delle immagini, dato che producono una mole di dati piuttosto ampia. Basti pensare che 10 km di acquisizione possono raccogliere su nastro all'incirca 16 GB di informazione. Inoltre, dato il rapido sviluppo di applicativi per il supporto all’analisi e la crescente domanda per una risoluzione più elevata, sia spaziale che spettrale, e la scarsa capacità dei canali di trasmissione, non ci resta che comprimere in maniera efficiente i dati acquisiti dai sensori.

14

2. Related worksIn [1], [2] e [3] vengono analizzati diversi tipi di algoritmi di compressione per le immagini iperspettrali e, da quanto si evince, il migliore algoritmo lossless attualmente in circolazione è SLSQ, algoritmo del quale discorreremo nel capitolo successivo.In generale, le tecniche principali con cui è stata trattata la compressione delle immagini iperspettrali sono:

1. Algoritmi general purpose, liberi da brevetti ed open source come BZIP2 e GZIP; Generalmente l’algoritmo BZIP2 consente di produrre nella maggior parte dei casi file compressi molto piccoli rispetto a quelli prodotti da GZIP.

2. Algoritmi per la compressione di immagini standard come JPEG LS e JPEG 2000; Questa scelta è razionale poiché, osservando il risultato di un’estrazione dell’immagine da una banda, essa potrebbe essere trattata come una qualsiasi immagine naturale;

3. Algoritmi basati sulla Vector Quantization come LPVQ;4. Algoritmi Predittivi come LOCO-I e il già citato SLSQ.

In seguito mostriamo alcuni risultati ottenuti da [5], i quali confrontano i diversi algoritmi di compressione citati:

Immagine JPEG-LS JPEG-2000 LPVQ SLSQCuprite 2.09 1.91 3.18 3.15

Jasper Ridge 2.00 1.80 2.88 3.15Low altitude 2.14 1.96 2.94 2.98Lunar Lake 1.99 1.82 3.28 3.15

15

Moffet Field 1.91 1.78 3.00 3.14Media 2.03 1.85 3.06 3.12

I risultati dimostrano come SLSQ, in media, fornisca risultati migliori rispetto a tutti gli altri algoritmi di compressione. Altra conferma della bontà di SLSQ arriva da [6], nel quale la sezione dedicata alla compressione di Immagini Iperspettrali afferma che attualmente le tecniche prima elencate sono le uniche disponibili e fra esse la migliore soluzione è proprio SLSQ.

16

3. L’algoritmo SLSQSLSQ è un algoritmo a basso costo computazionale, ed è considerato ancora lo stato dell'arte degli algoritmi di compressione lossless per le immagini iperspettrali. SLSQ sfrutta la predizione lineare per la codifica delle bande definite come intra-band, mentre per il resto viene adottato un predittore lineare ottimizzato, di nome Spectral Oriented Least Squares (SLSQ). Il predittore per le intraband è ispirato al predittore mediano usato in JPEG-LS, mentre SLSQ, in ambito inter-band, per ogni campione, considera il coefficiente ottimo del predittore lineare, ovvero dato il sottoinsieme 3D dei dati processati viene applicato il metodo dei minimi quadrati. In questo modo l'algoritmo abbatte entrambi i tipi di correlazione che caratterizzano l'immagine iperspettrale: spaziale18 e spettrale19. Di solito, ma non sempre, la correlazione spettrale è più forte della correlazione spaziale. SLSQ propone un nuovo predittore lineare intraband chiamato LP il quale viene utilizzato su precise bande. La predizione è calcolata usando poche informazioni di contorno che seguono un pattern a L. Definito il valore della predizione e inviato al codificatore entropico (arithmetic coder) viene poi sottratto al valore predetto.

17

3.1 Struttura di SLSQIniziando dalla banda Zero il compressore comprime tutte le bande successive. Il contesto 3D è definito dai valori M (pixel prossimi a quello corrente) ed N (bande precedenti da considerare). Altri valori da definire sono k ed IB, dove k è la banda corrente ed IB è un vettore che contiene una serie di bande in cui è applica la predizione intraBand (da cui IB). Se la banda corrente k è in IB allora si usa il predittore lineare di JPEG-LS modificato detto appunto LP, dove la sua struttura è definita da:

dove X rappresenta il valore da predire. Nel caso in cui la banda non appartiene al vettore IB useremo il predittore SLSQ. Dato il pixel corrente x(0,0) l'algoritmo considererà tutti i pixel adiacenti, secondo la seguente funzione di distanza

Quindi il vettore X conterrà i predecessori ordinati in base alla distanza del livello precedente, mentre nella matrice C saranno collocati gli M predecessori per tutti gli N livelli superiori. Quindi la predizione del pixel corrente è calcolata come:

18

dove con N indichiamo l'ordinamento del predittore. Il vettore dei coefficienti di predizione ottimale αO = [α1, ..., αn] è definito da:

in modo da minimizzare la potenza dell'errore di predizione. In questo modo i dati usati nella predizione sono scelti in un sottoinsieme finito, evitando di inviare, in questo modo, informazioni al decoder.Utilizzando la notazione matriciale, scriveremo che

dove

Derivando rispetto ad α e settandola a 0, il coefficiente del predittore ottimo è il risultato del sistema lineare

Una volta individuati i coefficienti del predittore ottimo, l’errore di predizione sarà ottenuto attraverso la differenza tra il pixel corrente ed il pixel predetto, e successivamente sarà inviata al codificatore entropico.

19

3.2 Una panoramica sui codificatori entropiciIn teoria dell'informazione una codificazione entropica è uno schema di compressione dati lossless che è indipendente dalle specifiche caratteristiche del mezzo. Nell’ambito di questo lavoro sono stati utilizzati due codificatori entropici, il codificatore aritmetico e PAQ8, che verranno descritti di seguito.

3.2.1 AC CodingIl codificatore aritmetico sostituisce uno stream di simboli di input con un singolo valore floating-point. L’output del processo di codifica è rappresentato da un singolo numero reale x tale che: 0 ≤ x ≤ 1. Questo singolo numero reale può essere unicamente decodificato per riprodurre l’esatto stream di simboli.Una volta che le probabilità di apparizione dei caratteri sono note, i singoli simboli necessitano di essere assegnati ad un range intorno alla “linea di probabilità”, ovvero in un range compreso tra 0 e 1. Ogni carattere è assegnato alla porzione del range compresa tra 0 e 1 che corrisponde alla sua probabilità di apparizione nella stringa in input. Nel dettaglio, lo pseudocodice degli algoritmi di compressione e decompressione è mostrato di seguito:

Algoritmo di compressionelow = 0.0;high = 1.0;while ( ( c = getc( input ) ) != EOF )

range = high ­ low;high = low + range * high_range( c );low = low + range * low_range( c );

output (low);

20

Algoritmo di decompressione

number = input_code();for ( ; ; )

symbol = find_symbol_straddling_this_range( number );putc( symbol );range = high_range( symbol ) ­ low_range( symbol );number = number ­ low_range( symbol );number = number / range;

3.2.2 PAQ8PAQ8 è una serie di software di archivazione che consentono di raggiungere un tasso di compressione molto elevato, a scapito della velocità di esecuzione e della memoria occupata. In particolare, PAQ8 utilizza un algoritmo context-mixing, in cui sono impiegati diversi tipi di algoritmi di codifica:

1. Arithmetic coding;2. Adaptive model weighting;3. Neural Network mixing;4. Context modeling;5. Text preprocessing.

La peculiarità dell’algoritmo consiste nell’ottenere un tasso di compressione molto più elevato rispetto agli altri codificatori. Tuttavia, però, al fine di ottenere tale risultato, è costretto a compiere un numero elevato di operazioni e richiede quindi un tempo di esecuzione di molto superiore a tutti i restanti codificatori entropici.

21

4. Parametrizzare SLSQIn questo capitolo si descriverà il problema preso in esame nell’ambito di questo progetto. In particolare, saranno descritti i dettagli relativi alla parametrizzazione dell’algoritmo SLSQ, definendo i vantaggi derivanti. Inoltre, si discuterà del modo in cui utilizzare le informazioni storiche per ottenere delle predizioni migliori, ovvero si prenderà in esame il problema di decidere se, memorizzando gli errori calcolati precedentemente, si riesce ad effettuare una predizione più vicina alla predizione ottima.Definito il problema, si procederà nella descrizione di come le modifiche all’algoritmo sono state progettate ed implementate.

22

4.1 Analisi del problemaAllo stato iniziale del progetto, l’implementazione dell’algoritmo SLSQ era strutturata in maniera tale da predirre un valore x considerando esclusivamente i quattro pixel più vicini, secondo la distanza euclidea, e una sola banda precedente.Compito di questo lavoro è modificare il tool che implementa l’algoritmo SLSQ in modo da permettere all’utente la scelta del numero di pixel vicini e del numero di bande precedenti da utilizzare. In particolare, la scelta dell’utente sarà limitata alla selezione di un numero di pixel compreso tra 1 e 16. Questo significa che il numero di pixel vicini al pixel da predirre verranno selezionati come nella figura seguente:

Il vantaggio atteso dall’uso di più pixel e/o più bande è una predizione più accurata di un pixel della banda in esame. Questo comporta un conseguente miglioramento del compression ratio (CR), ovvero una riduzione della dimensione della rappresentazione dell’immagine iperspettrale.Altro aspetto considerato nel progetto è l’utilizzo di informazioni storiche per il miglioramento della predizione. In dettaglio, si è tentato di migliorare la predizione di un pixel memorizzando gli errori precedenti, così da controllare eventuali predizioni errate.

23

4.2 Processo di applicazione della modifica richiesta

4.2.1 Assicurarsi che l’algoritmo modificato non cambi il suo comportamento esternoQuello che si intende assicurare una volta applicata la modifica richiesta consiste non solo nella modifica dell’implementazione dell’algoritmo SLSQ, ma anche e soprattutto il controllo che tale modifica produca risultati conformi ai risultati ottenuti con l’algoritmo assegnatoci inizialmente. Di seguito è mostrato il processo applicato per la modifica richiesta.

Innanzitutto, è possibile parallelizzare le attività di compresione del codice sorgente e l’attività

24

di running dell’algoritmo non parametrizzato, che ci fornisce una chiara indicazione dei risultati attesi applicando l’algoritmo parametrizzato e utilizzando la stessa configurazione dell’algoritmo non parametrizzato.La fase di comprensione del codice consente agli sviluppatori di avere un’idea chiara della struttura dell’implementazione dell’algoritmo: in questo modo, può essere identificato l’impact set, ovvero l’insieme delle classi che subiranno modifiche in seguito alla richiesta di parametrizzazione.L’output della fase di impact analysis è l’insieme degli artefatti che dovranno essere modificati: a questo punto l’implementazione della modifica può avere inizio.Il nuovo algoritmo può essere testato in cerca di errori di implementazione, prima della fase di running sulle immagini del test set messoci a disposizione. Tale fase di running dovrà essere effettuata utilizzando la stessa configurazione dell’algoritmo non parametrizzato, così da assicurare che l’output dell’algoritmo, sia prima che dopo la modifica, sia lo stesso.

25

4.2.2 Ambiente di sviluppo utilizzatoLo sviluppo di tutte le modifiche all’algoritmo SLSQ è stato svolto sulle macchine dei quattro partecipanti al progetto più un elaboratore desktop di proprietà dell’Università degli Studi di Salerno. Le caratteristiche di ciascun elaboratore sono riportate nella seguente tabella.

Sistema operativo Processore RAMUbuntu 12.04 Intel i3 8 GbUbuntu 13.04 Intel i7 8 Gb

Mac OS X 10.8.2 Intel i7 4 GbLinux Mint 15 AMD C60 4 GbLinux Mint 15 Intel Atom N270 2 Gb

Per quanto riguarda invece l’ambiente di sviluppo, sono stati utilizzati sia Eclipse Juno [9] che NetBeans 7.3 [10]. Entrambi gli IDE sono stati configurati con la versione 1.7 di OpenJDK [11]. In particolare, le modifiche all’algoritmo sono state effettuate utilizzando Eclipse Juno. C’è stata la necessità di utilizzare NetBeans 7.3 per la modifica dell’interfaccia grafica, poiché questo IDE mette a disposizione uno strumento per la creazione di interfacce grafiche tramite la funzione di drag and drop degli elementi grafici, consentendo quindi una modifica dell’interfaccia rapida ed efficace.

26

4.2.3 Fase di Impact AnalysisLa prima fase della progettazione della modifica è consistita nella definizione dell’insieme di classi che potenzialmente potevano essere impattate dalla parametrizzazione dell’algoritmo. Sostanzialmente, effettuare preventivamente uno studio del genere ci ha consentito di individuare i fattori che avrebbero potuto influire sull’implementazione del cambiamento, oltre che darci un’idea dello sforzo necessario all’implementazione e ai tempi che sarebbero occorsi.L’output di questa fase è rappresentato dall’insieme delle classi che devono essere modificate in seguito alla parametrizzazione dell’algoritmo di SLSQ, che è riassunto nella seguente tabella.

ID CLASSE NOME DELLA CLASSE1 it.unisa.slsq.algorithms.SLSQCompressionAlgorithm2 it.unisa.slsq.algorithms.SLSQDecompressionAlgorithm3 it.unisa.aviris.slsq.ui.SLSQCompressionThread4 it.unisa.aviris.slsq.ui.SLSQDecompressionThread5 it.unisa.aviris.slsq.ui.MainFrame6 it.unisa.slsq.contexts.Contexts

Le prime due classi (ID 1 e 2) necessitano di essere modificate poiché l’algoritmo di compressione e di decompressione sono state implementati tenendo fissati (hardcoded) il numero di pixel e il numero di bande utilizzate per la predizione.Le classi Thread (ID 3 e 4) sono le classi attraverso le quali sono lanciati gli algoritmi di compressione di decompressione, quindi rientrano nell’impact set poiché potenzialmente potrebbero essere soggette a modifiche.La classe it.unisa.aviris.slsq.ui.MainFrame (ID 5) rappresenta il componente principale

27

dell’interfaccia grafica, e per questo dovrà sicuramente essere modificata per aggiungere i nuovi parametri richiesti.Infine, la classe it.unisa.slsq.contexts.Contexts (ID 6) dovrà essere modificata poiché tratta lo schema secondo cui sono individuati i pixel vicini nell’algoritmo non parametrizzato. Sarà quindi necessario generalizzare la ricerca del contesto in modo da trovare lo schema giusto per qualsiasi numero di pixel e bande.

28

4.2.4 Modifica dell’algoritmo di SLSQLa prima modifica da implementare è sicuramente quella che riguarda il compressore, definito dalla classe it.unisa.slsq.algorithms.SLSQCompressionAlgorithm. Per compiere la modifica richiesta, è stato necessario aggiungere alla signature del metodo i parametri riguardanti il numero di bande e il numero di pixel da utilizzare nel processo di predizione. All’interno del metodo è stata implementata la risoluzione del sistema lineare definita nel paragrafo 3.1, utilizzando una libreria esterna chiamata Efficient Java Matrix Library [7].La classe it.unisa.slsq.algorithms.SLSQDecompressionAlgorithm che implementa il decompressore, è stata modificata per la stessa ragione della classe precedente. Sono stati quindi introdotti i parametri per il numero di bande e il numero di pixel da utilizzare nel processo di predizione all’interno della signature del metodo.Le classi it.unisa.aviris.slsq.ui.SLSQCompressionThread e it.unisa.aviris.slsq.ui.SLSQDecompressionThread sono state modificate in modo da adattare le chiamate agli algoritmi di compressione e decompressione in ragione dei nuovi parametri introdotti.All’interfaccia grafica del sistema, definita dalla classe it.unisa.aviris.slsq.ui.MainFrame, sono stati aggiunti i campi per consentire all’utente di inserire i valori relativi al numero di bande e al numero di pixel. L’interfaccia modificata è mostrata di seguito:

29

Infine, è stata aggiunta la classe it.unisa.slsq.contexts.GeneralizedContexts, poiché la classe it.unisa.slsq.contexts.Contexts era implementata ad hoc per l’analisi della sola banda corrente e la banda precedente. La nuova classe, invece, generalizza la ricerca del contesto a tutte le bande definite dall’utente.

30

4.2.5 Testing dell’algoritmoUna volta terminata l’implementazione dell’algoritmo parametrizzato SLSQ, è necessario assicurarsi che il codice scritto sia corretto. Per questa ragione sono stati eseguiti dei test al fine di individuare errori di implementazione e/o soluzioni più efficienti.

4.2.5.1 Ambiente di testI test per la verifica della correttezza dell’algoritmo sono stati svolti sulle macchine dei quattro partecipanti al progetto. Le caratteristiche di ciascun elaboratore sono riportate nella seguente tabella.

Sistema operativo Processore RAMUbuntu 13.04 Intel i7 8 Gb

Mac OS X 10.8.2 Intel i7 4 GbLinux Mint 15 AMD C60 4 GbLinux Mint 15 Intel Atom N270 2 Gb

4.2.5.2 Problemi riscontratiL’algoritmo SLSQ, per definizione, utilizza computazioni tra matrici al fine di ottenere la predizione dei pixel. La soluzione di sistemi lineari può essere influenzata dalla natura delle matrici utilizzate.Dalla teoria delle matrici sappiamo che, nel caso in cui trattiamo una matrice mal condizionata, allora piccole perturbazioni negli elementi della matrice, o piccole variazioni del vettore X utilizzato nel sistema, possono produrre grandi variazioni nelle soluzioni del sistema lineare. Nel

31

caso analizzato, ci sono diversi casi in cui le matrici possono essere mal condizionate. In particolare questo accade quando gli elementi della matrice hanno molti elementi uguali. Essendoci, all’interno della matrice, valori dei pixel nell’intorno del pixel che si intende predirre, allora è molto probabile che l’algoritmo tratti matrici mal condizionate. Si rende necessaria, dunque, una gestione delle cattive predizioni nelle matrici mal condizionate.

4.2.6 Trattare le matrici mal condizionate

4.2.6.1 Utilizzo del preprocessing

Una prima opzione per risolvere il problema delle matrici mal condizionate è introdurre una fase di preprocessing dell’immagine in input al momento della compressione, definendo il range di valori dei pixel.Si costruisce un file .range (che verrà utilizzato dal processo di decompressione) in cui vengono memorizzati il valore minimo e massimo dei pixel dell’immagine. Successivamente questi valori verranno utilizzati nella fase di predizione, sia per la compressione che per la decompressione. In particolare, quando il valore del pixel predetto non rientra nel range reale dell’immagine, si suppone ci sia stato un errore di predizione dovuto a mal condizionamento e si procede, dunque, ad una nuova predizione utilizzando un predittore mediano, non affetto dal problema sopracitato.

4.2.6.2 Utilizzo di una threshold

Una maniera alternativa per la risoluzione del problema delle matrici mal condizionate è l’utilizzo di una threshold. In dettaglio, non si effettua un preprocessing del dato in input, ma si effettua un controllo durante la fase di predizione utilizzando una soglia definita dall’utente.Se il valore del pixel predetto si discosta di un valore definito dalla soglia rispetto al valore

32

reale dello stesso pixel della banda precedente, si assume che ci sia stato un errore di predizione e quindi si effettua una nuova predizione utilizzando MedianPrediction.

33

4.2.7 Modifiche all’algoritmo dopo la fase di testingIn seguito all’analisi dei problemi riscontrati nella fase di testing, si è deciso di dare all’utente la possibilità di scelta del metodo da utilizzare per la risoluzione del problema delle matrici mal condizionate. Quindi, tutte le classi già modificate di cui si è parlato nel paragrafo 4.2.3, sono state adattate in maniera da prendere in input altri due parametri:

1. Un parametro booleano che indica la scelta dell’utente nell’utilizzare o meno il metodo di preprocessing di cui al paragrafo 4.2.4.1;

2. Un valore intero che indica la soglia scelta dall’utente, nel caso in cui venga selezionato il metodo di risoluzione del problema delle matrici mal condizionate attraverso la threshold.

L’interfaccia grafica è stata dotata di due campi che consentono l’inserimento di tali informazioni. La modifica è riportata di seguito:

34

4.2.8 Confronto del risultato ottenuto con la configurazione di defaultL’ultima fase prima della sperimentazione dell’algoritmo implementato su un test set composto da un numero maggiore di immagini iperspettrali, consiste nel confronto dell’algoritmo parametrizzato con l’algoritmo fornitoci inizialmente.In particolare, un confronto equo è stato ottenuto utilizzando la configurazione seguente:

Id configurazione Numero di pixel Numero di bandeP4_B1 4 1

I risultati ottenuti dall’applicazione dei due diversi algoritmi sull’immagine Lunar Lake, sono riportati nella seguente tabella:

Algoritmo CR BPPAlgoritmo iniziale 3.17 5.05

Algoritmo parametrizzato 3.12 5.14

La differenza tra i risultati è imputabile al fatto che i due algoritmi lavorano utilizzando strutture dati molto diverse: nel caso dell’algoritmo parametrizzato l’utilizzo di una matrice e la conseguente risoluzione di un sistema lineare provoca degli arrotondamenti che nell’altro algoritmo non sussistono, implicando una differenza nei risultati.Inoltre, i calcoli eseguiti nell’algoritmo iniziale sono calcoli ad hoc per la configurazione in esame, per questo decisamente più precisi rispetto alla risoluzione di un sistema lineare.Con l’obiettivo di fornire all’utente sempre un algoritmo capace di dare risultati migliori, si è deciso di trattare la configurazione P4_B1 in maniera separata da tutte le altre. Questo significa

35

che, nel caso in cui si lavori con questa configurazione, verrà sempre utilizzato il vecchio algoritmo, in modo da fornire una migliore compressione.

36

5. Sperimentazione dell’algoritmo5.1 Configurazioni da testareSono state individuate una serie di configurazioni che permettessero di valutare l’andamento delle due varianti dell’algoritmo utilizzate, la prima con l’uso del preprocessing e la seconda applicando una threshold. In sintesi sono state testate le configurazioni con un numero di pixel vicini da uno a sedici, considerando per ognuna da una a quattro bande. Per ogni configurazione è stato definito un id in modo da poter confrontare le differenze tra le prestazioni delle due varianti dell’algoritmo in maniera più rapida. L’id riporta nella prima parte il numero di pixel, preceduto da ‘P’, e nella seconda parte il numero di bande precedenti, dopo ‘B’.

Id Configurazione Numero di pixel Numero di bandeP1_B1 1 1P2_B1 2 1P3_B1 3 1P4_B1 4 1P5_B1 5 1P6_B1 6 1P7_B1 7 1P8_B1 8 1P9_B1 9 1

P10_B1 10 1P11_B1 11 1

37

P12_B1 12 1P13_B1 13 1P14_B1 14 1P15_B1 15 1P16_B1 16 1P1_B2 1 2P2_B2 2 2P3_B2 3 2P4_B2 4 2P5_B2 5 2P6_B2 6 2P7_B2 7 2P8_B2 8 2P9_B2 9 2

P10_B2 10 2P11_B2 11 2P12_B2 12 2P13_B2 13 2P14_B2 14 2P15_B2 15 2P16_B2 16 2P1_B3 1 3

38

P2_B3 2 3P3_B3 3 3P4_B3 4 3P5_B3 5 3P6_B3 6 3P7_B3 7 3P8_B3 8 3P9_B3 9 3

P10_B3 10 3P11_B3 11 3P12_B3 12 3P13_B3 13 3P14_B3 14 3P15_B3 15 3P16_B3 16 3P1_B4 1 4P2_B4 2 4P3_B4 3 4P4_B4 4 4P5_B4 5 4P6_B4 6 4P7_B4 7 4

39

P8_B4 8 4P9_B4 9 4

P10_B4 10 4P11_B4 11 4P12_B4 12 4P13_B4 13 4P14_B4 14 4P15_B4 15 4P16_B4 16 4

40

5.2 Descrizione del test setLe varianti dell’algoritmo sono state testate su un set di immagini iperspettrali, descritte nel paragrafo 1.3, ognuna delle quali composta da più scene. Nella tabella seguente sono descritte le caratteristiche delle immagini test.

Id Configurazione Descrizione Linee Campioni BandeDS01_IMG1_sc01 Cuprite 512 614 224DS01_IMG1_sc02 Cuprite 512 614 224DS01_IMG1_sc03 Cuprite 512 614 224DS01_IMG1_sc04 Cuprite 512 614 224DS01_IMG1_sc05 Cuprite 158 614 224DS01_IMG2_sc01 Jasper Ridge 512 614 224DS01_IMG2_sc02 Jasper Ridge 512 614 224DS01_IMG2_sc03 Jasper Ridge 512 614 224DS01_IMG2_sc04 Jasper Ridge 512 614 224DS01_IMG2_sc05 Jasper Ridge 512 614 224DS01_IMG2_sc06 Jasper Ridge 26 614 224DS01_IMG3_sc01 Low Altitude 512 614 224DS01_IMG3_sc02 Low Altitude 512 614 224DS01_IMG3_sc03 Low Altitude 512 614 224DS01_IMG3_sc04 Low Altitude 512 614 224DS01_IMG3_sc05 Low Altitude 512 614 224

41

DS01_IMG3_sc06 Low Altitude 512 614 224DS01_IMG3_sc07 Low Altitude 512 614 224DS01_IMG3_sc08 Low Altitude 105 614 224DS01_IMG4_sc01 Lunar Lake 512 614 224DS01_IMG4_sc02 Lunar Lake 512 614 224DS01_IMG4_sc03 Lunar Lake 407 614 224DS01_IMG5_sc01 Moffett Field 512 614 224DS01_IMG5_sc02 Moffett Field 512 614 224DS01_IMG5_sc03 Moffett Field 512 614 224DS01_IMG5_sc04 Moffett Field 495 614 224

42

5.3 Ambiente di testSi è preferito utilizzare un pc diverso come ambiente di test per due motivi principali:

rendere obiettivo il confronto tra le due varianti dell’algoritmo; abbassare l’impatto dei tempi necessari per l’esecuzione dei test.

Le caratteristiche principali dell’ambiente di test sono riportate in tabella.

Sistema operativo Ubuntu 12.04Processore Intel Core i3-2100 CPU @ 3.10GHz

Memoria RAM 8 Gb

43

5.4 Descrizione dei testIn questo paragrafo sono elencati i test che saranno descritti brevemente i test che si intendono effettuare per la fase di sperimentazione, insieme con le relative motivazioni.

5.4.1 PreprocessingIl test riguarda l’esecuzione dell’algoritmo SLSQ con le modalità di individuazione degli errori di predizione descritte nel paragrafo 4.2.4.1. I dati analizzati riguardano la variazione del compression ratio, utilizzato come indice prestazionale, al variare del numero di bande precedenti e di pixel utilizzati nel calcolo della predizione. Oltre alla misura delle prestazioni di compressione, è stato misurato anche il tempo di esecuzione per le varie configurazioni.Le configurazioni testate sono descritte nel paragrafo 5.1, mentre il dataset oggetto del test è descritto nel paragrafo 5.2. Gli errori di predizione sono codificati secondo la tecnica di Arithmetic Coding.

5.4.2 ThresholdIn questo test, la modalità di individuazione degli errori di predizione è effettuata confrontando la predizione SLSQ con dei valori soglia, come descritto al paragrafo 4.2.4.1.Come per il test precedente, sono stati misurati il compression ratio ed il tempo di esecuzione. Le configurazioni testate sono state ridotte rispetto al test con preprocessing per l’individuazione degli errori di predizione, secondo motivazioni e modalità descritte contestualmente all’analisi dei risultati del test, nel paragrafo 5.5.1.Gli errori di predizione sono codificati secondo la tecnica di Arithmetic Coding.

5.4.3 Confronto tra Preprocessing e ThresholdScopo dei test descritti è quello di valutare l’impatto computazionale del preprocessing rispetto

44

alla soluzione con soglia determinata dall’utente. La prima modalità non richiede alcun intervento da parte dell’utente, e garantisce una individuazione accurata degli errori di predizione in fase di compressione. Questo approccio necessita però di scorrere tutti i pixel delle immagini alla ricerca dei valori massimo e minimo prima di effettuare qualsiasi operazione di compressione, operazione che potrebbe risultare onerosa. Al contrario, la soluzione con valori di soglia individuati dall’utente non necessita di alcuna operazione preliminare alla compressione, ma potrebbe portare a falsi positivi o falsi negativi, a seconda dell’accuratezza dei valori specificati. Non essendoci alcun modo di conoscere i valori esatti a priori, questi andrebbero individuati empiricamente, sulla base di prove o esecuzioni precedenti dell’algoritmo.Un confronto tra le due modalità permette di valutare vantaggi e svantaggi di entrambi, ed eventualmente individuare la modalità che offre il miglior compromesso tra compression ratio e tempo di esecuzione.

5.4.4 Confronto tra AC e PAQ8pIl punto di forza di SLSQ è l’efficacia di compressione unita ad una bassa complessità computazionale. Questo vale quando si introducono nel calcolo della predizione valori limitatamente ad una banda precedente. Introducendo bande precedenti ulteriori a quella immediatamente precedente a quella corrente, si perde la bassa complessità tipica di SLSQ, nella ricerca di migliori prestazioni di compressione. Proprio questa considerazione, porta a valutare la possibilità di fare le stesse considerazioni per la tecnica di codifica dell’errore di predizione. Data la perdita di complessità lineare causata dall’introduzione di bande precedenti ulteriori alla prima, si prova a sostituire Aritmetic Coding con una codifica più complessa, nella fattispecie PAQ8p (vedi paragrafo 3.2), che potrebbe portare ad un compression ratio migliore.

45

Ciò che si cerca nel confronto tra queste codifiche entropiche è la possibilità di migliorare ulteriormente il compression ratio al costo della maggiore complessità della tecnica di codifica, e valutare l’impatto sui tempi di esecuzione.

46

5.5 Risultati ottenuti

5.5.1 PreprocessingDi seguito sono riportati i risultati ottenuti dalla sperimentazione sul test set specificato nel paragrafo 5.2, con l’utilizzo dell’algoritmo parametrizzato di SLSQ con l’opzione del preprocessing per la risoluzione dei problemi di mal condizionamento. Per i dati completi, fare riferimento a [8].

Il grafico è suddiviso in 4 parti, che rappresentano le diverse configurazioni relativamente al numero di bande precedenti. Per ognuna di queste parti, sull'asse delle ascisse è riportato il numero di pixel. L'asse delle ordinate riporta la performance per il singolo test, misurata come CR (Compression Ratio) medio tra tutte le immagini iperspettrali del dataset. Valori maggiori corrispondono a prestazioni migliori.Dal grafico si osserva un andamento logaritmico, all'aumentare del numero di pixel impiegati

47

per la predizione. Il valore della prestazione tende a crescere rapidamente per i primi test, per poi assestarsi per quantità di pixel maggiori. Tale andamento è comune a tutte le configurazioni con diverso numero di bande precedenti. Differentemente da quanto ci si potrebbe aspettare, la prestazione migliore corrisponde al massimo numero di pixel con 3 bande precedenti a quella corrente.Oltre alla misura delle prestazioni, è utile osservare anche il tempo di esecuzione dell'algoritmo per le diverse configurazioni, al fine di individuare un compromesso tra efficacia della compressione e tempi di attesa.

Il grafico, analogamente a quello precedente, è suddiviso per numero di bande precedenti utilizzate per la predizione. Sull'asse delle ordinate è riportato il tempo medio di esecuzione dell'algoritmo sulle diverse immagini del dataset. Valori più bassi corrispondono a prestazioni migliori. I dati sperimentali mostrano una crescita lineare rispetto al numero di pixel (salvo alcune anomalie per le configurazioni a 2, 3 e 4 bande), mentre rispetto al numero di bande, i

48

tempi aumentano del 15-20 % tra configurazioni successive. Le anomalie riscontrate nelle configurazioni 2 bande 1 pixel, 3 bande 1-2 pixel e 4 bande 1-2-3 pixel sono dovute al ricalcolo della predizione a causa di matrici malcondizionate. Per queste configurazioni, la matrice utilizzata nella soluzione del sistema lineare ha pochi elementi, i quali hanno maggior probabilità di essere uguali, e di conseguenza si riscontra un numero di matrici malcondizionate superiore a quello riscontrato per le altre configurazioni. Il consistente numero di rielaborazioni della predizione porta ad un tempo di esecuzione maggiore rispetto a configurazioni più complesse, nonostante queste richiedono molte più operazioni di calcolo per la soluzione del sistema.Come si può notare, l'ordine di grandezza del peggioramento del tempo di esecuzione all'aumentare delle bande, è di gran lunga maggiore dei miglioramenti minimi di prestazione osservabili nell'analisi del fattore di compressione. In altre parole, l'aumento del numero di bande precedenti porta ad un miglioramento solamente marginale a partire dalla configurazione a 2 bande, a fronte di un notevole peggioramento del tempo di esecuzione. Per quanto riguarda i pixel invece, scegliere la configurazione più complessa ma con CR migliore (16 pixel) non comporta drastici peggioramenti del tempo di esecuzione, rispetto a configurazioni con meno pixel ma con compression ratio solamente prossimo al massimo riscontrato.Ciò osservato, si può operare una riduzione sul numero di configurazioni di test al fine di velocizzare le sperimentazioni successive. Scopo delle sperimentazioni che seguono, infatti, non è quello di osservare l'andamento delle prestazioni per ogni configurazione possibile, ma confrontare metodi di correzione delle predizioni e codifiche dell'errore differenti, relativamente a configurazioni più vicine ad un utilizzo reale del software. Per i test successivi, si è deciso di limitare le configurazioni a quelle che seguono:

49

- 1 banda precedente, 4-8-12-16 pixel- 2 bande precedenti, 4-8-12-16 pixel- 3 bande precedenti, 4-8-12-16 pixel- 4 bande precedenti, 4-8-12-16 pixel

50

5.5.2 ThresholdSi riportano nei grafici seguenti le analisi relative al test dell’algoritmo SLSQ, con individuazione degli errori di predizione tramite valori di soglia (vedi paragrafo 4.2.4.2). Per i dati completi, fare riferimento a [8].

Come nel test precedente, il trend del rapporto di compressione medio tra le immagini compresse segue l’andamento del test precedente, con una rapida crescita per pochi pixel e un assestamento per numeri di pixel maggiori. Di nuovo, non ci sono miglioramenti significativi a partire dalla seconda configurazione di bande precedenti.Come per il test per la configurazione con preprocessing, vengono mostrati i tempi di esecuzione medi.

51

Come prevedibile, la crescita dei tempi di esecuzione non segue nella stessa misura la crescita del CR, all’aumentare delle bande precedenti utilizzate per la predizione.A questo punto, viste le caratteristiche comuni ad entrambe le soluzioni, viene mostrato un confronto diretto rispetto a CR e tempi di esecuzione, relativamente alle stesse configurazioni e stesso dataset.

52

5.5.3 Confronto tra Preprocessing e ThresholdNel grafico riportato di seguito, sono messe direttamente a confronto entrambe le soluzioni, per quanto riguarda la prestazione di compressione. Valori maggiori corrispondono a prestazioni migliori.

In verde sono riportate le prestazioni dell’algoritmo con preprocessing delle immagini per l’individuazione dei valori massimo e minimo. In blu, le prestazioni dell’algoritmo che utilizza i valori di soglia specificati prima dell’esecuzione. In tutte le configurazioni, si può notare una prestazione lievemente migliore (dell’ordine di 10-2 punti) impiegando il preprocessing. Questo è dovuto all’individuazione esatta degli errori di predizione causati da matrici malcondizionate. L’uso di una soglia prefissata invece, non consente di individuare tutte le predizioni che sono fuori dal range dei pixel reali, portando alla codifica di un errore di maggiore entità e alla conseguente diminuzione del rapporto di compressione.

53

Di seguito è riportato il grafico dei tempi di esecuzione per le stesse configurazioni. Valori minori corrispondono a prestazioni migliori.

L’utilizzo del preprocessing implica un aumento significativo dei tempi di esecuzione, nell’ordine dei 10 secondi tra le due modalità. Risulta evidente come la discrepanza minima tra i rapporti di compressione non giustifica il significativo peggioramento dei tempi di esecuzione causato dalla scansione completa delle immagini prima della compressione. Tale peggioramento è accentuato nelle configurazioni più complesse, con più bande precedenti e più pixel. Si è in grado di affermare pertanto, che l’utilizzo di una soglia prefissata, determinata empiricamente, pur non consentendo di evitare completamente le predizioni SLSQ fuori dal range dei valori reali, consente comunque di ovviare al problema senza incorrere nel ritardo introdotto dal preprocessing.

54

5.5.4 PAQ8pCome da descrizione del test, nel paragrafo 5.4, si è provato ad utilizzare la tecnica di codifica entropica PAQ8p per codificare gli errori di predizione. L’intenzione è quella di migliorare il rapporto di compressione con una tecnica di codifica più complessa, in considerazione della perdita di complessità lineare introducendo bande precedenti ulteriori alla prima per l’algoritmo SLSQ.Eseguendo i primi test sul dataset, ed analizzando i primi risultati, si è subito osservato un sostanziale miglioramento del rapporto di compressione, quantificato in 0.3 punti rispetto alla codifica aritmetica. Il vantaggio di compressione si paga però con un tempo di esecuzione molto superiore ai test effettuati con codifica degli errori aritmetica. In particolare, per la sola fase di codifica degli errori di predizione, si passa da tempi di circa 3-4 minuti per AC (Arithmetic Coding) a 60 minuti per PAQ8p. Si è deciso quindi di non proseguire con il test completo e di considerare PAQ8p come una tecnica di codifica troppo complessa e non applicabile nell’ambito dell’algoritmo di compressione SLSQ, concentrando le risorse sul testing di altre tecniche di parametrizzazione, trattate nel capitolo successivo.

55

6. Uso di informazioni storiche6.1 Perché utilizzare informazioni storicheLe informazioni ottenute dalle predizioni di pixel, precedenti al pixel del quale stiamo effettuando la predizione, rappresentano una fonte preziosa per il miglioramento della predizione dei pixel mancanti. Nel caso in cui l’errore, nei pixel precedenti, si è attestato intorno ad una soglia α, la nostra assunzione è quella che, successivamente, gli errori di predizione devono anch’essi essere nel medesimo intorno α.Utilizzando questa assunzione, il vantaggio che si spera ottenere è una predizione più accurata di un pixel della banda in esame, che comporta un miglioramento del compression ratio (CR).

56

6.2 Definizione dell’euristica per l’utilizzo di informazioni storicheL’euristica è definita in maniera da considerare N errori di predizione precedenti al pixel con il quale si sta lavorando all’iterazione corrente. Ad ognuno di questi N errori, l’euristica assegna un peso w, in modo da definire l’importanza di ciascun pezzo di storia considerata.Nel dettaglio, segue lo pseudocodice dell’euristica considerata:

previousErrorN //Errore all'iterazione i ­ N

...

previousError2 //Errore all'iterazione i ­ 2

previousError1 //Errore all'iterazione i ­ 1

predictedPixel //Pixel predetto utilizzando SLSQ con threshold

adjustedPredictedPixel = predictedPixel + (w[0] * previousError1 +

... + w[N ­ 1] * previousErrorE)

dove w[0] + ... + w[N ­ 1] = 1.0.

57

6.3 Parametrizzare la scelta del numero di errori da considerare e del peso da assegnare a ciascuno di essiAffinché sia possibile testare questa variante dell’algoritmo di SLSQ, è necessario, ancora una volta, apportare delle modifiche nell’implementazione in modo tale da consentire all’utente di poter avvalersi dell’opportunità di utilizzare l’euristica delle informazioni storiche e, in tal caso, selezionare il numero di errori che intende considerare come storia precedente del pixel in esame e il peso da assegnare a ciascuno di questi errori.Alle classi individuate nell’impact set e definite nel paragrafo 4.2.2 sono stati introdotti due parametri:

un valore intero che corrisponde al numero di errori da considerare come storia; un vettore pesi, per memorizzare le informazioni riguardanti i pesi da assegnare a

ciascun errore.

Ad ogni nuova predizione effettuata dall’algoritmo, il vettore che rappresenta gli N errori fin qui accumulati, viene aggiornato per far shiftare di un errore la storia del pixel che si sta predicendo. In questo modo, ci si assicura di considerare, di volta in volta, gli N errori di predizione del pixel in esame.All’interno dell’interfaccia, invece, è stato inserito un tasto che consente di attivare l’euristica e, contemporaneamente, provoca l’apertura di un nuovo frame in cui è presente una tabella nella quale l’utente può inserire il numero di errori da considerare e il peso associato a ciascun errore. Tali modifiche sono riportate di seguito:

58

59

6.4 Descrizione del test setIl confronto tra i due algoritmi è stato eseguito su due diversi test set, il primo dei quali descritto nel paragrafo 5.2, il secondo descritto nella tabella seguente.

Id Configurazione Descrizione Linee Campioni BandeDS02_IMG1_sc01 Yellowstone 512 677 224DS02_IMG1_sc02 Yellowstone 512 677 224DS02_IMG1_sc03 Yellowstone 512 677 224DS02_IMG1_sc04 Yellowstone 512 677 224DS02_IMG1_sc05 Yellowstone 512 677 224DS02_IMG1_sc06 Yellowstone 512 680 224DS02_IMG1_sc07 Yellowstone 512 680 224DS02_IMG1_sc08 Yellowstone 512 680 224DS02_IMG1_sc09 Yellowstone 512 680 224DS02_IMG1_sc10 Yellowstone 512 680 224DS02_IMG2_sc1 Hawaii 512 614 224DS02_IMG3_sc1 Maine 512 680 224

60

6.5 Confronto con SLSQ parametrizzatoIl confronto tra l’algoritmo SLSQ parametrizzato con l’opzione di utilizzo di una threshold per il problema del mal condizionamento delle matrici e la versione dell’algoritmo che utilizza l’euristica descritta nel paragrafo 6.2 è stato realizzato in due diversi modi. Il primo confronto è stato realizzato sul dataset descritto nel paragrafo 5.2, considerando le prime scene delle diverse immagini, mentre per un ulteriore approfondimento del test si è eseguita la compressione e decompressione anche delle immagini oggetto del dataset descritto nel paragrafo precedente.Per poter utilizzare le informazioni storiche è necessario definire una configurazione che indichi i) il numero di errori da considerare e ii) il peso da assegnare a ciascuno di questi. Sono state selezionate due configurazioni:

Id configurazione N w1 w2EAC_1 2 0.7 0.3EAC_2 2 0.6 0.4

In particolare, la storia è formata dall’ultimo errore, al quale è assegnato il peso maggiore, e il penultimo errore calcolato. Il grafico seguente mostra l’andamento delle due configurazioni in relazione all’algoritmo di SLSQ parametrizzato con l’opzione di utilizzo di una threshold per il problema del mal condizionamento delle matrici.

61

Come si evince dal grafico, l’algoritmo SLSQ che utilizza le informazioni storiche sugli errori precedentemente calcolati ha un compression ratio decisamente minore dell’algoritmo standard SLSQ. Un aspetto interessante è però legato alla variazione della configurazione dei pesi, che fornisce risultati sensibilmente diversi; in particolare, la configurazione EAC_2, che assegna pesi sostanzialmente bilanciati ai due errori considerati, ha un compression ratio maggiore.Il secondo confronto è stato effettuato sul dataset descritto nel paragrafo 6.4, utilizzando le stesse configurazioni EAC_1 ed EAC_2 per l’algoritmo SLSQ con l’utilizzo di informazioni storiche. Il grafico seguente mostra i risultati del confronto.

62

Dal grafico si nota come il test sul dataset più estensivo conferma quanto osservato nel test precedente. Entrambe le configurazioni con correzione della predizione sulla base degli errori precedenti hanno performance di compressione decisamente inferiori rispetto a SLSQ senza correzione. Allo stesso modo, la configurazione con i pesi più bilanciati, è leggermente migliore.Contrariamente a quanto ci si aspettava, l’errore di predizione non è influenzato o strettamente correlato con gli errori dei pixel immediatamente precedenti.

63

7. Conclusioni e sviluppi futuriLe immagini Iperspettrali sono una raccolta ed elaborazione di tutte le informazioni provenienti dallo spettro elettromagnetico dell'oggetto osservato. Il problema consiste nell'acquisizione delle immagini, dato che producono una mole di dati piuttosto ampia.Dato il rapido sviluppo di applicativi per il supporto all’analisi e la crescente domanda per una risoluzione più elevata, sia spaziale che spettrale, e la scarsa capacità dei canali di trasmissione, non ci resta che comprimere in maniera efficiente i dati acquisiti dai sensori.L'algoritmo SLSQ ha un basso costo computazionale ed è considerato ancora lo stato d'arte degli algoritmi di compressione lossless per le immagini iperspettrali.Il lavoro di questo progetto è consistito nel: parametrizzare il numero di pixel vicini e numero di bande precedenti utilizzati

dall’algoritmo SLSQ nella compressione delle immagini; testare l’utilizzo di informazioni storiche, ovvero informazioni relative agli errori delle

predizioni precedenti, nell’algoritmo, in modo da tentare di avere predizioni più accurate.L'obiettivo è, ovviamente, riuscire a predire nel modo più accurato i pixel, con una conseguente riduzione dell'errore di predizione. Questo comporterebbe un miglioramento del compression ratio (CR), ovvero una riduzione della dimensione della rappresentazione dell’immagine iperspettrale.Il primo lavoro è consistito nel parametrizzare il tool, assicurandosi che i risultati ottenuti dopo la modifica fossero quanto più vicini possibile a quelli forniti dalla versione precedente del tool con i parametri di default, ovvero prendendo in considerazione quattro pixel ed una banda.Per valutare lo sforzo richiesto per la modifica è stata effettuata un impact analysis sul codice sorgente. Sono state poi modificate le componenti responsabili della fase di compressione e

64

decompressione delle immagini e successivamente l'interfaccia grafica.La soluzione prodotta è stata quindi testata per valutarne l'efficienza e l'efficacia e correggerne eventuali difetti. La fase di testing ha rilevato che l'algoritmo, durante il processo di risoluzione dei sistemi lineari, può essere influenzato dalla natura delle matrici utilizzate.I test hanno confermato che è molto probabile che vengano trattate matrici mal condizionate per la predizione di alcuni pixel. Si rende necessaria, dunque, una gestione degli errori derivanti da questo problema. Sono state ideate due soluzioni. preprocessing dell'immagine, atta ad individuare il range dei valori dei pixel; threshold definita dall'utente.

In entrambi i casi se si suppone ci sia stato un errore di predizione dovuto a mal condizionamento, si procede ad una nuova predizione utilizzando un predittore mediano, non affetto dal problema sopracitato.L'interfaccia grafica è stata quindi adattata inserendo i nuovi parametri che permettono di risolvere il problema del mal condizionamento delle matrici.Il confronto tra la versione iniziale del tool e quella parametrizzata utilizzando quattro pixel vicini e una banda ha riportato un risultato migliore per la versione iniziale. Questo è dovuto sostanzialmente al fatto che la versione iniziale è ottimizzata per quella particolare configurazione del problema ed utilizza una diversa struttura dati. Per questo motivo si è trattata in maniera diversa questa configurazione preferendo l'approccio precedente.E' stata quindi condotta una sperimentazione per verificare e confrontare le performance della soluzione basata su preprocessing e di quella basata su threshold. Il dataset per il testing è costituito da un insieme di immagini iperspettrali fornite dalla NASA.Tutti i test sono stati effettuati nello stesso ambiente per due motivi principali: rendere obiettivo il confronto tra le due varianti dell’algoritmo;

65

abbassare l’impatto dei tempi necessari per l’esecuzione dei test.I test effettuati sulla soluzione basata su threshold sentenziano che: scegliere la configurazione di pixel vicini più complessa ma con CR migliore (16 pixel)

porta a prestazioni migliori e non comporta drastici peggioramenti del tempo di esecuzione;

l'aumento del numero di bande precedenti porta ad un miglioramento solamente marginale a partire dalla configurazione a 2 bande, a fronte di un notevole peggioramento del tempo di esecuzione.

Confrontando le due metodologie di trattamento delle matrici malcondizionate, applicando il preprocessing si può notare un miglioramento del rapporto di compressione solamente marginale a fronte di un aumento dei tempi di esecuzione. Di conseguenza si preferisce utilizzare valori di soglia prefissati, decisi dall’utente e determinati empiricamente.Si è provato a cercare un miglioramento nel rapporto di compressione approfittando della perdita di complessità lineare, causata dall’utilizzo di più bande precedenti, codificando gli errori di predizione con la complessa tecnica di codifica PAQ8p. Questa permette di migliorare significativamente il compression ratio, ma al prezzo di un aumento dei tempi di esecuzione che rende PAQ8p non adatta al contesto di questa sperimentazione.Si è iniziato quindi uno studio volendo verificare se l'utilizzo di informazioni storiche possa portare dei vantaggi in termini di aumento del compression ratio. Si presume, infatti, che le informazioni ottenute dalle predizioni di pixel precedenti al pixel del quale stiamo effettuando la predizione, rappresentano una fonte preziosa per il miglioramento della predizione.Affinché sia possibile testare questa variante dell’algoritmo di SLSQ, è necessario apportare delle modifiche nell’implementazione al fine di poter selezionare il numero di errori che si intendono considerare come storia precedente del pixel in esame e il peso da assegnare a

66

ciascuno di questi errori.Sono stati introdotti due nuovi parametri: un valore intero che corrisponde al numero di errori da considerare come storia; un vettore pesi, per memorizzare le informazioni riguardanti i pesi da assegnare a

ciascun errore.E' stata conseguentemente adattata l'interfaccia grafica ed effettuato un test, utilizzando lo stesso ambiente precedente, su due diversi dataset forniti dalla NASA. Il fine del nuovo test è stato quello di verificare e confrontare le prestazioni dell'algoritmo basato sulle informazioni storiche rispetto a quello standard con threshold.I risultati sentenziano che l’algoritmo SLSQ che utilizza le informazioni storiche ha un compression ratio decisamente minore dell’algoritmo standard SLSQ. Un aspetto interessante è però legato alla variazione della configurazione dei pesi, che fornisce risultati sensibilmente diversi. Di fatti, la configurazione che assegna peso 0.6 al primo errore e peso 0.4 al secondo consente sempre di ottenere un compression ratio leggermente superiore alla configurazione che assegna peso 0.7 al primo errore e peso 0.3 al secondo.L’ultima fase di questo lavoro è consistita nell’esecuzione dell’algoritmo SLSQ con utilizzo di threshold per la risoluzione del problema di mal condizionamento delle matrici e dell’algoritmo SLSQ con utilizzo di informazioni storiche su un secondo dataset formato da 3 immagini con 12 scene. I risultati confermano le prime analisi: l’algoritmo che utilizza le informazioni storiche non migliora in alcun modo il compression ratio, il quale rimane ampiamente superiore con l’utilizzo dell’algoritmo SLSQ con utilizzo di threshold per la risoluzione del problema di mal condizionamento delle matrici.Gli sviluppi futuri potrebbero essere finalizzati all’aumento del numero di pixel vicini considerati nelle configurazioni. Si è infatti dimostrato che scegliere una configurazione di pixel più

67

complessa non comporta drastici peggioramenti dei tempi di esecuzione. Si potrebbe quindi aumentare questa quantità fin quando: il compression ratio non decresce all’aumentare dei pixel; il tempo di esecuzione non aumenta drasticamente al crescere del numero dei pixel.

Per quanto concerne invece l’algoritmo che utilizza le informazioni storiche, si potrebbe testare il comportamento della configurazione che utilizza un solo errore precedente e che, quindi, assegna peso pari ad 1 a questo errore.

68

8. Riferimenti[1] IEEE SIGNAL PROCESSING LETTERS, VOL. 12, NO. 2, FEBRUARY 2005 “Low- Complexity Lossless Compression of Hyperspectral Imagery via Linear Prediction”, Francesco Rizzo, Member, IEEE, Bruno Carpentieri, Giovanni Motta, Student member, IEEE, and James A. Storer, Senior Member, IEEE.[2] “High Performance Compression of Hyperspectral Imagery with Reduced Search Complexity in the Compressed Domain”, Francesco Rizzo, Bruno Carpentieri - Dipartimento di Informatica e Applicazioni "R. M. Capocelli", Università degli Studi di Salerno (SA) 84081 Italy - Giovanni Motta, James A. Storer , Computer Science Department, Brandeis University, Waltham, MA 02454 USA.[3] "Hyperspectral data compression" G Motta, F Rizzo, JA Storer, JA Storer - 2006 - books.google.com.[4] “The Data Compression Book” – Marc Nelson, Jean Loup Gailly – M&T Books – Second Edition.[5] "Predictive Coding of Hyperspectral Images" Agnieszka C. Miguel, Richard, E. Ladnerz, Eve A. Riskiny, Scott Haucky, Dane K. Barneyz, Amanda R. Askewz, Alexander Changz.[6] “Handbook of Data Compression” , Springer London , David Salomon and Giovanni Motta – 2009.[7] Efficient Java Matrix Library: Official site:http://code.google.com/p/efficient-java-matrix-library/[8] Uno studio empirico sulla parametrizzazione dell’algoritmo SLSQ per la compressione diimmagini iperspettrali, Google Drive Folder:https://drive.google.com/folderview?id=0B1zAlxyNAIgxMGlfZkNYcTR5dTQ&usp=sharing

69

[9] Eclipse Juno Official Site: http://www.eclipse.org/juno/[10] NetBeans Official Site: https://netbeans.org[11] OpenJDK Official Site: http://openjdk.java.net

70

A. APPENDICE - Sintesi risultati dei testIn questa sezione sono riportati i risultati dei test in maniera sintetica. Per le descrizioni e le analisi dei test si rimanda al capitolo 5, mentre per i risultati completi fare riferimento a [8].

Per ogni test, vengono mostrati i valori medi tra tutte le immagini di compression ratio, BPP e tempo di esecuzione. L’id della configurazione indica il numero di pixel ed il numero di bande.Di seguito l’elenco dei contenuti di questa sezione:

Preprocessing - Dataset 1 prime scene Threshold - Dataset 1 prime scene Errors Adjustment - Dataset 1 prime scene Threshold - Dataset 1 completo Threshold - Dataset 2 completo Errors Adjustment - Dataset 2 completo

71

A.1 Preprocessing - Dataset 1 - Prime sceneConfigurazione CR BPP Tempo (ms)

P4_B1 3.10 5.17 205682P8_B1 3.13 5.12 222007

P12_B1 3.13 5.11 238246P16_B1 3.13 5.11 255326P4_B2 2.98 5.37 227568P8_B2 3.15 5.08 251636

P12_B2 3.19 5.01 277001P16_B2 3.21 4.99 305889P4_B3 2.71 5.90 251896P8_B3 3.10 5.17 286691

P12_B3 3.18 5.04 324337P16_B3 3.21 4.99 362678P4_B4 2.23 7.18 286673P8_B4 3.01 5.32 325421

P12_B4 3.14 5.10 376566P16_B4 3.19 5.02 430719

72

A.2 Threshold - Dataset 1 - Prime sceneConfigurazione CR BPP Tempo (ms)

P4_B1 3.09 5.18 2047256P8_B1 3.12 5.13 2144692

P12_B1 3.13 5.12 227398P16_B1 3.13 5.12 2423612P4_B2 2.98 5.37 2200756P8_B2 3.15 5.09 2425812

P12_B2 3.19 5.02 2652988P16_B2 3.20 4.99 2867478P4_B3 2.71 5.92 2413558P8_B3 3.09 5.18 271461

P12_B3 3.17 5.05 3041714P16_B3 3.20 4.99 335658P4_B4 2.22 7.21 2735406P8_B4 3.00 5.33 3033284

P12_B4 3.14 5.11 3450354P16_B4 3.19 5.03 3888324

73

A.3 Errors Adjustment - Dataset 1 - Prime sceneConfigurazione CR - variante 1 CR - variante 2

P4_B1 2,79 2.83P8_B1 2,83 2.87

P12_B1 2,84 2.88P16_B1 2,84 2.88P4_B2 2,76 2.76P8_B2 2,91 2.92

P12_B2 2,94 2.95P16_B2 2,96 2.96P4_B3 2,50 2.50P8_B3 2,88 2.90

P12_B3 2,95 2.97P16_B3 2,98 2.99P4_B4 1,96 1.96P8_B4 2,81 2.82

P12_B4 2,92 2.94P16_B4 2,97 2.99

74

A.4 Thresold - Dataset 1 - Tutte le sceneConfigurazione CR BPP Tempo (ms)

P4_B1 3.08 5.20 15572948P8_B1 3.11 5.16 3404793

P12_B1 3.11 5.15 4058792P16_B1 3.11 5.15 15610325P4_B2 2.97 5.40 9826368P8_B2 3.13 5.11 5358504

P12_B2 3.17 5.05 9224419P16_B2 3.19 5.03 4115861P4_B3 2.69 5.94 229236P8_B3 3.08 5.20 9228020

P12_B3 3.16 5.08 16308702P16_B3 3.19 5.03 12490360P4_B4 2.21 7.24 9873587P8_B4 2.99 5.36 10539384

P12_B4 3.12 5.13 4165451P16_B4 3.17 5.05 13177961

75

A.5 Threshold - Dataset 2 - Tutte le sceneConfigurazione CR BPP Tempo (ms)

P4_B1 3.50 5.02 22244225P8_B1 3.52 4.99 579285433

P12_B1 3.51 5.02 997389013P16_B1 3.49 5.03 998981713P4_B2 3.43 5.04 24322305P8_B2 3.66 4.77 582335033

P12_B2 3.70 4.73 168190053P16_B2 3.72 4.71 1003966113P4_B3 3.08 5.52 26582025P8_B3 3.61 4.80 724234027

P12_B3 3.72 4.69 589025433P16_B3 3.76 4.64 1009016013P4_B4 2.47 6.75 1418846453P8_B4 3.51 4.91 33131305

P12_B4 3.69 4.71 593373733P16_B4 3.77 4.63 320438247

76

A.6 Errors Adjustment - Dataset 2 - Tutte le sceneConfigurazione CR - variante 1 CR - variante 2

P4_B1 3.15 3.19P8_B1 3.18 3.21

P12_B1 3.19 3.22P16_B1 3.19 3.22P4_B2 3.06 3.06P8_B2 3.27 3.29

P12_B2 3.31 3.32P16_B2 3.32 3.34P4_B3 2.73 2.73P8_B3 3.26 3.27

P12_B3 3.34 3.36P16_B3 3.38 3.39P4_B4 2.10 2.09P8_B4 3.18 3.19

P12_B4 3.33 3.35P16_B4 3.39 3.41

77