A Novel Map Matching Method Based on Improved Hidden Markov and Conditional Random Fields Model

Abstract

ABSTRACTAiming at the inherent “labeling bias” problem of Hidden Markov Models (HMMs) in the process of low-frequency sampling rate GPS trajectory map matching, this paper proposes a map matching method that combines HMMs and Conditional Random Field Models (CRFs). Various features including vehicle driving direction, direction change between candidate roads, shortest path, and spatial localization accuracy of trajectory points are integrated to optimize the state transfer process in the HMM model. The Viterbi algorithm was then employed to calculate the joint probability values of all candidate paths and the path with maximum probability value was selected as the matching path. The proposed map matching method was validated using publicly available Global Positioning System (GPS) vehicle trajectories from Guangzhou, Dongguan, and field-collected vehicle trajectory data from Ganzhou, China. The results demonstrated that the proposed method achieves high matching accuracy while maintaining efficient matching efficiency. The percentage of correct matching of GPS sampling points remains above 95%, and the average calculation time for each candidate road segment is kept within 50 ms. These advancements can greatly benefit location-based services that rely on map matching technology.

Keywords

• Map matching
• hidden markov model (HMM)
• conditional random fields (CRFs)
• floating vehicle
• GPS trajectory