Beschreibung

Titel

Verfahren und System zur Lokalisierung eines Streckenabschnittes in einer Karte

Die vorliegende Erfindung betrifft ein Verfahren und ein System zur Lokalisierung eines bestimmten Streckenabschnittes aus einer ersten digitalisierten Karte eines Straßennetzes in einer zweiten digitalisierten Karte des Straßennetzes.

Die Verbesserung der Verkehrslage wird seit Jahren durch öffentliche Verkehrsbeeinflussungen in Form von Schilderbrücken und Wechselwegweisern angestrebt. Sie sind üblicherweise auf wenige Alternativrouten zu einer ebenfalls geringen Zahl von Zielen begrenzt. Neben dem individuellen Wunsch, schnellstmöglich an sein Ziel zu gelangen, ist es beispielsweise für die Kommunen von Interesse, Verkehrsströme so zu lenken, dass negative Auswirkungen so gering wie möglich bleiben. Hierbei ist der Wunsch nach einer individuell optimierten Route mit den

Zielsetzungen einer kollektiven Verkehrslenkung zusammenzuführen.

Ein Teilaspekt der vorstehenden Problematik ist die Beschreibung des Ortes von Hinweisen und Störungen, der auch als Location bezeichnet wird. Im allgemeinen Sprachgebrauch wird mit einer Location, zu deutsch einer örtlichkeit, ein Standort, also eine definierte Position in einem Straßennetz beschrieben. Location-based-services sind demnach Dienste, die den Standort des Benutzers mit einbeziehen. Dabei muss die Location nicht immer punktbasiert sein, wie der deutsche Begriff des Standortes impliziert. Eine Location kann somit auch im Netz ausgedehnt sein, beispielsweise ein bestimmter Straßenabschnitt.

Bei einer heutzutage üblichen dynamischen Navigation wird von einem Navigationssystem aufgrund empfangener Verkehrsdaten zu der aktuellen Verkehrslage die bereits berechnete Route überprüft und gegebenenfalls unter Berücksichtigung der veränderten Verkehrssituation erneut berechnet. Die Verkehrsdaten sind üblicherweise der Location bzw. einem bestimmten Streckenabschnitt des Straßennetzes zugeordnet, um eine Lokalisierung zu ermöglichen. Das Navigationssystem muss nun den bestimmten Streckenabschnitt in der ihm zur Verfügung stehenden Karte eindeutig lokalisieren, um die empfangene Verkehrsmeldung bei der Routenberechnung berücksichtigen zu können. Diese Lokalisierung wird auch mit Referenzierung bezeichnet.

Die Referenzierung einer Location soll nun genau diesen möglicherweise ausgedehnten Ort beschreiben, so dass er in einer fremden digitalisierten Karte eingepasst werden kann. Anders ausgedrückt handelt es sich dabei um ein Verfahren zur Beschreibung von Locations in einem Netz oder in Teilen eines Netzes mittels standardisierter Kodierungsvorschriften unabhängig von dessen speziellen Karteneigenschaften. Die

Karte ist eine digitale Interpretation der Realität. Der Vorgang der Interpretation ist nicht standardisiert, wird jedoch in ähnlicher Vorgehensweise durchgeführt. Von verbleibenden Unterschieden sollte das Verfahren weitgehend unabhängig bleiben.

Hierbei ist die Referenzierung einer Location nicht unbedingt neu. Die postalische

Adresse ist ein sehr altes Mittel der Referenzierung. Sie unterteilt sich in hoheitlich festgelegte Gebiete mit Nummern, bundesweit einheitlichen Ortsnamen und katasterlich festgelegte Straßennamen mit Hausnummern. Fehlt die Kenntnis über einen Eintrag, wenn beispielsweise eine Straße unbekannt ist, besteht nur eine sehr unzureichende Möglichkeit, die Referenz in der digitalisierten Karte wieder zu finden.

Bei der Georeferenzierung werden meist Koordinaten verwendet. Dabei werden Punkte zur Einpassung übereinander gelegt. Koordinaten und euklidische Abstände zeigen aber nicht die wirkliche Netzwerkentfernung zwischen verschiedenen Locations. So können geometrisch benachbarte Punkte durch natürliche Barrieren in dem Verkehrsnetz weit

voneinander entfernt sein. Eine geringe Verschiebung der Koordinaten zwischen Sender und Empfänger kann also große Fehler bei der Interpretation verursachen.

Als Grundlage für die Fahrzeugnavigation greifen die Navigationssysteme auf digitalisierte Karten des Straßennetzes zu. Diese Karten sind allerdings nicht standardisiert, so dass es bei Karten von unterschiedlichen Herstellern zu Abweichungen in der digitalisierten Karteninformation und zu Verschiebungen der Koordinaten kommen kann. Diese Unterschiede entstehen beispielsweise durch verschiedene Interpretationen der Realität, beispielsweise standardisierte Kurvenradien und Kreuzungsdarstellungen, sondern auch durch einen kontinuierlichen Entwicklungsprozess des Netzwerks über die

Zeit.

In verschiedenen Gemeinschaftsprojekten wurden europaweit Vorschläge zur Thematik der Referenzierung einer Location gemacht, die hier als Grundlage dienen sollen. Das Projekt AGORA hat beispielsweise eine Methode zur Encodierung von Referenzen einer

Location und spezifizierter Regeln aufgezeigt, die zu der gewünschten Unabhängigkeit der Referenzen der Location von der Karte führen sollen.

In der EP 1 122 518 Al wird ein Verfahren zur Decodierung von linienförmigen geografischen Objekten mit Hilfe einer Datenbank offenbart, die ein Verkehrswegenetz mit linienförmigen Objekten enthält. Es ist vorgesehen, dass jeweils eine Menge von Punkten eines zu decodierenden Objekts und der Objekte des Verkehrswegenetzes gebildet wird, dass für mehrere relative Lagen der Punktmengen zueinander für eine der Punktmengen die Zahl von Punkten ermittelt wird, welche innerhalb eines vorgegebenen Abstandes mindestens eines der Punkte liegen, und dass das zu decodierende Objekt in derjenigen relativen Lage, in der die Zahl am größten ist, durch Ausgabe des dann mit dem Objekt korrelierten Teils des Verkehrswegenetzes decodiert wird.

Ferner wird in der EP 1 225 552 Bl ein Verfahren zur Referenzierung einer Location in einem insgesamt geografischen Kontext offenbart, bei dem bezüglich eines von einem

Service-Provider bereitgestellten ersten Straßensegments zwischen zwei

aufeinanderfolgenden Drehpunkten, die dazwischen eine kleinste gewichtete Entfernung bereitstellen, jedem zweiten Straßensegment, das eine disjunkte Alternative zu dem ganzen ersten Straßensegment oder einem Teil davon ist, eine gewichtete Entfernung zugeordnet wird, die wesentlich größer ist als die gewichtete Entfernung des ganzen bzw. des Teils.

Diese bisher bekannten Verfahren wenden vorhandene Informationen in mehr oder weniger direkter Form an und sind daher besonders bei fehlender Information, beispielsweise ein fehlender Straßenabschnitt, fehleranfällig.

Vor diesem Hintergrund ist es die Aufgabe der vorliegenden Erfindung, eine Lokalisierung eines Streckenabschnittes in einer Karte zu verbessern und die Robustheit gegenüber Ungenauigkeiten im zu Grunde liegenden Kartenmaterial zu erhöhen. Hierbei soll die Effizienz in der Ausführung und bei dem Speicherverbrauch bereitgestellt werden.

Diese Aufgabe wird durch ein Verfahren mit den Merkmalen gemäß Anspruch 1 sowie durch ein System mit den Merkmalen des Anspruchs 13 gelöst.

Erfindungsgemäß ist bei einem Verfahren und einem System der eingangs beschriebenen

Art vorgesehen, dass der Streckenabschnitt als schwarz/weißes oder farbiges Straßenausschnittsbild aufgefasst wird, worin die Straßen durch unterscheidbare Grauoder Farbwerte erkennbar sind. In dem Straßenausschnittsbild werden stufige, harte Grauoder Farbübergänge in weiche Grau- oder Farbverläufe überführt und das weichgezeichnete Straßenausschnittsbild wird mit einer bestimmten Transformation transformiert. Ein zweites Straßenausschnittsbild wird in der zweiten Karte in einer angenommenen Nähe des bestimmten Streckenabschnittes festgelegt. Stufige, harte Grauoder Farbübergänge in dem zweiten Straßenausschnittsbild werden in weiche Grau- oder Farbverläufe überführt und das weichgezeichnete Straßenausschnittsbild wird mit der bestimmten Transformation transformiert. Abschließend werden die Transformations-

Koeffizienten miteinander verglichen, um aus einer Bewertung der Transformations-

Koeffizienten die örtliche Lage des bestimmten Streckenabschnittes in der zweiten Karte zu ermitteln.

Hierbei ist bei zwei miteinander kommunizierenden Systemen, die auf jeweils eine digitalisierte Karte zugreifen, nicht festgelegt, ob stets beide Systeme die Transformation für den Straßenausschnitt ihrer Karte durchführen oder ob eines der beiden Systeme für beide Kartenausschnitte die Transformation durchführt, um anschließend die Transformations-Koeffizienten bewertend zu vergleichen.

Das Straßennetz besteht aus im Wesentlichen linienförmigen Objekten, die in der digitalisierten Karte üblicherweise als Polygonzüge abgespeichert sind. Erfindungsgemäß wird diese linienartige Darstellung als punktweise aufgebautes Bild aufgefasst. In diesem Straßenausschnittsbild sind die Straßen von den dazwischen liegenden Freiflächen durch unterschiedliche Färbungen unterscheidbar, beispielsweise können die Straßen schwarz und die Freiflächen weiß dargestellt sein.

Diese bildliche Darstellung ist nun in einfacher Weise in eine Beschreibung mittels einer Matrix übertragbar, bei der die Zahlenwerte der einzelnen Matrixelemente einer bestimmten Farbe bzw. einem bestimmten Grau- oder Farbwert entsprechen. Somit steht eine Darstellung der Karteninformation zur Verfügung, die mittels geeigneter

Algorithmen modifizierbar und interpretierbar ist.

Durch das erfindungsgemäß vorgenommene Weichzeichnen wird die anschließend durchgeführte bestimmte Transformation gegenüber einer geringen, beispielsweise punktweisen Verschiebung des Straßenausschnittsbildes stabilisiert. Zusätzlich wird die

Auswirkung geringer Abweichungen in den beiden digitalisierten Karten des Straßennetzes reduziert.

In vorteilhafter Weise werden bei dem Weichzeichnen ausgehend von den Straßen die Grau- oder Farbwerte von Bildpunkten der Straßenumgebung punktweise dem Grau- oder

Farbwert der Straße angepasst. Alternativ werden bei dem Weichzeichnen ausgehend von

den Freiflächen die Grau- oder Farbwerte der Bildpunkte der Straßenumgebung punktweise dem Grau- oder Farbwert der Freiflächen angepasst. Bei einer Farbauswahl mit schwarzen Straßen und ursprünglich weißen Freiflächen, wird die Straßenumgebung in eine Graustufen- Abbildung umgewandelt.

Bevorzugt ist vorgesehen, dass bei dem Anpassen der Einfluss der Grau- oder Farbwerte mit einer definierten Abklingfunktion monoton abnimmt. Diese Abklingfunktion kann durch eine lineare, hyperbolische, exponentielle, polynomiale oder logarithmische Funktion oder eine Funktion als beliebige Kombination der vorstehend aufgezählten Funktionen sein.

Vorteilhaft ist vorgesehen, dass bei dem erfindungsgemäßen Verfahren Koeffizienten einer ortstreuen Transformation berechnet werden. Dadurch bleibt auch in dem transformierten Bild bzw. in den transformierten Daten die Ortsinformation erhalten. Befindet sich ein Streckenabschnitt in dem betrachteten Kartenausschnitt in einem oberen linken Bereich, so wird auch das transformierte Bild in dem oberen linken Bereich die diesen Streckenabschnitt betreffende Information enthalten.

Bevorzugt werden in einer erfindungsgemäßen Ausgestaltung des Verfahrens Wavelet- Koeffizienten einer Wavelet-Transformation berechnet. Besonders bevorzugt ist die Verwendung des Haar-Wavelets, das wie folgt definiert ist:

In vorteilhafter Weise werden bei dem Vergleichen der Transformations-Koeffizienten mehrere Matrizenvergleiche durchgeführt, bei denen jeweils eine Differenzmatrix berechnet wird und anschließend Matrixelemente gezählt werden, die betragsmäßig einen

vorbestimmten Grenzwert unterschreiten. Die Anzahl ist dann das Maß der Güte für die Bewertung und die Minima in der Differenzmatrix dienen zur Lokalisierung des Streckenabschnitts.

Alternativ werden bei dem Vergleichen der Transformations-Koeffizienten mehrere

Matrizenvergleiche durchgeführt, bei denen eine Differenzmatrix berechnet und anschließend die Norm der Differenzmatrix gebildet wird, welche zur Bewertung der Güte verwendet wird. Die Lokalisierung erfolgt wiederum anhand der Minima in der Differenzmatrix. Die Norm ist hier als eine Längenfunktion der Matrizen zu verstehen. Dabei sind mögliche Ausprägungen die Spektralnorm, die Unendlichnorm oder die

Einsnorm.

Bevorzugt werden die Transformations-Koeffizienten über mehrere Dekompositionsstufen berechnet und insbesondere bevorzugt wird die Lokalisierung mit einer höheren Dekompositionsstufe begonnen, wodurch eine Verkleinerung des

Suchradius auf niedrigeren Dekompositionsstufen möglich wird. Höhere Dekompositionsstufen zeichnen sich durch eine Reduktion der Datenmenge der Bildpunkte aus und bleiben beispielsweise durch die Ortstreue der verwendeten Wavelet- Funktion lokalisierbar trotz einer zunehmenden Unscharfe des Ortes. Dies kann schneller zu Ergebnissen aufgrund einer geringeren Anzahl an Berechnungsschritten führen.

In vorteilhafter Weise kann aus der Bewertung der Transformations-Koeffizienten zusätzlich ein Versatz, eine Verdrehung und/oder eine Verzerrung des bestimmten Streckenabschnittes in der zweiten Karte ermittelt werden kann. Dies führt zu einer größeren Robustheit gegenüber Abweichungen in den zur Verfügung stehenden digitalisierten Karten.

Nachfolgend wird das erfindungsgemäße Verfahren unter Bezug auf die beigefügten Zeichnungen beispielhaft näher erläutert, in denen:

Figur 1 - eine schematische Skizze zweier Systeme mit digitalisierten Karten zeigt, die miteinander zu vergleichen sind,

Figur 2 - einen Ausschnitt eines Straßennetzes zeigt,

Figur 3 - einen Ausschnitt eines Straßennetzes auf der Encoderseite zeigt, und

Figuren 4a-d - jeweils einen Ausschnitt eines Straßennetzes auf der

Decoderseite zeigen.

Figur 1 zeigt schematisch skizziert ein Sendersystem 1 mit einer in einem Datenspeicher

2 abgespeicherten digitalisierten Karte eines Straßennetzes. Ein bestimmter Streckenabschnitt bzw. Straßenausschnitt, gekennzeichnet durch das Bezugszeichen 3, wird in dem Sendersystem 1 mit einem geeigneten Verfahren für eine Datenübertragung kodiert. Die kodierte Karteninformation wird anschließend über eine übertragungsstrecke 4 an ein Empfängersystem 5 übertragen.

In einer zweiten digitalisierten Karte, die in einem Datenspeicher 6 des Empfängersystems 5 abgespeichert ist, soll ein dem Streckenabschnitt 3 entsprechende Streckenabschnitt 7 lokalisiert werden. Für den Vorgang der Kodierung und Dekodierung werden nur Geometriedaten der Straßen in den Straßenausschnitten 3 und 7 zur

Verfügung gestellt.

Der in der Figur 1 gezeigte Aufbau lässt prinzipiell zwei alternative Möglichkeiten für die Durchführung des erfindungsgemäßen Verfahrens zu. In einer der beiden Variationen wird auf der Encoderseite, also durch das Sendersystem 1, das dem Streckenabschnitt 3

entsprechende Straßenausschnittsbild weichgezeichnet und in eine Matrixform übertragen. Anschließend wird auf die Matrix die Wavelet-Transformation durchgeführt.

Die bei der Transformation entstehenden, mehreren Koeffizientenmatrizen werden über die übertragungsstrecke 4 auf die Decoderseite bzw. an das Empfängersystem 5 übertragen. Decoderseitig wird ebenfalls ein dem gesuchten Streckenabschnitt 7 möglicherweise entsprechendes Straßenausschnittsbild in gleicher Weise verarbeitet.

Bei der zweiten Variation führt die Encoderseite keine Transformation durch, sondern überträgt die geometrische Information des Streckenabschnittes. In diesem Fall wird auf der Decoderseite für beide Kartendarstellungen die Wavelet-Transformation durchgeführt. Bei der zweiten Variation kann die zu übertragende Datenmenge deutlich geringer ausfallen, als bei der ersten Variation mit der übertragung von mehreren Koeffizientenmatrizen. Nachteilig ist allerdings, dass der gesamte Berechnungsaufwand decoderseitig anfällt.

Anschließend werden in beiden Variationen die jeweiligen Koeffizientenmatrizen miteinander verglichen. Für mehrere mögliche Lagen des gesuchten Objektes zu dem Referenzobjekt wird eine Zahl ermittelt, die eine ähnlichkeit der Wavelet-transformierten Werte des Objektes zu denen des Referenzobjektes ermittelt. Das zu dekodierende Objekt wird in derjenigen Lage, in der die so ermittelte ähnlichkeit eine genügend große, definierte Güte erreicht hat, als wieder gefunden angesehen.

In der Figur 2 ist ein Ausschnitt 8 eines Straßennetzes 9 gezeigt. Die einzelnen Straßen 9 sind durch schwarze Linien dargestellt. Die Zwischenräume bzw. Freiflächen 10 zwischen den schwarz dargestellten Straßen 9 sind weiße Flächen. Aus der Figur 2 ersichtlich ist jeweils ein abrupter übergang von einer Freifläche 10 zu einer Straße 9 durch den Farbwechsel von Weiß auf Schwarz zu erkennen.

Erfindungsgemäß wird in einem ersten Schritt dieser übergang verschmiert bzw. der

Straßenverlauf weichgezeichnet. Dies führt dazu, dass die Straßen 9 weiterhin schwarz

bleiben während die Freiflächen 10 von den Straßen 9 ausgehend eine Farbgebung erhalten, die immer heller wird je weiter die nächste Straße 9 entfernt ist. Jedem Bildpunkt wird somit eine Farbe oder Graustufe zugeordnet. Der Kartenausschnitt 8 kann dabei als n x m-Matrix aufgefasst werden, bei der die jeweiligen Matrizenelemente einem Bildpunkt zugeordnet sind und der Zahlenwert dem Grau- oder Farbwert entspricht.

Auf die Matrix wird die Wavelet-Transformation mit der Haar-Funktion angewendet. Dadurch werden die entsprechenden Koeffizientenmatrizen der horizontalen, vertikalen und diagonalen Wavelet-Koeffizienten erhalten. Die Zahlenwerte dieser Koeffizientenmatrizen ergeben bei einer erneuten Darstellung mit Hilfe der den

Zahlenwerten entsprechenden Grau- oder Farbwerte eine Darstellung des Straßenausschnitts 8 jeweils als eine Gebirgslandschaft, bei der die Straßen den Bergkämmen entsprechen.

Die Wavelet-Transformation ergibt horizontale Wavelet-Koeffizienten, vertikale

Wavelet-Koeffizienten und diagonale Wavelet-Koeffizienten. Die Gebirgslandschaft bzw. das Höhenprofil der horizontalen Wavelet-Koeffizienten betonen den Anteil der horizontal verlaufenden Straßen, während die Information der vertikal verlaufenden Straßen nahezu verschwindet. Entsprechend andere Höhenprofile mit anderen Betonungen ergeben somit die Darstellungen der vertikalen bzw. der diagonalen Wavelet-

Koeffizienten.

In Figur 3 ist ein Kartenausschnitt 11 der Encoderseite dargestellt, der zum Teil dem Kartenausschnitt 8 aus Figur 2 entspricht. In der Figur 3 ist ein Bereich um einen Kreisverkehr 12 invertiert dargestellt, der als Location auf der Decoderseite wieder gefunden werden soll.

In den Figuren 4a bis d ist jeweils der wieder zu findende Kreisverkehr 12 der Figur 3 in vier unterschiedlichen Kartendarstellungen der Decoderseite gezeigt. In der Darstellung der Figur 4a stimmt der Kreisverkehr 13 vollständig mit dem invertierten Ausschnitt der

Figur 3 überein. Der Kartenausschnitt der Figur 4b lässt lediglich eine Zufahrtsstraße bei

dem Kreisverkehr 14 vermissen. In der Darstellung der Figur 4c ist eine der Zufahrtsstraßen des Kreisverkehrs 15 abweichend von dem Kreisverkehr 12 der Figur 3 dargestellt, während die Darstellung der Figur 4d bei dem Kreisverkehr 16 lediglich eine der Zufahrtsstraßen vorhanden ist und die übrigen fünf Zufahrtsstraßen vollständig fehlen.

Die Anwendung des erfindungsgemäßen Verfahrens führt dazu, dass selbstverständlich der Kartenausschnitt 4a als gesuchte Location erkannt wird. Aber auch die abweichenden Darstellungen der Figuren 4b und 4c werden ohne größere Schwierigkeiten als die gesuchte Location identifiziert.

Die Wahrscheinlichkeit die Location der Figur 3 als Bestandteil der Figur 4d wieder zu finden, hängt unter anderem davon ab, ob in der näheren Umgebung eine ähnliche Straßenform, beispielsweise ein weiterer Kreisverkehr, existiert. Die fehlende Aussagekraft lässt sich an der Tatsache erkennen, dass das Maximum sich weniger steil von den umliegenden Gebieten, aber auch in der Höhe in Bezug auf beliebige andere untersuchte Orte weniger markant abhebt. Es bleibt aber festzustellen, dass das erfindungsgemäße Verfahren ausreichend robust genug gegenüber Abweichungen der Kartendarstellungen ist, so dass die Straßenverläufe oder Kreisverkehre 14 bzw. 15 der Figuren 4b bzw. 4c ohne Probleme als der gesuchten Streckenabschnitt oder Kreisverkehr

13 aus der Figur 3 lokalisiert werden und bei fehlender Aussagesicherheit die ungenauere Aussage ebenfalls erkannt werden kann.