Zuordnung und geometrischer Abgleich von Geodaten
In Geographischen Informationssystemen werden oft Daten unterschiedlichster Herkunft miteinander verknüpft. Beispielsweise werden beim Map Matching GPS-Trajektorien mit Straßendaten verknüpft, um für eine zurückgelegte Route Informationen über Straßennamen und abgehende Straßen zu gewinnen. Die Schwierigkeit des Problems ergibt sich aus der geometrischen Ungenauigkeit der Daten. Hinzu kommt, dass GPS durch Abschattungen (z.B. in Tunneln) nicht überall verfügbar ist. Ein vielversprechender Ansatz für die Fahrzeugnavigation besteht darin, Fahrzeuge mit zusätzlichen Sensoren auszustatten, die es ermöglichen, genaue Zuordnungen mit Objekten herzustellen, welche in Geoinformationssystemen erfasst sind. Dies können beispielsweise Pfähle von Verkehrsschildern oder Fahrbahnmarkierungen sein.
Außerdem befassen wir uns mit ähnlichen Zuordnungsproblemen, die bei der Verknüpfung von Datensätzen unterschiedlicher Detailgrade auftreten.
Vehicle Localization by Matching Triangulated Point Patterns.
In: O. Wolfson, D. Agrawal und C.-T. Lu (Herausgeber): Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM-GIS'09), November 4-6, 2009, Seattle, WA, USA, Seiten 344-351. 2009.
J.-H. Haunert und C. Brenner.
[doi] [PDF] [BibTeX]
We consider the problem of localizing a moving vehicle based on landmarks that were detected with a vehicle-mounted sensor. Landmarks are represented as points; correspondences of these points with the ones in a reference database are searched based on their geometric configurations. More specifically, we triangulate the landmark points and we match the obtained triangles with triangles in a reference database according to their geometric similarity. We maximize the number of triangle matches while considering the topological relations between different triangles, for example, if two triangles share an edge then the corresponding reference triangles must share an edge. Our method exploits that the observed points typically form a certain configuration: They appear at a limited distance from the vehicle's trajectory, thus the typical point pattern has a large extent in the driving direction and a relatively small lateral extent. This characteristic allows us to triangulate the observed point set such that we obtain a triangle strip (a sequence of triangles) in which each two consecutive triangles share one edge and each triangle connects three points that are relatively close to each other, that is, the triangle strip appropriately defines a neighborhood relationship for the landmarks. The adjacency graph of the triangles becomes a path; this allows for an efficient solution of our matching problem by dynamic programming. We present results of our method with data acquired with a mobile laser scanning system. The landmarks are objects of cylindric shape, for example, poles of traffic signs, which can be easily detected with the employed sensor. We tested the method with respect to its running time and its robustness when imposing different types of errors on the data. In particular, we tested the effect of non-rigid distortions of the observed point set, which are typically encountered during dead reckoning. Our matching approach copes well with such errors since it is based on local similarity measures of triangles, that is, we do not assume that a global non-rigid transformation between the observed point set and the reference point set exists.
Matching River Datasets of Different Scales.
In: M. Sester, L. Bernard und V. Paelke (Herausgeber): Advances in GIScience: Proceedings of the 12th AGILE International Conference on Geographic Information Science, June 2-5, 2009, Hannover, Germany, Reihe Lecture Notes in Geoinformation and Cartography, Seiten 56-63. Springer, Berlin, Germany, 2009.
B. Kieler, W. Huang, J.-H. Haunert und J. Jiang.
[doi] [PDF] [BibTeX]
In order to ease the propagation of updates between geographic datasets of different scales and to support multi-scale analyses, different datasets need to be matched, that is, objects that represent the same entity in the physical world need to be identified. We propose a method for matching datasets of river systems that were acquired at different scales. This task is related to the problem of matching networks of lines, for example road networks. However, we also take into account that rivers may be represented by polygons. The geometric dimension of a river object may depend, for example, on the width of the river and the scale. Our method comprises three steps. First, in order to cope with geometries of different dimensions, we collapse river polygons to centerlines by applying a skeletonization algorithm. We show how to preserve the topology of the river system in this step, which is an important requirement for the subsequent matching steps. Secondly, we perform a pre-matching of the arcs and nodes of the line network generated in the first step, that is, we detect candidate matches and define their quality. Thirdly, we perform the final matching by selecting a consistent set of good candidate matches. We tested our method for two Chinese river datasets of the same areal extent, which were acquired at scales 1:50 000 and 1:250 000. The evaluation of our results allows us to conclude that our method seldom yields incorrect matches. The number of correct matches that are missed by our method is quite small.