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 A geographic information system (GIS) is a type of database containing Geographic data and information, geographic data (that is, descriptions of phenomena for which location is relevant), combined with Geographic information system software, sof ...

. The most common approach is to take recorded, serial location points (e.g. from

GPS The Global Positioning System (GPS), originally Navstar GPS, is a Radionavigation-satellite service, satellite-based radionavigation system owned by the United States government and operated by the United States Space Force. It is one of t ...

) and relate them to edges in an existing street

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

(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 Transportation engineering or transport engineering is the application of technology and scientific principles to the planning, functional design, operation and management of facilities for any mode of transportation in order to provide for t ...

. Map matching algorithms can be divided in

real-time Real-time or real time describes various operations in computing or other processes that must guarantee response times within a specified time (deadline), usually a relatively short time. A real-time process is generally one that happens in defined ...

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. 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.

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 and this subject is still undergoing active research and development.

Approaches

Geometric approach

The earliest approached to solve the map matching problem based on similarity between points' curve and the road curve.

Hidden Markov Models

Map matching is described as a

hidden Markov model A hidden Markov model (HMM) is a statistical Markov model in which the system being modeled is assumed to be a Markov process — call it X — with unobservable ("''hidden''") states. As part of the definition, HMM requires that there be an ob ...

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.

Implementation

Map matching is implemented in a variety of programs, including the open-source GraphHopper and Open Source Routing Machine routing engines. It is also included in a variety of proprietary programs and mapping/routing applications.

References

{{reflist Cartography Computing terminology