Map matching

Last updated
Map matching example with GraphHopper Map Matching Example with GraphHopper.png
Map matching example with GraphHopper

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.

Contents

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. However, the defects on low accuracy can be reduced due to integration of spatio-temporal proximity and improved weighted circle algorithms. [2]

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:

There are other examples [3] and this subject is still undergoing active research and development. [4] [5] [6] [7]

Approaches

Geometric approach

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

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. [9]

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. [10] [11]

Implementation

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

Related Research Articles

<span class="mw-page-title-main">Geographic information system</span> System to capture, manage and present geographic data

A geographic information system (GIS) consists of integrated computer hardware and software that store, manage, analyze, edit, output, and visualize geographic data. Much of this often happens within a spatial database, however, this is not essential to meet the definition of a GIS. In a broader sense, one may consider such a system also to include human users and support staff, procedures and workflows, the body of knowledge of relevant concepts and methods, and institutional organizations.

<span class="mw-page-title-main">European Geostationary Navigation Overlay Service</span> System that enhances the accuracy of GPS receivers

The European Geostationary Navigation Overlay Service (EGNOS) is a satellite-based augmentation system (SBAS) developed by the European Space Agency and EUROCONTROL on behalf of the European Commission. Currently, it supplements the GPS by reporting on the reliability and accuracy of their positioning data and sending out corrections. The system will supplement Galileo in a future version.

Robotic mapping is a discipline related to computer vision and cartography. The goal for an autonomous robot is to be able to construct a map or floor plan and to localize itself and its recharging bases or beacons in it. Robotic mapping is that branch which deals with the study and application of ability to localize itself in a map / plan and sometimes to construct the map or floor plan by the autonomous robot.

<span class="mw-page-title-main">Automotive navigation system</span> Part of the automobile controls

An automotive navigation system is part of the automobile controls or a third party add-on used to find direction in an automobile. It typically uses a satellite navigation device to get its position data which is then correlated to a position on a road. When directions are needed routing can be calculated. On the fly traffic information can be used to adjust the route.

<span class="mw-page-title-main">Mobile phone tracking</span> Identifying the location of a mobile phone

Mobile phone tracking is a process for identifying the location of a mobile phone, whether stationary or moving. Localization may be affected by a number of technologies, such as the multilateration of radio signals between (several) cell towers of the network and the phone or by simply using GNSS. To locate a mobile phone using multilateration of mobile radio signals, the phone must emit at least the idle signal to contact nearby antenna towers and does not require an active call. The Global System for Mobile Communications (GSM) is based on the phone's signal strength to nearby antenna masts.

Address geocoding, or simply geocoding, is the process of taking a text-based description of a location, such as an address or the name of a place, and returning geographic coordinates, frequently latitude/longitude pair, to identify a location on the Earth's surface. Reverse geocoding, on the other hand, converts geographic coordinates to a description of a location, usually the name of a place or an addressable location. Geocoding relies on a computer representation of address points, the street / road network, together with postal and administrative boundaries.

<span class="mw-page-title-main">Tracking system</span>

A tracking system, also known as a locating system, is used for the observing of persons or objects on the move and supplying a timely ordered sequence of location data for further processing.

<span class="mw-page-title-main">TomTom</span> Dutch manufacturer of automotive navigation systems

TomTom N.V. is a Dutch multinational developer and creator of location technology and consumer electronics. Founded in 1991 and headquartered in Amsterdam, TomTom released its first generation of satellite navigation devices to market in 2004. As of 2019 the company has over 4,500 employees worldwide and operations in 29 countries throughout Europe, Asia-Pacific, and the Americas.

A positioning system is a system for determining the position of an object in space. One of the most well-known and commonly used positioning systems is the Global Positioning System (GPS).

Global Navigation Satellite System (GNSS) receivers, using the GPS, GLONASS, Galileo or BeiDou system, are used in many applications. The first systems were developed in the 20th century, mainly to help military personnel find their way, but location awareness soon found many civilian applications.

<span class="mw-page-title-main">Indoor positioning system</span> Network of devices used to wirelessly locate objects inside a building

An indoor positioning system (IPS) is a network of devices used to locate people or objects where GPS and other satellite technologies lack precision or fail entirely, such as inside multistory buildings, airports, alleys, parking garages, and underground locations.

Wi-Fi positioning system is a geolocation system that uses the characteristics of nearby Wi‑Fi access point to discover where a device is located.

<span class="mw-page-title-main">Satellite navigation device</span> Device that can calculate its geographical position based on satellite information

A satellite navigation device, satnav device or satellite navigation receiver is a user equipment that uses one or more of several global navigation satellite systems (GNSS) to calculate the device's geographical position and provide navigational advice. Depending on the software used, the satnav device may display the position on a map, as geographic coordinates, or may offer routing directions.

<span class="mw-page-title-main">Here Technologies</span> Netherlands-based mapping data company

Here Technologies is a Dutch multinational group specialized in mapping technologies, location data and related automotive services to individuals and companies. It is majority-owned by a consortium of German automotive companies and American semiconductor company Intel whilst other companies also own minority stakes. Its roots date back to U.S.-based Navteq in 1985, which was acquired by Finland-based Nokia in 2007. Here is currently based in The Netherlands.

<span class="mw-page-title-main">Computer cartography</span> Compiling data to create a visual image

Computer cartography is the art, science, and technology of making and using maps with a computer. This technology represents a paradigm shift in how maps are produced, but is still fundamentally a subset of traditional cartography. The primary function of this technology is to produce maps, including creation of accurate representations of a particular area such as, detailing major road arteries and other points of interest for navigation, and in the creation of thematic maps. Computer cartography is one of the main functions of geographic information systems (GIS), however, GIS is not necessary to facilitate computer cartography and has functions beyond just making maps. The first peer-reviewed publications on using computers to help in the cartographic process predate the introduction of full GIS by several years.

<span class="mw-page-title-main">Turn-by-turn navigation</span> Feature of GPS navigation devices

Turn-by-turn navigation is a feature of some satellite navigation devices where directions for a selected route are continually presented to the user in the form of spoken or visual instructions. The system keeps the user up-to-date about the best route to the destination, and is often updated according to changing factors such as traffic and road conditions. Turn-by-turn systems typically use an electronic voice to inform the user whether to turn left or right, the street name, and the distance to the next turn.

<span class="mw-page-title-main">OsmAnd</span> Offline maps & navigation Android and iOS app

OsmAnd is a map and navigation app for Android and iOS. It uses the OpenStreetMap (OSM) map database for its primary displays, but is an independent app not endorsed by the OpenStreetMap Foundation. It is available in both free and paid versions; the latter unlocks the download limit for offline maps and provides access to Wikipedia points of interest (POIs) and their descriptions from within the app. Map data can be stored on the device for offline use. Using the device's GPS capabilities, OsmAnd offers routing, with visual and voice guidance, for car, bike, and pedestrian. All of the main functionalities work both online and offline.

<span class="mw-page-title-main">GraphHopper</span>

GraphHopper is an open-source routing library and server written in Java and provides a routing API over HTTP. It runs on the server, desktop, Android, iOS or Raspberry Pi. By default OpenStreetMap data for the road network and elevation data from the Shuttle Radar Topography Mission is used. The front-end is open-source too and called GraphHopper Maps.

<span class="mw-page-title-main">Locus Map</span>

Locus Map is a multi-functional Android navigation app. Primarily it is designed and used for leisure time outdoor activities like hiking, biking, or geocaching. The app is also used by professionals e.g. by S&R teams or for collecting geospatial data.

<span class="mw-page-title-main">Karta GPS</span> Free satnav application for smartphones

Karta GPS is a mobile application developed by Karta Software Technologies Lda., a daughter company of NDrive, for the Android, iOS and iPadOS operating systems. It is distributed for free and pairs open-source map data from OpenStreetMap alongside curated content from Yelp and Foursquare.

References

  1. ↑ Pereira, Francisco Câmara; Costa, Hugo; Pereira, Nuno Martinho (2009-09-11). "An off-line map-matching algorithm for incompletemap databases". European Transport Research Review. 1 (3): 107–124. Bibcode:2009ETRR....1..107P. doi: 10.1007/s12544-009-0013-6 . hdl: 10316/102766 . S2CID   56046090 . Retrieved 2014-11-23.
  2. ↑ Teng, Wenxin; Wang, Yanhui (8 July 2019). "Real-Time Map Matching: A New Algorithm Integrating Spatio-Temporal Proximity and Improved Weighted Circle". Open Geosciences. 11 (1): 288–297. Bibcode:2019OGeo...11...23T. doi: 10.1515/geo-2019-0023 .
  3. ↑ Brakatsoulas, Sotiris; Pfoser, Dieter; Wenk, Carola & Salas, Randall (September 2, 2005). "On Map-Matching Vehicle Tracking Data" (PowerPoint). Proc. VLDB conference 2005.
  4. ↑ 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.
  5. ↑ Marchal; Hackney; Axhausen (July 2004). "Efficient map-matching of large GPS data sets - Tests on a speed monitoring experiment in Zurich" (PDF).
  6. ↑ Schuessler; Axhausen (October 2009). "Map-matching of GPS traces on high-resolution navigation networks using the Multiple Hypothesis Technique (MHT)" (PDF).[ permanent dead link ]
  7. ↑ Willard (October 2013). "Real-time On and Off Road GPS Tracking". arXiv: 1303.1883 [stat.AP].
  8. ↑ Bernstein, David; Kornhauser, Alain (1996-08-01). New Jersey Institute of Technology (ed.). "An Introduction to Map Matching for Personal Navigation Assistants".{{cite journal}}: Cite journal requires |journal= (help)
  9. ↑ Jafarlou, Minoo; Naderi, Hassan (2022). "Improving Fuzzy-logic based map-matching method with trajectory stay-point detection". arXiv: 2208.02881 [cs.LG].
  10. ↑ Newson, Paul; Krumm, John (November 2009). "Hidden Markov Map Matching Through Noise and Sparseness". I17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2009).
  11. ↑ Luo, An; Chen, Shenghua; Xv, Bin (November 2017). "Enhanced Map-Matching Algorithm with a Hidden Markov Model for Mobile Phone Positioning". ISPRS International Journal of Geo-Information. 6 (11): 327. Bibcode:2017IJGI....6..327L. doi: 10.3390/ijgi6110327 . ISSN   2220-9964.
  12. ↑ "Map Tracking" . Retrieved 14 March 2018.
  13. ↑ "open-tracking-tools". GitHub . 16 March 2020.
  14. ↑ "Map Matching Implementation in Java". GitHub . 30 April 2020.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.