Passende Links und Ideen auf der Karte? [geschlossen]

Ich verwende OpenStreetMap und sein vektorielles Straßennetz und möchte einen Map Matcher-Algorithmus implementieren.

Derzeit kann ich für jede GPS - Position das nächste Straßensegment abrufen und die Projektion dieser Position auf dieses Segment berechnen, wie auf diesem Bild (roter Stift ist die reine GPS - Position, blau das abgebildete Segment und grün das zugeordnete Position):

Aufgrund der mangelnden Genauigkeit des GPS springt die zugeordnete Position jedoch manchmal von Segment zu Segment und kann von Zeit zu Zeit eine inkonsistente zugeordnete Position liefern.

Mein aktueller Algorithmus ist sehr einfach: Aus der reinen GPS-Position erhalte ich das nächstgelegene Segment und entscheide, dass die zugeordnete übereinstimmende Position auf diesem liegt. Ich weiß, dass dies wirklich verbessert werden kann.

Ich kann mir vorstellen, dass die Berücksichtigung der Fahrzeugrichtung die Kartenanpassung verbessert. Kennen Sie einen anderen Ansatz, mit dem ich meine Kartenanpassung verbessern kann?

Ich suche einen Link und / oder Open Source Software?

Das Projizieren von Punkten auf die Linie, wie Sie es bereits tun, ist direkt in PostGIS möglich. Ich habe darüber vor einiger Zeit hier geschrieben

Aber um Ihr Problem zu lösen, wenn die Punkte näher am falschen Segment als am richtigen Segment liegen, könnte dies ein möglicher Ansatz sein.

1. Bilde eine Linienfolge der Punkte
2. Probieren Sie die in Algorithmen vorgeschlagenen Lösungen für die Segmentübereinstimmung aus , um die gesamte Linie anstatt nur Punkt für Punkt abzugleichen

Nachdem ich Ihre Frage und die verschiedenen Antworten gelesen hatte, interessierte ich mich für dieses Problem. Nachdem ich ein wenig über Map-Matching-Algorithmen gelesen habe, habe ich Folgendes verstanden:

• Um den GPS-Standort an die Straße anzupassen, benötigen Sie die tatsächlichen Straßendaten im Vektorformat
• Es hilft, wenn Sie unterschiedliche Gewichte für unterschiedliche Straßen haben. Die Wahrscheinlichkeit, dass ein Punkt mit einer Autobahn übereinstimmt, ist also höher als mit einer Seitenlinie.
• Sie müssen den Verlauf und die Geschwindigkeit des GPS-Lesens erfassen. Wenn zum Beispiel der GPS-Punkt seit langer Zeit mit der Fahrspur übereinstimmt, sollten Sie dies berücksichtigen und nicht direkt mit der Autobahn abstimmen. -Der tatsächliche Abgleich erfolgt mithilfe verschiedener statistischer Techniken.

Zur weiteren Lektüre schlage ich Folgendes vor:

• Kartenanpassung für GPS-Trajektorien mit niedriger Abtastrate
• Einige Kartenabgleichalgorithmen für persönliche Navigationsassistenten
• Eine dreistufige allgemeine Kartenanpassungsmethode in der GIS-Umgebung: Perspektive einer Reise- / Transportstudie

Beantwortung meiner eigenen Frage!

1- Ein nettes .pdf, das ich gerade zu diesem Thema gefunden habe:

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

Dies ist auch ein Link zu einer C ++ - Open-Source-Implementierung des Karten-Matchers , der im Dokument http://eden.dei.uc.pt/~camara/files/mgemma.zip beschrieben
ist dass es die mit der Karte übereinstimmenden Positionen mit dem GANZEN Pfad als Eingabe berechnet und dies nicht für jede Position im laufenden Betrieb tun kann).

2- Dann habe ich gerade diese gründlich gelesen und sie ist meiner Meinung nach wirklich gut: https://dspace.lboro.ac.uk/dspace-jspui/bitstream/2134/4860/1/velaga.pdf "Entwickeln ein erweiterter gewichtsbasierter topologischer MapMatching-Algorithmus für intelligente Verkehrssysteme "
Der Algorithmus wird klar erklärt und Gewichtseinstellungswerte werden ebenfalls in der Dokumentation angegeben.

Es gibt eine Menge Arbeit zum Map-Matching. In diesem Artikel finden Sie einen kurzen Überblick über einige relativ neue Arbeiten (vor 2007). In jüngerer Zeit scheinen Ansätze, die auf Hidden-Markov-Modellen basieren, unter normalen Umständen recht gut zu funktionieren. Schauen Sie sich zum Beispiel dieses Dokument aus dem Jahr 2009 an. Die Idee und das Modell sind recht einfach und sollten Ihnen auch dann keine Probleme bereiten, wenn Sie nicht mit HMMs vertraut sind (in diesem Fall keine Panik, es gibt viele) von Tutorials und Einführungen online)

Das Verfahren wird auch als "Vektorkonflation" bezeichnet. Es gibt eine spezielle Wiki-Seite ( http://wiki.openstreetmap.org/wiki/Conflation ), die einen allgemeinen Überblick bietet und Softwarepakete (Open Source) auflistet, mit denen Straßenvektorkonflikte wie "JOSM conflation plugin" und "Potlatch 2 merging" durchgeführt werden können tool "," RoadMatcher "(für OpenJUMP) und andere.

Bei Map-Matching-Algorithmen hängt es davon ab, ob Sie eine Echtzeit- oder eine Offline-Verarbeitung benötigen. Im letzteren Fall können hochmoderne Algen ~ 1000 Punkte pro Sekunde verarbeiten. Der Speicherbedarf hängt natürlich von der Abdeckung ab. Zu diesem Zweck haben wir es geschafft, das OSM-Straßennetz des Planeten auf ca. 16 GB zu komprimieren.

Außerdem müssen Sie die Kartenanpassung von der Pfadableitung unterscheiden : Dies sind zwei getrennte Prozesse, je nachdem, ob Sie Daten mit hoher oder niedriger Frequenz haben. Wenn Sie relativ wenige Punkte haben (z. B. 1 Daten pro Kilometer im städtischen Kontext), ist dies eine Pfadableitung, da normalerweise davon ausgegangen werden muss, wohin das Gerät fährt. Die Inferenz von Pfaden ist in der Regel schwieriger, wird jedoch mit modernen Geräten weniger problematisch / Preis für die Datenerfassung.

Sie können in meinem Profil nach einer API suchen, die den Kartenabgleich direkt in OSM ausführt: Sie verwendet den topologischen Abgleich und funktioniert beispielsweise gut mit Floating Car-Daten.

Strava Slide beschreibt, wie sich kumulierte Streckendaten über ein Straßennetz wie "Täler" verhalten können und wie die vorgeschlagene Route "an ihren Platz fallen" würde, als wäre es eine Perlenkette.

Nach dem Testen der meisten zuvor genannten Frameworks habe ich Barefoot gefunden und kann es wirklich empfehlen. Es verwendet Hidden-Markov-Modelle als probabilistischen Map-Matching-Ansatz (Details in ihrem Artikel "Das Auto auf die Karte setzen" ) und ist in Java implementiert. Es ist Open Source und wird von der CarIT-Abteilung von BMW aktiv entwickelt.

Das Thema wird als Kartenanpassung bezeichnet. Aber als erste sehr gute Annäherung ist es wahrscheinlich gut genug, nur die nächsten Punkte für jeden GPS-Punkt nachzuschlagen (ohne dass Korrekturen den richtigen Weg erraten).

Mein Open Source-Projekt mit dem Namen graphhopper funktioniert nicht für iOS ( Update : jetzt auch für iOS) und es ist auch keine voll funktionsfähige Android-App für das, was Sie wollen. Sie können jedoch die Serverversion verwenden, um eine iOS-App zu erstellen, oder die Offline-Android-Demo als Start verwenden. Ich habe den Algorithmus map matching lösen hier , nur einen groben Prototyp aber funktioniert überraschend gut.

Versuchen Sie, einige gute Testdaten zu erhalten. Verwenden Sie zusätzlich zum Aufzeichnen von Punkten auf Ihrem Zielgerät ein GPS mit höherer Genauigkeit für die Trackaufzeichnung. Dadurch werden Fehler im GPS und in den zugrunde liegenden OSM-Daten identifiziert. Das Erkennen vernünftiger Schwellenwerte erleichtert das Entwerfen des Algorithmus erheblich.

Wenn Sie Straßendaten für Ihre Region erhalten können, sind Sie möglicherweise am automatischen Bulk-Snapping mit FOSS interessiert

Abhängig davon, ob Sie Daten in Echtzeit plotten möchten oder eine spätere Nachbearbeitung auf Ihrem PC planen, kann GRASS hilfreich sein.

Ich habe eine API gefunden , die möglicherweise einfach funktioniert, ohne sofort eine eigene Lösung entwickeln zu müssen.

Sie verwenden OSM-Daten für den Kartenabgleich. Sie haben auch eine Demo-Seite , die das Hochladen von GPX-Dateien ermöglicht, um zu sehen, wie gut dies für Sie funktionieren könnte.

Sie müssen die Qualität Ihrer Daten nicht unbedingt verbessern. Die Verwendung eines topologischen Algorithmus mit einem speicherinternen Straßennetz verbessert Ihre Übereinstimmung erheblich. Suchen Sie nach Referenzen: http://trb.metapress.com/content/p31485vw72645686