文档介绍：上海交通大学
硕士学位论文
3S系统中的地图匹配方法研究
姓名:付国庆
申请学位级别:硕士
专业:计算机软件与理论
指导教师:步丰林;戚正伟
20081201
3S 系统中的地图匹配方法研究

摘要
“3S 系统”即 GIS/GPS/LBS 系统,就是采取 GPS 作为定位手段,
为用户提供 LBS 服务的嵌入式 GIS 系统。“地图匹配”研究的问题就
是如何在 3S 系统的导航地图和 GPS 信号精度都比较低下的情况下,
将接收到的 GPS 位置匹配到地图上的实际位置上去。
本文首先简要介绍了 3S 系统的含义以及典型的 3S 系统的架构,
然后回顾总结了现有的地图匹配算法,包括基于地图几何信息的点到
点、点到线和线到线匹配,基于地图拓扑结构信息的匹配算法,以及
将这两者结合起来的综合性的地图匹配算法。基于地图几何信息的匹
配算法是将地图视为点、线等几何对象的集合,利用 GPS 点以及相邻
GPS 点连接形成的矢量线段与地图上几何对象的相似度来进行匹配。
这类算法最大的缺点是备选路段范围大,算法效率低,并且不能保证
连续 GPS 点的匹配结果具有连续性。这些缺点可以利用地图的拓扑信
息,即路段与路段之间的连通性等性质有效地克服。因此,将地图几
何信息与拓扑信息结合起来的匹配算法在准确度和性能上均有所提
高,但仍存在着不少缺点,如准确度低,不能自我纠正,一次匹配错
误可能导致连续的后续匹配错误等。
接着,本文以这些算法为基础,提出了一种新的地图匹配算法,
很好地克服了上述缺点。该算法的主要特点包括:保存多个匹配结果,
并可回溯,在后续匹配中自我校正历史匹配记录;综合考虑了多种匹
配因素,并根据匹配因素的权重对匹配度进行拟合;充分利用了历史
匹配记录,缩小了备选路段的范围,同时将备选路段分成三个等级,
即当前路段、当前路段的后续路段以及当前路段后续路段的后续路段,
在算法效率和准确度之间取得了良好的平衡;计算简单,没有复杂的
积分计算,适用软硬件资源紧张的嵌入式实时系统;可以快速高效地
构建出用户所有可能的运动轨迹等。
为支持该算法,本文同时还设计了一种数据结构—PS Graph。PS
Graph 其实是一种具有特殊用法的用来存储匹配结果的有向图,它可
以很自然地表示 GPS 点匹配路段之间的前后关系,并且可以随着匹配
的 GPS 点的增多而灵活地扩展,并在回溯时高效地删除历史匹配记录。
同时文中还描述了一种简洁方便的方法来从 PS Graph 中计算用户可
能的运动轨迹的数目。
最后,本文在 2010 年上海世博会的预研项目—“水晶球”项目中
实现并测试了本文提出的数据结构和匹配算法,实际运行效果良好。

关键词:地图匹配,3S 系统,地理信息系统(GIS),基于位置的服务
(LBS),全球定位系统(GPS)
Research of Map-Matching Methods in GIS/GPS/LBS Systems

ABSTRACT
3S systems are embedded GIS systems that use GPS as positioning
approach and provide LBS services for users. Since in real world, both
the digital map and the GPS signal are not precise enough, we need map
matching algorithms to map the GPS position we receive from GPS
receivers to the real road segment of the digital map.
This thesis first gives a brief introduction to 3S system and the
architecture of typical 3S systems, and then reviews current existing map
matching algorithms, including those based on the map's geometric
information and those based on the map's topologic information, and
those based on both. Map matching algorithms based on the map's
geom