SMAP
Kreisbogensplines zur Darstellung hochgenauer digitaler Karten
Methoden für den Einsatz von Kreisbogensplines zur Darstellung hochgenauer digitaler Karten
Kreisbogensplines und digitale Karten
Kreisbogensplines, also Kurven bestehend aus Kreisbögen und Strecken, stellen eine Offset- und Abstandsberechnung in geschlossener Form bereit und erlauben eine kompakte Repräsentation. In jüngsten Forschungsprojekten (Ko-PER) hat sich daher ihr Einsatz zur Repräsentation von Fahrbahnverläufen in hochgenauen digitalen Karten bewährt.
SMAP – Minimaler Speicherbedarf bei frei wählbarer Genauigkeit
Für die Erzeugung digitaler Karten liegen meist zunächst Fahrbahnmarkierungen als Punktlisten vor, die etwa aus Kamerabildern extrahiert wurden (vgl. Abb., Kasten 1). Für eine effiziente Weiterverarbeitung werden einzelne Fahrstreifen jedoch als Kurven benötigt (vgl. Abb., Kasten 3). Für diese Passkurven wird neben einer hohen Approximationsgenauigkeit eine kompakte Darstellung angestrebt.
Der am FORWISS entwickelte SMAP-Algorithmus (G. Maier, Smooth Minimum Arc Paths) löst dieses Mehrzieloptimierungsproblem in optimaler Weise: Unter Einhaltung einer einstellbaren, maximalen Abweichung von den Eingangspunkten wird ein Kreisbogenspline mit der beweisbar kleinstmöglichen Anzahl an Kreisbögen und Strecken (kurz: Segmenten) generiert. Durch einen so genannten Toleranzkanal (vgl. Abb., Kasten 2) der sich durch eine Start- und eine Zielstrecke auszeichnet, wird die vom Benutzer gewählte Genauigkeit kontrolliert. Ein Smooth Minimum Arc Path (SMAP) ist ein Kreisbogenspline, der innerhalb des Toleranzkanals die Start- und Zielstrecke miteinander verbindet und die kleinstmögliche Anzahl an Segmenten besitzt.
Im Gegensatz zu anderen Ansätzen aus der Literatur werden dabei die Breakpoints automatisch berechnet und werden nicht aus einer vordefinierten, diskreten Menge an Punkten gewählt. Diese „echte“ Minimalität führt zu einer deutlichen Reduktion der resultierenden Segmentzahl und damit des Speicherbedarfs. Das SMAP-Verfahren lässt sich aufgrund einer Charakterisierung der Lösungen mittels „alternierender Folgen“ effizient algorithmisch umsetzen. Dies sind abwechselnd linke und rechte Randberührungen der Kurve an den Kanal.
Weitere Anpassungen für den Kartenbau
Für eine komplett automatisierte Erstellung digitaler Karten, die über einzelne Fahrstreifen hinausgeht, müssen auch zyklische Strukturen, Verzweigungen und Selbstüberschneidungen berücksichtigt werden. Zudem gilt es das oben beschriebene Vorgehen um eine zusätzliche Glättung hinsichtlich des Quadratmittelfehlers und weitere Nebenbedingungen wie etwa Krümmungsbeschränkungen zu erweitern. Im Rahmen des DFG-Projekts „Methoden für den Einsatz von Kreisbogensplines zur Darstellung hochgenauer digitaler Karten“ (http://gepris.dfg.de/gepris/projekt/225923277) soll eine verallgemeinerte Theorie der Kreisbogenspline-Passung entwickelt werden, die den abgeleiteten algorithmischen und modelltheoretischen Herausforderungen genügt.
