Verfahren und Vorrichtung zur Erstellung einer fahrspurgenauen Straßenkarte Gebiet der Erfindung

Die vorliegende Erfindung betrifft allgemein die Erstellung von Straßenkarten. Insbesondere betrifft die vorliegende Erfindung ein Verfahren und eine

Datenverarbeitungsvorrichtung zur Erstellung einer digitalen fahrspurgenauen Straßenkarte.

Stand der Technik

Insbesondere im Hinblick auf ein automatisiertes und/oder autonomes Fahren von Fahrzeugen wurden in vergangener Zeit diverse Verfahren zur Erstellung digitaler Straßenkarten entwickelt.

In einer Arbeit von Uruwaragoda et al., 2013,„Generating Lane Level Road Data from Vehicle Trajectroies Using Kernel Density Estinnation", Proceedings of the 16th International I EEE Annual Conference on Intelligent Transportation Systems (ITSC 2013), 201, ist beispielsweise ein Verfahren zum Schätzen einer Anzahl und einer Breite von Fahrspuren auf Straßen offenbart. Dazu wird ausgehend von einer fahrbahngenauen Straßenkarte die Mittellinie der Straße in diskreten Abständen rechtwinkelig geschnitten. Zu jeder dieser Lotrechten werden die Schnittpunkte mit Trajektorien von Fahrzeugen auf der Straße berechnet und jeweils eine Kerndichteschätzung durchgeführt. Somit werden Stützstellen entlang der Straße erzeugt, welche Informationen über eine Spuranzahl und eine Spurbreite enthalten und abschließend verknüpft werden können.

In einer Arbeit von Schroedel et al.,„Mining GPS Traces for Map Refinement", Data Mining and Knowledge Discovery, 2004, 9, werden Informationen über eine Spuranzahl und eine Spurbreite ohne Kartenvorwissen abgeleitet, indem ein Algorithmus die Trajektorien von Fahrzeugen zunächst in Segmente unterteilt und die Mittellinie identifiziert. Entlang dieser Mittellinie werden lotrechte

Abstände zu den Trajektorien der Fahrzeuge mit Dichteschätzverfahren kategorisiert, um Aussagen über die Fahrspuren treffen zu können. In Betaille et al.,„Creating Enhanced Maps for Lane-Level Vehicle Navigation", I EEE Transaction on Intelligent Transportation System, 2010, 4, 2010, 10 ist ein modellbasierter Ansatz verfolgt, in welchem durch Klothoide beschriebene Modelle an gemessene Trajektoriendaten von Fahrzeugen angepasst werden.

Offenbarung der Erfindung

Mit Ausführungsformen der Erfindung können in vorteilhafter Weise ein verbessertes Verfahren zum Erstellen einer detaillierten und präzisen

fahrspurgenauen Straßenkarte sowie eine entsprechende

Datenverarbeitungsvorrichtung bereitgestellt werden.

Ein Aspekt der Erfindung betrifft ein Verfahren zur Erstellung und/oder

Generierung einer fahrspurgenauen Straßenkarte, insbesondere einer digitalen fahrspurgenauen Straßenkarte. Das Verfahren weist dabei die folgenden Schritte auf:

Bereitstellen einer digitalen fahrbahngenauen Straßenkarte zur

Beschreibung eines Straßenverlaufs wenigstens einer Straße;

- Bereitstellen eines Trajektoriendatensatzes, welcher eine Mehrzahl von

Trajektoriendaten von Verkehrsteilnehmern entlang der wenigstens einen Straße aufweist;

Identifizieren und/oder Ermitteln der wenigstens einen Straße unter Segmentieren, Aufteilen und/oder Einteilen der fahrbahngenauen

Straßenkarte in wenigstens ein Straßensegment;

Modellieren des Straßensegments in wenigstens einem Straßenmodell, wobei das Straßenmodell eine Mehrzahl von Parameter zur geometrischen und/oder topologischen Beschreibung von Fahrspuren der Straße aufweist; zufälliges Variieren und/oder Verändern, insbesondere mehrfaches zufälliges Variieren und/oder Verändern, von Parameterwerten zumindest eines Teils der Parameter des Straßenmodells durch zufälliges Auswählen einer Änderungsoperation des Straßenmodells zur Änderung von

Parameterwerten;

Zuordnen zumindest eines Teils der Trajektoriendaten des

Trajektoreindatensatzes zu dem Straßenmodell unter Ermitteln wenigstens eines Wahrscheinlichkeitswertes für das Straßenmodell, wobei der Wahrscheinlichkeitswert mit einer Güte und/oder Qualität einer Abbildung, Nachbildung und/oder Imitierung der Trajektoriendaten durch das

Straßenmodell korreliert;

Ermitteln, basierend auf dem ermittelten wenigstens einen

Wahrscheinlichkeitswert, von optimalen Parameterwerten zumindest eines Teils der Parameter des Straßenmodells; und

Erstellen einer fahrspurgenauen Straßenkarte basierend auf den optimalen Parameterwerten des Straßenmodells.

Die„digitale fahrbahngenaue Straßenkarte" kann hier und im Folgenden eine Straßenkarte bezeichnen, welche lediglich Informationen bezüglich eines Straßenverlaufs und/oder einer Fahrbahn enthält, jedoch keine Informationen bezüglich einzelner Fahrspuren auf der Fahrbahn. Beispielsweise kann die fahrbahngenaue Straßenkarte einen oder mehrere Knoten und Kanten aufweisen, wobei eine Kante zur Darstellung einer Straße und/oder eines Straßenabschnitts und ein Knoten zur Darstellung einer Kreuzung verwendet werden kann. Gleichsam kann die fahrbahngenaue einen Graphen mit Knoten und Kanten bezeichnen. Dabei können die Kanten durch Pfeile und die Knoten durch Punkte in dem Graphen und/oder der fahrbahngenauen Straßenkarte gegeben und/oder dargestellt sein.

Der Begriff„fahrspurgenaue Straßenkarte" kann eine digitale Straßenkarte und/oder einen Graphen bezeichnen, welcher Informationen bezüglich einzelner Fahrspuren aufweist. Die fahrspurgenaue Straßenkarte kann insbesondere Informationen bezüglich einer Geometrie einzelner Fahrspuren, wie etwa bezüglich einer Fahrspurbreite, einer Fahrspuranzahl, eines Abstandes zwischen Fahrspuren entgegengesetzter Fahrtrichtung und/oder einer Krümmung einer Straße und/oder eines Straßenabschnitts enthalten. Diese geometrischen Informationen können etwa in zumindest einem Teil der„Parameter zur geometrischen Beschreibung von Fahrspuren der Straße" berücksichtigt und/oder enthalten sein. Gleichsam können die„Parameter zur geometrischen Beschreibung" Parameter zur Beschreibung einer Anzahl von Fahrspuren, einer Breite einzelner Fahrspuren, einer Krümmung einer Straße bzw. einzelner Fahrspuren und/oder eines Abstandes zwischen Fahrspuren entgegengesetzter Fahrtrichtung aufweisen. Ferner kann die fahrspurgenaue Straßenkarte

Informationen bezüglich einer Topologie der Fahrspuren enthalten, wobei die Topologie einen Verbindungsweg, eine Verbindung und/oder eine Konnektivität zwischen einzelnen Fahrspuren beschreiben kann. Diese topologischen Informationen können etwa in zumindest einem Teil der„Parameter zur topologischen Beschreibung von Fahrspuren der Straße" berücksichtigt und/oder enthalten sein. Gleichsam können die„Parameter zur topologischen

Beschreibung von Fahrspuren der Straße" Parameter zur Beschreibung eines Verbindungswegs, einer Verbindung, einer Konnektivität zwischen einzelnen

Fahrspuren, eines Verschwindens einzelner Fahrspuren in dem Straßensegment und/oder eines Erzeugens einer zusätzlichen Fahrspur in dem Straßensegment aufweisen. Der Begriff„Trajektoriendaten" kann geographische Koordinaten bezeichnen, wie etwa GPS-Koordinaten (Global Positioning System, GPS) und/oder GNSS-Daten (Global Navigation Satellite System, GNSS), welche eine Trajektorie, ein Bewegungsprofil, einen Fahrweg und/oder eine Bewegung eines

Verkehrsteilnehmers, wie etwa eines Fahrzeugs, eines Fahrrads und/oder eines Fußgängers, entlang einer Straße und/oder auf einer Kreuzung beschreiben.

Gleichsam kann der Begriff„Trajektoriendatensatz" eine Menge derartiger Trajektoriendaten eines oder mehrerer Verkehrsteilnehmer bezeichnen.

Ferner kann der Begriff„Modellieren des Straßensegments in wenigstens einem Straßenmodell" ein Abbilden, ein Nachbilden, ein Nachahmen und/oder ein

Imitieren des Straßensegments in dem wenigstens einen Straßenmodell bezeichnen. Dabei kann das Straßenmodell eine mathematische und/oder modellbasierte Abstraktion und/oder Beschreibung des Straßensegments bezeichnen.

Im Folgenden ist das erfindungsgemäße Verfahren zusammengefasst. Die fahrbahngenaue Straßenkarte kann beispielsweise in einer

Datenverarbeitungsvorrichtung von einem Datenspeicher der

Datenverarbeitungsvorrichtung eingelesen werden. Dabei kann die

fahrbahngenaue Straßenkarte einen oder mehrere Knoten und/oder eine oder mehrere Kanten zur geographischen Beschreibung einer oder mehrerer Straßen und/oder einer oder mehrere Kreuzungen aufweisen. Das Bereitstellen der fahrbahngenauen Straßenkarte kann somit ein Einlesen der fahrbahngenauen Straßenkarte und/oder ein Einlesen der wenigstens einen Kante und/oder des wenigstens einen Knoten umfassen. Die fahrbahngenaue Straßenkarte kann dann, beispielsweise anhand des wenigstens einen Knotens und/oder der wenigstens einen Kante, analysiert werden und in wenigstens ein Straßensegment unterteilt und/oder segmentiert werden. Insbesondere kann die fahrbahngenaue Straßenkarte eine Mehrzahl von Straßen aufweisen, welche jeweils, beispielsweise basierend auf den Knoten und/oder Kanten, in einzelne Straßensegmente unterteilt werden können. Mit anderen Worten können Straßen und/oder die wenigstens eine Straße basierend auf den Knoten und/oder Kanten identifiziert werden. Daran anschließend kann jedes der identifizierten

Straßensegmente in einem separaten Straßenmodell abgebildet, modelliert, nachgebildet und/oder imitiert werden. Danach kann für jedes der

Straßenmodelle, welche jeweils einem Straßensegment zugeordnet sein können, zumindest ein Teil der Parameter des jeweiligen Straßenmodells variiert und/oder verändert werden. Insbesondere können die Parameter eines jeden Straßenmodells mehrfach iterativ variiert werden, wobei Parameter

unterschiedlicher Straßenmodelle zeitgleich oder in einer zeitlichen Abfolge nacheinander variiert werden können. Dabei können die Parameterwerte unabhängig von den Trajektoriendaten variiert werden. Des Weiteren können die

Trajektoriendaten zu den jeweiligen Straßenmodellen, beispielsweise anhand von geographischen Koordinaten der Trajektoriendaten und/oder der

fahrbahngenauen Straßenkarte, zugeordnet werden. Dabei kann ermittelt werden, welche der Trajektoriendaten in einem der Straßensegmente

angeordnet sind, so dass basierend darauf die zu den einzelnen

Straßenmodellen zugehörigen Trajektoriendaten ermittelt werden können.

Insbesondere kann der Schritt des Modellierens in dem Straßenmodell vor dem Schritt des Zuordnens der Trajektoriendaten zu dem Straßenmodell erfolgen. Anschließend kann überprüft werden, wie gut die Trajektoriendaten durch die jeweiligen Straßenmodelle imitiert und/oder nachgebildet sind, wobei als Maß für die Güte und/oder Qualität einer solchen Abbildung für jedes der Straßenmodelle ein Wahrscheinlichkeitswert ermittelt werden kann. Gleichsam kann der

Wahrscheinlichkeit im Kontext der Erfindung ein Maß für eine Qualität und/oder Güte einer Abbildung, Nachbildung und/oder Imitierung der Trajektoriendaten durch das entsprechende Straßenmodell bezeichnen. Insbesondere kann für jedes der Straßenmodelle eine Mehrzahl von Wahrscheinlichkeitswerten durch mehrfaches unabhängiges Variieren eines Teils der Parameter jeden

Straßenmodells ermittelt werden. Aus den für jedes der Straßenmodelle ermittelten Wahrscheinlichkeitswerten kann sodann jeweils wenigstens ein im Vergleich zu anderen Wahrscheinlichkeitswerten desselben Straßenmodells hoher und/oder ein höchster Wahrscheinlichkeitswert ausgewählt werden, welcher somit einer optimalen Konfiguration des zugehörigen Straßenmodells und/oder den optimalen Parameterwerten des zugehörigen Straßenmodells entsprechen kann. Ferner kann im Rahmen der Ermittlung des höchsten

Wahrscheinlichkeitswertes das sogenannte Simulated Annealing Verfahren zum Einsatz kommen. Dies kann bewirken, dass Änderungsoperationen, welche eine Übereinstimmung zwischen Straßenmodell und Trajektoriendaten verschlechtern mit fortschreitender Zeit des Optimierungsprozesses seltener akzeptiert werden und/oder dass die Optimierung des Straßenmodells direkt in den optimalen Parameterwerten des Straßenmodells, d.h. dem wahrscheinlichsten und/oder besten Straßenmodell, endet. Letztlich können somit die

Wahrscheinlichkeitswerte sowie die Parameterwerte der einzelnen

Straßenmodelle iterativ optimiert werden. Die optimalen Parameterwerte der einzelnen Straßenmodelle können selektiert und/oder ausgewählt werden und können somit eine fahrspurgenaue Straßenkarte darstellen und/oder

repräsentieren. Mit anderen Worten kann die fahrspurgenaue Straßenkarte durch die optimalen Parameter des wenigstens einen Straßenmodells gegeben sein.

Das erfindungsgemäße Verfahren kann somit vorsehen, dass eines oder mehrere Straßensegmente in einem oder mehreren Straßenmodellen abgebildet werden und anschließend iterativ die optimalen Parameterwerte des einen Straßenmodells oder der Straßenmodelle ermittelt werden.

Das erfindungsgemäße Verfahren kann daher ein modellbasiertes

Optimierungsverfahren bezeichnen, basierend auf welchem in vorteilhafter Weise aus Bewegungsprofilen, Trajektoriendaten und/oder Fahrtrajektorien eines oder mehrerer Verkehrsteilnehmer eine genaue topologische und geometrische Straßenkarte eines befahrenen Straßennetzes abgeleitet und/oder ermittelt werden kann. Dabei können insbesondere eine Anzahl, ein Verlauf, eine Breite, ein Abstand und/oder eine Konnektivität einzelner Fahrspuren mit hoher Präzision bestimmt werden. Dies kann für gerade Straßensegmente,

Kurvensegmente und/oder für Kreuzungssegmente erfolgen.

Die Erfindung kann insbesondere als auf den nachfolgenden beschriebenen Erkenntnissen beruhend angesehen werden. Mit einer Verfügbarkeit von Konnektivitätslösungen in vielen Serienfahrzeugen und/oder über Smartphone- Anwendungen können bereits heute unzählige Bewegungsprofile und/oder Trajektoriendaten von Fahrzeugen und/oder Verkehrsteilnehmern erfasst werden. Dies kann somit eine Datenquelle darstellen, welche einfach, kostengünstig und frühzeitig verfügbar sein kann. Gleichzeitig gewinnt die flächendeckend genaue Kartierung des Straßennetzes weltweit im Kontext des automatischen Fahrens immer größere Bedeutung. Das erfindungsgemäße Verfahren kann daher in vorteilhafter Weise eine genaue Kartierung eines Straßennetzes basierend auf einer Analyse von bekannter Bewegungsprofile, Trajektoriendaten und/oder Fahrtrajektorien, etwa einer großen Fahrzeugflotte, ermöglichen. Beispielsweise im Vergleich zu einer Kartierung durch hoch spezialisierte Messfahrzeuge, wie sie häufig von traditionellen Kartenherstellern vorgenommen wird, können die für das erfindungsgemäße Verfahren

verwendeten Trajektorien kostengünstig, einfach und in großen Mengen bereitgestellt werden, so dass eine kostengünstige, schnelle, flächendeckende sowie präzise Kartierung eines Straßennetzes vorgenommen werden kann.

Gemäß einer Ausführungsform werden die optimalen Parameterwerte basierend auf einer Monte Carlo Methode, insbesondere basierend auf einer Reversible Jump Markov Chain Monte Carlo Methode (RJMCMC), ermittelt. Insbesondere kann das zufällige Auswählen einer Änderungsoperation zur zufälligen Variierung der Parameterwerte wenigstens eines Teils der Parameter des Straßenmodells basierend auf der Monte Carlo Methode und/oder der Reversible Jump Markov Chain Monte Carlo Methode erfolgen. Dabei können alle oder zumindest ein Teil der Änderungsoperationen als gleichverteilt angenommen werden und basierend auf einer Zufallszahl kann eine der Änderungsoperationen zur zufälligen

Variierung zumindest eines Teils der Parameterwerte ausgewählt, d.h. gleichsam gewürfelt, werden. Nach zufälliger Auswahl einer Änderungsoperation kann diese Änderungsoperation durchgeführt werden und anschließend kann entschieden werden, ob die dadurch hervorgerufene Änderung in den Parameterwerten akzeptiert oder verworfen wird. Im Zuge der RJMCMC Methode können allgemein Eingabedaten, wie etwa die Trajektoriendaten, als Realisierung eines Zufallsexperiments angesehen werden, wobei eine Verteilung der Eingabedaten durch das zugrundeliegende Straßennetz und/oder das Straßenmodell impliziert werden kann. Ziel der RJMCMC Methode kann dabei sein, die unbekannte

Verteilung, wie etwa das tatsächliche Straßennetz, anhand des Straßenmodells zu rekonstruieren. Dabei kann das Straßenmodell und/oder die Parameterwerte des Straßenmodells zufällig und/oder unabhängig von den Trajektoriendaten variiert werden. Anschließend können je nach ermitteltem

Wahrscheinlichkeitswert und/oder je nach Höhe des ermittelten

Wahrscheinlichkeitswertes die zugehörigen Parameterwerte bzw. die Änderung der Parameterwerte verworfen oder angenommen werden, etwa basierend auf einem Vergleich mit einem Schwellenwert und/oder basierend auf einer

Bewertungsmetrik. Auch kann im Zuge der Ermittlung der optimalen

Parameterwerte ein Simulated Annealing Verfahren zum Einsatz kommen.

Gemäß einer Ausführungsform weist das Straßenmodell wenigstens einen Straßenblock zum Modellieren einer zumindest in einem Teilbereich des

Straßensegments konstanten Anzahl von Fahrspuren auf. Alternativ oder zusätzlich weist das Straßenmodell wenigstens einen Verbindungsblock zum Modellieren, basierend auf wenigstens einer geometrischen Parametermatrix und wenigstens einer topologischen Parametermatrix, einer sich zumindest in einem Teilbereich des Straßensegments ändernden Anzahl von Fahrspuren auf, wobei Werte der geometrischen Parametermatrix eine Änderung einer

Fahrspurenanzahl innerhalb des Straßensegments beschreiben, und wobei Werte der topologischen Parametermatrix eine Verbindung zwischen einzelnen Fahrspuren innerhalb des Straßensegments beschreiben. Mit anderen Worten kann vorgesehen sein, jedes identifizierte Straßensegment durch zumindest einen Straßenblock und einen Verbindungsblock des Straßenmodells zu modellieren. Insbesondere kann vorgesehen sein, jedes identifizierte

Straßensegment durch einen zwischen zwei Verbindungsblöcken angeordneten Straßenblock zu modellieren. Durch Verwendung je eines Straßenblocks in jedem Straßensegment, welcher eine konstante Fahrspuranzahl modelliert, kann in vorteilhafter Weise ein Rechenaufwand reduziert sein. Ferner kann durch Verwendung wenigstens eines Verbindungsblocks pro Straßensegment eine Flexibilität des Straßenmodells erhöht sein, da etwaige Änderungen in einer Geometrie und/oder Topologie von zwei aneinander angrenzenden

Straßensegmenten zuverlässig und umfassend in dem Verbindungsblock modelliert und/oder berücksichtigt werden kann. Dabei kann der Verbindungblock je eine geometrische und je eine topologische Parametermatrix für jede

Fahrtrichtung einer Fahrbahn aufweisen. Mit anderen Worten kann der

Verbindungsblock über zwei geometrische und zwei topologische

Parametermatrizen zur Modellierung einer Geometrie und/oder Topologie von Fahrspuren unterschiedlicher Fahrtrichtung aufweisen.

Gemäß einer Ausführungsform weist der Schritt des Modellierens des

Straßensegments in dem Straßenmodell die folgenden Teilschritte auf: Parametrisieren des Straßensegments in einem Einheitsintervall, so dass jeder Punkt der Straße in dem Straßensegment über einen

Parametrisierungswert in dem Einheitsintervall festgelegt ist;

Segmentieren und/oder Einteilen des Straßensegments in wenigstens einen Straßenblock und wenigstens einen Verbindungsblock des

Straßenmodells;

Modellieren, Nachbilden und/oder Imitieren eines Verschwindens oder eines Erzeugens einer Fahrspur innerhalb des Straßensegments basierend auf wenigstens einer geometrischen Parametermatrix des

Verbindungsblocks;

Modellieren, Nachbilden und/oder Imitieren einer Verbindung einzelner Fahrspuren innerhalb des Straßensegments basierend auf wenigstens einer topologischen Parametermatrix des Verbindungsblocks; und

Ermitteln von Werten der geometrischen Parametermatrix und/oder von Werten der topologischen Parametermatrix basierend auf einer zufälligen

Auswahl einer Änderungsoperation des Straßenmodells.

Dabei kann der Schritt des Parametrisierens einen Schritt des Ermitteins einer Länge und/oder einer Längserstreckung des Straßensegments und einen Schritt des Normierens auf die ermittelte Länge umfassen. Mit anderen Worten kann jedes Straßensegment eindimensional parametrisiert werden, wodurch in vorteilhafter Weise jeder Punkt des Straßensegments durch einen Wert zwischen Null und Eins, d.h. durch einen Wert des Einheitsintervalls, beschrieben werden kann.

Gemäß einer Ausführungsform weist die digitale fahrbahngenaue Straßenkarte wenigstens eine Kreuzung und eine Mehrzahl von mit der Kreuzung

verbundenen Straßen auf, wobei das Verfahren weiter die folgenden Schritte aufweist:

Identifizieren der wenigstens einen Kreuzung unter Segmentieren und/oder Einteilen der fahrbahngenauen Straßenkarte in wenigstens ein

Kreuzungssegment;

Modellieren, Abbilden, Nachbilden und/oder Imitieren des

Kreuzungssegments in wenigstens einem Kreuzungsmodell, wobei das

Kreuzungsmodell eine Mehrzahl von Parameter zur geometrischen und/oder topologischen Beschreibung von Fahrspuren der Kreuzung aufweist;

zufälliges Variieren und/oder Verändern, insbesondere mehrfaches zufälliges Variieren, von Parameterwerten zumindest eines Teils der Parameter des Kreuzungsmodells durch zufälliges Auswählen einer

Änderungsoperation des Kreuzungsmodells zur Änderung von

Parameterwerten;

Zuordnen zumindest eines Teils der Trajektoriendaten des

Trajektoriendatensatzes zu dem Kreuzungsmodell unter Ermitteln wenigstens eines Wahrscheinlichkeitswertes für das Kreuzungsmodell, wobei der Wahrscheinlichkeitswert mit einer Güte und/oder einer Qualität einer Abbildung der Trajektoriendaten durch das Kreuzungsmodell korreliert;

Ermitteln, basierend auf dem ermittelten wenigstens einen

Wahrscheinlichkeitswert, von optimalen Parameterwerten zumindest eines

Teils der Parameter des Kreuzungsmodells; und

Erstellen einer fahrspurgenauen Straßenkarte basierend auf den optimalen Parameterwerten des Kreuzungsmodells. Erfindungsgemäß kann daher vorgesehen sein, jedes Straßensegment der fahrbahngenauen Straßenkarte durch ein Straßenmodell und jedes

Kreuzungssegment durch ein Kreuzungsmodell zu modellieren. Dadurch können in vorteilhafter Weise die individuellen Eigenschaften von Kreuzungen und Straßen modelliert werden und es kann ein Rechenaufwand reduziert sein.

Zudem kann dies eine Präzision und/oder Genauigkeit der erstellten

fahrspurgenauen Straßenkarte erhöhen. Dabei kann eine Kreuzung in der fahrbahngenauen Straßenkarte etwa durch Identifizieren eines mit mehr als zwei Kanten verbundenen Knotens identifiziert werden. Gemäß einer Ausführungsform weist das Kreuzungsmodell ein äußeres

Kreuzungsmodell zum Modellieren einer befahrbaren Fläche der Kreuzung basierend auf einem Distanzparameter (d) und einem Winkelparameter (a) auf. Alternativ oder zusätzlich weist der Schritt des Modellierens des

Kreuzungssegments in dem Kreuzungsmodell die folgenden Teilschritte auf: - Ermittein eines Kreuzungsknotens in der fahrbahngenauen Straßenkarte, etwa basierend auf einem Ermitteln eines mit mehr als zwei Kanten verbundenen Knotens in der fahrbahngenauen Straßenkarte; Ermitteln einer Anzahl von mit dem Kreuzungsknoten verbundenen Kanten der fahrbahngenauen Straßenkarte unter Ermitteln einer Anzahl von mit der Kreuzung verbundenen Straßen, wobei die Anzahl der ermittelten Kanten der Anzahl der mit der Kreuzung verbundenen Straßen entsprechen kann; - Generieren und/oder Erzeugen einer der Anzahl von mit der Kreuzung

verbundenen Straßen entsprechenden Anzahl von Kreuzungsarmen, wobei jeder der Kreuzungsarme durch einen Distanzparameter (d) zur Angabe eines Abstandes eines Zentrums der Kreuzung zu einer

Begrenzungsfläche der Kreuzung entlang des jeweiligen Kreuzungsarmes definiert ist, und wobei jeder der Kreuzungsarme durch einen

Winkelparameter (a) zur Angabe eines Drehwinkels zwischen dem jeweiligen Kreuzungsarm und einer Referenzrichtung, beispielsweise eines Referenzkreuzungsarmes, definiert ist.

Durch das äußere Kreuzungsmodell kann in vorteilhafter Weise ein

Anschlussquerschnitt zwischen den Kreuzungsarmen und den daran

angeschlossenen Straßen präzise modelliert und/oder aufeinander abgestimmt sein, beispielsweise im Hinblick auf eine Anzahl von Fahrspuren, eine Breite von Fahrspuren, eines Abstandes zwischen Fahrspuren entgegengesetzter

Fahrtrichtung und/oder einer Krümmung.

Gemäß einer Ausführungsform weist das Kreuzungsmodell ein inneres

Kreuzungsmodell zum Modellieren, basierend auf einer Faktormatrix (F) des Kreuzungsmodells, von in die Kreuzung einführenden Fahrspuren, von aus der Kreuzung ausführenden Fahrspuren und eines Verlaufs von Fahrspuren über eine befahrbare Fläche der Kreuzung auf. Alternativ oder zusätzlich weist der

Schritt des Modellierens des Kreuzungssegments in dem Kreuzungsmodell die folgenden Teilschritte auf:

Modellieren, Nachbilden, Abbilden und/oder Imitieren zumindest eines Teils von in die Kreuzung einführenden Fahrspuren, zumindest eines Teils von aus der Kreuzung ausführenden Fahrspuren und eines Verlaufs zumindest eines Teils von über eine Kreuzungsfläche der Kreuzung führenden Fahrspuren basierend auf einer Faktormatrix (F), wobei Werte der

Faktormatrix (F) einen Verlauf und eine Verbindung von Fahrspuren über die Kreuzungsfläche beschreiben; und

Ermitteln von Werten der Faktormatrix (F) basierend auf zumindest einem Teil der Trajektoriendaten des Trajektoriendatensatzes. Durch das innere Kreuzungsmodell kann in vorteilhafter Weise jede mögliche Verbindung einzelner Fahrspuren über die Kreuzungsfläche präzise modelliert werden. Ferner kann durch Ermitteln der Werte der Faktormatrix basierend auf den Trajektoriendaten eine Anzahl möglicher Verbindungen der Fahrspuren über die Kreuzung und somit ein Rechenaufwand reduziert sein, da die

Trajektoriendaten stets tatsächliche und realistische Verbindungen der

Fahrspuren repräsentieren und/oder darstellen können. Gemäß einer Ausführungsform weist das Straßenmodell und/oder ein

Kreuzungsmodell jeweils einen Anzahlparameter (L) zur Beschreibung einer Anzahl von Fahrspuren, einen Breitenparameter (W) zur Beschreibung einer Breite einzelner Fahrspuren, einen Krümmungsparameter (C) zur Beschreibung einer Krümmung einer Straße und einen Abstandsparameter (G) zur

Beschreibung eines Abstands zwischen Fahrspuren entgegengesetzter

Fahrtrichtung auf. Voranstehend genannte Parameter können Parameter eines inneren Kreuzungsmodells und/oder eines äußeren Kreuzungsmodells des Kreuzungsmodells sein. Auch können voranstehend genannte Parameter Parameter eines Straßenblocks und/oder eines Verbindungsblocks des

Straßenmodells sein. Der Abstand zwischen Fahrspuren entgegengesetzter

Fahrtrichtung kann etwa eine bauliche Trennung zwischen benachbarten Fahrspuren entgegengesetzter Fahrtrichtung beschreiben. Durch voranstehend aufgelistete Parameter des Straßenmodells und/oder des Kreuzungsmodells kann in vorteilhafter Weise sichergestellt sein, dass Straßen und/oder

Kreuzungen präzise modelliert werden können und so eine präzise

fahrspurgenaue Straßenkarte erstellt werden kann.

Gemäß einer Ausführungsform weist das Straßenmodell und/oder ein

Kreuzungsmodell wenigstens eine Änderungsoperation ausgewählt aus der Liste bestehend aus einer Einfügoperation zum Einfügen eines Verbindungsblocks in einen Straßenblock, eine Verschmelzoperation zum Verschmelzen zweier Straßenblöcke und eines Verbindungsblocks zu einem Straßenblock, eine Anpassungsoperation zum Anpassen eines Parametrisierungswertes zur Parametrisierung einer Längserstreckung einer Straße; eine Hinzufügeoperation zum Hinzufügen einer Fahrspur, eine Entfernungsoperation zum Entfernen einer

Fahrspur, eine Abstandsanpassungsoperation zum Anpassen eines Abstandes zwischen Fahrspuren entgegengesetzter Fahrtrichtung, eine Breitenanpassungsoperation zum Anpassen einer Breite einer Fahrspur und eine Krümmungsanpassungsoperation zur Anpassung einer Krümmung einer Straße in dem Straßenmodell, eines Straßenblocks und/oder eines Verbindungsblocks des Straßenmodells auf. Mittels voranstehend aufgelisteter

Änderungsoperationen können in vorteilhafter Weise die Parameterwerte sämtlicher und/oder zumindest eines Großteils der Parameter des

Straßenmodells und/oder des Kreuzungsmodells durch zufällige Auswahl einer der Änderungsoperationen variiert werden. Ferner können die

Änderungsoperationen sämtliche denkbaren und realistischen Änderungen eines realen Straßennetzes zuverlässig abbilden, was wiederum erlauben kann, eine präzise und realistische fahrspurgenaue Straßenkarte zu erstellen.

Gemäß einer Ausführungsform weist das Verfahren weiter einen Schritt des Verwerfens oder Akzeptierens von basierend auf dem zufälligen Auswählen einer Änderungsoperation zufällig variierten Parameterwerten basierend auf einer

Bewertungsmetrik auf, welche die Güte der Abbildung der Trajektoriendaten durch das Straßenmodell und/oder ein Kreuzungsmodell beschreibt. Dabei weist die Bewertungsmetrik einen ersten Term zur Beschreibung einer

Übereinstimmung zwischen den Trajektoriendaten und dem Straßenmodell und/oder einem Kreuzungsmodell auf. Weiter weist die Bewertungsmetrik einen zweiten Term zur Berücksichtigung wenigstens einer vorbestimmten Kenngröße einer Straßengeometrie, insbesondere einer Kenngröße bezüglich einer

Fahrspurbreite und/oder einer Straßenbreite, auf. Beispielsweise kann es für eine Kenngröße eine stochastische Vorgabe bezüglich der Werte der Kenngröße geben, welche die Dimension der Kenngröße vorbestimmen kann.

Beispielsweise kann eine Spurbreite mittels einer Normalverteilung festgelegt sein, so dass eine Spurbreite in der Nähe von rund 3,25 m gesucht werden soll. Damit kann vermieden werden, dass Spurbreiten von z.B. 6 m untersucht werden. Über die Bewertungsmetrik kann daher in vorteilhafter Weise jedwedes Vorwissen über eine Straßengeometrie und/oder eine Kreuzungsgeometrie berücksichtigt werden. Beispielsweise können in der Bewertungsmetrik

Baunormen und/oder Baurichtlinien für den Straßenbau berücksichtigt werden. Damit kann insbesondere sichergestellt sein, dass durch das erfindungsgemäße Verfahren realistische fahrspurgenaue Straßenkarten erstellt werden können. Auch kann eine Rechenzeit dadurch reduziert sein. Ein weiterer Aspekt der Erfindung betrifft eine Datenverarbeitungsvorrichtung zum Ermitteln einer fahrspurgenauen Straßenkarte basierend auf einer digitalen fahrbahngenauen Straßenkarte. Dabei ist die Datenverarbeitungsvorrichtung dazu eingerichtet, das Verfahren, wie voranstehend und nachfolgend

beschrieben, auszuführen. Dabei kann der Begriff„eingerichtet sein" bedeuten, dass die Datenverarbeitungsvorrichtung beispielsweise über ein

Programmelement verfügt, welches bei dessen Ausführung, etwa auf einem Prozessor der Datenverarbeitungsvorrichtung, die Datenverarbeitungsvorrichtung anleitet, das erfindungsgemäße Verfahren auszuführen. Beispielsweise kann das Programmelement entsprechende Softwareinstruktionen aufweisen.

Sämtliche Merkmale, Schritte, Funktionen und/oder Charakteristika, welche voranstehend und nachfolgend in Bezug auf das erfindungsgemäße Verfahren beschrieben sind, können Merkmale, Funktionen und/oder Charakteristika der Datenverarbeitungsvorrichtung, wie voranstehend und nachfolgend beschrieben, sein und umgekehrt.

Gemäß einer Ausführungsform weist die Datenverarbeitungsvorrichtung einen Datenspeicher zur Speicherung einer digitalen fahrbahngenauen Straßenkarte und einen Prozessor auf. Auf dem Datenspeicher kann ferner ein

Programmelement gespeichert sein, welches bei dessen Ausführung auf dem Prozessor die Datenverarbeitungsvorrichtung anleitet, das erfindungsgemäße Verfahren auszuführen.

Kurze Beschreibung der Zeichnungen

Im Folgenden werden Ausführungsbeispiele der Erfindung mit Bezug auf die beiliegenden Figuren detailliert beschrieben.

Fig. 1 zeigt eine Datenverarbeitungsvorrichtung gemäß einem

Ausführungsbeispiel der Erfindung.

Fig. 2 zeigt ein Flussdiagramm zur Illustration von Schritten eines Verfahrens zur Erstellung einer fahrspurgenauen Straßenkarte gemäß einem

Ausführungsbeispiel der Erfindung. Fig. 3A bis 3D illustrieren jeweils ein Verfahren zur Erstellung einer

fahrbahngenauen Straßenkarte.

Fig. 4A bis 4C illustrieren jeweils Schritte eines Verfahrens zur Erstellung einer fahrspurgenauen Straßenkarte gemäß einem Ausführungsbeispiel der Erfindung.

Fig. 5A bis 5C illustrieren jeweils ein Straßenmodell gemäß einem

Ausführungsbeispiel der Erfindung. Fig. 6A bis 6D illustrieren jeweils ein Kreuzungsmodell gemäß einem

Ausführungsbeispiel der Erfindung.

Fig. 7A bis 7E illustrieren jeweils Änderungsoperationen gemäß einem

Ausführungsbeispiel der Erfindung.

Fig. 8A und 8B illustrieren jeweils eine Anwendung einer Bewertungsmetrik gemäß einem Ausführungsbeispiel der Erfindung.

Die Figuren sind lediglich schematisch und nicht maßstabsgetreu. In den Figuren sind gleiche, gleich wirkende oder ähnliche Elemente mit gleichen

Bezugszeichen versehen.

Ausführungsformen der Erfindung Fig. 1 zeigt eine Datenverarbeitungsvorrichtung 10 gemäß einem

Ausführungsbeispiel der Erfindung.

Die Datenverarbeitungsvorrichtung 10 weist einen Datenspeicher 12 auf. In dem Datenspeicher 12 kann etwa eine fahrbahngenaue Straßenkarte 14 hinterlegt sein, welche wenigstens einen Knoten 11 (siehe z.B. Fig. 3C und 3D) und/oder eine Kante 13 (siehe z.B. Fig. 3C und 3D) zur Beschreibung eines

Straßenverlaufs einer Straße 17 (siehe Fig. 4A) und/oder einer Kreuzung 19 (siehe Fig. 4A) aufweisen kann. Insbesondere kann die Fahrbahngenaue Straßenkarte 14 eine Mehrzahl von Knoten 11 und/oder Kanten 13 zur

Beschreibung eines Straßennetzes mit mehreren Straßen 17 und/oder

Kreuzungen 19 aufweisen. Auch kann in dem Datenspeicher 12 ein Trajektonendatensatz 16 hinterlegt sein, welcher eine Mehrzahl von

Trajektoriendaten 27 (siehe Fig. 3B) von Verkehrsteilnehmern aufweisen kann.

Alternativ oder zusätzlich kann die Datenverarbeitungsvorrichtung 10 eine Schnittstelle 15 aufweisen, über welche die fahrspurgenaue Straßenkarte 14 und/oder der Trajektonendatensatz 16 der Datenverarbeitungsvorrichtung 10 bereitgestellt werden kann. Die Schnittstelle 15 kann etwa drahtlos ausgeführt sein, so dass die fahrbahngenaue Straßenkarte 14 und/oder der

Trajektonendatensatz 16 beispielsweise über WLAN, Bluetooth Server und/oder oder dergleichen drahtlos empfangen werden kann, beispielsweise von wenigstens einem Server und/oder über eine Cloud-Umgebung.

Weiter weist die Datenverarbeitungsvorrichtung 10 wenigstens einen Prozessor 18 auf. Auf dem Prozessor 18 kann ein etwa in dem Datenspeicher 12 hinterlegtes Programmelement ausgeführt werden, welches die

Datenverarbeitungsvorrichtung 10 und/oder den Prozessor 18 anleitet, das erfindungsgemäße Verfahren zur Erstellung einer fahrspurgenauen Straßenkarte 22, so wie voranstehend und nachfolgend beschrieben, auszuführen. Optional kann die Datenverarbeitungsvorrichtung 10 über ein Bedienelement 20 zur Eingabe einer Bedieneingabe, etwa durch einen Benutzer, aufweisen. Das Bedienelement kann zudem ein Anzeigeelement 21 zur Anzeige der

fahrbahngenauen Straßenkarte 14, der fahrspurgenauen Straßenkarte 22 und/oder des Trajektoriendatensatzes 16 aufweisen.

Fig. 2 zeigt ein Flussdiagramm zur Illustration von Schritten eines Verfahrens zur Erstellung einer fahrspurgenauen Straßenkarte 22 gemäß einem

Ausführungsbeispiel der Erfindung. In einem ersten Schritt S1 wird eine digitale fahrbahngenauen Straßenkarte 14 zur Beschreibung eines Straßenverlaufs wenigstens einer Straße 17 und/oder wenigstens einer Kreuzung 19 bereitgestellt, beispielsweise über den

Datenspeicher 12 und/oder über die Schnittstelle 15 der

Datenverarbeitungsvorrichtung 10. Insbesondere kann die fahrbahngenaue Straßenkarte 14 eine Mehrzahl von Straßen 17 und Kreuzungen 19 aufweisen.

Ferner wird in Schritt S1 ein Trajektonendatensatz 16 bereitgestellt, welcher eine Mehrzahl von Trajektoriendaten 27 von Verkehrsteilnehmern entlang der wenigstens einen Straße 17 und/oder der wenigstens einen Kreuzung 19 aufweist. Auch der Trajektoriendatensatz 16 kann über den Datenspeicher 12 und/oder über die Schnittstelle 15 der Datenverarbeitungsvorrichtung 10 bereitgestellt sein.

In einem Schritt S2 wird die wenigstens eine Straße 17 unter Segmentieren der fahrbahngenauen Straßenkarte 14 in wenigstens ein Straßensegment 26 (siehe Fig. 4C) identifiziert. Dies kann basierend auf den Knoten 1 1 und/oder Kanten 13 der fahrbahngenauen Straßenkarte 14 erfolgen. Optional kann in Schritt S2 wenigstens eine Kreuzung 19 unter Segmentieren der fahrbahngenauen

Straßenkarte 14 in wenigstens ein Kreuzungssegment 19a erfolgen.

Insbesondere kann in Schritt S2 die fahrbahngenaue Straßenkarte 14 in eine Mehrzahl von Straßensegmente 26 und eine Mehrzahl von Kreuzungssegmenten 19a unterteilt werden.

In einem weiteren Schritt S3 wird das wenigstens eine Straßensegment 26 in wenigstens einem Straßenmodell 28 (siehe Fig5A, 5B) modelliert. Insbesondere können in Schritt S2 alle Straßensegmente 26 jeweils in einem Straßenmodell 28 modelliert werden. Zudem kann in Schritt S3 die wenigstens eine Kreuzung 19 in einem Kreuzungsmodell 34 (siehe Fig. 6A-6C) modelliert werden. Insbesondere kann jede der Kreuzungen 19 in einem separaten Kreuzungsmodell 34 modelliert werden. Dabei weist jedes der Straßenmodelle 28 und/oder jedes der

Kreuzungsmodelle 34 eine Mehrzahl von Parameter zur geometrischen und/oder topologischen Beschreibung von Fahrspuren 23 auf.

In einem weiteren Schritt S4 werden Parameterwerten zumindest eines Teils der Parameter des Straßenmodells 28 und/oder des Kreuzungsmodells 34 durch zufälliges Auswählen einer Änderungsoperation 40, 41 , 42, 43, 44, 46, 48, 50 (siehe Fig. 7A-7E) des Straßenmodells 28 und/oder des Kreuzungsmodells 34 variiert. Insbesondere können in Schritt S4 die Parameterwerte aller

Straßenmodelle 28 und aller Kreuzungsmodelle 34 iterativ und mehrfach variiert werden.

In einem weiteren Schritt S5 wird zumindest ein Teil der Trajektoriendaten 27 des Trajektoreindatensatzes 16 zu dem Straßenmodell 28 unter Ermitteln wenigstens eines Wahrscheinlichkeitswertes für das Straßenmodell 28 zugeordnet.

Insbesondere können in Schritt S5 die Trajektoriendaten 27 zu jedem der Straßenmodelle 28 unter Ermitteln jeweils wenigstens eines

Wahrscheinlichkeitswertes für jedes der Straßenmodelle 28 zugeordnet werden. Ferner können in Schritt S5 die Trajektoriendaten 27 zu dem wenigstens einen Kreuzungsmodell 34 unter Ermitteln wenigstens eines Wahrscheinlichkeitswertes zugeordnet werden können in Schritt S5 die Trajektoriendaten 27 zu jedem der

Kreuzungsmodelle 34 unter Ermitteln jeweils wenigstens eines

Wahrscheinlichkeitswertes für jedes der Kreuzungsmodelle 34 zugeordnet werden. Die Wahrscheinlichkeitswerte korrelieren dabei mit einer Güte einer Abbildung der Trajektoriendaten 27 durch das jeweilige Straßenmodell 28 und/oder das jeweilige Kreuzungsmodell 34.

In einem Schritt S6 werden basierend auf dem ermittelten wenigstens einen Wahrscheinlichkeitswert optimalen Parameterwerte zumindest eines Teils der Parameter des Straßenmodells 28 und/oder des Kreuzungsmodells 34 ermittelt. Insbesondere können für jedes der Straßenmodelle 28 und/oder für jedes der

Kreuzungsmodelle 34 optimale Parameterwerte ermittelt werden.

In einem Schritt S7 wird eine fahrspurgenaue Straßenkarte 22 basierend auf den optimalen Parameterwerten des wenigstens einen Straßenmodells 28 und/oder des wenigstens einen Kreuzungsmodells 34 erstellt. Insbesondere kann die fahrspurgenaue Straßenkarte 22 durch die optimalen Parameterwerte aller Straßenmodelle 28 und/oder aller Kreuzungsmodelle 34 gegeben sein.

Fig. 3A bis 3D illustrieren jeweils ein Verfahren zur Erstellung einer

fahrbahngenauen Straßenkarte 16. Die derart erstellte fahrbahngenaue

Straßenkarte 16 kann als Grundlage für die Erstellung einer fahrspurgenauen Straßenkarte 22 dienen. Entsprechend können sämtliche in Bezug auf Fig. 3A bis 3D beschriebenen Schritte auch Teil des erfindungsgemäßen Verfahrens zur Erstellung einer fahrspurgenauen Straßenkarte 22 sein.

In Fig. 3A ist Trajektoriendatensatz 16 mit einer Mehrzahl von gesammelten Trajektoriendaten 27 und/oder Trajektorien 27 illustriert. Ferner illustriert Fig. 3A ein Segmentieren und/oder Einteilen der Trajektoriendaten 27 in verschiedene Verkehrsszenarien und/oder Segmente 24a-c. Schematisch sind in Fig. 3A ein erstes Segment 24a, welches eine Kurve beschreibt, ein zweites Segment 24b, welches eine Kreuzung beschreibt, und ein drittes Segment, welches eine Straße beschreibt, gezeigt. Die Segmente 24a-c werden dabei wie im Folgenden beschrieben ermittelt.

Die von einer Fahrzeugflotte gesammelten Trajektoriendaten 27, etwa GNSS Trajektorien 27, können in einer beliebigen Anzahl ein ebenso beliebig großes

Verkehrsszenario beschreiben. Um die Dimension der auszuwertenden Daten greifbar zu machen, können die Trajektorien 27 automatisiert gemäß einer Logik aufgeteilt werden. Dazu können die Trajektoriendaten 27, welche als

Eingabedaten bezeichnet werden können, in verschiedene Verkehrsszenarien 24a-c und/oder verschiedene Segmente 24a-c unterteilt werden, wobei jedes der

Segmente 24a-c eine gerade Straße, eine Kurve oder eine Kreuzung

beschreiben kann.

In einem automatisierten Verfahren kann jede Trajektorie 27 durchlaufen werden und anhand von Grenzwerten in einer Fahrtwinkeländerung und/oder einer

Geschwindigkeit können einzelne Messpunkte als potentielle Kurvenpunkte identifiziert werden. Diese Punkte liegen somit entweder auf einer Kurve, einer Kreuzung oder können durch Messfehler zu Stande kommen. Anschließend können alle identifizierten Punkte über Distanzgrenzwerte geclustert, aggregiert und/oder zusammengefasst werden. Ab einer bestimmten Menge an

zusammengefassten Punkten wird das Cluster als eine Kurve und/oder eine Kreuzung angesehen. Basierend auf den gefundenen Kurven und/oder

Kreuzungen kann dann eine Triangulation und darauf eine Delaunay Zerlegung konstruiert werden. Eine jede Zelle dieser Zerlegung kann final eine

eigenständige Verkehrssituation 24a-c und/oder ein Segment 24a-c beschreiben.

Gleichsam könne die Segmente 24a-c als Zellen 24a-c der Zerlegung

interpretiert werden.

Basierend auf einer Menge an Trajektoriendaten 27, etwa GNSS

Fahrzeugtrajektorien 27, kann eine fahrbahngenaue Straßenkarte 14 erzeugt werden, welche einem Graphen, bestehend aus Knoten 1 1 und Kanten 13, entsprechen kann, wobei die Knoten 1 1 und Kanten 13 eine Straßenmittellinie repräsentieren können. Exemplarisch ist eine derartige fahrbahngenaue

Straßenkarte 14 in Fig. 3D illustriert.

Zur Erstellung der fahrbahngenauen Straßenkarte 14 können zunächst die Eingabedaten 16, 27 wie bei Fig. 3A beschrieben segmentiert werden. Für jede Zelle 24a-c kann anschließend ein Graph initialisiert werden, welcher das Verkehrsszenario des jeweiligen Segments 24a-c bzw. der jeweiligen Zelle 24a-c beschreiben kann. Das angestrebte Ziel ist dabei, dass die Modelle in den Zellen 24a-c, verknüpft über Randbedingungen, individuell entwickelt und abschließend zu einem Graphen fusioniert werden können. Exemplarisch ist das Erstellen einer fahrbahngenauen Straßenkarte 14 in den Figuren 3B-3D für das

Straßensegment 24c aus Fig. 3A gezeigt. Fig. 3B zeigt dabei eine Zelle 24c bzw. ein Segment 24c und die Fahrzeugtrajektorien 27. Fig. 3C zeigt eine initiale Straßenkarte 14 und Fig. 3D eine optimierte Straßenkarte 14. Die Straßenkarten 14 der Figuren 3C und 3D könne auch als Zellgraphen 14 bezeichnet werden.

Zur Initialisierung können zunächst alle Zellränder 25 mit den Trajektorien 27 geschnitten werden, um die Straßenzentren auf den Zellrändern 25 zu ermitteln, wie in Fig. 3B gezeigt. Diese Zentren können in die Graphen der entsprechenden Zellen 24c als Knoten 1 1 aufgenommen, wie in Fig. 3C gezeigt. Zusätzlich kann in jeder Zelle 24c der Schwerpunkt der Zelle 24c als Knoten 1 1 in den Graph eingefügt und durch Kanten 13 mit den Knoten 1 1 auf den Zellrändern 25 verbunden werden. Zur Verknüpfung der Trajektoriendaten 27 und der Modelle bzw. Zellgraphen kann eine Bewertungsmetrik eingeführt werden, welche beschreibt, wie gut die Modelle die Daten abbilden. Dabei können einerseits die Distanz zwischen den Modellen und den Trajektoriendaten 27 und andererseits die Unterschiede in der Fahrtrichtung berücksichtigt werden. Um die Modelle zu optimieren und die finale fahrbahngenaue Straßenkarte 16, wie in Fig. 3D gezeigt, zu erstellen, kann eine

Reversible Jump Markov Chain Monte Carlo (RJMCMC) Methode eingesetzt werden. Dabei werden die Trajektoriendaten 27 als die Realisierung eines Zufallsexperimentes angesehen, dessen Verteilung durch das zugrundeliegende Straßennetz impliziert wird. Ziel der Methode ist, die unbekannte Verteilung, in diesem Fall das Straßennetz, zu rekonstruieren. Dabei werden die Modelle zufällig, unabhängig von den Trajektoriendaten 27 variiert und anschließend kann eine Entscheidung über eine Annahme oder ein Verwerfen der Änderung aufgrund der Bewertungsmetrik getroffen werden. Die zufällige Variierung der Modelle erfolgt durch die zufällige Auswahl vorgeschriebener

Änderungsoperationen. Zur Auswahl stehen beispielsweise eine

Bewegoperation, eine Erzeugoperation, eine Entfernoperation, eine

Aufteiloperation und/oder eine Verschmelzoperation. Bei der Bewegoperation wird ein Knoten 1 1 eines Zellgraphen 24c im Raum bewegt. Die Erzeugoperation beschreibt das Hinzufügen eines neuen Knotens 1 1 in den Graphen 24c und bildet mit der Entfernoperation ein reversibles Paar von Operationen. Bei der Verschmelzoperation wird ein Knoten 1 1 in eine benachbarte Kante 13 eingefügt, sodass zwei nahe beieinanderliegende Kanten 13 stückweise vereint werden.

Die Aufteiloperation löst ein derartiges Konstrukt wieder auf und stellt somit das Gegenteil der Verschmelzoperation dar. Das Vorhandensein von reversiblen Paaren kann für eine korrekte stochastische Beschreibung des Vorgangs vorteilhaft sein. Wie aus einem Vergleich der Figuren 3C und 3D ersichtlich, wurde während der Optimierung der mittlere Knoten 1 1 entfernt, da dieser zur

Beschreibung der Straße 17 nicht erforderlich ist.

Fig. 4A bis 4C illustrieren jeweils Schritte eines Verfahrens zur Erstellung einer fahrspurgenauen Straßenkarte 22 gemäß einem Ausführungsbeispiel der Erfindung. Im Speziellen ist in Fig. 4A eine fahrbahngenaue Straßenkarte 14 gezeigt. Fig. 4B illustriert ein Parametrisieren und Fig. 4C ein Segmentieren von Straße 17 der Straßenkarte 14. Ferner zeigen Fig. 5A bis 5C jeweils ein

Straßenmodell 28 gemäß einem Ausführungsbeispiel der Erfindung. Im

Speziellen zeigt Fig. 5A einen Verbindungsblock 30 des Straßenmodells 28, Fig. 5B zeigt einen Straßenblock 32 des Straßenmodells 28 und Fig. 5C zeigt geometrische und topologische Parametermatrizen des Verbindungsblocks 30 aus Fig. 5A.

Fig. 4A zeigt einen straßengenauen Graphen 14 und/oder eine fahrbahngenaue Straßenkarte 14, welche eine Straße 17 und an den Enden jeweils eine

Kreuzung 19 mittels Knoten 11 und Kanten 13 beschreibt. Um die Straße 17 in eine fahrspurgenaue Straßenkarte 22 zu überführen, wird die Straße 17 zunächst eindimensional parametrisiert. Somit kann, wie in Figur 4B dargestellt, jeder Punkt p der Straße 17 über einen Wert p e [0; 1] des Einheitsintervalls beschrieben werden.

Basierend auf dieser Parametrisierung können Straßensegmente 26, wie Figur 4C dargestellt, definiert werden. Mit anderen Worten wird die Straße 17 in eines oder mehrere Straßensegmente 26 unterteilt, welche etwa basierend auf den Knoten 11 und/oder Kanten 13 identifiziert werden können. Die Segmentierung der Straße 17 in Straßensegmente 26 kann es erlauben, Verkehrssituationen auf Fahrspurebene in dem Straßenmodell 28 zu

beschreiben, wie in Fig. 5A bis 5C illustriert. Dabei wird das Fahren auf einer konstanten Anzahl an Fahrspuren 23 und die Aufweitung bzw. Verengung der Straße 17 um eine Fahrspur 23 unterschieden.

Ein allgemeiner Straßenblock 32, wie in Fig. 5B gezeigt, kann dabei über einen Anzahlparameter L zur Beschreibung einer Anzahl von Fahrspuren 23, einen Breitenparameter W zur Beschreibung einer Breite einzelner Fahrspuren 23, einen Krümmungsparameter C zur Beschreibung einer Krümmung einer Straße 17 und einen Abstandsparameter G zur Beschreibung eines Abstands zwischen benachbarten Fahrspuren 23 entgegengesetzter Fahrtrichtung aufweisen. Auch kann der Straßenblock 28 über einen Typenparameter T zur Beschreibung eines Typs einer Fahrbahnmarkierung für jede Fahrspur 23 verfügen. Der Parameter G kann dabei eine Größe einer baulichen Trennung zwischen den

entgegengesetzten Fahrspuren 23 beschreiben.

Ein allgemeiner Straßenblock 32 kann somit durch die Größe

definiert sein.

Eine Straße 17 ist somit definiert als eine Menge von m Straßensegmenten 26

und deren Parametrisierungswerten P, welche die longitudinale Ausdehnung auf der Straße 17 gemäß Figuren 4A bis 4C beschreiben gegeben sein:

Um einen gekrümmtes Straßensegment 26 darzustellen, können alle

Verbindungen von Fahrspuren 23 auf dem Straßensegment 26 durch kubische Hermite Polynome beschrieben werden. Dadurch ist es möglich, dass ein Straßensegment 26 nicht nur eine konstante Krümmung aufweist, sondern einen beliebigen Verlauf annehmen kann, wobei lediglich die Randbedingungen der Stetigkeit und Differenzierbarkeit eingehalten werden, um einen realistischen Straßenverlauf zu erzeugen. Die Randbedingungen werden durch die Vorgabe der Anschlusspunkte und der Steigung bzw. dem Steigungsvektor in den Anschlusspunkten eingebracht. Um den Verlauf der Polynome zu beeinflussen, ist der Betrag der Steigungsvektoren als Parameter C in dem Straßenmodells 28 zugänglich bzw. integriert. Ein allgemeiner Straßenblock 32, im Folgenden auch als B _A bezeichnet, kann durch weitere Einschränkungen oder Ergänzungen spezifiziert werden. Ein Straßenblock 32 wie in Fig. 5B gezeigt, enthält die Einschränkung, dass die Anzahl L der Fahrspuren 23 in dem jeweiligen Straßensegment 26 konstant bleibt. Somit kann ein Straßenstück abgebildet werden, auf welchem sich lediglich die inhärenten Eigenschaften wie die Spurbreiten W ändern. In Figur 5B sind die Fahrspuren 23 mit Kennwerten -1, -2, +1, +2 gekennzeichnet, wobei das Vorzeichen eine Fahrtrichtung angibt und die Fahrspuren jeder Fahrtrichtung mit fortlaufenden natürlichen Zahlen 1, 2 nummeriert sind.

Ein Verbindungsblock 30, im Folgenden auch als B _C bezeichnet, wie in Fig. 5A dargestellt, beschreibt eine Verkehrssituation, in welcher sich die Anzahl L der Spuren 23 ändert und in der somit eine Zusammenführung oder Aufspaltung von Fahrspuren 23 modelliert werden kann. Daher wird der Verbindungsblock 30 gegenüber dem Straßenblock 32 durch eine Verbindungspermutation

ergänzt, welche sowohl geometrisch beschreibt, welche

Fahrspur 23 verschwindet bzw. erzeugt wird, als auch topologisch definiert, welche Fahrspuren 23 verbunden sind. Wie in Figur 5C dargestellt, wird für jede Fahrtrichtung eine individuelle geometrische Parametermatrix und eine

topologische Parametermatrix angegeben. Eine existierende Information

bzw. Verbundenheit von Fahrspuren 23 wird binär durch eine Eins und eine Nicht-Verbundenheit durch eine Null verdeutlicht, wie in Fig. 5C gezeigt. Auch in Figuren 5A und 5C sind die Fahrspuren 23 mit Kennwerten -1, -2, +1, +2 gekennzeichnet, wobei das Vorzeichen eine Fahrtrichtung angibt und die

Fahrspuren 23 jeder Fahrtrichtung mit fortlaufenden natürlichen Zahlen 1, 2 nummeriert sind. Beispielsweise ist es in der in Fig. 5A dargestellten Situation topologisch möglich, auf der linken Seite von der Fahrspur -1 auf die neue Fahrspur -2 zu wechseln, oder auf der vorhandenen Spur zu verbleiben. Diese topologische Information ist nicht gleichbedeutend mit einem einfachen

Spurwechselmanöver, was durch die Art der Fahrbahnmarkierung impliziert werden kann. Ein Verbindungsblock 30 kann daher als

definiert sein.

Zusätzlich zu diesen Einschränkungen an das Straßenmodell 30 kann ferner vorgegeben sein, dass zwischen zwei Straßenblöcken 32 ein Verbindungsblock 30 liegt, um gegebenenfalls die Unterschiede zwischen den Straßenblöcken 32 (z.B. bzgl. der Fahrspuranzahl L) auszugleichen. Sollte keine Änderungen nötig sein, kann der Verbindungsblock 30 als Spezialfall einen Straßenblock 32 darstellen.

Fig. 6A bis 6D illustrieren jeweils ein Kreuzungsmodell 34 gemäß einem

Ausführungsbeispiel der Erfindung. Im Speziellen zeigen Fig. 6A und 6B ein äußeres Kreuzungsmodell 36 des Kreuzungsmodells 34, Fig. 6C zeigt ein inneres Kreuzungsmodell38 des Kreuzungsmodells 34 und Fig. 6D zeigt eine Faktormatrix F des inneren Kreuzungsmodells aus Fig. 6C.

In der bisherigen Repräsentation einer Straßenkarte 14, wie etwa in Fig. 4A gezeigt, wurde eine Kreuzung 19 durch einen Knoten 11, welcher mit mehr als zwei Kanten 13 verbunden ist, dargestellt. Für die fahrspurgenaue Abbildung und/oder Modellierung einer Kreuzung 19 werden sowohl geometrische

Informationen über eine Kreuzungsfläche 37 und/oder eine befahrbare Fläche 37 bzw. Kreuzungsfläche 37, als auch topologische Informationen über die

Konnektivität der ein- und ausführenden Fahrspuren 23 und deren Fahrweg über die Kreuzungsfläche 37 benötigt. Dazu wird die fahrbahngenaue Straßenkarte 14 zunächst in wenigstens ein Kreuzungssegment 19a segmentiert und/oder ein

Kreuzungssegment 19a wird in der fahrbahngenauen Straßenkarte 14

identifiziert. Das Kreuzungssegment 19a wird dann in einem inneren

Kreuzungsmodell 38 und einem äußeren Kreuzungsmodell 36 modelliert, wie im Folgenden näher erläutert.

Das Kreuzungsmodell 34, im Folgenden auch mit bezeichnet, setzt sich aus

zwei verschiedenen Einzelmodellen zusammen. In Figur 6A und 6B ist ein äußere Kreuzungsmodell 36, im Folgenden auch mit bezeichnet, dargestellt.

Zur Initialisierung werden die Knoten 11 der fahrbahngenauen Straßenkarte 14 untersucht und anhand der verbundenen Kanten 13 werden Kreuzungsknoten 35 identifiziert. Da eine große Kreuzung 19 in der fahrbahngenauen Straßenkarte 14 durch mehrere Knoten 11 beschrieben sein kann, können mithilfe eines

Distanzwertes gegebenenfalls mehrere Knoten 11 zusammengefasst werden.

Das äußere Kreuzungsmodell 36 kann auf dem Zentrum der beteiligten Knoten 11 erzeugt werden. Anhand der identifizierten Kreuzungsknoten 35 kann direkt die Information entnommen werden, wie viele Straßen 17 mit der Kreuzung 19 verbunden sind. Für jede Straße 17 wird ein Kreuzungsarm A1-A4 erzeugt. Jeder Kreuzungsarm A1-A4 verfügt über einen Distanzparameter d, welcher den Abstand vom Zentrum zum Beginn der Kreuzungsfläche 37 bezüglich dieses Kreuzungsarmes A1-A4 beschreibt und einen Winkelparameter a, welcher relativ zu einer Referenzrichtung, beispielsweise der Ostrichtung, einen Drehwinkel definiert. Durch diese beiden Parameter d, a ist für jeden Kreuzungsarm A1-A4 ein Übergangspunkt von der Straße 17 in die Kreuzungsfläche 37 festgelegt.

Das innere Kreuzungsmodell 38, im Folgenden auch mit bezeichnet, ist in

Fig. 6C und 6D illustriert. Das innere Kreuzungsmodell 38 beschreibt die

Konnektivität der Fahrspuren 23. Jeder Kreuzungsarm A1-A4 verfügt dabei über die gleichen Informationen wie ein allgemeiner Straßenblock 32 des

Straßenmodells 28, wodurch die Geometrie der verbundenen Straßen 17 festgelegt ist. Zwischen jeder ein- und ausführenden Fahrspur 23 kann eine Verbindung bestehen, deren Verlauf durch ein kubisches Hermite Polynom beschrieben werden kann. Somit wird jede Verbindung durch einen Parameter C beeinflusst, der den Verlauf über die Kreuzungsfläche 37 vorgeben kann. Die Parameter C werden in der Faktormatrix F gespeichert, wie in Fig. 6D dargestellt, wobei ein Wert von Null angibt, dass die Verbindung nicht existiert. Durch die Identifizierung der äußeren Spurverläufe wird zusätzlich die Begrenzung der Kreuzungsfläche 37 definiert. Die Faktormatrix F kann dabei für jede

Fahrtrichtung und jeden Kreuzungsarm A1-A4 eine Zeile und eine Spalte aufweisen. Der Übersichtlichkeit halber sind unterschiedliche Fahrtrichtungen durch unterschiedliche Vorzeichen der Indizes in Fig. 6D illustriert. Ferner sind die Fahrspuren 23 der einzelnen Kreuzungsarme A1-A4 in Fig. 6D fortlaufend mit natürlichen Zahlen nummeriert.

Im Folgenden werden Details des in voranstehenden Figuren, insbesondere den Figuren 4A bis 6D, beschriebenen Straßenmodells 28, des Kreuzungsmodells 32 sowie das erfindungsgemäßen Verfahrens zur Erstellung der fahrspurgenauen Straßenkarte 22 beschrieben.

Zur Initialisierung der Modelle 28, 34 wird die fahrbahngenaue Straßenkarte 14 in Straßen 17 und Kreuzungen 19 aufgeteilt. Auf jeder Kreuzung 19 wird ein initiales Kreuzungsmodell 34 mit einem Armabstand von d _n = 25m erzeugt, wobei die Anzahl der angeschlossenen Straßen 17 und somit die

Winkelparameter a der Kreuzungsarme A1-A4 aus der Straßenkarte 14 bestimmt werden. Anschließend werden die Straßenmodelle 28 zwischen den Kreuzungen 19 generiert, wobei eine Straße 17 im Graph durch eine Kette {v _x , ... , v _Y } beschrieben wird. Im fahrspurgenauen Straßenmodell 28 wird auf jedem Knoten 11 ein Verbindungsblock 30 und dazwischen ein Straßenblock 32 erzeugt. Jede Straße 17 beginnt und endet mit einem Verbindungsblock 30, welcher gegebenenfalls die Unterschiede zwischen dem angrenzenden Straßenblock 32 und dem Kreuzungsanschluss korrigieren kann. Jede Straße 17 wird als zweispurig mit je einer Fahrspur 23 pro Fahrtrichtung initialisiert. Die Gesamtheit der α Straßenmodelle 28 und fr Kreuzungsmodelle 34 wird im Folgenden als bezeichnet.

Die initialisierten Modelle 28, 34, Φ stellen die aktuelle Konfiguration des Gesamtmodells dar. Die Parameter dieser Modelle sind die beschriebenen Eigenschaften bzw. Parameter der Straßenblöcke 32, der Verbbindungsblöcke 30, der inneren Kreuzungsmodelle 36 und der äußeren Kreuzungsmodelle 38. Diese sollen unter Verwendung einer RJMCMC Methode variiert werden, daher werden im Folgenden die möglichen Änderungsoperationen und die

entsprechenden Übergangskerne eingeführt. Für alle Modelle 28, 30, 32, 34, 36, 38 gibt es einerseits Änderungsoperationen, welche lediglich die Werte der vorhandenen Parameter beeinflussen und andererseits jene, welche die

Dimension eines Modells 28, 30, 32, 34, 36, 38 verändern.

Fig. 7A bis 7E illustrieren jeweils Änderungsoperationen 40, 41, 42, 43, 44, 46, 48, 50 gemäß einem Ausführungsbeispiel der Erfindung. Im Speziellen illustriert Fig. 7A linker Hand eine Einfügoperation 40 zum Einfügen eines

Verbindungsblocks 30 in einen Straßenblock 32 sowie eine Verschmelzoperation

41 zum Verschmelzen zweier Straßenblöcke 32 und eines Verbindungsblocks 30 zu einem Straßenblock 32 als reversible Änderungsoperation 41 zu der

Einfügoperation 40. Ferner illustriert Fig. 7A rechter Hand eine

Anpassungsoperation 42 zum Anpassen eines Parametrisierungswertes zur Parametrisierung einer Längserstreckung einer Straße 17. Fig. 7B illustriert eine

Hinzufügeoperation 43 zum Hinzufügen einer Fahrspur 23 und eine

Entfernungsoperation 44 zum Entfernen einer Fahrspur 23. Weiter zeigt Fig. 7C eine Abstandsanpassungsoperation 46 zum Anpassen eines Abstandes G zwischen Fahrspuren 23 entgegengesetzter Fahrtrichtung, Fig. 7D zeigt eine Breitenanpassungsoperation 48 zum Anpassen einer Breite W einer Fahrspur 23 und Fig. 7E zeigt eine Krümmungsanpassungsoperation 50 zur Anpassung einer Krümmung C einer Straße 17. Bezüglich eines Straßenmodells 28 werden die Änderungsoperationen 40, 41, 42, 43, 44, 46, 48, 50 nochmals in zwei Klassen unterteilt. Die Einfügoperation

40, die Verschmelzoperation 41 und die Anpassungsoperation 42 wie in Fig. 7A dargestellt, verändern das Straßenmodell 28 auf Block-Ebene, das heißt die individuellen Eigenschaften werden nicht verändert, sondern nur die Anzahl der Straßenblöcke 32 und Verbindungsblöcke 30 sowie deren räumliche

Ausdehnung werden verändert. Bei der Hinzufügeoperation 43 wird ein vorhandener Straßenblock 32 in zwei Straßenblöcke 32 und einen

Verbindungsblock 30 aufgeteilt. Die Entfernungsoperation 44 verbindet entsprechend eine derartige Konstellation und bildet mit der Hinzufügeoperation 43 ein reversibles Paar, dessen Auswahlwahrscheinlichkeiten so gewählt werden können, dass die erweiterte Detailed Balance Condition erfüllt ist. Bei der Anpassungsoperation 42 werden die Grenzen eines Straßenblocks 32 und/oder Verbindungsblocks 30 bzgl. der Parametrisierung des Straßenmodells 28 verändert. Die Hinzufügeoperation 43, die Entfernungsoperation 44, die

Abstandsanpassungsoperation 46, die Breitenanpassungsoperation 48 und die Krümmungsanpassungsoperation 50 verändern die Eigenschaften bzw.

Parameterwerte eines Straßenblockes 32. Die Parameterwerte eines

Verbindungsblockes 30 können nicht aktiv, sondern nur passiv verändert werden. Diese passen ihre Parameter den angrenzenden Straßenblöcken 32 an. Die Hinzufügeoperation 43 zum Hinzufügen einer Fahrspur 23 und eine

Entfernungsoperation 44 bilden dabei ebenfalls ein reversibles Paar, während die drei Adjustierungsoperationen42, 46, 50 lediglich die Werte der Parameter verändern.

Um keine der Änderungsoperationen 40, 41, 42, 43, 44, 46, 48, 50 bei der zufälligen Variierung von Parameterwerten des Straßenmodells 28 und/oder des Kreuzungsmodells 34 zu präferieren bzw. um jede der Änderungsoperationen 40,

41, 42, 43, 44, 46, 48, 50 mit gleicher Wahrscheinlichkeit auszuwählen, werden die Auswahlwahrscheinlichkeiten aller Änderungsoperationen 40, 41, 42, 43, 44. 46, 48, 50 als identisch angenommen:

Im Folgenden werden die einzelnen Änderungsoperationen 40, 41, 42, 43, 44, 46, 48, 50 genauer betrachtet. Der Übergang von der oberen Darstellung in Figur 7A zur Darstellung linker Hand der Fig. 7A erfolgt mittels der Einfügoperation 40. Die longitudinale

Ausdehnung des zu teilenden Straßenblocks 32, B _s ist über die Parametrisierung P des Straßenmodells mit den Werten mit der parametrisierten

Länge definiert. Zur Teilung werden zwei neue Werte

auf dieser Länge mit < u _; benötigt:

Die Akzeptanzwahrscheinlichkeit wird bestimmt als:

Die Jacobimatrix der Transformation lautet mit einer Determinante von 1, da die Matrix Dreiecksform hat.

Die Verschmelzoperation 41 kann als umgekehrter Fall angesehen werden. Die Konstellation Straßenblock 32, Verbindungsblock 30, Straßenblock 32 wird zusammengefasst, wobei für die Transformation keine neuen Komponenten benötigt, sondern berechnet werden. Die Konstellation ist in der Parametrisierung P des Straßenmodells 28 durch die Folge {p _a , _b ,p _c ,p _ci } dei\n\eri. Die

Akzeptanzwahrscheinlichkeit lautet:

Die Anpassungsoperation 42 beschreibt als Übergang zwischen der oberen Darstellung in Fig. 7A und der Darstellung rechter Hand in Fig. 7A. die

Veränderung eines der beiden Parametrisierungswerte eines Straßenblocks 32.

Der Parameter kann dabei maximal um die halbe parametrisierte Länge p, des Straßenblocks 32 verändert werden. Um keine Bewegungsrichtung zu präferieren wird die Suchfunktion als Zufallsbewegung realisiert: Um, wie in Fig. 7B dargestellt, eine neue Fahrspur mit Hinzufügeoperation 43 einzufügen, wird das Straßenmodell 28 um eine neue Fahrspurbreite einer Fahrspur 23 ergänzt. Die neue Spurbreite wird aus einer Normalverteilung gezogen, dessen Erwartungswert und Varianz sich aus straßenbaulichen Vorgaben ergeben. Diese können im Kontext des Szenarios bzw. der Art der Straße 17 bestimmt werden. Für die Transformation folgt:

Die Determinante der Jacobimatrix ist 1 und die Akzeptanzwahrscheinlichkeit ergibt sich zu: Die Akzeptanzwahrscheinlichkeit für die gegensätzliche Entfernungsoperation 44 wird entsprechend berechnet, wobei die Komponente u die Spurbreite der zu entfernenden Fahrspur 23 ist:

Die drei in Figuren 7C, 7D, 7E dargestellten Änderungsoperationen 46, 48, 50 verändern die vorhandenen Parameterwerte des Straßenmodells 28 und/des Kreuzungsmodells. Daher werden die entsprechenden Suchfunktionen als Gleichverteilung realisiert:

Da das Kreuzungsmodell 34 aus dem inneren Kreuzungsmodell 36 und dem äußeren Kreuzungsmodell 38 besteht, gibt es für jedes Untermodell 36, 38 verschiedene Änderungsoperationen. Wie in Figuren 6A und 6B dargestellt, beeinflussen die zwei Parameter Distanz d und Winkel a die Gestalt des äußeren Kreuzungsmodells 36. Die Anzahl der Kreuzungsarme A1-A4 wird bereits im Initialisierungsprozess aus der Straßenkarte 14 extrahiert und wird nicht mehr verändert. Somit werden zwei Änderungsoperationen definiert, welche die beiden Parameter d, a, aber nicht die Dimension des äußeren Kreuzungsmodells 36 verändern. Mit anderen Worten kann das äußere Kreuzungsmodell über eine Distanzparameteränderungsoperation und eine

Winkelparameteränderungsoperation verfügen. Daher werden Suchfunktionen als Gleichverteilung umgesetzt:

Im inneren Kreuzungsmodell 38 verfügt jeder Kreuzungsarm A1-A4 über einen Anschlussquerschnitt, welcher die gleichen Eigenschaften wie ein Straßenblock 32 hat. Da an jedem Kreuzungsarm A1-A4 ein Verbindungsblock 30

angeschlossen ist, reagiert dieser auf die Änderungen des Kreuzungsarmes Al-

A4 genau wie auf Änderungen eines Straßenblocks 32. Daher sind die

Änderungsoperationen zum Variieren der Anschlusseigenschaften identisch zu den bereits definierten eines Straßenblocks 32. Mit anderen Worten verfügt das innere Kreuzungsmodell 38 über die voranstehend beschriebenen

Änderungsoperationen 40, 41, 42, 43, 44, 46, 48, 50. Die Beeinflussung der

Faktormatrix F aus Figur 6D geschieht nicht durch eine RJMCMC Operation.

Fig. 8A und 8B illustrieren jeweils eine Anwendung einer Bewertungsmetrik gemäß einem Ausführungsbeispiel der Erfindung.

Für die Bewertungen wird einerseits ein Maß bezüglich der Übereinstimmung zwischen dem Straßenmodell 28 und/oder dem Kreuzungsmodell 34 und den Trajektoriendaten 27 in einem ersten Term und andererseits Vorwissen über die Modelle 28, 34 in einem zweiten Term berücksichtigt. Im Folgenden

werden diese Maße dargelegt.

Im ersten Schritt werden die Fahrzeugtrajektorien 27 auf die Fahrspuren 23 abgebildet. Dazu wird zunächst jede Mittellinie eines jeden Straßensegments 26 und jeder Kreuzung 19 in einen Graphen überführt, wobei die Mittellinie kleinschrittig mit Knoten 11 und Kanten 13 diskretisiert wird. Jeder Graph wird anschließend mit dem Douglas-Peucker-Algorithmus auf eine minimale Anzahl von Knoten 11 optimiert. Abschließend werden diese Graphen zu einer

Gesamtrepräsentation G fusioniert. Im nächsten Schritt wird für jede Trajektorie 27 ein Hidden-Markov-Modell (HMM) erzeugt, welches als versteckte Zustände die Kanten 13 des generierten

Graphen G und als emittierte Beobachtungen die Trajektorienpunkte hat. Das HMM wird mit Hilfe des Viterbi-Algorithmus gelöst und ergibt die

wahrscheinlichste Zuordnung eines jeden Messpunktes zu einer Fahrspur 23:

Als Bewertungsmaß werden der euklidische Abstand Y _d zwischen Trajektorie und Fahrspur gemäß Figur 8A, sowie der eingeschlossene Fahrtwinkel Y _a gemäß

Figur 8B ausgewertet. Zusätzlich wird ein Grenzwert für die minimale Anzahl an Durchfahrten eingeführt. Y _f beschreibt eine Sprungfunktion, welche bewirkt, dass

Fahrspuren mit zu wenigen Durchfahrten als nicht zuverlässig eingestuft und die Konfiguration abgelehnt wird. Allgemein ist die Definition der Funktion von der Gesamtzahl an Durchfahrten abhängig und kann gegebenenfalls so gestaltet werden, dass ein bestimmter Wert als normale Anzahl gewertet wird und eine Abweichung zur Abwertung führt. Der erste Term der Bewertungsmetrik ist somit gegeben durch:

Die Sprungfunktion zur Berücksichtigung der Durchfahrten ist dabei definiert als: wobei die Fahrspuren des Models, die Anzahl der Trajektorien, welche auf die χ-te Spur abgebildet wurden und η die minimal zu erreichende Anzahl an Durchfahrten beschreibt.

In Wird Vorwissen über die fahrspurgenauen Modelle 28, 34 berücksichtigt. Um die Straßensegmente und Kreuzungen 19 realistisch zu halten werden

Regularisierungsterme eingeführt, welche die Entwicklung der Eigenschaften beeinflussen. Reguliert werden dabei die Breite einer Fahrspur und die Länge eines Blocks: Bezüglich der Spurbreite w wird eine Normalverteilung angenommen, dessen Parameter im Kontext des Szenarios zu wählen sind. Kenngrößen zu

verschiedenen Szenarien können aus diversen Richtlinien zum Straßenbau entnommen werden.

Overfitting würde in diesem Verfahren durch eine Aufreihung sehr kurzer

Straßensegmente 26 entstehen. Um dem entgegen zu wirken wird eine

Minimallänge für ein Straßensegment eingeführt, welche durch die Regul mit Hilfe einer Sprungfunktion realisiert wird:

Nachdem alle Straßenmodelle 28 und Kreuzungsmodelle 34 initialisiert wurden, kann das Verfahren mithilfe der definierten RJMCMC Änderungsoperationen 40, 41, 42, 43, 44, 46, 48, 50 variiert werden. Dazu wird eine Zielfunktion

Ermittelt, welche sowohl die Übereinstimmung zwischen den Trajektoriendaten 27 und den Modellen 28, 34 in als auch vorhandenes Vorwissen, über zu

vermeidende und zu bestärkende Entwicklungen der Modelle 28, 34 in

bestimmt, wobei das Verhältnis zwischen den Daten- und dem

Modellwissen bestimmt.

Ein entsprechender Algorithmus zur Durchführung des erfindungsgemäßen Verfahrens kann in eine Aufwärmphase und eine Hauptphase unterteilt sein. In der Aufwärmphase können etwa nicht alle Änderungsoperationen40, 41, 42, 43, 44, 46, 48, 50 zur Verfügung stehen, sondern es können nur

Abstandsanpassungsoperation 46 der Straßenmodelle 28 bzw. Kreuzungsmodell 34 verwendet werden. Das mit dieser Maßnahme behandelte Problem tritt bei Straßen mit großer baulicher Trennung auf: Bei einer gleichberechtigten Auswahl der Operationen und einem initialen Modell ohne bauliche Trennung kann das Verfahren schnell ein Modell mit vielen Fahrspuren erzeugen. Es werden anschließend viele Iterationen dazu verwendet, die überflüssigen Fahrspuren 23 gegen eine bauliche Trennung zu tauschen. Durch die Aufwärmphase kann eine bessere initiale Schätzung der Trennung in sehr wenigen Iterationen erreicht werden.

Ferner kann das sogenannte Simulated Annealing Verfahren zum Einsatz kommen, dessen Zweck ist, die oben beschriebene Zielfunktion in Abhängigkeit der Laufzeit zu beeinflussen:

wobei die Funktion für jede Zelle eine Kühlfunktion mit

darstellt. Dies bewirkt, dass sich die Entstehung der Markov- Kette auf besser bewertete Regionen der Zielfunktion konzentrieren kann. In der Praxis bedeutet dies, dass Änderungsoperationen, welche die Bewertung verschlechtern mit fortschreitender Laufzeit seltener akzeptiert werden. Der Wert der Kühlfunktion sinkt, sobald eine vorgeschlagene Änderungsoperation abgelehnt wurde. Die Kühlfunktion ist dabei eine exponentiell abnehmende Funktion:

wobei der Parameter Λ so gewählt wird, dass eine bestimmte Anzahl an Schritten 5 benötigt wird, um eine Temperatur zu erreichen. Dazu wird die

Funktion in eine Berechnungsvorschrift in Abhängigkeit der Schrittanzahl überführt:

Ergänzend ist darauf hinzuweisen, dass„umfassend" keine anderen Elemente ausschließt und„eine" oder„ein" keine Vielzahl ausschließt. Ferner sei darauf hingewiesen, dass Merkmale, die mit Verweis auf eines der obigen

Ausführungsbeispiele beschrieben worden sind, auch in Kombination mit anderen Merkmalen anderer oben beschriebener Ausführungsbeispiele verwendet werden können. Bezugszeichen in den Ansprüchen sind nicht als Einschränkung anzusehen.