Details
| Original language | English |
|---|---|
| Title of host publication | 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2009 |
| Pages | 344-351 |
| Number of pages | 8 |
| Publication status | Published - 4 Nov 2009 |
| Event | 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2009 - Seattle, United States Duration: 4 Nov 2009 → 6 Nov 2009 |
Publication series
| Name | GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems |
|---|
Abstract
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.
Keywords
- Dynamic programming, Point pattern matching, Positioning
ASJC Scopus subject areas
- Earth and Planetary Sciences(all)
- Earth-Surface Processes
- Computer Science(all)
- Computer Science Applications
- Mathematics(all)
- Modelling and Simulation
- Computer Science(all)
- Computer Graphics and Computer-Aided Design
- Computer Science(all)
- Information Systems
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2009. 2009. p. 344-351 (GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › peer review
}
TY - GEN
T1 - Vehicle localization by matching triangulated point patterns
AU - Haunert, Jan Henrik
AU - Brenner, Claus
PY - 2009/11/4
Y1 - 2009/11/4
N2 - 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.
AB - 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.
KW - Dynamic programming
KW - Point pattern matching
KW - Positioning
UR - http://www.scopus.com/inward/record.url?scp=74049087390&partnerID=8YFLogxK
U2 - 10.1145/1653771.1653819
DO - 10.1145/1653771.1653819
M3 - Conference contribution
AN - SCOPUS:74049087390
SN - 9781605586496
T3 - GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
SP - 344
EP - 351
BT - 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2009
T2 - 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2009
Y2 - 4 November 2009 through 6 November 2009
ER -