Passende Links und Ideen auf der Karte? [geschlossen]

43

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):

Bildbeschreibung hier eingeben

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?

yonel
quelle
4
Sie können einen Kreis hinzufügen. Google verwendet die Zellenrezeption und erstellt einen hellblauen Kreis, um Ihre ungefähre Position anzuzeigen. Deine App sieht gut aus, gute Arbeit. Wenn Sie die Vektordaten haben, können Sie von Ihrem GPS-Punkt aus auf die nächste Linie fangen
Mapperz
4
Das Schlüsselwort, das Sie suchen, ist Map Matching. Großes Thema.
Uffe Kousgaard
1
Uffe hat recht, Kartenübereinstimmung. In diesem Artikel finden
Sie
Vielen Dank! lexicore, das Papier wird während der Eingabe an meinen Drucker gesendet. Zeit, sich einen Überblick zu verschaffen. Vielen Dank für den Link.
Scrrr
Ich würde den Algorithmus verbessern, indem ich statt nur der Scheitelpunkte auch versuchen würde, an der tatsächlichen Straße zu rasten.
Devdatta Tengshe

Antworten:

11

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
Nicklas Avén
quelle
Danke für deine Antwort. Die Projektion ist in Ordnung: Ich mache es bereits (nicht über ST_Closest, weil es nicht in Spatialite verfügbar ist, das ich verwende, aber das ist in Ordnung). Ich habe mir auch nur die Frage angesehen, die Sie angesprochen haben, und über die Existenz dieser "Hausdorff-Distanz" erfahren, deren Betrachtung interessant sein könnte.
Yonel
10

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:

Devdatta Tengshe
quelle
Ja, ich habe auch gelesen und angefangen, mit der Implementierung eines einfachen Algorithmus zu spielen, den ich erweitern kann. Bisher habe ich einige Daten von OSM heruntergeladen und spiele damit, wie ich sie für meine Zwecke am besten speichern (und darauf zugreifen) kann. Es ist ein interessantes Thema, denke ich. :) Ich werde diese Frage aktualisieren, sobald ich etwas habe, das funktioniert. Danke auch für die Links!
Scrrr
Ich würde vorsichtig sein, wenn ich Gewichte benutze. "Die Wahrscheinlichkeit, dass ein Punkt mit einer Autobahn übereinstimmt, ist also höher als mit einer Seitenlinie." ... Das hängt von den Eingabedaten ab und kann sehr schief gehen.
Underdunkel
@ Devdatta, ich bekomme eine 404 auf den zweiten Link. Haben Sie einen alternativen Link, anstatt dass ich ihn einfach weg bearbeite?
Chau
Ich habe keinen kostenlosen Link zu diesem Artikel. Aber wenn Sie in einem akademischen Umfeld sind. Der Artikel sollte nach einer schnellen Suche verfügbar sein
Devdatta Tengshe
@ Chau: Ich fand das PDF unter: researchgate.net/profile/Alain_Kornhauser/publication/…
Devdatta Tengshe
7

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.

yonel
quelle
4

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)

Nick
quelle
1
Gerade ist mir klar geworden, dass das in meiner Antwort erwähnte Barefoot- Projekt auf dem von @Nick empfohlenen Papier basiert.
Nik
4

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.

markusN
quelle
1
Ich habe immer gedacht, dass man eine Konfluenz mit zwei Linienebenen macht, anstatt Punkte auf Linien abzugleichen. Ist es wirklich dasselbe?
Underdunkel
4

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.

Fabrice Marchal
quelle
Können Sie die von Ihnen verwendeten Algorithmen erweitern? Und wie hilft die Verkleinerung des Straßennetzes?
Devdatta Tengshe
Geringere Abdeckung = kleineres Netzwerk, das im Speicher verbleibt. Das beschleunigt die Berechnung etwas. Referenzen: trb.metapress.com/content/p31485vw72645686
Fabrice Marchal
3

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.

Heltonbiker
quelle
2

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.

nik
quelle
2

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.

Karussell
quelle
1

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.

Matthew Snape
quelle
1

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.

Michal Zimmermann
quelle
1

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.

Arthur McFlint
quelle
-1

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

Fabrice Marchal
quelle