Map matching
{{Short description|Matching of coordinates to physical locations}}
File:Map Matching Example with GraphHopper.png]]Map matching is the problem of how to match recorded geographic coordinates to a logical model of the real world, typically using some form of Geographic Information System. The most common approach is to take recorded, serial location points (e.g. from GPS) and relate them to edges in an existing street graph (network), usually in a sorted list representing the travel of a user or vehicle. Matching observations to a logical model in this way has applications in satellites navigation, GPS tracking of freight, and transportation engineering.
Map matching algorithms can be divided in real-time and offline algorithms. Real-time algorithms associate the position during the recording process to the road network. Offline algorithms are used after the data is recorded and are then matched to the road network.{{cite journal |title=An off-line map-matching algorithm for incompletemap databases |journal= European Transport Research Review|date=2009-09-11 |last1=Pereira |first1=Francisco Câmara |last2=Costa |first2=Hugo |last3= Pereira |first3=Nuno Martinho |volume=1 |issue=3 |pages=107–124 |url=https://www.academia.edu/1869728 |accessdate=2014-11-23 |doi=10.1007/s12544-009-0013-6|s2cid= 56046090|doi-access=free |bibcode= 2009ETRR....1..107P|hdl=10316/102766 |hdl-access=free }} Real-time applications can only calculate based upon the points prior to a given time (as opposed to those of a whole journey), but are intended to be used in 'live' environments. This brings a compromise of performance over accuracy. Offline applications can consider all points and so can tolerate slower performance in favour of accuracy. However, the defects on low accuracy can be reduced due to integration of spatio-temporal proximity and improved weighted circle algorithms.{{cite journal |last1=Teng |first1=Wenxin |last2=Wang |first2=Yanhui |title=Real-Time Map Matching: A New Algorithm Integrating Spatio-Temporal Proximity and Improved Weighted Circle |journal=Open Geosciences |date=8 July 2019 |volume=11 |issue=1 |pages=288–297 |doi=10.1515/geo-2019-0023|bibcode=2019OGeo...11...23T |doi-access=free }}
Examples and use cases
Uses for map-matching algorithms range from the immediate and practical, such as applications designed for guiding travellers, to the analytical, such as generating detailed inputs for traffic analysis models and the like.
Probably the most common use of map-matching is where a traveller has some mobile computer giving him or her directions across a street network. In order to give accurate directions, the device must know exactly where in the street network the user is. A GPS location has positional error though, so picking the nearest street segment and routing from there will likely not work. Instead, the history of locations reported by the GPS can be used to guess a plausible route and infer the current location more accurately.
Other uses, more analytical in nature, include:
- extracting traffic flow information from vehicle GPS tracks
- associating user-reported attributes with a street
- automatically infer turn restrictions based on an analysis of multiple GPS tracks
There are other examples {{cite web |first1= Sotiris |last1= Brakatsoulas |first2= Dieter |last2= Pfoser |first3= Carola |last3= Wenk |author3-link= Carola Wenk |first4= Randall |last4= Salas |name-list-style=amp |date= September 2, 2005 |url= http://www.vldb.org/archives/website/2005/program/slides/fri/s853-brakatsoulas.ppt |format= PowerPoint |title= On Map-Matching Vehicle Tracking Data |publisher= Proc. VLDB conference 2005}} and this subject is still undergoing active research and development.{{cite journal |author1= Yin Lou |author2= Chengyang Zhang |author3= Yu Zheng |author4= Xing Xie |author-link4= Xing Xie |author5= Wei Wang |author6= Yan Huang |name-list-style= amp |date= November 4, 2009 |url= http://research.microsoft.com/apps/pubs/default.aspx?id=105051 |journal= Microsoft Research |title= Map-Matching for Low-Sampling-Rate GPS Trajectories}}{{cite web |author1=Marchal |author2=Hackney |author3=Axhausen |date=July 2004 |url=http://www.strc.ch/conferences/2005/Marchal.pdf |title=Efficient map-matching of large GPS data sets - Tests on a speed monitoring experiment in Zurich}}{{cite web |author1=Schuessler |author2=Axhausen |date=October 2009 |url=https://edit.ethz.ch/ivt/vpl/publications/reports/ab568.pdf |title=Map-matching of GPS traces on high-resolution navigation networks using the Multiple Hypothesis Technique (MHT) }}{{Dead link|date=March 2020 |bot=InternetArchiveBot |fix-attempted=yes }}{{cite arXiv |author1=Willard|date=October 2013 |eprint=1303.1883 |title=Real-time On and Off Road GPS Tracking|class=stat.AP }}
Approaches
= Geometric approach =
The earliest approached to solve the map matching problem based on similarity between points' curve and the road curve.{{Cite journal |last1=Bernstein |first1=David |last2=Kornhauser |first2=Alain |date=1996-08-01 |editor-last=New Jersey Institute of Technology |title=An Introduction to Map Matching for Personal Navigation Assistants |url=https://rosap.ntl.bts.gov/view/dot/38257 |language=English}}
= Topological approach =
Topological map matching aligns GPS points with a road network by considering the connectivity and relationships between road segments. It accounts for the structure of the network, path constraints, and the sequence of GPS points to provide accurate and realistic route matching, especially in complex environments.
= Advanced approach =
Advanced map-matching algorithms, including those based on Fuzzy Logic, Hidden Markov Models (HMM), and Kalman filters, significantly enhance the accuracy of GPS point location estimation. However, achieving this level of precision often requires substantial processing time.{{Cite arXiv |last1=Jafarlou |first1=Minoo |last2=Naderi |first2=Hassan |date=2022 |title=Improving Fuzzy-logic based map-matching method with trajectory stay-point detection |class=cs.LG |eprint=2208.02881 |language=English}}
= Hidden Markov Models =
Map matching is described as a hidden Markov model where emission probability is a confidence of a point to belong a single segment, and the transition probability is presented as possibility of a point to move from one segment to another within a given time.{{Cite journal |last1=Newson |first1=Paul |last2=Krumm |first2=John |date=November 2009 |title=Hidden Markov Map Matching Through Noise and Sparseness |url=https://www.microsoft.com/en-us/research/publication/hidden-markov-map-matching-noise-sparseness/ |journal=I17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2009) |language=en}}{{Cite journal |last1=Luo |first1=An |last2=Chen |first2=Shenghua |last3=Xv |first3=Bin |date=November 2017 |title=Enhanced Map-Matching Algorithm with a Hidden Markov Model for Mobile Phone Positioning |journal=ISPRS International Journal of Geo-Information |language=en |volume=6 |issue=11 |pages=327 |doi=10.3390/ijgi6110327 |bibcode=2017IJGI....6..327L |issn=2220-9964|doi-access=free }}
Implementation
Map matching is implemented in a variety of programs,{{cite web| url= https://www.showmymap.com/proximity-radius-circles/| title=Map Tracking| accessdate = 14 March 2018}}{{Cite web|url=https://github.com/brandonwillard/open-tracking-tools|title = open-tracking-tools|website = GitHub|date = 16 March 2020}} including the open-source GraphHopper and Open Source Routing Machine routing engines.{{Cite web|url = https://github.com/graphhopper/map-matching|title = Map Matching Implementation in Java|date = 30 April 2020|accessdate = |website = GitHub|publisher = |last = |first = }} It is also included in a variety of proprietary programs and mapping/routing applications.