Map Matching and Map Conflation
Geographic Information Systems allow users to combine data from different sources. For example, by applying map matching algorithms, GPS trajectories can be combined with road network data to infer information on road names and adjoining links. Due to geometric errors of the trajectory and the road network data, map matching is difficult. Moreover, GPS may be unavailable, for example, due to occlusions in tunnels. A promising approach is therefore to equip cars with additional sensors, for example, cameras or laser scanners, which allow objects to be detected and to be matched with features in a geographic information system. Such objects can be, for example, poles of traffic signs or traffic lights.
We also develop algorithms for matching geospatial data sets of different scales, which due to map generalization may contain very different contents. For example, while in large-scale maps rivers are represented as area features, in small-scale maps they are represented as line features.
Vehicle Localization by Matching Triangulated Point Patterns.
In: O. Wolfson, D. Agrawal und C.-T. Lu, editors, Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM-GIS'09), November 4-6, 2009, Seattle, WA, USA, pages 344-351. 2009.
J.-H. Haunert and 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 and V. Paelke, editors, Advances in GIScience: Proceedings of the 12th AGILE International Conference on Geographic Information Science, June 2-5, 2009, Hannover, Germany, series Lecture Notes in Geoinformation and Cartography, pages 56-63. Springer, Berlin, Germany, 2009.
B. Kieler, W. Huang, J.-H. Haunert and 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.