algorithme de lissage d'une trace GPS

salut,

Je fais un petit programme (on dira pour le plaisir...) qui calcule le cumul D+ d'une trace GPX.
J'ai pris ce que j'avais sous la main : l'UTMB, D+ 9500m.
Trace (puis kmz->kml->gpx) depuis le site officiel :
http://www.ultratrailmb.com/documents/P ... B-2011.kmz

Si je programme bêtement les cumuls, j'obtiens +10988m (et -11426m...).
Evidemment c'est pas ça pour le D+ (sans compter que Chamonix s'est affaissé entre temps), alors j'ai pensé lisser la liste des altitudes.
J'ai commencé par faire la moyenne simple du point et de ses deux voisins : +9707m.
J'ai modifié le truc en pondérant 1/4, 2/4, 1/4, résultat +9807m...
Alors j'ai lissé par bloc de 5 points (suivant une binômiale, pour les connaisseurs...) : 1/16, 4/16, 6/16, 4/16, 1/16. Ca me semblait cool comme pondération.
Et là je sors +9534m, ce qui semble bon.

Questions :
1) le seuil est-il à rajouter absolument en complément ?
2) y a-t-il un relatif consensus sur la bidouille optimale (en moyenne) ?
3) comment procèdent les nombreux sites/logiciels au niveau du lissage ?

Merci !

d'ou sort ce 9500m de D+ pour l'UTMB ?
l'indication d'un organisateur est-elle forcèment juste ?
tes algos fonctionnent-ils pour un parcours au profil différent comme l'ecotrail (fichiers gps dispos depuis http://www.kikourou.net/calendrier/cour ... -2012.html ) ?

ça paraît moins convaincant sur ce parcours plat. (Mais les D+- des kikoureurs sont très variables dans l'affichage du site.)
Je vais rajouter le seuil pour voir.

ça paraît moins convaincant sur ce parcours plat. (Mais les D+- des kikoureurs sont très variables dans l'affichage du site.)
Je vais rajouter le seuil pour voir.

si tu arrives à avoir un algo qui est plus juste que celui du site, cela m'intéresse. peut-être faut-il ne pas avoir le même algo selon les différences d'altitude entre points hauts et points bas (différence entre un UTMB et un eco-trail).

[Mathias]

tu peux aussi jeter un oeil à visugpx.com, qui propose, une fois qu'on a uploadé sa trace, le graphique du D+ en ajustant le seuil à 5m, 10m,... et ça fait de sacrés différences !

merci de vos réponses.

Oui j'ai découvert visugpx après avoir attaqué le prog, pour comparer mes résultats. (J'utilisais clicgpx auparavant.)
Je vais réfléchir à l'implémentation du seuil (facile si critère basique, mais peut-être y a-t-il plus subtil).

Le vrai problème c'est d'avoir des parcours à la fois issus de GPS basiques et d'un parcours GPS de référence. Ensuite, vu que les mesures standards de nos GPS/alti sont assez vaseuses, il n'y a évidemment pas de méthode idéale pour corriger ça !

J'avais bossé sur ce problème il y a quelques temps pour le logiciel "Turtlesport" (http://turtlesport.sourceforge.net/FR/home.html) qui est un logiciel opensource écrit en java (et multiplateforme) par Denis Apparicio. Il exploite actuellement les GPS Garmin. Les D+ qu'il donnait étaient mauvais et surtout on n'avait pas le même D+/D- sur une boucle .

J'ai testé avec des algorithmes de lissage Savitzky-Golay http://robert.mellet.pagesperso-orange. ... grs_06.htm avec un template plus ou moins large. Un schéma plus large (je suis allé jusqu'à 15 points) améliorait les choses mais c'est lourd en calcul. Il faut dire que le forerunner, coté précision dans l'altitude c'est un poème!

Finalement j'ai implémenté un bête seuillage à 10m comme on le trouve sous visugpx (tant qu'on ne prends/perds pas 10m de D+/D- j'ignore la variation) pour sortir au mieux des imprécisions du GPS. C'est très économe en temps de calcul (ce genre de logiciel stocke les points dans un base de donnée et calcul le D+/D- cumulé quand tu ouvres le parcours) et ça donne des résultats quasi identiques sur les cumuls. C'est ce qui tourne aujourd'hui dans Turtlesport (ils ont intégré ma proposition de correctif).

Sur du plat, ça reste assez mauvais, mais en partant de données imprecises difficile de faire quelques chose de bien. Imagine 10000 points avec une imprécision de plusieurs mètres. Et comme tu cumules d'un coté les erreurs en D+ et de l'autre les erreurs en D- ça ne se compense pas!
Sur de la bosse ça donne de bons résultats en comparant avec une carte topo.

bon, avec le fichier gpx ecotrail (loicm 26/03/2012), la bonne recette est lissage 5 points et seuil 0,3m.
J'obtiens D+ 1524m. (C'est ça le D+ "officiel" ?)
Mais la méthode à appliquer est très différente d'une trace écotrail à l'autre... (Ne serait-ce que si les altitudes ont été obtenues à l'alti ou au GPS.)

Prochain objectif : essayer de seuiller automatiquement en fonction du type de trace GPX...

@çamontetrop : merci de ta réponse.

La description de l'implémentation du seuil à la Visugpx ici. Pour le lissage, il existe une infinité de méthodes...

J'avais trouvé un moyen correct de réduire les erreurs sur un enregistreur perso en stockant avec le point le nombre de satellites utilisés pour le fix (cf la trame GGA du protocole NMEA, l'information est accessible sous Android), et en pondérant la valeur du point en fonction du nombre (en partant du principe que la qualité de l'altitude est proportionnelle au nombre de sats en vue).
Mais bon, je fais juste mon intéressant.
Et pour l'anecdote, ma Suunto T6 annonce 1064 m de D+ sur l'Ecotrail 80 (barométrique), sachant qu'elle a un seuil de 3m et efface donc pas mal de petites bosses. Mais je ne suis pas sur que nous ayions eu les1500m D+ annoncés.

pour implémenter un essai de calcul plus fin du D+, je dois utiliser les positions. To continue, donc... I'll be back !
J'ai encore des idées en stock (mais aussi des enfants...) !
(Je sais bien que trouver une recette miracle est utopique, mais la prog reste amusante...)

... mais la prog reste amusante...)

(yep. dommage qu'on ne puisse faire de l'art pour l'art et qu'il faille délivrer des trucs qui font plaisir aux utilisateurs, on serait bien mieux à user la planète sur des causes perdues comme le cumul D+ depuis le GPS...)

[Mathias]

sinon y'a les traces de courses de ski de rando.
http://www.kikourou.net/entrainement/fi ... ?id=186554
avantage : des montées sans un seul mètre de D-, et des descentes quasi pareil

pour implémenter un essai de calcul plus fin du D+, je dois utiliser les positions. To continue, donc... I'll be back !
J'ai encore des idées en stock (mais aussi des enfants...) !
(Je sais bien que trouver une recette miracle est utopique, mais la prog reste amusante...)

Ça serait une idée de faire ça en plugin sur un logiciel libre, genre PyTrainer (y'a déjà un kikou qui le traduit et un autre kikou qui le package pour une distrib Linux, donc ça resterait en famille...)

http://sourceforge.net/projects/pytrainer/

ah ben ça tombe bien je programme en python...
J'ai implémenté le calcul de distance, j'obtiens 163km pour l'utmb, ce qui semble ça.
Mais j'ai encore une petite erreur d'arccos avec l'écotrail, bizarre. Le COS en région parisienne est différent de celui de Chamonix ?

Le COS en région parisienne est différent de celui de Chamonix ?

Bah, ça dépend de l'ellipsoïde de référence, quelque part...

ok c'est bon j'ai chopé une formule infâme mais moins problématique.
Ca me donne 83km pour l'écotrail.
Reste à utiliser ça pour tester des bidouilles de seuillage/lissage auto.

Si tu peux nous faire bénéficier de ton choix final... Je pourrai peut être essayer de le coder en Java dans Turtlesport, juste histoire de contribuer un peu à ce logiciel libre que j'utilise beaucoup!

Pour répondre à Mathias, les erreurs de D+/D- cumulé sont moins génantes sur du gros D+ que sur du plat car si le GPS se loupe de 4 ou 5m sur chaque point mais qu'il prend un point tout les 15 ou 20m de D+ ou D- les erreurs n'apparaissent pas. Le problème est principalement sur le plat ou faiblement vallonné....
Sur les digues de l'isère je prends régulièrement 200m de D+ au GPS en 20Km! Un facteur 10 sur le D+ réel et ni le lissage ni le seuillage ne semblent pouvoir corriger ces oscillations pendant l'acquisition des données!

J'y vois bien d'autres soucis, y-compris sur les sorties à fort D+:
- sur VisuGPX, entre le non-lissage et le lissage sur 15 points, et si en plus tu ajustes le seuil, les résultats sont plus que fantaisistes: je préfères nettement GPS Visualizer qui convertit tes fichiers en corrigeant les altitudes "suivant la meilleure source"; ça donne souvent des boucles avec une différence de D+ nulle ou égale à 1m, et bien plus proches des mesures sur carte IGN;
- selon ton réglage de GPS, si tu paramètres la fréquence d'enregistrement des points à plus ou moins rapide, tu obtiens des différences énormes pour le même parcours (les altitudes et autres virages sont plus ou moins gommés);
- enfin, selon ta propre progression, si tu cours vite, la précision de ton parcours sera moindre que si tu marches doucement.

Eric

J'y vois bien d'autres soucis, y-compris sur les sorties à fort D+:
- sur VisuGPX, entre le non-lissage et le lissage sur 15 points, et si en plus tu ajustes le seuil, les résultats sont plus que fantaisistes:

Fantaisistes je ne sais pas mais différent oui et c'est logique!
Regarde par exemple comment fonctionne le seuil ici. Pour moi une valeur de seuil de l'ordre de grandeur de la précision, soit 10m, me semble un bon compromis. Pour le lissage a la Visugpx (méthode des moyennes glissante), c'est normal qu'il y est une grosse différence entre 3 et 15 points par ex! Avec 15pts tu lisses un max les courbes

je préfères nettement GPS Visualizer qui convertit tes fichiers en corrigeant les altitudes "suivant la meilleure source"; ça donne souvent des boucles avec une différence de D+ nulle ou égale à 1m, et bien plus proches des mesures sur carte IGN;

Avec Visugpx, tu peux faire du seuil, du lissage et aussi remplacer toutes tes altitudes par celles d'une base (= calage des altitudes). C'est ce que font tous les Soft: Carto Explorer, Sporttracks, Openrunner... et surement aussi GPS Visualizer. Seul la base de données change...

- selon ton réglage de GPS, si tu paramètres la fréquence d'enregistrement des points à plus ou moins rapide, tu obtiens des différences énormes pour le même parcours (les altitudes et autres virages sont plus ou moins gommés);

Avec quel GPS et quelles fréquences?
Avec mon Garmin 305, c'est soit 1 pts/sec soit en mode intelligent (en pratique avec ce dernier c'est toujours environ 10-15 pts /min) et jamais vu de grosse différence.

- enfin, selon ta propre progression, si tu cours vite, la précision de ton parcours sera moindre que si tu marches doucement.

Pour moi c'est le contraire! Avec une fréquence d'enregistrement identique, plus tu va doucement, plus tu as de données et donc plus tu as de bruit dans les données.

- selon ton réglage de GPS, si tu paramètres la fréquence d'enregistrement des points à plus ou moins rapide, tu obtiens des différences énormes pour le même parcours (les altitudes et autres virages sont plus ou moins gommés);

Avec quel GPS et quelles fréquences?
Avec mon Garmin 305, c'est soit 1 pts/sec soit en mode intelligent (en pratique avec ce dernier c'est toujours environ 10-15 pts /min) et jamais vu de grosse différence.

Garmin aussi, mais Dakota 20, avec possibilité d'enregistrer selon une fréquence "normale", ou "plus" ou "moins souvent"; j'ai déjà testé en mode "très souvent"(ce qui doit correspondre à ton mode 1pt/seconde), et le fait d'obtenir plus de points enregistrés m'a amené plus de précisions dans le parcours; je préfère cependant rester en mode normal car sur sortie (très) longue, mes piles ne me permettent pas d'enregistrer les parcours en entier.

- enfin, selon ta propre progression, si tu cours vite, la précision de ton parcours sera moindre que si tu marches doucement.

Pour moi c'est le contraire! Avec une fréquence d'enregistrement identique, plus tu va doucement, plus tu as de données et donc plus tu as de bruit dans les données.

Voila qui m'étonne un peu; ce que je constate, c'est que les zigzags du terrain sur une descente deviennent des droites quand je cours, alors que l'enregistrement du même sentier à la marche en montée est rendu plus proche de la réalité. Et c'est d'ailleurs ce que je reproche à Openrunner, qui gomme beaucoup de points, pas toujours à bon escient!

Eric

Si je dis pas de conneries, la cadence de rafraîchissement des capteurs grand public est 1 seconde (fréquence du cycle NMEA)...IL est logique que le tracé enregistré soit plus juste lorsqu'on va lentement (puisque pour la même longueur de parcours, on passe plus de temps et donc on enregistre plus de points...)

Si je dis pas de conneries, la cadence de rafraîchissement des capteurs grand public est 1 seconde (fréquence du cycle NMEA)...IL est logique que le tracé enregistré soit plus juste lorsqu'on va lentement (puisque pour la même longueur de parcours, on passe plus de temps et donc on enregistre plus de points...)

Plus de points donc plus de bruit dans les mesures non? Sachant qu'a chaque enregistrement, tu as une précision de +/-5m, plus il y a de points, plus la probabilité d'accumulé des erreurs est grande, non?
Typiquement pour le D+, c'est l'accumulation des erreurs qui par exemple sans seuil, donne des D+ non nul sur du plat.

bon ça avance : je suis sur la piste d'un seuil fixé (pour le moment 5m) couplé ensuite à un lissage de bruit blanc par FFT (en supprimant toutes les harmoniques d'intensité "trop faible").
Travail à venir : fixer automatiquement ce "trop faible" en fonction de la "qualité" du signal (que je compte tester comme une formule (laquelle ?... à bidouiller) basée sur la différence de D+- signal brut - signal seuillé).

J'ai pour le moment 3 traces GPX très différentres : UTMB (bonne qualité), écotrail (80, bonne qualité), écotrail (80, mauvaise qualité : D+ brut de presque 7000m !!).
Si vous avez de quoi tester (genre les berges de l'Isère signalées plus haut, ou un truc problématique), merci de m'indiquer le lien !

Si vous avez de quoi tester (genre les berges de l'Isère signalées plus haut, ou un truc problématique), merci de m'indiquer le lien !

http://www.kikourou.net/entrainement/fi ... ?id=176711
http://www.kikourou.net/entrainement/fi ... ?id=187130

autre truc interessant, prendre plusieurs traces d'une même course et voir si ton algo donne la même chose pour tout les fichiers.
http://www.kikourou.net/parcours/traces-gps.php pour trouver des tracés de course
par exemple : http://www.kikourou.net/entrainement/fi ... ?id=147625
trouves-tu le même D+ pour chaque tour, vu l'inexactitude sur une portion du parcours ?

pour faire avancer la réflexion: comment trouver un D+ juste avec des instruments "faux"

photos prises en bord de mer méditerranée à 1 jour d'intervalle. Le GPS aurait du indiquer 2 m au pire... j'ai le choix entre +11 et -6: un écart de 17 m!

Dans les deux cas, le GPS était allumé depuis longtemps, donc bien calé et sans obstacle, il devait recevoir de nombreux satellites

P1030834.JPG (91.92 Kio) Consulté 4929 fois

P1030812.JPG (94.36 Kio) Consulté 4929 fois

si j'avais été au milieu de la campagne, je ne serais pas posé de question et j'aurais pris comme une certitude la valeur annoncée....


et autre élément: la traversée en bateau entre La londe les Maures et Porquerolle
48 minutes à monter descendre sur une mer houleuse. A l'arrivée, mon GPS m'indique "à chaud" un D+ de 70 m (de mémoire). Une fois passé dans Garmin connect, je retrouve D+=3m et D-=6 m
j'ai allumé mon GPS sur le pont du bateau, je suis allé en cabine de pilotage (+3m) et j'ai arrêté la mesure sur le quai (-6m par rapport à la cabine).
1/ J'en déduis que Garmin connect écrête correctement les valeurs de la montre
2/ si j'avais couru, j'aurais bien eu ces 70m de bosses dans les jambes...

@fulgurex : la prochaine fois, affiche la précision dans tes champs de données pour juger de la qualité du signal.
D'autre part, il faut faire la différence entre mesure instantané de l'altitude et calcul du D+. Les erreurs se compensent ( (-6)m + (+6)m = 0 m ).

Je radote mais avec Garmin Connect et si tu as utilisé la correction d'altitude, toutes les altitudes sont remplacés par celle d'une base de données style IGN. Ceci est impossible à faire en direct avec ton 310XT à moins d'avoir une mémoire interne de dingue.

J'ai une sortie Kayak de 12km dans les Calanques il y a quelques semaines avec mon 305. J'ai aussi quelques valeurs farfelues en instantanée mais un D+ négligeable avec ST+correction d'altitude et c'est normal.

Ce ne sont pas les instruments qui sont faux mais la manière dont ton 310 fait le calcul du D+ qui n'est pas optimal.

bon ça avance : je suis sur la piste d'un seuil fixé (pour le moment 5m) couplé ensuite à un lissage de bruit blanc par FFT (en supprimant toutes les harmoniques d'intensité "trop faible").
Travail à venir : fixer automatiquement ce "trop faible" en fonction de la "qualité" du signal (que je compte tester comme une formule (laquelle ?... à bidouiller) basée sur la différence de D+- signal brut - signal seuillé).

J'ai pour le moment 3 traces GPX très différentres : UTMB (bonne qualité), écotrail (80, bonne qualité), écotrail (80, mauvaise qualité : D+ brut de presque 7000m !!).
Si vous avez de quoi tester (genre les berges de l'Isère signalées plus haut, ou un truc problématique), merci de m'indiquer le lien !

Là, ça va être lourd en calcul! Et puis FFT suppose périodicité, donc parcours en boucle seulement. Même si c'est souvent le cas ce n'est pas généralisable.

Et puis FFT suppose périodicité, donc parcours en boucle seulement. Même si c'est souvent le cas ce n'est pas généralisable.

Pas sur de comprendre ton objection? FFT permet de séparer les fréquences de bruit de celles du signal, je ne vois pas où est la nécessité d'avoir un parcours en boucle pour cela.

@fulgurex : la prochaine fois, affiche la précision dans tes champs de données pour juger de la qualité du signal.

je suis d'accord avec tout ce que tu as dit.
le seul truc que je voulais faire remarquer, c'est qu'à postériori, on récupère un listing de points en 3D, sans pouvoir en connaitre la véracité, et qu'il faut faire avec ...
Aucun moyen de savoir combien de satellites ont été utilisés, ou si l'appareil a été perturbé...

Et puis FFT suppose périodicité, donc parcours en boucle seulement. Même si c'est souvent le cas ce n'est pas généralisable.

Pas sur de comprendre ton objection? FFT permet de séparer les fréquences de bruit de celles du signal, je ne vois pas où est la nécessité d'avoir un parcours en boucle pour cela.

Es tu sûr qu'il ne faut pas une certaine périodicité de ton signal ? Je suis pas un spécialiste de ces théories...

Imagine que tu fais le parcours une infinité de fois et là tu as un signal périodique.
Peut-être pas au niveau du rythme cependant.
Sérieusement, la transfo de Fourier discrète n'a pas besoin d'un signal périodique ; d'ailleurs la première chose que j'ai testée est que mon signal non modifié était retrouvé par transfo inverse.

Autre chose, ce n'est pas lourd en calcul (n*ln(n), s'il y a même 5000 points ça fait pas énorme). D'ailleurs sur mon portable c'est quasi-instantané, même en python.

Je progresse sur le seuil de suppression de bruit. Bien sûr rien n'est parfait, mais je cherche une solution qui soit satisfaisante en moyenne. Je vous tiens au jus.

@fulgurex : la prochaine fois, affiche la précision dans tes champs de données pour juger de la qualité du signal.

je suis d'accord avec tout ce que tu as dit.
le seul truc que je voulais faire remarquer, c'est qu'à postériori, on récupère un listing de points en 3D, sans pouvoir en connaitre la véracité, et qu'il faut faire avec ...
Aucun moyen de savoir combien de satellites ont été utilisés, ou si l'appareil a été perturbé...

100% d'accord! D'ailleurs je ne comprends pas pourquoi, du moins sur les Garmin Forerunner, l'utilisateur n'a pas le choix des variables d'output. Je préfère cent fois avoir l'historique de la précision plutôt que le cardio... Quid des autres GPS: Edge, Suunto, Polar...?
En cherchant ce qui cache derriére la précision qu'affiche un Garmin, j'ai trouvé ça (en bas de page)
http://www.kowoma.de/en/gps/accuracy.htm

salut,

Je fais un petit programme (on dira pour le plaisir...) qui calcule le cumul D+ d'une trace GPX.
J'ai pris ce que j'avais sous la main : l'UTMB, D+ 9500m.
Trace (puis kmz->kml->gpx) depuis le site officiel :
http://www.ultratrailmb.com/documents/P ... B-2011.kmz

Si je programme bêtement les cumuls, j'obtiens +10988m (et -11426m...).
Evidemment c'est pas ça pour le D+ (sans compter que Chamonix s'est affaissé entre temps), alors j'ai pensé lisser la liste des altitudes.
J'ai commencé par faire la moyenne simple du point et de ses deux voisins : +9707m.
J'ai modifié le truc en pondérant 1/4, 2/4, 1/4, résultat +9807m...
Alors j'ai lissé par bloc de 5 points (suivant une binômiale, pour les connaisseurs...) : 1/16, 4/16, 6/16, 4/16, 1/16. Ca me semblait cool comme pondération.
Et là je sors +9534m, ce qui semble bon.

Questions :
1) le seuil est-il à rajouter absolument en complément ?
2) y a-t-il un relatif consensus sur la bidouille optimale (en moyenne) ?
3) comment procèdent les nombreux sites/logiciels au niveau du lissage ?

Merci !

ft,
tu en sais déjà beaucoup mais tu trouveras peut être un complément ou un "protocole de test" pour tes algos dans ce fil de discussion La face cachée du calcul du dénivelé cumulé (D+)
Florent

En réfléchissant bien, je suis de l'avis de Flo que seuil + moyenne glissante (encore appelé lissage) suffit bien pour obtenir un D+ cohérent, encore mieux si on part d'un alti baro couplé au GPS. Je ne pense pas que la Transformée de Fourier apporte un plus. Encore faut il optimiser le seuil et la largeur de l'intervalle de lissage. Dommage que GARMIN ne réussisse pas à implémenter correctement ce calcul pourtant simple dans ses firmwares pour avoir un D+ fiable en live sur la 910 par exemple, et qu'il faille recourir à des programmes externes comme Flo a indiqué dans son topo.

pardon du lag, mais ça fait qqs temps que je ne me suis pas occupé de l'algo.

La FFT ne me semble pas fondamentale en effet, après qqs tests. Mais pas pour autant inintéressante ; il s'agit bien après tout de lisser un bruit blanc (je parle surtout pour un alti barométrique, restons sérieux !).
En revanche, ce qui est une piste que je vais explorer cet été (quand j'aurai du temps) c'est de faire en sorte que le lissage/seuillage soit automatisé en fonction du parcours GPS et non pas imposé d'emblée.
Le pricipe tel que je le sniffe : seuiller le parcours à 1m, 2m, 3m etc. puis observer les caractéristiques (à préciser) de la courbe obtenue pour la seuiller/lisser de manière optimale en moyenne.

est ce qu'on peut faire le lissage en temps réel ( dans le cas d'une application de tracking) ?
ou il existe un autre moyen de corriger les erreurs ?