Geometry-based railway track extraction from OpenStreetMap data

Abstract

Geografische Datenbanken stellen meist lineare Elemente wie Flüsse, Straßen und Eisenbahnstrecken als Polylines, Sequenzen von Punkten, die diese Elemente approximieren, dar. In Datensätzen wie beispielsweise von OpenStreetMap (OSM), werden Eisenbahnstrecken als ungeordnete Mengen von Polylines gespeichert. Dies kann für Anwendungen, die eine sequenzielle Verarbeitung dieser Merkmale erfordern, in weiterer Folge zu Herausforderungen führen. Diese Diplomarbeit behandelt das Problem der Transformation ungeordneter Mengen von Streckensegmenten in eine einzelne Lösungsmenge. Die aus einem Algorithmus resultierende Lösungsmenge soll alle Eisenbahnstrecken aus der Eingabemenge darstellen, wobei jedes Element der Lösungsmenge eine durchgehende Polyline ist. Der Algorithmus soll ganze Eisenbahnstrecken möglichst genau aus der Eingabemenge erkennen, die Eisenbahnstrecken der realen Welt akkurat repräsentieren und dabei möglichst stabil gegen Bearbeitungsfehler sein. Wir definieren einen Prozess, der Streckensegmente in einem zweidimensionalen Koordinatensystem ordnet und verbindet, um dies zu bewerkstelligen. Angestoßen durch Anforderungen der Track Machines Connected GmbH (tmc), einem Unternehmen für Eisenbahndigitalisierung, für eines ihrer Software-Projekte, präsentiert diese Arbeit einen rein geometriebasierten Ansatz zur Lösung des Problems. Die vorgestellten heuristischen Algorithmen nutzen Strategien wie das Verbinden von Streckensegmenten und eine Approximierung der Wahrscheinlichkeiten von Streckensegmentverbindungen. Dabei wird das Problem auf ein Graphenproblem, das Maximum Weighted Path Cover Problem, reduziert und gelöst. Zu den behandelten Themen und Schlüsselfragen gehören die Charakterisierung problematischer Eingabe-Instanzen, die Beschreibung und Darstellung der algorithmischen Verfahren und ein Vergleich der Algorithmen mit unterschiedlichen Parametern, hinsichtlich Lösungsqualität und Laufzeiteffizenz. Die Ergebnisse dieser Arbeit zeigen, dass der hier präsentierte heuristische Algorithmus eine signifikante Verbesserung gegenüber einer einfachen Proof-of-Concept Lösung darstellt.

Geographic databases commonly represent linear features like rivers, roads, and railway tracks as polylines, which are sequences of points approximating these features. However, in datasets like OpenStreetMap (OSM), railway tracks are stored as unordered sets of polylines, posing challenges for applications requiring sequential processing of these features. This thesis addresses the problem of transforming unordered sets of track segments into a single set of polylines, the solution set, to accurately represent real-world railway tracks while being robust to editing errors. We define a process to connect and order track segments in a two-dimensional coordinate system to accurately represent railway systems. Motivated by the needs of Track Machines Connected GmbH (tmc), a railway digitalization company, this thesis proposes a geometry-based approach to solve the problem. The introduced heuristic algorithms utilize strategies such as track segment merging and defining weight functions to determine the probability of segment connections. A reduction of this problem to a graph problem, the Maximum Weighted Path Cover Problem, is used in our approach to solve the problem. Key questions addressed include characterizing problematic input instances, defining the algorithmic methods, metrics for solution quality, and performing an algorithm comparison of the algorithms, with different parameters, in terms of solution quality and runtime performance. The results of this work demonstrate that the heuristic algorithm presented in this thesis constitutes a significant improvement over a simple proof-of-concept solution.