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年上海世博会的预研项目—“水晶球”项目中实现并测试了本文提出的数据结构和匹配算法,实际运行效果良好。? ??

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 3S 系统
• 1.1.2 3S 系统的典型架构
• 1.1.3 3S 系统中的关键技术分析
• 1.2 地图匹配方法综述
• 1.2.1 地图结构相关术语
• 1.2.2 地图匹配问题定义
• 1.2.3 地图匹配算法的分类
• 1.3 论文结构
• 1.4 本章小结
• 第二章 现有的地图匹配方法研究
• 2.1 基于地图几何信息的地图匹配算法
• 2.1.1 点到点匹配
• 2.1.2 点到线匹配
• 2.1.3 线到线匹配
• 2.2 基于地图拓扑结构的地图匹配算法
• 2.3 基于统计学和模糊理论的地图匹配算法
• 2.4 综合性的地图匹配算法
• 2.5 提高数据源的准确性
• 2.6 现有地图匹配方法总结
• 2.7 本章小结
• 第三章 一种新的地图匹配方法
• 3.1 PS Graph 数据结构
• 3.1.1 PS Graph 的初始化
• 3.1.2 PS Graph 的生长
• 3.1.3 PS Graph 的收缩
• 3.1.4 从 PS Graph 中查询匹配结果
• 3.2 地图匹配算法
• 3.2.1 地图匹配算法描述
• 3.2.2 匹配过程
• 3.2.3 匹配算法优化
• 3.3 匹配过程示例
• 3.4 本章小结
• 第四章 算法实现
• 4.1 “水晶球”项目介绍
• 4.2 GPS 信号的获取与解析
• 4.2.1 GPS 系统介绍
• 4.2.2 GPS 手机介绍
• 4.2.3 GPS 数据格式介绍
• 4.2.4 WinCE 平台上的 GPS 信号读取与解析
• 4.3 关键数据结构与伪码
• 4.3.1 辅助数据结构
• 4.3.2 关键数据结构 PSGraph
• 4.3.3 辅助方法
• 4.3.4 关键匹配算法
• 4.4 算法运行结果
• 4.5 本章小结
• 第五章 全文总结
• 5.1 主要结论
• 5.2 研究展望
• 参考文献
• 致谢
• 参与课题及已发表论文