search

bmwcarit / barefoot

Java map matching library for integrating the map into software and services with state-of-the-art online and offline map matching that can be used stand-alone and in the cloud.
Apache License 2.0
671 stars 183 forks source link

Matching algorithm tuning #27

Closed larnacoeur closed 7 years ago

larnacoeur commented 8 years ago

Hi,

I've reviewed very many routes along with its matched versions and I noticed that sometimes Barefoot choose more important roads in matching, even if the position samples are rather obvious (like in the picture below). I think it may be related to object's speed which makes Barefoot 'think' that object is travelling on road with bigger max speed. Is there a way to handle that somehow? Like put more priority on geocoordinates than timestamps?

szybszadroga

smattheis commented 8 years ago

Where are the position samples in this example? To be honest, this looks like a map problem, e.g. a one-way, a not considered road type or an unconnected road, but I can't say it for sure. If it's really a road priority problem, you can modify the road types easily to your needs with this file: https://github.com/bmwcarit/barefoot/blob/master/map/tools/road-types.json

larnacoeur commented 8 years ago

Position samples are in the black polyline. Ok, I will look into that. Thank you either way.

smattheis commented 8 years ago

Ah okay. Well, since the yellow line, which seems like the matching result, turns into that road but makes a u-turn it looks pretty much like a not feasible route and, hence, takes the other (wrong) way.

jongiddy commented 8 years ago

Here's a similar instance, where the actual trail (red) shows the driver has turned onto a side road, and performed a U-turn to go back the other way, but the map-matched trail (blue) shows that the driver re-traced their steps over the nearby A route (the dark blue line indicates 3 trips over the same road).

missing-u-turn

smattheis commented 8 years ago

@jongiddy The large number of position samples on the Cardiff Road should acutally provide enough evidence to match it to that road. Can you send me a link to the map extract you used and also the input data? I would like to trace that example back to the problem.

jongiddy commented 8 years ago

Using the Wales map from http://download.geofabrik.de/europe/great-britain/wales.html

Input data at https://gist.github.com/jongiddy/12861e5d86be5e900f7b82898ec7ec7e

smattheis commented 8 years ago

Thanks for the example. I can reproduce the problem and will check how the algorithm balances higher priority roads. I assume that I will soon provide little patch either in the release or, if it's too specific for the main branch, just in this issue.

Side note: I'm trying to build a little benchmark setup for such problems but what I need is actually a nice dataset that includes a larger number of traces with longer traces and it must include the ground truth. This is a little problem. Any suggestions or ideas are appreciated. Benchmark algorithm is already implemented and released. (https://github.com/bmwcarit/barefoot/blob/master/src/main/java/com/bmwcarit/barefoot/matcher/Benchmark.java)

smattheis commented 7 years ago

Fixed in commit https://github.com/bmwcarit/barefoot/commit/952e63f620fa1dba82eb33865be4b130c86e3334 and released in https://github.com/bmwcarit/barefoot/releases/tag/0.1.1 and tested with trace and map of Wales provided with comment https://github.com/bmwcarit/barefoot/issues/27#issuecomment-245239188 . The bug seems to be fixed for that case and originated from an errorneous emission probability. Closing this issue for now as data for the original issue described in https://github.com/bmwcarit/barefoot/issues/27#issue-175180880 is not available.