Methoden für den Einsatz von Kreisbogensplines zur Darstellung hochgenauer digitaler Karten
Theoretische Informatik
Zusammenfassung der Projektergebnisse
Im Rahmen dieses Projekts wurden Methoden für den Einsatz von Kreisbogensplines für hochgenaue digitale Karten entwickelt, die eine automatische Kartenerstellung mit für die Praxis tauglichen Skalierbarkeitseigenschaften erlauben. Basierend auf dem SMAP-Verfahren, das Punktsequenzen innerhalb eines Toleranzkanals mit Kreisbogensplines minimaler Segmentzahl approximiert, wurden geeignete Ansätze und Grundlagen erforscht: Neben den notwendigen Erweiterungen des Verfahren für Selbstüberschneidungen, Verzweigungen und zyklische Strukturen zur Modellierung komplexerer Straßenverläufe, standen besonders zwei Themen im Fokus: Stabilität und Robustheit des Algorithmus und die präzise Repräsentation von Krümmungsverläufen. Der original veröffentlichte Algorithmus zur Berechnung eines SMAPs hatte numerische Gesichtspunkte in entscheidenden Berechnungsschritten kaum adressiert. Ein alternativer algorithmischer Zugang für eben jene Teile behebt indes diese Lücken: Statt des Versuchs der direkten Berechnung eines optimalen Segments und somit der Gefahr eines Fehlschlagens aus numerischen Gründen, wird jenes iterativ ermittelt: Es werden sukzessive Kandidaten solange optimiert bis sie dem gesuchten Segment entsprechen. Der resultierende iterative Algorithmus ermöglicht die numerisch stabile Berechnung eines SMAPs mit derselben worstcase-Komplexität wie der Original-Algorithmus. In der Praxis ist die Laufzeit sogar signifikant geringer. Erstaunlicherweise stellte sich heraus, dass der neuartige Zugang eine eindeutige Lösung mit lokalen Optimalitätseigenschaften hinsichtlich des Krümmungsverlaufs ermöglicht. Die ohnehin positiven Krümmungseigenschaften des SMAPs aufgrund seiner Segmentzahlminimalität konnten so noch wesentlich verbessert werden, was auch in praktischen Tests bestätigt werden konnte. Damit konnte die Nutzbarkeit der resultierenden digitalen Karte qualitativ aufgewertet werden: Anwendungen, die neben einer effizienten und hochgenauen Darstellung eine möglichst präzise Krümmungsschätzung benötigen, können davon profitieren. Beispielsweise könnten darauf basierend Trajektorien autonomer Fahrzeuge mit einem natürlichen und ruckfreien und damit angenehmen Fahrgefühl generiert werden. Besonders auf vergleichsweise kurvigen Streckenabschnitten könnten diese Vorteile zu tragen kommen. Es ist geplant, die Praxistauglichkeit der gewonnenen Erkenntnisse im Rahmen eines DFG-Erkenntnistransferprojekts gemeinsam mit einem Industriepartner zu untersuchen.
Projektbezogene Publikationen (Auswahl)
- Generation of high precision digital maps using circular arc splines. Intelligent Vehicles Symposium (IV), IEEE, 2012
A. Schindler, G. Maier, F. Janda
- Minimum description length arc spline approximation of digital curves. 19th IEEE International Conference on Image Processing, IEEE, 2012
G. Maier, F. Janda, A. Schindler
- Approximation of a closed polygon with a minimum number of circular arcs and line segments. Computational Geometry, 46.3: 263-275, 2013
G. Maier, G. Pisinger
- Evaluation of a Mapping Strategy Based on Smooth Arc Splines for Different Road Types. 16th International IEEE Conference on Intelligent Transportation Systems (ITSC 2013), IEEE, 2013
S. Brummer, F. Janda, G. Maier, A. Schindler
- Optimal arc-spline approximation with detecting straight sections. International Conference on Computational Science and Its Applications, Springer Berlin Heidelberg, 2013
G. Maier, A. Schindler, F. Janda, S. Brummer
- Optimal arc spline approximation. Computer Aided Geometric Design, 31.5: 211-226, 2014
G. Maier
(Siehe online unter https://doi.org/10.1016/j.cagd.2014.02.011) - Numerically stable computation of circular visibility
S. Brummer, G. Maier, T. Sauer
