移动平台上四邻域梯度阈值的SIFT匹配优化

雷俊锋，郭 勇，肖进胜，朱月苓，张 存

（武汉大学 电子信息学院，湖北 武汉430072）

0 引 言

SIFT算法［1，2］存在计算量大、实时性差等缺点。很多学者在SIFT的基础上做出了改进，Calonder M.等基于SIFT提出了BRIEF算法［3］，提高了运算速度，但抗旋转和多尺度效果不明显；Rublee E.等在BRIEF的基础上提出的ORB算法［4］，一定程度上增强了BRIEF的抗旋转性能；Faraj A.等将SIFT特征点增加角度特征［5］，根据角度特征将特征点分类，以提高匹配效率；徐阳等，在SIFT的极值点检测时增加自适应阈值［6］，根据图像情况，生成适当数目的极值点，减少图像中特征点的数目，进而降低匹配运算量。有些学者借助于多核CPU、GPGPU和FPGA等硬件设备实现算法加速。基于多核CPU的SIFT算法［7］和基于GPGPU的SIFT算法［8］主要使用大量的并行计算以提高运算速度；基于FPGA的SIFT算法［9］利用并行FPGA资源以提高运算速度。

近几年随着移动平台的飞速发展，移动设备的数据处理能力越来越强大，将优秀的算法移植到移动端是一种趋势，这也极大方便了复杂算法在仪器仪表等便携式设备上的使用。很多学者利用移动处理器的特点，使用移动GPU和CPU将复杂算法在移动端实现，G.－R.Kayombya对SIFT算法在Z400系列高通移动GPU上的实现做了研究［10］。K.－T.Cheng等对面部识别算法在移动 GPU上的实现做了研究［11］，与移动CPU相比速度有所提升，却牺牲了一定的运算精度。Rister B.等在G.－R.Kayombya的基础上，对SIFT算法在移动GPU上进行了一定的优化［12］。对于SIFT特征点生成这一阶段，他们的工作在一定程度上优化了算法在移动平台上的实现效率，但是由于目前移动设备及编程语言的限制，SIFT算法的匹配阶段还无法借用移动处理器的GPU优化匹配效率，只能通过理论方面的优化实现匹配阶段的加速。

针对上述算法的缺点和不足，本文提出了一种四邻域梯度值分组的匹配方法，将特征点与周围4个点的梯度值作为特征之一，在匹配之前对特征点对的主梯度值关系进行判断，只将符合条件的点进行匹配运算，相当于减少了大量的特征点，提高了匹配效率。

1 SIFT算法的基本原理

SIFT算法是通过提取图像局部特征以实现图像间准确的匹配，它在尺度空间上寻找极值点，提取图像的特征不变量，以此构成图像的特征描述符。主要过程为：①建立多尺度空间。②极值点检测及定位。③确立特征方向。④计算特征描述子。⑤特征点匹配与错误剔除。

1.1 建立多尺度空间

一幅二维图像，在不同尺度下的空间表示可由图像与高斯核空间域卷积得到，如式 （1）所示

式中：G（x，y，σ）——尺度可变的二维高斯函数；＊——卷积运算；I（x，y）——待处理图像，表示图像的尺度空间。Lowe提出了高斯差分函数算子 （difference of Gaussian，DoG）对原始图像进行卷积计算，以有效的在尺度空间检测稳定的关键点，如式 （2）所示

式中：k——不同的高斯核尺度，k的初始值为1，尺度以k倍递增。

1.2 尺度空间极值点检测及精确定位

在高斯差分空间中，选择中间的几层图像，将图像的每个点和同一尺度上周围的8个点以及上下相邻尺度图像对应位置的9x2个点进行比较，以判断其是否是极值点，检测到的所有极值点就是SIFT待选特征点的集合。由于DoG算子会产生比较强的边缘响应，还需要舍弃的对比度边缘响应的不稳定点以及高对比度的点，以获得比较稳定的特征点。

1.3 确立关键点特征方向

首先计算关键点邻域内每个像素点的梯度和方向的分布特征，然后进行统计以计算每个关键点的方向参数，如式 （3）和式 （4）所示

式中：m（x，y）和θ（x，y）分别为高斯空间图像中点 （x，y）处的梯度值和方向，L所用的尺度为每个关键点各自所在的尺度图像。

将邻域内所有点的梯度值按照角度值进行求和统计，把最大梯度值对应的角度值作为关键点的主方向，如果次大梯度值大于最大值的0.8倍时，所对应的角度值也作为该点的主方向。

1.4 特征描述子的计算

针对任意的关键点，选择其所在的高斯尺度图像，以关键点为中心选择16像素x16像素大小的区域，将该区域进行均匀划分，使每个子区域的大小为4像素x4像素，共为16个子区域。获得每个4像素x4像素的子区域中的8方向梯度直方图，再对16个子区域的8方向梯度值按照位置进行依次排序，最后生成16x8＝128维向量，SIFT描述子就是该128维向量。

1.5 特征点匹配与误匹配点的剔除

生成当两幅图像的SIFT特征描述子之后，计算关键点128维向量特征描述子的欧氏距离，以此为判断依据以确定两幅图像中关键点相似性。这样的匹配结果会存在一定的错误匹配点，再使用RANSAC算法处理以消除错误匹配。

2 四邻域梯度值阈值的匹配控制方法

传统SIFT算法在匹配时的特征点有3个特征信息，即坐标、尺度、128维描述子，在匹配过程中使用关键点128维向量描述子的欧式距离作为判断依据以确定两幅图像中关键点相似性。匹配时，需要找出两幅图像中关键点对之间的最近欧氏距离和次最近欧氏距离，并将两个距离进行对比，符合条件的则为相似点。欧氏距离是指在m维空间向量中两个点之间的真实距离，定义为

式中：D为m＝128维向量描述子的欧氏距离，xi，yi为相匹配图像的描述子相对应维的值，可以看出，如果进行传统的匹配方法，将所有的特征点都进行欧氏距离计算的计算量会很大，这也是SIFT算法匹配过程中计算复杂度高，耗时久的原因。因此，如何减少欧氏距离的计算是降低算法复杂度的有效方法。

特征点的描述子的生成，是在将特征点邻域内，不同的像素的梯度值与和像素与特征点距离相关的加权系数的乘积所生成的，加权系数如式 （6）所示

式中，weight——梯度值的加权系数，x——区域内的点与关键点的列向距离，y——区域内的点与关键点的行向距离，σ——描述子窗口宽度与直方图列数一半的乘积。由此可知在匹配过程中，距离特征点越近的特征点区域内的像素点的梯度值对匹配结果影响越大，距离特征点越远的特征点区域内的像素点的梯度值对匹配结果影响越小，特征点周围四邻域的梯度值对匹配起着关键作用。

因此根据描述子的特点，特征点的匹配是和特征点邻域的梯度值是有关系的，根据大量的实验统计特征点邻域内不同区域梯度值与正确匹配点的梯度值的关系，本文提出了一种四邻域主梯度值阈值进行匹配控制的方法。该方法将关键点四邻域主梯度值作为特征点的特征之一，在进行主方向统计时，计算特征点周围四邻域的梯度值之和，即将特征点主方向所对应的梯度值作为新的特征，在匹配阶段中使用。

对高斯差分空间所检测的稳定极值点，在相对应的高斯空间图像上特征点的3×1.5σ邻域内，根据式 （4）计算像素的角度值，根据式 （3）计算相对应梯度值，使用角度所对应的梯度直方图对区域内像素点的梯度和方向进行统计。直方图划分规则为，将360°分为36个柱，每一个柱为10°，每个直方图的值表示相对应方向范围的梯度值和。将特征点周围四邻域的梯度值作为特征点新的特征，在图像的特征点进行匹配前，比较图像1和图像2中的特征点的四邻域梯度值，并将比较的值按照阈值进行分类，符合条件的则继续进行相对应的欧氏距离计算和后续匹配计算，不符合条件的舍去，不进行欧氏距离计算和匹配计算，这样可以大量减少进行欧氏距离计算的特征点，从而降低运算复的杂度，节约运算时间。

3 实验结果及分析

实验所使用的移动处理器为：瑞芯微RK3066。CPU为：ARM Cortex－A9，RAM：1GB，频率：1.6GHz。软件环境：Android平台为4.1。算法使用Android NDK在Eclipse工具上实现。使用标准图像数据库［13］里面图像，在同样的实验环境条件下，运行传统算法和优化算法，并对实验结果进行对比和分析。其中的几对图像在不同阈值下的实验结果见表1和表2。

表1 不同阈值条件下匹配点数的对比

表2 不同阈值条件下匹配时间的对比

表1为不同的图像对分别在0.01至0.05阈值条件下的匹配结果与传统算法的匹配结果的对比，每组图像的数据分别为原始尺寸实验数据，和对原始图像进行适当缩小之后的数据。从实验结果中可以看出，随着阈值的增加，匹配的点数不断增加。当阈值比较小的时候，匹配的点数与传统算法相比，匹配的点数较少，随着阈值增加匹配点数增加，当阈值超过0.02之后，匹配的点数趋于稳定，并与传统算法匹配数目基本一致。同时，对匹配的点的坐标进行检查，相对应图像间匹配点的坐标也是一致的。

表2为不同图像对分别在0.01至0.05阈值条件下的匹配时间与传统算法匹配时间的对比，每组图像的数据分别为原始尺寸实验数据，和对原始图像进行适当缩小之后的数据。从实验结果可以看出，阈值越小匹配的时间越短，随着阈值的增加匹配时间不断增加。但是由于原始图像尺寸较大，所检测的特征点数目较多，运算时间因此实现实时性比较困难，这一点不如桌面电脑处理器，这是由于移动处理器的带宽和频率远逊于电脑处理器所导致的。通过对表中实验数据分析可以看出，对图像进行适当缩放之后，匹配时间就会减少很多。通过对表1和表2的综合分析，当选取阈值为0.02时，本文改进的算法的匹配结果和传统算法的匹配结果基本保持一致，而且也明显的减少了匹配所消耗的时间，不同图像对的匹配一致性和加速效果分析见表3。

表3 匹配效率和一致性分析

表3为相对应图像对在优化算法和传统算法的条件下匹配效率和一致性分析结果。左侧为对原始图像适当缩小之后的实验数据，右侧为原始图像的实验数据。加速比为传统算法的匹配时间和优化算法在阈值为0.02时匹配时间的比值，匹配重合率为优化算法的正确匹配点数与传统算法的正确匹配点数的比值。

随机选择图像库中的一对测试图像，在传统算法和优化算法不同阈值条件下的实验测试结果如图1所示。图1中选择的是boat中的一对图像，即为表1、表2、表3中的尺寸为420x340的boat图像，图像间有一定的缩放、旋转和仿射变换。图1中，图1（a）为传统匹配方法中匹配结果，图1（b）至图1（f）为优化之后的匹配算法在阈值为0.01至0.05的不同与之条件下的匹配结果，0.02之后，匹配点数趋于稳定，并与传统算法匹配数目基本一致，但匹配时间增加，当阈值为0.02时，可以保证匹配结果的同时大幅提高匹配效率。

图1 传统匹配方法和优化匹配方法不同阈值的匹配结果对比

通过对实验数据的分析可以看出，当优化后的算法阈值为0.02时，传统匹配方法和优化后匹配方法的匹配点数基本完全一致，其中对于匹配点数少于传统方法的图像，匹配点的重合率也是很高的，在实际应用中几乎不影响匹配结果，甚至对于某几幅图像优化算法的匹配点数多出几个；实验还对不同匹配方法的匹配点的坐标进行分析，匹配点的坐标也基本一致。此外优化的四邻域梯度阈值方法的匹配速度较传统方法相比有2.0倍至3.0倍的提高。实验结果表明当阈值选取0.02时，在保证匹配点数和结果正确性的前提下也提高了匹配效率。实验还通过对200组图片进行对比实验并对结果进行分析，实验结果与上述实验结果基本相符，平均可以提高2.0至3.0倍匹配速度。因此，该优化算法在保证匹配结果正确性的前提下，可以提高匹配效率。由于目前移动平台的处理器在频率和带宽方面和桌面电脑处理器都有较大的差距，对于大尺寸图像的处理实时性效果没有较小尺寸的图像的明显。对于尺寸较小的图像或者将较大尺寸图像适当缩小之后，在移动平台上基本可以实现实时性。

4 结束语

在原有SIFT匹配算法的基础上，另外增加特征点周围四邻域的主梯度值作为该特征点的特征之一，对匹配算法进行控制。图像进行128维向量描述子的欧氏距离计算之前，使用阈值0.02对特征点对之间的四邻域主梯度值分组，符合条件的组内的点继续进行运算，组外的点予以删除，以此来减少运算量达到减少运算时间的目的。实验结果表明，所提出的主梯度阈值控制法，不但保证了匹配结果的正确性也提高了运算效率。对于尺寸较小的图像，或者将尺寸较大图像适当缩小，在移动端基本可以实现实时性。

［1］Sima AA，Buckley SJ.Optimizing SIFT for matching of short wave infrared and visible wavelength images ［J］.Remote Sensing，2013，5 （5）：2037－2056.

［2］Liu Xuejun，Shao Zhenfeng，Liu Jun.Ontology－based image retrieval with SIFT features ［C］／／First International Conference on Pervasive Computing Signal Processing and Applications.Harbin，China：IEEE，2010：464－467.

［3］Calonder M，Lepetit V，Strecha C，et al.BRIEF：Binary robust independent elementary features ［G］.LNCS 6314：Computer Vision－ECCV，2010：778－792.

［4］Rublee E，Rabaud V，Konolige K，et al.ORB：An efficient alternative to SIFT or SURF ［C］／／IEEE International Conference on Computer Vision.Barcelona，Spain：IEEE，2011：2564－2571.

［5］Faraj A，Danijela RD，Axel G.VF－SIFT：Very fast SIFT feature matching ［G］.LNCS 6376：Pattern Recognition，2010：222－231.

［6］XU Yang，CAO Jie.Improved SIFT algorithm based on the contrast threshold ［J］.Electronic Design Engineering，2012，20 （19）：174－177 （in Chinese）.［徐阳，曹杰.一种基于对比阈值的改进SIFT算法 ［J］.电子设计工程，2012，20（19）：174－177.］

［7］OUYANG Peng，YIN Shouyi，GAO Hui，et al.Parallelization of computing－intensive tasks of SIFT algorithm on a reconfigurable architecture system ［J］.IEICE Transactions on Fundamentals of Electronics， Communications and Computer Sciences，2013，E96A （6）：1393－1402.

［8］Sinha N，Frahm JM，Pollefeys M，et al.Feature tracking and matching in video using programmable graphics hardware ［J］.Machine Vision and Application，2011，22 （1）：207－217.

［9］Chiu Liang－Chi，Chang Tian－Sheuan，Chen Jiun－Yen，et al.Fast SIFT design for real－time visual feature extraction ［J］.IEEE Transactions on Image Processing，2013，22 （8）：3158－3167.

［10］Kayombya G－R.SIFT feature extraction on a smartphone GPU using OpenGL ES 2.0 ［D］.Massachusetts： MIT.Department of Electrical Engineering and Computer Science，2010.

［11］Cheng K－T，Wang Y.Using mobile GPU for general purpose computing－a case study of face recognition on smartphones［C］／／International Symposium on VLSI Design，Automation and Test.Hsinchu，Taiwan：IEEE，2011：54－57.

［12］Rister B，Wang Guohui，Wu M，et al.A fast and efficient sift detector using the mobile GPU ［C］／／IEEE International Conference on Acoustics，Speech and Signal Processing.Vancouver，Canada：IEEE，2013：2474－4678.

［13］Oxford.Visual geometry group－affine covariant regions dataset［EB／OL］.http：／／www.robots.ox.ac.uk／～vgg／data／data－aff.html，2014.