Real-Time Map Matching with a Backtracking Particle Filter Using Geospatial Analysis
<p>Overview of the structure of the developed algorithm that uses particle filtering as a map-matching process. Starting from a position derived, for example, through a location fingerprint, odometry data from inertial measurements are transferred to polar coordinates, resulting in the estimation of the propagated position. This estimation is improved via spatial constraints and further corrected by additional information from the location fingerprint, resulting in the final position estimate, which serves as the starting point for the next propagation step.</p> "> Figure 2
<p>Overview of some of the geospatial analyses used in GeoPandas, with <span class="html-italic">distance</span> shown in (<b>a</b>), <span class="html-italic">spatial join</span> in (<b>b</b>), <span class="html-italic">query by attribute</span> in (<b>c</b>), and <span class="html-italic">buffer</span> in (<b>d</b>).</p> "> Figure 3
<p>Overview of the backtracking process. A particle with valid trajectory is randomly chosen (<b>a</b>). Particles are randomly created in a specified radius (<b>b</b>). Newly created particles with invalid trajectories (red) are discarded until a particle with a valid trajectory (green) is found (<b>c</b>) and is accepted as a new particle (<b>d</b>).</p> "> Figure 4
<p>Overview of the particle filter algorithm. The initial position and heading, derived from the location fingerprint, is used for the initialization of the particles, which are then propagated according to the odometry output. The particles are then filtered in the correction/update according to spatial constraints, leading to a final location estimation, which is further improved by the location fingerprint. Via the backtracking process, the number of valid particles is increased up to the original amount of particles by considering spatial constraints. Next, the next propagation step starts.</p> "> Figure 5
<p>Overview of the used filtering methods, with the cm in (<b>a</b>), cr in (<b>b</b>), and cl in (<b>c</b>).</p> "> Figure 6
<p>Floor plans of the ground floor (<b>a</b>), 1st floor (<b>b</b>), and 4th floor (<b>c</b>), with the blue lines representing the routing edges.</p> "> Figure 7
<p>Ground truth points (orange) of the “eight path”; the red dot is the starting position and the green dot is the finish.</p> "> Figure 8
<p>Ground truth points (orange) of the <span class="html-italic">zerotofour</span> path in (<b>a</b>–<b>c</b>); the red dot is the starting position and the green dot is the finish.</p> "> Figure 9
<p>CDF of the positioning error of the <span class="html-italic">eight</span> path with a step length correction of 0.1 m for the backtracking PF and the PDR with a step length correction of 0.1 m.</p> "> Figure 10
<p>Part of the trajectory of the <span class="html-italic">eight</span> path, that wrongly proceeds in the “gallery”, when using the weighting by routing support method, where black arrows indicate the walking direction and the green points represent the position estimates for each step.</p> "> Figure 11
<p>Example of the trajectory correction (from (<b>a</b>–<b>d</b>)) through the backtracking functionality, where the green dots represent the valid, propagated particles, and the blue dot is the resulting position estimate. First, most particles took a “wrong” path (<b>a</b>), continuously getting deleted when trying to pass the wall (<b>a</b>–<b>c</b>). While more particles are getting deleted, more particles with plausible trajectories are getting created through the backtracking process, until all particles are recovered and now only represent positions with reasonable trajectories again (<b>d</b>).</p> "> Figure 12
<p>Effect of the support through the weighting by routing support on the deviated trajectory.</p> "> Figure 13
<p>CDF of the positioning error of the <span class="html-italic">zerotofour</span> path with a step length correction of 0.2 m for the backtracking PF and the PDR with a step length correction of 0.2 m.</p> "> Figure 14
<p>CDF of the positioning error of the <span class="html-italic">eight</span> path without step length correction for the backtracking PF and the PDR without step length correction.</p> "> Figure 15
<p>Trajectory (green dots) from the cl method for the <span class="html-italic">eight</span> path without step length correction for the backtracking PF.</p> "> Figure 16
<p>CDF of the positioning error of the <span class="html-italic">zerotofour</span> path with a step length correction of 0.15 m for the backtracking PF and the PDR with a step length correction of 0.15 m.</p> ">
Abstract
:1. Introduction
2. Methodology
2.1. Geospatial Analysis
- Intersects returns True if the boundary or interior of the object intersect in any way with those of the other;
- Contains returns True if no points of the other geometry lie in the exterior of this geometry and at least one point of the other geometry’s interior lies in the interior of this geometry. A line’s endpoints are its boundary and are therefore not contained;
- Within returns True if this object’s boundary and interior intersect only with the interior of the other (not its boundary or exterior), making it the ‘inverse’ of contains;
- Touches returns True if the given objects’ boundaries have at least one point in common, but their interiors do not intersect with any part of the other.
- Distance returns the direct distance between geometries. It is also the orthogonal distance between a point and a line feature or edge, if the orthogonal projection of the point exists (see Figure 2a). Here, the distance from the corners of polygon B and the edges of the polygons A and C is simultaneously the orthogonal distance, whereas the distance between the corners of A and C is not);
- Spatial join is used to merge geometric objects based on their spatial relationships, as shown in Figure 2b. Spatial relationships, that can be used as requirements for the spatial join include intersects, contains, within, or touches;
- Query by attribute returns all objects of the given GeoDataFrame that hold the queried attribute value, as shown in Figure 2c, where all objects with the Type value of B are selected and marked in blue;
- Buffer generates a representation of all points in a given distance of the geometry as a polygon. In Figure 2d, the resulting buffer-polygons around a given line and a square-shaped polygon are displayed in green.
2.2. Backtracking Particle Filter
2.3. Location Fingerprint
3. Map Matching Based on a Backtracking Particle Filter
Algorithm 1 Map-matching algorithm with backtracking PF |
Input: Output: result
|
Algorithm 2 Backtracking Algorithm |
Input: Output:
|
Algorithm 3 Backtracking test |
Input: Output:
|
4. Test Data
4.1. Building Information
4.2. Sensor Data
5. Results
6. Conclusions
Author Contributions
Funding
Data Availability Statement
Conflicts of Interest
References
- Willemsen, T.; Keller, F.; Sternberg, H. Kartengestützte MEMS-basierte Indoor-positionierung mittels Partikel Filter. In Oldenburger 3D-Tage; Photogrammetrie-Laserscanning Optische 3D-Messtechnik Th. Luhmann/Ch. Müller (Hrsg.), Wichmann, VDE Verlag GmbH, Berlin and Offenbach: Oldenburg, Germany, 2015; ISBN 9783879075287. [Google Scholar]
- Winter, S. Indoor spatial information. Int. J. 3-D Inf. Model. 2012, 1, 25–42. [Google Scholar] [CrossRef]
- Wang, H.; Sen, S.; Elgohary, A.; Farid, M.; Youssef, M.; Choudhury, R.R. No need to war-drive: Unsupervised indoor localization. In Proceedings of the 10th International Conference on Mobile Systems, Applications, and Services, Applications, and Services, Windermere, UK, 25–29 June 2012; pp. 197–210. [Google Scholar]
- Li, F.; Zhao, C.; Ding, G.; Gong, J.; Liu, C.; Zhao, F. A Reliable and accurate indoor localization method using phone inertial sensors. In Proceedings of the 2012 ACM Conference on Ubiquitous Computing, Pittsburgh, PA, USA, 5–8 September 2012; pp. 421–430. [Google Scholar] [CrossRef]
- Lewandowicz, E. Network models of 2D and 3D carastral data. In Proceedings of the 9th International Conference on Environmental Engineering, ICEE 2014, Vilnius, Lithuania, 22–23 May 2014. [Google Scholar] [CrossRef]
- Shoushtari, H.; Willemsen, T.; Sternberg, H. Many ways lead to the goal—Possibilities of autonomous and infrastructure-based indoor positioning. Electronics 2021, 10, 397. [Google Scholar] [CrossRef]
- Yang, J.; Cao, Z.; Zhang, Q. A fast and robust local descriptor for 3D point cloud registration. Inf. Sci. 2016, 346, 163–179. [Google Scholar] [CrossRef]
- Dubé, R.; Dugas, D.; Stumm, E.; Nieto, J.; Siegwart, R.; Cadena, C. SegMatch: Segment based place recognition in 3D point clouds. In Proceedings of the 2017 IEEE International Conference on Robotics and Automation (ICRA), Singapore, 29 May–3 June 2017; pp. 5266–5272. [Google Scholar] [CrossRef] [Green Version]
- Willemsen, T. Fusionsalgorithmus zur Autonomen Positionsschätzung im Gebäude, Basierend auf MEMS-Inertialsensoren im Smartphone. Ph.D. Thesis, HafenCity Universität Hamburg, Hamburg, Germany, 2016. [Google Scholar]
- White, C.E.; Bernstein, D.; Kornhauser, A.L. Some map matching algorithms for personal navigation assistants. Transp. Res. Part C Emerg. Technol. 2000, 8, 91–108. [Google Scholar] [CrossRef]
- Lan, K.C.; Shih, W.Y. On calibrating the sensor errors of a PDR-based indoor localization system. Sensors 2013, 13, 4781–4810. [Google Scholar] [CrossRef] [PubMed] [Green Version]
- Park, J.G.; Teller, S. Motion Compatibility for Indoor Localization; Technical Report; Massachusetts Institute of Technology: Cambridge, MA, USA, 2014. [Google Scholar]
- Gu, F.; Valaee, S.; Khoshelham, K.; Shang, J.; Zhang, R. Landmark Graph-Based Indoor Localization. IEEE Internet Things J. 2020, 7, 8343–8355. [Google Scholar] [CrossRef]
- Xiao, Z.; Wen, H.; Markham, A.; Trigoni, N. Lightweight map matching for indoor localisation using conditional random fields. In Proceedings of the 13th International Symposium on Information Processing in Sensor Networks (IPSN-14), Berlin, Germany, 15–17 April 2014; pp. 131–142. [Google Scholar]
- Bataineh, S.; Bahillo, A.; Díez, L.E.; Onieva, E.; Bataineh, I. Conditional Random Field-Based Offline Map Matching for Indoor Environments. Sensors 2016, 16, 1302. [Google Scholar] [CrossRef] [PubMed] [Green Version]
- Thiagarajan, A.; Ravindranath, L.; LaCurts, K.; Madden, S.; Balakrishnan, H.; Toledo, S.; Eriksson, J. Vtrack: Accurate, energy-aware road traffic delay estimation using mobile phones. In Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems, Berkeley, CA, USA, 4–6 November 2009; pp. 85–98. [Google Scholar]
- Newson, P.; Krumm, J. Hidden Markov map matching through noise and sparseness. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Seattle, WA, USA, 4–6 November 2009; pp. 336–343. [Google Scholar]
- Ma, Y.; Dou, Z.; Jiang, Q.; Hou, Z. Basmag: An optimized HMM-based localization system using backward sequences matching algorithm exploiting geomagnetic information. IEEE Sens. J. 2016, 16, 7472–7482. [Google Scholar] [CrossRef]
- Wu, Y.; Chen, P.; Gu, F.; Zheng, X.; Shang, J. HTrack: An efficient heading-aided map matching for indoor localization and tracking. IEEE Sens. J. 2019, 19, 3100–3110. [Google Scholar] [CrossRef]
- Peter, M.; Fritsch, D.; Schafer, B.; Kleusberg, A.; Link, J.A.B.; Wehrle, K. Versatile geo-referenced maps for indoor navigation of pedestrians. In Proceedings of the International Conference on Indoor Positioning and Indoor Navigation (IPIN), Sydney, Australia, 13–15 November 2012; pp. 1–4. [Google Scholar]
- Davidson, P.; Collin, J.; Takala, J. Application of particle filters for indoor positioning using floor plans. In Proceedings of the 2010 Ubiquitous Positioning Indoor Navigation and Location Based Service, Kirkkonummi, Finland, 14–15 October 2010; pp. 1–4. [Google Scholar]
- Woodman, O.; Harle, R. Pedestrian localisation for indoor environments. In Proceedings of the 10th International Conference on Ubiquitous Computing, Seoul, Korea, 21–24 September 2008; pp. 114–123. [Google Scholar]
- Yu, C.; Lan, H.; Gu, F.; Yu, F.; El-Sheimy, N. A map/INS/Wi-Fi integrated system for indoor location-based service applications. Sensors 2017, 17, 1272. [Google Scholar] [CrossRef] [PubMed]
- Gu, F.; Hu, X.; Ramezani, M.; Acharya, D.; Khoshelham, K.; Valaee, S.; Shang, J. Indoor localization improved by spatial context—A survey. ACM Comput. Surv. 2019, 52, 64. [Google Scholar] [CrossRef] [Green Version]
- Wendel, J. Integrierte Navigationssysteme; Oldenbourg Verlag: München, Germany, 2011; ISBN 9783486704396. [Google Scholar] [CrossRef]
- Aggarwal, P.; Syed, Z.; El-sheimy, N.; Noureldin, A. MEMS-Based Integrated Navigation; Artech House: Norwood, MA, USA, 2010. [Google Scholar]
- Gordon, N.J.; Salmond, D.J.; Smith, A.F.M. Novel approach to nonlinear/non-Gaussian Bayesian state estimation. In IEE Proceedings F-Radar and Signal Processing; IET: London, UK, 1993; Volume 140, pp. 107–113. [Google Scholar]
- Widyawan; Klepal, M.; Beauregard, S. A Novel Backtracking Particle Filter for Pattern Matching Indoor Localization. In Proceedings of the First ACM International Workshop on Mobile Entity Localization and Tracking in GPS-Less Environments (MELT ’08), San Francisco, CA, USA, 19 September 2008; Association for Computing Machinery: New York, NY, USA, 2008; pp. 79–84. [Google Scholar] [CrossRef]
- Shoushtari, H.; Askar, C.; Harder, D.; Willemsen, T.; Sternberg, H. 3D Indoor Localization using 5G-based Particle Filtering and CAD Plans. In Proceedings of the International Conference on Indoor Positioning and Indoor Navigation (IPIN), Lloret de Mar, Spain, 29 November–2 December 2021. [Google Scholar] [CrossRef]
- Cappelli, C. The Language of Spatial Analysis; Esri Press: Redlands, CA, USA, 2013; Available online: https://www.esri.com/content/dam/esrisites/sitecore-archive/Files/Pdfs/library/books/the-language-of-spatial-analysis.pdf (accessed on 1 July 2021).
- Peuquet, D. A Conceptual Framework and Comparison of Spatial Data Models. Cartogr. Int. J. Geogr. Inf. Geovis. 1984, 21, 66–113. [Google Scholar] [CrossRef] [Green Version]
- QGIS Development Team. QGIS. QGIS Webpage. Available online: http://qgis.osgeo.org (accessed on 3 April 2022).
- Redlands, CA: Environmental Systems Research Institute (ESRI). ArcGIS. ArcGIS Webpage. Available online: www.esri.com (accessed on 3 April 2022).
- Developers, G. Geometric Manipulations. GeoPandas Documentation. Available online: https://geopandas.org/docs/user_guide/geometric_manipulations.html (accessed on 2 July 2021).
- Gills, S. The Shapely User Manual. 2021. Available online: https://shapely.readthedocs.io/en/latest/manual.html#binary-predicates (accessed on 2 July 2021).
- Arulampalam, M.S.; Maskell, S.; Gordon, N.; Clapp, T. A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking. IEEE Trans. Signal Process. 2002, 50, 174–188. [Google Scholar] [CrossRef] [Green Version]
- Real Ehrlich, C.; Blankenbach, J. Indoor localization for pedestrians with real-time capability using multi-sensor smartphones. Geo-Spat. Inf. Sci. 2019, 22, 73–88. [Google Scholar] [CrossRef] [Green Version]
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. |
© 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).
Share and Cite
Harder, D.; Shoushtari, H.; Sternberg, H. Real-Time Map Matching with a Backtracking Particle Filter Using Geospatial Analysis. Sensors 2022, 22, 3289. https://doi.org/10.3390/s22093289
Harder D, Shoushtari H, Sternberg H. Real-Time Map Matching with a Backtracking Particle Filter Using Geospatial Analysis. Sensors. 2022; 22(9):3289. https://doi.org/10.3390/s22093289
Chicago/Turabian StyleHarder, Dorian, Hossein Shoushtari, and Harald Sternberg. 2022. "Real-Time Map Matching with a Backtracking Particle Filter Using Geospatial Analysis" Sensors 22, no. 9: 3289. https://doi.org/10.3390/s22093289