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
665 stars 186 forks source link

Question to emission #91

Open dvent89 opened 6 years ago

dvent89 commented 6 years ago

https://github.com/bmwcarit/barefoot/blob/master/src/main/java/com/bmwcarit/barefoot/matcher/Matcher.java#L208

Why do we reduce the emission if we have a heading, should not we increase the emission value?

smattheis commented 6 years ago

We do not reduce the emission, we add a probability weight. Of course, the product of the probabilities of emission and heading is naturally less or equals than the probability of the emission because probability is normalized to a relative value between 0 and 1, but what matters is the adjustment of the probability distribution over candidates because some candidates have higher and some have lower probability for observing a certain heading. If we normalize the products of the candidates afterwards, such that all the products sum up to 1, we would see that probabilities of some candidates in fact increased and some decreased. (In some cases we can skip the normalization because we only want to know the candidate with maximum probability which doesn't require normalization.)

dvent89 commented 6 years ago

Hi sebastian,

thank you for your fast reply. Iam wondering on what is this formula based on. I could not find this in Newson and Krumm documents. The maximum "normalization" you can acquire is 0.01, this looks not feasbile for me .

smattheis commented 6 years ago

The integration of heading angles as emission probabilities into the HMM algorithm as described by Newson and Krumm is standard mathematics. To get an overview, I recommend this book: https://www.amazon.de/Artificial-Intelligence-Modern-Approach-Global/dp/1292153962 see chapter 15 "Probabilisitic reasoning over time"

I don't know what you mean with "maximum normalization". I have to admit, the statement about "maximum normalization" and 0.01 makes no sense to me.

dvent89 commented 6 years ago

emission = Math.max(1E-2, 1 / sqrt_2pi_sigA Math.exp((-1) da / (2 sigA))); The maximum use is not correct, mathemaical correct would be to use multiplikation of exponents.

emission = (1 / sqrt_2pi_sig2 1 / sqrt_2pi_sigA ) Math.exp((-1) dz dz / (2 sig2) + (-1) da da / (2 sigA));

so we escpae the multiplication of small numbers.

smattheis commented 6 years ago

The use of Math.max is not what I would refer to as a normalization but a definition of a (relative!) minimum for the emission probability of candidates. Could you please provide some more details about your question or statement? It's quite difficult to understand your point without context.