（模式识别与智能系统专业论文）兼容路口校正的地图匹配算法研究.pdf

摘要 摘要 本论文研究的主要内容包括调研现阶段车辆导航系统及其主要的地图匹配 算法，根据g p s 定位系统误差和数字地图误差的特性分析，在借鉴已有研究成果 的基础上，设计了一种具有更高准确性和低运算量的实时地图匹配算法，并对数 字地图进行校正。 1 本论文设计了一种实时地图匹配算法 本文设计的多权值概率论实时地图匹配算法将匹配过程分为不同阶段，初始 阶段匹配、路口区域的匹配、车辆在匹配道路上位置的确定，该算法分别采用不 同措施提高匹配与显示准确度。其中在初始阶段，采用距离与车头向两个权值选 择置信区域里的候选道路：在路口区域，采用距离、车头向和轨迹走向三个权值 选择路口区域里的候选道路；在确定车辆在匹配道路上的位置时，根据前一个轨 迹拐弯点与路口节点的偏差，补偿当前时刻车辆沿道路方向上的匹配误差。 2 本文设计的实时地图匹配算法可以进行路口校正 在对数字地图具有自主知识产权的条件下，可以进行地图校正。本文通过路 口区域的多次行车轨迹，拟合车辆拐弯前后的g p s 采集数据得到轨迹拐弯点坐 标，在一定条件下校正矢量交通地图中的路口节点坐标。该功能在地图匹配的同 时完成，运算复杂度很小。为校正数字地图提供了一种简单可行的方法。 关键词：车辆导航系统地图匹配数字地图g p s 多权值 a b s t r a c t t h em a i nc o n t e n t so ft h i st h e s i si n c l u d et h er e s e a r c ho fv e h i c l en a v i g a t i o n s y s t e mm a pa n dt h em a i nm a p - m a t c h i n ga l g o r i t h ma tt h i ss t a g e t h er e s e a r c hr e s u l t s i nt h ed r a w i n gh a sb e e nb a s e do nt h eg p sp o s i t i o n i n gs y s t e me r r o ra n de r r o r c h a r a c t e r i s t i c so fd i g i t a lm a p s ah i g h e ra c c u r a c ya n dl o wc o m p u t a t i o n ，r e a l t i m e m a p - m a t c h i n ga l g o r i t h m si sd e s i g n e d ，a n dt h ed i g i t a lm a pc a nb ec o r r e t e d ( 1 ) i nt h ep a p e r , ar e a l - t i m em a p m a t c h i n ga l g o r i t h mi sd e s i g n e d t h em a pm a t c h i n gi sc l a s s i f e d i n t ot h r e ed i f f e r e n ts t a g e s ，t h ei n i t i a l s t a g eo f m a t c h i n g ，t h em a t c h i n gi ni n t e s e e t i o na n dd e t e r m i n i n gt h el o c a t i o no ft h ev e c h i l e o n t h er o a d f o re a c hs t a g e , t h ea l g o r i t h mi m p r o v et h em a t c h i n ga c c u r a c ya n dt h ed i s p l a y 、i t hd i f f e r e n tm e a s u r e s i nt h ei n i t i a ls t a g e ，b o t ht h ed i s t a n c ea n dt h eh e a d i n go ft h e v e h i c l ea r et a k e nt os e l e c tt h er i g h tr o a df o r mt h ec a n d i d a t er o a d s i nt h ej u n c t i o n a r e a ，d i s t a n c e ，h e a d i n ga n dt h et r a c eo fv e h i c l ea r et a k e nt os e l e c tt h er i g h tr o a di nt h e c a n d i d a t er o a d s i nd e t e r m i n gt h ev e h i c l e sl o c a t i o no nt h er o a d ，t h ed e v i a t i o nw h i t hi s c o n s t r u c t e db yl a s tj u n c t i o na n dt h et r u n i n go fv e h i c l et r a c ei st a k e nt oc o m p e n s a t et h e e r r o ra l o n gt h er o a d 。 ( 2 ) t h er e a l t i m em a pm a t c h i n ga l g o r i t h mc a nc a l i b r a t et h ec o o r d i n a t e so ft h e i n t e r s a c t i o n i fh a v i n gt h ei n d e p e n d e n ti n t e l l e c t u a lp r o p e r t yr i g h t so ft h ed i g i t a lm a p ，i ti sa b l e t oc o r r e c ti t i nt h i st h e s i s ，t h ec o o r d i n a t eo ft h ej u n c t i o nc a l lb eo b t a i n e df r o mf i t t i n g t h ed a t ec o l l e c t e db yg p sc o o r d i n a t e so ft h ev e h i c l eb e f o r ea n da f t e rt h ej u n c t i o n u n d e rc e r t a i nc o n d i t i o n s ，t h ed a t e sa r ec o l l e c t e df r o mm u l t i p l et r a c k si nt h ei n t e s e c t i o n r e g i o n t l l i s f u n c t i o ni sd o n ea tt h es a m et i m e 、i mt h em a pm a t c h i n g i t s c o m p u t a i t o n a lc o m p l e x i t yi ss m a l l i ti sas i m p l ea n df e a s i b l en e wm a h o df o rm a p c o r r e c t i o n k e yw o r d s ：v e h i c l en a v i g a t i o ns y s t e m ，g p s ，m a pm a t c h i n g ，d i g i t a lm a p ，m u l t i - w e i g h t i i i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：签字日期： 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 导师签名 签字日期 廿i 血掣 蒿 口 一 一 名 期 开 签 日 ，公 者 字 日 作 签 第1 章绪论 第1 章绪论 本章首先介绍论文研究的背景，并根据研究现状提出研究内容和预期成果， 本章最后是论文的结构安排。 1 1 研究背景 近年来，随着经济发展，城市车辆保有量大幅增加，道路网建设日益复杂化， 交通拥挤成了影响居民生活和经济建设的一个重要现象，由此造成的生命与财产 损失惊人。2 0 0 9 年，中国共发生交通事故2 3 8 3 5 1 起，死亡人数达6 7 7 5 9 ，受伤 人数达2 7 5 1 2 5 ，直接财产损失9 1 亿元，其中绝大部分交通事故发生在城市中。 而以北京为例，由交通拥堵造成的人均经济损失达3 3 5 6 元月，道路通畅时北京 居民平均每天花费在路途上的时间为4 0 1 分钟，而交通拥堵时这个时间则达到 了6 2 3 分钟。由于交通拥堵，中国每年损失的g d p 达5 8 。到2 0 1 5 年，全 国汽车保有量将达到9 0 0 0 万辆，城镇人口将突破8 亿，城市交通的矛盾会更加 突出。 智能交通系统( i t s ) 应运而生。智能交通系统就是以缓和道路堵塞和减少 交通事故，提高交通利用者的方便、舒适为目的，利用交通信息系统、通讯网络、 定位系统和智能化分析与选线的交通系统的总称。它通过传播实时的交通信息使 出行者对即将面对的交通环境有足够的了解，并据此作出正确选择；通过消除道 路堵塞等交通隐患，建设良好的交通管制系统，减轻对环境的污染；通过对智 能交叉路口和自动驾驶技术的开发，提高行车安全，减少行驶时间。美国从上世 纪6 0 年代起就开始研究智能交通系统( i t s ) ，迄今该国的交通业发展程度已是全 球领先，但正如前述，智能交通系统还有很大的发展空间。本论文研究的内容是 智能交通系统里面的一个部分：车辆导航和定位，重点研究地图匹配算法，这也 是i t s 中比较重要的部分之一。 车辆导航系统是智能交通系统( i t s ) 的技术基础，了解导航系统的发展进 程对车辆导航系统的开发和i t s 的建设有着重要的意义。2 0 世纪8 0 年代，第一 代导航系统进入市场，它将航位推算单元与1 张地图结合就能完成定位功能。自 从引进全球定位系统和数字化的地图后，导航系统的精确性得以保证，同时，随 着通信和计算机系统的更新，路线的计算速率也大大提高，目前，导航系统还在 不断发展。我国的车辆导航系统的研究开发工作起步不久，但发展迅速，特别是 g p s 定位技术在智能交通领域的大力推广应用，随着经济的发展，居民生活水平 的提高，车载g p s 导航系统几乎出现在每一辆新型家用轿车里面，作为物美价 廉的位置传感器，g p s 迅速占领中国的个人导航服务和车辆安全监控等行业，成 第j 章绪论 为移动终端最常见的定位设备的核心器件。 1 2 研究现状 到目前为止，车辆导航系统可大致分为四代。 第一代导航系统于2 0 世纪8 0 年代进入市场，它就是结合航位推算单元与印 刷地图来实现定位功能的，因而导航系统定位精度不太准确。 第二代导航系统出现于2 0 世纪8 0 年代后期，该系统以航位推算为基础并且 采用装有地图数据库的c d r o m ，将大量的地图储存在一个c d r o m 盘片上。 在第二代的后期产品中，还出现了地图匹配技术。航位推算系统的主要缺点是一 旦前面点的推算误差没有补偿，则误差会一直累积，后续点的匹配精度将会不断 降低，另外c d r o m 盘片容量较小。 第三代导航系统出现在海湾战争( 1 9 9 3 ) 后，当时g p s 技术已广泛应用。 g p s 大大提高了导航系统的定位精确性。另外，航位推算系统( d r s ) 也发生了 进步，采用了陀螺仪和车轮传感器( a b s 中的) ，效果得到改进。这一代导航系 统最新的产品是p o i ( p o i n to f i n t e m e t ) ，p o i 是由导航系统数据库支持的一大特 色功能，即系统可以在用户要求下显示有关目的地的详细信息，如当地旅馆、博 物馆、警察局信息等。 第四代导航系统产品在1 9 9 7 ：午前已开始使用。最大的变化就是动态线路诱 导( d y n a m i cr o u t eg u i d a n c e ) 系统的产生，它是车载导航系统中的重要组成部 分。系统由d v d r o m 取代c d r o m ，容量更大，所有这些最新信息储存于p o i 中，结合存储于d v d r o m 中数字地图数据库技术，在车辆上就可以选择最佳 的行驶路线。为了实现这一目标，我们可收集当时的相关道路情况后发送给正在 路上行驶的车辆，如交通事故报告、交通流情况等。 当今g p s 民用定位精度已经可以达到1 4 米，该精度基本可以满足民用定位 用途。而在短时间内g p s 系统必将稳定存在一段时间。在这种情况下，如何利 用现有设备尽量提高导航精度，有两个有力的武器：高效的地图匹配算法和高精 度的数字地图。 ( 1 ) 高效的地图匹配算法。现有的主要地图匹配算法可以分为四类：几何匹配、 拓扑匹配、概率论匹配、其他高级匹配。从最早的研究至今，地图匹配算法的研 究历史已有二十多年。随着研究的一步步深入，匹配效果也越来越好。但是在某 些场景，如初始匹配阶段、交叉口处、环路、高架桥等特殊地点，这些地点地理 条件复杂，是现在所有算法出现误匹配的主要原因，即车辆匹配到错误路径或者 出现跳变或位置往复等现象，这不仅使用户无法准确判断自己的位置，也影响了 交通诱导与路径规划等服务功能的实现。另外，现有很多成熟的地图匹配算法已 经能够基本解决车在哪条道路上行驶，但车在该道路上的具体位置这些算法大都 2 第l 章绪论 采用直接垂直投影，虽然车辆行驶道路是对的，但是通过分析g p s 的误差特性， 可以发现车辆在道路上的具体位置却存在着不小的误差，这对后续匹配会造成不 利的影响，这种方法不能满足某些更高精度要求的应用领域。 ( 2 ) 高精度的数字地图。数字地图是导航系统的基础，也是广大用户能够见到 的最直观匹配结果的显示平台。从早期的印刷地图，到现在广泛使用的数字地图， 地图的精度在不断提高，地图的信息量也在不断增大。但是在当今道路网络复杂 的城市地区，现有的数字地图还或多或少的存在着拓扑误差和绝对误差。精度还 有待进一步提高。而如果地图精度不够高，则必然会给地图匹配算法带来更大的 运算代价，甚至造成误匹配，特别是在交叉口或者密集路网区域。但是在当前导 航系统研究中很少有人同时考虑提高地图匹配算法的效率和数字地图精度，这是 由于大部分地图匹配算法研究者并没有自主知识产权的数字地图，他们往往在自 己制作的一个小范围的路网上进行网络仿真或者采用其他机构制作的专用数字 地图进行匹配实验。对地图匹配算法投入的研究往往忽视了数字地图对匹配效果 的影响，如果数字地图本身就存在精度问题或者在小区或其他一些较偏僻地区数 字地图的道路精度达不到使用者的要求时，就必须将两者有机的结合起来才能有 利于从整体把握导航系统。 1 3 研究内容 从上面的介绍可以看出地图匹配算法和数字地图在车辆导航系统中的重要 性，同时也能了解当前地图匹配算法存在的一些不足之处。随着交通复杂程度的 增加，需要新的更准确更高效的算法来满足导航系统的需求。 在本文的研究中，首先会了解g p s 定位的原理，分析导航系统中的误差特性， 然后调研现有的主要地图匹配算法，总结其优缺点，为本文提出的算法做好理论 基础。然后设计一种计算代价较小而又具有较高准确性的多权值概率论实时地图 匹配算法，分三个阶段：初始阶段、路口区域、确定车辆在匹配道路上的位置， 详细阐述各阶段的匹配思想。最后介绍本文地图匹配算法中集成的路口校正功 能，通过路口区域的多条车辆行驶轨迹，在一定条件下对路口节点坐标进行校正。 所有算法都在仿真平台中检验其效果，其中o p s 数据源来自于实车测试，在合 肥市内的一些道路上测得。 1 4 本文安排 论文第2 章介绍车辆导航系统的误差分析，包括g p s 系统简介与误差分析， 以及数字地图及其误差分析。第3 章分类介绍已提出的主要地图匹配算法，并总 结现有地图匹配算法有待解决的几个问题。第4 章介绍本文提出的多权值概率论 第l 章绪论 实时地图匹配算法并仿真检验算法效果。第5 章介绍路口校正的思想和过程。第 6 章对整个研究进行总结，并对今后的工作进行展望。 4 第2 章车辆导航系统的误差分析 第2 章车辆导航系统的误差分析 车辆导航系统在智能交通系统( i t s ) 中占有重要地位。精确的定位是车辆 导航系统的关键，根据定位方式的不同，有多种车辆定位系统。其中主要的定位 方式有美国的g p s ，俄罗斯的g l o n a s s 和欧洲的伽利略系统。本章重点介绍g p s 定位系统，并分析g p s 定位和数字地图的误差特性，为本文后续设计地图匹配 算法提供相关理论基础。 2 1g p s 系统简介 由于g p s 定位精度较高，信号稳定，接收机价格低廉，现在投入使用的车载 定位系统以g p s 为主。 2 1 1 全球定位系统g p s 简介 全球定位系统( g l o b a lp o s i t i o n i n gs y s t e m ，通常简称g p s ) ，又称全球卫星定 位系统，是一个中距离圆型轨道卫星导航系统。它可以为地球表面绝大部分地区 ( 9 8 ) 提供准确的定位、测速和高精度的时间标准。系统由美国国防部研制和 维护，可满足位于全球任何地方或近地空间的军事用户连续精确的确定三维位 置、三维运动和时间的需要。 2 1 2 全球定位系统g p s 的组成 g p s 空间星座部分：g p s 的空间部分是由2 l 颗工作卫星组成，它位于距地表 2 02 0 0 k m 的上空，均匀分布在6 个轨道面上( 每个轨道面4 颗) ，轨道倾角为5 5 0 。 此外，还有3 颗有源备份卫星在轨运行。卫星的分布使得在全球任何地方、任何 时间都可观测到4 颗以上的卫星，并能在卫星中预存的导航信息。g p s 的卫星因 为大气摩擦等问题，随着时间的推移，导航精度会逐渐降低。 地面监控系统：地面控制系统由监测站( m o n i t o rs t a t i o n ) 、主控制站( m a s t e r m o n i t o rs t a t i o n ) 、地面天线( g r o u n da n t e n n a ) 所组成，主控制站位于美国科罗拉多 州春田市( c o l o r a d os p r i n g ) 。地面控制站负责收集由卫星传回之讯息，并计算卫星 星历、相对距离，大气校正等数据。 用户设备部分用户设备部分即g p s 信号接收机。其主要功能是能够捕获到 按一定卫星截止角所选择的待测卫星，并跟踪这些卫星的运行。当接收机捕获到 跟踪的卫星信号后，就可测量出接收天线至卫星的伪距离和距离的变化率，解调 出卫星轨道参数等数据。根据这些数据，接收机中的微处理计算机就可按定位解 算方法进行定位计算，计算出用户所在地理位置的经纬度、高度、速度、时间等 第2 章车辆导航系统的误差分析 信息。接收机硬件和机内软件以及g p s 数据的后处理软件包构成完整的g p s 用 户设备。g p s 接收机的结构分为天线单元和接收单元两部分。接收机一般采用 机内和机外两种直流电源。设置机内电源的目的在于更换外电源时不中断连续观 测。在用机外电源时机内电池自动充电。关机后，机内电池为r a m 存储器供电， 以防止数据丢失。目前各种类型的接受机体积越来越小，重量越来越轻，便于野 外观测使用。其次则为使用者接收器，现有单频与双频两种，但由于价格因素，一般 使用者所购买的多为单频接收器。 2 1 3g p s 系统的功能 g p s 系统已经深入到经济生活的各个方面，其主要用途有：精确定时，广泛 应用在天文台、通信系统基站、电力系统、电视台中等。工程施工，道路、桥梁、 隧道、高层建筑的施工中大量采用g p s 设备进行工程测量。勘探测绘，野外勘 探及城区规划中都有用到。导航，广泛应用于制导、车辆、船舶、飞机、星际和 个人导航。定位。应用于车辆防盗系统，手机及p d a 中的防盗和定位，儿童老 人等特殊人群的随身定位等。授时，用于给电视发射站、电信基站等提供精准的 同步时钟源。 2 1 4g p s 定位的基本原理 卫皇2 卫皇3 4 挑铂 【蕊一妒+ 锄y 丹瓴曲邓锋瞻体毫d l 【国一x ) - 冲魄y ) 脚临矽】1 珥峨r 惋滂d 2 【( x 3 一x ) 2 + 奶一y 玲慨妒】1 砷嗨饯净岛 【l ：x 4 - x ) 2 - t 1 ) 是扩展系数，这个扩展系数是用 来补偿和轨道不稳、大气传输、多路径以及接收端噪声有关的误差。在z h a o ( 1 9 9 7 ) 的论文里，赢取30 3 。如图23 所示，实际采集数据也大致印证了这 一论断。 图2 3 一天之i 自g p s 单点定位，间隔1 秒 误差区域之所以是一个椭圆，是由于接收机对经度和纬度定位的精确度 不同而造成的，这就对地图匹配算法提出了一个要求：在利用距离搜索当前 g p s 点附近的道路时，搜索半径最小应该是误差椭圆半长轴的两倍，因为同 第2 章车辆导航系统的误差分析 时也要确保数字地图中的道路出现最大误差的情况下能搜到道路。本文算法 就采用这种思想。 ( 2 ) g p s 误差具有慢漂移特性。由于卫星位置的变化g p s 单点定位所得数 据是随时间变化的，误差是时变的，但是短时间内连续两次测量的序列很接近 用不同接收机得到的数据之间的误差也很小，远小于误差本身。不管是经度还是 纬度其误差都是平滑的，很少有突变。如图2 4 所示，取1 0 0 0 个单点g p s 测 量点的纵坐标，即纬度信息( 弧度表示) ，从中可以看出随时间变化，这些点的 纬度值是连续变化的，几乎没有突变。在我们的试验中，连续两点的偏差差值很 少超过2 m ( 9 5 ) 。 圈24 连续1 0 0 0 个g p s 单点定位的经度和纬度随变化曲线，间隔1 秒 ( 3 ) 数据分析结果显示，在大部分情况下，相邻两观测点的距离基本等于实 际两点的距离。在9 5 的情况下，两者之间的差值小于l m 。 通过图25 可以看出上述两种现象与地图匹配的联系。图中n i n 2 是当前车辆 正在行驶的道路，v c 和v p 是当前和前一时刻车辆在该道路上的真实位置，g c 和 g p 为当前和前一时刻g p s 测量点的位置，e c 和e p 为当前和前一时刻的误差，d g 为当前和前一时刻g p s 测量点之间的距离，d v 为当前和前一时刻车辆的真实距 离。在通常g p s 操作条件下，上述两条实验中发现的现象可以归纳为e c e p d g d v 。即由点v c 、v p 、g c 和g p 组成的四边形近似为平行四边形。这一结论非 第2 章车辆导航系统的误差分析 常重要，在之后的第四章的地图匹配算法中要用到。 卜。g 弩c n 芒n i i 萨击_ n 2 由平行四边形的性质可知如果已知平行四边形其中三个点( 按顺序) ，则第 四个点也就确定了。比如知道了前一个观测点和匹配点，又测得了现在的观测点， 那么可以根据这三个点得到平行四边形的第四个点，则路上距离这个点最近的点 可以被当做当前点的实际位置，本文将这种方法叫做平行四边形匹配方法。显而 易见，该方法可以明显减小沿道路方向上的匹配误差。 另外一个可由上述分析得到的结论是在通常的g p s 操作条件下，两连续测量 点的连线方向与车辆正在行驶的道路方向基本一致，g p s 测量数据里德车头向与 车辆正在行驶的道路方向也基本一致。因此车辆的车头向和两连续测量点的连线 方向可以拿来判断当前行驶道路，也可以用来校正任何积累的地图匹配误差，并 且可以做到实时协调车辆的真实位置和测量位置。如图2 6 所示，通过测量点 p 1 、p 2 和p 3 的车头向或者连线方向的变化值就可以知道车辆刚刚转了一个9 0 度的弯，那么p 2 测量点的真实车辆位置就应该在b 处，而p 3 点的真实车辆位置 则可以由上述平行四边形方法得到。 d c p 1 2p 3p 4 产- op l 一 ， b p o al 图2 6 与g p s 方向信息有关的误差特性 e 第2 章车辆导航系统的误差分析 2 3 数字地图及其误差分析 数字地图是导航系统的基础，没有数字地图的显示，再高的定位精度对使用 者来说也无任何意义。只有可视化的在高精度的数字地图中显示出车辆的轨迹或 位置，才能完成车辆导航、路径规划以及动态发布交通状况等i t s 中的重要功能。 然而，现有的地图匹配算法很少关注数字地图本身的影响，或者不能将地图 匹配与数字地图校正结合起来。这主要是因为缺乏对数字地图的自主知识产权。 现在的大部分实用的数字地图都是一些专门的地图制作公司在做，人们如有需要 用到则直接向这些地图制作商们购买，然而，这样做有两个缺点：1 当我们需要 一些小区或者比较偏远地方的数字地图时，这些现有的地图往往不够细致到这些 地方，或者在某些地区现有的数字地图存在较大的偏差，而这必将影响地图匹配 算法的效果。2 向专门的数字地图制造商们订购地图往往价格不菲。 所以，下面本文将介绍数字地图对地图匹配算法的影响。 2 3 1 数字地图的误差及其对地图匹配算法的影响 按照数字地图误差的种类不同，( 刘志德，2 0 0 8 ) 将其分为两类：拓扑误差 和地理误差。 ( 1 ) 拓扑误差 在制作过程中，由于人为原因，造成数字地图中道路的拓扑关系与真实道路 发生差异，典型的有：1 道路冗余，2 道路缺失，3 误增的独立道路，4 交叉口处 道路不相交，5 多余的道路节点。如图2 7 中所示，其中虚线为实际道路，实线 为制作的数字地图中的道路。 l ： 5 l ： 厅、 l ：，一、，。冬： 、1 1 一 n ；( 2 ，_ k ， 图2 7 一些典型的数字地图拓扑误差 ( 2 ) 地理误差 在制作过程中，由于人为原因，道路的拓扑关系并没发生错误，而是道路的 一些参数与实际道路有差异，典型的有：1 角度与实际道路有差异，2 长度，3 道路节点的位置。如图2 8 所示，其中虚线为实际道路，实线为制作的数字地图 中的道路。 1 2 第2 章车辆导航系统的误差分析 、 乓子 ( 3 、 ， 、 ) 图2 8 一些典型的数字地图地理误差 一般来说，数字地图中存在地理误差并不一定就有拓扑误差，但是较大的地 理误差也会导致拓扑误差。由于测量设备的精度有限，在制作数字地图的过程中， 地理误差是不可能消除的，但是可以保证不出现拓扑关系的错误。在地图匹配过 程中，拓扑误差对匹配效果影响交大，有可能造成误匹配或较大的显示误差。而 地理误差会增加匹配算法的复杂度，比如迫使匹配算法的搜索半径增大，另外， 交大的地理误差也有可能造成误匹配，特别是在路网密集区域。对于这两类误差， 要尽可能的减小地理误差，并消灭拓扑误差。 2 3 1 路网模型对地图匹配算法的影响 相对于可以量化的数字地图误差，路网模型对地图匹配算法的影响更容易被 忽略。 当前被广泛使用的一种路网模型就是点弧式模型。该模型用线段来表示道 路，节点是线段的端点。但这种模型存在以下几个影响匹配效果的方面。 ( 1 ) 用没有宽度的线段代表有宽度的实际道路。点弧式模型往往使用没有宽 度的线段来代表有宽度的道路，这在一定程度上会影响匹配效果，因为先在城市 道路中的干道宽度可达3 0 m 左右，而g p s 误差半径约为1 5 m ，当用一条直线来 代表双向道路时显示不直观，而用两条直线代表双向道路则g p s 采集点与道路 的距离信息往往会带来误匹配。 ( 2 ) 用线段代表存在弧度的实际道路。大部分道路是平直的，但是有些道路 存在弧度，而点弧式模型用分段线段来代替弧线，这样肯定存在误差，而对弧 线分段过多又会增加存储空间和弧段区域的匹配复杂度。 ( 3 ) 用点代表有实际面积的路1 2 1 。实际路口区域面积往往很大，存在多种转 弯情况，而点弧式模型用一个点来代表路口。这样做压缩了车辆的转弯信息， 从而增加了路口区域的误匹配概率。 ( 4 ) 用二维地图代表三维路网。实际的城市道路存在高架桥、立交桥以及城 第2 章车辆导航系统的误差分析 市地面的高低起伏，而点弧式路网模型往往采用平面地图代表实际的空间路网。 这样做忽略了g p s 采集点里的高度信息，在高架桥或立交桥区域，地图匹配算 法往往会发生误匹配。 2 4 本章小结 本章主要讲述车辆导航系统中的误差分析。首先对g p s 系统进行简介，包括 其组成、功能、原理等，然后分析g p s 系统的误差种类及其对地图匹配的影响。 接着介绍了数字地图及其误差分析，阐述了路网模型对地图匹配算法的影响。本 章为后面本文设计地图匹配算法提供了理论基础。 1 4 第3 章现有的地图匹配算法介绍 第3 章现有的地图匹配算法介绍 地图匹配算法将位置信息和特定的道路网络数据联系在一起，来决定当前车 辆正在行驶的正确道路和车辆在该道路上的具体位置。地图匹配算法是智能交通 系统中车辆导航中的重要组成部分。近年来，在世界范围内不少研究机构和个人 已经研究了一些成熟的地图匹配算法。本章将分类介绍这些主要的算法，并分析 器优缺点，然后总结现有算法的一些主要局限性，为本论文第四章设计一种新算 法做理论准备。 3 1 现有的主要地图匹配算法 按照使用的主要方法不同，本论文将现有的地图匹配算法分为四类：几何匹 配、拓扑匹配、概率论匹配、其他高级匹配。 3 1 1 几何匹配 最基本的也是最早被使用的一种匹配算法是几何匹配。它只考虑g p s 采集点 和某些道路网络元素的距离，比如到道路或者节点的距离，而不考虑道路之间的 拓扑关系。 最早被使用的几何匹配算法是一种简单的寻找算法，被称作点点匹配：把 g p s 采集点匹配到离它最近的节点，节点包括路口和弧段折点，如图3 1 所示。 该算法最早出现在b e m s t e i na n dk o r n h a u s e r ( 1 9 9 6 ) 的论文中。 ，d? ，工 图3 1 点- 点匹配不恿图 显而易见，这种算法的问题是：如果道路网的节点越多，则匹配的精确性越 高，而道路网的节点越少，匹配误差越大，特别是当在一条较长道路上没有折点 时，则所有的点都会被匹配到路口节点处。 另外一种几何匹配算法是点弧匹配，在年b e r n s t e i n 和k o m h a u s e r 的论文和 w h i t ee ta l ( 2 0 0 0 ) 年的论文中都有提及。其基本思想是将导航系统所得的采集点 第3 章现有的地图匹配算法介绍 匹配到离它最近的道路弧段上，道路弧段被近似为分段的线段，离采集点最近的 线段就被选为匹配道路，如图3 2 所示。 o - - o - - o - 一一- 4 ； 6 6占占6 s6s 6 6 图3 2 点- 弧匹配不意图 虽然这种方法比点点匹配的效果更好，但是也存在一些问题，比如当进入道 路网络比较密集的市区时，算法的稳定性不足，另外由于导航和数字地图的误差 原因，距离最近的道路有时并不是当前行驶的正确道路，特别是在道路交叉口附 近，只用距离判断行驶道路往往会出错。 另外一种几何匹配算法叫做弧弧匹配。算法将车辆轨迹与道路进行比较。 b e m s t e i n 和k o r n h a u s e r 和w h i t e 以及p h u y a l ( 2 0 0 2 ) 年分别在他们的论文里都有提 到。该方法首先使用点点匹配找出候选道路节点，然后将车辆轨迹与连接在这 个道路节点上的所有分段线性弧段进行比较，平均距离最短者为匹配道路。 弧弧匹配方法在一定程度上考虑了先前点的信息，即历史数据，但是它对测 量异常值非常敏感，另外该算法使用了点点匹配，也将其缺点吸收了进来。 总的来说，所有的几何匹配算法的主要缺点是它们都忽略了g p s 测量点的关 联性和道路网络的拓扑联通性，因此，在匹配的过程中很可能会出现车辆在道路 间来回摆动。并且因为判断候选道路的标准往往比较单一( 主要是距离) ，造成 了几何匹配算法对道路网络的精确性要求非常高，对测量异常值很敏感。关于算 法的效率，n i e l s e ne ta l ( 2 0 0 4 ) 年证明只有点点匹配的速度足够快，但是他在哥 本哈根做的一个包含3 0 0 0 段旅程涉及3 0 0 0 0 0 个道路弧段的实验表明，误匹配率 到达了惊人的3 0 ，这难以在实际生活中应用。尽管如此，几何匹配的一些思想 还是可以应用到其他的地图匹配算法当中。 3 1 2 拓扑匹配 拓扑匹配算法不仅考虑g p s 采集点和道路网络元素的距离，而且将历史g p s 采集点的信息以及道路网络的拓扑连通性纳入考虑范围。 大部分拓扑匹配算法分两步进行工作，首先通过几何匹配找到初始节点或道 路，然后，从一束候选道路集中选择一条道路来扩展车辆行进的路径。通常这束 1 6 第3 章现有的地图匹配算法介绍 候选道路集由前一条已匹配的道路和后继道路组成。 o r e e n f e l d ( 2 0 0 2 ) 设计了一种带权的拓扑匹配算法，该算法基于对路网的拓 扑分析，但是只利用了定位信息中的坐标值，没有使用任何得自于g p s 采集数 据的车头向或速度信息。 这个方法对异常值非常敏感，因为异常值会导致轨迹在计算轨迹走向时的错 误。 m e n g ( 2 0 0 6 ) 在分析了道路网络的拓扑性质后，也提出了一种简单的拓扑匹 配算法。该算法基于车辆轨迹与道路的拓扑特性( 比如道路的转弯，道路曲率和 道路连通性) 的比较。算法进行一系列的条件测试去减少不满足门限要求的候选 道路，这些门限通过现场试验获得，利用g p s d r 得到的路网数据信息来实验该 算法，并通过空间路网信息，包括交叉口的转弯限制去改进算法。 该算法的主要缺点就是在车辆运行到交叉口时，如果连接在该交叉口上的道 路方向不同时，算法效果不好，会出现匹配的摆动，这时算法就变成了一个后向 的处理过程而非实时的。 q u d d u s ( 2 0 0 3 ) 提出了一种基于路网几何特性和得到的导航数据间多种相似 规则的增强型拓扑匹配算法。算法的目标是用尽量少的数据输入让算法变得简单 快捷。他的算法也利用了o r e e n f e l d ( 2 0 0 2 ) 提出的相似性规则。为了改善算法 的效果，通过引入一些附加的规则和参数( 比如速度，车头向等) ，相似性权值 表被增强。不同的权值因子被用来控制这些权值的贡献大小。 q u d d u s ( 2 0 0 3 ) 的算法效果很好，但是也有一些局限性，比如算法本身要确定 很多阈值及因子，并且这些数值因城市不同而不同，所以在实际应用当中需要花 费很多时间确定这些参数，并且算法势必对有些规则有遗漏，特别是在交叉口处， 比如轨迹走向与道路方向夹角的变化量等，而如果考虑的规则过多，又会反过来 影响到算法的速度。 3 i 3 概率论匹配 概率论匹配算法采用置信区域去筛选当前匹配道路。即当前采集点一定范围 内的道路为匹配道路，而如果置信区域内有多条道路，则再采用其他规则去确定 正确匹配道路，置信区域往往是椭圆或矩形。 这种技术最早被h o n e y ( 1 9 8 9 ) 用来将从d r 传感器得到的数据匹配到地图 上。z h a o ( 1 9 9 7 ) 将这种方法应用于g p s 数据的匹配中，并且他提出置信区域 的范围由g p s 定位的误差方差来决定，若置信区域内有多条道路，再采用诸如 距离、车头向、连通性等规则来进一步判断匹配道路。 z h a o 的算法只是停留在概念阶段，他并没有用实验去检验算法效果，并且还 有一些规则他没有考虑到，比如车辆的速度信息、车辆到下一个道路节点的距离 1 7 第3 章现有的地图匹配算法介绍 信息等，而这些信息可以更进一步的改进匹配效果。 c h u n ga n ds h a l a b y ( 2 0 0 5 ) 提出将连接在前一条已匹配道路上的所有道路纳 入候选道路集，而g r e e n f e l d 在2 0 0 2 年的论文中将连接在所有后续道路的后续道 路也纳入到候选道路集中，这样做都是为了增大算法的容错性，减小误匹配概率， 但候选道路集过于臃肿时算法的速度必然会降低。 q c h i e n g ( 2 0 0 4 ) 提出了一种增强的概率论匹配算法。在他的算法中，置信 区域仅在靠近路口附近时才运用，车辆在道路上运行而距离路口还有一段路程时 不用置信区域。 这样是为了减小运算量，因为如果每一个点都运用置信区域去判断匹配道路 的话会有一系列步骤要做，显然会增大运算量，并且如果两条路离得很近的话， 一直运用置信区域有可能因为测量误差而造成误匹配，以至于出现车辆在两条路 上摆动的现象。本文的算法也采用了这一思想，但是这样做也给初始匹配和路口 处匹配提出了更高的要求，因为一旦经过这些位置后发生了误匹配那么错误将一 直积累下去。 出于减小误匹配的目的，m a g e dj a b b o u r ( 2 0 0 8 ) 和n a d i e ns c h u e s s l e r ( 2 0 0 9 ) 等人分别提出了一种利用了多假设思想的地图匹配的算法，其突出特点就是对每 个点在确定匹配道路时，利用置信区域选出多个候选值并存储起来，每一条候选 路径都有一个得分，在g p s 序列结束时才选出得分最高的那条道路作为匹配道 路。 这种算法的主要优点就是在某个点发生误匹配时，将其对后续点的影响大大 降低。但是这也增加了算法的复杂度，特别是当g p s 测量点中的奇异值并不多 时这样做就得不偿失。 3 1 4 其他高级匹配方法 高级的地图匹配算法采用更为复杂的理论基础，比如卡尔曼滤波或扩展的卡 尔曼滤波、d s 理论、状态空间模型、粒子滤波器、交互式多模型、模糊逻辑模 型、贝叶斯推理等。下面介绍几种典型的高级匹配算法。 k i m ( 2 0 0 0 ) 的算法，应用于i t s 的整合导航系统。包含g p s 、d r 、地图匹 配算法。首先，一个简单的点弧匹配被用来识别正确的路，然后正交投影到该 路上，横向误差被显著减小，纵向误差依然存在，然后利用扩展的卡尔曼滤波器 重新估计车辆位置减小纵向误差。该滤波器的性能依赖于空间路网数据的质量， 特别是路弧的表示方法。另外，开始的点弧匹配可以通过考虑多种参数( 比如 车头向、速度、路网的拓扑分析等) 来改进，以降低后续误差。( 徐浩，2 0 0 7 ) 也使用了卡尔曼滤波算法来减小沿道路方向上的匹配误差率。 y a n g ( 2 0 0 3 ) 提出了一种使用模糊推理系统的基于d s 推理的改进的地图匹 1 8 第3 章现有的地图匹配算法介绍 配算法。算法的输入被一个卡尔曼滤波器平滑。g p s 待匹配点和周围路段的距离 通过使用点弧匹配概念获取，通过计算出的距离给路段赋予权值。结果显示算 法得到了9 6 的道路正确匹配率。但是，这个并不都是在市区的情况，因为点 弧匹配方法并没有充分考虑路网的拓扑结构。 s y e da n dc a n n o n ( 2 0 0 4 ) 的算法，描述了一个基于模糊逻辑模型的地图匹配 算法。包括两个子算法：( 1 ) 第一个点的匹配；( 2 ) 跟踪。在第一个子算法中，一 个模糊推理系统被用来寻找初始位置的正确匹配道路。识别出初始道路并将车定 位在上面后，进入第二个子算法。另外一个模糊推理系统被用来识别后续待匹配 点是否能被匹配到第一个点的匹配道路上。算法输入是距离、方向和车在路上的 行驶路程。算法大概需要3 0 s 去完成第一步的匹配，这对一些在路上的导航来说 时间太长了，在这个时间内甚至可以在路网密集地区行驶几个交叉口。另外，在 确定车辆在已找出的匹配道路上的具体位置时，算法并没有考虑和传感器以及路 网数据有关的误差信息。 总的来说，这些高级算法确实对匹配的精确度有不同程度的提高，但是其算 法的复杂度也有增加，对于那些比如智能手机、p d a 、车载导航仪等运算能力并 不强的设备来说，运算的效果可能因为运算能力的不足而打降低，有时会出现延 迟现象。 3 2 现有地图匹配算法有待解决的几个问题 ( 1 ) 初始地图匹配过程的问题 大部分地图匹配算法的初始匹配过程是：寻找落在初始g p s 点的一个置信区 域里的所有节点，以连接在这些节点上的所有路为候选路径。但有一种情况要处 理，如图3 3 所示，如图3 3 所示，若p 点为初始g p s 采集点。置信区域里没有 节点，即g p s 点在一条长路的中间位置时( 这种情况普遍存在) ，置信区域里面 只有道路没有节点，这时算法就要退化为再遍历所有节点，增加了复杂度。另外， 判断一个点是否在一个有倾角的椭圆内计算量比较大，因为事先还要去计算与接 收机性能有关的椭圆参数( 如半长轴、倾角等) 。 ( 2 ) 在交叉口的匹配问题 在路口处的匹配一直是地图匹配算法的一个难点，例如图3 4 所示的y 型交 叉口处，p ，、尸2 都能正确的匹配到道路a b 上，但是乃点到道路b c 和b d 的距 离相等，且乃点车辆的车头向为9 0 度( 与正北方向的顺时针夹角) ，这时如果 仅用与道路的距离和车头向与道路的方向相似性这两个规则去判断匹配道路时， 易出现误差。这类路口常见