Cartographier les liens et les idées? [fermé]

44

J'utilise OpenStreetMap et son réseau routier vectoriel et j'aimerais implémenter un algorithme de matcher de carte.

Actuellement, je suis en mesure, pour chaque position GPS, de récupérer le segment de route le plus proche et de calculer la projection de cette position sur ce segment, comme sur cette image (la goupille rouge correspond à la position GPS pure, position cartographiée):

entrez la description de l'image ici

Cependant, en raison du manque de précision du GPS, la position mappée passe parfois d’un segment à l’autre et peut parfois générer une position mappée incohérente.

Mon algorithme actuel est très basique: à partir de la position GPS pure, je récupère le segment le plus proche et décide que la position correspondante mappée correspond à celle-ci. Je sais que cela peut être vraiment amélioré.

J'imagine que la prise en compte de la direction du véhicule améliorera l'appariement des cartes, mais connaissez-vous une autre approche qui me permettrait d'améliorer mon outil de correspondance?

Je cherche un lien, et / ou un logiciel open source?

Yonel
la source
4
vous pouvez ajouter un cercle - Google utilise la réception cellulaire et crée un cercle bleu clair pour indiquer votre position approximative. Votre application a l'air bien, bon travail. Si vous avez les données vectorielles, vous pouvez accrocher la ligne la plus proche de votre point GPS - voir l'article de Paul Ramsey blog.cleverelephant.ca/2008/04/snapping-points-in-postgis.html
Mapperz
4
Le mot clé que vous recherchez est "Correspondance cartographique". Grand sujet.
Uffe Kousgaard
1
Uffe a raison, correspondance de carte. Vérifiez ce document pour quelques approches: cens.ucla.edu/~mhr/cs219/maps/white00.pdf
lexicore
Merci! lexicore, le papier est envoyé à mon imprimante au fur et à mesure que je tape ceci. Il est temps d'avoir un aperçu. Merci pour le lien.
scrrr
J'améliorerais l'algorithme en essayant également de se caler sur la route, plutôt que sur les sommets.
Devdatta Tengshe

Réponses:

11

La projection de points sur la ligne, comme vous le faites déjà, est possible directement dans PostGIS. J'ai écrit il y a quelque temps, ici

Mais pour résoudre votre problème lorsque les points sont plus proches du mauvais segment que du bon segment, cela pourrait être une approche possible.

  1. Construire une ligne de points
  2. Essayez les solutions suggérées dans Algorithmes pour faire correspondre les segments à la totalité de la ligne au lieu de point à point.
Nicklas Avén
la source
Merci pour votre réponse. La projection est OK: je le fais déjà (pas via ST_Closest car ce n’est pas disponible dans spatialite que j’utilise mais c’est correct). Je viens également de regarder la question que vous avez mentionnée et d’apprendre l’existence de cette "distance de Hausdorff" qui peut être intéressante à regarder.
Yonel
10

Après avoir lu votre question et les différentes réponses, je me suis intéressé à ce problème. Après avoir lu un peu les algorithmes de correspondance de carte, j'ai compris ce qui suit:

  • Pour faire correspondre l’emplacement GPS à la route, vous avez besoin des données routières réelles au format vectoriel.
  • Cela vous aidera si vous avez des poids différents pour différentes routes. Ainsi, les chances d'un point correspondant à une autoroute seront plus élevées, puis à égaler une ligne de côté.
  • Vous devez prendre l'historique et la vitesse de lecture du GPS. Par exemple, si le point GPS correspond à la voie latérale depuis longtemps, vous devez en tenir compte, et non pas le faire correspondre directement à la route. -L'appariement réel est fait en utilisant une variété de techniques statistiques.

Pour plus de lecture, je suggère ce qui suit:

Devdatta Tengshe
la source
Oui, je lisais aussi et j'ai commencé à jouer avec la mise en œuvre d'un algorithme simple que je peux développer. Jusqu'à présent, j'ai téléchargé certaines données d'OSM et je joue avec la meilleure façon de les stocker (et de les accéder) à mes fins. C'est un sujet intéressant je pense. :) Je mettrai à jour cette question une fois que quelque chose fonctionnera. Merci également pour les liens!
scrrr
Je ferais attention à utiliser des poids "Ainsi, les chances d'un point correspondant à une autoroute seront plus élevées, puis à égaler une ligne de côté." ... Cela dépend des données d'entrée et peut très mal se passer.
underdark
@ Devdatta, je reçois un 404 sur le deuxième lien. Au lieu de me contenter de le modifier, avez-vous un autre lien?
Chau
Je n'ai pas de lien d'accès gratuit à cet article. Mais si vous êtes dans une configuration académique. L'article devrait être disponible après une recherche rapide
Devdatta Tengshe
@Chau: J'ai trouvé le fichier PDF à l'
adresse suivante
7

Répondre à ma propre question!

1- Un joli fichier .pdf que je viens de trouver sur ce sujet:

http://safari.ce.sharif.edu/file/2011-06-06/259/2009_An%20off-line%20map-matching%20algorithm%20for%20incomplete%20map%20databases.pdf

qui renvoie également à une implémentation open source C ++ du matcher de carte décrit dans le document: http://eden.dei.uc.pt/~camara/files/mgemma.zip
(celui-ci est un matcher de carte hors ligne, à ma connaissance, qu’il calcule les positions appariées sur la carte avec le chemin TOUT en entrée et ne peut le faire à la volée pour chaque position).

2- Ensuite, je viens de lire celui-ci en profondeur et il est vraiment bon à mon avis: https://dspace.lboro.ac.uk/dspace-jspui/bitstream/2134/4860/1/velaga.pdf "Développement un algorithme topologique de correspondance topologique basé sur le poids amélioré pour les systèmes de transport intelligents "
L'algorithme est clairement expliqué et des valeurs de réglage du poids sont également fournies dans le document.

Yonel
la source
4

Il existe de nombreux travaux sur l'appariement de cartes. Voir le présent document pour un bref aperçu de certains travaux assez récents (antérieurs à 2007). Plus récemment, les approches basées sur les modèles de Markov cachés semblent assez bien fonctionner dans des circonstances normales. Par exemple, consultez ce document de 2009. L’idée et le modèle sont assez simples et ne devraient pas vous donner trop de mal à mettre en œuvre même si vous n'êtes pas familier avec les HMM (dans ce cas, ne paniquez pas, il y a de tutoriels et introductions en ligne)

Entaille
la source
1
Je viens de me rendre compte que le projet Barefoot mentionné dans ma réponse est basé sur le document que @Nick recommande.
Nik
4

La méthode est aussi appelée "fusion de vecteur". Il existe une page Wiki dédiée ( http://wiki.openstreetmap.org/wiki/Conflation ) qui donne un aperçu général et répertorie les packages logiciels (Open Source) permettant d'effectuer la conflation de vecteurs routiers du type "JOSM conflation plugin", "Fusion de Potlatch 2 tool "," RoadMatcher "(pour OpenJUMP) et d’autres.

markusN
la source
1
J'ai toujours pensé que la fusion est quelque chose que vous faites avec deux couches de lignes au lieu de faire correspondre des points à des lignes. Est-ce vraiment la même chose?
underdark
4

Pour les algorithmes de correspondance de carte, cela dépend si vous avez besoin d'un traitement en temps réel ou hors ligne. Dans le dernier cas, les algues à la pointe de la technologie peuvent traiter environ 1 000 points par seconde. La mémoire requise dépend bien sûr de la couverture. Nous avons réussi à réduire le réseau routier OSM de la planète sur environ 16 Gb à cette fin.

En outre, vous devez distinguer la correspondance de carte de l' inférence de chemin : il s'agit de deux processus distincts selon que vous disposez de données haute ou basse fréquence. Lorsque vous avez relativement peu de points (par exemple, 1 donnée par kilomètre dans un contexte urbain), il s'agit d'une inférence de chemin car il est généralement nécessaire de supposer que le périphérique est en déplacement. L'inférence de chemin est généralement plus difficile, mais le problème avec les appareils modernes / le prix d'acquisition des données devient moins problématique.

Vous pouvez vérifier dans mon profil une API qui effectue la correspondance de carte directement sur OSM: elle utilise la correspondance topologique et fonctionne bien avec les données de voiture flottante, par exemple.

Fabrice Marchal
la source
Pouvez-vous développer les algorithmes que vous utilisez? Et comment la réduction de la taille du réseau routier aide-t-elle?
Devdatta Tengshe
Moins de couverture = réseau plus petit à garder en mémoire. Cela accélère un peu le calcul. Références: trb.metapress.com/content/p31485vw72645686
Fabrice Marchal
3

Strava Slide décrit comment les données cumulées sur les traces d'un réseau routier peuvent se comporter comme des "vallées" et comment l'itinéraire proposé "se mettrait en place" comme s'il s'agissait d'une chaîne de perles.

Heltonbiker
la source
2

Après avoir testé la plupart des frameworks mentionnés précédemment, j'ai trouvé Barefoot et je le recommande vraiment. Il utilise des modèles de markov cachés comme une approche probabiliste d'appariement de carte (les détails dans leur document "Mettre la voiture sur la carte" ) et est implémenté en Java. Il est open-source et développé activement par le département CarIT de BMW.

nik
la source
2

Le sujet est appelé correspondance de carte. Mais en tant que première très bonne approximation, il est probablement suffisant de rechercher les points les plus proches pour chaque point GPS (sans qu'aucune correction ne devine le bon chemin).

Mon projet Open Source appelé graphhopper ne fonctionne pas pour iOS ( mise à jour : il fonctionne désormais également sur iOS), pas plus qu’une application Android entièrement fonctionnelle pour ce que vous voulez. Mais vous pouvez utiliser la version du serveur pour créer une application iOS ou utiliser la démo Android hors ligne comme point de départ. J'ai publié l'algorithme de correspondance de carte ici , un prototype approximatif mais qui fonctionne étonnamment bien.

Karussell
la source
1

Essayez d’acquérir de bonnes données de test. Utilisez un GPS d’enregistrement de trace plus précis, en plus des points d’enregistrement sur votre appareil cible. Ceci identifiera les erreurs dans le GPS et dans les données OSM sous-jacentes. La connaissance de seuils sensibles facilitera grandement la conception de l'algorithme.

Matthew Snape
la source
1

Si vous pouvez obtenir des données sur les routes pour votre région, vous pouvez être intéressé par la capture automatique en bloc avec FOSS

GRASS peut vous aider, que vous souhaitiez tracer des données en temps réel ou que vous envisagiez d'effectuer ultérieurement un post-traitement sur votre PC.

Michal Zimmermann
la source
1

J'ai trouvé une API capable de faire le travail sans avoir à développer immédiatement sa propre solution.

Ils utilisent les données OSM pour faire la correspondance cartographique. Ils ont également une page de démonstration qui permet le téléchargement de fichiers GPX pour voir si cela peut fonctionner pour vous.

Arthur McFlint
la source
-1

Vous n'avez pas nécessairement besoin d'améliorer la qualité de vos données. L'utilisation d'un algorithme topologique avec un réseau routier en mémoire améliorera considérablement votre correspondance. Vérifiez les références: http://trb.metapress.com/content/p31485vw72645686

Fabrice Marchal
la source