6 ms·

Using Open Street Maps and Kalman Filters to Clean Up GPS Data

139 points by tapan_pandita 10y ago

karussell 10y ago
Not sure what stack exactly they use under the hood, but we have created a sophisticated, very fast but similar algorithm implemented in Java. Bonus: everything is open source: https://github.com/graphhopper/map-matching https://github.com/graphhopper/map-matching including web API, routing engine, easy setup (no DB involved), simple demo UI, ... Only disadvantage I see: we currently do not support online map matching but this will surely come. BTW: kalman filters are very similar to our approach (hidden markov model). BTW2: Their FAQ is ridiculous: "Do you have competitors? No..." There are many companies with tracking and also open source products ...
johneth 10y ago
Kalman filters are very useful. There are several variants that can be implemented, depending on the available data and what you want to achieve. I found a great place to get your head around them was Roger Labbe's tutorials: http://nbviewer.jupyter.org/github/rlabbe/Kalman-and-Bayesian-Filters-in-Python/blob/master/table_of_contents.ipynb http://nbviewer.jupyter.org/github/rlabbe/Kalman-and-Bayesia...
- tapan_pandita 10y ago
  Thanks for sharing this! Looks super useful.
- arjun27 10y ago
  My favourite resource on Kalman is Tucker McClure's work: http://www.anuncommonlab.com/articles/how-kalman-filters-work/ http://www.anuncommonlab.com/articles/how-kalman-filters-wor...
hahaker 10y ago
This seems very useful, but isn't Google Maps doing similar stuff already? And if not, what are their concerns?
- tapan_pandita 10y ago
  The Google Maps APIs are point in time. Using OSM and Kalman filters, we can continuously snap points to the road in realtime. Plus it's a lot faster doing it on our own database than calling external APIs.
- sureshv 10y ago
  It's called snap to roads (interpolated mode): https://developers.google.com/maps/documentation/roads/snap https://developers.google.com/maps/documentation/roads/snap
wyldfire 10y ago
> OSM Filter: This uses publicly available OpenStreetMap road data and maps our GPS traces to nearest possible roads OSM is considered a reference for HyperTrack -- they snap to the OSM roads. But I wonder how they [OSM] might've constructed their maps given the similarly noisy GPS samples they likely would've crowdsourced from. Do they use kalman filters/more samples/higher precision GPS reference devices?
- zo1 10y ago
  I am guessing, but I don't think much of OSM's recent data is from GPS-samples. Roads don't pop into existence regularly, and when they do get built, my guess is someone adds them manually by referencing an underlying satellite layer. This probably doesn't apply to remote/rural/country-side areas, and for trails. In those cases, it's probably the other way around.
  - thomersch_ 10y ago
    Satellite/Areal imagery is not the most accurate thing. It might be skewed, misaligned or stitched incorrectly. In OpenStreetMap areal imagery is a great help, but not the single source of truth. For mappers those images are a good starting point, but there are always other objects near it that can be used as a reference, so that new objects are placed relatively to it. One single GPS trace is not very meaningful, but if you take several of them into account - optimally from different users with different devices - outliers become more visible and a smoothened path can be derived from it. OpenStreetMap has a theoretical resolution of a centimeter, but in reality such a precision is not necessary as the devices that are used for consuming maps have a limited accuracy. So if the path is -/+ 5 m, that's fine for us.
- arjun27 10y ago
  Great question. It's a combination of gps data[1] and a lot of manual work. Mapbox for one has strong data teams running mapping initiatives[2]. [1] https://blog.openstreetmap.org/2013/04/12/bulk-gpx-track-data/ https://blog.openstreetmap.org/2013/04/12/bulk-gpx-track-dat... [2] https://github.com/mapbox/mapping/wiki https://github.com/mapbox/mapping/wiki
Doctor_Fegg 10y ago
Sorry to be that guy, but: OpenStreetMap. One word, not pluralised.
- tapan_pandita 10y ago
  That's ok. As you can see, we are sticklers for accuracy too.
- pmontra 10y ago
  And I wonder if the PostgresDB they're using is PostgreSQL or something else. I googled https://betalist.com/startups/postgresdb https://betalist.com/startups/postgresdb but the link to the site doesn't work.
  - tapan_pandita 10y ago
    It's just plain old postgres
grecy 10y ago
Slightly related: I'm driving through West Africa now, and I loaded OSM onto my cheap-o used Garmin. [1] I have been absolutely shocked and blown away by the accuracy and detail of the maps. In the tiniest dirt street village, with less than 100 people, it correctly maps all the roads and even all the walking trails. Of course, in the big cities too. I'm staggered they have this level of detail. [1] http://garmin.openstreetmap.nl/ http://garmin.openstreetmap.nl/
- rmc 10y ago
  The mapping in west africa could be from the Humanitarian OpenStreetMap Team
- arjun27 10y ago
  Totally. Have you seen OSM Analytics - it has some really visualizations on how the data of geographies has evolved over time - in terms of roads, buildings etc. This link[1] shows Tanzania, for example. [1] http://osm-analytics.org/#/show/polygon:ivf~DvjpdAgots%40i~sBbfiB_ghe%40hyiK%7BdbHtczR%7DxoJlco%5Cnu_C/buildings/recency http://osm-analytics.org/#/show/polygon:ivf~DvjpdAgots%40i~s...

139 points by tapan_pandita 10y ago

Not sure what stack exactly they use under the hood, but we have created a sophisticated, very fast but similar algorithm implemented in Java. Bonus: everything is open source: https://github.com/graphhopper/map-matching https://github.com/graphhopper/map-matching including web API, routing engine, easy setup (no DB involved), simple demo UI, ... Only disadvantage I see: we currently do not support online map matching but this will surely come. BTW: kalman filters are very similar to our approach (hidden markov model). BTW2: Their FAQ is ridiculous: "Do you have competitors? No..." There are many companies with tracking and also open source products ...

johneth 10y ago

Kalman filters are very useful. There are several variants that can be implemented, depending on the available data and what you want to achieve. I found a great place to get your head around them was Roger Labbe's tutorials: http://nbviewer.jupyter.org/github/rlabbe/Kalman-and-Bayesian-Filters-in-Python/blob/master/table_of_contents.ipynb http://nbviewer.jupyter.org/github/rlabbe/Kalman-and-Bayesia...

tapan_pandita 10y ago
Thanks for sharing this! Looks super useful.
arjun27 10y ago
My favourite resource on Kalman is Tucker McClure's work: http://www.anuncommonlab.com/articles/how-kalman-filters-work/ http://www.anuncommonlab.com/articles/how-kalman-filters-wor...

hahaker 10y ago

This seems very useful, but isn't Google Maps doing similar stuff already? And if not, what are their concerns?

tapan_pandita 10y ago
The Google Maps APIs are point in time. Using OSM and Kalman filters, we can continuously snap points to the road in realtime. Plus it's a lot faster doing it on our own database than calling external APIs.
sureshv 10y ago
It's called snap to roads (interpolated mode): https://developers.google.com/maps/documentation/roads/snap https://developers.google.com/maps/documentation/roads/snap

wyldfire 10y ago

> OSM Filter: This uses publicly available OpenStreetMap road data and maps our GPS traces to nearest possible roads OSM is considered a reference for HyperTrack -- they snap to the OSM roads. But I wonder how they [OSM] might've constructed their maps given the similarly noisy GPS samples they likely would've crowdsourced from. Do they use kalman filters/more samples/higher precision GPS reference devices?

zo1 10y ago
I am guessing, but I don't think much of OSM's recent data is from GPS-samples. Roads don't pop into existence regularly, and when they do get built, my guess is someone adds them manually by referencing an underlying satellite layer. This probably doesn't apply to remote/rural/country-side areas, and for trails. In those cases, it's probably the other way around.
- thomersch_ 10y ago
  Satellite/Areal imagery is not the most accurate thing. It might be skewed, misaligned or stitched incorrectly. In OpenStreetMap areal imagery is a great help, but not the single source of truth. For mappers those images are a good starting point, but there are always other objects near it that can be used as a reference, so that new objects are placed relatively to it. One single GPS trace is not very meaningful, but if you take several of them into account - optimally from different users with different devices - outliers become more visible and a smoothened path can be derived from it. OpenStreetMap has a theoretical resolution of a centimeter, but in reality such a precision is not necessary as the devices that are used for consuming maps have a limited accuracy. So if the path is -/+ 5 m, that's fine for us.
arjun27 10y ago
Great question. It's a combination of gps data[1] and a lot of manual work. Mapbox for one has strong data teams running mapping initiatives[2]. [1] https://blog.openstreetmap.org/2013/04/12/bulk-gpx-track-data/ https://blog.openstreetmap.org/2013/04/12/bulk-gpx-track-dat... [2] https://github.com/mapbox/mapping/wiki https://github.com/mapbox/mapping/wiki

Doctor_Fegg 10y ago

Sorry to be that guy, but: OpenStreetMap. One word, not pluralised.

tapan_pandita 10y ago
That's ok. As you can see, we are sticklers for accuracy too.
pmontra 10y ago
And I wonder if the PostgresDB they're using is PostgreSQL or something else. I googled https://betalist.com/startups/postgresdb https://betalist.com/startups/postgresdb but the link to the site doesn't work.
- tapan_pandita 10y ago
  It's just plain old postgres

grecy 10y ago

Slightly related: I'm driving through West Africa now, and I loaded OSM onto my cheap-o used Garmin. [1] I have been absolutely shocked and blown away by the accuracy and detail of the maps. In the tiniest dirt street village, with less than 100 people, it correctly maps all the roads and even all the walking trails. Of course, in the big cities too. I'm staggered they have this level of detail. [1] http://garmin.openstreetmap.nl/ http://garmin.openstreetmap.nl/

rmc 10y ago
The mapping in west africa could be from the Humanitarian OpenStreetMap Team
arjun27 10y ago
Totally. Have you seen OSM Analytics - it has some really visualizations on how the data of geographies has evolved over time - in terms of roads, buildings etc. This link[1] shows Tanzania, for example. [1] http://osm-analytics.org/#/show/polygon:ivf~DvjpdAgots%40i~sBbfiB_ghe%40hyiK%7BdbHtczR%7DxoJlco%5Cnu_C/buildings/recency http://osm-analytics.org/#/show/polygon:ivf~DvjpdAgots%40i~s...