基于改进SURF和RANSAC算法的室内环境图像匹配

符秀辉, 周文俊, 赵茂鑫

(沈阳化工大学 信息工程学院， 辽宁 沈阳 110142)



基于改进SURF和RANSAC算法的室内环境图像匹配

符秀辉, 周文俊, 赵茂鑫

(沈阳化工大学 信息工程学院， 辽宁 沈阳 110142)

针对移动机器人在室内环境下定位及地图创建要求，比较SURF特征算法以及随机抽样一致性(RANSAC)算法各自优势，设计实现以改进SURF及RANSAC相结合的室内图像匹配方法.初始阶段，采用SURF算法提取图像特征，利用双向K最近邻分类法筛选提取到的特征点进行特征预匹配；再利用RANSAC算法对预匹配结果进行优化，剔除误匹配对，完成对图像的匹配矫正；最终得到准确的匹配图像.实验结果表明，此方法提高了匹配的正确率，也缩短了匹配时间，提高了匹配效率.

室内环境； SURF算法； 随机抽样一致性； 双向匹配； 图像匹配

图像匹配技术在数字图像领域是重要内容，其在诸如遥感成像、医疗检测、机器人定位、人脸匹配等领域有着广泛运用.而在移动机器人定位与地图创建中，针对室内环境中的目标定位和识别，需要对室内图像进行准确匹配.目前，在图像匹配方法中，已提出了多种特征点及匹配方式，例如Harris算子[1]、Moravec算子[2]及SIFT算子[3]等都是目前常用的特征点提取算子.这种稳定的图像特征，能够对产生几何位移、光照变化或者视角改变的图像进行匹配，对运动目标、及物体遮挡等因素也有较好的抗干扰效果[4].然而SIFT算子需要花费较长的检测时间[5].SURF算法[6]与SIFT算法类似，都具有对图像尺度和旋转的鲁棒性，且对图像的模糊及旋转处理得更好.但传统SURF算法存在计算量较大、匹配正确率较低的缺陷.针对室内环境中目标定位和识别的要求，为解决上述算法存在的不足，本文提出一种改进SURF和RANSAC算法相结合的室内环境图像匹配方法.经过改进后的匹配算法可提高室内图像匹配正确率，并提升匹配速度.

1 SURF特征描述

SURF特征检测分为特征点的提取和生成SURF特征描述.

1.1 特征点提取

SURF以Hessian矩阵判别局部极大值的方式提取特征点，Hessian矩阵：

(1)

式中：Lxx(x,σ)、Lxy(x,σ)和Lyy(x,σ)表示特征点在x点和y点处二阶高斯偏导数.Hessian矩阵行列式定义如下：

(2)

在文献[6]中为了提高卷积的计算速度，提出了一种方格型滤波器来近似替代卷积用的高斯二阶导数，以加速图像卷积的计算过程.其方格滤波器如图1所示，不同方向上的方格滤波器分别记为Dxx、Dyy、Dxy。

图1 9×9方格滤波器

使用方格型滤波器，使得矩阵形式变为：

det(H)=DxxDyy-(0.9Dxy)2

(3)

用Hessian矩阵求得图像尺度极值后，利用极值点3×3×3的领域进行非极值抑制，构建多尺度金字塔.利用不同的模板大小，可以形成多样的尺度特征金字塔图像，完成对特征点极值点的搜索[7].在不同尺度上寻找特征点，最后得到稳定的SURF特征点.

1.2 SURF特征点描述

利用关键点的领域信息生成关键点描述子，该描述子即为关键点的特征[8].根据描述子来判断计算两个关键点远近，即是否为同一个关键点.

若要SURF描述子符合旋转不变性，第一步需要确定描述子的主方向，以特征为圆心，6S(S为特征点的尺度)为半径的领域作为在x和y方向的Harr小波响应，利用直方图计算统计领域内各点的梯度大小和方向；然后结合全部内核方向内的Harr小波响应，两者相加，最后形成针对局部方向的新向量，找到最大分布角度作为描述子的方向.

以特征点为中心构造长为20S的矩形区域作为特征区域，并划分为4×4的子区域，以每个区域大小为5×5的像素集合作为采样区域，在这些采样区域内计算x和y方向上的小波响应，其结果记为dx和dy[9].如图2所示，提取四维特征向量：

V=(∑dx,∑|dx|,∑dy,∑|dy|).

所有子区域向量构成该点长度为4×4×4=64维的SURF特征描述符，具有旋转、尺度不变性及光照不变性，能够从图像中提取丰富而稳定的特征点.

图2 SURF特征描述符构成

2 匹配改进

2.1 改进SURF算法进行匹配

在图像匹配过程中,传统SURF特征点对于图像的描述信息已十分充足.SURF 特征算法对于图像的几何变换具有不变性，对光照的变化也有一定抗干扰性，只需对图像的SURF特征量进行分析计算，就可以获取图像关联信息，进行图像之间匹配[5].但SURF算法稳定性较差，不稳定的特征点常会被检测出来，会出现大量多余计算，降低匹配正确率和匹配时间.

针对以上问题，为提高匹配效率，本文对SURF算法进行了改进，以解决在实际过程中产生的匹配错误，提高图像匹配效率.主要算法实现如下：首先将采集到的图像1和图像2进行SURF特征匹配，提取初步特征点.然后在初匹配之后，引入双向K最近邻分类进行SURF特征点的筛选，得到最近距离的匹配点对，最近距离为欧式距离判断：

(4)

式中:xik是第一幅图其第i个特征第一矢量的第k个元素，xjk是第一幅图其中第j个特征对应特征矢量的第k个元素，n称为特征矢量的维数

K近邻分类，一种较为成熟的数据分类方式[10]. 利用投票机制，以若干离新样本为已知的最近样本，利用投票机制进行新样本甄别[11].

可表述为：若样本集SN={(x1,ω1),(x2,ω2),…,(xn,ωn)},xi是样本i的特征向量，ωi其是对应的类别，其中i∈{1,2,…,m}.若两个样本之间距离d(xi,xj)，则采用欧式距离d(xi,xj)=‖xi-xj‖.再对每个样本x在n个样本的前k个近邻进行识别，令只有ki个属于ωi类，这个类的判别函数：

gi(x)=ki, i∈{1,2,…,m}

(5)

其决策规则为：

(6)

输入待匹配图像1和图像2.首先，寻找图像1在图像2中对应到的最佳匹配特征点，然后再针对图像2在图像1中去寻找其最佳匹配特征，这样对于每个特征点，都会拥有2种不同视角的多个候选匹配点，基于描述子距离的值.每一个特征点均拥有2个候选匹配点，是基于描述子间距离的2个值，通过判断最优值和次优值距离之间的比率，对匹配点进行过滤.如果最优值的测量距离十分小，次优值又十分大，则选择最优值.反之，若二者差别不大，那么滤过此匹配对.双向特征匹配提高了SURF特征匹配的正确率，并减少了匹配时间.改进的图像预匹配流程如图3所示.

图3 图像匹配流程

2.2 RANSAC算法进行匹配矫正

为解决改进的SURF算法[12]在进行特征预匹配后,结果中仍存在着错误的匹配对，需要对这些误匹配对进行剔除工作，以便得到准确的匹配对.因此，本文引入RANSAC分类方法[13]再次对图像进行匹配矫正.

以给定点拟合直线举例，随机选取两个点，以这两个点来确定一条直线，称直线的支撑是其一定距离范围点的个数，计算支撑点的集数[14].多次抽样对参数进行评估，在每次随机抽样中选取数据确定模型的参数，根据估计参数对数据分类[15].允许误差内的数据，为之内点；误差外数据，为外点.RANSAC分类具有50 %的容错率，是一种鲁棒性很高的估计方式.

利用RANSAC方式筛选错误匹配对后，计算得出匹配图像间的坐标变换关系，求出变换矩阵，通过变换矩阵寻找到一幅图像中的点在另外一幅图像中的具体位置，见式(7).

(7)

本文RANSAC算法实行如下步骤：

(1) 设定初始内点数目为0个.从预匹配特征点中随机抽样出4对进行方程组构建，求解出变化矩阵的4组未知的参数值.

(2) 对其余对特征点经过矩阵M和预匹配点间的距离坐标进行计算，其中是一对预备匹配点.

(3) 如果小于设定阈值，则这个预备匹配点是内点，反之就是外点.

(4) 统计当前变换矩阵的内点数量，并对其进行更新.

(5) 选择另外4对预备匹配点，重复(1)到(4)，当内点最多，误差最小时停止.

在引入RANSAC算法后，进一步剔除了由改进SURF特征预匹配所产生的错误匹配对.估算出图像间的矩阵参数，从而确定图像1特征点在图像2或图像2特征点在图像1中的准确位置，得到最终匹配结果.

3 实验分析

以VS2010为实验环境验证方法的实际效果.以多组室内图像作为实验数据，进行匹配实验.实验图像为640×360像素大小的4组图像，前3组图像分别于不同室内场景、不同光源条件和不同拍摄角度下获得，第4组图像由第1组图像加入椒盐噪声获得，如图4所示.

图4 测试图像

3.1 实验结果

算法改进前与算法改进后的图像匹配数据结果见表1.

表1 匹配数据统计

算法改进前与算法改进后的图像匹配效果如图5所示.

图5 实验结果

3.2 实验结果分析

从表1可以看出：在对传统SURF匹配算法改进前，实验图像的匹配会产生大量的误匹配点数，且匹配时间较长.而在对传统SURF匹配算法改进后，从实验图像的匹配效果中能看出，大量误匹配点数被剔除，且匹配时间减少，匹配效率得到了提高.从整体效果上看，传统SURF算法匹配得到的匹配点对数会随着外界条件变化而变化，匹配的正确率也随之降低.而对传统SURF匹配算法进行改进后，并将其与RANSAC算法相结合，在不同外界条件下，改进后的匹配算法均能很好的剔除错误的匹配点，提高匹配的正确率.

第1组实验中，两幅图像在自然光源下，室内场景内物件单一，实验得到的效果良好；第2组实验中，两幅图像在外界光源干扰下，且室内场景内物件较多环境较复杂，实验效果没有第1组实验效果好；第3组实验中，图像拍摄角度不同，室内环境单一，无外界光源干扰，得到的效果最好；第4组实验中，在第1组实验图像中加入噪声干扰，在噪声干扰下实验效果下降但识别率仍较高.从4组实验中可知，改进后的匹配算法拥有很好的抗外界干扰能力，识别的正确率得到较大提升，缩短了匹配时间，从而提高了匹配效率.实验结果体现出本文方法对室内环境图像的良好匹配，能在室内环境图像匹配中取得较好匹配效果.

4 结 论

针对传统SURF算法存在的计算量较大、匹配正确率较低的缺陷，为提高室内环境图像的匹配效率.对传统SURF算法进行改进，并与RANSAC算法相结合，提出了一种适用于室内环境图像的匹配方法.实验结果表明：这种匹配方法对室内的不同复杂环境，不同光照条件及不同拍摄角度条件下的图像匹配有较好的效果.能够解决传统方式下单一使用SURF特征算法所产生的匹配失误，提高了在室内环境下图像匹配效率.随着进一步的研究与实验，可应用于现阶段移动机器人在室内环境下定位及地图创建.

[1] HARRIS C J,STEPHENS M.A Combined Corner and Edge Detector[C]//Proceedings of the 4th Alvey Vision Conference.Manchester:[s.n.],1988:147-151.

[2] MORAVEC H P.Rover Visual Obstacle Avoidance[C]//Proceedings of the 7thInternational Joint Conference on Artificial Intelligence.Vancouver[s.n.],1981:785-790.

[3] LOW D G.Distinctive Image Features from Scale-invariant Key Points[J].International Journal of Computer Vision,2004,60(2):91-110.

[4] 刘佳,傅卫平,王雯,等.基于改进SIFT 算法的图像匹配[J].仪器仪表学报,2013,34(5):1107-1111.

[5] 赵璐璐,耿国华,李康,等.基于SURF和快速近似最近邻搜索的图像匹配算法[J].计算机应用研究,2013,30(3):921-923.

[6] BAY H,ESS A,TUYTELAARS T,et al.Speeded-up Robust Features(SURF)[J].Computer Vision and Image Understanding,2008,110(3):346-359.

[7] 陈艺虾,孙权森,徐焕宇,等.SURF算法和RANSAC算法相结合的遥感图像匹配方法[J].计算机科学与探索,2012,6(9):822-828.

[8] 刘奇,何明一.基于SURF特征匹配的图像拼接算法[J].测控技术,2010,29(10):27-31.

[9] 罗文超,刘国栋,杨海燕.SIFT 和改进的 RANSAC 算法在图像配准中的应用[J].计算机工程与应用,2013,49(15):147-149.

[10]COVER T,HART P.Nearest Neighbor Pattern Classification[J].IEEE Transaction on Information Theory,1967,13(1):21-27.

[11]薛开,李强,徐贺,等.基于振动采用k-近邻法的机器人地形分类[J].振动、测试与诊断,2013,33(1):88-92.

[12]符秀辉，周文俊，赵茂鑫.基于改进SURF算法的室内环境图像快速拼接[J].计算机技术与发展,2015,25(8):39-42.

[13]FISCHLER M A,BOLLES R C.Random Sample Consensus:A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography[J].Communication of the ACM,1981,24(6):381-395.

[14]曲天伟,安波,陈桂兰.改进的RANSAC算法在图像配准中的应用[J].计算机应用,2010,30(7)：1849-1951.

[15]常青,张斌,邵金玲.基于SIFT和RANSAC的特征图像匹配方法[J].华东理工大学学报(自然科学版),2012,38(6):747-751.Indoor Environment Image Matching Based on Improved SURF and RANSAC Algorithm

FU Xiu-hui, ZHOU Wen-jun, ZHAO Mao-xin

(Shenyang University of Chemical Technology, Shenyang 110142, China)

In view of the requirements of binocular vision robot localization and navigation in the complex indoor environment,and compared the advantages of Speeded-Up Robust Features and Random Sample Consensus,and a matching method of indoor environment image put forward based on SURF and RANSAC algorithm.Firstly,feature of images deteced and pre-matched by using SURF.Secondly,using RANSAC algorithm to optimize the matching process,complete the correction of image matching and eliminate false matching.Last,get the images.The experiment verified the feasibility of the method,also has a good application effect in the indoor environment.

indoor environment; speeded-up robust features; random sample consensus; bidirectional matching; image matching

2015-03-23

国家自然科学基金资助项目(51375477)

符秀辉(1963-)，男，辽宁沈阳人，博士，教授，主要从事机器人控制及遥操纵机器人环境建模的研究.

2095-2198(2016)03-0262-05

10.3969/j.issn.2095-2198.2016.03.015

TP391.41

A