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