Aventuri în programarea și dezvoltarea GPS: un tutorial geospațial

Totul a început într-o excursie la Zbevnica cu mai bine de 10 ani în urmă. Aveam noul meu GPS la mine și un prieten de-al meu avea un GPS conectat la un telefon Windows ME. Drumul a fost grozav, dar când ne-am întors la mașini, am fost surprinși să vedem că un GPS a susținut că am mers 6,2 km, în timp ce celălalt a raportat 6,7 km. Unul a susținut că creșterea noastră de altitudine (adică, suma tuturor părților în sus ale drumeției noastre) a fost de 300 m, în timp ce celălalt a raportat că este de 500 m.

Fiind programator (și în cele din urmă programator GIS), am fost imediat intrigat de problemă. Mi-am spus: „Acest lucru nu ar trebui să fie atât de greu de rezolvat cu un simplu script”. La urma urmei, traseele GPS sunt doar o listă de tupluri sub formă de (latitudine, longitudine, altitudine) , nu?

Nu chiar.

Și așa am început excursia mea în lumea fascinantă a traseelor ​​GPS, a erorilor de urmărire și, mai general, a programării GIS.

Sistemele de informații geospatiale (GIS) este un domeniu imens și complex, care cuprinde proiecții hărți și date geodezice), procesarea datelor raste și vecto și teledetecție. O introducere cuprinzătoare în acest domeniu ar depăși cu mult scopul acestui articol. Și, din moment ce concentrarea pe o anumită problemă poate fi adesea o modalitate utilă de a te prezenta oricum într-un nou domeniu, voi prezenta câteva provocări GIS specifice pe care le-am întâlnit și câteva soluții posibile; și anume:

• Cum să recunoașteți, să înțelegeți și să corectați programatic erorile de urmărire GPS
• Cum să calculați și să obțineți informații suplimentare utile din traseele GPS

Pentru început, traseele GPS nu sunt doar o serie de tupluri (latitudine, longitudine, altitudine) . Multe dispozitive compatibile cu GPS vor furniza, de asemenea, metadate precum timpul, ritmul cardiac și așa mai departe. Unele dispozitive GPS vor oferi chiar informații despre cât de exacte sunt datele; alias „diluarea preciziei”. Dar, din păcate, majoritatea dispozitivelor GPS – în special cele de gamă inferioară care domină piața – nu vor furniza aceste informații și ne rămâne cu provocarea de a deduce singuri acuratețea dispozitivului (și, în mod ideal, corectăm în consecință, acolo unde este posibil. ).

Să începem cu un posibil algoritm de detectare a dispozitivelor GPS de gamă inferioară (precum majoritatea smartphone-urilor) care au de obicei date GPS de calitate scăzută.

Erori de cotă și idiosincrazii

Dacă locuiți în anumite părți ale lumii, este posibil să fi observat ceva ciudat despre precizia înălțimii GPS atunci când înregistrați traseele cu smartphone-ul. Când verificați cotele, acestea sunt înregistrate în mod constant ca fiind mai mari sau mai mici (cu o valoare constantă) decât cota corectă. De exemplu, locuiesc în Višnjan (Croația) și Android-ul meu îmi tot spune că mă aflu la aproximativ 35-40 de metri deasupra cotei reale.

De exemplu, iată un grafic al altitudinii GPS de la o scurtă excursie pe care am făcut-o acum câteva luni:

Două lucruri de remarcat aici.

În primul rând, „dealul” din prima parte a datelor GPS înregistrate a fost complet fabricat de dispozitiv . În timp ce graficul ar părea să indice că cel mai înalt punct din drumeția noastră a fost la doar câteva sute de metri de la început, în realitate a fost aproximativ 4 km mai târziu.

În al doilea rând, ceea ce este poate mai important (și nu este vizibil pe grafic) este faptul că întregul grafic este inexact . Valorile altitudinii au fost raportate în mod constant ca fiind cu aproximativ 30-40 de metri mai mari decât erau în realitate, așa cum vom discuta mai detaliat în acest articol.

Acestea sunt genul de lucruri care se pot întâmpla cu dispozitivele GPS ieftine. Și când putem detecta că pista are aceste erori, putem deduce că dispozitivul este probabil un GPS de calitate scăzută, care, prin urmare, poate fi de așteptat să aibă și alte erori – nu doar erori de altitudine – care sunt comune pentru astfel de dispozitive.

Erori de elevație la pornire

Există în esență două tehnici pe care dispozitivele GPS le folosesc pentru a determina altitudinea: „altitudinea GPS” (așa cum este raportată dispozitivului de sistemul prin satelit GPS) și „altitudinea barometrică” (calculată de dispozitiv pe baza citirilor presiunii barometrice). Nici unul nu este perfect.

Valorile de altitudine GPS pot avea multe erori mici (de obicei în intervalul +/- 10 m), care pot fi deosebit de problematice dacă decidem ulterior să calculăm câștigul cumulat al cotei. Altitudinea barometrică, pe de altă parte, este sensibilă nu numai la altitudine, ci și la condițiile meteorologice, care pot introduce propriul set de inexactități.

Prin urmare, unele dispozitive folosesc o abordare hibridă, folosind citiri barometrice pentru a înregistra altitudinea, dar folosind citiri GPS pentru a ajuta la (re)calibrarea acestor valori, pentru a ajuta la luarea în considerare a schimbărilor meteorologice (de presiune) și așa mai departe. Cu astfel de dispozitive, la pornirea traseului, cota barometrică poate fi complet greșită, dar apoi recalibrând-o cu tot mai multe date satelitare GPS, datele de cotă devin mai fiabile. Prin urmare, nu este neobișnuit cu astfel de dispozitive să întâlnească tipul de eroare de pornire „deal fals” pe care am observat-o mai devreme pe graficul nostru de altitudine.

Inexactități ale cotei GPS în curs

Pentru a explica eroarea constantă în raportarea altitudinii, trebuie să ne întoarcem la geografia din școala primară. Profesorii de geografie explică de obicei că Pământul nu este o sferă, ci un elipsoid. Dacă acest lucru ar fi, de fapt, strict adevărat, altitudinea ar fi ușor de calculat matematic. Dar nu este. Pământul este neregulat; în realitate, seamănă mai mult cu un cartof care seamănă cu un elipsoid decât cu un elipsoid perfect, ceea ce înseamnă că pentru dezvoltarea GIS aveți nevoie de un set de date de altitudine detaliat pentru aproape fiecare punct de pe pământ. În geodezie, acest elipsoid de referință (aka datum) este o suprafață definită matematic care aproximează geoidul, figura „mai adevărată” a Pământului.

Mai mult, este important să recunoaștem că chiar și aceste date sunt doar aproximări ale formei reale a suprafeței Pământului. Unii funcționează mai bine în anumite părți ale lumii, iar alții funcționează mai bine în altele. Ca exemplu, imaginea de mai jos (generată folosind biblioteca mea Ruby) arată cum diferă Pământul de unul dintre modelele elipsoide cele mai frecvent utilizate (datum WGS84). Porțiunile negre reprezintă părți ale Pământului de deasupra, iar albul reprezintă părți ale Pământului de dedesubt, elipsoidul ideal (contururile continentale și ale insulei prezentate în roșu).

Puteți vedea că India se află sub elipsoidul WGS84, partea de sud fiind minimul absolut (aproape -100 de metri!), iar Europa este deasupra acestuia.

Deoarece dispozitivele GPS de calitate scăzută nu folosesc astfel de date, ele doar calculează elevația presupunând un elipsoid perfect. Prin urmare, inexactitatea lor constantă.

Detectarea și corectarea erorilor de elevație GPS

În dezvoltarea aplicației GPS, detectarea faptului că un dispozitiv care ne-a înregistrat traseul are aceste tipuri de erori se poate face folosind setul de date Earth Gravitational Model EGM2008, denumit uneori și setul de date „undații geoide”. Cu EGM2008, putem aproxima diferența dintre suprafața reală a pământului și elipsoidul ideal.

Dar pentru a ști dacă traseul nostru GPS are această eroare, avem nevoie de încă un lucru - altitudinea reală . O bază de date publică care poate fi utilă în acest scop este Shuttle Radar Topography Mission (SRTM). SRTM este o bază de date raster care furnizează valori de altitudine la o rezoluție de aproximativ la fiecare 30 m (la ecuator) pentru SUA și la fiecare 90 m pentru restul lumii. De exemplu, când se calculează valorile SRTM pentru punctele din pista de mai sus, apare un grafic diferit (linia albastră):

O mică supărare aici sunt marginile aspre ale graficului, dar acest lucru este ușor de netezit. Rețineți că prin netezire pierdem puțină (dacă există) precizie, deoarece SRTM în sine oferă doar puncte discrete la poziții echidistante, între care trebuie să interpolăm în orice caz. Iată o versiune a graficului precedent cu o linie roșie suprapusă reprezentând datele SRTM netezite:

Toate acestea se pot face cu ușurință, întâmplător, folosind bibliotecile mele GPS Python:

• srtm.py: un parser python pentru datele de elevație Shuttle Radar Topography Mission (SRTM)
• gpxpy: o bibliotecă python simplă pentru analizarea și manipularea fișierelor GPX (GPX, formatul de schimb GPS, este un format ușor de date XML pentru datele GPS)

Pentru utilizatorii Ruby, există și biblioteca mea de analiză Geoelevations.rb pentru ondulațiile SRTM și EGM2008.

După ce am detectat aceste anomalii, în funcție de tipul de software cu care lucrăm, putem fie (a) să corectăm automat erorile, fie (b) pur și simplu să informăm utilizatorul că au fost detectate inexactități în datele de altitudine.

De asemenea, deoarece există diferiți algoritmi care pot fi utilizați pentru a corecta în mod programatic aceste erori de elevație GPS, este posibil să dorim să oferim utilizatorului opțiunea de a selecta ce algoritm să folosească (de exemplu, utilizatorul dorește să folosim doar datele SRTM netezite? „ca atare” sau dorește utilizatorul să folosim datele SRTM pentru a ajuta la corectarea cotelor raportate de dispozitiv).

Netezirea pistei și eliminarea valorii aberante

Dacă un jucător de fotbal ar purta un dispozitiv GPS și ar înregistra un joc, pista rezultată ar fi o mizerie. Terenul de joc ar fi plin dens cu o pistă constând din multe viraje bruște, accelerații și decelerații.

Din fericire, majoritatea cazurilor în care oamenii folosesc GPS nu vor avea același model - liniile de urmărire GPS (și accelerațiile) vor fi relativ netede. În astfel de cazuri, punctele neregulate din traseul nostru pot fi presupuse a fi induse de erori și astfel de valori aberante pot fi, prin urmare, eliminate în mod rezonabil cu o funcție de netezire.

În calitate de dezvoltator GIS, netezirea se realizează cel mai frecvent prin iterarea punctelor și schimbarea coordonatelor pe baza valorilor coordonatelor învecinate. De exemplu, putem schimba fiecare latitudine și longitudine cu un algoritm precum următorul:

 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

Cu cât coeficientul este mai mare, cu atât este mai mare impactul punctului învecinat corespunzător asupra locației modificate a punctului curent. Coeficienții pe care îi folosesc în acest exemplu (0,3, 0,4, 0,3) sunt oarecum arbitrari, dar în cele mai multe cazuri veți dori ca suma lor să fie egală cu 1,0. (O abordare mai sofisticată, de exemplu, ar fi folosirea distanței dintre puncte și apoi, cu cât punctul este mai aproape, cu atât coeficientul corespunzător este mai mare.)

Iată un exemplu de piesă cu multe erori aleatorii:

Observați cum pista nu urmărește bine poteca, are o mulțime de viraje ascuțite și dințate și, uneori, se îndepărtează complet de calea așteptată.

După câteva iterații „de netezire”, această piesă este transformată în:

Deși este mult mai bine, este încă imperfect. Rețineți că există încă locuri (în special în apropierea mijlocului căii) în care pista se îndreaptă încă de pe șosea.

Există și alte lucruri pe care le puteți încerca. În anumite regiuni și pentru anumite aplicații GPS, puteți utiliza și datele OpenStreetMap (OSM) pentru a încerca să ghiciți calea corectă și apoi să „prindeți” punctele pe această nouă linie. Deși acest lucru poate fi adesea util, poate fi și imperfect, cum ar fi în cazurile în care datele OSM conțin două linii paralele (de exemplu, o autostradă și un drum din apropiere) sau multe căi apropiate.

În astfel de cazuri, o posibilă soluție ar fi încercarea de a detecta tipul activității, folosind unele dintre tehnicile discutate mai departe în acest articol. Dacă putem deduce, de exemplu, că traseul a fost o pistă de drumeție și avem opțiunea de a ne aprinde pe o autostradă sau pe o potecă din apropiere, putem presupune cu siguranță că drumeția a fost de-a lungul potecii și nu a autostrăzii.

De asemenea, rețineți că, în timp ce acest exemplu demonstrează netezirea coordonatelor de suprafață (adică, longitudine/latitudine), netezirea poate fi o tehnică la fel de valabilă pentru eliminarea aberațiilor în datele de altitudine sau temporale, sau chiar în datele privind ritmul cardiac și cadența bicicletei.

Exemple de beneficii și utilizări suplimentare ale netezirii ar putea include:

• Calcularea creșterii totale a cotei. Pentru a calcula creșterea totală a cotei într-o pistă, nu este suficient să însumați toate micile „sărituri” în sus, deoarece acestea vor conține adesea erori mici. Netezirea cotei înainte de a face suma poate ajuta adesea la atenuarea acestei probleme.
• Eliminarea valorii aberante. După „netezire”, punctele care sunt prea departe de pistă pot fi detectate mai ușor. Acestea pot fi adesea presupuse a fi valori aberante și utilizatorului i se poate solicita să întrebe dacă ar trebui eliminate.

Există un fel de problemă în care acest algoritm este scurt: în unele cazuri, GPS-ul va înregistra o cale lină, dar calea va fi „deplasată” printr-o diferență constantă într-o anumită direcție. În astfel de cazuri, netezirea poate netezi și mai mult linia, dar nu va corecta această eroare de schimbare.

O problemă suplimentară mai puțin evidentă, dar semnificativă, cu tehnica simplistă de netezire pe care am descris-o este că transformarea modifică toate (sau aproape toate) punctele din cale, chiar și pe cele care nu sunt în eroare. Deși această abordare mai simplă tinde să fie o soluție rezonabilă pentru utilizatorul mediu de GPS, algoritmi de netezire mai sofisticați sunt cu siguranță utilizabili în programarea GIS. În unele cazuri, poate fi chiar mai bine să eliminați pur și simplu valorile aberante fără a efectua nicio netezire, în funcție de utilizator, dispozitiv și aplicație.

Detectarea vitezei maxime

Detectarea vitezei maxime a unei piste este destul de simplă dacă avem coordonatele și marcajele de timp ale tuturor punctelor de pe traseu. Doar calculați vitezele dintre puncte și găsiți cea mai mare valoare. Pare simplu.

Dar amintiți-vă, avem de-a face cu dispozitive GPS low-end și nu avem deplină încredere în date, ceea ce poate avea ramificații semnificative pentru calculul nostru. Dacă un dispozitiv înregistrează o locație la fiecare 5 metri și la un moment dat face o greșeală prin plasarea greșită a punctului cu 10 metri, atunci acea parte a pistei poate părea a fi de 3 ori mai rapidă decât era!

O abordare comună în lumea dezvoltării GIS este de a extrage toate vitezele dintre puncte și apoi doar eliminați primele 5% (adică folosiți percentila 95) în speranța că cei 5% eliminati reprezintă majoritatea erorilor. Dar acest lucru este, desigur, neștiințific și nu asigură rezultate corecte. În experimentarea cu această tehnică, am încercat valori diferite pentru percentile și am constatat că unele au funcționat bine pentru un dispozitiv GPS, unele au funcționat bine pentru altele. Unele merg bine pentru drumeții, iar altele pentru ciclism. Dar, în majoritatea cazurilor, rezultatele pur și simplu nu mi s-au părut potrivite.

După ce am încercat mulți algoritmi, ceea ce a funcționat pentru mine a fost simplu: să adaug un alt filtru pentru a elimina extremele, nu numai după viteză, ci și după distanță, după cum urmează:

1. Sortați punctele după distanța dintre vecini și eliminați primele 5%.
2. (Opțional:) Neteziți pista (orizontal și/sau vertical).
3. Sortați punctele după viteză între vecini și eliminați primele 5%.

Din experiența mea, acest algoritm dă rezultate destul de credibile, chiar și pentru traseele de pe dispozitive GPS ieftine cu erori aleatorii.

Deducerea tipului de activitate

În multe cazuri, viteza medie este suficientă pentru a determina tipul de activitate. Dacă viteza medie este de 5 km/h, de exemplu, este probabil o pistă de mers pe jos/de drumeții, în timp ce dacă viteza medie este de 30 km/h, este probabil o pistă de ciclism și așa mai departe.

Dar dacă viteza medie este de 12 km/h, nu poți fi sigur dacă utilizatorul mergea cu bicicleta montană sau alerga. În astfel de cazuri, viteza maximă poate ajuta uneori la diferențierea între cele două tipuri de activități. Mai exact, ne putem folosi de faptul că alergătorii ating rareori o viteză mai mare de două ori mai mare decât media, în timp ce bicicliștii o fac în mod regulat (de exemplu, în timp ce coboară la vale pe o potecă nu prea dificilă).

În consecință, o pistă cu o viteză medie de 12 km/h și o viteză maximă de 18 km/h a fost probabil înregistrată în timpul alergării, în timp ce o pistă cu o viteză medie de 12 km/h și o viteză maximă de 30 km/h a fost probabil înregistrată în timpul mersului cu bicicleta montană. (Desigur, trebuie să fim siguri că viteza maximă calculată este corectă, pentru ca aceasta să funcționeze în mod fiabil.)

Procentul de cer vizibil: un proxy inteligent pentru detectarea erorilor GPS

Precizia fiecărei măsurători GPS (adică latitudine, longitudine și altitudine) depinde foarte mult de numărul de sateliți care erau vizibili în momentul înregistrării. Deci, dacă am putea determina cumva câți sateliți erau „în vizor” la momentul fiecărei înregistrări, am putea folosi asta ca o modalitate de a aproxima acuratețea acelei înregistrări. Dacă am ști cumva, de exemplu, că toți sateliții GPS necesari sunt în vedere, am putea presupune un grad ridicat de acuratețe pentru datele GPS corespunzătoare. În schimb, dacă am ști cumva că nu sunt în vedere niciun sateliți GPS, am putea presupune că datele sunt predispuse la erori.

Dar înainte de a fi prea entuziasmat, luați în considerare complexitatea încercării de a rezolva o astfel de problemă GIS. În primul rând, ar trebui să știți cu ce sisteme de satelit GPS a fost capabil să comunice dispozitivul dvs. Există sistemul original de poziționare globală din SUA, Gallileo european și sistemul rusesc GLONASS. Unele dispozitive funcționează cu toate aceste tipuri de sateliți, dar multe nu. Și multe dispozitive nici măcar nu raportează ce sistem(e) folosesc.

Dar există o modalitate inteligentă de a ocoli această complexitate și de a realiza o aproximare brută a numărului de sateliți în vedere: utilizați procentul de cer vizibil ca proxy pentru numărul de sateliți vizibili . Cerul mai puțin vizibil înseamnă că GPS-ul nostru poate „vedea” (sau poate fi văzut) de mai puțini sateliți. Dar cum putem calcula procentul din cerul vizibil în orice punct de pe Pământ? Soluția este de fapt destul de simplă: putem calcula linia orizontului din jurul nostru folosind datele SRTM discutate anterior.

De exemplu, acesta este orizontul dacă vă aflați în valea de sub Triglav (cel mai înalt vârf al Sloveniei), calculat folosind SRTM:

(Pentru cei interesați, codul meu pentru a crea această imagine poate fi găsit aici.)

Această imagine este în principiu făcută din straturi de grafice echidistante de elevație, văzute dintr-un punct central. Cu cât zona albastră este mai întunecată, cu atât stratul de elevație este mai îndepărtat; cu cât zona albastră este mai deschisă, cu atât stratul de elevație este mai aproape. Cele mai înalte puncte desenate reprezintă linia orizontului. Dacă un satelit GPS se află sub această linie pe cer, dispozitivul nostru probabil nu poate vedea (sau fi văzut) de el. (Rețineți, totuși, că, deși imaginea este desenată ca dreptunghi aplatizat, în realitate veți avea nevoie de niște cunoștințe de bază despre geometria sferică pentru a calcula corect zona de sub orizont.)

Un alt lucru de reținut este că acesta nu este un glonț de argint pentru detectarea erorilor de elevație GPS. În primul rând, majoritatea părților Pământului nu sunt muntoase și, chiar și atunci când sunt, este în psihologia noastră să supraestimăm altitudinile; procentul real al cerului vizibil este mai mare de 75% în marea majoritate a regiunilor locuite . Dar, cu toate acestea, această metodă poate fi utilă în anumite situații, cum ar fi drumețiile montane, unde puteți trece de la a vă afla într-un canion adânc (cu recepție GPS slabă) la a vă afla pe o creastă de munte (unde recepția prin satelit este probabil mult mai bună). Deși această metodă nu este o măsură absolută a numărului de erori pe care le are pista, poate fi un indicator util al ce părți ale pistei dvs. pot fi mai predispuse la erori decât altele.

Învelire

Am discutat despre unele dintre cele mai frecvente tipuri de erori de urmărire GPS la care se poate aștepta cu dispozitivele GPS de gamă inferioară. Am oferit o înțelegere a cauzelor acestora, precum și câteva tehnici de programare GIS pentru corectarea lor.

În unele cazuri, putem corecta traseul cu un grad ridicat de încredere. În alte cazuri, putem cel puțin avertiza utilizatorul cu privire la porțiuni ale piesei care par discutabile. În cazurile în care nu suntem siguri, există întotdeauna opțiunea de a permite utilizatorului să repare singur traseul, ajutat de imagini aeriene și hărți. Estimările noastre probabilistice pot ajuta la evidențierea acelor părți ale pistei în care am detectat o probabilitate mai mare de erori.

În multe cazuri, tehnicile pe care le-am evidențiat pot fi o „soluție de 80%” satisfăcătoare, oferind utilizatorilor dispozitivelor GPS low-end un nivel rezonabil de îmbunătățire automată a preciziei traseelor ​​lor GPS.