Algorithmen für urbane Analysen

In modernen Städten werden riesige Mengen an Daten erfasst. Dabei sind sowohl die Sammlung als auch die Nutzung dieser Daten zu Analysezwecken wichtige Aufgaben. In unserer Forschung konzentrieren wir uns auf zwei Hauptthemen: (1) Die Bewegungsanalyse auf der Grundlage von Trajektoriendaten und (2) die Entwicklung effizienter Messstrategien für die Erzeugung vollständiger Stadt- und Gebäudemodelle.

In den letzten Jahrzehnten wurde eine Fülle von freiwillig zur Verfügung gestellten Trajektoriendaten öffentlich zugänglich gemacht, was durch die zunehmende Verbreitung von mit GNSS-Empfängern (Global Navigation Satellite System) ausgestatteten mobilen Geräten begünstigt wurde. Allein das OpenStreetMap-Projekt hat in den letzten 17 Jahren weltweit etwa 2,43 Millionen GNSS-Trajektorien gesammelt und veröffentlicht. Solche Datensätze eröffnen zahlreiche Anwendungsmöglichkeiten, z. B. die Extraktion von Bewegungsmustern, die Erstellung von Karten, das sogenannte „Social Routing“ oder die Analyse und Vorhersage von Verkehrsströmen. Der Umgang mit riesigen Trajektoriendatensätzen ist jedoch mit vielen Herausforderungen verbunden. Dies gilt vor allem für freiwillig zur Verfügung gestellte Trajektoriendatensätze, die häufig hinsichtlich der Genauigkeit des Standorts, der zugrunde liegenden Verkehrsart oder der Bewegungsabsicht sehr heterogen sind.

Darüber hinaus ist die automatische Interpretation und Rekonstruktion detaillierter städtischer Strukturen sowie die Generierung detaillierter Gebäudeinformationsmodelle (Building Information Models, BIM) ein zurzeit sehr dynamisches Forschungsgebiet. Die Generierung solcher Modelle für bereits bestehende Gebäude, also sogenannte „as-built BIMs“, ist aufgrund ihrer Komplexität besonders schwierig. Um diese Modelle effizient und kostengünstig erstellen zu können, bedarf es intelligenter Strategien zur Gewinnung der gewünschten Informationen, beispielweise unter Zuhilfenahme von möglichst wenigen Beobachtungen.

Ausgewählte Arbeiten

Trajektorien sind personenbezogene Daten und können sensible Informationen über die aufzeichnende Person preisgeben. Daher muss die Privatsphäre geschützt werden. Die Anonymisierung zielt darauf ab, persönlich identifizierbare Informationen aus den Daten zu entfernen. In diesem Zusammenhang haben wir Algorithmen entwickelt, um sensible Haltepunkte entlang der Trajektorie zu schützen, wie z. B. die Wohnung von Personen [1,2].

[1] Anna Brauer, Ville Mäkinen, Axel Forsch, Juha Oksanen, and Jan-Henrik Haunert. My home is my secret: concealing sensitive locations by context-aware trajectory truncation. International Journal of Geographical Information Science, 36(12):2496-2524, 2022.

[2] J.-H. Haunert, D. Schmidt, and M. Schmidt. Anonymization via clustering of locations in road networks (short paper). In Proc. 11th International Conference on Geographic Information Science (GIScience' 21). 2021. doi:10.25436/E2CC7P

Eine rohe Trajektorie wird in der Regel als eine mit einem Zeitstempel versehene Abfolge von Ortsmessungen dargestellt. Um trajektorienbasierte Anwendungen zu ermöglichen, müssen die rohen Trajektorien in entsprechender Weise verarbeitet werden. Dazu gehört in der Regel ein Abgleich mit der Karte, das sogenannte „Map Matching“, bei dem der Pfad im Netz identifiziert wird, der höchstwahrscheinlich zu der gegebenen Bewegungssequenz geführt hat. Das „Map Matching“ trägt dazu bei, das Rauschen zu reduzieren, welches z.B. durch Messungenauigkeiten der Sensoren entsteht, und ermöglicht weitere netzwerkbasierte Analysen. Das „Map Matching“ ist eine besondere Herausforderung, wenn das zugrunde liegende Straßennetz unvollständig ist [3] oder die Trajektorien nicht vollständig auf das zugrunde liegende Netz beschränkt sind [4].

[3] J.-H. Haunert and B. Budig. An algorithm for map matching given incomplete road data. In Proc. 20th International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL' 12). New York, NY, USA, 510–513, 2012. doi:10.1145/2424321.2424402

[4] Timon Behr, Thomas C. van Dijk, Axel Forsch, Jan-Henrik Haunert, and Sabine Storandt. Map matching for semi-restricted trajectories. In Proc. 11th International Conference on Geographic Information Science (GIScience' 21). 2021. doi:10.4230/LIPIcs.GIScience.2021.II.12

Routenplanungstools spielen in der modernen Mobilität eine wesentliche Rolle. Sie werden nicht nur im Pendlerverkehr eingesetzt, um den bestmöglichen Weg von einem Ort zum anderen zu finden, sondern auch für Freizeitaktivitäten, wie z.B. Rundfahrten mit dem Fahrrad, die am selben Ort beginnen und enden. Für beide Anwendungen ist es von entscheidender Bedeutung, das Optimierungsziel so zu wählen, dass es die Präferenzen der Nutzer*innen widerspiegelt. Diese Präferenzen können mit Hilfe von Trajectory-Mining-Ansätzen [5-7] aus den Trajektoriendatensätzen abgeleitet werden.

[5] J. Oehrlein, A. Förster, D. Schunck, Y. Dehbi, R. Roscher, and J.-H. Haunert. Inferring routing preferences of bicyclists from sparse sets of trajectories. In volume IV-4/W7 of ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Proc. 3rd International Conference on Smart Data and Smart Cities, pages 107-114. 2018

[6] J. Oehrlein, A. Förster, D. Schunck, Y. Dehbi, R. Roscher, and J.-H. Haunert. Inferring routing preferences of bicyclists from sparse sets of trajectories. In volume IV-4/W7 of ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Proc. 3rd International Conference on Smart Data and Smart Cities, pages 107-114. 2018.

[7] Axel Forsch, Johannes Oehrlein, Benjamin Niedermann, and Jan-Henrik Haunert. Inferring routing preferences from user-generated trajectories using a compression criterion. Journal of Spatial Information Science, 0(0):0, 2023. Accepted for publication on 15 Mar 2023.

Die Ergebnisse der einzelnen Verarbeitungsschritte sind oft schwer zu interpretieren, so dass geeignete Visualisierungen erforderlich sind. Isochronenkarten zeigen zum Beispiel das erreichbare Gebiet von einem bestimmten Ausgangspunkt innerhalb einer bestimmten Reisezeit. Wir haben Algorithmen für die automatische Generierung von Isochronen in multimodalen Verkehrsnetzen entwickelt [8], die eine einfache Analyse von Netzwerkdefiziten ermöglichen. Das Konzept der Isochronen kann für Routing-Präferenzen übernommen werden, um zu zeigen, wie gut erreichbar eine Region für bestimmte Routing-Profile ist.

[8] Axel Forsch, Youness Dehbi, Benjamin Niedermann, Johannes Oehrlein, Peter Rottmann, and Jan-Henrik Haunert. Multimodal travel-time maps with formally correct and schematic isochrones. Transactions in GIS, 25(6):3233-3256, 2021.

Im Zusammenhang mit der Erstellung von Stadt- und Gebäudemodellen hat das terrestrische Laserscanning immer mehr an Bedeutung gewonnen. Die Planung der Vermessungskampagne ist dabei eine entscheidende Aufgabe, da die Auswahl der Standpunkte die Qualität der resultierenden Punktwolke stark beeinflusst, z.B. ob ein kompletter Scan der gesamten Szenerie durchgeführt wurde und die einzelnen Scans mit ausreichender Qualität miteinander registriert werden können. Außerdem sollen aus ökonomischen Gründen so wenig Standpunkte wie möglich für die Messung verwendet werden. Wir haben daher Algorithmen entwickelt, die die minimale Anzahl von Standpunkten unter (1) Gewährleistung der vollständigen Abdeckung der Szenerie und (2) Garantie einer erfolgreichen anschließenden softwarebasierten Registrierung ermitteln. Dafür wenden wir gemischt-ganzzahlige lineare Programmierung (Mixed Integer Linear Programming / MILP) an. Diese Algorithmen bieten ein großes Potenzial, sowohl für statisches Laserscanning [9] als auch für Stop-and-Go-Scanning in Kombination mit einer optimalen Routenplanung [10].

[9] Youness Dehbi, Johannes Leonhardt, Johannes Oehrlein, and Jan-Henrik Haunert. Optimal scan planning with enforced network connectivity for the acquisition of three-dimensional indoor models. ISPRS Journal of Photogrammetry and Remote Sensing, 180:103-116, 2021.

[10] J. Knechtel, L. Klingbeil, J.-H. Haunert, and Y. Dehbi. Optimal position and path planning for stop-and-go laserscanning for the acquisition of 3d building models. ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, V-4-2022:129-136, 2022.

Building Information Models bestehen nicht nur aus der grundlegenden Struktur des Gebäudes, also aus den Wänden und Fenstern, sondern auch aus weiterführenden Infrastrukturinformationen, die jedoch meist in der Wand verborgen sind, z.B. dem elektrischen Leitungsnetz. Die Anreicherung eines BIM mit solchen Informationen ist aufgrund des hohen Messaufwands eine Herausforderung, da zumeist punktuelle Messungen, z.B. mithilfe eines Leitungsdetektors, erforderlich sind. Unter Verwendung von Normen und Standards kann erneut gemischt-ganzzahlige lineare Programmierung (MILP) angewendet werden, um eine Hypothese über den Verlauf der elektrischen Leitungen nur auf der Grundlage von leicht beobachtbaren Strukturen wie Lichtschaltern und Steckdosen zu erstellen. Darüber hinaus haben wir verschiedene „Reasoning“-Strategien entwickelt und getestet, um diese Hypothese mit möglichst wenigen Messungen eindeutig zu bestätigen [11].