关 键 词：

机械毕业设计

资源描述：

tx087车载GPS导航系统中地图匹配算法的研究,机械毕业设计

内容简介：

江苏大学毕业论文 论文题目 ： 车载 GPS 导航系统中地图匹配算法的研究 学 院 ： _计算机科学与通信工程学院 班 级 ： _计 算 机 002 班 姓 名 ： 黄 薇 指导教师 ： _陈 天 滋 二 00四年六月 nts江 苏 大 学 毕 业 论 文 摘 要 本文简单介绍了车辆导航系统 （ VNS） 的开 发目的和意义，对国内外 VNS的发展情况作了简要的回顾，并讨论了车辆导航系统各个模块的功能及其所利用的技术手段；着重讨论了车载 GPS 导航系统中的地图匹配技术。通过对现有地图匹配算法的分析比较，提出了改进的地图匹配算法，并分析了该算法的原理、过程及实现方式；最后，根据系统的整体设计及实践，叙述了本系统尚待解决的问题及其开发前景。 关键词：车辆导航系统，地图匹配，算法 nts江 苏 大 学 毕 业 论 文 Abstract This paper recommends that the purpose and meaning of Vehicle Navigation System(VNS), simply reviewing the state of development in both here and abroad,and discuss the function and technologies used of each module in VNS.Especially, Map Matching in VNS is discussed. With analyzing and comparing Map Matching Arithmetic in existence, the improved Map Matching Arithmetic is put forward, and its theory, process and implement manner is analyzed. Finally, based on the whole design and practice of this system, this text introduces the problems which have not been solved yet and its exploiting foreground. Key words: VNS, Map Matching,Arithmetic nts江 苏 大 学 毕 业 论 文 目 录 第一章 绪论 - 1.1 引言 - 1.2 车载 GPS导航系统研究目的及意义 - 1.3 国内外 VNS发展概况 - 1.4 研究内容 - 1.5 论文结构 - 第二章 车载 GPS 导航系统分析 - 2.1 车辆导航系统总体结构模型 - 2.2 车载导航系统结构分析 - 2.2.1 系统结构 - 2.2.2 功能模块 - 2.3 系统技术要求 - 第三章 地图匹配及其算法分析 - 3.1 地图匹配算法简介 - 3.1.1 引言 - 3.1.2 定义 - 3.2 现有的地图匹配算法 - 3.3 现有算法的局限性 - 第四章 车载导航系统地图匹配算法的设计思路 - 4.1 算法原理 - 4.2 算法数据分析 - 4.2.1 输入数 据定义 - 4.2.2 错误数据分析 - 4.3 地图匹配算法过程 - 4.3.1 选择合适路段 - 4.3.2 确定车辆在选定路段上物理位置 - 4.3.3 检查车辆是否仍然在当前路段 - 4.4 算法描述 - 4.4.1 步骤 - 4.4.2 流程图 - 第五章 结论与展望 - 5.1 结论 - 5.2 发展前景 - 致 谢 - 参 考 文 献 - nts江 苏 大 学 毕 业 论 文 第一章 绪论 1.1 引言 在人类的文明史上，车辆导航系统（ VNS）的研究和发展已有相当长的历史，最早可以追溯到公元前 2600 年以前的指北车和航海家通过观测星空来引导船舶。随着科技的发展， VNS技术也在缓慢的发展之中。到了二十世纪，随着科学技术的高度发展，将先进的信息处理技术、数据通信技术、电子控制技术及计算机处理技术等集于一体的智能交通系统的研究是 21世纪现代运输管理体系的模式和发展方向。卫星定位技术（ GPS）、地理信息系统（ GIS）、遥感技术（ RS）、数据库技术、间 接税网络技术、数字蜂窝移动通信技术（ GSM）、寻呼技术等高科技技术的出现，为我们新型城市交通管理系统提供了有力的技术解决手段。而计算机软件技术 WINDOWS NT、 VB、 VC、 ARC/INFO、 SQL SEVER等的进一步发展与完善，也为这些技术的集成提供了有效的联结手段 1。 技术的提高、应用的扩展使计算机、手机、寻呼机、 GPS接收机等硬件设施的性能提高而价格下降，与其相应的软件服务费用也在下降，达到了用户可接受的水平。这为我们使用、推广智能交通系统提供了可能，从而加速了城市智能交通管理系统战略的实施。 陆地车辆导航系统是智能交通系统的一个组成部分。它使车辆有“头脑”，能在道路上自由行驶，使道路“聪明”起来，达到最佳的状态，两者结合能使司机对周围环境了如指掌，使管理人员对交通状况和所有车辆的行踪一清二楚，人、车、路密切配合，达到和谐的统一。 1.2 车载 GPS导航系统研究目的及意义 从历史的角度上说，人类从来没有停止过寻求最大机动性的途径。当今交通已成为现代文明社会不可缺少的重要组成部分，汽车作为人类活动的工具在日常生活中的作用越来越明显。而人口的增长和交通工具的快速发展，使城市道路交通问题成为困扰各国的难题。如何改善城市交通运输，解决新一轮即将来临的由于车辆降价所带来私有车辆拥有量的骤增给交通带来新的压力，是我们有待解决的问题。另外，为迎合社会发展的需要， 110、 120、 122 等服务应运而生，跨城市的商贸交往及旅游的增多，也必须加强对这些特殊车辆及其用户的服务。如何面对有限的资源，科学决策交通建设，用最小的投资获得最大的效益，高效管理交通运输，解决与日俱增的公路交通系统的复杂性和拥挤度问题，是现代交通系统所面临的课题。 ITS 就是针对这些问题而提出来的。 因此，智能交通系统（ ITS）的研制具有很大的社会意 义和经济效益，其作用主要表现在以下几个方面： 1、 提高交通设施的利用率，减少阻塞，增加交通的机动性。在拥挤的大中城市，nts江 苏 大 学 毕 业 论 文 专家认为通过使用 ITS可以使道路的利用率提高 30%以上；据德国交通部门统计，在全德国，每年汽车司机因行错路而造成的经济损失就达几十亿美元。 2、 降低交通工具对环境的影响，保护环境。 3、 改善道路安全。据专家估计，采用 ITS后，在今后的 20年内可以降低 8%的交通灾难，每年交通事故的死亡人数可以减少 30%-70%。 4、 有利于打击和预防犯罪，提高需对突发事件反应的部门的能力，如公安、消防、急救病人等。 5、 促进相关 产业的发展。根据美国 GPS工业协会的统计， 2000年安装有 GPS的车用导航装置的市场销售额已达到 30亿美元，到 2005年，预计总销售量可达 2250万 2。 1.3 国内外 VNS发展概况 汽车导航系统由 GPS 导航、自律导航、微处理器、车速传感器、陀螺传感器、 CDROM驱动器、 LCD显示器组成。 车辆导航系统的概念最初起始于二十世纪六十年代末，美国公路局提出了一种电子路径引导系统。这是一种具有无线电路径引导能力的导航系统，用于控制和疏导交通。但由于资金问题而没有实现。 70年代初期，美国开发出了一种自主导航 系统，这种系统利用推算定位模块，借助于地图匹配算法进行车辆定位。一旦确定车辆沿着路径行驶的位置，该系统第二版本能够把路径引导指令显示在车内的等离子显示器上。终于在 80年代中期相继把先进的导航产品投入市场。它每年用于车辆导航系统的试验和部署经费为几亿美元。如：历时 6 年、花费几千万美元的测试动态路径导航的 ADVANCE 实验运行系统。到了 80年代，又有欧洲的“ CITY PILOT”车载航位推算系统，美国的 Etack Navigator，荷兰 Philips公司的“ CARIN”车辆定位系统。德国的“ ALI-SCOUT”车辆路线制定系统，英国的“ Auto Guide”车辆定位系统等，这些系统被称为第一代车辆导航系统。 在过去的 10 年中，由于 GPS 定位技术的广泛应用，车辆定位与导航系统以及智能交通系统有关的系统在世界范围内取得了迅猛的发展。在任一时刻，安装有 GPS 的汽车可以得到其位置、运行速度和运行方向，但是 GPS 的精度常受到卫星信号状况和道路环境的影响，一天之内，不同时段和地区的信号差别很大，有时甚至不能接收到正常的 GPS信号；另外，当车辆行驶在隧道、高层建筑附近、林荫道上（即所谓的城市峡谷）时，也不能正常接收到卫星信号 ，从而可能无法定位。因此，有需要采用组合导航的技术。 目前，国外已经有几十家公司进行车辆导航系统的研制和理论的研究，其中主要集中在美国、欧洲和日本及我国的台湾地区，如日本的丰田、尼桑、松下等，欧洲的飞利浦、西门子等。由于有着雄厚的资金和技术实力，因此他们的技术已经领先于其他国家。另外，这些国家和地区已经建立了大区域性的道路交通信息系统及其管理中心，导航设备以及与其相配套的数字地图和交通数据产品已经成为比较成熟的商品。如美国已经在其国内大部分城市建立起了实时交通信息监测及发布系统，日本也于 80年代推出了各种导 航器，并在 96 年推出了用调频广播和车载手机与中心联系的导航系统，用于交通数据nts江 苏 大 学 毕 业 论 文 的采集和发布。目前，日本的导航地图生产已经成为一个产业，日本导航协会负责从 1：640万到 1： 5000 的导航用电子地图的生产和更新。 相比较国外，国内的车辆导航起步和发展都比较晚，开始于 80 年代末期，其应用主要是集中在车辆的监控调度系统方面。目前具有一定开发能力的公司如大通公司、京惠达公司、图原公司等，也主要是进行这方面的工作。其主要的特征是代理国外的产品或基于单板机或笔记本以及 PC机的操作系统（主要是 Windows）和开发平台进行开 发，如图原公司的车辆监控系统运行的平台是 Windows98，开发平台是 Map-Engine，因此成本较高，使用、携带不够方便。另一方面，由于这些系统并不是专门为 VNS 设计的，因此相对来说效率较低。目前虽然有很多单位在进行这方面的研究，但是并没有一款成熟的产品上市。但已有许多公司都制作出了科研样机，如四维公司、大通公司等。我国目前投放到市场的导航产品，基本上都用于特殊车辆，如： 110车辆、运钞车、邮政车辆等，而它们都只是由中心监控导航，只能定位不能自主导航。具有电子地图又能语音导航的车载导航产品在国内目前尚较 为罕见。由于 VNS 在交通、旅游以及许多特种行业中有着巨大的市场，因此， VNS的研制有着良好的开发和应用前景。 2000 年 5 月 1 日，美国政府取消 SA 政策，使单 GPS 接收机定位精度从 100 米提高到优于 20米 3。这项政策的出台，更加推动了 VNS的发展。 1.4 研究内容 本课题以镇江地图为研究背景构建了 GPS 车辆导航系统的结构，建立了镇江市城市交通导航系统的初步模型。 在参考国内外已有系统的基础上，结合我国具体情况，本论文主要针对以下几个问题进行了理论和实践上的探讨： 1、 分析了国内外车辆导航系统的发展历史、现 状和趋势，以及一般车辆导航系统的组成，讨论了汽车导航系统开发目的及意义，并对我们研制的汽车导航仪的开发环境进行了简要的介绍。 2、 分析了车载导航系统的整体系统结构，详细描述了该系统各个功能模块的作用与实现方式。 3、 建立了地图数据库，进行道路网络分析，自动生成个相关接点的相关数据库。 4、 研究了车载导航系统中的地图匹配技术。分析比较了目前流行的地图匹配算法的优缺点，提出了改进的地图匹配算法，并着重介绍了该地图匹配算法的原理，过程及实现方式。 1.5 论文结构 本论文分为五章，具体结构如下： 第一章：绪论。介绍了 车辆导航系统（ VNS）的现状及开发目的和意义，对国内外VNS的发展情况作了简要的回顾，并介绍了本课题的研究内容。 nts江 苏 大 学 毕 业 论 文 第二章：车载 GPS导航系统分析。阐述了车载 GPS车辆定位与导航系统的结构模型，主要讨论了车载导航系统各个模块的功能及实现方法，并提出了整个系统所依赖的技术要求。 第三章：地图匹配及其算法分析。介绍了地图匹配技术，阐述了地图匹配的定义分类等，通过比较现有的地图匹配算法，分析了他们的优点及局限性。 第四章：车载导航系统地图匹配算法的设计思路。提出了改进的地图匹配算法，并分析了该算法的原理、过程及实现 方式。 第五章：结论与展望。根据系统的整体设计及实践，叙述了本系统已经解决的问题及存在的不足，并展望了本系统的开发前景。 nts江 苏 大 学 毕 业 论 文 第二章 车载 GPS 导航系统分析 2.1 车辆导航系统总体结构模型 车辆导航系统是智能交通系统（ ITS）的核心部分，是实现道路管理智能化的关键之一，是多种技术集于一体的综合系统。 城市智能交通导航系统模型主要分三大部分：车载导航系统、中心管理系统、通信网络。车载导航系统主要是实现车辆的定位、导航及与中心的交互；中心管理系统用来管理、调度和监控；通信网络负责各种数据的传输。它的总体构 架如图 2-1所示。 图 2-1 车辆导航系统总体框架 本课题的研究重点是具有自主控制功能的车载导航系统。该系统可以独立运行，但留有与中心的接口。 2.2 车载导航系统结构分析 2.2.1 系统结构 在 VNS 技术飞速发展的今天，已经有很多从高档到低档系列产品面世。在这些系统中，低档的有可能只是很简单的系统，这种系统可借助于人的干预来测定车辆和任何移动装置的位置；而高档的有可能是一个很复杂的系统，这个系统可通过无线电通信网络提供实时通信信息来自动为车辆导航。 车辆 GPS 定位管理系统主要是由车载 GPS 自主定 位，结合无线通信系统对车辆进行调度管理和跟踪。它包含多个功能模块， 可以实现车辆跟踪和交通管理等许多功能 。 系统结构如图 2-2 所示。 nts江 苏 大 学 毕 业 论 文 图 2-2 车载导航系统构成图 2.2.2 功能模块 本系统可分为五个功能模块，具体描述如下： （ 1） 数字地图数据库模块 负责存储数字地图信息。 它主要包括支持电子地图显示的地图数据库及用于路径引导的道路特征数据库，包含预先定义好存储格式的数字地图信息，须把车辆位置、数字地图和相关地理信息结合起来。它是定位和导航功能的基础，可为用户提供主要物标，用户能够在电子地图上根据需要进行 查询，并可在电子地图显示其位置。 （ 2） 定位模块 系统通过采用全球卫星定位系统（ GPS）技术，实现车辆定位。 定位系统融合了不同的传感器的输出，利用接收到的无线电信号自动的确定车辆的位置，辨别正在行驶的公路和所要接近的每一个交叉路口。 GPS 导航是由 GPS 接收机接收 GPS 信号， 并对信息和信号进行处理，经过复杂的计算完成定位工作 。为提高汽车导航定位精度 和可靠性 ，通常 结合两种或者两种意识的技术，取长补短来确定车辆位置。 （ 3） 路径规划和路径引导模块 路径规划被广泛认为是车辆导航系统领域的一个基本问题。 它是帮助司机在行驶前或 运行中，根据地图数据库模块所提供的地图或实时交通信息，规划行驶路径。通常 由驾驶员确定起点和终点，由计算机软件按照要求自动设计最佳行驶路线， 综合考虑距离、行驶速度、行驶时间、拐弯和交通灯的数目和动态交通信息等。 路径引导是指挥司机沿着由路径规划模块计算出的路线行驶的过程。 该引导过程可以在旅行前或者在途中以实时的方式进行。为了确定车辆当前的位置和产生适当的实时引导指令，如路口转向、街道名称、行驶距离等，须借助地图数据库和准确的定位。引导过程可以采用多感官效果，如闪烁、语音引导等技术。 （ 4） 地图匹配模块 nts江 苏 大 学 毕 业 论 文 地图匹配是 把测量到的 GPS 定位数据或从定位模块获取到的位置（轨迹）与地图数据库所提供的基于地图的位置（主要是路径）进行匹配，来确定车辆在地图上的位置。它在车辆导航系统中也起着很重要的作用。 对于市区来说，数字地图数据库的误差范围应该保持在 15m2以内（真实地面距离）8。 如果地图数据库足够准确，这一技术能改进定位模块的精确度。另一方面，通过地图匹配技术也可以进行导航系统的辅助传感器的校准。 （ 5） 人机接口模块 人机接口允许用户与定位和导航仪及各种装置间进行人机交互。 地图显示、路径规划、路径引导和其他活动的各种不同要求通 过这个人机接口送到导航仪中，然后再通过这个接口模块反馈给用户。人机接口的种类很多，通常的有开关、按钮、可视显示、语音识别等，在实际应用中可以选择一个或多个组合来实现。 2.3 系统技术要求 1、 硬件平台：便携式电脑 2、 操作系统： Windows 2000 3、 GIS开发平台： SuperMap Objects 这是超图地理信息技术有限公司基于 Active X/COM技术开发的组件式 GIS软件开发平台，是由一系列的 Active X组件构成。 包括：核心组件、布局组件、三维组件、拓扑组件、图例组件、数据表格组件、工作空间管 理组件、加密锁信息组件、辅助组件等多个可分拆的组件库。其组件库之间既可相互关联，也保持相对独立性。 SuperMap Objects 提供了 11 个 Active X 控件， 120多个 Active X对象，共有属性、方法、事件等接口 1200多个。 其中，控件是图形窗口交互界面的特殊的 Active对象。 除此之外，它还提供了试用于不同规模应用系统的空间数据访问引擎，如：SDB,MDB,DWB,DGN 等。 4、 数据库： SQL Server 2000 SQL Server是一个功能完备的数据库管理系统。它包括支持开发的引擎、标 准的 SQL语言、扩展的特性 (如复制、 OLAP、分析 )等功能。 Microsoft SQL Server 2000 的特性包括： （ 1） Internet 集成 ： SQL Server 2000 数据库引擎提供完整的 XML 支持。 （ 2） 可伸缩性和可用性 ： 同一个数据库引擎可以在不同的平台上使用 ， 从运行 Microsoft Windows 98 的便携式电脑 ， 到运行 Microsoft Windows 2000 数据中心版的大型多处理器服务器。 （ 3） 企业级数据库功能 ： SQL Server 2000 关系数据库引擎充分保护数据完整 性，同时将管理上千个并发修改数据库的用户的开销减到最小。 （ 4） 易于安装、部署和使用： SQL Server 2000 中包括一系列管理和开发工具，这些工具可改进在多个站点上安装、部署、管理和使用 SQL Server 的过程。 nts江 苏 大 学 毕 业 论 文 （ 5） 数据仓库： SQL Server 2000 中包括析取和分析汇总数据以进行联机分析处理 (OLAP) 的工具。 SQL Server 中还包括一些工具，可用来直观地设计数据库并通过 English Query 来分析数据。 5、 编程语言： Delphi 7.0 Delphi是 Borland公司 于 1994年底发布的用于开发数据库应用程序的工具， 其 基础编程语言是具有面向对象特性的 Pascal语言，它是目前开发客户 /服务器数据库应用程序的强有力的工具 。主要特点有： 可视化的开发环境：编辑器、调试器、窗体设计器 ；高效率的编译器：编译速度、编译后代码的长度 ； 编程语言强大的功能和合理的复杂性 ；对数据库的强大支持（ ODBC、 BDE、 ADO、 DBExpress）； VCL对设计和使用模式的扩充 ；对 WebServices的支持 ； XML支持 和 多平台支持等等。 nts江 苏 大 学 毕 业 论 文 第三章 地图匹配及其算法分析 3.1 地图匹配算法 简介 3.1.1 引言 目前，车辆定位使用的方法主要包括：无线导航技术 (Radio Navigation,如： GPS、GLONASS、 Sign Post等 )、航位推算 技术（ Dead Reckoning DR ）、地 图匹配 技术 （ Map Matching MM） 等。 其中，无线导航技术依赖于外界设备，其定位精度或受无线网覆盖面积的限制（如：Sign Post）、或受定位信号精确度的影响（如： GPS），并且 在城市路段复杂的情况下，往往会出现高楼和高架桥阻挡接收机的信号，使 GPS 定位信息有较大的偏差甚至 失去信号，单纯用 GPS 定位很难得到满意的定位效果 ； 航位推算可以实现车辆的自主导航，但是它需要车辆初始位置的输入， 并且精确度受方向探测仪及车速脉冲设备精度的限制，且其存在积累误差，即随着车辆行驶距离的增加，误差越来越大。 地图匹配（ Map Matching，简称 MM）这一软件纠错技术恰恰避免了以上两种定位技术无法克服的局限性。 地图匹配是一种通过模式识别理论为依据，基于“车辆始终行驶在道路上”的假设，通过找到车辆所在的道路，计算出准确的车辆位置。 也就是说，当推算定位指示车辆在地图上的某一位置时，车辆位置可以 被调整到地图上的绝对位置，这样做会消除积累误差，直到下一次地图匹配步骤。在每一个连续的系统周期中完成这个过程，就能实时得到更加准确的车辆位置。 地图匹配算法将其他定位方法（如 GPS、航位推算法等）测得的车辆位置或行驶轨迹，与车载的电子地图道路数据比较、匹配，找到车辆所在的道路，计算出车辆在道路上的位置，进而还可以通过各种方法来校正其它定位方法的误差，如：航位推算法的积累误差、 GPS的随机误差等。 地图匹配方法与以上两种定位技术配合使用，能够极大地提高车辆定位精度，减小定位误差。可以说，地图匹配算法的效果直接 关系到车辆定位的精度，地图匹配技术是决定导航产品最终性能的关键技术之一。 基于定位方法上述的特点，目前广泛采用的定位机制多为无线导航（如 GPS） +航位推算法（如惯性导航系统）并配合以地图匹配算法的综合定位方法。 3.1.2 定义 地图匹配，顾名思义，指的是两者的匹配，指的是系统接收到的 GPS 点的位置信息和电子地图的匹配 。 nts江 苏 大 学 毕 业 论 文 地图匹配算法以模式识别理论为基础，以某个车辆位置点或某段车行轨迹曲线作为待匹配样本，以该点或该轨迹曲线附近的所有道路上的位置点或道路曲线作为模板，通过待匹配样本与模板间的匹配，选择相似度 最高的模板作为匹配结果。最后根据匹配结果，校正定位模块的定位误差。 一般而言，地图匹配算法在匹配中应具备以下过程： （ 1） 通过预处理、特征提取等步骤对待匹配样本和所有模板进行分析、描述 ,并提取出相应的位置或形状特征。 （ 2） 根据算法的匹配规则 ,依次计算待匹配样本和所有模板间的匹配相似度。 （ 3） 最后 ,选取相似度最高的位置点或道路曲线模板 ,作为待匹配样本车辆位置点或车行轨迹曲线的匹配、分类结果 4。 地图匹配方法是借助电子地图数据库存储的高精度道路数据来提高车载导航系统的定位精度。 地图匹配根据其匹配目的的不同，可将其分为道 路匹配和非道路匹配。道路匹配是将 GPS 定位信息匹配到地理信息系统中的道路上，而非道路匹配是建立在道路匹配的基础上，是指车辆进入加油站、停车场或者其他地方作短暂的旅行，偏离道路时候的匹配。为了使用道路匹配更加有效，我们在进行匹配之前首先提出两个前提： （ 1） 车辆总是行驶在道路上； （ 2） 采用的道路数据精度要高于车载导航系统的位置估计精度。 事实上，在正常的交通情况下，和飞机导航与海洋运输不同，公路运输车辆局限于有限的公路网络系统，仅仅是进入停车场、或其他的短暂旅行，如加油站，因而条件 （ 1）是 可以满足的。条件 （ 2） 可以通过 使用高精度的电子地图数据库来实现。 地图匹配精度取决于数字地图的精度。一般来说，地图需具有优于 15米的位置精度。同时，为了保证地图匹配算法的鲁棒性，地图的拓扑关系必须完整精确，以反映真实的道路。如果行驶的道路未被录入数字地图中，由于车辆的实际行驶道路不在地图匹配算法考虑之中，地图匹配算法将不可避免地陷入矛盾之中。 地图匹配方法实际上是一个伪定位系统，通常先识别道路交叉点，再通过地图坐标来确定车辆的位置。地图匹配算法使用的前提是假设车辆在道路上行驶。当定位系统给定的车辆位置并不正好在数字地图的道路上时，地图匹配 算法找到可能行驶的路线，并将车辆位置校正于道路上；在车辆的行驶过程中，方向和行驶距离确定轨迹的形状，此形状也用来与地图上的道路网络相匹配。 3.2 现有的地图匹配算法 地图匹配算法是由简单的搜寻技术变化发展而成为复杂的精确技术，最早由 Kalman Filters (Tanaka et al.1990)提出 5。 从原理上来说， 目前主要有四种办法在研究 路径地图 匹配问题 ： 1、 概率统计方法 70年代，两个美国研究小组和一个英国研究小组分别独立发明了早期的常规路径匹nts江 苏 大 学 毕 业 论 文 配算法 ， 这种半确定算法已发展为一种概率统计推理 方法。 在我国，有专家提出了对“实时地图匹配技术中缓冲区分析的研究” 6，这实际上 就是基于概率统计法的原理 ,在比较精确的数字地图上 ,利用不低于标准定位服务( )定位精度的数据的前提下，采取中常用的缓冲区分析算法实现了 地图匹配。 一个典型的基于缓冲区分析的地图匹配算法流程应该是 : (1) 基于误差模型 ,根据接收的定位数据建立缓冲区； (2) 在该区域内抽取路径； (3) 基于取向、连通性等判断是否得到最佳匹配 ,若为否定答案则返回 (1)； (4) 利用最佳匹配数据更新位置。 该算法在概率统计推理的方法上采取 了许多改进措施，实践证明该算法快速有效，但 实际上，由于道路环境复杂， 并且由于 多方面误差的存在，这些算法很难精确区分车辆一定行驶在那个街道上，即使后来人们提出了很多修正措施。 基于概率分布理论 (如最近点法估计 )的地图辅助定位方法的缺陷在于没有充分应用行驶轨迹前后的相关性。 确切地说，系统可能得出如下结论，车辆 “ 很可能 ” 在某一道路上， “ 不可能 ” 在其他某些道路上，而且都不是完全的。如果要求一个精确定位与导航系统，这种模糊性是需要解决的。 2、 基于模糊逻辑的路径匹配算法 后来人们提出了基于模糊逻辑的路径匹配算法 7。这 种算法进而提出了一些规则来约束道 路匹配的精确性。 显然 ,应用模糊数学方法处理这一问题是十分合适的。 为此首先引入以下三条模糊逻辑评判规则 : （ 1） 若候选路段的取向与车辆当前的行驶方向一致 ,则候选路段是车辆当前行驶路段的可能性大。 （ 2） 若候选路段接近当前的传感器定位位置 ,则候选路段是车辆当前行驶路段的可能性大。 （ 3） 若候选路段形状与最近一段时间的车辆运行轨迹相似程度高 ,则候选路段是车辆当前行驶路段的可能性大。 然后定义模糊隶属度函数，以其为基础 ,就可以对候选路段是当前车辆所在路段的可能性作出综合评价。评判中 ,应考虑到候选路段 与前一时刻匹配路段的连通性。 实践证明，道路狭窄、两边高楼林立的城区 ,主干线上由于卫星信号受到频繁的遮挡和反射 , GPS定位数据出现频繁跳变甚至丢失 (轨迹中有空白段 )。由于推算定位需要由GPS定位数据给出初始位置和方向角 ,因此 ,组合定位的数据精度仍然主要依赖 GPS系统 ,并没有获得明显改善。 但是我们也应该看到，经模糊地图匹配修正处理后的定位数据被匹配到了正确的行驶路段上 ,精度获得了显著改善。 这种以模糊逻辑为基础的算法具有许多优点，现正在迅速发展之中。 3、 地图识别和图形识别的方法 也有学者利用地图识别和图形识别 的方法来研究路径匹配 。 nts江 苏 大 学 毕 业 论 文 因为在地图上，不同的几何特征有不同的颜色标示，比如一般来讲，道路是白色的，研究目标是将 GPS定位到最近的白 色道路上。 目前比较成熟的图像匹配方法主要有两大类 :基于灰度的匹配方法和基于特征提取的匹配方法。 利用灰度进行匹配 ,算法简单、直观 ,但计算量较大 ,影响实时性 ,主要原因 : (1) 没有充分利用像素相关性以及图像内的结构关系； (2) 计算机系统结构的限制 ,即冯诺依曼机固有的串行操作将像素灰度按顺序进行处理 ,没有充分利用像素处理的并行性质； (3) 灰度对照明条件十分敏感 ,当照明条件发生变化或由于不同的成像 条件而造成局部灰度反转时 ,直接基于灰度的匹配方法就会失效。 基于特征提取的匹配方法 ,是通过对灰度差异、噪声、几何畸变不敏感的图像特征 :如轮廓特征、强边缘特征 ,或分形特征等进行匹配的。然而利用图像特征进行匹配存在图像的特征提取与特征有效性问题 ,基于现有方法的特征提取和准确定位往往是很困难的 ,这使得基于特征提取的匹配方法在复杂场景匹配中 ,难以取得令人满意的效果。 在我国也有学者提出了“基于图像物理特征的并行地图匹配算法设计与研究” 8。文章针对地图匹配应用，在提出图像的质量和重心概念的基础上，设计了一种适于 SIMD结构的基于图像物理特征的二次搜索地图匹配算法。首先，利用图像的物理特征进行粗相关匹配，确定一些可能的匹配点作为搜索空间；然后，在这个小的匹配区域内，按照象素进行图像的精相关匹配，大大减少了图像的匹配次数和单次匹配的计算量，提高了算法的并行质量。 但是，对于物理特征区别不明显的图像来说，也往往会出现漏配和错配的情况。因此，该算法需要继续改进，如增加更多的物理特征或同时利用图像形态特征匹配等方法，另外，设计图像及其特征的存储组织方式是减少并行算法访问存储器次数和单次存取时间的有效途径。 4、 模式识别方法 除了 以上 三 种算法之外，日本等国家提出了模式识别方法。路径匹配基本上可以说是一种模式识别，因而可以利用神经网络的有关理论。 目前，大多数地图匹配算法都运用了模式识别原理。 各种不同的运算法则被称为地图匹配，并运用于不同的应用软件。目前，从匹配样本的类别上看 ,地图匹配算法主要可以分为 :位置点匹配和轨迹曲线匹配。 具体来说，也就是可以分为： 点到点的匹配、点到弧段的匹配、弧段到弧段的匹配（仅使用地图路网的几何特征）和点到弧段的匹配、弧段到弧段的匹配（利用路网的几何和拓扑特征）。 其中 ,位置点匹配算法逻辑简单 ,实时性好 ,但 在道路密集、道路形状复杂和交叉路口等情况下 ,匹配准确率较低；轨迹曲线匹配算法匹配准确率高 ,但算法复杂、计算量大 ,很难满足车辆定位的实时性要求。 各种地图匹配算法的情况比较见表 3-1。 nts江 苏 大 学 毕 业 论 文 作者，年份 算法 过程 内容 /缺点 Bernstein and Kornhauser (1996) Kim et al (1996) White et al (2000) 地图匹配看做搜索问题，或者说是点到点的匹配 把 GPS点匹配到路网上最近的接点或者是形状点 A） 只有几何信息 B） 不考虑历史信息 C） 路网资料数化 Bernstein and Kornhauser (1996) White et al. (2000) Taylor et al. (2001) 点到弧段的匹配 把 GPS点匹配到路网上最近的弧段（点到曲线的最小值） A） 只有几何信息 B） 很少利用历史信息，因此有时会选择错误路段 C） 不很稳定 White et al. (2000) 有方向的点到弧段的匹配 带方向信息的点到弧匹配算法，如当前 GPS点与弧段方向不可比较，则抛弃该弧段 A） 比点到弧段匹配更好的算法 B） 当车辆速度很慢或者为 0时， GPS方向有时出错 Bernstein and Kornhauser (1996) White et al. (2000) Taylor et al. (2001) 弧段到弧段的匹配 用定义部分道路中心线的一系列点的弧段定义连续的 GPS点位置 A） 几何信息 B） 对外部数据相当敏感 C） 有时会产生意想不到的结果 Bernstein and Kornhauser (1996) White et al. (2000) 改进的点到弧段的匹配 给出起始点，路网拓扑信息减少相似弧段的产生 运用了几何和拓扑信息，依赖起始点，一个错误的匹配会引起一系列错误的匹配 Bernstein and Kornhauser (1996) White et al. (2000) 改进的弧段到弧段的匹配 运用路网拓扑信息进行弧段到弧段的匹配 实现起来非常复杂 Krakiwsky et al.(1988) Scott and Drane(1994) Jo et al. (1996) 用统计方法实现地图匹配 考虑点的顺序并匹配到合适的路段，这弧段取决与路网 该物理运动模型只适用于直线，但现实确实路网 Greenfeld, J.S. (2002) 类似权值系统的标准 分析路网的拓扑信息 A） 简单 ，有效 B） 在交叉点容易产生错误匹配 C） 决定车辆方向不稳定 表 3-1 由表 3-1我们可以清楚地看到，当前的地图匹配算法的关键在于从众多的候选路段选择合适的匹配路段。一个错误的匹配可能导致一系列错误的匹配，另外，我们也必须关注拓扑道路网络的信息，地图匹配算法也需要考虑像市区范围内的交叉路口等的复杂的nts江 苏 大 学 毕 业 论 文 道路环境。 3.3 现有算法的局限性 我们知道，很多 算法的局限性是可以很容易识别的，就以下面两个算法为例，我们来分析算法的局限性，具体描述如下： 1、 Greenfeld (2002)算法 Greenfeld (2002)算法是应用类似权值的标准，通过分析路网的拓扑信息，来进行地图匹配的技术。但由于他没有考虑车辆的方向性，在决定车辆方向上有不少不稳定因素。特别是在交叉点容易产生错误匹配。 图 3-1 在交叉点没考虑车辆方向的错误匹配 在图 3-1，点 P1到 P20描绘了车辆在路网的行驶位置，在这个例子中，我们可以很容易地确定车辆行驶路线为 1-2-3-4。运用 Greenfeld (2002)算法或者其他的算法解释上面的部分，可以得到这些点的正确匹配路段直到 P10。然而，在点 P11，由于接收到的该 GPS点在P11和 P12所 在直线接近于路段 5， Greenfeld (2002)算法或者其他的算法会选择路段 5为合适路段。该算法选定该合适路段的原因是没有考虑车辆在 P11点的方向信息。还有许多相似的情况。 GPS/DR点的方向是相当精确的，通过考虑它，我们可以更容易地确定合适的路段。 2、 White et al(2000)算法 White et al(2000)算法是 考虑方向的点到弧段的匹配。它是比点到弧段匹配更好的算法，但是当车辆速度很慢或者为 0时， GPS方向有时会出错。 如图 3-2，我们也可以得到这样的 GPS/DR点的位置信息。在点 P1到点 P9，车辆匹配的合适