Aventures dans la programmation et le développement GPS : un didacticiel géospatial

Tout a commencé lors d'une randonnée à Zbevnica il y a plus de 10 ans. J'avais mon nouveau GPS avec moi et un de mes amis avait un GPS connecté à un téléphone Windows ME. La randonnée a été formidable, mais lorsque nous sommes retournés à nos voitures, nous avons été surpris de voir qu'un GPS affirmait que nous avions parcouru 6,2 km, tandis que l'autre indiquait 6,7 km. L'un a affirmé que notre gain d'altitude (c'est-à-dire la somme de toutes les parties en montée de notre randonnée) avait été de 300 m, tandis que l'autre l'a rapporté à 500 m.

En tant que programmeur (et éventuellement programmeur SIG), j'ai été immédiatement intrigué par le problème. Je me suis dit, "cela ne devrait pas être si difficile à résoudre avec un simple script." Après tout, les traces GPS ne sont qu'une liste de tuples sous la forme de (latitude, longitude, altitude) , n'est-ce pas ?

Eh bien pas vraiment.

Et c'est ainsi que commença mon excursion dans le monde fascinant des traces GPS, des erreurs de suivi et, plus généralement, de la programmation SIG.

Les systèmes d'information géospatiale (SIG) sont un domaine vaste et complexe, englobant les projections cartographiques et les données géodésiques), le traitement des données raste et vecto et la télédétection. Une introduction complète à ce domaine dépasserait largement le cadre de cet article. Et puisque se concentrer sur un problème spécifique peut souvent être un moyen utile de s'introduire dans un nouveau domaine de toute façon, je présenterai quelques défis SIG spécifiques que j'ai rencontrés et quelques solutions possibles ; à savoir:

• Comment reconnaître, comprendre et corriger par programmation les erreurs de suivi GPS
• Comment calculer et dériver des informations utiles supplémentaires à partir des traces GPS

Pour commencer, les traces GPS ne sont pas simplement une série de tuples (latitude, longitude, altitude) . De nombreux appareils compatibles GPS fourniront également des métadonnées telles que l'heure, la fréquence cardiaque, etc. Certains appareils GPS fourniront même des informations sur la précision des données ; aka, "dilution de précision". Mais, malheureusement, la plupart des appareils GPS - en particulier ceux bas de gamme qui dominent le marché - ne fourniront pas ces informations et nous nous retrouvons avec le défi de déduire nous-mêmes la précision de l'appareil (et idéalement de corriger en conséquence, si possible ).

Commençons par un algorithme possible pour détecter les appareils GPS bas de gamme (comme la plupart des smartphones) qui ont généralement des données GPS de mauvaise qualité.

Erreurs d'élévation et idiosyncrasies

Si vous vivez dans certaines parties du monde, vous avez peut-être remarqué quelque chose d'étrange concernant la précision de l'altitude du GPS lorsque vous enregistrez des tracés avec votre smartphone. Lorsque vous vérifiez les élévations, elles sont systématiquement enregistrées comme supérieures ou inférieures (d'une valeur constante) à l'élévation de droite. Par exemple, j'habite à Višnjan (Croatie) et mon Android n'arrête pas de me dire que je suis à environ 35-40 mètres au-dessus de l'altitude réelle.

Par exemple, voici un graphique d'élévation GPS d'une courte randonnée que j'ai faite il y a quelques mois :

Deux choses à noter ici.

Tout d'abord, la "colline" dans la première partie des données GPS enregistrées a été entièrement fabriquée par l'appareil . Alors que le graphique semblerait indiquer que le point culminant de notre randonnée n'était qu'à quelques centaines de mètres du départ, en réalité c'était environ 4 km plus tard.

Deuxièmement, ce qui est peut-être plus important (et non visible sur le graphique), c'est que l'ensemble du graphique est inexact . Les valeurs d'altitude ont toujours été signalées comme étant environ 30 à 40 mètres plus élevées qu'elles ne l'étaient en réalité, comme nous le verrons plus en détail plus loin dans cet article.

C'est le genre de choses qui peuvent arriver avec des appareils GPS bon marché. Et lorsque nous pouvons détecter que la trace comporte ces erreurs, nous pouvons en déduire que l'appareil est probablement un GPS de mauvaise qualité qui peut donc s'attendre à avoir également d'autres erreurs - pas seulement des erreurs d'élévation - qui sont communes à de tels appareils.

Erreurs d'élévation de démarrage

Il existe essentiellement deux techniques utilisées par les appareils GPS pour déterminer l'altitude : "l'altitude GPS" (telle que rapportée à l'appareil par le système de satellites GPS) et "l'altitude barométrique" (calculée par l'appareil sur la base des relevés de pression barométrique). Ni l'un ni l'autre n'est parfait.

Les valeurs d'altitude GPS peuvent comporter de nombreuses petites erreurs (généralement de l'ordre de +/- 10 m), ce qui peut être particulièrement problématique si nous décidons plus tard de calculer le gain d'altitude cumulé. L'altitude barométrique, en revanche, est sensible non seulement à l'altitude mais aussi aux conditions météorologiques, qui peuvent introduire leur propre ensemble d'imprécisions.

Certains appareils utilisent donc une approche hybride, utilisant des lectures barométriques pour enregistrer l'altitude, mais utilisant des lectures GPS pour aider à (ré)étalonner ces valeurs, pour aider à tenir compte des changements météorologiques (pression), etc. Avec de tels appareils, lors du démarrage de la piste, l'élévation barométrique peut être complètement erronée, mais ensuite en la recalibrant avec de plus en plus de données satellites GPS, les données d'élévation deviennent plus fiables. Il n'est donc pas rare avec de tels appareils de rencontrer le type d'erreur de démarrage "fake hill" que nous avons observé plus haut sur notre graphe d'élévation.

Inexactitudes continues de l'altitude du GPS

Pour expliquer l'erreur constante dans les rapports d'altitude, nous devons revenir à la géographie de notre école élémentaire. Les professeurs de géographie expliquent généralement que la Terre n'est pas une sphère mais un ellipsoïde. Si cela était, en fait, strictement vrai, l'altitude serait facile à calculer mathématiquement. Mais ce n'est pas. La Terre est irrégulière; en réalité, cela ressemble plus à une pomme de terre ressemblant à un ellipsoïde qu'à un ellipsoïde parfait, ce qui signifie que pour le développement SIG, vous avez besoin d'un ensemble de données d'altitude détaillées pour presque tous les points de la terre. En géodésie, cet ellipsoïde de référence (alias datum) est une surface définie mathématiquement qui se rapproche du géoïde, la figure « plus vraie » de la Terre.

De plus, il est important de reconnaître que même ces données ne sont que des approximations de la forme réelle de la surface de la Terre. Certains fonctionnent mieux dans certaines parties du monde, et d'autres fonctionnent mieux dans d'autres. À titre d'exemple, l'image ci-dessous (générée à l'aide de ma bibliothèque Ruby) montre comment la Terre diffère de l'un des modèles d'ellipsoïdes les plus couramment utilisés (le datum WGS84). Les parties noires représentent des parties de la Terre au-dessus, et le blanc représente des parties de la Terre en dessous, l'ellipsoïde idéal (contours continentaux et insulaires représentés en rouge).

Vous pouvez voir que l'Inde est en dessous de l'ellipsoïde WGS84 avec la partie sud étant le minimum absolu (presque -100 mètres !) et l'Europe est au-dessus.

Étant donné que les appareils GPS de mauvaise qualité n'utilisent pas de telles données, ils calculent simplement l'élévation en supposant un ellipsoïde parfait. D'où leur imprécision constante.

Détecter et corriger les erreurs d'élévation GPS

Dans le développement d'applications GPS, la détection qu'un appareil qui a enregistré notre trace présente ces types d'erreurs peut être effectuée à l'aide de l'ensemble de données Earth Gravitational Model EGM2008, également parfois appelé ensemble de données « ondulations du géoïde ». Avec EGM2008, nous pouvons approximer la différence entre la surface terrestre réelle et l'ellipsoïde idéal.

Mais pour savoir si notre trace GPS a cette erreur, nous avons encore besoin d'une chose : l'altitude réelle . Une base de données publique qui peut être utile à cette fin est la Shuttle Radar Topography Mission (SRTM). SRTM est une base de données raster qui fournit des valeurs d'élévation à une résolution d'environ tous les 30 m (à l'équateur) pour les États-Unis et tous les 90 m pour le reste du monde. Par exemple, lors du calcul des valeurs SRTM pour les points de la piste ci-dessus, un graphique différent (la ligne bleue) apparaît :

Un petit ennui ici est les bords rugueux du graphique, mais cela est facilement lissé. Notez qu'en lissant, nous perdons peu (voire pas du tout) de précision, puisque SRTM lui-même ne fournit que des points discrets à des positions équidistantes, entre lesquelles nous devons interpoler dans tous les cas. Voici une version du graphique précédent avec une superposition de lignes rouges représentant les données SRTM lissées :

Tout cela peut être fait facilement, accessoirement, en utilisant mes bibliothèques GPS Python :

• srtm.py : un analyseur python pour les données d'élévation de la mission de topographie radar de la navette (SRTM)
• gpxpy : une bibliothèque python simple pour analyser et manipuler des fichiers GPX (GPX, le format d'échange GPS, est un format de données XML léger pour les données GPS)

Pour les utilisateurs de Ruby, il y a aussi ma bibliothèque d'analyseurs Geoelevations.rb pour les ondulations SRTM et EGM2008.

Après avoir détecté ces anomalies, selon le type de logiciel avec lequel nous travaillons, nous pouvons soit (a) corriger automatiquement les erreurs nous-mêmes, soit (b) simplement informer l'utilisateur que des inexactitudes ont été détectées dans ses données d'altitude.

De plus, comme il existe différents algorithmes qui peuvent être utilisés pour corriger par programme ces erreurs d'élévation GPS, nous pouvons donner à l'utilisateur la possibilité de sélectionner l'algorithme à utiliser (par exemple, l'utilisateur veut-il que nous utilisions uniquement les données SRTM lissées "tel quel" ou l'utilisateur souhaite-t-il que nous utilisions les données SRTM pour aider à corriger les élévations signalées par l'appareil).

Lissage de la piste et suppression des valeurs aberrantes

Si un joueur de football devait porter un appareil GPS et enregistrer un match, la piste résultante serait un gâchis. Le terrain de jeu serait densément rempli d'une piste composée de nombreux virages serrés, accélérations et décélérations.

Heureusement, la plupart des cas où les gens utilisent le GPS n'auront pas ce même schéma - les lignes de suivi GPS (et les accélérations) seront relativement fluides. Dans de tels cas, les points erratiques de notre piste peuvent être présumés être induits par des erreurs et ces valeurs aberrantes peuvent donc être raisonnablement supprimées avec une fonction de lissage.

En tant que développeur SIG, le lissage est le plus souvent réalisé en parcourant les points et en modifiant les coordonnées en fonction des valeurs des coordonnées voisines. Par exemple, nous pouvons changer chaque latitude et longitude avec un algorithme tel que le suivant :

 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

Plus le coefficient est grand, plus l'impact du point voisin correspondant sur la position modifiée du point courant est important. Les coefficients que j'utilise dans cet exemple (0,3, 0,4, 0,3) sont quelque peu arbitraires, mais dans la plupart des cas, vous voudrez que leur somme soit égale à 1,0. (Une approche plus sophistiquée, par exemple, consisterait à utiliser la distance entre les points, puis, plus le point est proche, plus le coefficient correspondant est grand.)

Voici un exemple de piste avec beaucoup d'erreurs aléatoires :

Notez que la piste ne suit pas bien le chemin, comporte de nombreux virages serrés et dentelés et s'écarte parfois complètement du chemin prévu.

Après quelques itérations de « lissage », cette même piste se transforme en :

Bien que ce soit beaucoup mieux, c'est encore certes imparfait. Notez qu'il y a encore des endroits (en particulier près du milieu du chemin) où la piste dévie encore de la route.

Il y a d'autres choses que vous pouvez essayer. Dans certaines régions, et pour certaines applications GPS, vous pouvez également utiliser les données OpenStreetMap (OSM) pour essayer de deviner le bon chemin puis "aligner" les points sur cette nouvelle ligne. Bien que cela puisse souvent être utile, cela peut aussi être imparfait, comme dans les cas où les données OSM contiennent deux lignes parallèles (par exemple une autoroute et une route à proximité) ou de nombreux chemins proches.

Dans de tels cas, une solution possible serait d'essayer de détecter le type d'activité, en utilisant certaines des techniques discutées plus loin dans cet article. Si nous pouvons en déduire, par exemple, que la piste était une piste de randonnée et avoir la possibilité de s'accrocher à une autoroute ou à un chemin à proximité, nous pouvons supposer en toute sécurité que la randonnée était le long du chemin et non de l'autoroute.

Notez également que, bien que cet exemple démontre le lissage des coordonnées de surface (c'est-à-dire la longitude/latitude), le lissage peut être une technique tout aussi valable pour éliminer les aberrations dans les données d'altitude ou temporelles, ou même dans les données de fréquence cardiaque et de cadence de vélo.

Voici des exemples d'avantages et d'utilisations supplémentaires du lissage :

• Calcul du dénivelé total. Pour calculer le dénivelé total d'une piste, il ne suffit pas de faire la somme de tous les petits "sauts" en montée car ils contiennent souvent de petites erreurs. Lisser l'élévation avant de faire la somme peut souvent aider à atténuer ce problème.
• Suppression des valeurs aberrantes. Après « lissage », les points trop éloignés de la trace peuvent être plus facilement détectés. Ceux-ci peuvent alors souvent être supposés être des valeurs aberrantes et l'utilisateur peut être invité à demander s'ils doivent être supprimés.

Il y a un type de problème où cet algorithme échoue : dans certains cas, le GPS enregistrera un chemin régulier, mais le chemin sera "décalé" par une différence constante dans une certaine direction. Dans de tels cas, le lissage peut encore lisser la ligne mais ne corrigera pas cette erreur de décalage.

Un problème supplémentaire moins évident, mais significatif, avec la technique de lissage simpliste que nous avons décrite est que la transformation modifie tous (ou presque tous) les points du chemin, même ceux qui ne sont pas en erreur. Bien que cette approche plus simple tende à être une solution raisonnable pour l'utilisateur moyen de GPS, des algorithmes de lissage plus sophistiqués sont certainement utilisables dans la programmation SIG. Dans certains cas, il peut même être préférable de simplement supprimer les valeurs aberrantes sans effectuer de lissage en fonction de l'utilisateur, de l'appareil et de l'application.

Détection de la vitesse maximale

Détecter la vitesse maximale d'une piste est assez simple si nous avons les coordonnées et les horodatages de tous les points sur la route. Calculez simplement les vitesses entre les points et trouvez la valeur la plus élevée. Cela semble simple.

Mais rappelez-vous, nous avons affaire à des appareils GPS bas de gamme et nous ne faisons pas entièrement confiance aux données, ce qui peut avoir des ramifications importantes pour notre calcul. Si un appareil enregistre un emplacement tous les 5 mètres et qu'à un moment donné, il fait une erreur en déplaçant le point de 10 mètres, alors cette partie de la piste peut sembler être 3 fois plus rapide qu'elle ne l'était !

Une approche courante dans le monde du développement SIG consiste à extraire toutes les vitesses entre les points, puis à supprimer les 5 % supérieurs (c'est-à-dire utiliser le 95e centile) en espérant que les 5 % éliminés représentent la majorité des erreurs. Mais cela n'est certes pas scientifique et ne garantit pas des résultats corrects. Au cours de mes expériences avec cette technique, j'ai essayé différentes valeurs de centiles et j'ai constaté que certaines fonctionnaient bien pour un appareil GPS, d'autres fonctionnaient bien pour d'autres. Certains fonctionnent bien pour la randonnée et d'autres pour le vélo. Mais dans la plupart des cas, les résultats ne me convenaient tout simplement pas.

Après avoir essayé de nombreux algorithmes, ce qui a fonctionné pour moi était simple : ajouter un autre filtre pour supprimer les extrêmes, non seulement par vitesse, mais aussi par distance, comme suit :

1. Triez les points par distance entre voisins et supprimez les 5 % supérieurs.
2. (Facultatif :) Lisser la piste (horizontalement et/ou verticalement).
3. Triez les points par vitesse entre voisins et supprimez les 5 % supérieurs.

D'après mon expérience, cet algorithme donne des résultats assez crédibles, même pour les pistes d'appareils GPS bon marché avec des erreurs aléatoires.

Déduire le type d'activité

Dans de nombreux cas, la vitesse moyenne est suffisante pour déterminer le type d'activité. Si la vitesse moyenne est de 5 km/h, par exemple, il s'agit probablement d'une piste de marche/randonnée, alors que si la vitesse moyenne est de 30 km/h, il s'agit probablement d'une piste cyclable, et ainsi de suite.

Mais si la vitesse moyenne est de 12 km/h, vous ne pouvez pas être certain si l'utilisateur faisait du VTT ou courait. Dans de tels cas, la vitesse maximale peut parfois aider à différencier les deux types d'activités. Plus précisément, nous pouvons utiliser le fait que les coureurs atteignent rarement une vitesse supérieure au double de leur moyenne, alors que les cyclistes le font régulièrement (par exemple, en descendant sur un chemin pas trop difficile).

Ainsi, une piste avec une vitesse moyenne de 12 km/h et une vitesse maximale de 18 km/h a probablement été enregistrée en courant, alors qu'une piste avec une vitesse moyenne de 12 km/h et une vitesse maximale de 30 km/h a probablement été enregistrée en VTT. (Bien sûr, nous devons être sûrs que notre vitesse maximale calculée est correcte, pour que cela fonctionne de manière fiable.)

Pourcentage de ciel visible : un proxy intelligent pour la détection d'erreurs GPS

La précision de chaque mesure GPS (c'est-à-dire la latitude, la longitude et l'élévation) dépend beaucoup du nombre de satellites qui étaient visibles au moment de l'enregistrement. Donc, si nous pouvions déterminer d'une manière ou d'une autre combien de satellites étaient "en vue" au moment de chaque enregistrement, nous pourrions l'utiliser comme moyen d'approximation de la précision de cet enregistrement. Si nous savions d'une manière ou d'une autre, par exemple, que tous les satellites GPS nécessaires étaient en vue, nous pourrions supposer un haut degré de précision pour les données GPS correspondantes. Inversement, si nous savions d'une manière ou d'une autre qu'aucun satellite GPS n'était en vue, nous pourrions supposer que les données sont sujettes aux erreurs.

Mais avant de vous exciter trop, considérez la complexité de tenter de résoudre un tel problème SIG. Tout d'abord, vous devez savoir avec quel(s) système(s) de satellites GPS votre appareil est capable de communiquer. Il y a le système de positionnement global basé aux États-Unis, le Gallileo européen et le système russe GLONASS. Certains appareils fonctionnent avec tous ces types de satellites, mais beaucoup ne le font pas. Et de nombreux appareils n'indiquent même pas quel(s) système(s) ils utilisent.

Mais il existe un moyen astucieux de contourner cette complexité et d'obtenir une approximation grossière du nombre de satellites en vue : utiliser le pourcentage de ciel visible comme approximation du nombre de satellites visibles . Un ciel moins visible signifie que notre GPS peut « voir » (ou être vu) par moins de satellites. Mais comment calculer le pourcentage du ciel visible sur n'importe quel point de la Terre ? La solution est en fait assez simple : nous pouvons calculer la ligne d'horizon autour de nous en utilisant les données SRTM discutées précédemment.

Par exemple, c'est l'horizon si vous vous trouvez dans la vallée en dessous du Triglav (le plus haut sommet de Slovénie) tel que calculé à l'aide de SRTM :

(Pour ceux que ça intéresse, mon code pour créer cette image se trouve ici.)

Cette image est essentiellement constituée de couches de graphiques d'élévation équidistants vus d'un point central. Plus la zone bleue est foncée, plus la couche d'altitude est éloignée ; plus la zone bleue est claire, plus la couche d'altitude est proche. Les points les plus hauts dessinés représentent la ligne d'horizon. Si un satellite GPS se trouve en dessous de cette ligne dans le ciel, notre appareil ne peut probablement pas voir (ou être vu) par lui. (Notez cependant que bien que l'image soit dessinée sous forme de rectangle aplati, en réalité, vous auriez besoin de connaissances de base en géométrie sphérique pour calculer correctement la zone sous l'horizon.)

Une autre chose à garder à l'esprit est qu'il ne s'agit pas d'une solution miracle pour détecter les erreurs d'élévation GPS. Tout d'abord, la plupart des régions de la Terre ne sont pas montagneuses et, même lorsqu'elles le sont, il est dans notre psychologie de surestimer les élévations ; le pourcentage réel du ciel visible est supérieur à 75% dans la grande majorité des régions habitées . Mais néanmoins, cette méthode peut être utile dans certaines situations, comme la randonnée en montagne où vous pouvez passer d'un canyon profond (avec une mauvaise réception GPS) à une crête de montagne (où la réception satellite est probablement bien meilleure). Bien que cette méthode ne soit pas une mesure absolue du nombre d'erreurs de la piste, elle peut être un indicateur utile des parties de votre piste qui sont plus sujettes aux erreurs que d'autres.

Emballer

Nous avons discuté de certains des types d'erreurs de suivi GPS les plus courants auxquels s'attendre avec les appareils GPS bas de gamme. Nous avons fourni une compréhension de ce qui les cause ainsi que des techniques de programmation SIG pour les corriger.

Dans certains cas, nous pouvons corriger la piste avec un degré élevé de confiance. Dans d'autres cas, nous pouvons au moins alerter l'utilisateur sur des portions de la piste qui semblent douteuses. En cas de doute, il est toujours possible de permettre à l'utilisateur de fixer lui-même la trace, à l'aide d'images aériennes et de cartes. Nos suppositions probabilistes peuvent aider à mettre en évidence les parties de la piste où nous avons détecté une probabilité d'erreurs plus élevée.

Dans de nombreux cas, les techniques que nous avons décrites peuvent être une « solution à 80 % » satisfaisante, offrant aux utilisateurs d'appareils GPS bas de gamme un niveau raisonnable d'amélioration automatisée de la précision de leurs tracés GPS.