一种改进的SIFT图像检测与特征匹配算法
杨雨薇1, 张亚萍1,2
1.云南师范大学 信息学院,云南 昆明 650500
2.云南大学 信息学院,云南 昆明 650500
通信作者:张亚萍(1979-),女,云南人,副教授,博士,主要研究方向为计算机图形学、并行计算.

作者简介:杨雨薇(1993-),女,江苏人,硕士生,主要研究方向为计算机图形学.E-mail:18287112897@163.com.

摘要

提出了一种改进的SIFT图像特征检测与匹配算法.以包含像素信息的深度图为基础,通过相应的映射关系,将深度图变成二维图像,再依据深度图每个网格顶点处的局部微分性质确定二维图像上的灰度值,得到二维灰度特征图像;利用SIFT算法对特征图像进行特征点的检测;然后将K近邻算法和双向特征匹配算法相结合,使得匹配得到的结果更加准确,误匹配对更少,并把匹配结果还原到深度图上;最后采用随机抽样一致性RANSAC算法对误匹配点对进行剔除,实现2幅图像的配准.实验结果验证了这种改进算法的鲁棒性和有效性.

关键词: SIFT算法; 双向匹配; RANSAC; 映射
中图分类号:TP391 文献标志码:A 文章编号:0258-7971(2017)03-0376-09
An improved SIFT image detection and feature matching algorithm
YANG Yu-wei1, ZHANG Ya-ping1,2
1.College of Computer Science and Information Technology,Yunnan Normal University,Kunming 650500,China
2.School of Information Science and Technology,Yunnan University,Kunming 650500,China
Abstract

An improved SIFT image feature detection and matching algorithm is proposed.Firstly,this paper is based on the depth map containing the pixel information.Through the corresponding mapping relation,the depth map is transformed into a two-dimensional image.And then the gray value of the two-dimensional image is determined according to the local differential property of each vertex of the depth map to get the two-dimensional gray feature image.Secondly,the SIFT algorithm is used to detect the feature points of the feature images.Thirdly,the K-nearest neighbor algorithm and the bidirectional feature matching algorithm are combined to make the matching result more accurate and fewer mismatching pairs,then restore the matching results to the depth map.Finally,the random sampling consistency RANSAC algorithm is used to eliminate the mismatching points,and the registration of two images is realized.The experimental results demonstrate the robustness and effectiveness of the improved algorithm.

Keyword: SIFT(Scale-Invariant Feature Transform); bidirectional matching; RANSAC(Random Sample Consensus); mapping

在计算机图像领域, 有一种非常有效的特征点检测与匹配算法, 它所提取的图像特征点能够对图像旋转、尺度缩放保持不变性, 对环境噪声也具有一定程度的稳定性.并且, 它所提取得到的特征点的数量大, 速度快, 精度高.这就是哥伦比亚大学David Lowe在1999年提出的尺度不变特征变换(SIFT)算法, 后来他又做了一些完善, 于2004年正式发表[1].现在SIFT算法被广泛应用于物体辨识、机器人地图感知与导航、三维重建等众多领域[2].利用尺度空间的方法对三维网格进行特征点的检测与匹配, 许多学者在这一方面做了研究并取得了一定的成果.Lee和Varshney等[3]利用不同尺度下的高斯核函数对平均曲率进行加权平均, 得到高斯加权平均曲率, 然后对相邻尺度间的高斯加权平均曲率求解差分方程, 运用非线性组合算子对差分进行求和, 这样就可以得到网格顶点处的特征值, 最后将特征值里的局部极值点定义为网格的特征点.Schlattmann等[4]在尺度空间图像角点检测算法的基础上, 通过保持体积不变的平均曲率流算法建立了三维网格上的尺度空间, 然后得到每个尺度下的特征值, 最后将局部极值点定义为网格的特征点.Novatnack和Nishino等[5]运用三维网格转化为二维图像的方法来检测网格上的特征, 首先将三维网格通过法矢映射为二维图像, 接着在二维图像上检测特征, 网格上对应的特征可以通过映射关系得到, 这种方法可以同时检测出三维网格上的特征点和特征线.但是, 上述的几种方法在对特征点进行匹配时, 会显得非常困难.吴楚等[6]利用极限约束基本矩阵改进SIFT特征匹配算法, 匹配精度大大提高.刘焕敏等[7]基于特征向量匹配对的唯一性约束, 提出了双向匹配的SIFT算法, 使得误匹配率降低.李刚等[8]利用视差梯度约束和特征点筛选的方法, 在双向匹配SIFT算法的基础上, 更好地降低了误匹配点对.所以本文利用改进的双向SIFT(Scale-Invariant Feature Transform)算法进行匹配.

本文提出的特征点检测与匹配算法是基于深度图而言的, 深度图中含有大量的像素信息, 通过相应的映射关系, 将深度图转化为二维灰度特征图像.接着对特征图像进行特征点的检测.针对常见的误匹配情况, 本文的算法中加入了特征点的双向匹配, 并结合RANSAC算法(Random Sample Consensus)去除误匹配, 从而得到较好的结果.

1 改进的匹配算法

SIFT算法的基本内容为4步:尺度空间极值检测、关键点定位、方向确定、关键点描述.其实质是在不同的尺度空间上查找特征点, 并计算出特征点的方向.对于含有大量像素信息的深度图来说, SIFT算法检测出来的特征点数量较少, 会遗漏很多图像信息, 并且单向匹配时存在误匹配点对的数量比较大, 结果如图1所示.针对这些问题, 本文提出了改进的SIFT图像特征检测与匹配算法, 具体过程主要有:深度图转化为特征图像、特征点检测、特征点匹配、去除误匹配.

图1 深度图特征检测与匹配结果Fig.1 Depth map feature detection and matching results

1.1 深度图转化为特征图像

对深度图进行特征提取, 由于受到角度位置和景深的影响, 会使提取到的特征点数量较少, 如图2(a)所示(特征点个数是278).为了解决这一问题, 我们通过相应的映射关系, 将深度图变成二维灰度特征图像, 然后再用SIFT算法进行特征点的检测和匹配, 如图2(b)所示(特征点个数是294).下面详细介绍如何将深度图转化为特征图像.

图2 深度图和特征图像上的特征点Fig.2 Feature points on depth map and feature image

首先用V(x, y, z)来表示一幅深度图在空间中所有点的坐标, Q(x, y)表示深度图投影到相机平面上的点的坐标, 计算空间中V(x, y, z)对应的像素包围盒Box(Qmin, Qmax)的范围, 创建与包围盒大小一样的深度图的特征图像R(x, y), 则深度图V(x, y, z)与特征图像R(x, y)存在一种映射的关系.

f:VR, Vi(xi, yi, zi)→ f[Vi(xi, yi, zi)]=Ri(xi, yi, zi)=Qi(xi, yi, zi)-Qmin, (1)

f为深度图到特征图像转换的映射关系, 包围盒Box所对应的QminQmax分别代表对角点的2个坐标.

本文计算出空间中任意一点Vi(xi, yi, zi)处的曲率, 然后利用公式(3)转换成灰度值, 应用在特征图像上, 这样可以保证特征图像完全反映出深度图的特征.

其次, 对深度图V(x, y, z)进行三角形网格化, 并且估算出每个顶点处的法向量.本文在以网格顶点为圆心, 2为半径的区域内计算平均曲率和高斯曲率[9], 记每个顶点的坐标为v(x, y, z), Kp(v)表示平均曲率, Kg(v)表示高斯曲率, 具体公式如下:

F(v)= Kp2(v)-λKg(v)2, (2)

λ 为特征参数, 根据经验, λ 的取值范围在[0.3, 0.7] 时, 特征点正确匹配对数较多, 所以本文选取λ =0.45, 这样得到的实验结果为最佳.F(v)是得到的特征曲率, 用如下公式可转换为该点处的灰度值:

IR(r)= 2551-(F(f-1(r))-Fmin)(Fmax-Fmin), rR; 255, rR.(3)

IR(r)为特征图像上每一点的灰度值, f-1(r)为特征图像到深度图的反向映射关系, FmaxFmin表示特征曲率F(r)在该范围内的最大值和最小值.

1.2 特征点检测 首先定义G(x, σ )为尺度空间因子σ 的二维高斯函数:

G(x, σ )= 12πσ2exp -(x2+y2)2σ2. (4)

相对应的高斯拉普拉斯函数(LOG)为:

2G(x, σ )= 2x2+2y2G(x, σ )=Gxx(x, σ )+Gyy(x, σ ), (5)

其中, Gxx(x, σ )= 2x2G(x, σ ).

特征图像I(x)在LOG下的响应函数为:

I(x)* 2G(x, σ )=Ixx(x, σ )+Iyy(x, σ ), (6)

其中, * 表示空间卷积运算符, Ixx(x, σ )=I(x)* Gxx(x, σ )是对高斯运算符的响应函数.IyyIxy也是类似的定义.

然后, LOG对于盘形特征点区域具有类似于滤波的效果, 当高斯尺度空间因子σ 和特征区域半径r满足这样一种关系:σ = r2时, 特征区域中心x0获得局部最大响应函数:

maxx, σI(x)* 2G(x, σ )= I(·)* 2G., r2(x0). (7)

根据热动力方程原理, 方程(5)可以近似为高斯差分方程(DOG):

2G(x, σ )≈ G(x, 2σ)-G(x, σ)σ22-σ2. (8)

将公式(8)代入公式(6)简化结果为:

I(x)* 2G(x, σ )≈ I(x)* G(x, 2σ)-I(x)* G(x, σ)σ22-σ2. (9)

因此, DOG的局部极值点被认为是SIFT算法识别的特征点.

定义Gx(x, σ )= xG(x, σ )和Gy(x, σ )= yG(x, σ ).

经典的SIFT算法描述符是基于梯度强度M(x, σ )和方向θ (x, σ )的:

M(x, σ )= Ix(x, σ)2+Iy(x, σ)2, (10)

θ (x, σ )=arctan Iy(x, σ)Ix(x, σ),

其中, Ix(x, σ )=I(x)* Gx(x, σ ).

SIFT算法特征点描述符是以向量的形式表示的:

U(x, σ )= U1(x, σ)TU1(x, σ), , UK(x, σ)TUK(x, σ)T, (11)

其中包括了K个特征点描述子UK(x, σ ), 每个特征点描述子是由一系列子区域内计算的M(x, σ )加权定向直方图组成, 如下面定义:

A1, …, ANN个定向直方图的系数, 具体定义为:

lA(θ )= 0, θA; 1, θA.(13)

相对于主角的重新分配定向角, θ 使得该加权的直方图保持旋转不变性.公式(11)保证了该直方图的光照不变性.

1.3 特征点匹配

传统的SIFT特征点匹配方法是根据2幅图像中关键点的欧式距离来进行配对, 在匹配时比较与关键点的特征向量最近的和次近的关键点, 即选取一幅图像中的某个关键点, 然后找到它与另一幅图像中欧氏距离最近的前2个关键点, 在这2个关键点当中, 若最近距离除以次近距离的比值比某个比例阈值小, 那么这一对匹配点就是可接受的.对于含有大量像素信息的深度图来说, SIFT算法检测出来的特征点数量较少, 会遗漏很多图像信息, 并且单向匹配时存在误匹配点对的数量比较大.

本文采用改进之后的双向KNN匹配算法, 使得匹配的结果更加精确.双向匹配算法的基本思想是对每一组二维图像进行2次单向的特征点匹配, 在这2次匹配中的二维图像的顺序是相互交换的, 然后提取出2次匹配后特征点集的交集部分, 也就是取出坐标值完全相同的所有特征点, 将坐标值不完全相同的特征点剔除, 如图3所示.

图3 老鼠的双向匹配示意图Fig.3 Schematic diagram of two-way matching of mice

具体而言, 对于2个特征点集来说, 求出第1个特征点集里每一个特征点在第2个特征集中对应的匹配点, 也就是求出第1个特征点集中每一个关键点在第2个特征点集中的最近邻NN(Nearest Neighbor)和次近邻SCN(Second Closest Neighbor)的距离比率NN/SCN, 当距离比率NN/SCN小于或等于匹配阈值ratio时, 这时的对应点便认为是正确匹配, 否则便会被作为错配点而剔除.因而匹配阈值ratio的值的选取十分关键, 经过对大量任意存在尺度、旋转和亮度变化的2幅图片进行匹配, 结果显示ratio取值在0.4~0.6最理想.ratio的值若小于0.4, 则会出现匹配对数很少或者没有的情况, 若ratio的值大于0.6, 则匹配对数很多, 同时也存在大量的错配点.本文在双向匹配时选取的阈值为0.4.

在求取SIFT特征向量的时候, 同一个点可能对应着多个方向, 因而属于不同的特征点[10], 它们之中的全部或者部分点可能产生正确的匹配对.但是事实上, 它们是同一个点, 因而需要依据像素的坐标值去除上述重复的匹配点, 运用双向匹配算法便可有效地去除这样的大部分重复匹配点.

1.4 去除误匹配

随机抽样一致性算法(RANSAC)是有效剔除图像误匹配的算法之一[11], 因此被广泛应用.

在本文中首先定义如下参数:初始最大内点(本文指精确匹配点)数max_inliner=0, 反投影误差阈值threshold的取值一般为0.001~0.01, 最大循环次数max_circle=1000, numof_inliner为当前基础矩阵F所对应的内点数, 通过矩阵F所计算出来的对称变换误差为di.

假设2幅二维图像中的一对特征点mi=(u, v, 1)T, m'i=(u', v', 1)T, 变换矩阵F满足方程

[u'i v'i 1] F11F12F13F21F22F23F31F32F33uivi1=0, (14)

通过归一化线性变换估计出变换矩阵F.计算mi进行变换后得到的坐标到m'i的距离d(m'i, Fm'i)2, 同时对m'i做相同的计算得到距离d(mi, F-1m'i)2.

di=d(m'i, Fmi)2+d(mi, F-1m'i)2. (15)

指定一个阈值threshold, 当对应点的对称变换误差di小于该阈值时, 认为这对点是符合模型的内点.

本文RANSAC算法的具体思想是:

(1) 输入2幅平面图像中的初始匹配点对;

(2) 初始化相关的参数;

(3) 从样本集中任意抽取4对匹配点对, 确保他们不在一条直线上, 这作为初始的随机样本, 根据归一化线性变换求取局部变换矩阵F中的8个对应的未知参数;

图4 算法流程图Fig.4 Algorithm flow chart

(4) 通过计算出的局部F来求取特征点对的反投影误差距离di, 统计当满足di< threshold时, 内点的个数numof_inliner+1, 若numof_inliner≥ max_inliner, 则用局部F替代当前F, 并且更新最大内点的数量;

(5) 依据所有内点数重新计算变换矩阵F;

(6) 得到2幅平面图像之间的变换矩阵F.

算法流程如图4所示.

RANSAC算法在把循环次数置为无穷大的条件下, 可从包含很多的错误点对的点集中较为稳定地估算出对应模型的参数, 在本文中, 把最大循环次数设为1000, 在进行了1000次循环后必然能估计出非常稳定的模型参数, 并且达到去除外点的目的.

2 实验与结果分析

本文对开源的SIFT算法进行了改进, 首先将深度图转化为特征图像, 然后进行特征点的提取, 双向匹配得到更加准确的匹配对数, 从而应用在原始深度图上, 最后通过随机抽样一致性算法(RANSAC)对深度图上的匹配对数进行提纯.本文的具体实现步骤如下:

步骤1:将输入的两幅深度图I1、I2转化为特征图像T1、T2;

步骤2:对特征图像T1、T2进行特征点的提取;

步骤3:计算特征图像T1到T2单向匹配得到的匹配对集合P1; 然后计算特征图像T2到T1单向匹配得到的匹配对集合P2;

步骤4:求P1、P2的交集, 即双向匹配的匹配对集合A;

步骤5:将点集A还原到深度图上;

步骤6:通过RANSAC算法去除误匹配, 得到最终的匹配对集合B.

为了验证本文的改进算法在获取准确匹配对数时的有效性, 我们进行了大量的实验.实验的环境是主频3.4GHz、内存为4.0GB的Windows7、64位操作系统的戴尔PC机, 开发工具是Microsoft Visual Studio 2012, 开发语言是C++和OpenCV2.2.

为了将原始SIFT算法与本文改进SIFT算法进行对比, 我们选取了3种不同类型的模型, 分别运用原始SIFT算法和本文改进SIFT算法进行特征点的检测和匹配, 实验结果说明了本文改进之后的算法具有较为广泛的适用范围.

实验一, 我们分别选取了工业用的钣金、佛陀以及花瓶作为模型, 用SIFT算法分别对深度图及特征图像检测特征点, 实验结果如图5(a)~(c)所示, 表1列举了检测到的特征点数.

图5 特征点检测结果图Fig.5 Feature points detection results

表1 特征点检测结果 Tab.1 Feature point detection results

实验2, 对钣金、佛陀和花瓶模型的特征图像进行双向匹配, 匹配结果如图6(a)~(c)所示, 表2列举了SIFT算法单向匹配对数和本文改进算法双向匹配对数.

实验3, 双向匹配之后的点对, 仍然存在较多的误匹配点, 运用RANSAC算法对深度图上的点进行剔除, 图7是SIFT算法与本文加入误匹配剔除算法的结果之间的对比, 表3列举了SIFT算法最后匹配对数和本文改进算法最后的匹配对数.

图6 特征图像双向匹配Fig.6 Feature image bidirectional matching

表2 特征图像匹配对数 Tab.2 Feature image matching pairs

图7 SIFT算法(左)和本文加入误匹配剔除算法(右)结果的比较Fig.7 SIFT algorithm(left) and the comparison of the results of the error matching elimination algorithm in this paper(right)

表3 最终匹配对数 Tab 3 Final match logarithm

通过以上3组实验可以知道:

(1) 当特征图像上的细节内容比较丰富时, 得到的特征点的个数比较多, 相应的特征点的匹配对数也会比较多, 例如佛陀模型和花瓶模型; 相反, 特征图像上的细节内容比较少时, 得到的特征点的个数就会减少, 相应的特征点的匹配对数也会较少, 例如钣金模型.

(2) SIFT算法直接对深度图提取特征点, 得到的数量较少; 反之, 先将深度图转化为特征图像, 再用SIFT算法提取特征点, 得到的数量会比较多.SIFT算法对特征图像进行单向匹配之后, 由于景深、位移等因素, 会存在较多的误匹配点对.本文采用双向匹配, 取2次匹配的交集, 虽然可能会去掉个别正确的匹配对, 但是这样得到的结果更加准确.最后, 对双向匹配之后的点对进行误匹配剔除.各项数据均优于SIFT算法, 说明本文改进算法是稳定有效的.

(3) 2幅特征图像公共部分的大小和形状, 会对最终正确的特征点匹配对数产生影响, 公共部分范围越大, 形状越平滑, 则得到的特征点匹配对数越多; 反之则越少.

3 总结

本文以含有像素信息的深度图为基础, 提出了一种改进的SIFT图像检测与特征匹配算法.基于原始SIFT算法, 将深度图的配准问题转化为特征图像上的特征点检测与匹配问题, 通过双向匹配方式, 并结合RANSAC算法对误匹配点进行剔除, 使用3组不同类型的模型进行了实验验证.实验结果表明, 本文改进算法具有较强的鲁棒性并且适用范围广.下一步的研究方向是将本文的匹配结果进行进一步提纯, 使其能够应用在文物的修复等领域.

The authors have declared that no competing interests exist.

参考文献
[1] LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110. [本文引用:1]
[2] MIKOLAJCZYK K, TUYTELAARS T, SCHMID C, et al. A comparison of affine region detectors[J]. International Journal of Computer Vision, 2005, 65(12): 43-72. [本文引用:1]
[3] LEE C H, VARSHNEY A, JACOBS D W. Mesh saliency[J]. ACM Transactions on Graphics, 2005, 24(3): 659-666. [本文引用:1]
[4] SCHLATTMANN M. Intrinsic features on surfaces[C]. Proceedings of the 10th Central European Seminar on Computer Graphics, Vienna, 2006: 169-176. [本文引用:1]
[5] NOVATNACK J, NISHINO K. Scale-dependent 3D geometric features[C]. Proceedings of the 11th IEEE International Conference on Computer Vision, Riode Janeiro, 2007: 14-20. [本文引用:1]
[6] 吴楚, 刘士荣, 杨帆. 基于极线约束的SIFT特征匹配算法研究[C]. 中国过程控制会议, 2011: 1173-1178.
WU C, LIU S R, YANG F. Research on SIFT feature matching algorithm based on epipolar constraint[C]. China Process Control Conference, 2011: 1173-1178. [本文引用:1]
[7] 刘焕敏, 王华, 段慧芬. 一种改进的SIFT双向匹配算法[J]. 兵工自动化, 2009, 28(6): 89-91.
LIU H M, WANG H, DUAN H F. An improved SIFT bidirectional matching algorithm[J]. Ordnance Industry Automation, 2009, 28(6): 89-91. [本文引用:1]
[8] 李刚, 曾荣盛, 韩建涛, . 基于双向SIFT的未标定图像的立体匹配[C]. 第四届全国信号和智能信息处理与应用学术会议论文集, 2010: 253-257.
LI G, ZENG R S, HAN J T, et al. Stereo matching of uncalibrated images based on bidirectional SIFT[C]. Proceedings of the Fourth National Conference on Signal And intelligent Information Processing and Applications, 2010: 253-257. [本文引用:1]
[9] DONG C S, WANG G Z. Curvatures estimation on triangular mesh[J]. Journal of Zhejiang University-Science A, 2005, 6(1): 128-136. [本文引用:1]
[10] 阮小丽, 陈庆虎, 邱益鸣, . 基于不变因子的SIFT误匹配点剔除及图像检索[J]. 红外技术, 2015, 37(7): 560-565.
RUAN X L, CHEN Q H, QIU Y M, et al. SIFT mismatching points elimination and image retrieval based on invariant factor[J]. Infrared Technology, 2015, 37(7): 560-565. [本文引用:1]
[11] WU X, ZHAO Q, BU W. A SIFT-based contactless palmprint verification approach using iterative RANSAC and local palmprint descriptors[J]. Pattern Recognition, 2014, 47(10): 3314-3326. [本文引用:1]