An improved hidden Markov model-based map matching algorithm considering candidate point grouping and trajectory connectivity

ABSTRACT

The hidden Markov model-based map matching algorithm (HMM-MM) is an effective method for online vehicle navigation and offline trajectory position correction. Common HMM-MMs are susceptible to the influence of adjacent road segment endpoints and similar parallel roads, because the multi-index probability model may ignore some indexes when the probability of other indexes is high. This makes the map-matching result not meet the assumption that vehicles always travel the shortest or optimal path, and it cannot guarantee that the trajectory points can match to the nearest position of the maximum likelihood road segment, resulting in poor accuracy. In this paper, an IHMM-MM is proposed. IHMM-MM (1) modifies the definition of transition probability and no longer takes the straight-line distance between trajectory points as the reference for the shortest path length between candidate point pairs. (2) supplements the definition of observation probability and introduces the point-line relation function to screen and group candidate points. (3) adds additional logic outside the HMM probability model to consider the trajectory connectivity and fill in the key trajectory points where the vehicles travel. Experiments show that the IHMM-MM can effectively improve the sampling frequency of trajectory data and has better performance in complex urban road environments.

KEYWORDS:

• Map-matching algorithm
• hidden Markov model
• Viterbi algorithm
• floating car data
• complex urban road environment

Acknowledgments

The authors would like to thank the editors and reviewers for their professional comments.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data and code availability statement

The data and codes that support the findings of this study are available in “figshare.com” with the identifier at https://doi.org/10.6084/m9.figshare.15168312.

Additional information

Funding

This work was supported by the National Key Research and Development Program of China; under Grant No. 2021YFB2501101