Map Matching

Dive into processing of Raw GPS Data

April 2, 2018 - 2 minute read -
it

You are possibly know, that when we are dealing with GPS data it can have a huge errors in measurements, that’s is just because nature of GPS itself.

I will not cover an theoretical background, just will show you one way of dealing with GPS measurements from objects getting over road network.

I will supose, that you are familliar with graph theory a bit.

When we are supposed to go from our raw GPS point to point on road network (road graph), in simpliest case we can just do ‘OKAY LETS FIND CLOSEST POINT ON ROAD GRAPH AND SAY THAT IT IS OUR POINT’, it will work, let’s say in 50% of cases and probably whenever GPS measurement accuracy is high, but once there are a huge thickness of graph edges (roads) nor accuracy is getting low, you probably will find out that this algorithm no longer works as expected.

There are a nice academical work covering one of possible algorithms to do what is called Map Matching, a pretty nice way, article Hidden Markov Map Matching Through Noise and Sparseness.

I gonna make a simple coverage of that article, so probably everyone could understand.

Okay, under the hood of this algorithm is a two math structures, it is a road network graph edges is a road, vertices is a intersections, pretty simple huh? That graph can actually had a very different properties, but in simple case (let’s say we are talking about data from OSM), it is geometry of road, direction, probably some additional info (could be also speed limit on some limited cases and etc). Second structure is called Hidden Markov Model, it is probabilistic model, in this case it is used with Viterbi algorithm, to find out the most probabilistic way of object over road network.

So whenever we got an our GPS measurement, we create a new layer in HMM with candidates for it from road graph, every has a probability that it is actually an ground truth, after adding a new layer, there are a links to previous layer, that also has a probability, so that is a transfer probabilities, “how much possible is we can go to that road from that”.

Okay, where i can COPY PASTARINO, or JUST use LIBBERINO?

Here you go, man:

Hope it helps!