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

Tunnel recognition #49

Closed vzahn closed 6 years ago

vzahn commented 7 years ago

Hi @smattheis,

I'm looking for an improvement in the algorithm regarding the recognition of tunnels.

My concern is, that I have several tracks, where a tunnel has nearly the same geometry as a surface road. In these situations the matching is often wrong and leeds to really ugly routings:

image

Shown in green is the correct way through the tunnel and red is the surface routing, which BF prefers ...

Now I have to make two changes:

  1. Extend the road class with a tunnel flag and fill it from the original map
  2. Extend the calculation of emission probabilities

First point is trival, but the second is puzzling me. A simple assumption is, that if I have a GPS measurement the tracker cannot be in a tunnel. But this of course is to simple as the tunnel can be very short or the ramps down in and up from the tunnel are modelled as tunnel, but has still have good satellite signal.

I have made some promissing experiments in changing the minimize function of road point candidates or in decreasing the emission propability of road points. But overall I'm unsure about a robust solution ...

Have you thought about this or have you ad hoc any good ideas on a solution for this?

BR Volker

smattheis commented 7 years ago

That's an interesting question: First of all, can you really detect bad signal quality with your devices/in your data? If this is the case, we can model this information with a probability to be in a tunnel and join it with the emission probability. (If so, I think this is a specific solution for your setting because many settings, especially with historic traces, don't have that information, but it's totally valid to think about that problem if you have that information.) I think "joining the probabilities" is what you mean with "extending the mission probabilities", right? I don't know yet about the feasibility, but I'm optimistic because I did something similar with the heading information which was quite successful for my test data.

Some other questions to understand your approach and the effects: What changes did you make to the minimize function? and What means that you decreased the emission probability, do you mean you changed the sigma value?

vzahn commented 7 years ago

In fact we can get the signal quality from the GPS chip in our device, but I'd like to use it just to ignore bad measurements on the device, meaning the device only sends measurments with good quality. Everything else would be to many data on the GSM transmission.

My first approach with the minimize function was, that I deleted all road point candidates, which are in a tunnel. This corresponds to the assumption, that in a tunnel I can't get a satellite signal. This worked really fine for a lot of situations, but then I detected measurements within a tunnel, e.g. the car was driving the ramp down into a tunnel and had clear satellite signals but in the map modelling the ramp was already assigned with the tunnel flag. So the minimize wrongly eliminated the road point candidate and the MM looked for alternate route or got an HMM break. Thus I skipped that approach.

My second approach was to decrease the emission probabilty of a road point by increasing the spatial distance dz of sample and road point, when the road has got a tunnel flag, e.g. dz *= 100 or dz +=100. This also is working for most situations but of course is a bit arbitrary ...

But that hint of yours regarding the heading is promising ... I will think on a similar solution and make some tests!

smattheis commented 7 years ago

That means you have a binary information with "sufficient/good" or "insufficient/bad" signal quality, right? If you have a little dataset with matched positions and, hence, information if (1) the position is in a tunnel or not OR (2) if the deviation between measurement and matched position increases, you could actually check if there's some evidence in that data? One possibility to model this, is to increase the sigma value for measurements with bad quality which lets then rather routes decide for most likely matches. This would be an awesome feature, because the GPS error distribution IS a driving but fixed parameter of map matching and information to adapt the error distribution will be definitely a nice and elegant approach. (I'm not sure right now, how to implement in detail, but: What I did with the azimuth is, I just included this as information in the sample data and considered it in the matcher for when determining candidates and calculating the probabilities.)

smattheis commented 6 years ago

I'm closing this issue for now. If there more/new aspects on this issue, please reopen it.