Abstract: In order to solve the problem that most of the existing map matching methods are difficult to effectively balance the matching speed and accuracy in the complex urban environment, a trajectory segmentation map matching method based on the complexity partition of the road network is proposed. The method includes two parts：road network partition and trajectory segment matching. The road network is divided into complex areas and non-complex areas through the constructed road network complexity partition model. Then, the trajectory segments in the complex areas are matched using the improved hidden Markov model, and the trajectory segments in the non-complex areas are matched based on the fast matching model of geometric topology is used for matching. Finally, the matched trajectory segments in different regions are spliced to obtain the matching result of the complete trajectory. In order to obtain the optimal parameters of the road network complexity partition model, 11 sets of comparative experiments with different parameter settings are carried out, and the final results are compared with the matching results of the ST-matching algorithm and the traditional hidden Markov model. The results show that the matching accuracy of the method in this paper is above 96% in the three data sets, and the matching time is reduced by 60% compared with the other two comparison algorithms, which effectively improves the matching efficiency under the premise of ensuring the matching accuracy.

Key words: map matching, road network partition, trajectory segmentation, hidden Markov model, geometric topology

摘要： 针对现有大多数地图匹配方法在城市复杂环境下难以有效平衡匹配速度和精度的问题，提出了一种基于路网复杂度分区的轨迹分段地图匹配方法。该方法包括路网分区和轨迹分段匹配两个部分。通过构建的路网复杂度分区模型将路网划分为复杂区域和非复杂区域；对复杂区域内的轨迹段采用改进的隐马尔可夫模型进行匹配，非复杂区域内的轨迹段采用基于几何拓扑的快速匹配模型进行匹配；将不同区域内匹配的轨迹段进行拼接，得到完整轨迹的匹配结果。为得到路网复杂度分区模型的最优参数，进行了11组不同参数设置的对比实验，并将最终结果与ST-matching和传统隐马尔可夫模型两种地图匹配方法匹配的结果进行对比。结果表明，在三个数据集的匹配准确率均在96%以上，比其他两种对比算法匹配时间减少了60%，在保证匹配准确率的前提下有效提升了匹配效率。

关键词: 地图匹配, 路网分区, 轨迹分段, 隐马尔可夫模型, 几何拓扑