一种具有实时性的SIFT特征提取算法

李鹤宇，王 青

(北京航空航天大学自动化科学与电气工程学院，北京 100191)

一种具有实时性的SIFT特征提取算法

李鹤宇，王 青

(北京航空航天大学自动化科学与电气工程学院，北京 100191)

针对尺度不变特征变换(SIFT)算法实时性差和在生成灰度图时信息丢失的问题，提出一种对比度增强和使用DAISY描述符的SIFT特征提取算法。首先，通过彩色图和原始灰度图计算像素的颜色调整值和曝光调整值，根据调整值与原灰度级获得对比度增强的灰度图。其次，使用改进后的灰度图提取SIFT特征点，并根据邻域灰度级计算不同高斯核和方向下的卷积方向图。最终，由特征点和采样点不同方向的偏导数值获得DAISY描述符，该描述符结构简单，便于计算。对由标准图像数据集提取的特征点使用K近邻(KNN)算法进行匹配，以评价在不同变化下算法的准确率。试验结果表明，该算法能够获得更多的特征点，并且在保证准确率的同时降低描述符生成部分和特征匹配部分的时间。

尺度不变特征变换(SIFT)；图像匹配；对比度增强；DAISY描述符

0 引 言

图像匹配算法是遥感技术、飞行器景象导航、目标特征跟踪问题、空间探测器位姿估计的基础，广泛应用于航天领域[1-5]。Ma等[6]针对遥感图强度不同时匹配点对较少的问题，定义了一种新的梯度，并将特征点的尺度、方向等信息引入到匹配算法中。陈方等[7]提出一种景象匹配辅助导航算法，对尺度不变特征变换(Scale-invariant feature transform,SIFT)特征点检测和匹配进行优化，以获取航向和位置偏差信息。Toshihiko等[8]针对小天体着陆问题，将弹坑、岩石等灰度变化明显的区域作为陆标，并利用图像匹配技术对其进行跟踪。孙小炜等[9]采用基于目标灰度特征的粒子滤波方法抑制图像匹配的漂移，实现对非刚性变形目标的稳定跟踪。郝刚涛等[10]针对故障卫星绕本体最大惯量轴慢转时信息缺失的问题，使用基于特征匹配的即时定位与地图构建(Simutaneous localization and mapping,SLAM)系统测量相对位置。

由Lowe[11]提出的SIFT算法，对不同视角变换和外界环境干扰具有较强的鲁棒性。但是，SIFT使用灰度图进行处理，丢失部分彩色图信息，并且为了获得较好的性能，算法复杂，不能达到实时性。针对上述问题，学者们进行了多方面的研究。Zhao等[12]利用灰度级分布，进行不同程度的曝光调整，达到增强对比度的效果；Abdelhakim等[13]提出一种Colored SIFT算法，新生成的描述包含颜色信息，并对集合变化具有较强的鲁棒性；Kwon等[14]根据物体的表面反射特性计算不变色值，根据该值检测图像局部特征并生成描述符。Lee等[15]减小SIFT中高斯滤波器的标准偏差并简化高斯金字塔的构建以降低算法复杂度；Yao等[16]通过下采样替代上采样保存插值运算，并减少尺度空间的组数和每组的层数。

Tola等[17-18]提出DAISY描述符，由于其对称性的结构和较快的运算速度，得到了广泛的关注。学者多将其应用于基于密集选取的局部特征提取。Huang等[19]将DAISY描述符与树状结构相结合，通过计算匹配成本来避免局部最优结果。Velardo等[20]利用DAISY描述符提取面部特征，并使用递归网格算法实现匹配。

本文提出一种基于对比度增强和DAISY描述符的SIFT特征提取算法，以增强颜色鲁棒性并降低运算时间。

1 SIFT算法流程

1.1 彩色图转化为灰度图

将RGB模式的彩色图转化为灰度图Gray的方式：

Gray=0.299R+0.587G+0.114B

(1)

式中：R、G、B分别代表像素点红、绿、蓝三个通道。

1.2 构建高斯差分金字塔

高斯尺度图像L(σ)由初始图像I和高斯函数G(σ)卷积得到，根据卷积的可分离性，通过L(σ1)求取L(σ2)：

(2)

图1 尺度空间构建Fig.1 The construction of scale space

改变高斯核σ的值，获得不同尺度下的高斯卷积图像，构成高斯金字塔的第0组，组内图层按高斯核从低到高排列，通过下采样得到下一组的第1层图像。以此类推，获得高斯金字塔，其中每一层图像的尺度为：

(3)

式中：o表示组数，O表示总组数，r表示层数，s设为3。通过高斯金字塔组内相邻层灰度的差值获得高斯差分金字塔(Difference of Gaussian, DOG)，如图1所示。

1.3 特征点检测

对DOG组内除边界层外的点，对比8邻域点和相邻图层各9个点，得到局部极值点，并使用泰勒级数展开式拟合函数：

(4)

通过使式(4)右侧等于0，得到亚像素级别的特征点坐标。为了获得稳定的特征点，还需要去除灰度级较小的极值点和在边缘处的极值点。

1.4 主方向计算

为每一个特征点分配一个主方向，以便实现旋转不变性。在以特征点为中心，3×1.5σ的邻域范围内，统计像素点梯度方向和幅值，用直方图表示统计结果，峰值所对应的角度作为特征点的方向，如图2所示。至此获得图像的亚像素级特征点坐标和对应的方向。

图2 特征点主方向选取示意图Fig.2 Illustration of the feature point main direction selection

1.5 描述符生成

根据主方向对特征点的邻域进行旋转，以特征点为中心，将矩形邻域范围内的像素点分为4×4个区域，对360°进行8等分，统计每个区域内所有点的梯度幅值和方向，生成128维的描述子。

2 本文算法

本文引入对比度增强算法，并使用DAISY描述符替代原有的SIFT描述符。算法流程图如下：

图3 本文算法流程图Fig.3 The flow chart of the proposed algorithm

2.1 对比度增强算法

式(1)中R、G、B三个通道的系数根据人眼对三种颜色敏感度确定，由于三者系数不同，会出现不同颜色产生相同灰度级的现象，影响算法最终效果。此外，彩色图每个像素点包含三个信息通道，灰度图采用单通道模式，转化为灰度图时会有信息丢失现象，影响算法效果。因此本文算法通过计算颜色调整和曝光调整两个量，对灰度图的初始值进行调整，增加对比度，保留更多的局部梯度信息。

2.1.1 颜色调整

将RGB模式的图像转化为YCbCr模式：

(5)

式中：Y、Cb、Cr分别代表灰度、红色色度和蓝色色度通道。统计Cb通道和Cr通道的平均值，用mb和mr表示。每个像素点的颜色调整Yci根据该点Cbi通道和Cri通道的相对大小、mb和mr的相对大小确定，并得到调整后的中间值P。

YCi=ksgn(mr-mb)×sgn(Cri-Cbi)×

(6)

P=Y+YC

(7)

式中：k的值取为3，α的值取为0.15。

2.1.2 曝光调整

灰度图的信息主要由平均灰度级和局部对比度构成。平均灰度级约等于127.5[12]时，能够获得较好的全局信息，因此灰度级接近127.5的像素点进行较大的调整；图像不同范围的灰度级均匀分布时能够保留较多的局部对比度，因此灰度级远离127.5像素点进行较小的曝光调整：

YEi=(128-mP)exp[-(i-0.5)2/2σ2]

(8)

式中：将σ的值设定为0.25时。最终获得调整后的灰度图T：

T=Y+YC+YE

(9)

2.2 描述符生成

通过SIFT获得特征点位置和主方向后，算法将DAISY描述符应用于稀疏选取，达到提升计算效率的目的。

DAISY描述符计算灰度图多个方向和尺度下的卷积方向图，根据特征点和采样点处的不同方向的偏导数生成描述符。首先，计算原始图像I在不同方向的偏导数[17-18]：

(10)

(a)+=max(a,0)

(11)

式(10)中：等号右侧表示计算图像I每个点o方向的偏导数值，当像素点偏导数值小于零时，取为0。由这些值组成的新矩阵称为方向图，记为Go，共计算8个方向的方向图，相邻方向间隔45°。

其次,对方向图进行不同尺度的卷积计算：

(12)

最后,以特征点为圆心，在卷积方向图M层同心圆上分别获得N个均匀分布的采样点，同心圆的半径分别为R1,…,RM，同一圆上采样点对应卷积方向图的高斯核相同，高斯核大小与同心圆半径成正比，其结构如图4所示。

图4 DAISY描述符结构Fig.4 The structure of DAISY operator

根据特征点和采样点的偏导数值获得描述符，如下所示：D(u,v) =

(13)

DAISY描述符采用圆形网格结构，具有更好的定位属性[20]。此外，在计算卷积方向图时，由于高斯卷积函数具有可分离性，可以降低计算量。因此该算子具有较好的性能，并能提高计算效率。

3 仿真校验

对算法进行仿真，并与文献[12]算法进行比对，以验证算法的特性。仿真硬件开发平台为：处理器为Intel(R) Core(TM) i5-5200U CPU @ 2.20G Hz，内存8.00 GB；软件开发平台为Windows 10操作系统、Microsoft Visual Studio Professional 2013、OpenCV 2.4.9。试验使用牛津大学机器人实验室的图像数据集[21]，仿真采用其中的仿射变化图集、亮度变化图集、清晰度变化图集，并通过实测图模拟旋转变化，每组包含5张图像，其中组内图像变化程度依次增加。仿真计算图像平均灰度、图像特征点个数和匹配正确率三个量，以衡量本文算法的性能。

统计原始灰度图和对比度增强灰度图像素点的平均灰度级，并计算SIFT算法特征点的数量，每组图像的灰度平均值如表1所示。从表1可以看出，加入对比度增强算法后的平均灰度级接近127.5，保留更多的局部信息，从而提取更多的特征点。此外，特征点增加的数量与平均灰度级的变化量有关，亮度变化图集和旋转变化图集经过对比度增强算法，平均灰度级获得较大的调整，特征点数量分别增加26.2%、41.3%。

表1 特征点提取数量

在每个图集中，以第一张图像作为基准，使用K最近邻(K-nearest neighbor,KNN)算法[22]与后四张图像进行匹配，统计匹配时间和正确率。原算法和本文算法对每组第1、2幅图像的匹配结果如图5、图6所示。两种算法对特征点进行匹配所需要的时间和正确率分别如表2～9所示。

图5 原算法匹配结果Fig.5 The matching result of the original algorithm

图6 本文算法匹配结果Fig.6 The matching result of the proposed algorithm

匹配结果匹配数量正确匹配正确率描述符生成/s特征匹配/s图1图291587395．4%7．5917．588图1图331927285．2%7．5328．668图1图4552240．0%7．8788．01图1图537718．9%7．6898．523

表3 本文算法仿射变化图集匹配准确率及时间

表4 原算法亮度变化图集匹配准确率及时间

表5 本文算法亮度变化图集匹配准确率及时间

表6 原算法清晰度变化图集匹配准确率及时间

表7 本文算法清晰度变化图集匹配准确率及时间

表8 原算法旋转变化图集匹配准确率及时间

表9 本文算法清晰度变化图集匹配准确率及时间

通过对比表2～9的数据可以发现，对于仿射变化、亮度变化和旋转变化，改进后的算法在描述符生成和特征匹配部分都能明显提高计算效率，对于清晰度变化，除后两组的描述符生成时间外，改进后算法的运行时间小于原算法对应部分。原算法的匹配准确率随着变化程度的加强而降低，而改进后的算法在较大的清晰度变化下，仍能获得较高的匹配正确率，对于其它三种变化，改进后的算法和原算法的匹配正确率相近，没有出现明显的差异。因此，改进后的算法能够在保证匹配正确率的同时降低运算时间。

4 结 论

针对SIFT算法结构复杂、存在信息丢失的问题，本文提出一种改进的SIFT特征匹配算法。首先，根据彩色图计算像素点的颜色调整、曝光调整，获得对比度增强的灰度图，以保留更多的信息。其次，使用SIFT算法获得特征点坐标和主方向。最后，利用DAISY描述符中心对称的结构和易于实现旋转计算的特点，通过特征点和采样点在卷积方向图中的梯度值，获得特征向量。仿真结果表明，对比度增强的灰度图能够提取更多的特征点，本文算法能够对不同图像变化保持鲁棒性，维持较高的匹配准确率，并有效降低描述符生成和特征点匹配部分的计算时间。下一步的研究重点是对特征提取部分进行简化，简化高斯金字塔的构建步骤，以进一步提高运算速度。

[1] 刘玉, 王敬东, 李鹏. 一种基于SIFT和KLT相结合的特征点跟踪方法研究[J]. 宇航学报, 2011, 32(7):1618-1625. [Liu Yu, Wang Jing-dong, Li Peng. A feature point tracking method based on the combination of SIFT algorithm and KLT matching algorithm[J]. Journal of Astronautics, 2011, 32(7):1618-1625.]

[2] 龚俊斌, 张大志, 杨雪梅,等. 抗旋转和缩放的SAR与可见光图像自动配准算法[J]. 宇航学报, 2011, 32(6):1350-1358. [Gong Jun-bin, Zhang Da-zhi, Yang Xue-mei, et al. Automatic registration algorithm for SAR and optical image with rotation and scale invariability[J]. Journal of Astronautics, 2011, 32(6):1350-1358.]

[3] 王红梅, 李言俊, 张科. 一种基于Contourlet变换的图像匹配算法[J]. 宇航学报, 2008, 29(5):1643-1647. [Wang Hong-mei,Li Yan-jun,Zhang Ke.An image matching algorithm based on contourlet transform[J]. Journal of Astronautics, 2008, 29(5):1643-1647.]

[4] 张科, 王红梅, 李言俊. 一种基于可操纵金字塔的鲁棒图像匹配算法[J]. 宇航学报, 2005, 26(6):717-721. [Zhang Ke, Wang Hong-mei, Li Yan-jun. A robust steerable pyramid-based image matching algorithm[J]. Journal of Astronautics, 2005, 26(6):717-721.]

[5] 李莹, 叶培建, 彭兢,等. 火星探测出舱机构的识别定位与坡度测量[J]. 宇航学报, 2016, 37(2):169-174. [Li Ying, Ye Pei-jian, Peng Jing, et al. Egress mechanism recognition and slope measurement for Mars exploration[J]. Journal of Astronautics, 2016, 37(2):169-174.]

[6] Ma W P, Wen Z L, Wu Y, et al. Remote sensing image registr-ation with modified SIFT and enhanced feature matching[J]. IEEE Geoscience & Remote Sensing Letters, 2016(99):1-5.

[7] 陈方, 熊智, 许允喜,等. 惯性组合导航系统中的快速景象匹配算法研究[J]. 宇航学报, 2009, 30(6):2308-2316. [Chen Fang, Xiong Zhi, Xu Yun-xi, et al. Research on the fast scene matchin algorithm in the inertial integrated navigation system[J]. Journal of Astronautics, 2009, 30(6):2308-2316.]

[8] Toshihiko M, Tatsuaki H, Keiken N. Optical guidance for autonomous landing of spacecraft[J]. IEEE Transaction on Aerospace and Electronic Systems, 1999, 35(2):459-473.

[9] 孙小炜, 李言俊, 陈义. 一种新的红外目标跟踪方法[J]. 宇航学报, 2008, 29(5):1637-1642. [Sun Xiao-wei, Li Yan-jun, Chen Yi. A novel infrared object tracking method[J]. Journal of Astronautics, 2008, 29(5):1637-1642.]

[10] 郝刚涛, 杜小平, 宋建军. 空间翻滚非合作目标相对位姿估计的视觉SLAM方法[J]. 宇航学报, 2015, 36(6):706-714. [Hao Gang-tao, Du Xiao-ping, Song Jian-jun. Relative pose estimation of space tumbling non-cooperative target based on vision-only SLAM[J]. Journal of Astronautics, 2015, 36(6):706-714.]

[11] Lowe D G. Distinctive image features form scale invariant keypoints[J]. International Journal of Computer Vision, 2004,60(2): 91-110.

[12] Zhao Y, Zhai Y W, Dubois E, et al. Image matching algorithm based on SIFT using color and exposure information[J]. Journal of Systems Engineering and Electronics, 2016, 27(3):691-699.

[13] Abdelhakim A E, Farag A A. CSIFT: a SIFT descriptor with color invariant characteristics[C]. IEEE Conference on Computer Vision and Pattern Recognition,New York,USA,June 17-22,2006.

[14] Kwon O S, Ha Y H. Panoramic video using scale-invariant feature transform with embedded color-invariant values[J]. IEEE Transactions on Consumer Electronics, 2010, 56(2):792-798.

[15] Lee C, Rhee C E, Lee H J. Complexity reduction by modified scale-space construction in SIFT generation optimized for a mobile GPU[J]. IEEE Transactions on Circuits & Systems for Video Technology, 2016(99).

[16] Yao L F, Feng H, Zhu Y Q, et al. An architecture of optimised SIFT feature detection for an FPGA implementation of an image matcher[C]. International Conference on Field-Programmable Technology, Sydney,Australia,December 9-11,2010.

[17] Tola E, Lepetit V, Fua P. A fast local descriptor for dense matching[C]. IEEE Conference on Computer Vision and Pattern Recognition, Anchorage,USA,June 23-28,2008.

[18] Tola E, Lepetit V, Fua P. DAISY: an efficient dense descriptor applied to wide-baseline stereo[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2010, 32(5):815-830.

[19] Huang X S, Zhang J, Wu Q, et al. Dense correspondence using non-local DAISY forest[C]. International Conference on Digital Image Computing: Techniques and Applications (DICTA), Adelaide,Australia,November 23-25,2015.

[20] Velardo C, Dugelay J L. Face recognition with DAISY descriptors[C]. MM′10 and Sec′10, ACM SIGMM Multimedia and Security Workshop, Rome, Italy, September 9-10, 2010.

[21] Robotics Research Group. Affine covariant features[EB/OL].2007[2017].

[22] Cover T M, Hart P E. Nearest neighbor pattern classification[J]. IEEE Transactions on Information Theory, 1967, 13(1)：21-27.

通信地址：北京航空航天大学自动化科学与电气工程学院(100191)

电话：13161237733

E-mail:liheyu_umaa@163.com

A Real-Time SIFT Feature Extraction Algorithm

LI He-yu, WANG Qing

(1. School of Automation Science and Electrical Engineering, Beihang University, Beijing 100191, China)

In order to be implemented for real-time execution and use color information, an improved scale-invariant feature transform (SIFT) algorithm based on the contrast enhancement and DAISY descriptor is proposed in this paper. The color offset and the exposure offset of the pixel are calculated from the color image and the original grayscale image. The two offsets are added to the gray level to gain the contrast enhancing image according to which the SIFT feature points and the main directions are got. The DAISY descriptor of the feature point is obtained from the partial derivative values of the feature point and the sampling points with different directions. To evaluate the accuracy of the algorithm under different view changes, the feature points extracted from the standard image data sets are matched by the K-nearest neighbor (KNN) algorithm. The experimental results show that the algorithm can obtain more feature points. Furthermore, it guarantees the accuracy while reducing the time of the descriptor generating process and the feature matching process.

Scale-invariant feature transform (SIFT); Image matching; Contrast enhancement；DAISY descriptor

2017- 05- 03;

2017- 05-23

国家自然科学基金(61374012)

TP391

A

1000-1328(2017)08-0865-07

10.3873/j.issn.1000-1328.2017.08.011

李鹤宇(1993-)，男，硕士生，主要从事图像处理、机器视觉的研究。