基于GOS的不停车收费系统-毕业论文.doc

《基于GOS的不停车收费系统-毕业论文.doc》由会员分享，可在线阅读，更多相关《基于GOS的不停车收费系统-毕业论文.doc（41页珍藏版）》请在三一办公上搜索。

1、毕 业 设 计（论 文）题目：基于GPS的不停车收费地图匹配方法研究院 别： 专业班级： 学生姓名： 学 号： 指导教师： 2013年6月15日摘 要基于GPS的不停车收费技术代表着未来道路收费的发展方向，精确的地图匹配决定该收费系统能否成功实现精确收费。本文概述了各种常用的地图匹配算法，并就各种地图匹配算法进行系统的分析和对比，在此理论基础上，提出基于GPS的不停车收费系统的地图匹配算法。本文以自驾车从黄岛到济南为例，对此路线中收费用地图中的关键点即收费点进行定义，并提出了一种新的专门用于收费的地图匹配算法。此算法被证实是具有可行性的。关键词：GPS，不停车收费，收费电子地图，地图匹配ABS

2、TRACTDo parking charge based on GPS technology represents the future development direction of road pricing.Accurate map matching decided to achieve precise charging of the success of the charging system. This article outlined the various commonly used map matching algorithm, and a variety of map mat

3、ching algorithm for system analysis and comparison, based on the theory, put forward the no parking charge system based on GPS map matching algorithm. Taking self-driving from Huangdao to Jinan as an example, this route in charge with the points on the map the charge points are defined, and a new ma

4、p matching algorithm is designed to charge. The algorithm is proved to be feasible.Key Words: GPS,no parking charge, electronic map,map matching 目 录摘 要：IABSTRACTII目 录11 绪论31.1 论文研究的背景31.2 道路收费的发展历程31.3 GPS收费系统的原理与特点51.3.1 DSRC电子收费技术61.3.2 ANPR电子收费技术71.3.3 基于GPS的不停车收费技术91.3.4 DSRC、ANPR和基于GPS的电子收费技术的性

5、能比较及分析121.4本文研究内容及结构132 地图匹配技术152.1 地图匹配的基本原理152.2 常用地图匹配算法182.2.1 最短距离算法182.2.2 概率统计算法192.2.3 基于拓扑关系的算法202.3 地图匹配方法分析212.4 地图匹配的应用223 基于GPS的不停车收费系统地图匹配方法243.1基于GPS不停车收费地图匹配的作用243.2 基于GPS的收费地图的定义243.2.1道路收费地图收费关键点及收费路段定义253.2.2主线站出入口特殊处理253.2.3收费关键点和收费路段属性值的定义253.2.4地图精简273.3基于GPS的不停车收费系统的地图匹配方法283.

6、3.1 地图匹配中搜索范围的确定283.3.2卫星收费地图匹配算法描述293.4 该算法可行性实验344 总结36致 谢37参考文献381 绪论1.1 论文研究的背景高速公路因其“高速、高效、安全、舒适”等优点，在现代化公路建设中己成为发展的必然趋势。作为连接主要城市和重要港口的枢纽高速公路，已成为承载繁忙运输的交通要道。我国的“十二五”规划中明确指出，要进一步完善公路网络，发挥路网整体效率。全国公路总里程已超过400万公里，五年增加38万公里，高速公路里程已达6.4万公里，总里程数位于世界第一。然而，与公路建设相比，公路收费的自动化水平却相对滞后，传统的收费方式（找零、回票、投币）无法缓解尖

7、峰时间的车流量，效率低下，使车辆在收费站区域滞留，形成“瓶颈”，不能很好的发挥高速公路的服务优点，从而使电子不停车收费系统应时而生。电子不停车收费系统是智能交通系统的主要服务内容之一，是国内外正在不断开发并推广普及的一种用于公路、大桥和隧道的电子自动收费系统。目前广泛应用的主要是利用专用短程微波通信技术，通过路侧单元（RSU）与车载单元（OBU）的信息交换，自动识别车辆，采用电子支付方式，自动完成车辆通行费扣除的全自动收费方式。而基于GPS的不停车收费系统是世界上最先进的电子收费方式之一，它的诸多优点注定其必将成为未来发展的方向。作为电子不停车收费中最具广泛应用前景的GPS不停车收费系统正逐渐

8、受到人们的青睐。卫星收费电子地图是卫星收费系统中的核心技术，能够实现 GPS 的不停车收费技术的精确收费，而目前正由于车载设备成本高，使该收费系统受到一定的限制，因此车载收费电子地图匹配方法具有重要的研究价值。目前关于国外道路收费方面技术资料大多限于对收费系统的介绍，而收费地图匹配技术介绍很少。常规的用于导航系统中的地图匹配方法是通过投影距离和车辆行驶方向与路段矢量方向差值加权的方法来进行地图匹配，判断出车辆行驶的路段。由于这些方法需要完全的地图路段信息较大的计算能力和存储单元，从而增加了车载设备的成本。另外需要判断匹配的路段较多，对信号可靠性的要求也比较高。加之道路收费自身的一些特点，上述方

9、法不适合道路收费使用。因此需要对基于GPS的不停车收费地图匹配方法进行大量研究和试验。1.2 道路收费的发展历程自从道路收费开始应用与人们的日常生活中以来，收费技术经历了从低级到高级，从功能简单到功能完善丰富的过程。首先是无任何设备的人工收费方式，发展成为现在的半自动收费和电子收费。道路收费技术发展历程如图1-1所示。人工收费是指完全靠收费员来分辨车型、发卡、开票验证、按里程计收费用、保管现金、统计数据和结帐的收费方法。从20世纪60年代以来，很多地方就采用这种简单的收费办法。目前，中国的一些收费公路（特别是低等级公路）仍广泛采用这种收费方式。半自动收费是指在道路入口处由人工识别车型、发卡，但

10、在出口处通过仪器设备来读卡、人工进行收费、显示收费金额、付费放行等的收费方式。电子不停车收费（Electronic Toll Collection，简称ETC）系统是国际上正在努力开发并推广普及的一种专门用于公路、桥梁和隧道的新型电子自动收费技术。它包括三种技术：基于DSRC（Dedicated ShortRange Communication，短程无线通信）电子收费技术、基于ANPR（Automatic Number Plat Recognition，车牌识别）电子收费技术及基于GPS（Global Positioning System全球定位系统）电子收费技术。ETC的三大特点：无需人、不

11、停车、无现金。图1-1 道路收费发展历程首先，高速公路收费由传统的人工收费到不停车非现金收费经历了漫长的过程，虽然国内外目前均是多种收费方式并存的情况，但不停车电子收费必然成为未来收费方式的主流发展方向，世界各国均在努力发展适合本国国情的不停车收费系统，并在努力促使其标准化。在国际上，美国、欧洲、日本很早就针对不停车收费系统中的研发技术、工程实施、标准规范进行了深入研究。在美国，电子不停车收费方式已经成为美国回收公路投资和养护费用的高效率手段，最著名的联网运行电子不停车收费系统是EZpass系统。葡萄牙的Via Vance电子收费系统可以算作欧洲具有代表意义的联网电子收费系统之一，事实已证明，

12、Via Vance电子收费系统是既有利于道路使用者又有利于道路运营商的有效收费手段。国际标准化组织（ISO）、欧洲准化委员会（CEN）也在开展不停车收费领域的技术标准化工作。其次，联网收费项目已经成为国内、国际不停车收费的主流方向，但在电子收费系统从引进我国到实施，经过了一段时间的实践，目前也取得了一定的进展。如今国内的ETC系统采用的基本都是基于DSRC技术的不停车收费系统。由于早期的不停车收费系统的引进采取公路管理部门自主引进的方式，没有一个统一的标准，各个地区不停车收费系统的技术标准不尽相同。至于车道结构、通信网络、监控系统等等更是各行其是。至今我国的基于DSRC的技术标准也还在制定和完

13、善中，仍未公布。如今，我国公路收费系统从各路段独立收费的状态步入了联网统一收费、通行费多业主拆分的时代。在实施区域联网收费的进程中，标准的不一致，协调上的困难，使我国的不停车收费系统逐渐暴露出了一些问题:1）各个城市的不停车收费系统需要在地区内得以统一，比如说首先在省的范围内。这就需要扩大规模，路网规模的扩大，将导致ETC系统规模的扩大，使一次性投资增加，周期更长，风险更大。2）现有的不停车收费系统造价比较高，许多关键的设备需要引进。3）国内己建的收费站中，大多数的入口收费站和出口收费站的交通量小，车道数量少，如果考虑单独辟出一条专用的ETC车道在建设上比较困难，在利用率上又不够经济。总之，我

14、国的ETC项目进展并不顺利，有些大项目碰到了很复杂的协调问题，有些项目正式运行后因多种原因无法扩大规模，用户群较小。与半自动收费方式相比，电子收费系统的运行市场化特色更浓一些，要求运营公司有很高的商业运作能力。在现阶段，各方面的精力主要集中在人工半自动的区域联网收费工作上。1.3 GPS收费系统的原理与特点电子收费技术从实现的技术手段上可分为3种：短程无线通信（Dedicated Short-Range Communication，DSRC）电子收费技术，车牌识别 （Automatic Number Plat recognition，ANPR）电子收费技术及卫星定位（Vehicle Posit

15、ioning System，车辆定位系统）电子收费技术。1.3.1 DSRC电子收费技术1. DSRC电子收费技术的定义DSRC电子收费技术是近几年国际上比较成熟的收费技术。它是利用安装在路侧的路边设备 （R0adSaid Unit，简称RSU）与行驶在收费道路的车辆上的车载装置（OnBoard Unit，简称OBU）联系起来，司机不停车、不使用现金而支付通行费用的一种收费技术。它可以应用在城市道路收费、公路收费及大桥和隧道收费中。 2. DSRC电子收费系统的构成DSRC电子收费系统包括前端系统和后台系统组成：其中前端系统包括OBU车载单元、DSRC路边设备、车辆分类系统、执法系统等；后台系

16、统主要实现车辆通行费的结算、清分等功能。3. DSRC电子收费系统的工作原理整个DSRC电子收费系统大致的运行过程是：1）用户前往发行安装部门，申请安装车载装置，预缴通行费或设立事后付费帐户，相应的信息被存入车载装置中，然后该车便可以上路行驶。2）在进入收费站时，车辆按规定限速通过收费车道。DSRC路边设备通过天线与车载单元进行双向通信，收费操作在通信的过程中同时完成。收费操作的具体步骤包括根据车型按照收费标准确定收费额、核对余额、帐号信息、有关结果通知对方等。如果一切无误（剩余余额充足或帐号有效时），则正常结束收费操作（改写余额、记帐等）。否则（剩余余额不足或帐号无效时）启动执法系统记录其车

17、辆号码，以保证通行费最终能被征收，不致流失。3）每次收费操作，都需将收费操作的相关信息递交后台系统，后台系统对这些信息按照不同类别分别进行处理。正常收费信息可以积累汇总，产生相应的收入报告，同时，事后付款方式的收费数据将定时（或实时）递送给后台系统，以便生成转帐清单向金融机构请求支付。不正常收费信息将立即通知执法系统，以确保统一及时处理。后台系统除了接收收费车道呈递的信息外，还向收费车道发送相关信息，如收费标准、帐号“黑名单”等。 4）在系统中，金融机构负责提供金融服务，包括管理事后付款帐户及收费帐户，处理各种转帐、清帐事务，还参与车载装置的发行、安装。同时，它也向系统提供一定的信息，如不良信

18、息帐号的“黑名单”业务结算结果等。4. DRSC 优缺点DRSC电子收费是利用安装在路侧的路边设备 （RSU）与行驶在收费道路车辆上的车载装置（OBU） 联系起来，司机不停车、不使用现金而支付通行费用的一种收费技术。它具有如下优点： 1）收费精确。对于采用DSRC电子收费技术组成的道路收费系统，它可以对通过设有天线的收费站点的车辆进行精确收费、误差极小、并可以结合图像抓拍等技术，对于未安装车载装置（OBU）的车辆进行严格控制。 2）技术成熟，系统完整性好。DSRC电子收费系统是经过多年发展的成熟技术。在采用该技术的条件下，道路收费系统可以适应多种实际应用要求，包括多种费用支付要求，且系统灵活性

19、好，可以与其它应用比较密切地结合。 同时存在以下不足： 1）系统的前期投资大。该技术要求用户在相应的车辆上安装车载OBU，导致前期投资比较大。一般单片式OBU价格为200300元，双片式则多达500元左右。 2）违章处理弊端。要求用户必须安装OBU，否则按违章车辆处理。用户的配合问题也是该系统有效实施的关键。3）需要安装龙门架。一方面增加大量投资，另一方面，如果是在城市道路上会有碍市容，同时在市区中安装龙门架存在地理位置限制、影响交通等问题1.3.2 ANPR电子收费技术 1ANPR电子收费技术的定义 车牌识别技术（Automatic Number Plate Recognition，简称AN

20、PR）是基于图像处理与光学字符识别（OCR）的汽车牌照自动识别技术，主要运用“不同车辆不同牌照”的思想概念来识别车辆。ANPR电子收费技术是指在收费区内不设收费站，司机或者车主需要预先预付交通道路通行费，并将汽车牌照输入到计算机的数据库中。当车辆行使到收费区及出口时，系统利用车牌识别摄像机拍摄车辆照片，并将图片传输至中心，通过ANPR软件自动识别车辆，并与计算机数据库内的交款车辆进行比对，已付款的车辆进行核销，未付款的车辆会被记录下来，待工作人员核实之后，就会送出罚单。 2ANPR电子收费系统的构成 ANPR电子收费系统由前端采集系统和后台收费管理系统组成。前端采集系统包括视频摄像机（获取车辆

21、图像）和照明灯（用于拍摄光源补充）以及相应的视频传输设备等，后台收费管理系统主要实现车辆通行费的管理等功能。3ANPR电子收费系统的工作原理整个ANPR电子收费系统的工作流程如下： 1）司机或者车主需要通过通行费支付系统预先预付交通道路通行费。预付手段有4种：路侧自助付费，因特网付费，手机付费和特约银行付费。在付费的同时需要将车主自己的车牌号码输入收费管理系统中，以便保存到相应的车牌数据库中。 2）当车辆行驶到收费区内及出入口时，ANPR电子收费系统就利用安装在收费区域边缘（出入口）的固定视频摄像机或移动视频摄像机拍摄通过的车辆照片并通过一定传输线路将视频流传至收费管理中心。 3）收费管理中心

22、通过ANRP软件读取图像、识别车牌以及与数据库内交款车辆的车牌进行匹配，已付款的车辆进行核销，未付款的车辆会被记录下来，待工作人员核实之后，就会送出罚单。对于那些不能识别的车牌将有中心系统通过人工的办法来识别，对于那些未付款的车辆将会保存它进入收费区域配有时间、日期以及位置的图片，以便作为处罚的证据。 4. ANPR电子收费系统概况 车牌识别技术在道路收费的应用主要是辅助收费系统的执法功能，在半自动收费和电子收费中都是利用ANRP来实现逃费抓拍系统（Video Enforcement System，简称VES），而真正采用ANPR作为一种收费技术是2003年2月伦敦市政府在中心区实施道路拥挤收

23、费。除伦敦外，采用相似技术的有安大407ETR（Expos Tol Route）电子收费系统以及英国Darford桥梁电子收费系统。随着车牌识别精度的改善，相信这种收费技术将会有越来越大的发展空间。同样，车牌识别技术在我国道路收费的应用主要是辅助收费系统的执法功能，在半自动收费和电子收费中都是利用ANRP来实现逃费抓拍系统。但是伦敦拥挤收费已经在我国引起强烈反响，我国的北京、上海、广州、南京、深圳等城市已经开展了城市拥挤收费的研究，相信ANPR电子收费技术在不久的将来会有助于解决中国城市拥挤问题。5. ANPR电子收费技术的优缺点 ANPR电子收费技术适用于预交费的情况，可实行对经过的车辆进行

24、自动扣款收费，能实现不停车收费，它有如下特点： 1）ANPR收费系统只需在固定识别点安装摄像机（需要配套的支撑装置，如电线杆），路侧设施投人相对比较少，且ANPR收费技术不需要安装车载设备，减免了道路收费用户的投人； 2）通过ANPR软件识别车牌并能添加相应的时间、地点信息，便于按里程、滞留收费。同时存在以下弊端： 1）自动车牌识别技术虽然发展的时间比较长，但是识别率不高，是制约ANPR收费的关键所在；2）车牌识别技术的性能指标（识别率）不能满足道路收费的实际需要，系统的稳定性需要进一步提高； 3）运营管理复杂，不能完成现场扣款； 4）天气对摄像机捕获车辆图像的影响比较大； 5）ANPR收费系

25、统功能扩展性是有限的。1.3.3 基于GPS的不停车收费技术1. 基于GPS的不停车收费技术的定义 它利用卫星定位系统（Global Positioning System，简称GPS）及全球移动通信系统（Global System for Mobile Communication，简称GSM），通过与车载装置的通信，进行不停车收费。2. 基于GPS的不停车收费技术的构成 该系统包括GPS接收装置,用于接收GPS数据, 定位车辆; 电子地图及数据库, 其中包含所有收费高速公路及其出口的空间位置信息及高速公路段落名称、段落长度、所属业主及收费标准等属性信息;缴费卡,可持卡缴费及传递数据。3. 工作

26、原理基于卫星定位和无线接入技术的新一代收费系统，通过自动记录车辆行驶的位置和里程，综合考虑道路收费车辆参数和道路收费因素，自动计算车辆的通行费，由无线传输网络将数据传输到收费管理中心，根据相关公路收费政策，对车辆收取通行费。卫星定位收费系统包括智能车载收费设备（OBU）、稽查系统、管理中心3大部分组成，共同组成1个完整的卫星定位收费网络，如图1-2所示。 图1-2 卫星定位网络收费图该系统通过GPS接收卫星信号定位车辆当前位置,定位数据与电子地图结合应用路径辨识算法等判断车辆当前位置是否属于收费高速公路,如位于收费公路,记录虚拟入口时间、入口站号,接着等待出口,通过GPS定位当汽车离开公路时记

27、录出口时间,出口站号,通过入口站号与出口站号到数据库中查询其它属性信息,并增加收费记录。费用支付可采用实时支付或先使用后支付两种方式。实时支付可用缴费卡与车载装置相连,当车辆驶离高速公路时,实时扣取缴费卡中的相应费用,余额不足限定值时提示充值;先使用后付费方式可定期到指定机构交纳费用。无论哪种收费方式均可在缴费时传递收费数据, 然后依据收费数据通过银行或指定收费机构对收缴费用进行划分。定期对收费数据备份和更新电子地图及数据库。4. 系统特点（1）适用性好基于GPS的不停车收费系统利用现有车道即可, 不需要对车道改进, 不受道路扩宽, 增加车道等的影响,为采用该收费方式的汽车专留一个车道, 未安

28、装该种收费系统的车辆走人工收费车道, 随着该收费方式的普及, 逐渐取消所有人工收费车道。整个过程全部利用现有车道。另外由于该系统不需要在道路上建设收费设施, 因而不受道路施工的影响。当整个路网有新建高速公路时, 更新电子地图数据库即可。（2）可移植性强该收费系统在小范围内实验成功后可快速进行大规模推广, 有利于自动收费系统的快速发展。可首先对一个小行政区内车辆进行实验, 实验成功后, 大范围效仿相同方式进行即可。具有建设周期短, 硬件设施投入少, 易于大规模推广的特点。（3）可扩展性好该收费系统可与GPS卫星导航系统共同开发,并可进行功能扩展, 提供其它服务功能, 如车辆跟踪、信息查询、出行路

29、线规划等。在日本超过60%的新车出厂时就已安装了车辆导航系统, 可以预见, 随着更多汽车企业的介入,导航产品市场将逐渐成熟, 导航产品前景广阔, 与GPS相关的其它服务功能正在悄然兴起, 基于GPS的收费系统与GPS服务产品共同开发将更能调动道路使用者的积极性。 5. 基于GPS的不停车电子收费技术的优缺点 基于GPS的不停车电子收费技术是利用GPS及GSM，通过与车载装 置OBU的通信，进行不停车收费。它的特点如下： 1）GPS电子收费系统可以将路旁设备降低到很少，无需龙门架，不会因为安装龙门架而影响市容美观和道路交通，更适合于城市道路有效空间的利用。同时降低了设备的投资，在地理位置受限制的

30、地方，这种技术的优势更为明显。 2）提供灵活的收费区域定义和灵活的费用支付。DSRC收费技术在土地使用模式发生变化、收费区域需要改变时，克服传统基础设施改变存在比较大的困难。而GPS通过改变虚拟收费点的定义，非常容易实现。3）车载装置可由市场直接提供，GPRSGSM以及GPS技术规格己标准化，很多厂商具有生产制造能力，系统供应商较难垄断车载设备市场，故很容易跨平台或系统使用。 4）车载装置不仅是用作支付收费道路通行费的工具，它只要载人相关的应用软体，即可产生多用途，如：车载导航，车队管理，移动商务，车辆保全，交通信息等。 5）车载装置易扩展为移动商务基础平台的终端设备，并衍生其它商机。 6）具

31、有长距离通信的优点，收费机制较不受空间限制，容易实时地在整个区域内按里程收费及实施匝道收费，具备收费策略调整弹性。 同时基于GPS的不停车收费技术存在以下不足： 1）用户的OBU成本高，如果由此造成用户的数量减少，可能影响系统的有效运行。2）车载电子地图的更新复杂。 3）如果系统设计得不合理，将会涉及到用户的隐私问题，这是很多国家暂时不考虑这种方式的一个原因。 4）在技术上，相对于DSRC电子收费技术要新。GPS技术是成熟的，但应用在不停车收费方面比较少。在城市道路中GPS定位信号容易受到建筑物的阻挡，影响车辆的定位，需要辅助系统支持。 5）GPS电子收费系统的运营需要配套法规、政策和严厉的惩

32、罚制度，特别是针对那些“违规车辆”以及故意损坏车载装置的行为。 1.3.4 DSRC、ANPR和基于GPS的电子收费技术的性能比较及分析DSRC收费技术、ANPR收费技术及VPS收费技术，这3种电子收费技术都各有自己的优缺点。下面将从路侧设施成本、车载装置成本、技术成熟性、收费准确率、按车型收费、按里程或滞留收费、电磁干扰、景观影响、天气影响、外埠车辆收费、功能扩展、兼容性和可维护性等方面来比较，见表1-1。表 1-1 三种收费技术的性能比较特性指标DRSC收费技术ANPR收费技术GPS收费技术路侧设备成本高较低不需要车载装置成本较低（约500元）不需要高（约5000元）技术成熟性成熟比较成熟

33、不成熟收费准确率高一般高按车型收费好差好按里程、滞留收费一般好好电磁干扰有无有景观影响有有无天气影响无严重无 运营管理简单复杂（不能完成现场扣款）简单外埠车辆收费方便不方便比较方便功能扩展宽窄宽兼容性较差一般好可维护性较差一般好DSRC电子收费技术和基于GPS的不停车收费技术主要应用于公路收费，而ANPR电子收费技术主要用于城市拥挤收费。由以上3种收费技术的原理及技术性能比较分析可知：1） ANPR电子收费技术不成熟、且车牌识别精度不高，是制约这种技术发展的最大障碍。 2） DSRC电子收费技术成熟、且广泛使用，但需要高额费用来建设、维护路边设备。 3） 基于GPS的不停车收费技术比较新、且车

34、载装置投人较高，但其灵活的收费区域定义和费用支付方式及毋需建设龙门架等路边设备已受到全球的关注。 4）对一个较大范围的路网进行收费，基于GPS的不停车收费技术则可能较合适。以德国为例，其实施的货车收费系统将按其行驶里程与重量来计算应缴的道路通行费，由于其收费范围较大，收费点分布较广，采用DSRC电子收费技术的难度较大，费用也高，VlX3可能是较好的选择。对一条相对独立的收费公路，桥梁或隧道而言，DSRC电子收费技术可能是最佳选择，它用在类似新加坡的较小范围且单一、集中的市区道路收费也很合适。 5）由于收费分区与计价方式复杂，这类系统通常必须具备一套全国性或区域性的收费系统。再进一步设想，对于一

35、个收费区的不同道路按不同道路的等级实施差别费率时，基于GPS的不停车收费技术则更具有优势。1.4本文研究内容及结构基于GPS的不停车收费技术代表着未来道路收费的发展方向，精确的地图匹配决定该收费系统能否实现成功收费。本文概述了各种常用的地图匹配算法，并就各种地图匹配算法进行系统的分析和对比，在此理论基础上，提出基于GPS的不停车收费系统的地图匹配算法，本文以自驾车从黄岛到济南为例，对收费用地图中的关键点即收费点进行定义，并提出了一种专门用于收费的地图匹配算法。具体内容如下：1. 基于GPS的不停车收费系统的原理和特点概述，并就各种ETC技术对比分析。2. 系统的提出各种地图地图匹配技术。3.

36、以黄岛前往济南为例，对基于GPS地图进行重新定义，并给出了新的地图匹配算法。4总结。 2 地图匹配技术2.1 地图匹配的基本原理将用导航定位方法得到的车辆位置或行驶轨迹与车载的电子地图道路数据相比较、匹配，从而找到车辆所在的道路，并且显示出车辆的实时位置的软件修正技术叫地图匹配（Map Matching，MM）。地图匹配过程可分为两个相对独立的过程:1）寻找车辆当前行驶的道路；2）将当前定位点匹配到车辆行驶的道路上。地图匹配的两个条件是高精度的数字地图和车辆在路网中行驶。如果条件成立，就可以把定位数据和车辆运行轨迹同数字化地图所提供的道路位置信息相比较，通过适当的匹配过程确定出车辆最可能的行驶

37、路段以及车辆在该路段中的最大可能位置。反之，则地图匹配将产生错误的位置输出，并可能导致系统性能的严重下降。一般认为用于匹配的数字地图误差不应超过15m。由于陆地车辆在除了进入停车场等之外的决大多数时间都位于道路网络中，因此使用地图匹配技术的条件是满足的。在图2-1中，点A、B、C都是GPS观测点，显然这些观测点都没有准确的定位在道路上，地图匹配的任务就是通过一定的方法将这些点校正到道路的中心线上。现在地图匹配的算法有很多，但根据利用信息不同，大体上可以归结为两大类：1） 基于几何信息的地图匹配方法；2） 基于拓扑关系的地图匹配方法。基于几何信息的地图匹配方法有三类：点到点的匹配；点到线的匹配；

38、线到线的匹配。前两种可视为搜索问题，最后一种可视为统计估计问题。图2-1 地图匹配示意图1）点到点的匹配点到点的匹配就是搜索地图数据库中的节点、形状点或自定义的点距离GPS观测点最近的点作为匹配点。该方法简单易行，实现快速，但是匹配结果与路段上待匹配的点集关系密切，待匹配的点越多，匹配效果越好。匹配形式如图2-2显示。图2-2 点到点的匹配在图4-2中，A1、A2、A3、A4、A5、B1、B2、B3都是GPS观测点P的待匹配点。从图中可以看出，距离PA3是最短的，按照点到点匹配方法，应该将车辆匹配到A3点，但从图中直观看出，P点匹配到线段B上似乎更为合理些，因为P更靠近线段B。缺点在于匹配点少

39、时匹配结果不准确。2）点到线段的匹配点到线段的匹配就是搜索所有可能的线段，以GPS观测点到线段距离为判断依据，观测点到条线段距离最近的那条线段作为匹配路段，观测点到匹配路段的投影点即为匹配点。这种方法同样比较简单，也很直观，但该方法得到的结果的不足在于匹配结果会出现来回摆动的情况，当GPS观测点距离多条路段的距离相等时就无法进行路段匹配了，匹配形式如图2-3所示。图2-3点到线段的匹配在图4-3中，P1、P2、P3、P4是连续的GPS观测点，它们的匹配结果是这样的：（P1B1），（P2A1），（P3A2或P3B2），（P4B3）。可以看出，匹配结果出现了在线段A、B间摇摆的情况，还有观测点P3

40、无法确定匹配点。点到点的匹配、点到线的匹配都是仅仅利用了当前观测点位置进行匹配，没有充分利用历史和未来的观测点位置，有很大的局限性。3）线到线的匹配线到线的匹配就是将一系列GPS观测点拟合到道路网相应的路段中，拟合的标准就是观测点形成的折线到路段之间的距离，距离最短的为匹配路段。连线间的距离可以有很多种定义的方式，如定义两折线X、Y的距离为取它们间最近点的距离，即。匹配的示意图如图2-4（a）所示。图2-4 线到线的匹配（a）在图2-4（a）中，GPS观测点出现了一个离群点P，按照上述的匹配方法，GPS观测点被匹配到路段B上，这显然不合理，合理的匹配应该被匹配到线段A上。两折线间距离的定义还可

41、以如下，按照这样距离计算方式同样也会出现像图2-4（b）那样的错误匹配了。图2-4（b） 线到线的匹配在图2-4（b）中，待匹配路段A的坐标为（6t，6），待匹配路段B的坐标为（3，6t），GPS观测点连线的线段P的坐标为（6t，3）。按照上述距离计算方式，至于的计算，如果距离定义有正负定义（定义线一侧的点到线的距离为正，则另一侧的点到线的距离就为负），则；如果距离定义是取绝对值，则通过计算可得。按照匹配方法，就要选择B为匹配路段了，但从图上直观的看，选择A作为匹配路段似乎更为合理。在图中，P的长度为6，如果要求以使得GPS观测点正确的被匹配到A上，通过计算，P的长度至少是15，这显然延迟太大

42、，达不到实时校正车辆位置并正确显示的要求。上述的三种地图匹配方法相对来说都是计算简单，仅利用了数字地图的单一信息，不能保证任何时候都能得到正确的匹配结果，无法满足真正地图匹配的要求，因此根据这三种基本地图匹配方法衍生出来了许多比较实用的地图匹配算法。2.2 常用地图匹配算法地图匹配的常用算法有很多，比如最短距离算法、基于拓扑关系的算法、概率统计算法、模糊逻辑算法、相关性算法等等。下面对其中的几种进行简要分析。2.2.1 最短距离算法最短距离法是一种基础的匹配方法。该方法根据道路属性，预先设置一个匹配阈值，在数字地图数据库中的所有或部分路段中，计算当前获取的GPS数据与各道路路段之间的距离以及G

43、PS数据在该道路路段上的最短距离点，将在阈值范围内各路段的匹配距离进行比较，得到一条距离最短的路段，则该道路为GPS点的匹配路段，该最短距离点为GPS点的匹配点。最短距离法简单易行，能在很大程度上消除地图匹配中各种误差产生的影响，但它没有考虑GPS数据接收中的各种情况及道路的地形特征，通常作为一种基本方法，与其他匹配方法结合来得到好的效果。2.2.2 概率统计算法基于概率统计的地图匹配同样是一种基础的匹配方法。概率统计算法的基本思想是根据GPS接收到的数据，首先设置一个置信区域，并从中提取用以匹配的道路位置信息，依据已有匹配结果的概率统计，经过比较判断，确定车辆在这一置信区域内的匹配路段。基于

44、误差模型，根据接收的GPS定位数据建立缓冲区。按照统计理论，定位误差椭圆可推导如下: （2-1） （2-2） （2-3）其中，是椭圆长半轴取向与正北方向的夹角，a和b是误差椭圆的长、短轴，和分别是GPS东向和北向测量误差的标准差，是协方差，是单位权值的后验方差。通过改变的值来调整误差椭圆的大小，获得不同的可信度。在车辆导航系统中，利用GPS的接收模块的参数来定义误差椭圆。误差椭圆的定义如图2-5所示。图2-5 误差椭圆的定义该算法利用误差椭圆确定了误差区域，以便从数字地图数据库中提取候选路段的信息，从而减少候选路段的数目，缩短地图匹配的计算时间，但它没有历史信息进行有效利用，当道路较为密集的时

45、候，可能会出现匹配点在几条路段间反复跳跃的情况，与基于拓扑关系的地图匹配方法相结合能得到较好的效果。2.2.3 基于拓扑关系的算法拓扑空间关系是一种对空间结构进行明确定义的数学方法。GIS中，常将空间事物抽象成点、线、面等几何要素，并在点、线、面之间建立拓扑关联关系。具有拓扑信息的矢量数据是网络分析必要的数据来源。数字地图数据包含：1）节点：表示空间对象所在的位置，或者线段的起始、终止点，它具有特定的拓扑性质。2）形状点：表示线、面经过的点，不具拓扑性质。3）线（弧线）：起始与终止点为节点、并且具有若干形状点的有序点集。4）面：由若干弧线相连的封闭曲线围成的区域称为面，面以弧线的形式表示，但通

46、过代码与弧线区别，且其内部填充方式可以设置。建立道路网拓扑关系的一般步骤为：1）数据预处理：数据压缩（剔除冗余数据，提高计算速度）和自动断链（使整幅图图形无相交或自相交链）。2）结点匹配：建立点、弧段关联关系。3）追踪多边形：以左转算法或右转算法跟踪，生成多边形，建立多边形与弧段的关系。4）多边形嵌套关系的生成，建立多边形嵌套关系树，即找出多边形包含的“岛屿”，建立多边形与多边形之间的关系。5）具有嵌套关系多边形的关联弧段的左右面的编号调整及多边形内点自动生成。基于拓扑关系的匹配算法是在道路层网络拓扑关系的数据基础上进行的，是利用历史轨迹对地图数据库的道路信息进行实时的模式识别的一种方式。拓扑

47、关系在电子地图中一般是指节点和路段之间的拓扑关系。在一段时间内，车辆行驶的区域是有限的，而且这个区域的道路也是有限的，因此在区域中建立的道路实体对也是有限的。电子地图足够精确并且具有路网拓扑完整性是地图匹配能够正常工作的前提。由于受车辆速度的限制，在一定的时间内，车辆只能驶经有限的路段上。如下图2-6所示，假设当前时刻车辆行驶在道路1上，由于速度等各种因素的存在，在下一时刻，车辆只可能出现在道路2、道路3或道路4上，即与道路1相连的道路链上，不可能直接跳到道路5或道路6上，如下图2-6所示。图2-6 道路拓扑关系基于拓扑关系的算法通过对前一次匹配结果和车辆前进方向的分析，利用道路层的网络拓扑关系，来确定当前车辆的匹配位置。但是，这种方法也仅利用了电子地图的单一信息，同时，其匹配效果