Map matching
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 estimate recorded satellite positioning reports (eg. from GPS) as relating to edges in an existing street segment graph (network), usually in a sorted list representing travel of a user or vehicle. Matching observations to a logical model in this way has applications in satellite 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.[1] 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.
Example
In real world drivers often use some GPS tracking device. The precision of those devices is very different, additionally there will be sampling errors caused by the sampling rate of the device. There are several cases like on a bridge, on a motorway with different directions or on a simple crossing where a higher precision would be required to identify the correct (digital) road. To work around this limitation and improve the probability of determination of the correct road some algorithm needs to be implemented which bases its heuristic on previous points, records the speed and "guesses" which of the (digital) roads is more likely to be the selected. There are other examples.[2] This is still a subject to research.[3][4][5]
Implementation
An open source prototype for map matching is implemented with the help of the routing engine GraphHopper in Java.[6]
Applications
There are several applications when a unique street ID is known after the map matching process:
- extracting traffic flow information from vehicle GPX tracks or
- additional attributes like the beauty, user ratings etc can be associated to a street
- automatically assign turn instructions after a GPX track was recorded
References
- ↑ Pereira, Francisco Câmara; Costa, Hugo; Pereira, Nuno Martinho (2009-09-11). "An off-line map-matching algorithm for incompletemap databases". Springer. Retrieved 2014-11-23.
- ↑ Brakatsoulas, Sotiris; Pfoser, Dieter; Wenk, Carola & Salas, Randall (September 2, 2005). "On Map-Matching Vehicle Tracking Data" (PowerPoint). Computer Technology Institute.
- ↑ Yin Lou; Chengyang Zhang; Yu Zheng; Xing Xie; Wei Wang & Yan Huang (November 4, 2009). "Map-Matching for Low-Sampling-Rate GPS Trajectories". Microsoft Research.
- ↑ Marchal; Hackney; Axhausen (July 2004). "Efficient map-matching of large GPS data sets - Tests on a speed monitoring experiment in Zurich" (PDF).
- ↑ Schuessler; Axhausen (October 2009). "Map-matching of GPS traces on high-resolution navigation networks using the Multiple Hypothesis Technique (MHT)" (PDF).
- ↑ "Map Matching Implementation in Java".