Matching Notes

Snapping GPS tracks to roads

The vehicles that I'm tracking on Orangetrack report their location approximately every 30s. This results in GPS tracks that look like:

The 30s resolution gives us a good indication of the route taken but the jittery track doesn't look great when shown on a map.

The trace looks much better if we smooth it out and 'snap' it to the actual road network.

To do the snapping I've been using the new match feature of the Open Source Routing Machine (OSRM) project.

OSRM is a routing library designed to work with OpenStreetMap data. It's written in C++, is super fast and ships with a HTTP interface that makes it easy to interact with from any language.

There are also some good Node.js bindings which are what I'm using to do the matching.

Matching the route

The algorithm used to match to the road network is described in the paper Hidden Markov Map Matching Through Noise and Sparseness. It has been shown to work well with GPS points spaced that up to ~30s apart at driving speed.

In order to perform the match, we need to prepare a dataset of the road network to match against. This comes in the form on a .osrm file. The details of how to generate .osrm files are described on the OSRM wiki.

Then, to perform a match, we provide the GPS coordinates and corresponding timestamps to the match algorithm:

var OSRM = require('osrm')
var osrm = new OSRM("england-latest.osrm");
var options = {
  coordinates: [[51.492785,-0.101248],[51.494388,-0.100776],[51.495658,-0.100282],[51.495003,-0.098759],[51.494455,-0.096399]],
  timestamps: [1434702335,1434702365,1434702395,1434702425,1434702455]
osrm.match(options, function(err, response) {
  // response.matchings contains an array of possible matches

The matched result is a nice improvement on the original GPS track: