（交通信息工程及控制专业论文）列车监控系统中地图匹配算法的研究.pdf

北京交通大学硕士学位论文 摘要 摘要 智能交通系统是当前交通运输系统的发展趋势，车辆位置又是智能交 通系统的重要信息，地图匹配则是获取精确位置信息的关键。 论文首先介绍了地图匹配概念及其基本原理，讨论了目前存在的并普 遍应用的各种算法的特点并进行了对比。 在此基础上，针对铁路线路的一维特性以及调车站场平行股道多、拓 扑复杂等特点，对专用的地图模型以及地图匹配算法进行了研究。基于简 单化，实用化，层次化的思想提出了适用于铁路列车监控系统的拓扑模型 和轨道模型，并通过对曲线近似误差的数学分析，保证了地图模型的精度。 系统首次采用载波相位实时差分技术对铁路线路进行测量，生成专用地 图，并通过多传感器数据融合以及使用地图匹配输出校j 下传感器的方法提 高了系统定位精度。系统采用基于状态实时切换的地图匹配算法，既保证 了简单情况下的实时性，又保证了复杂情况下的准确性。软件系统采用面 向对象设计，在增加系统鲁棒性的同时，降低了系统的维护开销。 此后，结合青藏线卫星定位及信息传输系统研究项目以及智能化调车 系统项目，对系统中主要算法的性能指标进行了评价和分析，证明了系统 设计和算法设计的合理性和可行性。 最后，论文针对系统的不足提出了三点改进建议。 关键词：全球卫星定位系统，地理信息系统，地图匹配，地图模型 北京交通大学硕士学位论文 a b s r i r a ( 了 a b s t r a c t t 1 l ed e v e i o p m e n to fi n t e l l i g e n t i l a n s p o n a t i o ns y s t e m ( i t s ) i so n eo ft h e m o s tu i g e n tt h i n g si nt h ef i e l do ft r a n s p o r t a t i o n ，a n dv e h i c l el o c a t i o ni so n eo f t h em o s ti m p o n a n ti n f o r m a t i o no fl t s w h a t sm o r e ，m 印- m a t c h i n g ( m m ) j s t h ep r i m a r yw a yf o r0 b t a i n j n ga c c u r a t el o c a t i o ni n f o n n a t i o n f i r s to fa l l ，t h i sp 印e ri n t r o d u c e sb a s i cc o c e p ta n dt h e o r yo fm m t 1 l e n t h ec h a r a c t e r i s t i c so fe x i s t i n gm ma l g o r j t h m sc u r r e n t l yw i d e l yu s e da r el i s t e d a n dc o m p a r e d b a s e do nt h e s e ，c o n c e m i n gt h ei n h e r i t e do n e - d i m e n s i o n a lt r a i nt r a c k p r o f i l ea n dc o m p l e xt 叩o l o g ya n da b u n d a n c eo fp a r a l l e ln - a c k si nm a r s h a l l i n g y a r d s ，t h ea u t h o ri n v e s t i g a t e st h ed e d i c a t e dm a pm o d e l sa i l dm ma l g o f i t h m s c o n s i d e r i n gs i m p l e n e s s ，p r a c t i c a b i l i t ya n dh i b e f a r c hy ，t h i sp a p e fp r e s e n t st h e t o p o l o g j c a i t r a c km o d e l t h a tf j t st h er e q u i r e m e n t so ft r a i nm o n i t o f i n gs y s t e m ， a n dg u a r a n t e e si t sa c c u r a c yb ym a t h e m a t i c a la n a l y s i so ft h ee r f o rp f o d u c e db y a p p m x i m a t i o no fc u e s f o rt h ef j s tt j m e ，r e a lt i m e 砌n e m a t j c ( r t k ) i s u t i l i z e dt om e a s u f et h et r a c k sf b rb u i l d i n gt h ed e d i c a t e dm a p a n dt h e a c c u r a c yo fl o c a t i o n i se n h 柚c e d b y d a t af u s j o no fm u l t i - s e n s o r sa n d c a l i b r a t i o no fs e n s o r su s i n gt h eo u t p u to fm mm o d u l e t h ep m p o s e dm m a l g o r i t h ms w i t c h e si nn l n t i m ec o r r e l a t i n gt ot h eo p e r a t i n gs t a t e sa n d ，h e n c e ， c a ng a i nn o to n l yt h ea b i l “yo fr e a l t i m em a t c h j n gb u ta l s ot h ea c c u r a c yo f r e s u l t si ns i m p l ea n dc o m p l i c a t e ds i t u a t i o n sr e s p e c t i v e l y n l es o f t w a r ei s d e s i g n e dt o t a l l yb a s e do no b j e c to r i e n t e da c h i t e c t u r e ，w h i c ha s s u r e st h i s s y s t e m sr o b u s t n e s sa n d ，m e a n w h i l e ，l e s se x p e n s eo fm a i n t e n a n c e t l l ea u t h o ra l s om a k e st h ea n a l y s i sa n de v a l u a t i o na b o u tt h ep e r f o 珊锄c e o fk e ya l g o r i t h m su s e d t 1 1 e e v a l u a t i o nw o r ki sc o n d u c t e dw i t ht h e s et w o p r o j e c t s ，o n eo fw h i c hi si n v e s t i g a t i o no nq i n 曲a i - t i b e ts a t e l l i t el d c a t i o na i l d i n f o 咖a t j o nt h n s m j s s i o ns y s t e m ，出eo t h e ro n ej sr e s e a r c ha n dd e v e 】o p m e n t ( r & d ) o fi n t e l l i g e n t i z e dm a f s h a l l i n gy a r d 1 1 h i sp a p e ra l s od e m o n s t r a t e st h e f e a s i b i l i l y 柚dl o g i c a lr a t i o n a l i t yo fs y s t e mf r a m e w o r ka n dt h ed e s i g no f c o r r e l a t i v ea i g o r i t h m s l a s tb u tn o t i h el e a s t ，t h r e es u g g e s t i o n sa r ef i n a l l yp o s e d k e y w o r d s ： g l o b a l p o s i t j o n i n gs y s t e m ( g p s ) ，g e o 伊a p h i c a li n f 0 皿a t i o n s y s t e m ( g l s ) ，m a p m a t c h i n g ( m m ) ，m a pm o d e l 韭室壅望查兰塑：! 兰垡堡茎 釜= 兰 第一章概述 1 1 选题背景卜【1 0 】 智能交通系统是将先进的信息技术、计算机技术、数据通信技术、传 感器技术、电子控制技术、自动控制技术、运筹学、人工智能等学科成果 综合运用于交通运输、服务控制和车辆制造，加强了车辆、道路和使用者 之间的联系，从而形成一种高效的综合交通系统。智能交通系统的研究已 走过3 0 多年的历程，美国、欧洲和日本已成为世界智能交通系统的三大 基地。目前，另外一些国家和地区的智能交通系统研究也已经具备相当规 模，如澳大利亚、韩国、新加坡、香港等。可以说，全球正在形成一个新 的智能交通系统产业，难以数计的大小项目正在开发中，发展规模和速度 惊人，以“保障安全、提高效率、改善环境、节约能源”为目标的智能交 通系统概念正在逐步形成。9 0 年代初，我国学者开始关注国际上智能交 通系统的发展，1 9 9 5 年以后，我国关于智能交通系统的研究、试验和国 际交流同益频繁。交通部已将智能交通系统列入中长期规划。同时，许多 单位、高校和科研院所等也都分别成立了智能交通系统工程研究中心，专 门进行智能交通系统研究。 智能交通系统是一种综合高效的交通系统。从发展的眼光来看，智能 交通系统能够综合利用现有的道路设施，减少交通拥挤，加强对车辆的集 中管理和调度，为驾驶员提供足够的交通、公安、娱乐等信息，实现人、 车、路三者的密切结合和统一，从而可以极大提高交通运输效率，保障交 通安全，增强行车的舒适性，改善环保质量，提高能源利用率。为此，智 能交通系统已引起各国的重视，北美、欧洲以及亚洲中经济发达，交通拥 挤的国家，都将其列入国家计划并投入巨资，以推动其发展。该系统还将 有许多的内容需要进一步的丰富和完善。随着科学技术的不断发展，人们 坚信未来的智能交通系统将会更加科学有效。 在l t s 研究领域，以实现道路的“信息化”、“智能化”为目标的交通 信息系统的丌发与应用以欧洲、美国、日本为中心迅速展开。同时众多其 它国家和地区也纷纷参与，并投入力量开展研究活动，目前交通信息采集 系统已成为世界规模的热点研究课题。 欧洲的研究项目主要有d r i v e r ( d e d i c a l e dr o a di n f r a s t n i c t u r ef o r v 曲i c l es a f e t yi ne u r o p e ) 、p r o m e t h e u s ( p m 斟锄m ef o rae u r o p e a n 1 1 r a f f i cw j t hh i 曲e s te f f i c i e n c ya n du n p r e c e d e n t e ds a f c t y ) 、t r a f f i c - m a s t e r 、 第1 页 苎皇奎塑查兰堡主兰丝堡兰 笙二量 e u r o s c o u t 和l d c o m o t i v 。而最早的智能交通系统是美国的智能车路系 统。其中较典型的有a d w 州c e ( a d v a n c e dd r i v e ra n dv c h j c l ea d v i s o r y n a v i 叠a t i o nc o n c e p t ) 和t r a v t e k 项目。日本的v l c s ( v e h i c l el n f o 皿a t i o n a n dc o m m u n i c a t i o ns v s t e m ) 项目，也颇具参考价值。 国外的l t s 技术发展迅速，目前已经具有相当多的系统应用。然而， 国内的交通系统的建设和相关软硬件的开发还比较薄弱，尤其是理论算法 的研究。但拥有很大的发展空间，有利于向更加深入和广泛的领域发展。 北京市作为i t s 示范城市，同时进行北京市交通综合信息平台、智能交通 管理、先进公交系统的示范工程建设，为i t s 和g p s 这些先进技术的应 用提供了良好的发展空间。 1 2 智能交通系统中地图匹配技术的发展趋势 在智能交通系统中，位置信息是关键。通常采用的定位技术有三种： 独立定位技术、卫星定位技术和地面无线电定位技术。其中，无线导航技 术依赖于外界设备，其定位精度或受无线网覆盖面积的限制，或受定位信 号精确度的影响( 如g p s ) ，d r 技术的精确度则受到方向传感器以及测 速脉冲设备精度的限制，而且存在累计误差，随着车辆形式距离的增加， 误差会随之增大。 地图匹配( m a pm a t c h i n g m m ) 技术恰恰克服了以上两种定位技术的 局限性。浚技术以模式识别理论为依据，基于“车辆始终行驶在道路上” 与“电子地图数据是准确的”的假设，通过找到车辆所在的道路，计算出 准确的车辆位置，从而达到校正定位过程产生的误差的目的。 地图匹配算法与其它几种定位技术配合使用，能够极大的提高车辆定 位精度，减小定位误差。可以说地图匹配算法的效果直接关系到车辆定位 的精度，地图匹配技术是决定导航产品最终性能的关键。 由于上述原因，目前广泛应用的定位系统多采用航位推算法和无线导 航配合地图匹配算法的综合定位方法。 然而，随着地图匹配技术的发展，地图匹配技术已经不局限于在精确 定位系统中进行应用，在车辆导航，飞行器导航，室内机器人导航，交通 流分析，甚至地图图像识别中都有着广泛的应用。而且系统应用也逐渐从 数据采集、数据预处理、多传感器数据融合到地图匹配的常见形式的开环 系统向以地图匹配结果作为反馈的闭环系统转变。 总而言之，地图匹配是精确定位强有力的手段。 第2 贞 北京交通大学硕上学位论文 第一章 1 3 论文结构 本论文共分六章，下面分别陈述各章主要内容。 第一章主要是概述部分。对本论文的选题背景以及相关内容进行了简 单介绍，并概要叙述本文结构框架。 第二章将介绍地图匹配算法的基本原理。讨论了地图匹配这一利用已 有数据来提高车辆监控系统定位精度的软件纠错技术，并阐述了其突出的 实际价值。之后，本章就目前比较常用的地图匹配算法进行了评述，并给 出了初步比较。 第三章是介绍了系统涉及的主要技术。包括全球定位系统( g l o b a l p o s j t i o n i n gs y s t e m g p s ) 技术；地理信息系统( g e o g r a p h i c a li n f o r m a t i o n s v s t e m g i s ) 技术：移动检测技术( p r o b ev e h i d e p v ) ；面向对象体系 结构( o b i e c to r i e n t e dm c h i t e c t u r e 0 0 a ) 以及组件技术。 第四章详细描述了系统设计与实现。本章将介绍在g i s 平台基础上 搭建的监控系统结构，并且详细的阐述系统涉及的技术细节，包括地图匹 配数据库的建立，坐标转换公式，卡尔曼滤波算法。之后，在理论研究的 基础上，提出了一种“铁路专用的地图匹配算法”模型。 第五章是运行结果评价及结论。主要包括青藏线数据的处理以及三家 店车站调车作业数据的匹配等。在理论基础和实验结果上，配以详实的数 据和图表来说明分析误差的来源和算法的效果。 第六章部分就上述内容进行总结之后，提出了系统在安全和技术支持 方面的改进，并就系统的应用前景做出了展望。 第3 页 北京交通人学硕士学位论文 第二章 第二章地图匹配基本原理 在本章中，首先介绍了地图匹配算法的基本概念，并以此为基础讨论 了这一利用已有空间地图数据来提高定位精度的技术。之后，本章就目前 比较常用的地图匹配算法进行了评述，并给出了初步比较。最后给出了地 图匹配的几种典型应用，并以此为据阐述了其实际应用价值。 2 1 地图匹配概念及主要算法 2 1 1 基本概念 一般来讲，比较当前车辆的坐标和数字地图的过程叫作地图匹配 【1 0 】。陔算法以模式识别理论为基础，以某个车辆位置点或某段车行轨迹 曲线作为待匹配样本，根据一定规则在空间地图数据库中选取一定量的点 或曲线作为匹配模板库，通过样本与模板库中的实体进行比较，选择特征 相似度最高的一对样本实体对作为匹配结果。最后根据确定的地形实体， 来定位行驶中的车辆，并减小定位误差。可以简单来说，地图匹配是利用 某一地区的已知信息来提高定位估算精度并以此来减小定位误差的一种 方法f 1 1 】。 地图匹配算法在一般应具备以下过程： 通过预处理提取出待匹配样本的位置或形状特征； 根据适当规则，计算待匹配样本和所有实体问的匹配相似度； 选取相似度最高的样本一实体对，作为匹配结果进行定位。 常规的地图匹配基本思想是把车辆路线同接近以前匹配点的已知道 路相比较，形状与当前路线和先前匹配路线相似的道路被选为车辆行驶的 道路。常规的地图匹配算法有半确定性算法和概率统计算法等。 倘若根据匹配样本的类型，地图匹配算法主要可以分为位置点匹配和 轨迹曲线匹配两种。其中，位置点匹配算法逻辑简单，实时性好，但在道 路密集、道路形状复杂、交叉路口和立交桥等情况下，匹配准确率较低。 相对来说，轨迹曲线匹配算法匹配准确率高，但算法复杂、计算量大，很 难满足车辆定位的实时性要求。 地图匹配可采用集中的、分级的或者混合式的方法同定位传感器协同 工作。在集中方式下，多传感器数据以集成、融合的方式与地图进行匹配； 在分散方式下，每个传感器和传感器组以独立的形式与地图进行匹配；在 鹅4 页 j ! 室奎望查堂堡主堂焦堡兰 笙三里 混合方式下，集中方式和分布方式可顺序的应用以获得较好的匹配结果。 关于这一技术有许多变种，但是基本原理相同，就是利用数字地图滤掉车 辆传感器的误差，并确定最佳位置。 基于g p s 和多传感器的地图匹配算法有几个简单变种： 将g p s 作为匹配输出的正确性检查依据 将g p s 作为传感器之一 将g p s 作为唯一的传感器 d r 和g p s 是车辆导航系统所普遍采用的两种定位技术【1 2 】。g p s 具 有实时性强，精确度高，成本较低等特点，在卫星信号被阻挡或形成多径 反射后其可用性大打折扣，在城市交通中应用的时候尤为明显。而d r 系 统作为一种相对定位技术，其累积误差的产生也成为一种困扰。因此将上 述两种技术结合的想法应运而生。如此一来，系统可以利用g p s 信号校 正d r 传感器的误差，还可以使系统从不可预期的定位失效状态返回；同 时，d r 也为校正g p s 定位误差提供了反馈。毫无疑问，将原始定位数据 与地图信息融合的地图匹配算法有助于提高接收机输出的精度。 最终地图匹配所要输出的结果包括 9 1 ： 当前位置 当前运行方向 当前速度 当前经过的路段( 节点) 2 1 2 主要算法 目前地图匹配有各种算法，他们分别适用用于不同的情况。下面分别 就比几种算法做一讨论，并且在之后做出简单的比较。 l 、位置点匹配算法 由于位置点匹配算法逻辑简单，实时性好，实现极其容易，因此在简 单应用中被广泛采用。但是在道路密集、道路形状复杂、交叉路口和立交 桥等情况下，匹配准确率较低。因此，为弥补上述不足，学者们根据相应 的改进衍生出一系列的算法。 i 简单点匹配算法 图2 一l 表示了简单点匹配算法的基本原理【1 3 】。 图中点p 为待匹配的g p s 定位点，l 1 、l 2 表示g p s 点附近的道路。 第5 页 北京交通大学硕j 二学位论文 第二章 p l l l 图2 1 位置点匹配算法原理图 在位置点匹配算法中，把待匹配的g p s 定位点向附近所有道路做投 影，计算g p s 点与各道路间的投影距离墨，及车辆行驶方向与道路间的夹 角b 。选出r ，b 值小于给定阈值的所有道路并根据式2 1 计算各候选道 路的距离度量值 t ，4 + 口+ q 式2 1 其中，分别是投影线段长度和方向夹角的权重。在所有候选道 路中选择距离度量值最小的作为匹配道路，认为车辆正在该道路上行驶， 并且将车辆在匹配道路上的投影点作为车辆的当前位置。 i i 基于概率统计的匹配算法 车辆定位信息反映出来的车辆轨迹通常不能与实际道路状况完全吻 合。其原因是多方面的，有卫星信号经过多径反射形成的误差，有通信信 道噪声，有传感器的温度漂移，有预处理滤波器造成的误差以及来自地图 数字化方面的误差等。这就给地图匹配造成困难。 例如，在车辆行驶在复杂的路网中的时候，特别有许多平行的道路的 时候，严格区分车辆坐在的道路非常困难的。所以系统只能得出类似“车 辆很可能在某一道路上”的结论。系统只有参考足够多的历史轨迹， 才能确定车辆的具体位置。要解决这种“模糊性”，在地图匹配过程中需 要处理定性术语( 如：“可能性”) 的技术【1 5 】。 模糊逻辑己被证明时处理涉及定性术语、模糊语言和人工干预任务的 有效方法。利用模糊集合，具有模糊概念的术语能够用数学方法来定义。 专家知识和经验可表达成规则集。此外，通过适当的推理过程可做出结论， 该推理过程类似于人的推理能力。由于地图匹配是涉及模糊度的定性决策 过程，所以研制基于模糊逻辑地图匹配算法是有意义的。 第6 页 些室奎望生兰婴主兰壁堡兰 墨三垦 该算法首先要确定定位误差区域，然后从中选取提取用以进行匹配的 实体信息，最后再根据上述的点匹配算法进行，最后得出匹配结果。通常 情况下误差区域必须以一定的概率包含车辆的实际位置。由于g p s 定位 精度不受累积误差影响，因此，在组合导航系统中通常采用g p s 定位模 型参数来定义误差椭圆。 g p s 定位一旦失效，必须用d r 定位的误差参数来代替g p s 参数， 以保证系统运行的连续性。由于d r 具有误差累积效应，因此，在按d r 定位的误差参数定义误差椭圆后，还应乘上适当的扩展因子来扩大误差区 域，以反映误差累积对定位精度的影响【1 6 l 。 i i i 基于d s 证据理论的匹配算法l l 】【1 7 】 该算法与一般的概率理论的区别主要在于，该算法允许将证据与对已 知不确定性的集合的操作数相结合，所以能被应用于基于规则的逻辑推理 系统。这里仅作简单介绍，详细内容可以参考【1 8 】。 根据g p s 给出的用户坐标及经、纬度方向的定位误差( d o p 值) ，得 到置信椭圆a b c d 。如图2 2 所示，假设车辆沿着方向t 行驶，p 是根据 定位信息得到的当前车辆位置。 首先计算出位置点与周围道路的距离， 即在式2 1 中令珊，s 1 ，。；0 ，然后根据式 2 2 得到各条道路的可靠性m ，之后按照式 2 3 进行结果融合，根据融合后每条匹配道 路的证据支撑大小判定车辆在哪条路上行 驶： 其中 0 4 矗1 4 0 ，+ ) o 5 ，d 【3 0 ，4 0 ) o 6 ，d 【2 0 ，3 0 ) o 7 ，d 【1 5 ，2 0 ) o 悬d 【1 0 ，1 5 ) 0 9 ，d 【5 ，l o ) 0 9 5 ，d 【0 5 ) 帆删：驾岩 第7 页 图2 2 置信椭圆示意幽 式2 2 式2 3 北京交通大学硕上学位论文 第一二章 q 2 荟? t 。；：即，) 算法以g p s 信号和已有的数字地图为导航依据。 基于拓扑关系的匹配算法 首先介绍“道路实体对”的概念f 1 6 】： 图2 3 一个简化的单路线道路网络 电子地图足够精确并且具有路网拓扑完整性是地图匹配能够正常工 作的前提。由于受车辆速度的限制，因此在一定的时间内，车辆只能驶经 有限的路段。假设当前车辆行驶在道路1 上，并且在一分钟内车辆驶经的 路段小于或等于2 ，那么在当前时刻往后一分钟的时l 、日j 内，车辆只可能出 现图2 3 中的道路对r 12 ) 、( 13 ) 或者( 14 ) 上。 在该算法之中，以道路实体对为单元进行处理。图2 。3 中的道路实体 对可以用链表表示，例如( 12 ) 一( 13 ) 一( 14 ) 一( 23 ) ( 24 ) 一( 34 ) 一( 36 ) ( 45 ) 。由于在一定时间内，车辆行驶的区域是有限的，而且固定大小的区 域的道路数目也是有限的，因此可以建立的道路实体对也是有限的。该算 法减少了在复杂路网情况下的计算量。 2 、曲线匹配算法 c e 图2 4 曲线匹配算法示意 曲线匹配算法根据车辆行驶轨迹的曲线特性选择关键节点，出选取的 节点表示曲线，按照各种具体算法的曲线相似度比较方法，在候选道路中 第8 页 ! ! 塞銮望盔兰堡主堂竺堡塞塑三皇 选出与车辆行驶轨迹最为相似的路段作为匹配结果道路。最后基于测量曲 线与匹配结果道路之间的距离确定最佳轨迹f 1 9 1 。 1 简单线匹配 根据定位信息的统计特性可知，一般情况下，定位信息流中的有效信 息多于无效信息。因此，可以根据“少数服从多数”原则确定曲线相似 性，即在一段连续的位置点中进行抽样，用这些点来表示曲线，如果抽样 点集中多数点与某条道路匹配，则整个抽样点集中的所有点都将匹配到该 道路。 为了表示曲线相似程度，必须建立一种指标体系。该算法采用抽样点 集中点与曲线问距离的方差来表示曲线相似度。如图2 5 所示，显然点集 与道路l 1 的距离的方差比l 2 小，所以该行驶轨迹与l 1 匹配。如图2 6 所示，该算法同样适用于城市道路，并且逻辑简单，计算量小，精度较高。 l 2 鼍爱。窘 l l o p j n p l 图2 5 一般道路简单线匹配示意 图2 6 交叉路口简单线匹配示意 i i 基于r v m ( r 山t a t i o n a iv a r i a t i o nm e t r i c ) 的线匹配算法【2 0 】【2 l 】 地图匹配算法主要解决两个问题： 一、确定在候选道路中哪一条是车辆实际所行驶在的道路； 二、在道路上车辆实际处在的准确位置。 曲线匹配算法的关键在于如何快速直接有效的找出匹配结果道路，也 就是说，如何衡量两条曲线的相似性，从而在候选道路中选取出一条与车 辆行驶轨迹最相似的道路作为匹配结果。这里介绍的算法采用了一种新的 厦量方法，即r v m ( r o t a t i o n a lv a r i a t i o nm e t r i c ) 。该算法不需要密集的计 算( c o m p u t a t i o n a l l yn o n i n t e n s i v e ) 。 众所周知，平移和旋转时仅有的两种保持形状和大小的几何变换( 当 然，翻转也是一种，但不是这里研究的重点) 。那么如果一条曲线是另一 条曲线经过平移或旋转而成的，就说明两条曲线是一样的。就像下面将要 介绍的那样，计算两条曲线的r v m 值可以确定一条曲线是否近似由另一 条平移或旋转形成，即两条曲线有多么相似。换言之，r v m 提供了一种 评价曲线相似度的表达式。 第9 页 兰塞奎望叁兰堡主兰堡堡塞 兰三里 如图2 7 所示，不妨设a 为参照曲线，在盐线a 和b 上分别假设一 个起点，从起点开始，沿相同方向每个一个给定的相等跃度作切向量，通 过对产生的两个切向量组的关系比较，可以确定曲线a 和b 的关系。 不失一般性，定义为使b 组向量与a 组向量相同需要旋转的角度为 一对向量的夹角。定义逆时针向为正方向，顺时针方向为复方向。该角度 可以通过式2 4 进行计算。 o s 一1 嘲s _ 1 嘲 一“ 二- p 、：7 ， j 、- f 。 i 8 、。 滁 二上， 一； “、卜 一- ：j ， j ： 、h ： j 7 ，- * 0 式2 4 1 黑黧三、等 图2 - 9 曲线a 、b 不同 旋转和或平移后相同 一一。 幽2 - 8 相同曲线的r v m图2 1 0 不同曲线的r v m 由于图2 7 种任意一对切向量的角度都相等，所以曲线b 经过平移和 旋转后与a 相同。角度与向量的关系如图2 8 所示。 9 的方差就是曲线相似性的定量描述，这就是r v c ( r o t a t i o nv a r i a t i o n c o e f f j c i e n c t ) 的定义。如果两条曲线的r v c 等于0 ，就表示两条曲线经 过平移或旋转之后重合，或者两条曲线相同。如果r v c 具有很大的数值， 表示两条曲线具有不同的形状，如图2 9 所示，此时曲线a 与b 的r v m 如图2 1 0 所示。如果两条曲线大小不同，可以在其中一条进行缩放后再 进行比较。 篇l o 贞 一 事 苎塞奎望查兰堡兰堡堡苎 塑三兰 r v m 提出了一种方便快捷的衡量两条曲线相似度的方法，为曲线匹 配算法提供了强有力的保障。 1 1 1 基于i m t m ( i t e 髓t i v em u l t i r e s o l u t i o n1 h n dm e t r i c ) 的算法【2 0 】 首先介绍一下“线简化”( 1 i n es j m p l j f i c a t i o n ) 。线简化是解析一条复杂 曲线的总体趋势的过程。可 以把线简化看作是一种几何 低通滤波器。 如图2 1 1 所示，虽然两 条曲线的形状似乎相差很 大，但是经过适度的一般化 ( 线简化) 后，可以看到两 条曲线的总体趋势是非常相 近的，即两条曲线是匹配的。图2 1 1 车辆轨迹和道路德一般化示意图 线简化的算法有很多，最常用的是d o u 醇a s 和p e u c k e r 提出的算法。 该算法用容忍带宽表示蓝线一般化的程 ，= o 、 度，大带宽表示高度一般化，反之亦然。 “三 零带宽表示不变。i 选择道路集 i m t m 使用线简化和继承方法来降l 塑竿模j 垦曼： 篓兰苎苎璧掣恐! 篓粤蝥：凭曼：篓叁竺釜【r ；濂磊车轺i 酝i 丽有在；蘸嚣j 匹配算法直接比较车辆轨迹和模板库中l 赣磊谣￥酾蒜i 斟二蕊石| 所有的道路。为减少计算量，l m t m 采用 l ，_ 二一二二 二二 以下几个步骤：i 比较一般化后的车辆轨迹和n 条道路 1 通过高度线简化，比较车辆 ： 根磊磊函果函赢去丽 轨迹和模板库中所有道路的【相似的道路，改变n 值为新的模扳i 总体趋势，在模板库中剔除- - 竺的兰堂哩! ：窒墨! 粤 最不可能的道路，产生一个 ， ，移鹾套、申、 道路子集。l q j 是否仅剩余： 2 降低容忍带宽，重复上述步、i 罄警。 骤，产生一个更小的子集。r _ _ 将此萄函画1 3 重复上述迭代，直到最后只 匹配结果 剩下一条道路，则该道路就+ j 、 是匹配结果。 一 i m t m 算法流程如图2 1 2 所示。 图2 1 2l m l m 算法的流程 由于在算法的丌始，当模板库中的候选道路非常多的时候，采用了高 度线简化，所以降低了计算复杂度。这种有简入繁的过程，极大的节省了 第l 1 页 韭室奎望查里堡：! 兰竺笙：塞； 塑三兰 匹配时间，提高了算法性能。 3 、其他匹配算法 i 基于车辆行驶状态的匹配算法 实验证明，要达到相同的匹配效果的算法难度与车辆行驶的实际状况 有很大关系。因此如果能够根据不同的车辆行驶状态采用有针对性的不同 匹配算法不但有利于提高算法效率，还能达到更好的匹配效果。【1 4 】中介 绍了一种基于车辆行驶状态的算法。该算法将车辆行驶时的匹配定位处理 分成了五种不同状态，并针对每种状态各自的特点和定位要求，采取了不同 的处理方法。这五种情况包括：道路搜索( s e a t c h i n gr o a d ) 正常行驶 ( r u n n i n go nr o a d ) 转弯( ，r u r n i n g ) g p s 信号接收不佳( i n v a l i ds j 舻a 1 ) 停车 或低速滑行( l o ws p e e dr u n n i n g ) 【1 4 】。图2 1 3 表示了五种处理状态间的转 换关系。 其中，算法针对“道路搜索”、“转弯处理”这两处极易出现误匹配的 情况，采取了匹配可信度参数控制匹配处理的方法。匹配可信度参数是评 价某次地图匹配结果的可信程度的参数。该参数值的大小除了与此次匹配 结果和车辆位置问的距离及角度差直接相关以外，还与g p s 信号的接收 状况、车辆以前的匹配结果相关。该参数的具体计算方法参见【1 4 1 。 图2 - 1 3 行驶状态的转换 1 1 一种用于铁路的地图匹配算法【2 2 】 由于铁路线的特殊设计，拐弯角度变化率较小的特点，普通的传感器 根本不能探测出铁路弯道的角度变化情况，所以设计一种铁路专用的匹配 算法有其必要性。该算法利用了铁路线“一维继承性”的特点，算法的核 心是实时的在线检测由陀螺计和转速计所测得的角度变化率，并和数据库 所查询的相应的值相比较得到匹配结果。传感器融合需要由陀螺和速度传 感器或者单程计组成。 北京交通大学硕上学位论文 第二章 入 一7 图2 1 4 用丁铁路的地图匹配算法示意 i i i 一种用于个人定位系统的匹配算法【2 l 】 图2 1 5 一种_ j 丁个人定位系统的匹配示意 此算法的设计初衷是基于个人定位系统不同于车辆定位系统的一些 特性，比如由加速度计和回转罗盘所测得的数据比如步长和方向不如车轮 传感器所测得的数据精确。而且车辆总是在道路上行驶，而且相对变化较 小。而行人所走的路线则较为随意，而且有较大的起伏。所以，这个算法 应用三维的地图数据库，配合三维的陀螺以及传感器束实现匹配算法。 i v 基于g p s 测量特性的匹配算法【2 3 】 由于g p s 定位的不准确性，首先定义衡量g p s 定位的“稳定性”的 变量： 式2 5 其中砰是在第。个历元测量位置点与道路之间的距离以及第( n 1 ) 个历元测量位置点与道路之间的距离之差。不同的接收机有不同的r m s 值，从而反应其定位的“稳定性”。 虽然g p s 位置点的绝对误差可能很大，但是g p s 相邻位置点之间的 第l3 负 苎室奎塑查兰婴圭堂些堡兰塑三里 相对误差却较小。所以充分利用g p s 测量数据的这个特性，可以实现道 路的精确匹配。 v 基于神经网络的地图匹配算法【1 4 1 由于地图匹配是一种基于模式识别理论的减小定位误差的方法，因 此，毫无疑问，许多模式识别方法都可以在地图匹配中得到应用。其中之 一就是基于神经网络的方法。神经网络由许多相互联接的层结点( 神经元) 组成。神经网络是一个动态自适应系统，有学习能力，所以必须被训练以 适应现实世界的变化。 除不同的模式识别方法外，可采用集中的、分级的或混合式的方法同 定位传感器一同工作。在集中方式下，多传感器数据以集成、融合的方式 与地图进行匹配；在分散方式下，每个传感器或传感器组以独立的形式与 地图进行匹配；在混合方式下，集中方式和分布方式可顺序地应用以获得 更好的匹配结果。 v i 基于分组神经网络的地图匹配算法 2 4 】 在2 0 0 2 年，w i n t e r 先生曾经提出过利用人工神经网络( a n m c i a l n e u r a ln e t w 0 t k s a n n ) 来提高路段选择的效率和可靠性，随后又提出了 利用分组神经网络( m o d u l a rn e u r a ln e t w o r k s m n n ) 来进行地图匹配的 方法。 通过使用n e u r a l w a r ep r o f e s s i o n a l 来进行a n n 仿真，向an n 输入大 量的数据( 包括不同类型的路段，如直路、弯路、平行路段、交叉路口等) ， 可以训练神经网络。如果用于训练的数据维数太低，训练结果就可能达不 到预期要求；反之，数据维数太高，训练过程就会很慢。并且，使用反馈 系统可以减小系统的误差。 分组神经网络把路网分成不同的区域，分别代表不同的地理特征。进 行系统训练的时候，数据将自动地分入各子系统，形成多个个专家系统。 这种方法可以在g p s 卫星数较少或g p s 接收信号较差的情况下，如：峡 谷、草地、崎岖的地形，提高定位的准确度。 2 2 地图匹配算法总结 总之，目前存在和普遍采用的各种各样的地图匹配算法，分别适用于 不同的情况，并且各有各自的优缺点。综上所述，各种地图匹配大致可以 分为常规算法、基于概率统计的算法和基于模糊逻辑、拓扑关系的算法， 下面分别予以讨论。 l 、常规算法 其基本思想是把车辆的行驶轨迹同接近以前匹配点的道路进行比较。 第l4 页 ! ! 室奎望查兰堡兰篁丝塞 兰三里 在待选择的道路中根据计算得出的相似度的大小，得到匹配路段，并作为 车辆正在行驶的道路。 该系列算法的输入参数为车辆的初始位置( 经、纬度坐标) ，行驶方 向和行驶速度等。通过比较推算定位推算出的拐弯和由地图坐标计算出的 路段矢量所包含的拐弯，进行周期性的条件测试以确定车辆是否在已知的 道路网上行驶。由于推算定位传感器和地围坐标中的误差，往往无法得到 准确的对应。并且必须设置一个阈值来帮助有限的潜在匹配；否则，定位 任何匹配路段会变得很困难。这种方法通常假设车辆在道路上。每当系统 检测到车辆拐弯时，就会修正推算定位距离传感器产生的累积误差。如果 车辆的行驶路线在两个拐弯之间驶出了道路，系统将被误导以为车辆正常 经过弯道，并在该点错误的修正误差。 由于该系列算法假设是车辆沿着预先确定的道路行驶，而车辆驶出道 路时存在相当大的不确定性将极大的影响算法的鲁棒性，所以，该系列算 法现在很少被采用。然而，应当看到，在铁路应用中，由于车辆出轨的情 况极少发生，所以概算法仍不失为简单铁路应用的有效参考。 2 、基于概率统计的算法 地图匹配本身可以被看作是一类基于概率理论的算法。然而，由于一 般的基于概率理论的方法都需要有相当多的与优先概率和条件概率相关 信息支撑，所以通常来说该类算法需要较大的计算量。 该类算法要求推算定位的传感器误差在统计意义上被传播到位置决 策中。这些误差和误差模型定义的椭圆形或矩形区域用j 二描绘出真实车辆 位置所可能处于的区域边界。这种置信区域被叠加到电子地图，落在置信 区域中的道路实体被选取到匹配模板库中，最后通过车辆定位信息或行驶 轨迹和匹配模板库中的实体进行匹配，得到车辆行驶的道路。在匹配过程 中，需要进行连通性检查以确定车辆在经过交叉路口时的可能位置。 这种方法的优点的主要在于它不要求车辆总是在道路上。如果车辆不 在已知的道路网上，概率统计算法就会反复地比较传感器检测到的坐标和 偏离道路的路段坐标，并尽量识别车辆返回的路段。同时，这种故障恢复 的能力也体现了该类算法的鲁棒性。 3 、基于模糊逻辑的算法 基于上述内容，由于传感器的温度漂移，卫星多径反射效应和d r 系 统的累计误差等原因，由传感器采集到的原始定位数据通常不能反映车辆 的真实行驶轨迹，而且与电子地图中的道路实体相去甚远。这给地图匹配 算法造成了困难。 考虑一辆行驶在复杂路网中的车辆，特别是相互之间有很多平行道路 北京交通大学硕士学位论文 第二章 的时候，在任一时刻确定车辆正在哪一条道路上行驶都是困难的。一般情 况下，系统只能得出类似“车辆很可能在某一街道上”的结论。在这 种情况下，只有当提供足够多的附加信息和历史数据能够帮助确定车辆的 位置。如果要求一个精确定位与导航系统，这种模糊性需要解决。因此， 在地图匹配过程中需要处理定性术语( 如可能性) 的技术。 模糊逻辑已被证明是处理涉及定性术语。模糊语言和人工干预任务的 有效方法。利用模糊集合，具有模糊概念的术语能够用数学方法来定义。 专家知识和经验可表达成规则集。此外，通过适当的推理过程可做出结论， 该推理过程类似于人的推理能力。由于地图匹配是涉及模糊度的定性决策 过程，所以研制基于模糊逻辑地图匹配算法是有用的。除地图匹配模块外， 模糊逻辑也可以用于其他模块或子系统f 1 4 】。 上述算法的基本原理其实是相同的，都是通过识别车辆行驶的路段， 来精确地确定车辆的位置以便更新推算定位位置。它们的主要区别是，基 于模糊逻辑的算法使用模糊推理过程确定匹配路段，而另外两种算法是通 过概率统计推理方法确定匹配路段。具体来说，前者利用隶属函数描述与 候选路段有关的传感器误差模型，而后者以概率方式相对于候选路段定义 传感器误差模型。两种算法的匹配过程基本相同。每一候选路段都与一种 可能性相关。这些可能性根据相似性增加或减小。最后系统选取最高可能 性的候选路段作为匹配结果。当然，评价可能性的方法有很多。 4 、算法对比 基于以上讨论，选用算法的时候，应当根据不同的情况，不同的匹配 精度要求，采用不同的算法。当然，实际应用的时候，也可以结合各种算 法的优点，采取动态切换的办法进行。 目前，根据匹配样本类型，地图匹配算法主要可以分为：位置点匹配 和轨迹曲线匹配。 表2 1 算法对比 算法逻辑复杂度计算量实时性复杂情况匹配准确率鲁棒性i l 付胃占j e 酣 简单小好低 差 曲线匹配 复杂大差较高好 由于实际应用中，没有任何一种算法能在所有的情况下都表现出特别 突出的效果。所以，根据目前各种算法的优缺