视觉SLAM中ORB配准算法的研究

2019-09-02 09:18李艳山刘智李攀周玉轩王世凯
关键词:准点灰度像素

李艳山,刘智,李攀,周玉轩,王世凯

(长春理工大学 电子信息工程学院,长春 130022)

SLAM技术是实现移动机器人在未知环境中自主定位和导航的关键技术,V-SLAM技术则使用移动机器人搭载的相机采集的图像作为唯一的观测信息于运动过程中估计自身的轨迹,同时构建出环境的模型[1]。一个完整的V-SLAM算法框架包括图像的采集、局部相机轨迹和地图的估计、全局相机轨迹和地图的优化三部分。其中局部相机轨迹和地图的估计主要采用图像特征点法和直接法来实现。由于图像特征点法具有运行稳定、对外界干扰(光照、噪声、旋转、尺度等)具有良好的稳定性[2]。因此,越来越多的V-SLAM研究者采用基于图像的特征点的方法来完成图像的预处理。最早,Lowe提出了尺度不变特征变换(Scale-Invariant Feature Transform,SIFT)算法[3],该算法充分考虑了特征点在图像尺度变化过程中的鲁棒性,保证了特征点在图像尺度变化过程中配准的准确率。完文韬等人在2018年提出了一种改进的SIFT算法[4],该算法有效的剔除图像配准过程中的误匹配点对。但是,以上算法均很难满足V-SLAM的实时性要求。Bay等人在2016年提出了加速鲁棒特征(Speed-Up Robust Feature,SU-RF)算法[5],该算法主要解决SIFT算法中存在的计算量过大问题。张凤晶等人在2016年提出了改进的SURF算法[6],该算法在不增加配准的时间前提下,提高了配准的精确度。夏岩等人在2017年提出了改进的SURF算法[7],该算法提升了图像配准的成功率,同时缩短了配准的时间。但是,SIFT和SURF算法在V-SLAM中仍然需要一定的计算量,目前普通PC机的CPU难以进行实时的定位与建图,可以通过GPU进行加速计算,但是引入GPU将带来整个SLAM成本的提高。Rublee等人在2011年ICCV的论文中提出了基于FAST(Feature from Accelerated Segment Test)[8-9]特征点提取和BRIEF(Binary Robust Independent Elementary Feature)[10]特征描述,称之为ORB(Oriented FAST and Rotated BRIEF)算法[11],该算法和SURF、SIFT算法相比,其计算速度具有大幅度的提升。

ORB算法改进了FAST特征点提取算法,在原版FAST的基础上计算了特征点的主方向,使提取出来的特征点增加了旋转不变性。ORB算法主要通过检测局部像素灰度差异值来提取特征点,同时对特征点增加了的二进制描述子BRIEF,目前广泛的应用于实时性较高的V-SLAM系统中。然而,针对ORB算法在特征点提取时存在效率低下、随机采样一致性(Random Sample Consensus,RANSAC)[12]在特征点配准中存在耗时过长的问题,将导致V-SLAM系统的实时性及准确性大幅度下降。因此,本文在对ORB配准算法进行理论分析的基础上提出了一种改进版的ORB配准算法。首先,将介绍V-SLAM算法的整体流程及原ORB算法,包括特征点的提取及描述子计算方法。然后,分别提出了ORB和RANSAC的改进算法。最后,通过实验验证,改进的ORB配准算法比原算法更加高效、鲁棒。

1 V-SLAM整体流程及ORB配准算法

1.1 V-SLAM整体流程

在基于特征点法的整个V-SLAM过程中,首先对采集到的图像进行预处理,主要为图像的特征点提取与配准。然后,根据相邻图像之间的配准点来估计局部相机的运动轨迹及构建局部地图,然而仅仅通过累加原理来构建出全局的相机运动轨迹及全局地图,将不可避免出现累计误差。非线性优化部分采用Bundle adjustment(BA)算法[13]对相机位姿估计值、局部地图和闭环检测结果进行优化,从而得到全局一致的相机位姿轨迹和地图。基于特征点法的V-SLAM总体算法框架如图1所示。

图1 基于特征点法的V-SLAM总体算法框架

基于ORB算法的图像预处理的过程主要包括以下三个阶段:FAST特征点的提取过程,提取图像中的特征点位于什么位置;BRIEF描述子计算过程,对特征点周围的像素信息进行描述;特征点的配准过程,根据相近的特征点具有相近的描述子的原则,采用汉明距离结合RANSAC算法对所提取到的特征点进行精确的配准。基于ORB算法的图像预处理过程如图2所示。

图2 基于ORB算法的图像预处理过程

1.2 ORB特征点提取

在ORB算法中,使用FAST对特征点进行提取。由于FAST不具有旋转不变性,因此在ORB算法中对FAST检测子进行改进增加了旋转不变性,称为(Oriented FAST,oFAST)。FAST特征点提取思想:若图像中局部区域像素灰度出现明显变化(过亮或者过暗),则将该像素点定义为候选特征点,FAST特征点提取示意图如图3所示。

图3 FAST特征点提取示意图

FAST算法检测特征点过程如下:

(1)图像特征点提取。在图像中选取任意一个像素P,它的灰度值为Ip。设定一个合适的阈值。以像素P为中心,设置半径为3的一个离散化Bresenham圆,选取圆周上的16个像素点。如果圆上序号为1,5,9,13的像素亮度有3个同时都大于Ip+t或者小于Ip-t,则判定P可能为一个特征点,进行第2步,否则丢弃该点P。

(2)进一步判定圆上的12个连续的像素亮度值是否都大于Ip+t或者小于Ip-t,如成立则判定P为一个特征点,进行第3步,否则丢弃该点P。

(3)计算提取到特征点的Harris响应值并排序,选择前N个最大响应值作为最终特征点的集合。

(4)采用灰度质心法对提取到的特征点进行描述,增加特征点的旋转不变性。首先,图像块的矩定义如式(1)所示:

其中,I(x,y)为点(x,y)处的灰度值,p+q为灰度矩的阶数。要求x和y都在半径为r的圆形区域内,即x,y∈[-r,r].

通过图像块的矩,求出图像块的质心如式(2)所示:

连接图像块的几何中心O与质心C,得到一个方向向量,特征点的方向定义如式(3)所示:

(5)循环以上5步,对每一个像素执行相同的操作。

1.3 特征点描述子

ORB算法采用BRIEF描述子对提取到的特征点像素信息进行描述。BRIEF描述子描述方法为在特征点周围挑选指定数量的像素点对,通过比较相应的灰度值,利用一系列的0和1组合编码成以二进制形式描述特征。

对于一个光滑图像领域p的准则τ定义如式(4)所示:

其中,p(x)为平滑后的图像领域p在x处的灰度值,则特征可以被定义为n维二进制向量如式(5)所示:

其中,n可以为128、256、521等。n值大小的选取可以根据存储效率、识别率和速度的要求进行相应的选择。

由于BRIEF描述子不具有旋转不变性,因此对其进行改进并添加一个方向信息,称为rBRIEF。在位置(xi,yi)处,对任意的n个二进制特征,定义矩阵S如式(6)所示:

利用此区域的旋转方向θ和对应的旋转矩阵Rθ,对S进行变换如式(7)所示:

于是矫正后的BRIEF描述子为如式(8)所示:

得到校正的BRIEF之后,再进行贪婪搜索,在像素块中找出相关性最低的256个像素块对,作为最终的BRIEF。

2 ORB配准算法改进

2.1 ORB配准算法改进的总体思想

本文对ORB特征点的提取及配准算法分别进行改进,首先对待检测的图像采用区域二分法加速判断特征点在图像中的位置,然后对检测出来的特征点依次构建图像金字塔及引入灰度质心法以增加特征点的尺度不变性以及旋转不变性,最后采用改进的RANSAC配准算法剔除误匹配点对。改进的ORB配准算法整体流程如图4所示。

图4 改进的ORB配准算法整体流程图

2.2 FAST特征点提取算法改进方法

在特征点配准过程中,将相邻两张图像的非重叠区域视为无效区域,在无效区域中进行特征点的提取及配准是不正确的。如果在提取特征点时去除在无效区域的特征点提取、计算描述子及特征点匹配的时间,可以大大加速ORB算法的配准时间,从而提升V-SLAM算法框架的实时性。基于以上思想,提出FAST特征点提取的改进方法。首先,在特征点提取时对待提取的图像区域进行划分,将待提取特征点的图像均匀分成2个区域,并且进行分组编号。例如使用ORB算法提取一帧图像特征点的时间为T,则使用区域二分处理之后每块区域的特征点提取时间为t=T2,完成整帧图像的特征点配准所需要的时间t1为:

因为t1<2T,即提取每帧图像特征点的时间减少了25%。假设两帧图像的重叠率为x,可提高的效率为y,则:

所以不管x取值是多少,y的值总是不小于50%。即在ORB特征点提取过程中,采用区域二分法,特征点提取至少提高效率50%以上。

2.3 RANSAC算法改进方法

传统的RANSAC算法在剔除ORB特征点误匹配时没有考虑配准点的质量好坏便随机抽取,将提取出来的所有特征点都进行了迭代计算,导致特征点在配准过程中消耗了大量的时间。基于此问题,提出改进算法,将随机抽样的样本进行一次筛选,把明显错误的匹配对剔除,减少RANSAC的迭代次数。改进的RANSAC算法流程图如图5所示。

改进的RANSAC算法步骤如下:

(1)左图中提取到的特征点记作集合X={xi|xi∈X,i=1,2,...,n},与之对应的右图提取到的特征点记作集合Y={yi|yi∈Y,i=1,2,...,n}

(2)对集合X,Y中提取的特征点采用双向匹配交叉过滤方法对配准对进行筛选,过程如下:对集合X中的每个特征点xi找到集合Y中与之对应的特征点yi,同理,对集合Y中的每个特征点yi找到集合中X与之对应的特征点xi;同时引入逆向匹配机制,如果X中的特征点xi在Y中的匹配点为yi,且Y中的特征点yi在X中的匹配点为xi,则认为这对匹配对是正确的,如果匹配不成功,则直接剔除掉。

(3)设置一个描述子汉明距离的阈值,对筛选之后的配准点对进行汉明距离计算并排序,对汉明距离值大于设置的阈值的配准点对剔除。

(4)经过以上两步剔除误匹配之后,再使用RANSAC算法进行迭代配准特征点,从而得到更加准确的配准点对。

图5 改进的RANSAC算法流程图

3 实验结果及分析

3.1 实验安排

本节将改进的算法和原算法进行实验对比。实验环境:Ubuntu16.04操作系统,安装了OpenCV 3.1.0[14]。主要实验为:改进的FAST特征点提取算法对比实验和改进的RANSAC算法对比实验,并对实验结果进行比较和分析。为了验证本文提出的改进算法对环境具有普遍性、通用性,分别选取了室外场景和室内场景图片进行实验验证。

3.2 FAST特征点提取改进算法对比实验

为了验证本文提出的改进的FAST特征点提取算法的高效性,将分别选取像素大小为800×500的两幅室外和室内图片进行实验。首先,使用改进的FAST算法对采集到的图像进行特征点提取。然后,将改进算法与原算法提取到同一帧图像的特征点所用时间进行对比。图6所示为改进的FAST算法特征点提取室外场景图,图7所示为改进的FAST算法特征点提取室内场景图。

图6 改进FAST算法特征点提取室外场景图

图7 改进FAST算法特征点提取室内场景图

表1 FAST特征点提取算法耗时对比

表1为原FAST特征点提取算法和本文改进的FAST特征点提取算法处理同一帧图像特征点所用的时间对比。可以发现,使用改进的算法进行特征点提取时,处理的时间明显缩短,特征点提取效率提升40%左右。按照理论部分的结论,使用改进的算法提取特征点时,提取效率至少能提高50%,其主要原因在改进的FAST特征点提取算法中构建了图像金字塔以增加特征点的尺度不变性,浪费了一定的时间。实验表明,使用改进的FAST特征点提取算法可以大大提升特征点提取的速度。

3.3 RANSAC改进算法对比实验

为了验证本文提出的RANSAC改进算法对图像配准的高效性及准确性。选取像素大小为410×320的四幅室外和室内图片分别进行配准实验。首先,对待配准图像进行采集。图8(a)为待配准室外场景的左帧图像,图8(b)为待配准室外场景的右帧图像。图9(a)为待配准室内场景的左帧图像,图9(b)为待配准室内场景的右帧图像。其次,使用原FAST特征提取算法结合暴力匹配算法对采集到的室外和室内相邻场景图像分别进行特征点提取与配准。图10所示为原FAST算法结合暴力匹配算法的室外场景配准图,图11所示为原FAST算法结合暴力匹配算法的室内场景配准图。可以发现,暴力匹配算法将导致图像配准过程中出现大量的误匹配。然后,引入RANSAC算法剔除图像配准过程中出现的大量误匹配。图12所示为引入RANSAC算法的室外场景配准图,图13所示为引入RANSAC算法的室内场景配准图。可以发现,RANSAC算法可以有效的剔除暴力匹配中出现的大量的误匹配,但是还会存在少量的误匹配。最后,使用改进的FAST特征提取算法结合改进的RANSAC算法对采集到的室外和室内相邻场景图像分别进行特征点提取与配准。图14所示为改进的FAST算法结合改进的RANSAC算法的室外场景配准图,图15所示为改进的FAST算法结合改进的RANSAC算法的室内场景配准图。可以发现,使用改进的RANSAC算法可以进一步剔除原RANSAC算法遗留的误匹配对,进一步提升图像配准的准确性。同时,将改进的算法与原算法处理同一对图像的配准点集对数、剔误率、配准时间进行对比。

图8 室外场景待配准原始图像

图9 室内场景待配准原始图像

图10 FAST+暴力匹配算法室外场景准图

图11 FAST+暴力匹配算法室内场景准图

图12 FAST+RANSAC算法室外场景配准图

图13 FAST+RANSAC算法室内场景配准图

图14 改进FAST+改进RANSAC算法室外场景配准图

图15 改进FAST+改进RANSAC算法室内场景配准图

表2 室外场景配准算法结果对比

表3 室内场景配准算法结果对比

表2为FAST特征点提取算法结合暴力匹配算法、FAST特征点提取算法结合RANSAC算法、本文改进的FAST特征点提取算法结合改进RANSAC算法对采集到的室外场景图像进行配准结果的对比。表3为暴力匹配算法、FAST特征点提取算法结合原始RANSAC算法、本文改进FAST特征点提取算法结合改进RANSAC算法对采集到的室内场景图像进行配准的结果对比。可以发现,使用改进的FAST特征点提取算法结合改进的RANSAC算法进行图像配准时,虽然最终得到的配准点集个数略有减少,但是更有效地剔除了配准过程中出现的误匹配。在提升配准速度的同时,大大提升了配准的精确度。实验表明,使用改进的FAST特征点提取算法结合改进RANSAC的算法进行图像配准时,可以提升配准速度,同时能够有效地剔除误匹配,保证了配准点对的准确性。

4 结论

本文提出了一种改进的ORB图像配准算法。在原有算法的基础上,首先采用二分区域法对提取图像特征点时进行预处理,之后使用改进的RANSAC迭代算法完成特征点匹配。通过实验结果表明,改进的ORB配准算法在保证配准特征点数量相当的同时可以有效地剔除误匹配,保证了配准点集之间的准确性,同时提升了配准的速度。其改进的ORB算法给V-SLAM中的位姿估计算法提供了良好的初始值,其结果有助于提升V-SLAM系统的实时性和位姿估计及建图的准确性。ORB配准算法仍有许多难点,如特征点较少图像之间的配准、尺度变化图像之间的配准、旋转变化图像之间的配准等,这些难点还有待深入研究。

猜你喜欢
准点灰度像素
采用改进导重法的拓扑结构灰度单元过滤技术
像素前线之“幻影”2000
Bp-MRI灰度直方图在鉴别移行带前列腺癌与良性前列腺增生中的应用价值
准点
“像素”仙人掌
准点率前十,日本机场占五席
ÉVOLUTIONDIGAE Style de vie tactile
基于最大加权投影求解的彩色图像灰度化对比度保留算法
JAL获得世界航空公司准点率三冠王
高像素不是全部