# Map matching links and ideas? [closed]

I'm using OpenStreetMap 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):

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 ?

I seek any link, and/or open source software?

• 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 blog.cleverelephant.ca/2008/04/snapping-points-in-postgis.html – 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: cens.ucla.edu/~mhr/cs219/maps/white00.pdf – 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

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 Algorithms for matching segments to match the whole line instead of just point by point
• 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

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:

• 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: researchgate.net/profile/Alain_Kornhauser/publication/… – Devdatta Tengshe Apr 21 '15 at 8:33

Answering to my own question !

that also links to a C++ open source implementation of the map matcher described in the document: http://eden.dei.uc.pt/~camara/files/mgemma.zip
(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 : https://dspace.lboro.ac.uk/dspace-jspui/bitstream/2134/4860/1/velaga.pdf "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.

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)

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

The method is also called "vector conflation". There is a dedicated Wiki page (http://wiki.openstreetmap.org/wiki/Conflation) 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.

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

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.

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.

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

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.

If you can obtain roads data for your region, you might be interested in Automatic bulk snapping with FOSS

Depending on whether you want to plot data in a real time, or are you planning on doing some postprocessing at your PC afterwards, GRASS might be of help.

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.

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: http://trb.metapress.com/content/p31485vw72645686