Progetto e sviluppo di un algoritmo di compressione per dati prodotti da tracker GPS

Introduzione Un nuovo approccio Test e validazione Conclusioni

Progetto e sviluppo di un algoritmo dicompressione lossy per dati prodotti da dispositivi

di posizionamento

Mariano Calandra

relatore

Chiar.mo Prof. Walter Balzano

Corso di Laurea in Informatica, Universita degli studi di Napoli Federico II

9 Maggio 2012

Mariano Calandra Progetto e sviluppo di un algoritmo di compressione lossy


Dispositivi di posizionamentoCosa sono e a cosa servono

Cos’e? – Un dispositivo di posizionamento e un piccolo rilevatorein grado di registrare istante per istante le proprie coordinate dilatitudine, longitudine e tempo grazie alla tecnologia GPS.

A cosa serve? – Le rilevazioni fornite sono memorizzate peranalisi future, o condivise in tempo reale.



Traiettorie e tracciati

L’insieme di tali rilevazioni e detto traiettoria e ci permette disapere dov’era l’oggetto rilevato in un determinato istantetemporale.

La proiezione atemporale di tali rilevazioni e detta tracciato.



Compressione di una traiettoriaPerche e come comprimere

Perche? – La memorizzazione, cosı come la condivisione, di unnumero elevato di traiettorie potrebbe essere computazionalmentemolto dispendiosa.

Come? – Eliminando dall’insieme di rilevazioni iniziali quelleridondanti o meno importanti.



Gli algoritmi di compressione

La scelta di quali punti eliminare dalla traiettoria e affidata ad unalgoritmo di compressione.

Esistono due tipi di algoritmi:

algoritmi lossless;

algoritmi lossy;



Gli algoritmi di compressione

Tra gli algoritmi lossy piu conosciuti troviamo:

l’algoritmo di Douglas-Peucker;

l’algoritmo di Bellman;



Gli algoritmi di compressioneL’algoritmo Douglas-Peucker

L’algoritmo Douglas-Peucker e un algoritmo di compressioneappartenente alla famiglia degli algoritmi di line-simplification.



Gli algoritmi di compressioneL’algoritmo Douglas-Peucker

PRO:

render grafico molto preciso

richieste computazionali non elevate

CONTRO:

scarsa approssimazione spazio-temporale



Gli algoritmi di compressioneL’algoritmo Bellman

L’algoritmo di Bellman considera le traiettorie come se fosserodelle funzioni matematiche univocamente definite.

PRO:

Algoritmo spazio-temporalmente ottimale

CONTRO:

Impossibile comprimere traiettorie con dei loop

Elevata complessita computazionale



Gli algoritmi di compressioneBellman e la problematica dei loop

Un loop si verifica, quando in due istanti di tempo diversi ildispositivo di rilevamento registra le stesse coordinate di latitudinee longitudine.



Un nuovo approccioObiettivi

Sviluppare un nuovo algoritmo che consideri le traiettorie al paridell’algoritmo Bellman e che inoltre:

sia insensibile ai loop;

abbia una buona qualita spazio-temporale;

abbia una complessita computazionale non troppo alta;



La problematica dei loopCome evitarli?

Esprimendo latitudini e longitudini come funzione del tempotrascorso. Avremo dunque:

componente latitudinale;

componente longitudinale;



Componenti spazio-temporali

Le componenti spazio-temporali saranno delle coppie di valori〈x , y〉.

x y

t1 lat1

t2 lat2

t3 lat3

t4 lat4

... ...

tn latn−1

tn latn

x y

t1 lon1

t2 lon2

t3 lon3

t4 lon4

... ...

tn lonn−1

tn lonn



Sintesi alle differenzeComprendere il variare delle componenti

x yt1 lat1

}D2 = 〈t2, lat1 − lat2〉

D3 = 〈t3, lat2 − lat3〉{

t2 lat2

t3 lat3

}D4 = 〈t4, lat3 − lat4〉t4 lat4

... ...

Dn = 〈tn, latn−1 − latn〉{

tn−1 latn−1

tn latn

D1 avra come coordinate 〈t1, 0〉.



Grafico sintesi alle differenzeCome sfruttarlo

La proiezione di una generica sintesi alle differenze (latitudinale olongitudinale) avra un aspetto simile:

Il nostro algoritmo di compressione dovra ricreare tale grafico, nelmodo piu accurato possibile, usando un numero di punti inferiore.



Polilinea approssimante

La compressione meno precisa che possiamo ottenere e quella incui uniamo il primo e l’ultimo vertice.

L’intero grafico di sintesi (blu) e rappresentato con un solosegmento (rosso). Rappresentare un grafico come quello di figuracon un segmento comporta un errore, tale errore e detto errore diapprossimazione.




Se l’errore di approssimazione e piu piccolo della tolleranza decisadall’utente allora l’algoritmo si conclude. Altrimenti...

...l’algoritmo spezza l’errore in due errori piu piccoli, includendo unterzo punto al centro del grafico di sintesi.




Adesso che l’errore di approssimazione e piu di uno, si cerca qual equello piu grande. Se questo viola la tolleranza, allora...

...l’algoritmo spezza l’errore in due errori piu piccoli, come giaspiegato in precedenza.



Polilinea approssimanteMinima polilinea approssimante

Una volta che tutti gli errori di approssimazione saranno piu piccolidella tolleranza l’algoritmo potra arrestare il processo diminimizzazione dell’errore.

La polilinea che otterremo prendera il nome di minima polilineaapprossimante.



Polilinea approssimantePseudo-codice

1: procedure simplify(coords = {Tlat ‖ Tlon}, τ) return Plm

2: D = derive(coords);3: s = 14: e = size(D)5: Plm ← s, e6: error ← MSE (D, s, e)7: while error1.mse > τ do8: s = error1.start9: e = error1.end

10: vnew = round((s + e)/2)11: Plm ← vnew12: error ← MSE (D, s, vnew )13: error ← MSE (D, vnew , e)14: error1 → ∅15: end while16: end procedure Mariano Calandra Progetto e sviluppo di un algoritmo di compressione lossy


Polilinea approssimanteDiagramma di flusso



Polilinea approssimanteMinima polilinea approssimante generale

Alla fine dell’algoritmo avremo calcolato due polilinee:

una polilinea longitudinale

una polilinea latitudinale

Le due polilinee verranno fuse insieme e l’algoritmo si conclude.



Test e validazioneLa distanza sincronizzata euclidea

La distanza sincronizzata euclidea (SED) e la distanza che sicrea, a parita di tempo, tra un punto sulla traiettoria compressa eil rispettivo punto sulla traiettoria originaria.

La media di tali distanze ci fornira l’errore di approssimazionemedio.



Misure SEDTabella riepilogativa

SED% compressione

MC DP

0.00016032 0.0001750267 10%

0.0004254233 0.0005225867 20%

0.0007182033 0.0010979333 30%

0.0011839333 0.0021174333 40%

0.0018201 0.0040697333 50%

0.0033408 0.0064422667 60%

0.0061559 0.0117570667 70%

0.0136053333 0.0241546667 80%

0.0547436667 0.0581126667 90%

0.0091281867 0.0120499311 SED Medio0.08215368 0.10844938 SED Totale



Misure SEDGrafico riepilogativo



Conclusioni

PRO:

una buona compressione spazio-temporale

insensibilita ai loop

capacita computazionale quadratica

CONTRO:

scarsa compressione spaziale;



Punti deboliConsiderazioni

Come mitigare questo problema?

Scegliere il nostro algoritmo solo se per compressionisemantiche;

Utilizzare il nostro algoritmo congiuntamente ad algoritmi diline-fitting;



Sviluppi futuri

Verificare il margine di vantaggio ottenibile parallelizzandol’algoritmo;

Sviluppo di un metodo standard per la valutazione delletraiettorie compresse;



Grazie per l’attenzione!


Progetto e sviluppo di un algoritmo di compressione per dati prodotti da tracker GPS

Science

Transcript of Progetto e sviluppo di un algoritmo di compressione per dati prodotti da tracker GPS