-
Die
vorliegende Erfindung bezieht sich auf ein Verfahren zum Bestimmen
und Speichern einer nicht digitalisierten Straße.
-
Stand der Technik
-
Digitale
Karten bilden die Basis für sämtliche Navigationssysteme
und werden üblicherweise beispielsweise verwendet, um dem
Fahrzeuglenker zu einem erwünschten Ort zu führen
oder seine aktuelle Position anzuzeigen. Diese digitalen Karten
müssen bisher manuell um neugebaute Straßen erweitert werden.
Das bedeutet, dass üblicherweise der Nutzer nach einer
gewissen Zeit ein Update für die digitale Karte durchführen
muss.
-
Wird
ein solches Update nicht durchgeführt, ist eine neugebaute
Straße für den Algorithmus zur Berechnung einer
kürzesten oder schnellsten Route unbekannt und wird nicht
berücksichtigt, was zum Einen zu unnötig längeren
Fahrtzeiten, jedoch bei geänderten Straßenführungen
zum Anderen auch zu einer Verwirrung der Fahrzeuglenker durch sich
nicht deckende Anweisungen des Systems mit der wirklichen Infrastruktur
führen kann.
-
Eine
Verbesserung hierzu stellt das aus dem Stand der Technik bekannte
MapShare-Verfahren (http://www.connect.de/news/TomTom-Erfolg-mit-Map-Share_5061881.html)
dar, bei dem die Fahrzeuglenker einer Zentrale Unterschiede zwischen
einer digitalen Karte und der tatsächlichen Straßenstruktur
melden und diese dann in das digitale Kartensystem direkt eingepflegt
werden können. Eine manuelle Änderung der Karte
muss dabei aber immer noch erfolgen, einzig ändert sich
der Zeitpunkt, nämlich dass das Einpflegen zeitnaher erfolgt.
-
Offenbarung der Erfindung
-
Ausgehend
hiervon liegt der Erfindung die Aufgabe zugrunde, bei einem Verfahren
zum Bestimmen und Speichern einer nicht digitalisierten Straße der
eingangs genannten Art ohne manuelle Eingaben neue, befahrene Straßenstrecken
in einer digitalen Karte aufzunehmen.
-
Diese
Aufgabe wird durch die im Anspruch 1 angegebene Merkmalskombination
gelöst.
-
Gemäß der
vorliegenden Erfindung werden nun also während der Fahrt
des Fahrzeuges auf einer nicht digitalisierten Straße Ortungspunkte
aufgenommen. Mittels dieser Ortungspunkte wird ein Bereich eines
möglichen Straßenverlaufsbereichs bestimmt, dieser
gerastert und die einzelnen Raster mit Zustands- und/oder Übergangswahrscheinlichkeiten belegt.
Anhand des mit Wahrscheinlichkeiten belegten Rasters wird dann ein
wahrscheinlichster Straßenverlauf gefunden und dieser Straßenverlauf
in der digitalen Karte gespeichert.
-
Mit
einem solchen Verfahren ist es nun möglich, dass eine nicht
in der digitalen Karte enthaltene Straße, allein durch
das Befahren dieser, in eine digitale Karte aufgenommen wird.
-
Vorteilhafte
Ausgestaltungen der Erfindung sind in den Unteransprüchen
gekennzeichnet.
-
Gemäß einer
bevorzugten Ausführungsform der vorliegenden Erfindung
verläuft der mögliche Straßenverlaufsbereich
um die Ortungspunkte mit ihrem Unschärfebereich und unter
Berücksichtigung physikalisch möglicher Wege zwischen
zwei Ortungspunkten. Die Punkte werden immer mit einer gewissen
Unschärfe geortet. Diese einzelnen unscharfen Positionspunkte
werden zu einem zusammenhängenden Gebilde verbunden, das
nachfolgend als Schlauch bezeichnet werden soll. In diesem Schlauch
ist der mögliche Verlauf vom Start- zum Zielpunkt der neuen
Straße enthalten, die man abspeichern möchte.
-
Weiterhin
kann gemäß der bevorzugten Ausführungsform
mittels eines Fahrzeugmodells bestimmt werden, welche physikalisch
möglichen Wege zwischen zwei Ortungspunkten benutzt worden
sein können. Hier wird beispielsweise der maximale Lenkwinkel
oder die Beschleunigung berücksichtigt.
-
Zwei
aufeinander folgende unscharfe Punkte werden auf Basis der Bewegungsrichtung
eines solchen Fahrzeugmodells miteinander verbunden und damit eine
Fläche mit positiver Wahrscheinlichkeit und Bewegungsrichtung,
die sich aufgrund des Modells ergeben, definiert. Das Ergebnis ist
dann ein durchgehender Schlauch vom Start- zum Zielpunkt.
-
Dieser
Schlauch ist üblicherweise viel breiter als eine Straße,
da er die Ortungsungenauigkeit, sowie viele Annahmen und Annäherungen
aufweist.
-
Gemäß einer
weiteren bevorzugten Ausführungsform der vorliegenden Erfindung
erfolgt das Finden des wahrscheinlichsten Straßenverlaufs
mit Hilfe einer Markov-Kette. Eine Markov-Kette ist eine spezielle
Klasse von stochastischen Prozessen. Ziel ist es hierbei, Wahrscheinlichkeiten
für bestimmte mögliche Ereignisse anzugeben.
-
Ist
nun bei einem erfindungsgemäßen Verfahren ein
wahrscheinlicher Straßenverlauf gefunden worden, so wird
dieser vorzugsweise noch entdiskretisiert, das heißt, dass
die Strecke des Straßenverlaufs geglättet wird,
um einen realistischen Straßenverlauf zu erhalten. Hierfür
kann beispielsweise das aus dem Stand der Technik bekannte Network
Snakes verwendet werden.
-
Danach
kann dann das Abspeichern der neu ermittelten Straße vorzugsweise
mit Hilfe des Douglas-Peucker-Verfahrens erfolgen.
-
Das
Douglas-Peucker-Verfahren kann zu einer Punkteausdünnung
benutzt werden, um so eine durch Punkte gegebene Kurve zu vereinfachen.
Dies wird im Bereich der Navigation benutzt, um Speicherplatz zu
sparen, ohne dabei jedoch die Gestalt der Kurve zu verändern.
-
Weiterhin
ist es auch möglich, dass gemäß einer
bevorzugten Ausführungsform des erfindungsgemäßen
Verfahrens bei mehrmaligem Befahren der nicht digitalisierten Straße
die erhaltenen Werte abgeglichen werden und damit zu einer Verbesserung der
Lokalisierung der Straße herangezogen werden.
-
Ein
Ausführungsbeispiel der Erfindung wird nun nachstehend
anhand der Zeichnung näher erläutert. Es zeigen
hierbei
-
1 ein
Flussdiagramm gemäß einer bevorzugten Ausführungsform
des erfindungsgemäßen Verfahrens;
-
2 eine
schematische Darstellung der Ergebnisse einer Messung von Ortungspunkten
mit ihrem Unschärfebereich gemäß einer
bevorzugten Ausführungsform der vorliegenden Erfindung;
-
3 eine
schematische Darstellung einer Bestimmung eines Bereichs des möglichen
Straßenverlaufs gemäß einer bevorzugten
Ausführungsform;
-
4 eine
Darstellung einer Rasterung des möglichen Straßenverlaufsbereichs
gemäß einer bevorzugten Ausführungsform;
und
-
5 eine
Darstellung der möglichen Übergänge von
Raster zu raster gemäß Einer bevorzugten Ausführungsform
der Erfindung.
-
Die
in der Zeichnung dargestellte Ausführungsform des erfindungsgemäßen
Verfahrens besteht im Wesentlichen aus folgenden Schritten. In der 1 ist
der Verlauf des Verfahrens etwas genauer dargestellt. Im ersten
Schritt werden bei erkennen des Verlassens des bekannten Straßennetzes
damit begonnen, die sogenannten Off-Road-Koordinaten beziehungsweise
Ortungskoordinaten aufzuzeichnen 10. Diese aufgezeichneten
Ortungskoordinaten sind mit einer gewissen Unschärfe versehen.
-
Da
es sich bei einer Straße um ein stetiges Objekt handelt,
wird der Raum zwischen den Koordinaten durch Einbindung einer aus
einem Fahrzeugmodell abgeleiteten Fahrtrichtung ausgefüllt
und in einem schlauchartigen Gebilde mit einer Bewegungsrichtung
vom Start- zum Zielpunkt gespeichert 11. Innerhalb dieses
Schlauches befindet sich die neue, der digitalen Karte noch unbekannte
Straße. Durch das Fahrzeugmodell wird gemäß der
beschriebenen bevorzugten Ausführungsform bestimmt, welche
physikalischen Wege zwischen zwei Punkten möglich sind.
Hierbei wird beispielsweise der maximale Lenkwinkel oder die Beschleunigung
berücksichtigt.
-
Um
die Straße nun genauer zu bestimmen wird in einem weiteren
Schritt der Schlauch in ein Flächenraster übertragen 12.
Dabei bekommt jede Zelle des Rasters entsprechend der Verteilung
der gemessenen unscharfen Koordinaten und deren Verbindung mit einem
Fahrzeugmodell eine Gewichtung.
-
Auf
Basis dieser Zustandsgewichtung und der Bewegungsorientierung werden
Obergangswahrscheinlichkeiten berechnet 13, die in einem
weiteren Schritt 14 mit Hilfe einer Markov-Kette zu einer durchgehenden
Straße vom Start- zum Zielpunkt kontrastiert werden. Daran
schließt sich eine Entdiskretisierung des erhaltenen Weges
an 15 und dann wird die erhaltene Straße in der
digitalen Karte abgespeichert 16.
-
Falls
die Strecke öfters befahren wird, kann die Lokalisierung
der Straße noch optimiert werden 17. So könnte
beispielsweise der Start- und Zielpunkt noch genauer identifiziert
werden.
-
Mit
einem solchen erfindungsgemäßen Verfahren kann
eine noch nicht in der digitalen Karte enthaltene Straße
oder eine neue Straßenführung selbständig
in der Karte abgespeichert werden und steht damit für zukünftige
Routenberechnungen zur Verfügung.
-
Attribute
der neuen Straße, wie deren Name oder besondere Regeln,
wie beispielsweise eine Einbahnstraße, können
dann gegebenenfalls noch manuell hinzugefügt werden, womit
dann auch die neue Straße zur Zieleingabe verwendet werden
kann.
-
In
der 2 ist nun ein erster Schritt des erfindungsgemäßen
Verfahrens, das Aufzeichnen der Ortungskoordinaten 10 beim
Verlassen einer der digitalen Karte bekannten beziehungsweise Befahren einer
der digitalen Karte unbekannten Straße, dem sogenannten
Off-Road-Betrieb schematisch dargestellt.
-
Das
Aufzeichnen beginnt, wenn das Fahrzeug das gespeicherte Straßennetz
verlässt. Die erste Off-Road-Position wird als Startpunkt 20 gekennzeichnet.
Ab diesem Zeitpunkt wird jede Positionsmeldung in einem Speicher
abgelegt. Dabei sind die Positionen 21 mit einer gewissen
Unschärfe 22 versehen. Die Ortung ist dabei immer
mit einer gewissen Unschärfe versehen, die als Wahrscheinlichkeitsverteilung
dargestellt werden kann.
-
Die
Aufnahme und Abspeicherung der Orientierungskoordinaten 10 wird
so lange fortgesetzt, bis das Fahrzeug sich wieder gesichert auf
dem der digitalen Karte bekannten Straßennetz bewegt. Die letzte
Off-Road-Position wird dabei als Zielpunkt 23 markiert.
-
Start- 20 und
Zielpunkt 23 werden mit dem Punkt auf der zuletzt beziehungsweise
wieder erreichten befahrenen Straße der digitalen Karte
verbunden, die den kürzesten Abstand zum Start- 20 und
Zielpunkt 23 aufweist. Das Ergebnis ist eine Menge von
unscharfen Positionen mit einem Erwartungswert und einer Fläche
ebenfalls möglicher Koordinaten in einer Ebene.
-
In 3 ist
weiter gezeigt, wie diese einzelnen unscharfen Positionspunkte zu
einem zusammenhängenden Gebilde, eine Art Schlauch 30,
verbunden werden 11. Dieser Schlauch 30 beinhaltet den
Bereich, in dem die neue Straße zwischen Start- 20 und
Zielpunkt 23 enthalten ist, die man in der digitalen Karte
abspeichern möchte. Zwei aufeinander folgende unscharfe
Orientierungskoordinaten 22 werden anhand der möglichen
Bewegungsrichtung miteinander verbunden und dabei eine Fläche
mit positiver Wahrscheinlichkeit und Bewegungsrichtung, die sich
daraus ergeben, wie sich das Fahrzeug aufgrund eines Modells von
einer Position zur anderen bewegt haben könnte, definiert.
Ein solches Modell berücksichtigt beispielsweise einen
maximalen Lenkwinkel oder die Beschleunigung des Fahrzeuges.
-
Das
Ergebnis ist dann ein Schlauch 30 vom Start- 20 zum
Zielpunkt 23.
-
Hieran
schließt sich dann eine Diskretisierung 12 des
Schlauches 30 an. Hierzu wird, wie in 4 gezeigt,
ein Raster 40 über das Gebiet, das den Schlauch
enthält, gelegt und jede Zelle 41 des Rasters
enthält eine gleiche Übergangswahrscheinlichkeit
zu allen benachbarten Zellen, wo bei die Summe der Übergangswahrscheinlichkeiten 1 ergibt. Die
Wahrscheinlichkeit, dass die Zelle 41 in ihrem Zustand
verbleibt, wird Null gesetzt.
-
Gemäß der
gezeigten bevorzugten Ausführungsform wird im Folgenden
das Raster als quadratisches Raster beschreiben. Es wären
aber durchaus auch alle anderen Arten von Raster, wie beispielsweise
Rechteck- oder Dreieck-Raster möglich.
-
Gemäß dem
beschriebenen Raster gibt es von einer Zelle 41 acht mögliche Übergänge,
die alle eine Wahrscheinlichkeit von 1/8 erhalten. Zellen 41 am
Rand des Rasters erhalten entsprechend ihrer verringerten Nachbaranzahl
für die verbleibenden Übergänge eine
entsprechend höhere Wahrscheinlichkeit, so dass die Summe
der Wahrscheinlichkeiten wieder 1 ergibt.
-
Weiterhin
werden die Zellen 41 mit einer zweiten Wahrscheinlichkeit
belegt, dass die Straße durch diese Zelle 41 verläuft
und zwar entsprechend der Zustandswahrscheinlichkeit des Schlauchteils, der
die Zelle bedeckt.
-
Im
Folgenden erhält jede Zelle 41 eine Liste P mit
den möglichen sich anschließenden Zellen, die sich
aus der an der entsprechenden Stelle im Schlauch herrschenden Bewegungsrichtung
ergibt. Damit sind Übergänge von Zelle zu Zelle
nur in der Bewegungsrichtung möglich.
-
Zur
Veranschaulichung werden die Wahrscheinlichkeiten in 4 durch
unterschiedliche Musterungen dargestellt. Zellen mit der Wahrscheinlichkeit
0 sind weiß.
-
Mögliche Übergänge
von Zelle 41 zu Zelle 41 sind durch die Pfeile 50 in 5 dargestellt.
-
Hieran
schließt sich nun an, dass die vorher gleichmäßig
definierten Übergangswahrscheinlichkeiten auf Basis der
Zustandswahrscheinlichkeiten transformiert werden, so dass die Zellen
die Zustände für einen diskreten Markov-Prozess/Markov-Kette darstellen 14.
Eine Zelle 41 besitzt maximal drei Zellen, in die der Prozess
bzw. die Kette aufgrund der Bewegungsrichtung springen kann. Damit
gibt es maximal drei Übergangswahrscheinlichkeiten.
-
Zur
Berechnung der Übergangswahrscheinlichkeit von einer Zelle
zur anderen wird die relative Wahrscheinlichkeit der Zelle in Bezug
zur gesamten Wahrscheinlichkeit aller möglichen Zellen
berechnet.
-
Sind
nun w
1, w
2, w
3 die Zustandswahrscheinlichkeiten der benachbarten
möglichen Zielzustände einer Zelle v, so ergibt
sich die Wahrscheinlichkeit p
v,wi für
einen Übergang von v nach w
i durch
folgende Formel:
-
Diese
neuen Übergangswahrscheinlichkeiten ersetzen dann die alten
gleichverteilten. Alle anderen Übergangswahrscheinlichkeiten
werden auf 0 gesetzt. Auf diese Weise ergibt die Summe aller Übergangswahrscheinlichkeiten
wieder 1. Diese Gleichung ist zulässig, da es aufgrund
der Schlauchbildung keine isolierten Zellen mit positiver Zustandswahrscheinlichkeit
geben kann.
-
Die
Zustandswahrscheinlichkeit der Zelle v spielt bei der Berechnung
der Übergangswahrscheinlichkeiten keine Rolle. Für
Zellen am Rand des Rasters oder mit weniger möglichen Zielzellen,
wird die Übergangswahrscheinlichkeit mit einer entsprechend
geringeren Anzahl von Zielzellen berechnet. Das Ergebnis ist eine
Menge von Zuständen, die bis zu drei Übergangswahrscheinlichkeiten
aufweisen.
-
Die Übergangswahrscheinlichkeiten
der Zelle des Zielpunktes zu anderen Zellen werden auf 0 und die
Wahrscheinlichkeit, dass der Zustand in der Zelle verbleibt auf
1 gesetzt. Die übrigen Übergangswahrscheinlichkeiten
werden separat gespeichert. Das Ergebnis ist ein festgelegter Startzustand
und mit einer Markov-Kette zu erreichender Endzustand. Dieses Raster
mit den entsprechenden Übergangswahrscheinlichkeiten wird
im Speicher abgelegt.
-
Nun
schließt sich die Berechnung der Markov-Kette an, es wird
die Markov-Kette gesucht, die den Endzustand mit der höchsten
Wahrscheinlichkeit erreicht. Die Länge spielt dabei keine
Rolle. Dies soll sicherstellen, dass ein Pfad gefunden wird, der
im Wesentlichen Zellen hoher Wahrscheinlichkeit durchläuft.
-
Das
Verfahren ist endlich, da das Raster endlich ist und die Wahrscheinlichkeit
den Endzustand zu erreichen, 1 ist. Ebenso bildet die erhaltene Kette
eine durchgehende Strecke vom Start- zum Zielpunkt, was ein entscheidendes
Kriterium für das Abspeichern als neue Straße
ist.
-
Vor
dem Abspeichern in der digitalen Karte 16 wird die diskrete
Markov-Kette in eine entdiskretisierte Strecke transformiert 15.
Dies kann beispielsweise mit Network Snakes durchgeführt
werden, wobei der Verlauf der Strecke geglättet wird, um
einen realistischen Straßenverlauf zu erhalten.
-
Abschließend
werden mit dem bekannten Verfahren von Douglas-Peucker Stützpunkte
für de effiziente Abspeicherung der neuen Straße
herausgezogen und diese dann in die digitale Karte eingepflegt 16.
-
Die
Genauigkeit des abgespeicherten Straßenverlaufs kann durch
die Hinzunahme weiterer Ergebnisse beim mehrmaligen Befahren der
Strecke verbessert werden.
-
Hierbei
unterlaufen die neu ermittelten Koordinaten ebenfalls die oben beschriebenen
Prozesse, bis ein für die Berechnung der Markov-Kette vorbereitendes
Raster erstellt wurde, wobei immer das gleiche Raster verwendet
wird. Das Raster der alten Messung wurde in einem Speicher abgelegt.
Nun werden die beiden raster miteinander vermengt, indem die Übergangswahrscheinlichkeiten
pv,w und qv,w von
zwei Zellen v und w miteinander multipliziert und dann normiert
werden. Daraus folgt dann eine neue Übergangswahrscheinlichkeit
rv,w.
-
-
Aufgrund
von Messungenauigkeiten kann es hierbei vorkommen, dass unterschiedliche
Zellen als Startpunkte definiert werden, die allerdings räumlich eng
beieinander liegen. Das gleiche gilt für die Zielpunkte.
-
Das
für das Verfahren jedoch ein eindeutig bestimmter Start-
und Zielpunkt vorliegen muss, so wird dieser durch ein Verfahren
des minimalen quadratischen Abstandes definiert. Dieser Abstand
wird zu den beiden definierten Start- beziehungsweise Zielpunkten
gebildet und die entsprechende Zelle als Start- beziehungsweise
Zielzustand definiert. Hieran schließt sich dann das oben
beschriebene Verfahren an.
-
Durch
mehrmaliges Messen der gleichen Strecke können somit eventuelle
Messfehler kompensiert und die Genauigkeit der Straßenführung
erhöht werden.
-
ZITATE ENTHALTEN IN DER BESCHREIBUNG
-
Diese Liste
der vom Anmelder aufgeführten Dokumente wurde automatisiert
erzeugt und ist ausschließlich zur besseren Information
des Lesers aufgenommen. Die Liste ist nicht Bestandteil der deutschen
Patent- bzw. Gebrauchsmusteranmeldung. Das DPMA übernimmt
keinerlei Haftung für etwaige Fehler oder Auslassungen.
-
Zitierte Nicht-Patentliteratur
-
- - http://www.connect.de/news/TomTom-Erfolg-mit-Map-Share_5061881.html [0004]