改进ORB-SLAM算法在户外离线即时导航的研究

邹倩颖, 关杰文, 肖 航, 符鑫珺

(电子科技大学 成都学院 云计算科学与技术系，成都 611731)

0 引 言

随着无人驾驶、无人勘探、AR/VR的应用日渐增多，优化并更有效应用ORB-SLAM算法成为亟需解决的问题。文献[1]中使用一种处理灰度图像的算法，利用自适应阈值选取算法，直接利用图像灰度进行低层次图像处理，且具有处理速度快等特点，但其在强高斯噪声和椒盐噪声环境下，检测效果较差。在FAST算法中，关键点又称为角点[2]，若一个点的像素及灰度值与邻域点的像素值差别较大或较小,那么它可能是角点。FAST算法以速度快而著称，但在判断特征点时使用的是固定阈值方法，不能很好地适应色彩变换较大的图像。

文献[3]中提出了另一种角点检测算法，Harris算子是一种基于信号的特征点提取算子，由于受到自相关函数引导，通过计算图像移动的灰度变化情况，对图像灰度进行一阶导数估算自相关矩阵来得出特征值，使Moravec算子具有了旋转不变性和光照不变性。但Harris角点检测算法仅对图像进行一次高斯平滑，没有解决单一尺度问题，对噪声的抗性也不足，而非极大值抑制的关键在于阈值的选取，阈值过大会让角点数量少;阈值过小会出现伪角点，精度方面自然不能保障。虽然后期的高斯尺度空间与Harris角点检测算法的结合解决了尺度不变性问题，同时达到了去噪的效果，但却大大增加了运算时间。同时，在户外进行地图路径规划时，实时性与特征点提取的精度也直接影响到了地图路径的规划。

针对特征点提取时固定阈值选取算法灵活性不足和传统的多尺度Harris角点检测耗时过多的问题，提出一种基于自适应阈值选取和局部搜索算法的改进室外场景特征点提取算法。通过采用改进室外场景特征点提取算法，计算图像局部点的灰度值与图像平均灰度值的方差表示对比度，然后利用积分图像求得局部灰度值的平均值，采用对比度与其局部灰度值的平均值来求得局部动态阈值，在计算卷积积分和拉普拉斯响应值筛选中通过局部搜索算法代替逐一比较的方法，降低了运算复杂度，使得实时处理制图数据得以提升。

1 改进室外场景特征点提取算法

1.1 算法流程

本文算法流程如图1所示,算法流程如下所示。

(1) 粗提取。特征点提取时，先进行阈值选取，划定要判定点的区域,运用积分图像进行局部平均阈值的计算。然后计算选取点的灰度值与局部图像平均灰度值的方差近似于对比度，利用对比度以及图像局部平均阈值的关系计算出最适宜于该点的阈值。

(2) 非极大值抑制。利用非极大值抑制来解决选取的多个特征点由于过于聚集形成特征块的问题。为每个检测到的特征点计算它的响应值。响应值是p点与它周围16个点的绝对差值,尤其先考虑2个相邻的特征点，并比较它们的值。响应值较低的点将会在选取的特征点中去除。

(3) ID3算法。将粗提取后的特征点作为一个训练集，使用ID3算法查询每个集合，训练为一个决策树，用于检测其他相似图片的OFAST检测。

图1 算法流程

(4) Harris角点检测。将目标图像进行高斯平滑处理，在x或y方向上取微分，决定了Harris角点当前尺度的变量和角点附近微分值变化的变量。为了判断角点是否为该局部尺度下的特征点，对提取的角点进行响应值计算，然后在点的邻域内进行响应值比较，搜索出响应值最大的点。

(5) 多尺度Harris角点检测。对每个尺度都进行计算，对于位置空间的每个候选点进行拉普拉斯响应计算，并满足绝对值大于给定的阈值条件。对满足条件的点进行局部搜索算法进行比较，得出既满足位置空间又适合尺度空间的Harris角点。

(6) BRIEF特征描述。在一定区域内取一对像素点，然后分别比较每对像素点的灰度大小并赋值于1或0，采用二进制编码，用Hamming距离[4]进行描述子的比较与匹配。

1.2 局部动态阈值确定

在FAST算法中，阈值[5]所代表的就是在提取特征点是其与周围邻域的点的最小对比度，也是其所能消除噪声的最大限量。阈值所选取的值直接影响了特征点提取的精准度。阈值越大，所提取的特征点也就越少;阈值越小，选取的特征点也就越少。在原有的FAST-12算法中采用的固定阈值的方法虽然在计算量上进行了一定的减少，但因为阈值是固定的，所以当在野外进行拍照完后，图像中很可能存在阴影，由于突发噪声等客观因素，不能很好地使得阈值的选取能随着全局图像灰度以及噪声的影响而随之变化。本文中提出了采用动态设置局部阈值T的方法[6]对特征点进行提取。局部动态阈值T的选取能随着局部不同特征点所具有的不同情况，得出一个对于特征点提取最适宜的阈值，以使得提取的特征点更加精确。

在FAST-12算法中，进行特征点的选取时实质上就是特征点的灰度值在于其周围点灰度值对比度的衡量[7]。对比度可以简单地理解为一幅图像里图像灰度反差的大小，也就是图像中各点的灰度值与平均灰度值之间的差异大小。因此在粗提取的改进上本文根据局部阈值与对比度相关，建立函数，以此实现局部阈值跟随局部图像变化而变换的目的。在粗提取中分析了对比度与图像阈值之间的关系，提出了图像在不同区域L下自适应阈值的计算。在图像上选取点为(x0，y0)，以(x0，y0)为中心取矩形区域，定义随全局图像变化而变化的阈值

(1)

式中：k为比例系数，根据相关实验,k值范围2.5～5.0时选取结果较为准确；

为所求选取区域内各点灰度值与区域内平均灰度值的方差，以此来近似表示该区域内的对比度;m(x0,y0)为局部区域内的平局灰度值。

本文采取Viola和Jones积分图像定义快速地进行局部均值的计算，

(2)

式中：i(x,y)表示输入图像中的像素点；ii(x,y)表示积分图像，

ii(x,y)=ii(x-1,y)+s(x,y)

(3)

s(x,y)=s(x,y-1)+i(x,y)

(4)

式中：s(x,y)表示点(x,y)的y方向上的所有原始图像之和，而对于计算选取的任一区域L内的局部均值，

(5)

式中：iiL(x,y)表示在区域L内的图像局部积分图像，则局部均值,

(6)

m(x,y)表示在区域L内的局部积分图像;(x-u)(y-v)表示区域L的面积。

1.3 非极大值抑制

在FAST算法中，关键点又称角点，主要检测局部像素灰度值变化明显的地方，以速度快而著称。角点的定义为如果一个点的像素及灰度值与邻域点的像素值差别较大(过亮或过暗)，那么它可能是角点，即在选取的点周围有足够多的点的灰度值大于或小于它，那么就定义此点为一个特征点。

如图2所示，在图像中选取一点p，在其周围形成一个圆形区域(半径为3的Bresenham圆[8])，则圆心p被16个像素点包围。在16个像素点形成的圆周上，如果有n个连续点的灰度值大于Ip+T或小于Ip-T，那么像素点p可以认为是一个候选特征点。n值通常选取为12时，能快速地排除一些非特征点，于是该算法[9]也被称为FAST-12算法。算法步骤如下：

(1) 在图像中选取像素点p，计算的灰度值，在图像中每点颜色都由红、绿、蓝三基色组成，假如在图像中任一点的颜色可以用坐标RGB(R，G，B)，那么该点坐标可计算出灰度值为：0.11B+0.59G+0.3R。

(2) 设置阈值T。

(3) 以像素p为中心，选取半径为3的圆上的16个像素点。

图2 FAST粗提取原理图

假如选取圆上有连续N个点的灰度值大于Ip+T或者小于Ip-T，那么认定该点为一个特征点，循环以上3个步骤，并对每个选取点执行相同的操作。

1.4 ID3算法

ID3算法[10]利用信息论中信息熵下降速度为选择标准，核心在于决策树各个结点上最高信息增益属性作为选择特征，通过贪心策略递归构建决策树，直到决策树能很好地分类训练集。

算法步骤如下所示。有输入数据集S，特征集F，阈值M，通过递归运算计算并输出决策树R。

(1) 若数据集S中所有个体属于同一类Ck，则R为单结点树，并将Ck作为该结点的类标记，返回R。

(2) 若F为空集，则R为单结点树，并将数据集S中个体数最大的类Ck作为该结点的类标记，返回R。

(3) 对特征集F中各特征对数据集S的信息选择增益，选择信息增益最大的特征Ag。

(4) 如果Ag的信息增益小于阈值M，则置R为单结点树，并将数据集S中实例数最大的类Ck作为该结点的类标记，返回R。

(5) 对Ag的每一可能值Ai，依Ag=Ai将数据集S分割为若干个非空子集Si，将Si中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树R，返回R。

(6) 对第i个子结点，以Si为训练集，以F-{Fg}为特征集，递归地调用步骤(1)～步骤(5)，得到子树Ri，返回Ri。

1.5 Harris角点检测

Harris[11]实现了旋转不变性，Harris算子提出一种基于信号的点特征提取算子。由于受到自相关函数的启发，通过平移窗口带来变化的自相似性来衡量角点，Harris算子效率极高，操作简单，只涉及一阶导数，在纹理信息丰富区域，能够提取出大量有用的特征点，通过Harris计算每个点的响应值并通过非极大值算法进行特征点的筛取，提取一定数量的优质特征点。若想要增多被检测特征点数量，那么就减小α的值，并且角点响应值R将增大，角点检测的灵活性将提高；反之，亦然。通过这种方法还能够实现图像旋转不变性，对亮度和对比度变化不敏感性。

如图3所示，若角点位置上的窗口倘若在其各方向上移动，区域内灰度值会发生较大变化，如果只在一个方向上移动时有较大变化，那么该点大概率在直线上；如果各个方向上移动都无变化，那么可能无角点。

图3 窗口移动示例

窗口移动后自相似性衡量如下式所示：

I(u+Δx,v+Δy))2·w(u,v)

(7)

式中：W(x·y)是以(x,y)为中心的窗口;w(x,y)是以(x,y)为中心的高斯加权函数;I(u,v)是窗口函数;Δx是在水平方向上的微小偏移量;Δy是在竖直方向上的微小偏移量。

一阶近似并化简，

(8)

M(x,y)=

(9)

用字母代替，

(10)

则可将自相关函数视为一椭圆函数，

C(x,y,Δy,Δx)≈AΔx2+2CΔxΔy+BΔy2

(11)

Harris则利用角点响应值R来判断角点，

R=detM-α(traceM)2

(12)

Harris角点检测能够做到实时性，但是该算法只能在单一尺度下检测角点，而非极大值抑制的关键在于阈值的选取，阈值过大会让角点数量少，阈值过小会出现伪角点，精度方面自然不能保障。

1.6 多出度Harris角点检测

1.6.1 高斯尺度空间的构建

对输入图像和可灵活选择多个尺度的高斯核函数[12]进行卷积运算，

L(x,y,σ)=G(x,y,σ)*I(x,y)

(13)

式中：σ表示尺度;L(x,y,σ)表示尺度空间;G(x,y,σ)表示高斯核函数;*表示卷积运算;I(x,y)表示输入图像。随着图像尺度的变化，原来的局部特征也会变化，可能会出现新的局部特征或者消失。

1.6.2 尺度响应值计算

对于尺度空间响应值计算构建一个点在领域内的梯度分布为

M=μ(x,y,σI,σD)=

(14)

式中：

Lx=I(x,y)*Gx(x,y,σ)

Ly=I(x,y)*Gy(x,y,σ)

x,y∈W(u,v)为图像窗口中的坐标;σD,σI分别表示微分尺度和积分尺度，σI是决定Harris角点当前尺度的变量，σD是决定角点附近微分值变化的变量;Ly(x,y,σD)、Lx(x,y,σD)分别是对图像进行高斯处理后对x或y方向取微分的结果;g(σI)表示尺度为σI的高斯卷积核。

检测算法从预先定义一组尺度进行积分尺度搜索，其中，σI…σn=σ0…knσ0。

一般K取1.4，但为了减少复杂性，令σD=sσI，从而得到μ(x,y,σI,σD),随后利用Harris角点进行响应判断:

cornerness=det(μ(x,y,σD)-

αtrace2(μ(x,y,σD))>thresholdH

(15)

对于满足式(9)的点进行周围8领域非最大值抑制，对于满足条件的每个尺度σn(n=1,2,…,n)都进行遍历搜索，因为空间位置候选点未必是尺度空间候选点，进行尺度搜索，寻找局部结构的显著尺度，

(16)

对于满足式(16)的点进行邻近两个尺度空间的拉普拉斯响应值进行比较得到各空间上的显著尺度值。

1.6.3 局部搜索算法

针对实时性绘图效率以及精度问题，本文在文献[13]基础上进行改进，使用局部搜索算法来代替逐一比较方法，提高了效率，又剔除了大部分伪角点，能在局部范围内提取更稳定特征点，达到了了实时性的效果。

对于阈值thresholdL进行适度降低，从而得到较多特征响应值，排除了阈值过高特征响应值较少的问题，从而保留了一定尺度上有极大概率有响应值与其匹配。

利用局部搜索算法[14]，具体算法步骤如下:将进行阈值比较后的特征响应值生成一个算子集{p}。

(1) 在p内生成初始的可能解xi，在xi∈p中如果有xi，执行步骤(2)，否则执行步骤(5)。

F(x,y,σn)>F(x,y,σl)

(17)

l∈{n-1,n+1}

对于满足式(17)的尺度值就是改点的特征尺度值，则是空间和尺度空间都满足的Harris角点。

1.7 BRIEF特征描述

BRIEF是对已检测到的特征点进行一种二进制编码描述，这种方法弃用了传统通过局部区域灰度直方图来描述特征点的方法。该方法特征描述符建立速度进行了提升，同时也一定程度上将特征匹配的时间进行了缩短，是一种非常快捷，很有潜力的算法。

首先，将图像进行处理，然后在特征点周围选择一个一定大小的局部区域，在这个局部区域内选择出来m个点对。然后对于每一个点对(p,q)，通过比较这两个点的亮度值(用N()函数表示)，如果N(p)N(q)，则这个点对生成了二值串中一个的值为1,否则为0。所有m个点对，都进行比较，就生成了一个m长的二进制串。

2 实验结果及分析

2.1 实验环境与数据集

本文选取Sturm等提供的数据源。通过使用搭载Kinect深度摄像机的Pioneer机器人采集的关于不同场景的数据集[15]验证改进算法的性能。这些数据包含了丰富的常见物体，并具有良好的数据采样光照度，可有效测试算法性能。本文程序基于VS2017的C++实现上述改进算法，所有实验运行环境为Intel双核2.30 GHz CPU计算机，运行系统为Ubuntu 16.04 LTS 。

2.2 结果分析

2.2.1 特征点提取个数对比

本文针对相同场景的不同图像进行比较，通过改变图像的亮度分别对SIFT算法(见图4(a))，优化前的OFAST算法(见图4(b))，以及优化后的OFAST算法(见图4(c))特征点提取效果进行比较。

(a) SIFT算法

(b) OFAST算法

(c) 改进OFAST算法

实验结果中SIFT算法提取特征点个数为206个，原有OFAST算法提取特征点个数为179个，改进后的OFAST算法体征点提取个数为116个；

改进OFAST算法相比较原有OFAT算法在特征点个数减少了35.2%。由此可见，本文中的算法所提取的特征点数量远少于原OFAST算法和SIFT算法，其特征点匹配更为精准，制图效果误差大大减少。

2.2.2 平均时间对比

提取时间代表了算法在提取特征点的快慢，在野外环境进行导航时，时间是一大重点，时间越快,算法性能更强。

SIFT算法提取特征点时间为375.3 s，原有OFAST算法提取特征点时间为9.3 s，改进OFAST算法提取特征点时间为1.3 s。实验证明,改进后OFAST比原有OFAST算法在提取特征点时效上提高了80.6%，而改进后OFAST比SIFT算法在提取特征点时效上提高了99.6%。由此可见，改进后的OFAST算法节省了大量的时间，其工作效率远远高于原OFAST算法和SIFT算法。

2.2.3 匹配正确率对比

提取特征点的匹配正确率对于后期制图有着重要的作用，匹配正确率越高，对于后期制图的效果更佳，对于路线规划更为清晰。

SIFT算法正确率为15.2%，原有OFAST算法正确率为37.4%，改进OFAST正确率为51.8%,改进后OFAST算法相比原有OFAST算法正确率提高了14.4%，改进OFAST正确率为51.8%,改进后OFAST算法相比SIFT算法正确率提高了36.6%。由此可见,改进后的OFAST算法可以更精准地匹配特征点，且精准程度远大于原OFAST算法和SIFT算法。

总而言之,原有的OFAST需要耗费大量时间来创建金字塔模型[16]，并对高斯差分图像通过泰勒公式进行展开，消耗大量时间。本文利用局部搜索算法简化局部特征点筛选，使得特征点更加显著，效率更高，对于实时性绘图精准度有所提升，能在较短时间内绘制出较高质量的图像。

3 结 语

改进基于自适应阈值选取和局部搜索算法适应于场景比较复杂，图像对比度多变的室外场景，在提高特征点精确度上相比原有OFAST算法提升了27.8%,在时效特征点提取算法相比原有OFAST算法提高了80.6%。改进后的ORB-SLAM可以广泛应用于地理情景教学、户外地形探索、建筑测绘领域。但改进后的OFAST算法虽然在特征点提取、平均时间响应、算法匹配正确率上有一定提升，但还未达到预期效果，未来将在粗提取方法进行进一步的优化。