基于曲线拟合与拓扑结构的地图匹配算法

2018-08-17滕志军

计算机工程 2018年8期

滕志军,,,,,

(1.东北电力大学信息工程学院,吉林吉林 132012; 2.国网七台河供电公司,黑龙江七台河 154600;3.东北师范大学附属中学,长春 132000; 4.国网吉林供电公司,吉林吉林 132011)

0 概述

随着北斗二代导航系统的逐渐完善,北斗导航定位技术已被广泛应用于地面移动目标的跟踪定位,车载导航系统就是众多的应用之一。但在实际的车辆导航中,由于定位数据的系统误差和偶然误差以及电子地图精度的问题,会造成定位点与车辆所在实际道路点存在偏差[1-3],这不仅会给驾驶者带来视觉上的疲劳,而且这种错误信息会带来严重的交通事故。因此,研究快速、准确、有效的方法来减少这种误差,对提高导航的性能尤为重要。目前解决这种问题的方法主要有2种[4-5]:一是提高导航定位数据和导航电子地图的精度,但是这种方法实现起来较复杂,成本较高;二是通过目前常用的匹配算法来修正车辆的正确位置,即通过计算定位点与道路点的误差进行强行修正[6],这种方法成本较低,比较容易实现,因此,成为研究的热点。

地图匹配技术已被广泛应用于车辆导航、导弹制导、雷达探测等方面。很多学者对该技术进行了详细研究。目前提出的算法主要有基于权重的地图匹配算法[7]、基于D-S证据推理的地图匹配算法[8]、基于模糊理论以及基于神经网络的地图匹配准则[9-10]等。这些算法各有优缺点,适应情况各不相同,而且原理比较复杂,实现难度较大。针对传统曲线拟合匹配算法在复杂路段精度低的缺陷[11-12],本文提出以相对误差为基准进行曲线拟合的地图匹配算法,在平行路段采用最短距离判别法来弥补曲线拟合算法在平行路段不精确的缺点。

1 地图匹配基本原理

地图匹配技术的实现首先要满足2个最基本的先决条件[13]:一是车辆总是行驶在道路上;二是所采用的道路电子地图的精度要高于定位数据的精度。进行车辆匹配时第1个条件是符合的,第2个条件中目前的电子地图精度也是符合要求的。地图匹配要实现2个目标[14-15]:首先要在候选路段内确定车辆所行驶的实际道路,其次就是对定位系统接收到的定位数据与实际的电子路况中的信息通过地图匹配算法进行修正,从而确定车辆所在的实际位置。

为了更详细地说明地图匹配过程,设车辆在图1所示道路系统上行驶,在t时刻车辆所在的实际位置为道路B的pt点,由于各种误差的存在,卫星定位数据给出的定位位置为PD。地图匹配就是通过一定算法找出道路B并确定车辆所在当前道路中的位置。

图1 地图匹配原理图

随着城市道路网的密集程度加大,相似相邻道路越来越多,在定量分析的情况下,高斯最小二乘法的评价依据是针对等精度数据而言的,也就是说观测数据有大体相同的绝对误差,但是卫星定位数据的误差不具有一致性[16]。针对这种情况,本文提出以相对拟合误差平方和最小为原则的曲线拟合地图匹配算法。

2 改进地图匹配算法的实现

2.1 数据预处理

城市道路系统一般比较复杂,密集的建筑物会对卫星定位数据造成一定的影响,易出现异常定位点。为了保证定位点的有效性,在进行地图匹配之前必须对卫星定位数据预处理,剔除经纬度或速度突变的数据,并根据汽车的行驶方向、速度等信息补全所剔除的定位点。

当出现漂移值时,利用车辆前一点速度和车辆方向进行插值,如图2所示。

图2 插值原理图

由于车辆获取定位点的频率较高,当车辆在弧线路段行驶时可以将道路看做短距离的直线路段,因此插值后定位点坐标如式(1)所示,其中(x,y)表示定位点坐标。

xi+1=xi+viΔtsinε

yi+1=yi+viΔtcosε

(1)

2.2 检索道路集合确定

误差区域示意图如图3所示,其中,x轴方向为东,y轴方向为北,椭圆中心为北斗系统接收的定位点,a为椭圆长半轴,b为椭圆短半轴,φ为误差椭圆长半轴与正北方向夹角,δ0称作扩张因子,可以通过其来调节椭圆大小,本文将其设置为1。

图3 误差区域示意图

由于椭圆在计算过程中较复杂,此处用误差圆来代替误差椭圆。误差圆的中心与椭圆中心为同一点,其半径为误差椭圆长半轴,如下式所示。

候选区域确定后,候选区域内的道路集合中包含车辆正在行驶的道路,但是随着道路网的密集程度加大,该集合内的道路条数可能较多,会消耗大量的匹配冗余时间。针对该问题,本文提出一种考虑道路网拓扑结构的策略。如图4所示,假设车辆正在道路1上行驶,考虑道路的拓扑结构、连通性以及车辆的行驶速度,与道路1相连的只有道路2和道路3,车辆下一时刻不可能出现在道路4～道路6上,减少了大量的道路检索时间,提高了算法的时效性。

图4 道路拓扑结构

2.3 匹配路段确定

确定匹配路段的过程如下:

1)改进的地图匹配算法以相对误差最小为最佳拟合准则。设定位点的坐标为pi(xi,yi)(i=1,2,…,N),用一个m次多项式y=a0+a1x+a2x2+…+amxm来拟合N个观测点数据,使得相对误差的平方和最小。下面给出求解过程。

k=0,1,…,m

(4)

进而可得如式(5)所示的正则方程组。

该正则方程组的解即为所求拟合多项式的系数,将多项式转化为矩阵形式并化简得到式(6)。

即XA=Y的形式,那么A=(XTX)-1XTY,这样就可以求得系数矩阵,因此,得出各系数的大小。

由于在电子地图中的道路是用直线和线段来代替的,地图匹配的前提是车辆行驶在道路上,考虑到这一前提,在一定的行驶距离内可以用直线来拟合车辆的历史轨迹,直线的斜率由上述求解方法可得:

鉴于道路的最短距离和合理的计算量本文选取5个观测点做一次拟合曲线,即用直线拟合,由式(7)可得该5点所拟合的直线斜率为:

其中,(xi,yi),i=1,2,3,4,5是导航定位数据经坐标转换后的地图坐标,由地图匹配的原理可知,k0反映了车辆的行驶方向,在测量误差允许的范围内笔者认为车辆方向夹角和候选道路夹角差值30°以内的道路为所要匹配的路段。因此,得出地图匹配算法的综合评价函数z为:

图5 距离匹配原理图

2.4 匹配点确定

车辆行驶路段确定后,采用垂直投影法将定位点投影到候选道路上,因为道路都近似于线段,所以可能会出现投影点不在道路上的情况。假设定位点D的坐标为(x,y),道路两端端点坐标分别为S(x1,y1)和M(x2,y2),如果D的投影点在道路上,设为N(xi,yi)。定义:

其中,θ是向量SD和向量SM的夹角。当01时投影点出现在M端延长线上,此时定义投影点为M(x2,y2)。如图6所示,D落在C区域内时投影点为N(xi,yi),落在C1区域时投影点为S(x1,y1),落在C2区域时投影点为M(x2,y2)。

图6 投影原理图

3 算法验证

3.1 实测验证

为了验证本文改进地图匹配算法的有效性,对其进行实测验证,定位模块为北斗UM220模块,地图通过调用百度地图来完成。在校园内进行跑图测试,图7给出了利用该算法进行实测的结果,采样频率为10 s。图7(a)是原始定位数据轨迹,图7(b)是在该算法下的匹配图。由图7(b)可以看出,各定位点能很好地匹配到所行驶的道路上,在道路复杂情况下,该算法仍具有最高的匹配准确率。

图7 实测结果

3.2 精度仿真

图8为4种不同地图匹配算法在同一条件下的匹配准确率仿真结果,从中可以看出:当车辆行驶附近有2条相似道路时,匹配准确率都达到98%以上;当出现3条以上相似候选道路时,虽然4种匹配算法匹配精度都有所下降,但是本文匹配算法相对其他算法匹配准确度下降缓慢;当检索区域内有5条相似道路时,本文算法的匹配准确率仍在92%左右。由此表明,本文改进算法在复杂路段仍具有较好的匹配性能。

图8 不同算法的匹配率比较

图9为对本文算法、传统曲线拟合算法、D-S证据理论算法、直接投影算法的匹配时间仿真结果。其中匹配时间为从获取定位点到寻找出车辆行驶道路然后进行垂直投影所花的平均时间。从图9(a)可以看出,在检索区域内有2条候选道路时,本文算法单点匹配时间约为4.45 ms,由4幅图横向比较来看,随着检索区域候选道路条数增加,本文算法单点匹配时间增幅较少,即使候选区域道路条数为5,本文算法单点匹配时间仍为5 ms左右,而其他比较算法均在8 ms以上,增幅较大,因此,本文算法在复杂道路下仍具有快速性。