Avventure nella programmazione e sviluppo GPS: un tutorial geospaziale

Tutto è iniziato durante un'escursione a Zbevnica più di 10 anni fa. Avevo con me il mio nuovo GPS e un mio amico aveva un GPS collegato a un telefono Windows ME. L'escursione è stata fantastica, ma quando siamo tornati alle nostre auto, siamo rimasti sorpresi di vedere che un GPS affermava che avevamo camminato per 6,2 km, mentre l'altro riportava 6,7 ​​km. Uno ha affermato che il nostro dislivello (cioè la somma di tutte le parti in salita della nostra escursione) era stato di 300 m, mentre l'altro lo ha riportato di 500 m.

Essendo un programmatore (ed eventualmente un programmatore GIS), sono stato subito incuriosito dal problema. Mi sono detto: " non dovrebbe essere così difficile da risolvere con una semplice sceneggiatura". Dopotutto, le tracce GPS sono solo un elenco di tuple sotto forma di (latitudine, longitudine, altitudine) , giusto?

Beh, non proprio.

Inizia così la mia escursione nell'affascinante mondo delle tracce GPS, degli errori di tracciamento e, più in generale, della programmazione GIS.

I sistemi di informazione geospaziale (GIS) sono un dominio vasto e complesso, che comprende proiezioni cartografiche e dati geodetici)), elaborazione di dati raste e vecto e telerilevamento. Un'introduzione completa a questo dominio andrebbe ben oltre lo scopo di questo articolo. E poiché concentrarsi su un problema specifico può spesso essere un modo utile per presentarsi comunque a un nuovo dominio, presenterò alcune sfide GIS specifiche che ho incontrato e alcune possibili soluzioni; vale a dire:

• Come riconoscere, comprendere e correggere programmaticamente gli errori di localizzazione GPS
• Come calcolare e ricavare ulteriori informazioni utili dalle tracce GPS

Per cominciare, le tracce GPS non sono solo una serie di tuple (latitudine, longitudine, altitudine) . Molti dispositivi abilitati al GPS forniranno anche metadati come ora, frequenza cardiaca e così via. Alcuni dispositivi GPS forniranno anche informazioni sull'accuratezza dei dati; alias, "diluizione della precisione". Ma, sfortunatamente, la maggior parte dei dispositivi GPS, in particolare quelli di fascia bassa che dominano il mercato, non forniscono queste informazioni e ci resta la sfida di dedurre l'accuratezza del dispositivo da soli (e idealmente correggere di conseguenza, ove possibile ).

Iniziamo con un possibile algoritmo per rilevare i dispositivi GPS di fascia bassa (come la maggior parte degli smartphone) che di solito hanno dati GPS di bassa qualità.

Errori di elevazione e idiosincrasie

Se vivi in ​​alcune parti del mondo, potresti aver notato qualcosa di strano sulla precisione dell'elevazione GPS quando registri le tracce con il tuo smartphone. Quando si controllano le quote altimetriche, vengono costantemente registrati come superiori o inferiori (di un valore costante) rispetto all'elevazione corretta. Ad esempio, vivo a Visignano (Croazia) e il mio Android continua a dirmi che sono circa 35-40 metri sopra l'altitudine effettiva.

Ad esempio, ecco un grafico dell'elevazione GPS di una breve escursione che ho fatto alcuni mesi fa:

Due cose da notare qui.

Innanzitutto, la "collina" nella prima parte dei dati GPS registrati è stata completamente fabbricata dal dispositivo . Mentre il grafico sembrerebbe indicare che il punto più alto della nostra escursione fosse a poche centinaia di metri dall'inizio, in realtà era circa 4 km dopo.

In secondo luogo, ciò che forse è più importante (e non visibile sul grafico) è che l'intero grafico è impreciso . I valori di altitudine sono stati costantemente riportati come circa 30-40 metri più alti di quanto non fossero in realtà, come discuteremo più dettagliatamente più avanti in questo articolo.

Questo è il tipo di cose che possono accadere con dispositivi GPS economici. E quando possiamo rilevare che la pista ha questi errori, possiamo dedurre che il dispositivo è probabilmente un GPS di bassa qualità che quindi ci si può aspettare anche altri errori – non solo errori di elevazione – che sono comuni a tali dispositivi.

Errori di elevazione all'avvio

Esistono essenzialmente due tecniche utilizzate dai dispositivi GPS per determinare l'altitudine: "altitudine GPS" (riportata al dispositivo dal sistema satellitare GPS) e "altitudine barometrica" ​​(calcolata dal dispositivo sulla base delle letture della pressione barometrica). Nessuno dei due è perfetto.

I valori di altitudine GPS possono presentare molti piccoli errori (tipicamente nell'intervallo di +/- 10 m), che possono essere particolarmente problematici se in seguito si decide di calcolare il dislivello cumulativo. L'altitudine barometrica, invece, è sensibile non solo all'altitudine ma anche alle condizioni meteorologiche, che possono introdurre una propria serie di imprecisioni.

Alcuni dispositivi utilizzano quindi un approccio ibrido, utilizzando letture barometriche per registrare l'altitudine ma utilizzando letture GPS per aiutare a (ri)calibrare quei valori, per aiutare a tenere conto dei cambiamenti meteorologici (pressione) e così via. Con tali dispositivi, all'avvio del tracciato, l'elevazione barometrica può essere completamente errata, ma poi ricalibrandola con sempre più dati satellitari GPS, i dati di elevazione diventano più affidabili. Pertanto, non è raro che tali dispositivi incontrino il tipo di errore di avvio "finta collina" che abbiamo osservato in precedenza sul nostro grafico di elevazione.

Inesattezze dell'elevazione GPS in corso

Per spiegare l'errore consistente nella segnalazione dell'altitudine, dobbiamo tornare alla geografia della nostra scuola elementare. Gli insegnanti di geografia di solito spiegano che la Terra non è una sfera ma un ellissoide. Se questo fosse, infatti, rigorosamente vero, l'altitudine sarebbe facile da calcolare matematicamente. Ma non lo è. La Terra è irregolare; in realtà, è più simile a una patata che assomiglia a un ellissoide che a un ellissoide perfetto, il che significa che per lo sviluppo del GIS è necessario un set di dati di altitudine dettagliato per quasi ogni punto della terra. Nella geodesia, questo ellissoide di riferimento (aka datum) è una superficie definita matematicamente che si avvicina al geoide, la figura "più vera" della Terra.

Inoltre, è importante riconoscere che anche questi dati sono solo approssimazioni della forma effettiva della superficie terrestre. Alcuni funzionano meglio in alcune parti del mondo e altri funzionano meglio in altre. Ad esempio, l'immagine qui sotto (generata usando la mia libreria Ruby) mostra come la Terra differisca da uno dei modelli ellissoidi più comunemente usati (il dato WGS84). Le porzioni nere rappresentano parti della Terra in alto e il bianco rappresenta parti della Terra in basso, l'ellissoide ideale (contorni del continente e dell'isola mostrati in rosso).

Puoi vedere che l'India è al di sotto dell'ellissoide WGS84 con la parte meridionale che è il minimo assoluto (quasi -100 metri!) E l'Europa è al di sopra.

Poiché i dispositivi GPS di bassa qualità non utilizzano tali dati, in realtà stanno solo calcolando l'elevazione assumendo un ellissoide perfetto. Da qui la loro costante imprecisione.

Rilevamento e correzione degli errori di elevazione GPS

Nello sviluppo di app GPS, è possibile rilevare che un dispositivo che ha registrato la nostra traccia presenta questi tipi di errori utilizzando il set di dati EGM2008 del modello gravitazionale terrestre, a volte indicato anche come set di dati "ondulazioni geoidi". Con EGM2008, possiamo approssimare la differenza tra la superficie terrestre effettiva e l'ellissoide ideale.

Ma per sapere se la nostra traccia GPS ha questo errore abbiamo bisogno di un'altra cosa: l'altitudine reale . Un database pubblico che può essere utile a questo scopo è lo Shuttle Radar Topography Mission (SRTM). SRTM è un database basato su raster che fornisce valori di elevazione con una risoluzione di circa ogni 30 m (all'equatore) per gli Stati Uniti e ogni 90 m per il resto del mondo. Ad esempio, quando si calcolano i valori SRTM per i punti nella traccia sopra, emerge un grafico diverso (la linea blu):

Un piccolo fastidio qui sono i bordi irregolari del grafico, ma questo è facilmente smussato. Si noti che lisciando perdiamo poca (se presente) precisione, poiché SRTM stesso fornisce solo punti discreti in posizioni equidistanti, tra i quali dobbiamo comunque interpolare. Ecco una versione del grafico precedente con una linea rossa sovrapposta che rappresenta i dati SRTM levigati:

Tutto questo può essere fatto facilmente, per inciso, usando le mie librerie Python GPS:

• srtm.py: un parser python per i dati di elevazione Shuttle Radar Topography Mission (SRTM).
• gpxpy: una semplice libreria Python per l'analisi e la manipolazione di file GPX (GPX, il GPS Exchange Format, è un formato di dati XML leggero per i dati GPS)

Per gli utenti di Ruby, c'è anche la mia libreria di parser Geoelevations.rb per le ondulazioni SRTM ed EGM2008.

Dopo aver rilevato queste anomalie, a seconda del tipo di software con cui stiamo lavorando, possiamo (a) correggere noi stessi gli errori o (b) semplicemente informare l'utente che sono state rilevate imprecisioni nei loro dati di elevazione.

Inoltre, poiché ci sono diversi algoritmi che possono essere utilizzati per correggere a livello di codice questi errori di elevazione GPS, potremmo voler dare all'utente la possibilità di selezionare quale algoritmo utilizzare (ad esempio, l'utente vuole che usiamo solo i dati SRTM levigati "così com'è" o l'utente desidera che utilizziamo i dati SRTM per correggere le elevazioni riportate dal dispositivo).

Levigatura della traccia e rimozione dei valori anomali

Se un giocatore di football indossasse un dispositivo GPS e registrasse una partita, la traccia risultante sarebbe un disastro. Il campo di gioco sarebbe densamente riempito da una pista composta da molte curve strette, accelerazioni e decelerazioni.

Fortunatamente, la maggior parte dei casi in cui le persone utilizzano il GPS non avranno lo stesso schema: le linee di traccia GPS (e le accelerazioni) saranno relativamente fluide. In questi casi, si può presumere che i punti irregolari nella nostra traccia siano indotti da errori e tali valori anomali possono quindi essere ragionevolmente rimossi con una funzione di smoothing.

Come sviluppatore GIS, lo smoothing si ottiene più comunemente iterando attraverso i punti e modificando le coordinate in base ai valori delle coordinate vicine. Ad esempio, possiamo modificare ogni latitudine e longitudine con un algoritmo come il seguente:

 points[n].latitude = points[n-1].latitude * 0.3 + points[n].latitude * .4 + points[n+1].latitude * .3 points[n].longitude = points[n-1].longitude * 0.3 + points[n].longitude * .4 + points[n+1].longitude * .3

Maggiore è il coefficiente, maggiore è l'impatto del corrispondente punto vicino o della posizione modificata del punto corrente. I coefficienti che uso in questo esempio (0,3, 0,4, 0,3) sono in qualche modo arbitrari, ma nella maggior parte dei casi vorrai che la loro somma sia 1,0. (Un approccio più sofisticato, ad esempio, sarebbe quello di utilizzare la distanza tra i punti e quindi, più vicino è il punto, maggiore è il coefficiente corrispondente.)

Ecco un esempio di una traccia con molti errori casuali:

Nota come la pista non segua bene il percorso, abbia molte curve strette e frastagliate e talvolta vira completamente fuori dal percorso previsto.

Dopo alcune iterazioni di "smussamento", questa stessa traccia viene trasformata in:

Anche se è molto meglio, è ancora certamente imperfetto. Nota che ci sono ancora punti (particolarmente vicino al centro del percorso) in cui la pista devia ancora fuori strada.

Ci sono altre cose che puoi provare. In alcune regioni, e per determinate applicazioni GPS, puoi anche utilizzare i dati di OpenStreetMap (OSM) per cercare di indovinare il percorso giusto e quindi "agganciare" i punti a questa nuova linea. Anche se questo può essere spesso utile, può anche essere imperfetto, come nei casi in cui i dati OSM contengono due linee parallele (ad esempio un'autostrada e una strada vicina) o molti percorsi vicini.

In questi casi, una possibile soluzione sarebbe quella di cercare di rilevare il tipo di attività, utilizzando alcune delle tecniche discusse più avanti in questo articolo. Se possiamo dedurre, ad esempio, che il sentiero era un sentiero escursionistico e abbiamo un'opzione per agganciare un'autostrada o un sentiero vicino, possiamo tranquillamente presumere che l'escursione fosse lungo il sentiero e non l'autostrada.

Si noti inoltre che, sebbene questo esempio dimostri il livellamento delle coordinate di superficie (cioè longitudine/latitudine), lo smoothing può essere una tecnica altrettanto valida per eliminare le aberrazioni nell'elevazione o nei dati temporali, o anche nei dati di frequenza cardiaca e cadenza della bicicletta.

Esempi di ulteriori vantaggi e usi dello smoothing potrebbero includere:

• Calcolo del dislivello totale. Per calcolare il dislivello totale in una pista non è sufficiente sommare tutti i piccoli “salti” in salita perché spesso conterranno piccoli errori. Smussare l'elevazione prima di fare la somma può spesso aiutare ad alleviare questo problema.
• Rimozione dei valori anomali. Dopo la "levigatura", i punti troppo lontani dalla pista possono essere rilevati più facilmente. Questi possono quindi essere spesso considerati valori anomali e all'utente può essere richiesto di chiedere se devono essere rimossi.

C'è un tipo di problema in cui questo algoritmo non è all'altezza: in alcuni casi il GPS registrerà un percorso regolare, ma il percorso sarà "spostato" da una differenza costante in una certa direzione. In questi casi, lo smussamento può smussare ulteriormente la linea ma non corregge questo errore di spostamento.

Un ulteriore problema meno ovvio, ma significativo, con la semplicistica tecnica di smoothing che abbiamo descritto è che la trasformazione modifica tutti (o quasi tutti) i punti del percorso, anche quelli che potrebbero non essere in errore. Sebbene questo approccio più semplice tenda ad essere una soluzione ragionevole per l'utente GPS medio, algoritmi di smoothing più sofisticati sono certamente utilizzabili nella programmazione GIS. In alcuni casi, potrebbe anche essere meglio rimuovere semplicemente i valori anomali senza eseguire alcun livellamento a seconda dell'utente, del dispositivo e dell'applicazione.

Rilevamento della velocità massima

Rilevare la velocità massima di una pista è abbastanza semplice se disponiamo delle coordinate e dei timestamp di tutti i punti del percorso. Basta calcolare le velocità tra i punti e trovare il valore più alto. Sembra semplice.

Ma ricorda, abbiamo a che fare con dispositivi GPS di fascia bassa e non ci fidiamo completamente dei dati, il che può avere ramificazioni significative per il nostro calcolo. Se un dispositivo registra una posizione ogni 5 metri e ad un certo punto commette un errore spostando il punto in modo errato di 10 metri, quella parte della traccia potrebbe sembrare 3 volte più veloce di quanto non fosse!

Un approccio comune nel mondo dello sviluppo GIS consiste nell'estrarre tutte le velocità tra i punti, quindi rimuovere semplicemente il 5% superiore (ovvero utilizzare il 95° percentile) sperando che il 5% eliminato rappresenti la maggior parte degli errori. Ma questo è certamente non scientifico e non garantisce risultati corretti. Nella mia sperimentazione con questa tecnica, ho provato diversi valori per i percentili e ho scoperto che alcuni funzionavano bene per un dispositivo GPS, altri funzionavano bene per altri. Alcuni funzionano bene per l'escursionismo e altri per andare in bicicletta. Ma nella maggior parte dei casi, i risultati non mi sembravano giusti.

Dopo aver provato molti algoritmi, quello che ha funzionato per me è stato semplice: aggiungere un altro filtro per rimuovere gli estremi, non solo per velocità, ma anche per distanza, come segue:

1. Ordina i punti in base alla distanza tra i vicini e rimuovi il 5% superiore.
2. (Facoltativo:) Leviga la pista (orizzontale e/o verticale).
3. Ordina i punti in base alla velocità tra i vicini e rimuovi il 5% superiore.

Dalla mia esperienza, questo algoritmo produce risultati abbastanza credibili, anche per tracce di dispositivi GPS economici con errori casuali.

Dedurre il tipo di attività

In molti casi, la velocità media è sufficiente per determinare il tipo di attività. Se la velocità media è di 5 kmh, ad esempio, è probabilmente una pista da passeggio/escursionismo, mentre se la velocità media è di 30 kmh, è probabilmente una pista ciclabile e così via.

Ma se la velocità media è di 12 kmh, non puoi essere certo se l'utente stesse andando in mountain bike o correndo. In questi casi, la velocità massima a volte può aiutare a differenziare tra i due tipi di attività. Nello specifico, possiamo sfruttare il fatto che i corridori raramente raggiungono una velocità superiore al doppio della loro media, mentre i ciclisti lo fanno regolarmente (ad es. in discesa su un percorso non troppo impegnativo).

Di conseguenza, una pista con una velocità media di 12kmh e una velocità massima di 18kmh è stata probabilmente registrata durante la corsa, mentre una pista con una velocità media di 12kmh e una velocità massima di 30kmh è stata probabilmente registrata durante la mountain bike. (Naturalmente, dobbiamo essere sicuri che la nostra velocità massima calcolata sia corretta, affinché funzioni in modo affidabile.)

Percentuale del cielo visibile: un proxy intelligente per il rilevamento degli errori GPS

La precisione di ciascuna misurazione GPS (cioè latitudine, longitudine ed elevazione) dipende molto dal numero di satelliti che erano visibili al momento della registrazione. Quindi, se potessimo in qualche modo determinare quanti satelliti erano "in vista" al momento di ogni registrazione, potremmo usarlo come un modo per approssimare l'accuratezza di quella registrazione. Se in qualche modo sapessimo, ad esempio, che tutti i satelliti GPS necessari erano in vista, potremmo presumere un alto grado di precisione per i dati GPS corrispondenti. Al contrario, se in qualche modo sapessimo che nessun satellite GPS è in vista, potremmo presumere che i dati siano soggetti a errori.

Ma prima di eccitarti troppo, considera la complessità del tentativo di risolvere un simile problema GIS. Prima di tutto, dovresti sapere con quale/i sistema/i satellitare/i GPS il tuo dispositivo era in grado di comunicare. C'è l'originale Global Positioning System con sede negli Stati Uniti, il Gallileo europeo e il sistema GLONASS russo. Alcuni dispositivi funzionano con tutti questi tipi di satelliti, ma molti no. E molti dispositivi non segnalano nemmeno quali sistemi utilizzano.

Ma c'è un modo intelligente per aggirare questa complessità e ottenere un'approssimazione grossolana del numero di satelliti in vista: utilizzare la percentuale di cielo visibile come proxy per il numero di satelliti visibili . Cielo meno visibile significa che il nostro GPS può “vedere” (o essere visto) da un minor numero di satelliti. Ma come possiamo calcolare la percentuale del cielo visibile in un punto qualsiasi della Terra? La soluzione è in realtà abbastanza semplice: possiamo calcolare la linea dell'orizzonte intorno a noi utilizzando i dati SRTM discussi in precedenza.

Ad esempio, questo è l'orizzonte se ti trovi nella valle sotto il Triglav (la vetta più alta della Slovenia) calcolata utilizzando SRTM:

(Per chi fosse interessato, il mio codice per creare questa immagine può essere trovato qui.)

Questa immagine è fondamentalmente composta da strati di grafici di elevazione equidistanti visti da un punto centrale. Più scura è l'area blu, più distante è lo strato di elevazione; più chiara è l'area blu, più vicino è il livello di elevazione. I punti più alti disegnati rappresentano la linea dell'orizzonte. Se un satellite GPS si trova al di sotto di questa linea nel cielo, il nostro dispositivo probabilmente non può vederlo (o essere visto) da esso. (Nota, tuttavia, che sebbene l'immagine sia disegnata come un rettangolo appiattito, in realtà avresti bisogno di alcune conoscenze di base della geometria sferica per calcolare correttamente l'area sotto l'orizzonte.)

Un'altra cosa da tenere a mente è che questo non è un proiettile d'argento per rilevare gli errori di elevazione GPS. Innanzitutto, la maggior parte delle parti della Terra non sono montuose e, anche quando lo sono, è nella nostra psicologia sopravvalutare le elevazioni; la percentuale effettiva del cielo visibile è superiore al 75% nella stragrande maggioranza delle regioni abitate . Tuttavia, questo metodo può essere utile in determinate situazioni, come le escursioni in montagna, dove potresti passare dall'essere in un canyon profondo (con scarsa ricezione GPS) all'essere su un crinale di montagna (dove la ricezione satellitare è probabilmente molto migliore). Sebbene questo metodo non sia una misura assoluta di quanti errori ha la traccia, può essere un utile indicatore di quali parti della tua traccia potrebbero essere più soggette a errori di altre.

Incartare

Abbiamo discusso alcuni dei tipi più comuni di errori di tracciamento GPS che ci si aspetta con i dispositivi GPS di fascia bassa. Abbiamo fornito una comprensione di ciò che li causa e alcune tecniche di programmazione GIS per correggerli.

In alcuni casi possiamo correggere la pista con un alto grado di confidenza. In altri casi, possiamo almeno avvisare l'utente di porzioni della traccia che appaiono discutibili. Nei casi in cui non siamo sicuri, c'è sempre la possibilità di consentire all'utente di aggiustare la pista da solo, aiutato da immagini aeree e mappe. Le nostre ipotesi probabilistiche possono aiutare a evidenziare quelle parti della traccia in cui abbiamo rilevato una maggiore probabilità di errori.

In molti casi, le tecniche che abbiamo delineato possono essere una soddisfacente "soluzione all'80%", fornendo agli utenti di dispositivi GPS di fascia bassa un livello ragionevole di miglioramento automatico dell'accuratezza delle loro tracce GPS.