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

题目：基于GPS的不停车收费地图匹配方法研究I 摘 要基于GPS的不停车收费技术代表着未来道路收费的发展方向，精确的地图匹配决定该收费系统能否成功实现精确收费。本文概述了各种常用的地图匹配算法，并就各种地图匹配算法进行系统的分析和对比，在此理论基础上，提出基于GPS的不停车收费系统的地图匹配算法。本文以自驾车从黄岛到济南为例，对此路线中收费用地图中的关键点即收费点进行定义，并提出了一种新的专门用于收费的地图匹配算法。此算法被证实是具有可行性的。关键词：GPS，不停车收费，收费电子地图，地图匹配青岛理工大学毕业设计（论文） ABSTRACTABSTRACTDo 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 matching 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 map matching algorithm is designed to charge. The algorithm is proved to be feasible.Key Words: GPS,no parking charge, electronic map,map matching II青岛理工大学毕业设计（论文） 目录26目 录摘 要：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的电子收费技术的性能比较及分析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.3.1 地图匹配中搜索范围的确定283.3.2卫星收费地图匹配算法描述293.4 该算法可行性实验344 总结36致 谢37参考文献3838青岛理工大学毕业设计（论文） 1 绪论1 绪论1.1 论文研究的背景高速公路因其“高速、高效、安全、舒适”等优点，在现代化公路建设中己成为发展的必然趋势。作为连接主要城市和重要港口的枢纽高速公路，已成为承载繁忙运输的交通要道。我国的“十二五”规划中明确指出，要进一步完善公路网络，发挥路网整体效率。全国公路总里程已超过400万公里，五年增加38万公里，高速公路里程已达6.4万公里，总里程数位于世界第一。然而，与公路建设相比，公路收费的自动化水平却相对滞后，传统的收费方式（找零、回票、投币）无法缓解尖峰时间的车流量，效率低下，使车辆在收费站区域滞留，形成“瓶颈”，不能很好的发挥高速公路的服务优点，从而使电子不停车收费系统应时而生。电子不停车收费系统是智能交通系统的主要服务内容之一，是国内外正在不断开发并推广普及的一种用于公路、大桥和隧道的电子自动收费系统。目前广泛应用的主要是利用专用短程微波通信技术，通过路侧单元（RSU）与车载单元（OBU）的信息交换，自动识别车辆，采用电子支付方式，自动完成车辆通行费扣除的全自动收费方式。而基于GPS的不停车收费系统是世界上最先进的电子收费方式之一，它的诸多优点注定其必将成为未来发展的方向。作为电子不停车收费中最具广泛应用前景的GPS不停车收费系统正逐渐受到人们的青睐。卫星收费电子地图是卫星收费系统中的核心技术，能够实现 GPS 的不停车收费技术的精确收费，而目前正由于车载设备成本高，使该收费系统受到一定的限制，因此车载收费电子地图匹配方法具有重要的研究价值。目前关于国外道路收费方面技术资料大多限于对收费系统的介绍，而收费地图匹配技术介绍很少。常规的用于导航系统中的地图匹配方法是通过投影距离和车辆行驶方向与路段矢量方向差值加权的方法来进行地图匹配，判断出车辆行驶的路段。由于这些方法需要完全的地图路段信息较大的计算能力和存储单元，从而增加了车载设备的成本。另外需要判断匹配的路段较多，对信号可靠性的要求也比较高。加之道路收费自身的一些特点，上述方法不适合道路收费使用。因此需要对基于GPS的不停车收费地图匹配方法进行大量研究和试验。1.2 道路收费的发展历程自从道路收费开始应用与人们的日常生活中以来，收费技术经历了从低级到高级，从功能简单到功能完善丰富的过程。首先是无任何设备的人工收费方式，发展成为现在的半自动收费和电子收费。道路收费技术发展历程如图1-1所示。人工收费是指完全靠收费员来分辨车型、发卡、开票验证、按里程计收费用、保管现金、统计数据和结帐的收费方法。从20世纪60年代以来，很多地方就采用这种简单的收费办法。目前，中国的一些收费公路（特别是低等级公路）仍广泛采用这种收费方式。半自动收费是指在道路入口处由人工识别车型、发卡，但在出口处通过仪器设备来读卡、人工进行收费、显示收费金额、付费放行等的收费方式。电子不停车收费（Electronic Toll Collection，简称ETC）系统是国际上正在努力开发并推广普及的一种专门用于公路、桥梁和隧道的新型电子自动收费技术。它包括三种技术：基于DSRC（Dedicated ShortRange Communication，短程无线通信）电子收费技术、基于ANPR（Automatic Number Plat Recognition，车牌识别）电子收费技术及基于GPS（Global Positioning System全球定位系统）电子收费技术。ETC的三大特点：无需人、不停车、无现金。图1-1 道路收费发展历程首先，高速公路收费由传统的人工收费到不停车非现金收费经历了漫长的过程，虽然国内外目前均是多种收费方式并存的情况，但不停车电子收费必然成为未来收费方式的主流发展方向，世界各国均在努力发展适合本国国情的不停车收费系统，并在努力促使其标准化。在国际上，美国、欧洲、日本很早就针对不停车收费系统中的研发技术、工程实施、标准规范进行了深入研究。在美国，电子不停车收费方式已经成为美国回收公路投资和养护费用的高效率手段，最著名的联网运行电子不停车收费系统是EZpass系统。葡萄牙的Via Vance电子收费系统可以算作欧洲具有代表意义的联网电子收费系统之一，事实已证明，Via Vance电子收费系统是既有利于道路使用者又有利于道路运营商的有效收费手段。国际标准化组织（ISO）、欧洲准化委员会（CEN）也在开展不停车收费领域的技术标准化工作。其次，联网收费项目已经成为国内、国际不停车收费的主流方向，但在电子收费系统从引进我国到实施，经过了一段时间的实践，目前也取得了一定的进展。如今国内的ETC系统采用的基本都是基于DSRC技术的不停车收费系统。由于早期的不停车收费系统的引进采取公路管理部门自主引进的方式，没有一个统一的标准，各个地区不停车收费系统的技术标准不尽相同。至于车道结构、通信网络、监控系统等等更是各行其是。至今我国的基于DSRC的技术标准也还在制定和完善中，仍未公布。如今，我国公路收费系统从各路段独立收费的状态步入了联网统一收费、通行费多业主拆分的时代。在实施区域联网收费的进程中，标准的不一致，协调上的困难，使我国的不停车收费系统逐渐暴露出了一些问题:1）各个城市的不停车收费系统需要在地区内得以统一，比如说首先在省的范围内。这就需要扩大规模，路网规模的扩大，将导致ETC系统规模的扩大，使一次性投资增加，周期更长，风险更大。2）现有的不停车收费系统造价比较高，许多关键的设备需要引进。3）国内己建的收费站中，大多数的入口收费站和出口收费站的交通量小，车道数量少，如果考虑单独辟出一条专用的ETC车道在建设上比较困难，在利用率上又不够经济。总之，我国的ETC项目进展并不顺利，有些大项目碰到了很复杂的协调问题，有些项目正式运行后因多种原因无法扩大规模，用户群较小。与半自动收费方式相比，电子收费系统的运行市场化特色更浓一些，要求运营公司有很高的商业运作能力。在现阶段，各方面的精力主要集中在人工半自动的区域联网收费工作上。1.3 GPS收费系统的原理与特点电子收费技术从实现的技术手段上可分为3种：短程无线通信（Dedicated Short-Range Communication，DSRC）电子收费技术，车牌识别 （Automatic Number Plat recognition，ANPR）电子收费技术及卫星定位（Vehicle Positioning System，车辆定位系统）电子收费技术。1.3.1 DSRC电子收费技术1. DSRC电子收费技术的定义DSRC电子收费技术是近几年国际上比较成熟的收费技术。它是利用安装在路侧的路边设备 （R0adSaid Unit，简称RSU）与行驶在收费道路的车辆上的车载装置（OnBoard Unit，简称OBU）联系起来，司机不停车、不使用现金而支付通行费用的一种收费技术。它可以应用在城市道路收费、公路收费及大桥和隧道收费中。 2. DSRC电子收费系统的构成DSRC电子收费系统包括前端系统和后台系统组成：其中前端系统包括OBU车载单元、DSRC路边设备、车辆分类系统、执法系统等；后台系统主要实现车辆通行费的结算、清分等功能。3. DSRC电子收费系统的工作原理整个DSRC电子收费系统大致的运行过程是：1）用户前往发行安装部门，申请安装车载装置，预缴通行费或设立事后付费帐户，相应的信息被存入车载装置中，然后该车便可以上路行驶。2）在进入收费站时，车辆按规定限速通过收费车道。DSRC路边设备通过天线与车载单元进行双向通信，收费操作在通信的过程中同时完成。收费操作的具体步骤包括根据车型按照收费标准确定收费额、核对余额、帐号信息、有关结果通知对方等。如果一切无误（剩余余额充足或帐号有效时），则正常结束收费操作（改写余额、记帐等）。否则（剩余余额不足或帐号无效时）启动执法系统记录其车辆号码，以保证通行费最终能被征收，不致流失。3）每次收费操作，都需将收费操作的相关信息递交后台系统，后台系统对这些信息按照不同类别分别进行处理。正常收费信息可以积累汇总，产生相应的收入报告，同时，事后付款方式的收费数据将定时（或实时）递送给后台系统，以便生成转帐清单向金融机构请求支付。不正常收费信息将立即通知执法系统，以确保统一及时处理。后台系统除了接收收费车道呈递的信息外，还向收费车道发送相关信息，如收费标准、帐号“黑名单”等。 4）在系统中，金融机构负责提供金融服务，包括管理事后付款帐户及收费帐户，处理各种转帐、清帐事务，还参与车载装置的发行、安装。同时，它也向系统提供一定的信息，如不良信息帐号的“黑名单”业务结算结果等。4. DRSC 优缺点DRSC电子收费是利用安装在路侧的路边设备 （RSU）与行驶在收费道路车辆上的车载装置（OBU） 联系起来，司机不停车、不使用现金而支付通行费用的一种收费技术。它具有如下优点： 1）收费精确。对于采用DSRC电子收费技术组成的道路收费系统，它可以对通过设有天线的收费站点的车辆进行精确收费、误差极小、并可以结合图像抓拍等技术，对于未安装车载装置（OBU）的车辆进行严格控制。 2）技术成熟，系统完整性好。DSRC电子收费系统是经过多年发展的成熟技术。在采用该技术的条件下，道路收费系统可以适应多种实际应用要求，包括多种费用支付要求，且系统灵活性好，可以与其它应用比较密切地结合。 同时存在以下不足： 1）系统的前期投资大。该技术要求用户在相应的车辆上安装车载OBU，导致前期投资比较大。一般单片式OBU价格为200300元，双片式则多达500元左右。 2）违章处理弊端。要求用户必须安装OBU，否则按违章车辆处理。用户的配合问题也是该系统有效实施的关键。3）需要安装龙门架。一方面增加大量投资，另一方面，如果是在城市道路上会有碍市容，同时在市区中安装龙门架存在地理位置限制、影响交通等问题1.3.2 ANPR电子收费技术 1ANPR电子收费技术的定义 车牌识别技术（Automatic Number Plate Recognition，简称ANPR）是基于图像处理与光学字符识别（OCR）的汽车牌照自动识别技术，主要运用“不同车辆不同牌照”的思想概念来识别车辆。ANPR电子收费技术是指在收费区内不设收费站，司机或者车主需要预先预付交通道路通行费，并将汽车牌照输入到计算机的数据库中。当车辆行使到收费区及出口时，系统利用车牌识别摄像机拍摄车辆照片，并将图片传输至中心，通过ANPR软件自动识别车辆，并与计算机数据库内的交款车辆进行比对，已付款的车辆进行核销，未付款的车辆会被记录下来，待工作人员核实之后，就会送出罚单。 2ANPR电子收费系统的构成 ANPR电子收费系统由前端采集系统和后台收费管理系统组成。前端采集系统包括视频摄像机（获取车辆图像）和照明灯（用于拍摄光源补充）以及相应的视频传输设备等，后台收费管理系统主要实现车辆通行费的管理等功能。3ANPR电子收费系统的工作原理整个ANPR电子收费系统的工作流程如下： 1）司机或者车主需要通过通行费支付系统预先预付交通道路通行费。预付手段有4种：路侧自助付费，因特网付费，手机付费和特约银行付费。在付费的同时需要将车主自己的车牌号码输入收费管理系统中，以便保存到相应的车牌数据库中。 2）当车辆行驶到收费区内及出入口时，ANPR电子收费系统就利用安装在收费区域边缘（出入口）的固定视频摄像机或移动视频摄像机拍摄通过的车辆照片并通过一定传输线路将视频流传至收费管理中心。 3）收费管理中心通过ANRP软件读取图像、识别车牌以及与数据库内交款车辆的车牌进行匹配，已付款的车辆进行核销，未付款的车辆会被记录下来，待工作人员核实之后，就会送出罚单。对于那些不能识别的车牌将有中心系统通过人工的办法来识别，对于那些未付款的车辆将会保存它进入收费区域配有时间、日期以及位置的图片，以便作为处罚的证据。 4. ANPR电子收费系统概况 车牌识别技术在道路收费的应用主要是辅助收费系统的执法功能，在半自动收费和电子收费中都是利用ANRP来实现逃费抓拍系统（Video Enforcement System，简称VES），而真正采用ANPR作为一种收费技术是2003年2月伦敦市政府在中心区实施道路拥挤收费。除伦敦外，采用相似技术的有安大407ETR（Expos Tol Route）电子收费系统以及英国Darford桥梁电子收费系统。随着车牌识别精度的改善，相信这种收费技术将会有越来越大的发展空间。同样，车牌识别技术在我国道路收费的应用主要是辅助收费系统的执法功能，在半自动收费和电子收费中都是利用ANRP来实现逃费抓拍系统。但是伦敦拥挤收费已经在我国引起强烈反响，我国的北京、上海、广州、南京、深圳等城市已经开展了城市拥挤收费的研究，相信ANPR电子收费技术在不久的将来会有助于解决中国城市拥挤问题。5. ANPR电子收费技术的优缺点 ANPR电子收费技术适用于预交费的情况，可实行对经过的车辆进行自动扣款收费，能实现不停车收费，它有如下特点： 1）ANPR收费系统只需在固定识别点安装摄像机（需要配套的支撑装置，如电线杆），路侧设施投人相对比较少，且ANPR收费技术不需要安装车载设备，减免了道路收费用户的投人； 2）通过ANPR软件识别车牌并能添加相应的时间、地点信息，便于按里程、滞留收费。同时存在以下弊端： 1）自动车牌识别技术虽然发展的时间比较长，但是识别率不高，是制约ANPR收费的关键所在；2）车牌识别技术的性能指标（识别率）不能满足道路收费的实际需要，系统的稳定性需要进一步提高； 3）运营管理复杂，不能完成现场扣款； 4）天气对摄像机捕获车辆图像的影响比较大； 5）ANPR收费系统功能扩展性是有限的。1.3.3 基于GPS的不停车收费技术1. 基于GPS的不停车收费技术的定义 它利用卫星定位系统（Global Positioning System，简称GPS）及全球移动通信系统（Global System for Mobile Communication，简称GSM），通过与车载装置的通信，进行不停车收费。2. 基于GPS的不停车收费技术的构成 该系统包括GPS接收装置,用于接收GPS数据, 定位车辆; 电子地图及数据库, 其中包含所有收费高速公路及其出口的空间位置信息及高速公路段落名称、段落长度、所属业主及收费标准等属性信息;缴费卡,可持卡缴费及传递数据。3. 工作原理基于卫星定位和无线接入技术的新一代收费系统，通过自动记录车辆行驶的位置和里程，综合考虑道路收费车辆参数和道路收费因素，自动计算车辆的通行费，由无线传输网络将数据传输到收费管理中心，根据相关公路收费政策，对车辆收取通行费。卫星定位收费系统包括智能车载收费设备（OBU）、稽查系统、管理中心3大部分组成，共同组成1个完整的卫星定位收费网络，如图1-2所示。 图1-2 卫星定位网络收费图该系统通过GPS接收卫星信号定位车辆当前位置,定位数据与电子地图结合应用路径辨识算法等判断车辆当前位置是否属于收费高速公路,如位于收费公路,记录虚拟入口时间、入口站号,接着等待出口,通过GPS定位当汽车离开公路时记录出口时间,出口站号,通过入口站号与出口站号到数据库中查询其它属性信息,并增加收费记录。费用支付可采用实时支付或先使用后支付两种方式。实时支付可用缴费卡与车载装置相连,当车辆驶离高速公路时,实时扣取缴费卡中的相应费用,余额不足限定值时提示充值;先使用后付费方式可定期到指定机构交纳费用。无论哪种收费方式均可在缴费时传递收费数据, 然后依据收费数据通过银行或指定收费机构对收缴费用进行划分。定期对收费数据备份和更新电子地图及数据库。4. 系统特点（1）适用性好基于GPS的不停车收费系统利用现有车道即可, 不需要对车道改进, 不受道路扩宽, 增加车道等的影响,为采用该收费方式的汽车专留一个车道, 未安装该种收费系统的车辆走人工收费车道, 随着该收费方式的普及, 逐渐取消所有人工收费车道。整个过程全部利用现有车道。另外由于该系统不需要在道路上建设收费设施, 因而不受道路施工的影响。当整个路网有新建高速公路时, 更新电子地图数据库即可。（2）可移植性强该收费系统在小范围内实验成功后可快速进行大规模推广, 有利于自动收费系统的快速发展。可首先对一个小行政区内车辆进行实验, 实验成功后, 大范围效仿相同方式进行即可。具有建设周期短, 硬件设施投入少, 易于大规模推广的特点。（3）可扩展性好该收费系统可与GPS卫星导航系统共同开发,并可进行功能扩展, 提供其它服务功能, 如车辆跟踪、信息查询、出行路线规划等。在日本超过60%的新车出厂时就已安装了车辆导航系统, 可以预见, 随着更多汽车企业的介入,导航产品市场将逐渐成熟, 导航产品前景广阔, 与GPS相关的其它服务功能正在悄然兴起, 基于GPS的收费系统与GPS服务产品共同开发将更能调动道路使用者的积极性。 5. 基于GPS的不停车电子收费技术的优缺点 基于GPS的不停车电子收费技术是利用GPS及GSM，通过与车载装 置OBU的通信，进行不停车收费。它的特点如下： 1）GPS电子收费系统可以将路旁设备降低到很少，无需龙门架，不会因为安装龙门架而影响市容美观和道路交通，更适合于城市道路有效空间的利用。同时降低了设备的投资，在地理位置受限制的地方，这种技术的优势更为明显。 2）提供灵活的收费区域定义和灵活的费用支付。DSRC收费技术在土地使用模式发生变化、收费区域需要改变时，克服传统基础设施改变存在比较大的困难。而GPS通过改变虚拟收费点的定义，非常容易实现。3）车载装置可由市场直接提供，GPRSGSM以及GPS技术规格己标准化，很多厂商具有生产制造能力，系统供应商较难垄断车载设备市场，故很容易跨平台或系统使用。 4）车载装置不仅是用作支付收费道路通行费的工具，它只要载人相关的应用软体，即可产生多用途，如：车载导航，车队管理，移动商务，车辆保全，交通信息等。 5）车载装置易扩展为移动商务基础平台的终端设备，并衍生其它商机。 6）具有长距离通信的优点，收费机制较不受空间限制，容易实时地在整个区域内按里程收费及实施匝道收费，具备收费策略调整弹性。 同时基于GPS的不停车收费技术存在以下不足： 1）用户的OBU成本高，如果由此造成用户的数量减少，可能影响系统的有效运行。2）车载电子地图的更新复杂。 3）如果系统设计得不合理，将会涉及到用户的隐私问题，这是很多国家暂时不考虑这种方式的一个原因。 4）在技术上，相对于DSRC电子收费技术要新。GPS技术是成熟的，但应用在不停车收费方面比较少。在城市道路中GPS定位信号容易受到建筑物的阻挡，影响车辆的定位，需要辅助系统支持。 5）GPS电子收费系统的运营需要配套法规、政策和严厉的惩罚制度，特别是针对那些“违规车辆”以及故意损坏车载装置的行为。 1.3.4 DSRC、ANPR和基于GPS的电子收费技术的性能比较及分析DSRC收费技术、ANPR收费技术及VPS收费技术，这3种电子收费技术都各有自己的优缺点。下面将从路侧设施成本、车载装置成本、技术成熟性、收费准确率、按车型收费、按里程或滞留收费、电磁干扰、景观影响、天气影响、外埠车辆收费、功能扩展、兼容性和可维护性等方面来比较，见表1-1。表 1-1 三种收费技术的性能比较特性指标DRSC收费技术ANPR收费技术GPS收费技术路侧设备成本高较低不需要车载装置成本较低（约500元）不需要高（约5000元）技术成熟性成熟比较成熟不成熟收费准确率高一般高按车型收费好差好按里程、滞留收费一般好好电磁干扰有无有景观影响有有无天气影响无严重无 运营管理简单复杂（不能完成现场扣款）简单外埠车辆收费方便不方便比较方便功能扩展宽窄宽兼容性较差一般好可维护性较差一般好DSRC电子收费技术和基于GPS的不停车收费技术主要应用于公路收费，而ANPR电子收费技术主要用于城市拥挤收费。由以上3种收费技术的原理及技术性能比较分析可知：1） ANPR电子收费技术不成熟、且车牌识别精度不高，是制约这种技术发展的最大障碍。 2） DSRC电子收费技术成熟、且广泛使用，但需要高额费用来建设、维护路边设备。 3） 基于GPS的不停车收费技术比较新、且车载装置投人较高，但其灵活的收费区域定义和费用支付方式及毋需建设龙门架等路边设备已受到全球的关注。 4）对一个较大范围的路网进行收费，基于GPS的不停车收费技术则可能较合适。以德国为例，其实施的货车收费系统将按其行驶里程与重量来计算应缴的道路通行费，由于其收费范围较大，收费点分布较广，采用DSRC电子收费技术的难度较大，费用也高，VlX3可能是较好的选择。对一条相对独立的收费公路，桥梁或隧道而言，DSRC电子收费技术可能是最佳选择，它用在类似新加坡的较小范围且单一、集中的市区道路收费也很合适。 5）由于收费分区与计价方式复杂，这类系统通常必须具备一套全国性或区域性的收费系统。再进一步设想，对于一个收费区的不同道路按不同道路的等级实施差别费率时，基于GPS的不停车收费技术则更具有优势。1.4本文研究内容及结构基于GPS的不停车收费技术代表着未来道路收费的发展方向，精确的地图匹配决定该收费系统能否实现成功收费。本文概述了各种常用的地图匹配算法，并就各种地图匹配算法进行系统的分析和对比，在此理论基础上，提出基于GPS的不停车收费系统的地图匹配算法，本文以自驾车从黄岛到济南为例，对收费用地图中的关键点即收费点进行定义，并提出了一种专门用于收费的地图匹配算法。具体内容如下：1. 基于GPS的不停车收费系统的原理和特点概述，并就各种ETC技术对比分析。2. 系统的提出各种地图地图匹配技术。3. 以黄岛前往济南为例，对基于GPS地图进行重新定义，并给出了新的地图匹配算法。4总结。青岛理工大学毕业设计（论文） 2 地图匹配技术 2 地图匹配技术2.1 地图匹配的基本原理将用导航定位方法得到的车辆位置或行驶轨迹与车载的电子地图道路数据相比较、匹配，从而找到车辆所在的道路，并且显示出车辆的实时位置的软件修正技术叫地图匹配（Map Matching，MM）。地图匹配过程可分为两个相对独立的过程:1）寻找车辆当前行驶的道路；2）将当前定位点匹配到车辆行驶的道路上。地图匹配的两个条件是高精度的数字地图和车辆在路网中行驶。如果条件成立，就可以把定位数据和车辆运行轨迹同数字化地图所提供的道路位置信息相比较，通过适当的匹配过程确定出车辆最可能的行驶路段以及车辆在该路段中的最大可能位置。反之，则地图匹配将产生错误的位置输出，并可能导致系统性能的严重下降。一般认为用于匹配的数字地图误差不应超过15m。由于陆地车辆在除了进入停车场等之外的决大多数时间都位于道路网络中，因此使用地图匹配技术的条件是满足的。在图2-1中，点A、B、C都是GPS观测点，显然这些观测点都没有准确的定位在道路上，地图匹配的任务就是通过一定的方法将这些点校正到道路的中心线上。现在地图匹配的算法有很多，但根据利用信息不同，大体上可以归结为两大类：1） 基于几何信息的地图匹配方法；2） 基于拓扑关系的地图匹配方法。基于几何信息的地图匹配方法有三类：点到点的匹配；点到线的匹配；线到线的匹配。前两种可视为搜索问题，最后一种可视为统计估计问题。图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。缺点在于匹配点少时匹配结果不准确。2）点到线段的匹配点到线段的匹配就是搜索所有可能的线段，以GPS观测点到线段距离为判断依据，观测点到条线段距离最近的那条线段作为匹配路段，观测点到匹配路段的投影点即为匹配点。这种方法同样比较简单，也很直观，但该方法得到的结果的不足在于匹配结果会出现来回摆动的情况，当GPS观测点距离多条路段的距离相等时就无法进行路段匹配了，匹配形式如图2-3所示。图2-3点到线段的匹配在图4-3中，P1、P2、P3、P4是连续的GPS观测点，它们的匹配结果是这样的：（P1B1），（P2A1），（P3A2或P3B2），（P4B3）。可以看出，匹配结果出现了在线段A、B间摇摆的情况，还有观测点P3无法确定匹配点。点到点的匹配、点到线的匹配都是仅仅利用了当前观测点位置进行匹配，没有充分利用历史和未来的观测点位置，有很大的局限性。3）线到线的匹配线到线的匹配就是将一系列GPS观测点拟合到道路网相应的路段中，拟合的标准就是观测点形成的折线到路段之间的距离，距离最短的为匹配路段。连线间的距离可以有很多种定义的方式，如定义两折线X、Y的距离为取它们间最近点的距离，即。匹配的示意图如图2-4（a）所示。图2-4 线到线的匹配（a）在图2-4（a）中，GPS观测点出现了一个离群点P，按照上述的匹配方法，GPS观测点被匹配到路段B上，这显然不合理，合理的匹配应该被匹配到线段A上。两折线间距离的定义还可以如下，按照这样距离计算方式同样也会出现像图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，这显然延迟太大，达不到实时校正车辆位置并正确显示的要求。上述的三种地图匹配方法相对来说都是计算简单，仅利用了数字地图的单一信息，不能保证任何时候都能得到正确的匹配结果，无法满足真正地图匹配的要求，因此根据这三种基本地图匹配方法衍生出来了许多比较实用的地图匹配算法。2.2 常用地图匹配算法地图匹配的常用算法有很多，比如最短距离算法、基于拓扑关系的算法、概率统计算法、模糊逻辑算法、相关性算法等等。下面对其中的几种进行简要分析。2.2.1 最短距离算法最短距离法是一种基础的匹配方法。该方法根据道路属性，预先设置一个匹配阈值，在数字地图数据库中的所有或部分路段中，计算当前获取的GPS数据与各道路路段之间的距离以及GPS数据在该道路路段上的最短距离点，将在阈值范围内各路段的匹配距离进行比较，得到一条距离最短的路段，则该道路为GPS点的匹配路段，该最短距离点为GPS点的匹配点。最短距离法简单易行，能在很大程度上消除地图匹配中各种误差产生的影响，但它没有考虑GPS数据接收中的各种情况及道路的地形特征，通常作为一种基本方法，与其他匹配方法结合来得到好的效果。2.2.2 概率统计算法基于概率统计的地图匹配同样是一种基础的匹配方法。概率统计算法的基本思想是根据GPS接收到的数据，首先设置一个置信区域，并从中提取用以匹配的道路位置信息，依据已有匹配结果的概率统计，经过比较判断，确定车辆在这一置信区域内的匹配路段。基于误差模型，根据接收的GPS定位数据建立缓冲区。按照统计理论，定位误差椭圆可推导如下: （2-1） （2-2） （2-3）其中，是椭圆长半轴取向与正北方向的夹角，a和b是误差椭圆的长、短轴，和分别是GPS东向和北向测量误差的标准差，是协方差，是单位权值的后验方差。通过改变的值来调整误差椭圆的大小，获得不同的可信度。在车辆导航系统中，利用GPS的接收模块的参数来定义误差椭圆。误差椭圆的定义如图2-5所示。图2-5 误差椭圆的定义该算法利用误差椭圆确定了误差区域，以便从数字地图数据库中提取候选路段的信息，从而减少候选路段的数目，缩短地图匹配的计算时间，但它没有历史信息进行有效利用，当道路较为密集的时候，可能会出现匹配点在几条路段间反复跳跃的情况，与基于拓扑关系的地图匹配方法相结合能得到较好的效果。2.2.3 基于拓扑关系的算法拓扑空间关系是一种对空间结构进行明确定义的数学方法。GIS中，常将空间事物抽象成点、线、面等几何要素，并在点、线、面之间建立拓扑关联关系。具有拓扑信息的矢量数据是网络分析必要的数据来源。数字地图数据包含：1）节点：表示空间对象所在的位置，或者线段的起始、终止点，它具有特定的拓扑性质。2）形状点：表示线、面经过的点，不具拓扑性质。3）线（弧线）：起始与终止点为节点、并且具有若干形状点的有序点集。4）面：由若干弧线相连的封闭曲线围成的区域称为面，面以弧线的形式表示，但通过代码与弧线区别，且其内部填充方式可以设置。建立道路网拓扑关系的一般步骤为：1）数据预处理：数据压缩（剔除冗余数据，提高计算速度）和自动断链（使整幅图图形无相交或自相交链）。2）结点匹配：建立点、弧段关联关系。3）追踪多边形：以左转算法或右转算法跟踪，生成多边形，建立多边形与弧段的关系。4）多边形嵌套关系的生成，建立多边形嵌套关系树，即找出多边形包含的“岛屿”，建立多边形与多边形之间的关系。5）具有嵌套关系多边形的关联弧段的左右面的编号调整及多边形内点自动生成。基于拓扑关系的匹配算法是在道路层网络拓扑关系的数据基础上进行的，是利用历史轨迹对地图数据库的道路信息进行实时的模式识别的一种方式。拓扑关系在电子地图中一般是指节点和路段之间的拓扑关系。在一段时间内，车辆行驶的区域是有限的，而且这个区域的道路也是有限的，因此在区域中建立的道路实体对也是有限的。电子地图足够精确并且具有路网拓扑完整性是地图匹配能够正常工作的前提。由于受车辆速度的限制，在一定的时间内，车辆只能驶经有限的路段上。如下图2-6所示，假设当前时刻车辆行驶在道路1上，由于速度等各种因素的存在，在下一时刻，车辆只可能出现在道路2、道路3或道路4上，即与道路1相连的道路链上，不可能直接跳到道路5或道路6上，如下图2-6所示。图2-6 道路拓扑关系基于拓扑关系的算法通过对前一次匹配结果和车辆前进方向的分析，利用道路层的网络拓扑关系，来确定当前车辆的匹配位置。但是，这种方法也仅利用了电子地图的单一信息，同时，其匹配效果有时也会受到拓扑关系质量的影响，空间拓扑范围越大，匹配效果就越差。2.3 地图匹配方法分析最短距离投影法逻辑简单、速度快、实时性好、所需内存空间少，但它没有考虑GPS数据接收中的各种情况及道路的地形特征，通常作为一种基本方法，与其他匹配方法结合能得到较好的效果。概率统计算法考虑了道路的地形特征，与其他方法结合能较好的解决匹配时道路中的合点与并行路段的问题，缺陷在于没有充分利用移动目标行驶轨迹前后的相关性。基于拓扑关系的算法对电子地图的精确度依赖性太高，而且该算法仅仅建立了结点与结点、结点与道路、道路与道路之间的拓扑关系。但在实际的道路通行过程中，还有很多的交通规则，这些规则限制了移动目标只能在某些道路上运动，而不能在受限制的道路上运动，这些交通规则我们统称为交通关系。两条道路如果仅仅是物理上连通是不够的，车辆是否能够从一条道路运动到另一条道路还要遵守交通规则。因此，要建立良好的道路拓扑关系，还应建立完整的交通关系以符合实际交通情况。基于以上这些情况，地图匹配算法的研究应该朝着多手段综合运用，相互补充、相互完善、精确化方向发展，对算法本身的准确性应该有一个检验机制，以最大程度保证算法的可靠性。2.4 地图匹配的应用在智能交通系统中，车辆控制、紧急救援、路径诱导、出行信息服务，公交调度等各种应用都需要精确地位置信息，地图匹配结合准确的空间地图数据对车辆位置信息进行校正，为各种智能化应用提供准确的位置信息，使得它们更加可靠。1. 在车辆定位导航系统中的应用地图匹配可以为车辆定位导航系统提供准确的位置信息，便于在地图上正确地显示车辆位置，向司机提供准确的行驶指令，并提供给司机从起点到目的地的最短路线，或最短行驶时间的路线，并为司机提供路线周围大型建筑物如银行、商店、加油站、旅馆等位置信息为用户的，还为用户提供道路的拥堵情况，方便用户及时调整路线，避免浪费时间和改善交通拥堵情况。2. 在车辆控制中的应用地图匹配由于可以提供比原始数据更为准确的位置信息，所以在车辆安全应用方面起到重要作用。例如，地图匹配可以应用于车辆巡航控制（Vehicle Cruise Control）系统中，具有地图匹配模块的系统可以根据电子地图所表现的路网中道路的曲率和拐点来自动的调整车辆的巡航速度。另外，精确的地图匹配还可以应用于车道保持（Lane Keeping）技术。虽然基于图像识别的车道保持技术已经相当成熟，但是由于恶劣天气对该系统的严重影响使得重新考虑一种新的方法成为一种必要。如果车辆定位精度能够达到10cm或者更小，那么当高精度的车道级别的地图出现时，车道保持以及其他安全技术将会变成可能。毫无疑问，没有地图匹配的协助，这将是个不可能完成的任务。3. 在道路收费上的应用在道路收费问题上，由于卫星定位与地图精度的精确度无法满足卫星收费的技术要求，因此需要优化的地图匹配方法来使之实现，这是本论文研究的重点。也是下文所要展开研究的问题。青岛理工大学毕业设计（论文） 3 基于GPS的不停车收费系统地图匹配方法 3 基于GPS的不停车收费系统地图匹配方法3.1基于GPS不停车收费地图匹配的作用基于GPS的不停车收费系统的匹配方法是通过对GPS采集的位置点信息与收费地图上的虚拟收费路段进行匹配，来判断当前车辆是否在收费路段上行驶，以判断是否对车辆进行收费，若需要进行收费，则记录收费信息和车辆的基本信息并发送到后台管理中心进行扣费处理。程序在接收到GPS定位数据信息后，先做译码处理，在提取位置、方向、速度及其他一些环境数据信息，最后将车辆位置信息和收费地图上路段通过一定的匹配方法进行精确地匹配，从而可以清晰区分收费路段和非收费路段，达到较准确地收费效果。GPS的定位精度、电子地图的绘制精度是影响GPS收费路段匹配准确性的主要因素。而只有在两者都达到一定精度条件下才能进行准确无误的匹配。但由于高速公路上行、下行车道间距离较小，通常只有5m左右，而目前GPS定位的精度仅在20m左右，此外受车载设备成本的限制，车载设备上不可能使用精度非常高的GPS接收机，而且也不可能使用精度非常高的电子地图。因此单纯依靠GPS定位和提高地图精度，很难区分上下行两个距离很近的点，因而对两条道路匹配混乱，导致收费路径的错误判断。要想实现定位信息与收费路段的精确匹配，首先要解决的就是地图匹配问题。3.2 基于GPS的收费地图的定义卫星收费电子地图不同于一般车载导航所用地图，这是一种专门用于道路收费的具有特定定义的地图，该地图包含收费路段的地理位置信息、形状数据信息、拓扑关系数据信息和属性信息等。对于收费用电子地图来说，基于我国高速公路大多采用封闭式收费系统的特点，即在收费公路所有出入口设立收费站，高速公路对外界呈“封闭状态”，车辆按进出收费站出入口进行收费，因此车载收费地图的定义需要围绕这些特点进行定义。收费电子地图根据存放位置的不同分为两部分：一是存储于车载单元中，对这部分的要求是尽可能的精简属性信息，以节约成本；二是存储在管理中心数据库中，此部分中包括了GPS定位收费所需要的详细全面的地理信息、包括路段编号、路段名称、路段长度、路段类型、限速、有节点编号、左节点编号、高速公路名称、高速公路公司代码、收费类型等。3.2.1道路收费地图收费关键点及收费路段定义本文所描述的车载收费地图由关键点和关键路段组成的，所谓关键点和关键路段是收费道路上的对道路走向和计费起到关键作用的点和路段。通过对现有高速公路布局和收费情况的分析，我们定义3种类型的关键点和3种类型的路段。入口点、出口点、经过点和入口路段、出口路段、经过路段。入口点是车辆经该点进入收费道路的点，和高速公路入口收费站对应；出口点是车辆经该点离开收费道路的点，和高速公路出口收费站对应；经过点，对于匝道收费站而言，是匝道和主路的交汇点，该点同时属于主路和匝道；由此定义入口点和经入口匝道与主路交汇的经过点组成的路段为入口路段；出口点和经出口匝道与主路交汇形成的经过点组成的路段为出口路段；经过点与经过点连接组成的路段为经过路段，多个相连接的经过路段组成主路路段。3.2.2 主线站出入口特殊处理主线收费站和匝道收费站不同，主线收费站出入口都是在主路上，为定义保持一致需要对主线收费站出入口做特殊处理，添加一个入口路段和出口路段。入口路段是从主线站入口开始沿道路方向在入口和下一个经过点的