Map matching links and ideas? [closed]

Question

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?

Answer 1

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

Answer 2

This question has been converted to Community Wiki and wiki locked because it is an example of a question that seeks a list of answers and appears to be popular enough to protect it from closure. It should be treated as a special case and should not be viewed as the type of question that is encouraged on this, or any Stack Exchange site, but if you wish to contribute more content to it then feel free to do so by editing this answer.

---

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:

• Map-Matching for Low-Sampling-Rate GPS Trajectories
• Some map matching algorithms for personal navigation assistants
• A Three-step General Map Matching Method in the GIS Environment: Travel/Transportation Study Perspective

Answer 3

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

http://safari.ce.sharif.edu/file/2011-06-06/259/2009_An%20off-line%20map-matching%20algorithm%20for%20incomplete%20map%20databases.pdf

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.

Answer 4

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)

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

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.

Answer 11

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.

Answer 12

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.