摘 要

通过相应的导航设备可以获取到用户或交通工具的位置信息，初始表现为一系列有序的GPS轨迹。然后就需要进行一定的操作将这些位置信息关联到电子地图的路网上，这个过程叫做地图匹配。其主要目的是跟踪车辆，对交通流进行分析和发现驾驶方向的起点。基于隐马尔可夫模型的地图匹配算法就可以将GPS轨迹中偏离路网的部分匹配到相应路网上，并且具有一定的实时性和准确性。论文完成的任务就是将隐马尔可夫模型应用到地图匹配当中，其中涉及到马尔科夫链模型的构建、如何求得转移概率和观测概率，并且需要用到维特比算法来找出最大概率路径。然后将GPS轨迹作为输入，并进行坐标变换后与电子地图数据进行匹配，然后得出匹配完成的路径。论文还对地图匹配后的结果进行了大致的总结，然后对基于隐马尔可夫模型的地图匹配算法的发展前景进行了展望。

关键词： 地图匹配；马尔科夫链；维特比算法；转移概率

Abstract

The position information of users or vehicles can be obtained by corresponding navigation devices, which initially presents as a series of orderly GPS trajectories. Then some operations are needed to correlate those location information to the road network of electronic map, which is called map matching. Its main purpose is to track vehicles, analyze traffic flow and find the starting point of driving direction. Map-Matching algorithm based on Hidden Markov Model can match the part of GPS trajectory deviating from the road network to the corresponding road network, and has a certain degree of real-time and accuracy. The task of this paper is to apply Hidden Markov Model to Map-Matching, which involves the construction of Markov chain model, how to obtain the transition probability and observation probability, and need to use the Viterbi algorithm to find the maximum probability path. Then, the GPS trajectory is taken as input, and the coordinate transformation is carried out to match with the electronic map data. Then the matching completion path is obtained. The paper also summarizes the results of map matching, and then looks forward to the future development of Map-Matching algorithm based on Hidden Markov Model.

Key words: Map-Matching; Markov Chain; Viterbi algorithm; Transition Probability

目 录

第1章 绪论 1

1.1 地图匹配的研究背景与意义 1

1.2 国内外研究现状 2

1.3 论文研究内容 3

第2章 常用的地图匹配算法 4

2.1 按数据信息类型划分 4

2.2 按采样频率划分 5

2.3 按考虑采样点的范围划分 5

2.4 按计算的实时性划分 5

第3章 地图匹配原理分析 7

3.1 隐马尔可夫模型 7

3.2 隐马尔可夫与地图匹配 9

3.3 Dijkstra算法 11

3.4 Viterbi算法 11

第4章 仿真结果与分析 15

4.1 仿真环境 15

4.2 QGIS安装使用与GPS导航轨迹点的导入 15

4.3 方案整体设计 17

4.4 仿真过程 17

4.5 仿真结果分析 18

第5章 结论 20

5.1 工作总结 20

5.2 体会与展望 20

参考文献 22

致 谢 23

第1章 绪论

1.1 地图匹配的研究背景与意义

自电子信息技术出现以来，导航系统的发展和空间数据采集手段的不断完善，人类几乎能在现代化科技的帮助下搜集到所有的空间位置信息，然而相当一部分位置信息都不是百分百准确的，而且庞大的信息量也需要现代地理方面的科学来进行处理。在上个世纪末到这个世纪初，人们在对采集的空间位置处理中有了不少成效，但是由于在进行数据采集过程中人们用到的仪器设备不同，测量的手段和对对象的侧重点也不尽相同，获得的数据各有优缺，有一定的差异，如何求同存异，将各种类型数据的优势进行集中和优化是一个亟待解决的难题，于是上个世纪80年代出现了地图合并技术，这种技术可以在一定程度上满足数据的集成和共享需求，矢量要素的自动匹配就是起源于这个领域。

随着GPS^[1]（Global Position System：全球定位系统）的广泛应用，高德地图、百度地图等便携APP更是人们日常生活的必备。有了定位加导航，人们的出行变得更加便捷，打开GPS定位，人们几乎可以去到任何地图数据上显示的地方。然而，相应的问题仍然是存在的。由于路网信息复杂，设备的精度和准确度限制以及环境对信号的共同作用下，携带GPS定位相关设备的用户或者交通工具的经纬度位置信息进行电子地图的路网匹配时会产生或大或小的误差。

如果不进行地图匹配，那么匹配之后的轨迹就会显示在路网之外。这在我们日常中非常常见，我们在户外使用地图时，经常会发现地图上显示定位点会显示在了不存在道路的区域。具体表现为用户或目标位置信息模糊，人们不能或不知道如何进行空间转移来达到自己的目的。

特别是在交叉路口，如图1.1所示，三个GPS轨迹点中，A、B两点均不能准确的显示在路网上，对于一些方向感较差的人来说，他们的出行很大程度上依赖于GPS定位与导航，如果是处在A点的情况下，很明显可以看出路网路径是直线，只要能判断出在路径上，或许影响不大沿着唯一路径走就是正确的选择；但若是在B点的情况下，路况比较复杂，显示中人们常常不能判断自己位置处在交叉路口的哪一部分，对人们的生活造成很大的不便。地图匹配就是使这种模糊定位的情况得到改善的方式，而从开始研究地图匹配问题到现在，已经出现了不少解决问题的算法，这些算法的效果各不相同为。因此，如何研究出一种可以快速并精准反映人或物体位置的算法就极其重要。

图1.1 GPS轨迹点示意图