基于GPS定位技术的车辆行驶里程计算研究与应用
随着经济的飞速增长，城市化进程的加快，机动车的增加为居民的出行带来便利的同时，发生在道路上的交通事故也在随之增加，利用GPS定位技术收集交通信息已经成为了当前研究的热点。本文为基于GPS定位技术的车辆行驶里程计算研究与应用，利用南京市出租车GPS定位数据进行分析，在进行数据的提取与预处理后，利用地图匹配算法还原车辆运行真实轨迹，最后建立模型对车辆行驶里程进行计算，主要有以下几个方面内容:　　首先结合交通工程理论及车辆行驶里程基础概念，提出了车辆行驶里程的一系列衍生概念，为车辆行驶里程的计算提供了理论依据。　　其次针...展开
随着经济的飞速增长，城市化进程的加快，机动车的增加为居民的出行带来便利的同时，发生在道路上的交通事故也在随之增加，利用GPS定位技术收集交通信息已经成为了当前研究的热点。本文为基于GPS定位技术的车辆行驶里程计算研究与应用，利用南京市出租车GPS定位数据进行分析，在进行数据的提取与预处理后，利用地图匹配算法还原车辆运行真实轨迹，最后建立模型对车辆行驶里程进行计算，主要有以下几个方面内容:　　首先结合交通工程理论及车辆行驶里程基础概念，提出了车辆行驶里程的一系列衍生概念，为车辆行驶里程的计算提供了理论依据。　　其次针对出租车GPS定位原始数据进行分析，提出了出租车GPS数据的处理的流程和方法，该方法能够有效地剔除超越研究范围、车辆停止重复定位、车辆定位数据跃变和定位数据漂移等情况的数据，为进行车辆轨迹地图匹配奠定了数据基础。　　再根据车辆行驶里程的计算要求，依据点到线的地图匹配方式进行改进，提出了基于路网拓扑关系的运行轨迹地图匹配方法，并对算法过程及算法流程进行了设计。　　最后对车辆行驶里程计算进行建模，根据时-空轨迹模型及经纬度两点间的距离计算，建立了单车车辆行驶里程模型，通过拓展得到车辆行驶里程计算模型。利用数理统计方法分析了车辆行驶里程计算方法的可行性并分析了对车辆行驶里程计算结果的影响因素。结合南京市出租车GPS定位数据进行车辆行驶里程计算实例分析。　　本研究利用GPS定位数据进行车辆行驶里程计算，为研究区域的经济发展、土地利用、交通规划、交通安全分析、环境评价、车队管理等提供有效的基础数据支持。收起
学位授予单位
机标分类号
本文读者也读过
加载中，请稍候
．客服电话
&&8:00-11:30,13:00-17:00(工作日)当前位置： >>
gps地图匹配算法
GPS 车辆导航与定位系统的 地图匹配算法研究研 究 生：徐浩 导 师：鲍 远 律 教授 专 业：模式识别与智能系统 论文完成时间：2007.5中国科学技术大学硕士毕业论文摘要摘要本论文研究的主要内容包括 调研现有车辆导航系统的地图匹配算法研究现 状，分析 GPS 轨迹数
据和交通矢量地图研究其误差特性，并且根据 GPS 车载接收 机误差和交通矢量地图误差的特点与现有算法的不足，设计具有更高准确性的地图 匹配算法来保证车辆导航系统的导航准确、及时和稳定。 在当前的车辆导航应用中， GPS 车载导航系统由于其定位的准确性、稳定性 一直是研究与应用的重点。由于独立 GPS 导航系统低廉的价格和易于布署安装的 因素，独立车载导航系统是目前民用车载导航系统中的主流。要满足用户对准确性 与实时性的要求，最基本的一步就是提高导航与定位系统的定位准确度，这包括两 个方面：确定当前车辆正在行驶的路段的准确性与确定车辆在行驶路段上的位置的 准确性。在独立 GPS 车辆导航系统中定位的准确性主要依靠地图匹配算法克服 GPS 误差和交通矢量地图的误差 ，使 GPS 轨迹匹配到矢量地图道路上的对应位 置。这不仅满足用户了解其在道路上准确位置的需求，而且为更高级的路径规划和 导航提示功能提供定位基础 。 根据对 GPS 误差和地图误差的研究，论文中设计了两个能够有效提高地图匹 配准确性的新地图匹配算法，与现有算法相比，这两个算法能够有效提高车辆在沿 道路方向上的准确性， GPS 轨迹沿道路方向上的误差是现有地图算法一直无法克 服的。同时第二个新算法根据 GPS 误差特点，重新设计了卡尔曼滤波器在地图匹 配算法中的应用模型，使车辆行驶过程中的慢漂移误差和随机误差都能够得到有效 校正。在车辆导航系统仿真平台上的使用结果表明，两个新算法都能够有效处理车 辆导航过程中 GPS 轨迹与对应地图道路点之间的误差，包括：垂直道路方向误差 和沿道路方向误差。通过仿真平台的验证，这两个算法能够明显提高定位的准确 性，尤其是在交叉路口附近，保证了车辆导航系统，路径规划和导航提醒的实时性 与准确性。 关 键 词 ：车辆导航系统 ，地图匹配算法 ， GPS，卡尔曼滤波I中国科学技术大学硕士毕业论文AbstractAbstractIn this paper, existing map-matching algorithms used in vehicle navigation systems are reviewed, characteristics of GPS track error and traffic vector map error are analyzed and two new map- matching algorithms are proposed by considering inadequacies of existing algorithms and error characteristic of GPS signal and traffic maps. The new algorithms have higher acc uracy to guarantee the accuracy and stability of vehicle navigation systems. Currently the GPS navigation system is the focus of research and application of vehicle navigation systems for its accuracy, stability. Since the independent GPS navigation system costs low price and is easy to be equipped, it is the mainstream of current civil application. It is basic to improve the accuracy of positioning system, which includes two parts: the accuracy of identifying the running-on road and the accuracy of corresponding location on the identified road. Accuracy of independent GPS navigation systems is tied to the map-matching algorithm, which overcomes GPS error and traffic map error to map vehicle GPS tracks onto corresponding roads. The map- matching task is not only the need for users to get their accurate location information on the map, but also the base of high-level path planning and navigation reminder functions. According to the research of GPS error and map road network error, the paper proposed two new map-matching algorithms that can improve accuracy of navigation systems greatly. Compared with existing algorithms, the proposed algorithms can effectively correct error in the road direction, which is not handled by existing algorithms. The second proposed algorithm redesigns the application method of Kalman filter in resolving map- matching problem to correct random error along with slow drift error at the same time. The experiment using new map-matching algorithms on a vehicle navigation platform demonstrates good results in dealing with GPS error and map road network error including the component in road direction and the direction perpendicular to the road. The efficiency of new algorithms is very good at promoting the accuracy of vehicle navigation system especially near intersections. Key-term: vehicle navigation system, map-matching algorithm, GPS, Kalman filter.II中国科学技术大学硕士毕业论文目录目录摘要 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． Ｉ Ａｂｓｔｒａｃｔ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． ＩＩ 目录．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． ＩＩＩ 第一章　绪论 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． １１．１　背景．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．１ １．２　研究目标．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．３ １．３ 论文安排 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．３第二章　车辆导航系统介绍 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． ４２．１　车辆导航系统功能．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．４ ２．２　车辆导航系统的组成．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．５ ２．３　车辆定位系统．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．６ ２．４　数字地图数据库．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．９２．４．１　地图矢量库 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．１１ ２．４．２ 地图数据库 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．１２第三章　车辆导航系统中的误差分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．． １３３．１ＧＰＳ 误差 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．１３３．１．１　ＧＰＳ 误差分类．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．１３ ３．１．２　各种类误差特点 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．１５ ３．１．３　常见克服 ＧＰＳ 误差方法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．１７３．２　交通矢量地图误差．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．１８３．２．１　矢量地图生成过程简介 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．１９ ３．２．２　交通矢量地图误差分析 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．２０第四章　　地图匹配问题以及现有算法介绍．．．．．．．．．．．．．．．．．．．．．．．． ２２４．１　地图匹配问题介绍．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．２２ ４．２　常见地图匹配算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．２４４．２．１　几何匹配算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．２５ ４．２．２　概率统计算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．２６ ４．２．３　其他高级算法 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．２６４．３　对现有算法分析．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．２６第五章　虚拟差分地图匹配算法．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． ２８５．１ 算法模型 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．２８ ５．２　初始阶段匹配道路的选取与利用 e( k ) 的车辆轨迹实时匹配．．．．．．．．．．．．．．２９ ５．３ 转弯过程后的地图匹配修正量的自动更新 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．３１ ５．４　算法程序流程概要描述．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．３４ ５．５　算法效果．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．３４ ５．６ 算法评论与总结 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．３７第六章　改进的卡尔曼滤波地图匹配算法．．．．．．．．．．．．．．．．．．．．．．．．． ３８６．１ 卡尔曼滤波器及其在车辆导航系统中的应用 ．．．．．．．．．．．．．．．．．．．．．．．．．．３８III中国科学技术大学硕士毕业论文目录６．２　算法模型．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．４０ ６．３ 转弯后状态变量与估计误差协方差的更新 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．４３ ６．４　完整算法流程．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．４５ ６．５　算法效果．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．４６ ６．６　算法评论与总结．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．４８第七章　总结与展望 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． ４９ 参考文献：．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． ５１ 致谢 ．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． ５３IV中国科学技术大学硕士毕业论文绪论第一章 绪论本章首先介绍论文研究 的基本背景 ，并且根据领域现状提出我们的研究目 标，本章的最后部分是论文内容的结构安排 。1.1 背景近年来随着车辆数量的快速增长与道路网范围的扩大与复杂 ，公路交通系统 的拥挤度和复杂性与日俱增，随之而来的是交通代价与浪费的不断提高，个人用户 的出行不便。研究发现，仅美国的主要城市每年由于交通拥挤而造成的浪费就已超 过 475 亿美元，每年因交通拥挤浪费的燃料达 143.5 亿升，浪费的工作小时为 27 亿。 并且 90 年代以来，这些数字以每年 5~10%的速度递增 [1]。越来越多的新科技 技术被用来保障交通舒畅和改善道路安全。由于计算机、信息和通信技术越来越广 泛地应用于交通的辅助和交通条件的改善，兴起了一个新的交通研究领域――智能 交通系统（ ITS ）。 智能交通系统 (ITS) 是未来交通系统的发展方向，其是将先进的信息技术、数 据通讯传输技术、电子传感技术、控制技术及计算机技术等有效地集成运用于整个 地面交通管理系统而建立的一种在大范围内、全方位发挥作用的，实时、准确、高 效的综合交通运输管理系统。当前 ITS 的服务领域有：先进的交通管理系统、先进 的出行者信息系统、先进的公共交通系统、先进的车辆控制系统、营运车辆调度管 理系统、电子收费系统、应急管理系统等。在本论文的研究中，我们研究的重点是 智能交通系统的一个重要组成部分：车辆定位和导航系统 ，它在智能交通的各个领 域中都有着重要作用。严格来说我们研究的是车辆定位与导航系统其中的一个重要 组成模块 ――地图匹配算法 。 尽管车辆定位和导航系统仅仅在最近几十年才开始出现在世界市场上，但是 在人类文明史上，他的研究和发展已经有相当长的历史[1]。在过去 20 多年中，车辆导航系统得到了迅猛发展，到今天为止应用已经相当广泛，而且随着时间推移和 技术发展，其普及趋势必将更加广泛而迅速。当前复杂的交通环境使用户对车辆导 航系统更加依赖。车辆导航系统在疏导交通，减少到达目的地时间提高车辆运行过 程安全性方面的贡献有目共睹。著名荷兰研究机构 TNO 最近公布了一项研究成果 证明了车辆导航系统对于交通安全的重要作用[2]。其主要研究结论如下：1中国科学技术大学硕士毕业论文绪论1. 2. 3. 4. 5.当在未知区域要行驶到未知目的地时，卫星导航系统的使用能够帮助车 辆驾驶者到达目的地。 卫星导航系统能够提高驾驶员的警惕性 ，缓解驾驶员压力。 没有使用卫星导航系统的驾驶员有 12%更大的可能性损坏车辆。 卫星导航系统的使用能够减少行驶距离的 16%。 车辆在未知区域要到达未知的目的地时，卫星导航系统能够 减少 18%的 行驶时间 。另外，该项研究还表明 ，导航系统能够减少车辆行驶过程中 50%的不恰当驾 驶操作。卫星导航系统能够使驾驶员集中注意力在车辆驾驶上而不是找路。 78%的 卫星导航系统用户感觉能够更好的掌控行驶过程中的各种状况。同时，卫星导航系 统能够减少驾驶员 20%的工作量 。 通常来说，导航系统有两个基本组成部分： 1）确定车辆地理位置的设备； 2）用来显示车辆位置的，由空间数字道路地图构成的地理信息系统（ GIS ）。最 常见的车辆定位方式有航位推测 （ DR）传感器 ，地面无线电 ，全球导航卫星系统 （如全球定位系统 GPS） ，和 集成导航系统（如集成航位推测和全球定位系 统）。 在过去二十年中，卫星导航系统，特别是美国的全球定位系统（ GPS）在陆 地车辆定位领域中占据了主导地位。尤其从 ２０００ 年 ５ 月，ＧＰＳ 的 Ｓ／Ａ（Ｓｅｌｅｃｔｉｖｅ　 Ａｖａｉｌａｂｉｌｉｔｙ）被美国政府取消后，ＧＰＳ 民用定位精度得到了很大的提高 。虽然 GPS 定位系统是当前比较准确的卫星全球定位系统， 但是定位过程中的误差是不 可避免的。在理想环境下的定位精度可以达到 １５ 米。实际上在城市建筑密集地区 以及山谷等影响 GPS 信号接收的环境下， GPS 的定位误差会不同程度的增大。与 此同时， 由于交通矢量地图的创建和数字化的过程中，不同程度的数字道路网误 差会被引入。定位系统的误差和交通地理信息系统的误差造成了导航过程中车辆位 置与对应行驶道路不匹配的情况。在交叉路口，环岛，和复杂的立体交叉道路场 合，这种不匹配的情况会更为严重。导航系统中的车辆位置匹配错误，不仅使用户 无法确定自己当前的准确位置，更不可能在这种情况下完成路径规划与交通引导的 功能。地图匹配算法就是针对这种匹配不准确问题设计的， 通过同时考虑车辆行 驶轨迹的历史信息和当前信息，以及交通矢量地图中的道路网拓扑结构，使车辆位 置准确匹配到其所行驶道路上的对应位置上。地图匹配算法对于 GPS 导航系统这 种单一定位设备的车辆导航系统有着非常重要的作用 。2中国科学技术大学硕士毕业论文绪论车辆导航系统包括两个重要部分，首先要在交通矢量地图上确定车辆当前行 驶所对应的道路，其次要确定车辆在这个地图道路弧上的准确对应位置。已经有很 多应用于车辆导航系统的地图匹配算法被提出，其中大部分的研究重点都在于如何 确定车辆行驶所对应的道路。确定对应道路是地图匹配的最基础任务，同时其正确 与否直接决定了对应车辆位置点确定的准确性。但是现有算法在给予匹配道路准确 性以其应有的重视的同时，并没有对车辆位置点的确定准确性给予足够的重视。大 部分都是在确定了匹配道路之后，简单的用垂直匹配方法完成匹配点的确定，也就 是过轨迹点做匹配道路的垂线，以垂足作为车辆位置的匹配点。这种情况造成了现 有算法无法有效校正定位系统和交通地图在沿道路方向的误差。当车辆在远离交叉 路口的道路弧上行驶时，这种不准确性还显示不出其危害性，但是当车辆在交叉路 口附近、转弯处或者其他复杂交通环境下，道路方向上的误差对于匹配准确性和可 靠性方面的影响就显示出来。甚至会危害到后续节点确定匹配道路过程的准确性。1.2 研究目标根据上面的介绍我们可以看出地图匹配算法对于车辆导航系统的重要性，同 时也能够了解到当前地图匹配算法存在的不足。随着交通状况的复杂，用户对车辆 导航系统准确性和可靠性的要求不断提高，新的更准确的地图匹配算法设计是提高 车辆导航系统准确性的一个重要途径 。 在这篇硕士论文的研究中，首先会调研已经提出的应用于导航系统的地图匹 配算法 ，找出现有算法的优缺点和问题所在。其次对 GPS 误差和地图误差进行分 析，总结其分布规律来为新算法的设计提供根据。在总结了现有算法和导航过程中 的误差之后，我们根据其特点设计能够提高车辆导航定位系统准确性和可靠性的地 图匹配算法，特别是对于现有算法没有解决的沿道路方向误差分量的校正提出可行 的解决方法。同时将设计的地图匹配算法实现并应用于实际运行的车辆导航系统， 通过实际导航过程来验证新地图匹配算法的效果 。1.3 论文安排论文的第二章会对车辆导航系统进行比较详细的介绍，使读者对整个研究的 背景和对象有更深入的了解。第三章介绍车辆导航系统中的误差和误差特点，主要 是 GPS 误差和交通电子地图误差。在第四章中会介绍 GPS 车辆导航系统中的地图 匹配算法问题、模型以及现有主要算法。论文第五章介绍新设计的利用虚拟差分修 正量来校正 GPS 轨迹的地图匹配算法。论文第六章介绍新的改进卡尔曼滤波地图 匹配算法 。第七章将对整个研究进行总结，并对今后的工作进行展望。3中国科学技术大学硕士毕业论文车辆导航系统介绍第二章 车辆导航系统介绍车辆导航系统作为智能交通系统的重要组成部分 ，起着基础而又重要的作 用。实际上根据采用的定位方式不同，当前有多种车辆定位系统，但是这些系统都 有相似的组成结构。本章我们将对车辆导航系统的功能、组成结构和不同的定位方 式进行介绍。使地图匹配算法在车辆导航系统中的应用有一个更明确具体的背景介 绍。其中将会 对 GPS 定位方式和 电子交通地图进行重点介绍。2.1 车辆导航系统功能车辆导航系统通常需要向用户提供与空间、时间相关的定位信息和引导提 示。具体来说 ，一个车辆导航系统通常需要以下功能： 定位功能 ，这是车辆导航系统最基本的功能 。通常包括显示车辆的经纬度 （以及海拔高度），并通过地理信息系统中的道路网信息 ，利用地图匹配算法在地 图道路上 显示车辆所在的位置，并且显示相关位置的道路、区域信息。 地图显示功能 ，用户可以通过调整显示的地图比例尺，来查看不同范围内， 不同区域的道路网信息。这种功能实际上是地理信息系统在车辆导航系统上的一个 简单任务实现 。 兴趣点查询 /显示功能， 这里所说的兴趣点是指用户感兴趣的、关心的 ，希望 获得其信息的位置对象，例如：旅馆，饭店，医院等。通常有多种查询方式，比 如，对指定城市指定区域查询范围内的兴趣点并显示，还有根据输入的兴趣点名称 来确定其所在的位置并显示，最常见的是显示车辆当前位置周围的兴趣点，给用户 提供以需要的出行信息 。 路径规划功能 ，通过用户输入起始位置和目的地（通常其实位置默认为当前 车辆所在位置），由车辆导航系统设计最优路径并输出给用户，这里的最优有多种 标准，包括时间最少，距离最短和交通状况最好等。路径规划功能不仅可以结合数 据库中存储的道路信息 ，而且可以实时通过无线通讯获得当前的交 通状况。 路径引导 ，路径引导功能是车辆导航系统区别于简单定位系统和 GIS 查询系 统的最典型区别。它规划好初始位置到目标位置的路径后 ，在每一个路口实时提醒 车辆驾驶人员接下来的行驶道路选择。以及当前距离目的地的距离和需要的时间估 算等信息 。4中国科学技术大学硕士毕业论文车辆导航系统介绍2.2 车辆导航系统的组成一个现代定位及导航系统通常由图 2.1 所示的部分或所有模块来组成；换句话 说，复杂的定位和导航系统需由代表不同功能和多种技术的模块来组成 。图 2.1 导航系统组成模块现在，将每个独立模块的功能总结如下： 定位模块融合不同传感器的输出，利用接 收到的无线电信号自动地确定车辆 或机动装置的位置，辨别正在行驶的公路和所要接近的每个交叉路口。典型的独立 定位技术是推算定位，而典型的无线电信号定位技术是使用全球定位系统（ GPS） 接收机。为了融合不同传感器的输出 ，现在研制出许多不同的融合方法 。 数字地图数据库也就是交通矢量地图 ，包含预先定义好存储格式的数字地图 信息，这样的存储格式有助于计算机处理与地图有关的信息，如辨别场所、公路等 级、交通规则和旅行信息等等。因为地图是用来表示地球表面的几何形状的，为了 开发和利用地图的各种功能，必须清楚不同地图数据库所用的相对参考坐标系。为 了缓解处理不同数字地图所遇到的麻烦，人们试图制定统一的标准以引导研制和应 用。 地图匹配是把 测量到的或从定位模块获取到的位置（轨迹）与地图数据库所 提供的基于地图的位置（路径）进行匹配来确定车辆在地图上位置的一种方法。如 果数据库相当准确，这一技术能改进定位模块的精确度。对于市区来说，数字地图 数据库的精度应保持在 15m 以内。地图匹配部分算法的改进正是这篇论文的研究 对象。5中国科学技术大学硕士毕业论文车辆导航系统介绍路径规划是帮助司机在行驶前或运行中规划路线的过程 ，这个过程是根据地 图数据库模块所提供的地图，如果可能的话再加上从无线通信网络收到的实时交通 信息来实现的。 通常采用技术是找到最小旅行代价路线，旅行代价可以是时间、 距离或选择路线的复杂度等等。 路径引导是指挥司机沿着由路径规划模块计算出的路线行驶 的过程。为了确 定车辆当前的位置和产生适当的实时引导指令（通常是转弯接着转弯或一次转 向），需要借助地图数据库和精确的定位。 人机接口允许用户与定位和导航计算机及装置进行人机交互 。地图显示、路 径规划、路径引导和其他活动的各种不同要求通过这个人机接口送到计算机中，然 后再通过这个接口模块反馈给用户。 无线通信模块进一步改进系统的性能和增加系统的功能 。通过一个或多个不 同种的通信网络，车辆和它的使用者或交通管理系统能够接收实时交通信息或报 告，这样就促使了车载系统或整个公路网络工作的更加安全和有效。此外，一个基 于无线信息和通信技术的中央遥控设施甚至能通过它的系统去帮助车辆定位和导 航。 定位模块和数字地图数据库模块是其中最基本最重要的两个模块，而地图匹 配算法起着连接这两部分的作用 。2.3 车辆定位系统定位模块是车辆定位与导航系统的重要组成部分。为了使用户获知车辆位置 或者向用户提供操纵指示，必须精确确定车辆的位置。对于任何性能良好的车辆定 位与导航系统来说 ，精确、可靠的车辆定位是必要的先决条件。 在车辆导航系统 中，车辆定位子系统负责实现定位模块的功能，为导航系统提供车辆的实时位置以 及方向、速度等运动状态信息。 常用的定位技术有三种：独立定位技术、卫星定位技术和地面无线电定位技 术[3]。推算定位（ Dead reckoning）是典型的独立定位技术。卫星定位技术 是把卫星定位接收器安装在车辆上来获得车辆位置。推算定位和 GPS 技术已广泛应用于 车辆上。下面我们具体介绍各种定位技术以及其特点 。 航位推算系统是根据已知位置，利用车辆运行的方向，速度，时间和距离信 息来估测车辆当前位置。有一系列的传感器种类可以用来获得对象的方向信息（如 陀螺仪，罗盘）和行驶距离（如里程表和加速度仪）。使用航位推测来获得位置的6中国科学技术大学硕士毕业论文车辆导航系统介绍准确性很大程度上决定于这些传感器的性能。通常使用的这些航位推测传感器会有 刻度误差（老化和制造工艺原因）和非线性误差。由于这些误差的存在，航位推测 系统的位置、速度和方向信息的误差会随之时间的增加而积累。用户设备由于购 买、操作和维护费用的存在，价格普遍教高。另外，航位推测系统的耗电量虽然会 随着体积和重量的减小而缩减，但仍然比 GPS 接收器的耗电量高。综合以上因 素，航位推测定位系统并不适合 单独作为当前车辆导航系统的定位设备 。 地面基站无线电定位系统，是通过一个信号塔向外广播其自身位置，临近的 接收器获得信号后，利用接收到的信号来确定自身的位置 。虽然该系统的误差不会 随时间累计，但是系统的使用受到地域和信号覆盖面积的限制，而且价格比较高， 当前使用的也很少 。 卫星导航系统 采用导航卫星对地面、海洋、空中和空间用户进行导航定位。 利用太阳、月球和其他自然天体导航已有数千年历史，由人造天体导航的设想虽然 早在 19 世纪 后半期就有人提出，但直到 20 世纪 60 年代才开始实现。 1964 年美国 建成 “ 子午仪” 卫星导航系统，并交付海军使用， 1967 年开始民用。 1973 年又开 始 研制 “ 导航星” 全球定位系统。苏联也建立了类似的卫星导航系统。中国、法国、日 本也开展了卫星导航的研究和试验工作。卫星导航综合了传统导航系统的优点，真 正实现了各种天气条件下全球高精度被动式导航定位。特别是时间测距卫星导航系 统，不但能提供全球和近地空间连续立体覆盖、高精度三维定位和测速，而且抗干 扰能力强。卫星导航系统由导航卫星、地面台站和用户定位设备三个部分组成。导 航卫星是卫星导航系统的空间部分，由多颗导航卫星构成空间导航网。地面台站跟 踪、测量和预报卫星轨道并对卫星上设备工作进行控制管理，通常包括跟踪站、遥 测站、计算中心、注入站及时间统一系统等部分。跟踪站用于跟踪和测量卫星的位 置坐标。遥测站接收卫星发来的遥测数据，以供地面监视和分析卫星上设备的工作 情况。计算中心根据这些信息计算卫星的轨道，预报下一段时间内的轨道参数，确 定需要传输给卫星的导航信息，并由注入站向卫星发送。用户定位设备：通常由接 收机、定时器、数据预处理器、计算机和显示器等组成。它接收卫星发来的微弱信 号，从中解调并译出卫星轨道参数和定时信息等，同时测出导航参数（距离、距离 差和距离变化率等），再由计算机 算出用户的位置坐标（二维坐标或三维坐标）和 速度矢量分量 。用户定位设备分为 船载、机载、车载和单人背负等多种型式 。 目前正在运行的全球卫星定位系统有美国的 GPS 系统和俄罗斯的 GLONASS 系统。 欧盟 1999 年初正式推出 “ 伽利略” 计划，部署新一代定位卫星。 该方案由7中国科学技术大学硕士毕业论文车辆导航系统介绍27 颗运行卫星和 3 颗预备卫星组成，可以覆盖全球，位置精度达几米， 亦可与美 国的 GPS 系统兼容，总投资为 35 亿欧元。 该计划预计于 2010 年投入运行。 另 外，中国还独立研制了一个区域性的卫星定位系统― ― 北斗导航系统。 该系统的 复盖范围限于中国及周边地区，不能在全球范围提供服务，主要用于军事用途。 GPS 全称是 Global Positioning System, 是美国国防部研制的一种全天候的，空 间基准的导航系统，可满足位于全球任何地方或近地空间的用户连续地精确地确定 三维位置和三维运动及时间的需要。它是一个中距离圆型轨道卫星导航系统。它可 以为地球表面绝大部分地区（ 98%）提供准确的定位 、测速和高精度的时间标准。 该系统的组成包括太空中的 24 颗 GPS 卫星；地面上的 1 个主控站、 3 个数据注入 站和 5 个监测站及作为用户端的 GPS 接收机。最少只需其中 4 颗卫星，就能迅 速 确定用户端在地球上所处的位置及海拔高度；所能收联接到的卫星数越多，解码出 来的位置就越精确。该系统是由美国政府于 20 世纪 70 年代开 始进行研制于 1994 年全面建成。使用者只需拥有 GPS 接收机，无需另外付费。 GPS 信号分为民用的 标准定位服务（ sps, standard positioning service)和军规的精密定位服务（ pss, precise positioning service)两类。民用讯号中加有误差（ SA），其最终定位精确度大概在 100 米左右；军规的精度在十米以下。 2000 年以后，美国政府决定取消对民用信号 所加的误差 (SA)。因此，现在民用 GPS 也可以达到十米左右的定位精度。 GPS 系 统拥有如下多种优点：全天候，不受任何 天气的影响；全球覆盖（高达 98% ）； 三维定速定时高精度；快速、省时、高效率；应用广泛、多功能；可移动定位；不 同于双星定位系统，使用过程中接收机不需要发出任何信号增加了隐蔽性，提高了 其军事应用效能。 GPS 导航系统的基本原理是测量出已知位置的卫星到用户接收机之间的距 离，然后综合多颗卫星的数据就可知道接收机的具体位置。要达到这一目的，卫星 的位置可以根据星载时钟所记录的时间在卫星星历中查出 。而用户到卫星的距离则 通过纪录卫星信号传播到用户所经历的时间，再将其乘以 光速得到。由于大气层电 离层的干扰，实际应用中这一距离并不是用户与卫星之间的真实距离，而是伪距 （ PR）。 当 GPS 卫星正常工作时，会不断地用 1 和 0 二进制码元组成的伪随机码（简 称伪码）发射导航电文。 GPS 系统使用的伪码一共有两种，分别是民用的 C/A 码 和军用的 P(Y)码。 C/A 码频率 1.023MHz, 重复周期一毫秒，码间距 1 微秒，相当于 300m； P 码频率 10.23MHz，重复周期 266.4 天，码间距 0.1 微秒，相当于 30m。而8中国科学技术大学硕士毕业论文车辆导航系统介绍Y 码是在 P 码的基础上形成的，保密性能更佳。导航电文包括卫星星历、工作状 况、时钟改正、电离层时延修正、大气折射修正等信息。它是从卫星信号中解调制 出 来，以 50b/s 调制在载频上发射的。导航电文每个主帧中包含 5 个子帧每帧长 6s 。前三帧各 10 个 字 码； 每 三 十 秒 重 复 一 次， 每小时更新一次 。后 两 帧 共 15000b。导航电文中的内容主要有遥测码、转换码、第 1、 2、 3 数据块，其中最重 要的则为星历数据 。当用户接受到导航电文时，提取出卫星时间并将其与 自己的 时钟做对比便可得知卫星与用户的距离，再利用导航电文中的卫星星历数据推算出 卫星发射电文时所处位置，用户在 WGS-84 大地坐标系中的位置速度等信息便可得 知。可见 GPS 导航系统卫星部分的作用就是不断地发射导航电文。然而，由于用 户接受机使用的时钟与卫星星载时钟不可能总是同步，所以除了用户的三维坐标 x、 y、 z 外，还要引进一个 ? t 即卫星与接收机之间的时间差作为未知数，然后用 4 个方程将这 4 个未知数解出来。所以如果想知道接收机所处的位置，至少要能接收 到 4 个卫星的信号 。 由于 GPS 定位的稳定性好 ，精度相对较高（尤其是 S/A 人为干扰取消以 后）， GPS 接收机价格低廉。通常的车载定位系统都以 GPS 定位为主。尽管 GPS 在车载导航系统中应用非常广泛 ，由于系统误差和随机误差的影响[3]，通过 GPS接收器获得的车辆位置与车辆的实际位置还是有几十米的误差。当需要较高定位精 度时可以采用 GPS 结合其他定位方法的方式进行定位。最典型的是通过卡尔曼滤 波器结合 GPS 定位系统与航位推测系统组成组合导航系统。不过，结合定位设备 的价格因素和使用的精度要求，民用车载导航系统一般是采用单独的 GPS 接收设 备进行车辆定位。这也是当前应用最广的车辆地位方式。通过独立车载 GPS 接收 器获得车辆位置的导航系统简称为 GPS 车辆导航系统 。2.4 数字地图 数据库数 字 地 图 数 据 库 是 地 理 信 息 系 统 的 一 种 。 地 理 信 息 系 统 (Geographic information system，简称 GIS) 系统，也称作地理资讯系统。 GIS 是一门综合性学 科，已经广泛的应用在不同的领域.，是用于输入、存储、查询、分析和显示地理 数据的计算机系统。一个地理信息系统(GIS) 是一种具有信息系统空间专业形式的 数据管理系统。在严格的意义上, 这是一个具有集中 , 存储 , 操作 , 和显示地理参考信 息的计算机系统。例如， 根据在数据库中的位置对数据进行识别。 地理信息系统 技术能够应用于科学调查, 资源管理 , 财产管理、发展规划、绘图和路线规划。 例9中国科学技术大学硕士毕业论文车辆导航系统介绍如 , 一个 GIS 系统能使应急计划者在自然灾害的情况下较易地计算出应急反应时间, 或利用 GIS 系统来发现那些需要保护不受污染的湿地。 地理信息系统具有以下 三个方面的特征： ①具有采集、管理、分析和输出多种地理空间信息的能力，具有空间性和动 态性；　 ②以地理研究和地理决策为目的，以地理模型方法为手段，具有区域空间分 析、多要素综合分析和动态预测能力 ，产生高层次的地理信息 ；　 ③由计算机系统支持进行空间地理数据管理，并由计算机程序模拟常规的或 专门的地理分析方法，作用于空间数据，产生有用信息，完成人类难以完成的任 务。　 在交通导航应用中使用的地理信息系统主要是数字地图数据库。我们所说的 GIS 往往是一个比较庞大的系统，而且包含了很多各类数据管理、决策的模块，它 是一种针对性比较强的系统，对于不同的用户，往往对数据有不同的操作、管理、 决策。但是它毕竟是一个以地理空间分布数据为基础的系统，所以有一个因素不能 少，那就是电子地图，它为系统提供最基本的地理信息。 电子地图按照其数据结构的不同，又主要分为矢量电子地图和栅格电子地图 两种，栅格电子地图也就是我们平时常见的位图。 矢量地图是指对点阵数据数字 地图图像进行跟踪识别得到的矢量数据以后的地图，然后对地图中线状地物如河 流、等高线、铁路、公路、等进行恢复，恢复的结果就是一幅矢量地图。在矢量地 图上可以方便的进行放大和缩小变换 。 电子地图的这两种实现 ，各有优缺点。栅格电子地图 ，主要是生成比较方 便，图像比较细致，和人们日常使用的地图类似，容易被用户接受，但是，栅格电 子地图数据量比较大，存储不方便，放大过程中会产生失真，数据不是很准确，很 难进行全局或者局部校正，更新起来也比较费事。矢量电子地图生成相对费事，但 是数据经过压缩，数据量小，地图可以随意缩放，缩放过程中不会失真，可以进行 全局或者局部校正，更新起来也很方便。例如成都市地图 ，按照比例尺 1： 200000 （约） ，转化为 24 位位图，大约 15M，而我们生成的矢量地图数据库 ，只有 137K ，近 3000 条道路（矢量边）的矢量文件大小只有约 61K。可见矢量电子地图 的优越性 。 绝大多数 GIS 系统中使用的地图是以矢量地图作为其表现形式的。如何来组10中国科学技术大学硕士毕业论文车辆导航系统介绍织一份矢量地图呢？数据是矢量地图的核心，电子地图可以看作由点、线、面这三 种几何对象以及它们的属性数据构成的数据的集合，所以我们引入了地图矢量库和 地图数据库这两个概念 [4]。矢量库是一组图形描述数据，保存了地图的几何数据； 数据库则是一组描述数据，保存地图各种几何对象的属性数据，二者之间通过地物 对象的序号建立索引关系， 如图 2.2。 一副地图可以看成是由点、线、面三种几何图形构成的 。点指的是单位之类 的地物实体，线则是道路、铁路之类的实体，而区划这类的实体就可以用面来表 征。依照传统的习惯，把点、线、面这三类地物按照从上到下的顺序排列。生成、 编辑电子地图的过程就是生成、编辑地图矢量库和数据库的过程，下面我们来详细 介绍一下这两个最重要的库 。矢量 地 图地图矢量库 图形数据组序号地图数据库 描述数据组图 2.2 矢量地图的组成2.4.1 地图矢量库矢量地图的最大特征就是用一系列的节点来表示整个道路网和其他相关的地 理对象[5]。节点之间的拓扑连接信息是节点构成道路和其他对象的基础。若干组节点构成弧段，若干组弧段构成道路 [6]。矢量地图的基本地理结构如图 2.3 所示对矢 量道路有如下基本定义 ：716 2 3 4 58节点：大节点： 1, 4, 7, 8 小节点： 2, 3, 4, 5 弧段：S1 [1, 2, 3, 4]， S2 [4, 5, 6, 7] ， S3 [4, 8] 道路：以上弧段任意组合均可能构成道路。图 2.3 矢量地图道路拓扑结构定义11中国科学技术大学硕士毕业论文车辆导航系统介绍1) 节点集合 N R (道路 ) 节点集合 N R 由线实体上所有的 N 个节点 ni = [ xni , yni ] 构成：TN R = {ni | i = 1,2,..., N } (1)式中节点 ni 在矢量交通地图上代表的实际经度与纬度分别记为 xni 与 yni 。 2) 弧段集合 S R 弧段集合 SR 由矢量地图上所有的 n 条弧段 Sk 构成：S R = { S k | k = 1, 2,..., n S }S(2)第 k 条弧段 S k 由组成它的所有 n k 个节点 nik 顺序构成：S k = {nik ∈ N R | i = 1,2,..., n k } (3)上式并隐含节点 nik 之间的顺次连接关系。弧段与其它弧段的相交只可能发生 在该弧段的端点处 ，即 n1k 或 n n k 。表示弧段端点的节点，称为大节点。弧段所包 含的除端点之外的节点称为小节点。大节点实际上就是道路交叉路口的中心点 (除 了地图边缘的道路终端点)，车辆从一条弧段转向另一条弧段必经过大节点，并且 这个大节点一定既是本条弧段的端点同时又是另一条弧段的端点。基于弧段端点在 实时地图匹配 中的特殊位置 ，本文对弧段端点例如 n j 将特别地记为 n j 。 3) 道路 R k 。道路是若干条弧的集合。 实时地图行驶道路匹配实际上是对组成 道路的弧段的 匹配。k2.4.2 地图数据库地图数据库中包含了各种地物的属性数据。 对于面地物，需要知道的属性有：类型、位置、形状、名称、颜色等； 对于点地物，需要知道的属性有：类型、位置、名称、显示图标、显示级别 等； 对于线地物，需要知道的属性有：类型、位置、形状、名称、颜色、显示宽 度、显示级别等； 上面提到的各种地物的属性数据中都有一项――类型，也就是它所属的组 （ Group） 。组，定义出了某一批地物的缺省属性，是一些具有相同或相近属性的 同类地物的集合。12中国科学技术大学硕士毕业论文车辆导航系统中的误差分析第三章 车辆导航系统中的误差分析GPS 车辆导航系统作为多功能模块的组合系统 ，不可避免的在其工作中会引 入以及受到一些模块误差的影响。这其中对 GPS 车辆导航系统影响比较大的主要 是定位模块中 GPS 定位信息的误差 以及地图数据库系统中交通道路网的位置误 差。对这些误差的种类 、产生原因以及其特点的深入研究与分析，是克服其对 GPS 车辆导航系统不利影响 ，设计有效地图匹配算法 的基础。3.1GPS 误差GPS 信号从卫星中发出到被车载 GPS 接收机获得并计算出车辆位置和其他运 行信息的过程中，有多种因素会影响到车辆从 GPS 信息获得的位置的准确性。 从 2000 年 5 月， GPS 的 S/A(Selective Availability)被美国政府取消后，理想环境下的 GPS 定位精度已经可以达到 20 米以内，实际上在城市建筑密集地区以及山谷等影 响 GPS 信号接收的环境下， GPS 的定位误差会不同程度的增大。影响 ＧＰＳ 信号准 确性的各种误差其性质各不相同，仔细比较研究各种误差的性质，是我们校正这些 误差的基础。　3.1.1 GPS 误差分类　GPS 误差主要包括以下几个方面卫星星历误差 、卫星钟差、电离层延迟、对 流层延迟、多路径效应、天线位置误差以及接收机软件和硬件造成的误差，总的来 说可以分为系统误差和随机误差 系统误差 ： １．　卫星星历误差　 在进行 ＧＰＳ 定位时，计算在某时刻 ＧＰＳ 卫星位置所需的卫星轨道参数是通过 各种类型的星历提供的，但不论采用哪种类型的星历，所计算出的卫星位置都会与 其真实位置有所差异，这就是所谓的星历误差。 　 ２．卫星钟差　 卫星钟差是 ＧＰＳ 卫星上所安装的原子钟的钟面时与 ＧＰＳ 标准时间之间的误 差。　 ３．卫星信号发射天线相位中心偏差 　[3]。13中国科学技术大学硕士毕业论文车辆导航系统中的误差分析卫星信号发射天线相位中心偏差是 ＧＰＳ 卫星上信号发射 天线的标称相位中心 与其真实相位中心之间的差异。 　 ４．电离层延迟　 由于地球周围的电离层对电磁波的折射效应，使得 ＧＰＳ 信号的传播速度发生 变化，这种变化称为电离层延迟。电磁波所受电离层折射的影响与电磁波的频率以 及电磁波传播途径上电子总含量有关 。　 ５．对流层延迟　 由于地球周围的对流层对电磁波的折射效应，使得 ＧＰＳ 信号的传播速度发生 变化，这种变化称为对流层延迟。电磁波所受对流层折射的影响与电磁波传播路径 上的温度 、湿度和气压有关 。　 ６．接收机钟差　 接收机钟差是 ＧＰＳ 接收机所使用时钟的钟面时与 ＧＰＳ 标准时之间的差异 。　 ７．接收机天线相位中心偏差　 接收机天线相位中心偏差是 ＧＰＳ 接收机天线的标称相位中心与其真实的相位 中心之间的差异。 　 随 机 误 差 ：　 １．　多路径效应 　 由于接收机周围环境的影响，使得接收机所接收到的卫星信号中还包含有各 种反射和折射信号的影响，这就是所谓的多路径效应 。　３．１　多路径误差　　　 ２．　接收机软件和硬件造成的测量噪声　14中国科学技术大学硕士毕业论文车辆导航系统中的误差分析在进行 ＧＰＳ 定位时，定位结果还会受到处理与控制软件和硬件等的噪声影 响。　 在以上介绍的各种误差中接收机钟差 、接收机天线相位中心偏差、接收机软 件和硬件造成的误差随所采用的 ＧＰＳ 接收设备不同而不同 。　 其他误差范围如下表所示 ：　表 ２．１　ＧＰＳ　误差　［３］　 误差源 　 卫星轨道与时钟偏差 　 电离层误差 　 对流层误差 　 接收测量误差　 多路径误差 　 误差和 　误 差 范 （ＵＥＲＥ）　 ２．３　 ７．０　 ０．２　 ０．６　 １．５　 ７．５　围 　独立 ＧＰＳ　水平误差（ＨＤＯＰ＝１．５）ＨＤＯＰ 为 ＧＰＳ 定位 ２２．５ 水平位置精度系数　 （＝２＊７．５＊１．５）　 　3.1.2 各种类误差特点通过我们上面的误差成因分析可以看出，多路径误差和 接收机软件硬件造成 的测量噪声在车辆运行中是随机变化的，当前时刻和前一时刻的误差没有关系，这 类误差也可以称其为不稳定的跳跃误差；系统误差中的各项虽然没有准确的计算方 式，但是它们的误差值在一定时间段内会保持相对稳定的 ，也就是说当前时刻的误 差值与前一时刻（或一定时间内的）的误差值相比变化比较小，可以称其为相对稳 定的慢漂移误差， 简称慢漂移误差。　 系统误差在相邻时刻或者短时间间隔内具有高度相关性 ，这意味着在相似环 境下较短时间内， GPS 主要误差相对稳定 [15]。有效利用 GPS 误差的这种特性使新 地图匹配算法能够利用历史时刻的轨迹偏差作为虚拟差分量对 GPS 轨迹位置进行 有效的校正，特别是对于其他算法不能有效处理的沿道路方向上的误差进行克服。 对于 GPS 轨迹位置主要误差的慢漂移特性以及时间与空间的相关性，我们通 过对实际观测数据的统计也证明了这种慢漂移性和相关性的存在，如图 3.2，图 3.3 所示。15中国科学技术大学硕士毕业论文车辆导航系统中的误差分析图 3.2 GPS 轨迹信息中位置信息误差的期望随时间的变化图 3.3 GPS 轨迹位置信息误差的自相关函数图 3.2 中车辆位置观测值的误差期望是渐变的，当车辆在同一路段或者相邻路 段上行驶时（时间 &300s） ，误差的期望值在定位的精度范围内基本保持不变 （ &1m），也就是说在一段连续时间内 GPS 的误差有相似趋势（方向和大小）。 图 3.3 中，位置观测误差的自相关函数并不是冲激函数 δ (k ) ，这说明从 GPS 车载 接收器获得的车辆位置信息并不是白噪声，当前时刻的位置概率分布与前面时刻 有关。总结两幅图的信息我们可以知道， GPS 轨迹误差并不总是均值为 0 的均匀 分布，在某段时间内总有一个相对稳定的偏差量， GPS 误差以这个偏差量为中心16中国科学技术大学硕士毕业论文车辆导航系统中的误差分析均匀分布，这正是慢漂移误差与随机误差共同作用的结果； GPS 轨迹误差与历史 轨迹误差有关 ，根据历史误差可以对当前误差进行估计或者预测。3.1.3 常见克服 GPS 误差方法在利用 GPS 进行定位或导航的应用中，多种方法被用来降低 GPS 误差带来的 影响，其中既有基于硬件的方法也有软件的方法。主要包括三种：差分 GPS、组 合定位以及滤波和地图匹配算法 。其中前两种主要靠硬件方式提高 GPS 轨迹的准 确度，第三种方法主要是软件算法上的实现。 3.1.3.1 差分 GPS图 3.4 差分 GPS 示意图为了消除或者减少 GPS 误差使民用的精确度提升，采用利用地面确定位置基 站协助 GPS 定位的方法，称为差分全球定位系统(Differential GPS), 简称 DGPS 。在 固定地点的基站通过自己的位置和接收到的 GPS 卫星信号来估算当前时刻各个 GPS 卫星信号的误差。也就是利用已知位置处的 GPS 误差来估算位置位置处的 GPS 误差，亦即利用附近的已知参考坐标点 (由其它测量方法所得 ), 来修正 GPS 的 误差。再把这个实时 (Real time) 误差值加入本身坐标运算的考虑 , 便可获得更精确 的值，前提是 GPS 信号对应的是相同的卫星也就是基站与差分 GPS 用户在临近区 域。17中国科学技术大学硕士毕业论文车辆导航系统中的误差分析差分 GPS 对于处理卫星位置和大气层延迟误差具有非常明显的效果，因为这 些误差在基站与临近 GPS 接收器之间是相关或者说相似的。 差分 GPS 主要能够校正共性误差，也就是说在基站和普通接收机上都有相似 取值的误差。多路径误差、硬件噪声、接收机钟差和天线位置误差等都无法克服。 差分 GPS 用户距离基站距离越近 ，克服误差的效果越好。 3.1.3.2 组 合 定 位系 统 单独的 GPS 定位系统无法获得车辆的准确位置，如果与其他定位设备或者传 感器进行信息融合，他们之间互相进行补偿组成组合导航系统，可以得到更高的定 位精度。组合信息通常来源于一个时间周期的多个传感器 ，或者来自于延长时间周 期的单个传感器。组合定位系统具有提供高精度和容错的潜力 。 多传感器集成 和融合给一个系统提供额外的益处。这包括坚固的操作性能， 扩展的空间覆盖，扩展的时间覆盖，增强的可信度，改进性能，增强空间分辨率， 提供系统操作的可靠性，增加了维数，各种设备的充分利用以及减少模糊等等。尽 管传感器融合有许多优点，但大多数融合方法明显地或隐含地产生某些假设。如果 假设的传感器模型不能恰当地描述来自真实传感器数据，则一个完美的传感器模型 和评价理论也不可能产生所期望的结果。当前使用比较普遍的传感器融合模型是卡 尔曼滤波器。 3.1.3.3 滤 波 和 地 图 匹 配 算 法 滤波和地图匹配算法是克服 GPS 误差的软方法。通过一些滤波器，如卡尔曼 滤波器，对 GPS 信号进行滤波，可以一定程度上消除 GPS 的随机误差。实际上对 GPS 误差有更好校正效果的是地图匹配算法。地图匹配算法的目标是将从 GPS 获 得的带有误差的车辆位置匹配到交通矢量地图的对应道路对应点上。当交通矢量地 图是准确的时，通过地图匹配算法获得的地图上的映射位置就是车辆的准确位置， 也就是通过地图匹配误差和准确地图信息消除了 GPS 位置信号中的误差影响 。 地图匹配算法是我们的研究重点，卡尔曼滤波也是我们要应用的工具，在论 文后面的部分中会进一步详细介绍。3.2 交通矢量地图误差鉴于矢量地图准确性对整个智能交通系统都有着非常重要的作用，如何提高 其准确性是当前研究的一个重点。通过现代的高精度测量手段、改进矢量地图生成18中国科学技术大学硕士毕业论文车辆导航系统中的误差分析方法和对矢量地图校正方法的研究[7]，当前许多大城市的地图已经非常准确了，特别是欧美等国家的交通矢量地图准确性非常高。但是对于交通矢量地图来说，要 完全消除一个区域地图的所有误差是不可能的。交通矢量地图误差的研究，特别是 对于道路网位置误差的研究，是提高 GPS 车辆导航系统准确性可靠性的一个重要 方面，而实际上对交通矢量地图误差的分析，以及在地图匹配算法中进行处理是当 前大部分相关 研究都忽视了的一个方面。3.2.1 矢量地图生成过程简介要研究矢量地图的误差，我们必须清楚矢量地图的生成过程 ，从而才可能知 道误差的来源。要生成一副交通矢量地图，首先是生成地图的矢量文件，生成矢量 地图的拓扑结构――矢量库。通常的方法是采用从点位图中识别、生成矢量地图的 方式。我们将从纸制地图扫描得到的点位图进行识别，提取出其中的道路信息，然 后将这些道路信息矢量化得到一副只包含道路信息的矢量文件，将这作为一副矢量 地图的基础。然后，在这个基础上进行编辑、校正，并输入各种地图上的有关数 据，生成电子地图的数据库，最终生成一个完整而准确的矢量地图[5]，如图 3.5 所 示。彩色地图 彩色地图识别地图矢量化软件 MapHandle线状的黑白位图矢 量 文 件矢量地图编辑软件 MapEditor完整而准确的矢量地图( 矢量库和数据库) GPS 或 GIS 应用系统图 ３．５ 交通矢量地图的生成　19中国科学技术大学硕士毕业论文车辆导航系统中的误差分析从图 3.5 的框图中我们可以看出生成一副较完备矢量交通地图，主要包括以下 三个步骤 ： ①彩色地图的道路识别；　 ②地图矢量化；　 ③矢量地图的校正和地图信息的添加；　 彩色地图的道路识别，就是根据一幅彩色交通地图，利用一定的算法，提取 出其中的道路、区域信息，形成一幅黑白位图 [4]。地图矢量化则是根据得到的线状 的黑白位图抽取出有意义的模式特征。矢量化后的地图经过校正和添加地图信息就 可以应用于车辆监控和导航系统了。3.2.2 交通矢量地图误差分析通过上面交通矢量地图生成过程的介绍，我们知道了其重要的三个步骤：彩 色地图的道路识别，地图矢量化，矢量地图的校正和地图信息的添加。对于地图误 差来源的分析 ，也就从这三个步骤入手。 首先在彩色地图道路识别的步骤中，原始的彩色地图（扫描地图或者航拍地 图）是带有误差的，包括整体线性误差和局部非线性误差 。这些误差在道路识别过 程中必然会被带入到识别的道路网中，并且道路识别过程中的模式匹配算法的不完 善也会加入新的误差。 在地图矢量化过程中，需要先将第一步得到的道路网中道路的宽度缩小到 1 个像素单位，在这一过程中由于原始地图道路宽度的不均匀，得到的结果可能会有 与原始道路状况不符合的道路线弯曲。在接下来的地图道路矢量化过程中，也会产 生一些地图的局部误差 。 经过最后一步的矢量地图校正，大部分道路网位置误差可以得到修正，但是 在地图的局部位置，由于校正过程中采样点密度不够或者分布不够均匀，会残留局 部的非线性误差，包括平移误差和旋转误差 。 通过论文第二章对矢量交通地图的结构介绍，我们可以知道 ，对矢量交通地 图，节点是形成交通道路网络最基本的单元。节点位置精度唯一决定了道路位置的 精度。在交通矢量地图中不管哪一种道路位置的不准确都是由节点位置不准确引起 的。图 2中是交通矢量地图中平移误差和局部旋转误差的示意图。实线表示的是地 图上的道路，虚线表示的是道路在地图上准确位置的所在 。图中的箭头表示地图上 点与准确位置之间的偏差关系。20中国科学技术大学硕士毕业论文车辆导航系统中的误差分析图 3.6 交通矢量地图中道路的平移误差和旋转误差从图 3.6 中我们可以看出，地图道路上相邻两点的误差是连续的，也就是说沿 某一条道路，其地图位置与实际位置是连续渐变的。地图误差的这种连续变化特性 也是可以在地图匹配算法中加以利用来克服地图误差带来的匹配误差。而且由于使 用中的交通矢量地图都是按照经纬度经过一定的校正处理 ，所以不会有大幅度的变 化，其连续慢变化的特性与 GPS 误差中的慢漂移误差的缓慢变化相似。21中国科学技术大学硕士毕业论文地图匹配问题以及现有算法介绍第四章 地图匹配问题以及现有算法介绍车辆导航系统实时接收 GPS 位置速度信息，以交通地图为背景显示车辆行驶 轨迹。保证所显示的轨迹反映车辆的实际行驶过程，包括行驶路段，转弯过程及当 前位置，就是地图匹配问题所要解决的目标。本节首先对地图匹配问题涉及到的基 础概念、误差模型给出简要说明，同时介绍当前流行的一些地图匹配算法的思路与 特点。4.1 地图匹配 问题介绍利用车载 ＧＰＳ 接收机实时获得车辆轨迹，进而确定其在交通矢量地图道路上 的位置，是当前车载导航系统的基础。独立 GPS 车载导航系统中克服 GPS 误差以 及地图误差显示车辆在道路网上的位置主要是通过地图匹配算法，也就是根据 GPS 信号中的数据和地图道路网信息，利用几何方法、概率统计方法 、模式识别 或者人工神经网路等技术将车辆位置匹配到地图道路上的相应位置[8-12]。由于行驶中的车辆绝大部分都是在道路上的，所以通常的地图算法都有一个车辆在道路上的 默认前提。地图匹配的准确性决定了 GPS 车辆导航系统的准确性、实时性 与可靠 性。具体来说取决于两方面：确定当前车辆正在行驶的路段的准确性与确定车辆在 行驶路段上的位置的准确性。前者是现有算法的研究重点，而后者涉及到沿道路方 向的误差校正，在现有算法中还没有得以有效解决。地图匹配的目标是将轨迹匹配 到道路上，当道路是准确的时，也就成了确定 GPS 的准确位置，然后利用垂直映 射方法完成匹配。要实时获得车辆所在的道路及位置通过地图匹配来实现是一种比 较普遍而且成本较低的方法。车辆导航与定位系统中的地图匹配问题概括来讲就是 将车载 GPS 接收机获得的带有误差的 GPS 轨迹位置匹配到带有误差的交通矢量地 图道路上的相应位置。下面我们通过具体的数学模型来给地图匹配问题以详细的数 学描述。 地图匹配的基本过程如图 4.1 所示。符号定义及其物理意义说明如下： 1) g ( k ) 是车辆 GPS 轨迹点 ，内容为 k 时刻车辆上的 GPS 定位数据（经纬 度），对应于矢量地图上相应的经纬度位置点。由于 GPS 误差和矢量地图误差的 存在，当车辆在道路弧段 Si 上行驶时 ， g ( k ) 通常并不位于弧段 S i 上。 2) p (k ) 为 g ( k ) 的地图道路匹配点 ，表示地图匹配算法对 g (k ) 进行偏差修正获 得的车辆 k 时刻在矢量地图道路上的对应点，简称 g ( k ) 的匹配点。匹配点所在矢量 地图弧段 S i 上的位置，应该尽可能反映出实际车辆在该段道路上的相应位置。22中国科学技术大学硕士毕业论文地图匹配问题以及现有算法介绍3) e( k ) 为 g ( k ) 的地图匹配修正量，表示 g ( k ) 与其匹配点 p (k ) 间的误差修正。 需要指明匹配点所在的弧段 p (k ) ∈ Si 时，使用符号 e( k )[ S i ] 表示 g ( k ) 对于弧段 Si 上 的匹配点所使用的匹配修正量。上述 3 个基本量之间的关系如图画所示，即p (k ) = g (k ) + e ( k )(4)地图匹配修正量 e( k ) 源自于 GPS 定位误差和交通矢量地图精度误差的综合误 差效应。S k1S k2 ni S k3e(k)p( k )g(k )v v Siv hSiv yv xev (k )q ( k)eh (k)v hSiS kinjS k6S k5图 4.1 地图匹配模型4) e( k ) 的正交分解 将 e( k ) 正交分解为弧段横向修正量 ev (k) ∈ R与弧段纵向 修正量 eh (k) ∈ R ，有 (5) v v 式中 e( k )[ S i ] 的纵向单位矢径 h = h Si 的正向与车辆在弧段 Si 上的前进方向一 v v v 致，横向单位矢径 v = v Si 与 h 垂直，构成右旋直交坐标如图 4.1 所示。需要注意的 是 , e v ( k ) 与 e h ( k ) 均为标量，它们的大小与符号说明如下。 5) 弧段横向修正量 ev (k ) 表示 g ( k ) 的道路弧段横向偏差， e v (k ) 的幅值 | ev (k ) | 大小表示 g ( k ) 到达弧段的最短距离，即 v ev (k ) v = q(k ) ? p (k ) (6)v v e( k ) = ev (k )v + eh ( k )h式中 q (k ) = q( g k , S i ) 称为 g ( k ) 的弧段 S i 最近点，也就是 g ( k ) 对弧段 Si 作垂线 v v 与弧段 Si 的交点。 ev (k)[Si ] 的符号正负取决于是否与横向单位矢径 v = v Si 的方向一 致。正值表示 g ( k ) 偏差在按前进方向测算的道路弧段 S i 的右侧 ，反之，当车辆g ( k ) 位于道路弧段的左侧， e v (k ) 为负值。 q (k ) 由 g ( k ) 与相应弧段 Si 唯一确定，所以 ev (k )[ Si ] 是一个已知标量。23中国科学技术大学硕士毕业论文地图匹配问题以及现有算法介绍6) 弧段纵向修正量 eh ( k ) 表示 g ( k ) 的道路弧段纵向偏差，反映 g ( k ) 的地图道 路匹配点 p (k ) 沿道路弧段方向上的预测偏差 ，即v e h (k )h = p (k ) ? q (k )(7)eh (k) 的取正值表示匹配点 p (k ) 位于 g ( k ) 的前方，反之，当车辆 g ( k ) 必须向后退方向匹配时 e h (k ) 为负值。 弧段纵向修正量 eh ( k )[ Si ] 与匹配点 p (k ) 直接相关，是地图道路匹配算法最重 要又最难精确求解的预测变量。如何克服这一误差分量的影响是论文研究的一个重 点。 地图匹配过程实际上就是利用车辆行驶的 GPS 轨迹 g (k ) ，基于矢量地图的拓 扑结构，以及其它可获得的车辆运动信息来确定车辆正在运行的道路弧段 S i ，以 及在上面的准确对应方位 p (k ) 。 4.2 常 见地 图 匹 配 算法 正如本章开始的时候介绍，地图匹配算法经常被用来在车辆导航系统中确定 车辆在道路上的位置。大部分地图算法都假设车辆行驶过程中是在有限的道路网上 进行的，在绝大部分情况下车辆都是满足这种情况的。当然，当车辆实际上不在已 知道路上行驶时，地图匹配可能增加 GPS 定位误差。还有一个假设是大部分现有 算法的前提，就是矢量地图的高精确度。但是在实际应用中，用户并不能得到所有 需要区域的高精确地图[1]。文献 [1]对于现有地图匹配算法作了很好的总结，并且在文献中介 绍了四种地 图匹配算法类型： 1）半确定性算法； 2）概率统计算法； 3）基于模糊逻辑的算 法； 4）模式识别算法。 半确定算法需要的一个基本前提是需要知道车辆的初始位置和车辆运行方 向，然后多种条件判断会用来判定车辆是否在已知道路网上。这种地图匹配算法一 般用于带有航位推测定位系统的车辆导航系统。概率统计算法是在从车辆导航系统 获得的轨迹位置周围建立矩形或者长方形的置信区域。模糊逻辑的算法是基于一系 列的规则及其权重的设计来实现的。是一种基于已有知识的规则系统。由于地图匹 配算法本质上是模式识别的过程，所以模式识别领域中的多种算法都可以应用于地 图匹配问题的解决 ，比较典型的是人工神经网络 。 地图匹配过程可以用多种算法实现，从简单的搜索技术 [13]，到复杂的数学工 具 [14]，如卡尔曼滤波。在后面地图匹配算法的详细回顾中，我们主要将其分为三24中国科学技术大学硕士毕业论文地图匹配问题以及现有算法介绍类：几何方法 ，概率统计算法和其他高级算法。 4.2.1 几 何 匹 配 算 法 几何匹配算法利用地图道路网的几何信息进行匹配，它只考虑路段的形状距 离等，而不考虑道路的连接关系。最常见的几何地图匹配算法，是一种简单的搜索 过程。每一个车辆 GPS 轨迹点被匹配到最近的地图道路网节点处或最近路段上的 最近点。这种算法在车辆导航系统中的实现非常简单，但是直接用其匹配原始车辆 轨迹经常会出现误识别，尤其是在道路密集的城市地区和交叉路口处。所以这种算 法在实际车辆导航系统中直接使用的很少。 一些高级匹配算法在对车辆轨迹进行处理后，用这种方法完成最后的步骤， 将经过处理或者识别的匹配点映射到对应道路上进行显示。文献［８］　对这种最简单 的匹配算法进行一下改进，利用 ＧＰＳ 信息中的速度方向信息或者车辆运行连续性参 考前面时刻轨迹点匹配的道路辅助选择当前轨迹匹配的道路，选择好匹配的道路后 将轨迹点投影到该道路曲线上完成匹配。当车行驶在道路上时，存在三个状态信 息，速度、方向和当前所在街道。不难理解三个事实：　当车辆远离交叉路口时，它 不可能从一条街“跳”到另一条街；连续两次从 ＧＰＳ 信号得到的方向绝对差总小于 某个小量，除非它在交叉路口转向；当车辆行驶在道路上时，偶尔较大偏离道路的 信号应该忽略 。概括来说，就是利用车辆轨迹的连续性和矢量电子地图的拓扑结 构，将车辆轨迹和道路网格进行匹配，从而过滤 ＧＰＳ 信号的定位误差，更形象一 些，可以说是根据 ＧＰＳ 信号将车辆“拉”到道路上来。因此，修正算法应该涉及车 辆当前和以前的方向及街道的拓扑索引。　这种改进后的匹配算法能够有效减少匹 配的误识别率 。　　 　文献［１５］中的方法考虑多个轨迹点的地图匹配算法是根据一段时间内 ，连续 多个轨迹点拟和为曲线与道路曲线进行比较匹配，确定车辆运行道路以及车辆在道 路上的位置。文献 [16] 中， White 对几种几何地图匹配算法进行了详细的介绍和比 较，包括点到点匹配、点到弧匹配、弧到弧匹配以及利用地图拓扑结构的地图匹 配。通过对各种算法的匹配效果进行比较，说明了利用更多点的信息可以提高识别 的准确率，而且匹配过程中利用地图拓扑结构可以有效提高地图匹配算法效果。文 献 [17] 提出了基于权重的几何地图匹配算法，首先比较车辆方向 (从 GPS 接收机获 得 ) 与周围道路方向的偏差，比较当前轨迹点与周围道路弧的距离偏差，然后对两 个偏差设定不同的权重，获得针对不同道路的权重和，最后比较这些权重和，最小25中国科学技术大学硕士毕业论文地图匹配问题以及现有算法介绍的就是匹配可能性最大的。这种算法利用了车辆的方向信息来辅助地图匹配。这些 改进后的几何地图匹配算法在确定了轨迹匹配后的道路后 ，用最短距离匹配方式， 将车辆轨迹映射到该道路上距离轨迹最近的点上 。 4.2.2 概 率 统 计 算 法 概率统计算法是在从车辆导航系统获得的轨迹位置周围建立矩形或者长方形 的置信区域。这种算法最早是 1989 年由 Honey et al 设计的[18]。文献 [1] 中介绍了其在 GPS 车辆导航系统中的应用， 置信区域的大小可以由 GPS 位置的各种误差大 小来确定。之后，置信区域被重叠到交通矢量地图上，来确定匹配道路。当置信区 域中包含多条路段时，利用车辆的速度方向信息、与前面匹配道路的关联信息以及 最近距离原则来确定唯一的匹配路段。当在一定可信度区域内没有道路时，视车辆 不在道路上。文献 [1] 中没有介绍对这种算法的具体实现 ，在具体设计时，车辆的 速度信息和距离下一个交叉路口的距离信息都可以被应用到概率统计算法中。算法 的主要目标也是如何正确识别当前车辆运行所在的道路。确定匹配道路后，用最短 距离匹配方式将车辆轨迹映射到该道路上距离轨迹最近的点上 。 4.2.3 其 他 高 级 算 法 除了上面两种常用的地图匹配处理思路以外，卡尔曼滤波、模糊理论和人工 神经网络等理论也被应用于车辆导航系统的地图匹配问题的解决中。卡尔曼滤波器 是一种高效率的递归滤波器（自回归滤波器） [19]，用于估计离散时间过程的状态 变量。卡尔曼滤波器最初就是用来设计空间导航系统的 [1] ，当前被广泛应用于各种 系统。在车辆导航系统中，也是目前使用的重要信号滤波手段和多传感器融合方 法。在独立 GPS 车载导航系统的地图匹配算法中，融合交通矢量地图上的道路网 信息，是这类算法与单纯的 GPS 接收器信号处理最大不同之处。例如论文 [20]中， 将地图上路段的几何数学表达式作为卡尔曼滤波的一个约束条件该地图匹配算法能 够部分校正沿道路方向的误差。论文 [21] 中介绍的算法虽然在状态空间中包含了互 相垂直的两个方向上的状态进行车辆位置预测估计。另外的地图匹配算法运用模糊 理论 ［９］，人工神经网络等领域的知识实现匹配过程［２２］。这些算法在固定场合下有很 高的匹配准确率，但是需要大量的数据进行算法参数的前期学习和总结 。 4.3 对 现 有 算 法 分 析 以上介绍的这些算法研究重点都在如何确定匹配道路上 ，而并没有设计有效26中国科学技术大学硕士毕业论文地图匹配问题以及现有算法介绍的方法在匹配道路上寻找匹配点，都是简单的采用垂直映射的方法，用轨迹点到匹 配道路的垂足作为匹配点。这样的处理方法对于弧段纵向偏差无能为力。同时也没 有明确的对地图误差给地图匹配带来的问题进行解决。而这些误差关系到定位与导 航准确性的重要因素，尤其是交叉点附近 。 对于导航过程中获得的各种信息利用的越充分越能提高地图匹配的准确性。 这些方法中考虑的车辆方向、速度、位置、历史轨迹和地图的拓扑结构信息，是新 算法中需要借鉴利用的。现有地图匹配算法的另外一个问题是对地图道路网误差的 忽视。虽然当前的交通矢量地图的准确性有了很大提高，但是某些区域的地图的位 置准确性不是很高，而且在相对准确的交通地图中的某些局部可能有较大误差，这 些都会对地图匹配算法的准确性产生影响。实际上地图匹配算法的概念就是将车辆 轨迹匹配到地图道路上，而不是简单的车辆轨迹误差校正 。这就意味着地图匹配算 法本身就应该包含匹配过程中对地图误差的克服与处理。 　 卡尔曼滤波器由于其对于包含随机噪声的信号有很好的滤波性能，所以是处 理车辆轨迹误差的一个很好工具，但是其模型对噪声的概率分布有比较高的要求， 要求其为 ０ 均值的白噪声。而根据论文第二章中的 ＧＰＳ 误差的均值曲线和自相关函 数曲线可以看出其并不符合卡尔曼滤波器的模型要求。当前大部分应用于独立 ＧＰＳ 导航系统的卡尔曼滤波器算法并没有很好的处理这个问题，直接将 GPS 信息中的 位置、速度、加速度作为状态空间量 [11]。在这种情况下，卡尔曼滤波器对车辆轨 迹位置等的预测估计并不是最优的。　 虽然现有算法中存在着一些不足，但 这些方法中对车辆方向 、速度、位置、 历史轨迹和地图的拓扑结构信息的考虑，是新算法设计中需要借鉴利用的。针对现 有算法的这些弊端和优点，利用 GPS 短期误差变化和地图局部误差变化的特点， 提出了带预测偏差实时校正的地图匹配新算法，新算法的特点在于充分利用交叉路 口前后的 GPS 轨迹成功实现预测偏差的实时更新。27中国科学技术大学硕士毕业论文虚拟差分地图匹配算法第五章 虚拟差分地图匹配算法基于对车辆运行过程中从车载 GPS 设备获得的车辆实时位置 、运行方向、运 行速度和历史轨迹数据以及交通矢量地图的拓扑结构的综合考虑，利用 GPS 信号 误差的慢漂移特性和矢量地图误差变化的连续性，我们设计了包含交叉路口实时更 新并且以虚拟偏差实时校正为特征的地图匹配新算法。这里的预测偏差起的作用就 如同差分 GPS 中基站提供的差分信号一样对 GPS 轨迹进行校正，所以把这种算法 叫做虚拟差分修正量校正算法。算法主要包括正常弧段上的预测偏差实时校正与交 叉路口处 预测偏差的实时更新两部分规则。5.1 算法模型弧段中(离交叉路口有一定距离)的地图道路匹配过程，就是基于已知的信息及 当前 GPS 位置 g ( k ) 求得地图 匹配修正量 e( k ) ，参见图 5.1。S k1 S k2 ni S k3g ( k ? 1) g(k )e(k ?1) ev(k ?1 )p(k ? 1)e(k ?1)ev (k )ε (k)p ? (k )e(k )Sk 6njS i p( k ) q ( k)Sk 5图 5.1 弧段上的地图道路匹配过程示意图设当前为时刻 k , 历史数据包括 车辆 GPS 轨迹点 g( k ? 1) 、地图道路匹配点p(k ? 1) 、匹配修正量 e(k ?1) 都是已知的 。当前数据包括 GPS 轨迹点 g ( k ) 以及 g ( k )的道路弧段横向偏差 eh ( k ) 也是已知或可以立即计算出的确定量。根据论文第三章? 中关于 GPS 主要误差相对稳定的结论，引入预测校正点 p (k ) 定义为? p ( k ) = g (k ) + e( k ? 1)(5.1)在没有更多信息的时候，取预测校正点 p ? ? ( k ) 的弧段 S i 最近点 q ( k) 作为 k 时刻的 车辆位置 g ( k ) 的地图道路匹配点 p (k) 是很自然合理的选择。所产生的预测补偿记 为ε (k ) = q ? (k ) ? p ? ( k ) ≈ ev ( k ) ? ev ( k ? 1)(5.2)28中国科学技术大学硕士毕业论文虚拟差分地图匹配算法ε (k ) 补偿 GPS 误差的慢漂移和地图道路误差的微变，严格来说 ε (k ) 主要校正的是 GPS 误差漂移和道路误差变化在垂直于道路方向的分量 ev (k) ，进而可以保证 其对于后续轨迹的垂直道路方向上的修正量 e v (k ) 的准确性。匹配修正量 e( k ) 的实 时校正公式如下：e( k ) = e(k ? 1) + ε ( k ) = p( k ) ? g (k )(5.3)匹配修正量 e( k ) 的实时校正 。考虑到车辆运行过程中有一些偶然误差 (多路径 原因或者信号干扰) 对 GPS 轨迹产生脉冲扰动，单独用公式 (5.3) 可能会使道路匹 配的预测偏差修正量 e( k ) 产生比较大的扰动。为了平滑这种扰动，我们采用前 3 个 GPS 轨迹点和匹配点距离的平均值来修正 e( k ) ：e( k ) = ∑m=0 [ p( k ? m) ? g ( k ? m)] / 3m =2(5.4)5.2 初 始 阶 段 匹 配 道 路 的 选 取 与 利 用 e( k ) 的 车 辆 轨 迹 实 时 匹 配 导航系统刚开始工作时，道路匹配的匹配修正量 e( k ) 还没有被赋以有效值。 初始阶段的主要目标是确定车辆实际运行的道路弧段 Si 。由于在后续轨迹点的匹 配过程中会用到历史轨迹匹配结果，所以如果初始阶段的匹配道路弧段 Si 判定错 误会严重影响后续轨迹的匹配准确性。在这一阶段，我们综合考虑轨迹到匹配弧段S i 的距离最短和 GPS 测定的车辆速度与弧段 Si 延伸的方向一致性 (方向夹角在 30o内定义为方向一致 )，特别是后一条件来判定车辆当前行驶的弧段 S i 。由于单个初 始轨迹点用这种方式也可能出现误判，特别是接近交叉路口处，实际的计算中采用 连续匹配在同一条弧段 S i 上的轨迹点数大于或等于某个阈值，则确认该弧段是当 前轨迹的匹配弧段。匹配弧段阈值记为 C eff ，测试程序取 C eff = 6 。这里的连续匹 配以车辆速度与某些弧段例如 Si ， S j 延伸的方向一致性为标准，满足这一条件后 选择弧段横向修正量 ev (k )[ Si ] 最小的那条弧段 S i 。 在车辆行驶过程中，我们获得了虚拟差分向量 ediff 后，可以对车辆实时 ＧＰＳ 轨 迹点进行地图匹配 。首先我们利用 ediff 对当前轨迹点 g ( k ) 进行校正 。根据公式? ? （５．１）用 ediff 作为差分量对 g ( k ) 校正获得点 p (k ) 。这时的点 p ( k ) 已经被消除了沿道路方向和垂直于道路方向的主要误差。因为 ＧＰＳ 误差漂移的存在以及可能的地图? 道路误差变化， p (k ) 并不一定落在地图道路上 ，这时我们利用从车载 ＧＰＳ 获得的? 车辆速度、方向信息以及地图拓扑结构信息和历史匹配数据来将 p (k ) 匹配到对应道路的对应位置上 。　29中国科学技术大学硕士毕业论文虚拟差分地图匹配算法由于车辆位置在远离交叉路口处的匹配道路选择简单，而在交叉路口附近由 于道路情况的复杂非常容易误判，从算法效率和匹配准确率两方面考虑，我们对于? 在远离交叉路口处和交叉路口附近的校正轨迹点 p (k ) 采取不同的匹配方法。首先我们确定前一时刻选择的匹配道路弧 S i 的两个端点 n j ( x j , y j ) 和 ni ( xi , yi ) 。计算预? (k )( x pk , y pk ) 分别到 n j ( x j , y j ) 和 ni ( xi , yi ) 的距离 d ik 和 d jk 。　 校正后的轨迹点位置 pd ik ＝ ( x pk ? xi ) 2 + ( y pk ? yi ) 2 　d jk ＝ ( x pk ? x j ) 2 + ( y pk ? y j ) 2 　? 设置 p (k ) 临近交叉口的判断阈值为 d effect ， d effect 越大，误识别率越低，实时性越差（我们在测试程序中取值为 ５０ｍ）。如果 d ik ＞＝ d jk ，并且 d jk ＜ d effect ，则判断? ? p (k ) 临近节点 n j 。如果 d jk ＞＝ d ik ，并且 d ik ＜ d effect ，则判断 p (k ) 临近节点 ni 。　? 当p (k ) 与两个端点都不临近时，说明车辆在远离交叉口的道路上行驶，这时 ? ? 根据车辆行驶道路的连续性 ，判断 p (k ) 的匹配路段为 Si ，将 p (k ) 垂直映射到 Si 上获得匹配点 p (k ) 。　? 　当p (k ) 临近节点 ni 时，说明此时车辆位置在交叉口附近，我们就要根据导航系统的各种输入信息以及地图信息来准确判断车辆所处的道路，保证匹配路段的 选择是最重要的，因为会关系到后续路段上的路段匹配的准确性。我们用来判断匹? 配路段主要根据车辆的方向信息 h( k ) ，经过预校正的 ＧＰＳ 轨迹位置 p (k ) 以及地图的拓扑关联。但是由于当车辆速度 v( k ) 低于一定程度 veffect 时（经过实验证明是 １０．８ｋｍ／ｈ 也就是 ３ｍ／ｓ），车辆方向误差比较大，可信度低，所以我们在利用车辆 的方向信息 h ( k ) 时要先判断车辆速度 v( k ) 是否大于有效阈值 veffect （测试程序中取 值为 １１ｋｍ）。具体过程描述如下 ：　 ? 如果 v( k ) ＞ veffect ，计算 p (k ) 到与 ni 相连接的各条弧的距离，确定距离最小弧Sl （ｌ 可以等于 ｉ），如果此时 h( k ) 方向与 Sl 方向（ ni 为方向起始点）的夹角 β k 小 ? 于预先设定的阈值 β effect （测试程序中我们设定为 ３０ 度），则判断 p (k ) 的匹配路段是 Sl ，将 p ? (k ) 垂直映射到 Sl 上，获得 p (k ) 。如果此时 β k 大于或者等于 β effect ，就说明? 用最短距离和方向判定法选取的匹配路段不一致，则此时 p (k ) 的匹配点 p (k ) 位于 节 点 ni （ 临 近 节 点 ， 也 就 是 将 车 辆 位 置 显 示 在 道 路 交 叉 口 处 ） 。 如 果 ? v( k ) ＜＝ veffect ，说明此时的方向信息 h ( k ) 无效，将 p (k ) 的匹配点 p (k ) 位置确定在上一时刻匹配位置 p (k ? 1) 上。　30中国科学技术大学硕士毕业论文虚拟差分地图匹配算法5.3 转弯过程后的地图匹配修正量的自动更新地图匹配修正量定时更新指的是在一定条件下避免使用实时校正公式 (8-10)而 获得新弧段 S j 上全新的准确的 e( k )[ S j ] 。当车辆经过交叉路口时，车辆在地图上的 准确匹配点是一个确定的交叉路口位置 n j 。在这种情况下，有可能实现匹配修正 量从上一弧段 e( k )[ Si ] 到当前弧段 e( k )[ S j ] 的一次更新。 为了提高 e( k ) 更新的准确性与可靠性，我们只对符合一定条件的转弯进行利 用。先设定几个变量，设定车辆轨迹匹配到当前路段上的轨迹点个数为 Ccurrent ，车 辆轨迹匹配到前一路段上的轨迹点个数为 Clast 。当轨迹点匹配到一个新的路段上 时， Clast ＝ Ccurrent 　并对 Ccurrent 置 ０，即 Ccurrent ＝０。之后每获得一个匹配在当前路段上 的轨迹点并且匹配点不在道路端点上（避免交叉路口处长时间等待带来的误差）， 对 Ccurrent 加 １。用符号α 来表示当前路段与上一路段的夹角（锐角）。我们设定Ceff 表示一个预先设定的匹配在某路段上点的个数的阈值， Ceff 越大，获得的ediff 稳定性越高，但是实时性越差（在我们的测试程序中设置为 ６）。用 α eff 表示一个预 先设定的当前路段与运行的上一路段夹角的阈值，同 C eff 一样， α eff 越大，获得的ediff 稳定性越高 ，但是实时性越差（在我们的测试程序中设置为 ３０ 度）。　　 为了减少短时间连续转弯的不稳定性和计算误差，我们选取用来计算获得虚 拟差分向量的转弯有以下条件： 　 　 １） Ccurrent＝ C eff 　并且　 Clast ＞＝ C eff 　（５．５）　 　 ２） α ＞ α eff 　（５．６）　 　 当条件 １）２）得到满足时， 由于弧段纵向修正量ev (k )[ S j ] 总是已知 ( 方程 5)，所以匹配修正量 e( k )[ S j ] 的初始更新转化成为弧段纵向修正量 eh ( k )[ S j ] 的初始更新。图 5 给出 了直观的求解过程示意图，分析如下。如果在道路转弯前和转弯后各选取一个点 g ( k1 ) 和 g (k 2 ) ，根据 GPS 误差的 慢漂移特性，如果地图准确，应该有e( k 2 )[ S j ] ≈ e( k1 )[ S i ](5.7)事实上在转弯处，也就是前一弧段 Si 上的终端同时又是当前道路弧段 S j 上的 始段处 (图 5.2 中对应标注 C current = 0 的大节点 n j )的 g ( k ) 有严格的e (k )[ S i ] = e (k )[ S j ](5.8)参考图 5.2 左上部的两个几何分析示意图易知，将矢量 e(k1 ) 在 ev (k 2 ) 与 eh ( k 2 ) 方向上作正交分解 ，可得各分量值为ev (k1 ) = ev (k 2 ) cosα + eh (k 2 ) sin α(5.9)31中国科学技术大学硕士毕业论文虚拟差分地图匹配算法eh (k1) = eh ( k2 ) cosα ? ev ( k2 ) sin α ev (k 2 ) = ev (k1 ) cosα ? eh (k1 ) sin α eh (k 2 ) = eh (k1 ) cosα + ev (k1 ) sin α的道路弧段上的纵向偏差分量 eh ( k 2 ) 的幅值为(5.10) (5.11) (5.12)　同样的将矢量 e(k2 ) 在 ev (k1 ) 与 eh ( k1 ) 方向上作 正交分解 ，可得各分量值为将方程(5.11)与 (5.12)两边分别同乘以 cosα 与 sinα 再相加 ，整理得出 e(k2 ) 在新eh (k 2 ) = [ev (k1 ) ? ev (k 2 ) cosα] sin α(5.13)　注 意 到 ev (k1 )[ S i ] 与 ev (k 2 )[ S j ] 均 是 已 知 确 定 性 变 量， 选 用 公 式 (5.13) 计 算eh ( k )[ S j ] 可以完全消除上一弧段上纵向积累偏差 eh ( k1 )[ S i ] 的影响，获得准确的纵向偏差更新 e h (k 2 )[ S j ] 。图 5.2 更新偏差修正量 e( k ) 的过程示意图　上述推导过程，假设地图较为准确，其时实际上的 eh ( k1 )[ S i ] 也较为准确，所 以利于图 5 的分析。必须指出，当地图不够准确，不能保证 e( k 2 )[ S j ] ≈ e(k1 )[ S i ] 。 原因是 eh ( k1 )[ S i ] 误差积累较大，会出现如图 5.2 所示的车辆运行及匹配过程。同样 的推导过程表明，弧段纵向修正量的更新值 e h (k 2 )[ S j ] 的计算公式仍然如 (5.13)所 示。 如图 5.3 所示，对应标注 C current = 0 的时刻，弧段纵向修正量已经从eh ( k )[ Si ] 自 动 更 新 为 eh ( k )[ S j ] ， 相 应 地 ， 地 图 匹 配 修 正 量 也 从 e( k )[ Si ] 自 动 更 新 为e (k )[ S j ] 。事实上前一弧段 Si 上的地图匹配修正量 e( k1 )[ S i ] 预侧的道路转弯路口为 ? ，由于矢量地图的误差，矢量道路转弯路口为节点 n 。可见 e (k )[ S ] 实际 节点 njjhi?。地图匹配修正量自动更新正好完全补偿了 上已经积累的误差 eerror ( k )[ Si ] = n j ? n i这一误差 ，即：32中国科学技术大学硕士毕业论文虚拟差分地图匹配算法e( k )[ S j ] = e (k )[ Si ] + eerror ( k )[ S i ]配。(5.14)方程 (5.14)说明匹配修正量自动更新同时获得了交叉路口道路弧段的零误差匹图 5.3 地图误差较大时的匹配修正量 e( k ) 更新示意图地图匹配修正量的自动平滑更新 ：在实际应用中，单次选取 g (k1 ) 和 g ( k 2 ) 计 算使用式 (20) 可能受到随机干扰影响计算结果，所以采用多点匹配方法平滑更新数 值计算。 在前一弧段的最后 C eff 个轨迹点的弧段横向修正量的平均值 d 1 来代替ev (k1 ) ，用当前弧段前 Ceff 个轨迹点到当前弧段的弧段横向修正量的平均值 d 2 来代替 | ev (k 2 ) | ，即d1 = ∑meff ev ( k1 ? m) Ceff =0C ?1C eff ?1(5.15) (5.16) (5.17)d 2 = ∑m =0 e v (k 2 ? m) C eff由方程（５．１５）获得 e( k 2 )eh (k2 ) = d1 ? d 2 cosα ] sinα `异常轨迹点的排除问题： 在车载 GPS 接收仪确定车辆轨迹的时候，某些误差 因素的漂移是可以接受的，但是某些时刻， G}