From Noisy to Precise: How LocationIQ’s Map Matching API Cleans GPS Data

GPS is widely used for location-based services, but raw GPS data can be noisy, incomplete, and imprecise. These inaccuracies can cause several problems if you’re accurately tracking the movement of vehicles or people. Despite the generally high accuracy, there are factors that can negatively impact GPS data quality. GPS signals can be weakened/ disrupted by tall buildings, trees, or just bad weather conditions, leading to noise in the GPS data, which appears in the form of coordinates that show erratic movements or move away from a sensible path. GPS receivers may provide incorrect location information due to hardware/ software malfunctions or because they might not be able to capture signals from enough satellites to provide a precise location fix.

Accuracy of GPS data is known to be an issue in areas with limited satellite coverage, such as urban canyons, tunnels, or indoor environments. The resulting inaccuracies in the GPS data can lead to incorrect interpretations of the location and movement of vehicles or people. To overcome these challenges, map matching algorithms and APIs are used to improve the accuracy and reliability of the GPS data.

GPS data can be noisy, incomplete, and imprecise.
Limit GPS signals and GPS receivers can be cause of bad data
Inaccuracies can lead to incorrect interpretations of location and movement data.

What is a Map Matching API?

Map Matching API takes a series of latitude and longitude coordinates from a GPS device, and determines the most likely route taken by a vehicle or person based on the road network. It improves the accuracy and reliability of GPS data by applying algorithms to associate raw GPS coordinates with the corresponding road network on a map. The output is a set of matched points that have been snapped to the nearest road segment, resulting in a clean path that can be displayed on a map.

Map Matching API matches GPS data to a road network to determine the most likely route taken.
It improves GPS accuracy and reliability.
Output is a clean path displayed on a map.

How to use LocationIQ’s Map Matching API?

LocationIQ’s map matching accepts upto 25 coordinates in a single API call – it outputs an array of waypoint objects and a geometry in the form of a polyline string representing the route along with distance, duration and other optional datapoints. LocationIQ’s map matching API supports various options and parameters, such as matching radius, maximum speed, and interpolation methods. You can customize these options by passing additional query parameters in the HTTP request.

Here is an example of an HTTP query URL for LocationIQ’s Map Matching API:

https://us1.locationiq.com/v1/matching/driving/42.34561,-71.09832;42.36521,-71.10388;42.37532,-71.04997?key=<YOUR_ACCESS_TOKEN>&steps=true&geometries=polyline6&overview=simplified&annotations=true

https://us1.locationiq.com/v1/matching/driving/: This is the endpoint for LocationIQ’s map matching API. The /matching/driving/ part of the URL specifies the mode of transportation to use for the map matching.
42.34561,-71.09832;42.36521,-71.10388;42.37532,-71.04997: These are the GPS coordinates that need to be matched to the road network. The coordinates are separated by semicolons. Note: Coordinates have to be passed in the order {longitude},{latitude} and not {latitude}, {longitude}.
key=<YOUR_ACCESS_TOKEN>: This is the API access token that you obtained from LocationIQ when you signed up for an account. It’s included in the URL as a query parameter to authenticate your request and determine your API usage limits.
steps=true: This parameter indicates whether to return step-by-step instructions for the matched route.
geometries=polyline6: This parameter specifies the format of the matched route geometry to be returned. In this case, polyline6 is used to return a compressed string of the route geometry.
overview=simplified: This parameter specifies the level of detail to include in the overview of the matched route. In this case, simplified is used to return a simplified overview of the route.
annotations=true: This parameter indicates whether to return additional details about the matched route, such as the duration and distance of each segment of the route.

How does the Map Matching API actually work?

LocationIQ’s Map Matching API uses Hidden Markov Models (HMMs) to match noisy GPS traces to the underlying road network. Hidden Markov Models are statistical models used to model sequential data, where each observation is a sequence of events or symbols.

To put it simply, an HMM is like a game where you observe a sequence of events, but you don’t know the rules of the game. The events are like the rolls of a dice or the cards in a deck, and the rules are like the probabilities of each event occurring given the previous events. The challenge is to figure out rules of the game by observing the sequence of events without knowing the rules. This involves estimating the probabilities of each event occurring given the previous events, as well as the probabilities of starting and ending the sequence with certain events.

Once the model is trained, it can be used to predict the most likely sequence of events given a new set of observations. This is how the map matching API works behind the scenes:

The first step is to prepare the road network data, which is typically in the form of OpenStreetMap (OSM) data. The data is processed and optimized for use in routing and map matching algorithms.
GPS Trace Preprocessing: The raw GPS data is preprocessed to remove any noise or outliers that may be present. The data is also resampled to a uniform time interval, typically 1-2 seconds.
Graph Construction: The preprocessed GPS data and road network data are combined to create a graph where each node represents a point on the road network, and each edge represents the distance between two nodes. The graph is optimized to reduce the number of edges while maintaining the overall topology of the road network.
Path Search: This function attempts to find the most likely path by searching for the path that has the highest likelihood of generating the observed GPS trace. A Hidden Markov Model is used to perform the path search. In the case of map matching, the events represent the nodes on the road network, and the observations represent the GPS coordinates.
Path Scoring: Each possible path is scored based on how well it matches the observed GPS trace. The score is based on the likelihood of the GPS trace given the path, as well as other factors such as the length of the path and the number of turns.
Output: The map matching API outputs the most likely path along the road network, as well as additional information such as the speed of travel along the path and the confidence level of the match.

Where is Map Matching API used?

Map matching API can be used in various applications where GPS data is used to track movement of a vehicle or a person. Some of the common use cases you’ll see are:

Fleet management: Logistics and transportation companies need to track their fleet of vehicles and report the path taken visually on a map view. Map matching API normalizes GPS data and snaps the travel path to the existing street network.
Urban planning: City planners need to analyze traffic patterns and plan infrastructure improvements. Map matching API can provide insights into traffic flow, congestion, and the most commonly used routes by normalizing GPS data points from multiple sources and planting them to existing street networks
Fitness tracking: Fitness apps focused on walking/ jogging need to track the route taken by a person during their workout. By matching the GPS data with the road network, the user gets a clean overview of the path taken and can compare it against previous workouts or share it on social media.

Map Matching API is a powerful API for accurately tracking the movement of vehicles and people in real-time. It allows businesses to improve the customer experience by normalizing data in real time. We’ve covered the basics, including the problems associated with raw GPS data and how Map Matching API solves them. We also discussed the advantages of using Map Matching API, such as improved accuracy, reduced noise, and better visualization of data