Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm using Open Street Map and its vectorial road network and I'd like to implement a map matcher algorithm.

Currently I'm able, for each GPS position, to retrieve the nearest road segment and calculate the projection of this position to that segment, like on this image (Red pin is the pure GPS position, in blue the mapped segment and in Green the mapped position):

enter image description here

However, due to the lack of accuracy of the GPS, sometimes the mapped position jumps from segment to another and can provide some inconsistent mapped position from time to time.

My current algorithm is very basic : from the pure GPS position, I get the nearest segment and decide that the mapped matched position is on this one. I know that this can be really improved.

I can imagine that taking the vehicle direction into account will improve the map matching but do you know any other approach that would enable me to improve my map matcher ?

Any link, and/or open source software is welcome ! Thanks

share|improve this question
you could add a circle - Google uses cell reception and creates a light blue circle to show your approx location. You app looks good, good work. If you have the vector data you can snap to the nearest line from your GPS point - see post by Paul Ramsey – Mapperz Feb 3 '11 at 15:07
The keyword you are looking for is Map Matching. Big subject. – Uffe Kousgaard Apr 18 '13 at 6:14
Uffe is right, map matching. Check this paper for a few approaches: – lexicore Apr 18 '13 at 6:53
Thanks! lexicore, the paper is being sent to my printer as I type this. Time to get an overview. Thank you for the link. – scrrr Apr 18 '13 at 14:02
I would improve the Algorithm, by also trying to snap to the actual road, rather than just the vertices. – Devdatta Tengshe Apr 30 '13 at 16:48

13 Answers 13

The projecting of points onto the line as you are already doing is possible to do directly in PostGIS. I wrote about is some time ago, here

But to solve your problem when the points is closer to wrong segment than the right segment maybe this could be a possible approach.

1) Build a linestring of the points
2) Try the suggested solutions in this Question to match the whole line instead of just point by point


share|improve this answer
Thx for your reply. The projection is OK: I'm doing it already (not via ST_Closest because it's not available in spatialite that I'm using but that's OK). I was also just looking at the Question you mentioned and learned about the existence of this "Hausdorff distance" that may be interesting to look at. – yonel Feb 3 '11 at 14:58

Try and acquire some good test data. Use an additional higher accuracy track logging GPS, in addition to logging points on your target device. This will identify errors in the GPS and in the underlying OSM data. Knowing sensible thresholds will make it much easier to design the algorithm.

share|improve this answer

There is a lot of work on Map-matching see this paper for a brief survey of some fairly recent work (prior to 2007). More recently, approaches based on Hidden Markov Models seem to perform quite well under normal circumstances. For instance, check out this paper from 2009. The idea and model are quite simple and shouldn't give you too much trouble to implement even if you're not familiar with HMMs (in which case, don't panic, there are plenty of tutorials and introductions online)

share|improve this answer
Just realized that the Barefoot-Project I mentioned in my answer is based on the paper @Nick recommends. – nik Jan 11 at 13:45

Answering to my own question !

1- A nice .pdf I just found about this subject :

that also links to a C++ open source implementation of the map matcher described in the document:
(this one is an offline map matcher, my understanding is that it compute the map matched positions with the WHOLE path as input and cannot do it on the fly for each position).

2- Then, I've just read this one in depth and it's really good in my opinion : "Developing an Enhanced Weight-Based Topological MapMatching Algorithm for Intelligent Transport Systems"
The algorithm is clearly explained and weight adjustment values are also provided in the doc.

share|improve this answer

The subject is called map matching. But as a first very good approximation it is probably good enough to just lookup the closest points for every gps point (without any corrections guessing the correct way).

My Open Source project called graphhopper is not something which works for iOS (update: it now works on iOS too), nor has it a fully functional Android app for what you want. But you could use the server version to built an iOS app or use the offline Android demo as a start. I've release the map matching algorithm here, just a rough prototype but works surprisingly well.

share|improve this answer

If you can obtain roads data for your region, you might be interested in this thread. Do you want to plot data in a real time? Or are you planning on doing some postprocessing at your PC afterwards? If so, GRASS might be of help.

share|improve this answer

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer; explain why your answer is right, ideally with citations. Answers that don't include explanations may be removed.

After reading your Question, and the various Answers, I got interested in this problem. After doing a bit of reading on Map-matching algorithms, I have understood the following:

  • To Match the gps Location to road, you need the actual road data in vector format
  • It will help if you have different weights for different roads. So the chances of a point matching with a highway will be higher, then with matching a side line.
  • You need to take the history, and speed of the gps reading. For example if the the gps point has been matching the side lane for a long time, you should take that into account, and not match it directly to highway. -The actual matching is done using a variety of statistical techniques.

For Further reading, I suggest the following:

share|improve this answer
Yes, I was also reading and started to play with implementing a simple algorithm that I can expand upon. So far I have downloaded some data from OSM and I am playing with how I can best store (and access) it for my purposes. It's an interesting topic I think. :) I will update this question once I have something that works. Also, thank you for the links! – scrrr Apr 19 '13 at 7:36
I would be careful with using weights "So the chances of a point matching with a highway will be higher, then with matching a side line." ... That depends on the input data and could go very wrong. – underdark Jul 13 '13 at 11:04
@Devdatta, I get a 404 on the second link. Instead of me just editing it away, do you have an alternative link? – Chau Apr 21 '15 at 7:29
I don't have a free access link to that article. But if you are in an academic setup. The article should be available after a quick search – Devdatta Tengshe Apr 21 '15 at 8:22
@Chau: I found the PDF at:… – Devdatta Tengshe Apr 21 '15 at 8:33

The method is also called "vector conflation". There is a dedicated Wiki page ( which gives a general overview and lists (Open Source) software packages to perform road vector conflation like "JOSM conflation plugin", "Potlatch 2 merging tool", "RoadMatcher" (for OpenJUMP), and others.

share|improve this answer
I always thought conflation is something you do with two line layers instead of matching points onto lines. Is it really the same? – underdark Jul 13 '13 at 11:05

For Map-Matching algorithms, it depends if you need real-time or offline processing. In the later case, state-of-the-art algos can process ~ 1000 points per sec. Memory requirements depends on the coverage of course. We've managed to squeeze the OSM road network of the planet on approx 16 Gb for that purpose.

Also, you need to distinguish map-matching from path inference : these are two separate process depending if you have high or low frequency data. When you have relatively few points (e.g. 1 data every kilometer in urban context), it's path inference as there is usually some assumption to be done to guess where the device is traveling. Path inference is usually harder but is getting less of a problem with modern devices/price of data acquisition.

You can check my profile for an API that does map-matching directly on OSM: it uses topological matching and works well with floating car data for instance.

share|improve this answer
Can you expand on the algorithms that you are using? And how does the decreasing the road network size help? – Devdatta Tengshe Jun 8 '13 at 17:37
Less coverage = smaller network to keep in memory. That speeds up computation a bit. References: – Fabrice Marchal Jun 13 '13 at 8:14

You do not need to improve the quality of your data necessarily. Using a topological algorithm with an in-memory road network will improve your matching considerably. Check for references:

share|improve this answer

Thank you. Those answers where really helpful. Knowing the right search terms is worth a lot :)

I've found an API that might just does the job without having to go through the effort of developing an own solution right away.

They use OSM data to do map matching. They also have a demo page which allows the upload of GPX files to see how well this might work for you.

share|improve this answer
That's a great link when you want to do map matching for few points, once in a while. – Devdatta Tengshe Jul 11 '13 at 8:23

A bit late, but might be of interest:

Strava Slide

The page describes how cumulative track data over a road network can behave like "valleys", and how the proposed route would "fall into place" like it was a string of beads.

share|improve this answer

After testing most of the before mentioned frameworks I found Barefoot and can really recommend it. It uses hidden markov models as a probabilistic map-matching approach (details in their paper "Putting the car on the map") and is implemented in Java. It is open-source and activily developed by BMW's CarIT Department.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.