Different approaches for map matching : links / ideas?

Question

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):

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

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 this Question to match the whole line instead of just point by point

/Nicklas

Answer 2

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 3

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.

Answer 4

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.