Map Matching Components

The Location Library implements a map matcher based on a Hidden Markov Model (HMM). This algorithm is key to updating attributes of a map, for example when performing Traffic Sign Recognition or Local Hazard Warning.

For a description of how to construct the HMM, see the Microsoft article Hidden Markov Map Matching Through Noise and Sparseness. The map matcher works by determining the path through an HMM with the highest probability.

The HMM contains states and transitions. The states of the HMM represent the position on a road segment at which the vehicle may have been at a specific point in time. The observations are position measurements that may contain some degree of noise and other information such as the heading.

This means that the emission probability of an observation in a specified state is the probability that the measurement was taken while the vehicle was at the specified position.

The transition probability from state s1 at time t1 to state s2 at time t2 is the probability that the vehicle moved from position p1 at time t1 to position p2 at time t2.

Framing the map matching problem in these terms naturally leads to three customization points:

• The candidate states to consider
• The emission probability for an observation in a specified state
• The transition probability from one state to another