Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

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
4  
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
2  
The keyword you are looking for is Map Matching. Big subject. –  Uffe Kousgaard Apr 18 '13 at 6:14
1  
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
show 1 more comment

12 Answers 12

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

/Nicklas

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
add comment

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
add comment

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
add comment

Answering to my own question !

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.

share|improve this answer
add comment

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, 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. Try importing some OpenStreetMap data and query it via the Location2NodesNtree. Feel free to ask here or on the mailing list for concrete implementation details.

share|improve this answer
add comment

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.

add comment

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
add comment

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.

share|improve this answer
1  
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
add comment

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: trb.metapress.com/content/p31485vw72645686 –  Fabrice Marchal Jun 13 '13 at 8:14
add comment

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

share|improve this answer
add comment

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
add comment

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
add comment

Your Answer

 
discard

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.