GPS导航系统中的地图匹配算法

liyf

GPS 导航系统中的地图匹配算法
王 敏，魏衡华，鲍远律
(中国科学技术大学自动化系，合肥 230027)
摘 要：传统算法对于复杂路况的匹配正确率较低，为此，提出一种适合于交通网络拓扑结构变化的动态平行四边形匹配算法。利用权值
选出匹配路段，并将全球定位系统(GPS)轨迹点投影到匹配路段上，在交叉路口以平行四边形匹配准则消除车辆轨迹点沿道路方向的误差，
通过动态偏差更新，解决卫星换星、大气云层遮挡、多路径效应等因素造成的偏差问题。引入该算法的GPS 车载系统在合肥市实地跑车实
验结果表明，其对于复杂路况仍能进行正确匹配，真实再现车辆行驶情况。
关键词：矢量地图；地图匹配；平行四边形匹配；智能交通系统；全球定位系统
Map-matching Algorithm in GPS Navigation System
WANG Min, WEI Heng-hua, BAO Yuan-lv
(Department of Automation, University of Science & Technology of China, Hefei 230027, China)
【Abstract】Aiming at the problem that existing map-matching algorithms have weakness to deal with complex traffic, this paper proposes a new
algorithm called parallelogram matching method, which can adaptive the topology changes of transport network. The method selects the match road
by weight and projected Global Positioning System(GPS) track points on it. The prallelogram matching criterion is used to eliminate the vehicle
trajectory point’s error in the direction of the road after intersection. Bias due to the satellite changed, clouds obscured the atmosphere and multipath
is effectively corrected by update. Real-life application of the method to the city of Hefei shows that it can correct GPS errors reasonably with
improved computational efficiency.
【Key words】vector map; map-matching; parallelogram matching; Intelligent Transportation System(ITS); Global Positioning System(GPS)
DOI: 10.3969/j.issn.1000-3428.2012.14.077
计 算 机 工 程
Computer Engineering
第38 卷 第14 期
Vol.38 No.14
2012 年7 月
July 2012
·开发研究与设计技术· 文章编号：1000—3428(2012)14—0259—03 文献标识码：A 中图分类号：TP391
1 概述
随着车辆的大幅度增加，为避免交通拥堵，城市道路网
络建设日益复杂化。由于全球定位系统(Global Positioning
System, GPS)具有全方位24 h 实时定位与导航能力，因此，
基于GPS 的智能交通系统(Intelligent Transportation System,
ITS)日益受到各个国家的重视。车辆导航和定位以地图匹配
算法为核心，为出行的车辆进行路径规划和实时引 导，提高
了交通系统效率。
数字地图一直是导航系统的基础，如果没有数字地图的
显示，无论定位精度多高，对使用者来说都毫无意义。然而，
现有的大部分数字地图在制作时都存在拓扑误差和地理误
差。此外，GPS 定位、测速精度受到空间卫星、电波传播途
径、接收设备和人为等因素影响。文献[1]对GPS 误差特点作
了详细的总结：(1)单点GPS 定位有误差椭圆现象；(2)GPS
误差有慢漂移特性；(3)在大多数情况下，相邻两观测点的距
离基本等于实际两点的距离。在95%的情况下，两者之间的
差值小于1 m。
目前，地图匹配常用的几种算法是几何匹配、拓扑匹配、
概率论匹配算法、高级地图匹配算法。几何匹配是最基本也
是最早被使用的一种匹配算法，它仅考虑GPS 数据采集点和
特定路网元素的距离，不考虑道路之间的拓扑关系。拓扑匹
配不仅考虑GPS 采集点和路网元素的距离，而且将历史采集
点信息及道路网络的拓扑连通性纳入考虑范围。文献[2]设计
了一种带权值的拓扑匹配算法，该算法基于对路网的拓扑分
析，但只利用了定位中的坐标信息，没有使用GPS 采集数据
的车头朝向或速度信息。概率论匹配算法利用置信区域筛选
当前匹配路段。为减小误匹配，文献[3-4]分别提出了一种利
用多假设思想的地图匹配算法，其特点是在为每个点确定匹
配路段时，利用置信区域选出多个候选值并存储起来，每条
候选路段都有一个得分，在GPS 序列结束时才选出得分最高
的路段作为匹配路段。高级的地图匹配算法采用更复杂的理
论基础。本文通过对GPS 误差和地图误差进行研究，设计一
种改进的适应交通网络拓扑的地图匹配算法——动态平行四
边形匹配算法。
2 地图匹配思想
地图匹配过程确定车载导航系统实时接收的GPS 轨迹点
在地图上所处的路段并最终确定车辆在该路段上的具体位
置。其每一步都可分为2 个阶段：待匹配路段的选定和匹配
路段上匹配点位置的确定，但是在车辆行驶过程中这2 个阶
段的重要性及计算的侧重点是不同的。在初始时段和经过交
叉路口时段，最重要的是确定车辆行驶所在的唯一正确的那
条路段，以免到非行驶路段上去求解匹配点的位置。当车辆
行驶到路段中部时，匹配路段已经确定，此时匹配的重点是
确定车辆的大概位置。车载导航系统位置精确匹配的重要指
标是减少匹配点沿道路方向上的误差，目前这仍被公认为是
地图匹配过程的难点之一。同时，还需要预测车辆是否已经
行驶进入到前面的交叉口区域，应当提前为经过交叉口后的
基金项目：国家自然科学基金资助项目(60974092)
作者简介：王 敏(1984－)，男，硕士研究生，主研方向：智能交通
系统，GPS/GIS 应用；魏衡华，高级工程师；鲍远律，教授
收稿日期：2011-09-08 E-mail：[img]mailto:ahangin@mail.ustc.edu.cn]ahangin@mail.ustc.edu.cn
260 计 算 机 工 程 2012 年7 月20 日
新匹配路段的选定采取必要的措施，如判断接近交叉路口的
距离、车头驶向的变化、车速变化、检测车辆在交叉口前的
等待时间等。
2.1 初始路段的选定与匹配点位置的确定
初始路段的选定用于确定算法启动时刻车辆实际所处的
路段，此时没有任何历史信息。后续GPS 轨迹点的匹配会用
到初始匹配信息，所以，初始路段的选定将直接影响后续轨
迹点匹配的准确性。
初始匹配的示意图如图1 所示，n1~n7 是道路的节点，
S1~S6是相连的路段，g1、g2、g3 是 GPS 轨迹点。以轨迹点为
中心、以半径为R 的圆形区域为置信区域[5-6]。置信区域与导
航设备有关。R 取文献[7]设定的椭圆形定位误差区域半长轴
的3 倍，经计算得出R 为60 m。与置信区域相交的路段都将
被列为候选路段，最终唯一正确的匹配路段再通过其他方式
确定。从图中可以看出，轨迹点1 g 的候选匹配路段是S1、S4。
图1 初始匹配示意图
在确定S1、S4 是1 g 的候选路段之后，分别计算轨迹点到
各候选路段的距离权值、速度和车头朝向权值，加权得出各
候选路段的总权值，取总权值最大的路段作为待匹配路段，
其他路段仍作为下一轨迹点的候选路段。
候选路段S j 的总权值定义为：
Wj Wjp Wjh ? ? ? (1)
其中，距离权值Wjp 表示轨迹点 gk 到候选路段的接近程度，
如果某条候选路段接近轨迹点，则该路段的距离权值就大。
距离权值定义为：
Wjp ? Dw (R ? Djg ) / R (2)
其中， Dw 是距离权值系数；R 是置信区域半径； Djg 是轨迹
点与候选路段的垂直距离，如果垂足不在路段上，则取轨迹
点到路段2 个端点连线长度的最小值。
另外，公式中速度和车头朝向权值Wjh 表示 GPS 轨迹点
处车辆速度、车头朝向与路段方向的接近程度对候选路段选
取的影响程度。其定义为：
Wjh ? vgkHw | cos(? gk ??sj ) | (3)
其中， vgk 是车辆行驶的速度； w H 是权值系数； gk ? 是车头
朝向(以正北方向为基准)； sj ? 是候选路段的方向或反方向(以
正北方向为基准)。一定范围内速度越快且候选路段方向与
车头朝向越接近，其路段的速度和车头朝向权值越大。当车
辆的速度小于3 m/s 时，独立GPS 接收机测得的车头朝向数
据不可靠[8]。因此，当速度小于 3 m/s 时，令 w 0 H ? 。
为了防止GPS 接收机刚开机时第1 次定位潜在的不稳定
性，可以利用更多的初始点1 2 3 k ( , , ) g k ? k k k 来累加更新候选
路段j S 的总权值j W ?，以提高初始匹配路段选择的准确性。
在导航系统初始匹配确定了待匹配路段j S 后，利用垂直
投影将GPS 轨迹点k g 投影到路段j S 上，垂足k p 即为相应时
刻车辆的匹配位置点。在最初3 个点因历史信息有限而没选
出匹配路段时，本文算法将直接显示未修正的GPS 定位点。
可以看出，垂直投影虽然可以将GPS 轨迹点投影到路面上消
除垂直道路方向的误差，但沿着道路方向上的误差仍然很
大。这种误差可以在车辆从初始匹配路段上行驶到第1 个交
叉口时得到校正。
2.2 经过交叉口后下一路段的选定
对于交叉口，由于车辆驶入这些路口经常会遇到红灯或
者减速，导致车头朝向信息不可靠，因此这时如果仅用距离
规则去判断匹配路段，误差显然会很大，很容易造成误匹配。
所以，本文处理车辆经过交叉口时下一个匹配路段选定问题
时，除了仍将距离权值jp W 及速度和车头朝向权值jh W 作为匹
配路段选定的重要依据外，还增加了一项反映车辆轨迹与候
选路段方向夹角变化的车辆行驶方向权值jt W ，用3 个权值的
总分来判断候选道路匹配的可能性。
车辆经过交叉路口时候选路段j S 的总权值定义为：
j jp jh jt W W W W ? ? ? ? (4)
夹角变化权值jt W 在一定程度上减小了车头朝向数据不
可靠的影响，其函数定义为：
jt w | cos( qk sj ) | W ? T ? ?? (5)
其中， w T 是车辆行驶方向的权值系数； qk ? 是车辆的行进方
向向量(参见图2) ( ) ( ) k k ( gk , gk ) k t ( g k t , g k t ) q g x y g x y ? ? ? ? ? 沿正北方
向的顺时针夹角； sj ? 是路段j S 的方向。
图2 车辆轨迹与路段夹角示意图
对交叉路口i n 处所有候选路段分别计算总权值，得分最
大的那条即为经过路口后的匹配路段。匹配路段确定以后，
新路段上每一时刻轨迹点所对应匹配点精确位置将采用动态
平行四边形匹配算法确定。
2.3 匹配点更精确位置的确定
如前所述，将GPS 轨迹点直接投影到匹配路段上做法简
单，但难以消除沿道路方向上的误差。消除车辆沿道路方向
误差的关键是找出GPS 轨迹点与其对应的车辆真实位置之间
的误差。近似平行四边形匹配算法能较好地补偿GPS 轨迹点
到其路段匹配点之间的误差。
本节利用GPS 轨迹与道路拓扑结构的相关性，即车辆运
动方向必须与其所在路段的方向一致并且在相邻2 个GPS 轨
迹点之间的行驶距离等于在道路上相应2 个匹配点之间的行
驶距离这一原则，提出一种改进的平行四边形匹配算法——
动态平行四边形匹配算法。
该算法利用车辆的轨迹拐点(轨迹拟合线的转折点，记
为k ? )对矢量地图相应交叉路口节点i n 的位置偏移向量k e 来
第38 卷 第14 期 261
王 敏，魏衡华，鲍远律：GPS 导航系统中的地图匹配算法
消除当前GPS 轨迹点k g 的匹配点k p 在所行进的匹配路段上
的垂直道路方向与沿着道路方向上的误差。利用数字地图道
路的拓扑信息与转弯前的车辆轨迹及当前GPS 轨迹点k g 动
态求得轨迹拐点k ? ，获得k ? 对交叉路口节点i n 的位置偏移
向量 ek ? ni ?? k 。基于短时间(300 s)内 GPS 轨迹点的漂移误
差基本恒定(总漂移误差
GPS导航系统中的地图匹配算法.pdf (1.23 MB, 下载次数: 3)

2014-10-1 07:08 上传

点击文件名下载附件
下载积分: 银子 -10 两