Source : Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS ‘09), Seattle, 4-6 novembre 2009, p. 336-343 · DOI 10.1145/1653771.1653818 (non imprimé dans le PDF, repris du corpus) · Microsoft Research · accès OPEN · PDF Newson2009-HMMMapMatching.pdf, sha256 8e75b8f176bba45f…, 8 pages Lu le : 2026-11-02. LECTURE COMPLÈTE (texte extrait en entier ; pages 4 à 7 relues dans le PDF pour les équations et les figures 4 à 8). Les valeurs lisibles seulement sur les barres des figures 7 et 8 ne sont pas reprises. Statut summarized. Thème : mobility · map-matching par HMM Métadonnées vérifiées dans le PDF : auteurs (Paul Newson, John Krumm), année 2009 et titre conformes au corpus. Le DOI n’est pas imprimé dans le PDF (seul l’ISBN 978-1-60558-6496/09/11 l’est) : non vérifiable ici.

Contexte et question

Le map-matching associe des positions GPS horodatées à un graphe routier. Apparier chaque point à la route la plus proche échoue dès que le bruit est notable : les 2e et 3e points de la Fig. 1 seraient mal appariés, et des erreurs groupées apparaissent en canyon urbain (§2). Les approches purement géométriques (White et al., Greenfeld, Fréchet de Brakatsoulas et al.) sont jugées sensibles au bruit et à l’échantillonnage. Les auteurs proposent un HMM « de principe » et mesurent comment il se dégrade quand la cadence baisse et quand le bruit augmente.

Méthode

• États du HMM : les N_r segments routiers r_i (entre intersections). Observations : les mesures z_t (§2).
• Émission (éq. 1, §3.1) : p(z_t | r_i) = 1/(√(2π) σ_z) · exp(−0,5 (‖z_t − x_t,i‖_grand cercle / σ_z)²), où x_t,i est le point du segment le plus proche de z_t. Bruit supposé gaussien centré ; les auteurs notent que le GPS n’est pas strictement gaussien mais que l’hypothèse « proved effective » (p. 339).
• Transition (éq. 2 et 3, §3.1) : p(d_t) = (1/β) exp(−d_t/β), avec d_t = | ‖z_t − z_t+1‖_grand cercle − ‖x_t,i* − x_t+1,j*‖_route |. La distance de route est celle d’un calculateur d’itinéraire au plus court. L’exponentielle est ajustée sur l’histogramme des écarts entre routes vérité-terrain (Fig. 5).
• État initial : π_i = p(z_1 | r_i), pas une loi uniforme (§3.1).
• Candidats : toute probabilité d’émission est mise à zéro au-delà de 200 m de z_t (§3.1, §4.2).
• Chemin optimal : Viterbi, qui maximise le produit des probabilités d’émission et de transition (§3.3). L’algorithme est présenté en traitement par lots ; une version à fenêtre glissante pour le temps réel est évoquée comme conjecture (§3).
• Estimation des paramètres (§5.2), directement sur les données et la vérité terrain, sans optimisation de performance (laissée à de futurs travaux) :
  • σ_z = 1,4826 · médiane_t(‖z_t − x_t,i*‖_grand cercle) (éq. 5), estimateur MAD ;
  • β = (1/ln 2) · médiane_t(| ‖z_t − z_t+1‖_grand cercle − ‖x_t,i* − x_t+1,j*‖_route |) (éq. 6), estimateur de Gather et Schultze.
• Prétraitement (§4.1) : on retire les points situés à moins de 2σ_z du dernier point conservé.
• Ruptures du treillis (§4.2), les transitions concernées reçoivent une probabilité nulle :
  • aucun candidat à moins de 200 m ;
  • recherche de route abandonnée quand la distance de route dépasse la distance grand cercle de 2000 m ou plus ;
  • vitesse implicite supérieure à 50 m/s (180 km/h), ou supérieure à trois fois la limite affichée.
• Réparation des ruptures (§4.2) : on retire les points z_t et z_t+1 de part et d’autre de la rupture, puis on élargit tant qu’elle n’est pas résorbée ; au-delà de 180 s, la trace est coupée en trajets traités séparément. Si la période d’échantillonnage d’origine dépasse 180 s, cette heuristique est omise.
• Pas de cap (heading) dans l’émission, contrairement à Hummel : les auteurs supposent l’absence de boussole et jugent le cap dérivé du GPS peu fiable aux longs intervalles (§3.3). Les transitions portent sur la distance de route et non sur le temps de parcours (Krumm et al. 2007), jugé plus sensible au trafic (§3.3).

Données

• Un trajet de test unique, région de Seattle : 7531 points à 1 Hz, environ 80 km (50 miles), environ 2 h (§5, Fig. 2).
• Récepteur grand public, puce SiRF Star III, WAAS activé (§5).
• Vérité terrain : appariement manuel, corrigé dans un outil graphique à partir de la sortie de l’algorithme (§5). Les auteurs précisent que seul le chemin est connu, pas la position exacte sur la route.
• Dégradations simulées (§5.1) : périodes de 2, 5, 10, 20, 30, 45, 60, 90, 120, 180, 240, 300, 360, 420, 480, 540 et 600 s en plus de 1 s ; bruit gaussien additionnel d’écart type 10, 15, 20, 30, 40, 50, 75 et 100 m, et un cas sans bruit ajouté. Les variances s’additionnent (éq. 4), ce qui permet de tenir compte du bruit déjà présent.
• Les données, la vérité terrain et le réseau sont publiés par les auteurs (§5.3, URL en note 1 p. 341).

Résultats chiffrés

• Métrique d’erreur : somme des longueurs de route ajoutées à tort (d+) et retranchées (d−), divisée par la longueur de la route correcte d0 (Fig. 6). Les auteurs la préfèrent à l’exactitude par position ou par segment, ambiguës aux intersections.
• Fig. 7 (erreur selon la période) : erreur très faible jusqu’à 30 s, puis croissante ; aux périodes de 300 à 600 s, les barres se lisent entre environ 0,4 et 0,9 (maximum vers 540 s), sans valeur imprimée.
• Fig. 8 (surface période × bruit) : l’algorithme est plus sensible au bruit à 1 s qu’aux longues périodes. Les auteurs l’expliquent par des points fréquents et bruités qui « pull the route rather violently in different directions » (p. 342).
• Aucune comparaison à un autre algorithme n’est rapportée : l’article ne mesure que l’algorithme proposé.

Limites déclarées par les auteurs

• Un seul trajet, un seul récepteur ; vérité terrain obtenue en corrigeant la sortie de l’algorithme lui-même (§5).
• Gaussienne imparfaite pour le GPS (§3.1).
• σ_z et β estimés sur les données et non optimisés (§5.2).
• Traitement par lots ; la version temps réel n’est qu’une conjecture (§3).
• Des ruptures du treillis existent (tunnel, canyon urbain, route absente de la carte) et sont traitées par suppression de points (§4.2).

Ce que ça change pour Teleforge (interprétation, hors de l’article)

• Référence de départ pour tout comparatif de map-matching : les formules des éq. 1 à 3, 5 et 6 et les seuils (200 m, 2σ_z, 2000 m, 50 m/s, 180 s) définissent une implémentation de référence à reproduire telle quelle avant toute variante.
• Les paramètres sont estimés sur un trajet vérité terrain propre, à 1 Hz et à σ_z de 4,07 m. Pour un boîtier à cadence plus faible ou plus bruité, σ_z et β sont à réestimer, pas à reprendre.
• La métrique d’erreur par fraction de route erronée (Fig. 6) est reprenable pour évaluer nos appariements ; elle ne demande pas de position exacte.
• Le résultat « 0,11 % à 30 s » vient d’un seul trajet urbain de Seattle (§1) : à ne pas généraliser à nos réseaux sans mesure propre.
• Le jeu de données publié est utilisable comme banc de non-régression d’une implémentation.