齐乃新，曹立佳，杨小冈，朱瑞奇

(第二炮兵工程大学a.304室;b.303室，西安710025)

基于圆环域描述的改进快速SIFT算法

齐乃新a，曹立佳a，杨小冈b，朱瑞奇a

(第二炮兵工程大学a.304室;b.303室，西安710025)

针对快速SIFT(Scale Invariant Feature Transform)算法去掉高斯加权环节，导致算法稳定性下降的不足，对快速SIFT算法中的特征描述子进行了改进，用圆形代替矩形并对区域进行分层，越靠近关键点层数越多，相当于对中心区域进行了加权，并通过仿真给出了最佳加权层数和特征描述子方向数。仿真实验表明:该算法不但满足了匹配正确率和实时性的要求，而且具有很高的稳定性和鲁棒性，能够满足目标跟踪的实时性要求。

快速SIFT算法;特征匹配;目标跟踪;实时性

视觉跟踪是计算机视觉和人工智能领域的重要研究课题之一，在视频监控、智能人机交互、精确制导武器成像制导等诸多领域具有广阔的应用前景。基于特征点的SIFT (Scale Invariant Feature Transform)跟踪算法，因其具有平移、旋转、尺度缩放、亮度变化等的不变性，对视角变化、仿射变化、噪声也保持一定程度的稳定性等优良特性，广泛应用于视觉跟踪中［1］。SIFT，即尺度不变特征变换，是David G Lowe在1999年首次提出，并于2004年进行了相应完善和总结［2］。SIFT是一种提取局部特征的算法，首先在尺度空间寻找极值点，提取出位置、尺度、旋转不变特征量，然后根据2幅图像特征量之间的距离实现图像匹配。

SIFT算法提取的特征点具有尺度不变性，非常适合对尺度变化的目标进行跟踪，但是由于所要计算的数据量较大，时间复杂度高，严重影响了跟踪算法的执行效率［3］。为此，很多学者对SIFT算法进行了改进，如SinhaSN［4］提出了一种基于图形处理单元(GPU)的SIFT高效算法;Matas J等［5］采用积分直方图和测定海森矩阵(Determination ofHessian matrix)对SIFT进行了加速，提出了SURF(Speeded Up Robust Features)算法，Michael Grabner［6］提出了利用积分图像近似替代SIFT的算法步骤，提出了Fast Approximated SIFT算法。它们虽然提高了算法速度，但算子描述质量都不是很高，算法的稳定性有所下降。

本文在积分直方图的框架下，兼顾算法的实时性和稳定性，对快速SIFT算法中的特征描述子进行了改进，用圆形代替矩形并对区域进行分层，越靠近关键点层数越多，相当于对中心区域进行加权，并通过仿真给出最佳加权层数和特征描述子方向数。本文算法不但能够保证匹配的实时性和稳定性，而且具有较高的鲁棒性，能够满足目标实时跟踪的要求。

1 快速SIFT算法

由于经典的SIFT算子构造尺度空间采用Gaussian卷积的方式，计算量大，不满足实时性要求，2006年Michael Grabner［6］利用积分图像来构造尺度空间，大大提高了特征关键点的提取速度。

1.1 积分图像

积分图像(Integral image)的定义由Paul Viola和Michael Jones于2001年给出［7］，它其中任意一点(i，j)的值ii(i，j)表示了如图1(a)所示的原图像斜线区域灰度值或灰度平方的总和，即:

或

其中，p(i′，j′)表示原图形中(i′，j′)点的灰度值或灰度直方图的平方。ii(i，j)可用式和式迭代计算得到:

其中，S(i，j)表示一列的积分，且S(i，－1)=0，ii(－1，j)= 0。求积分图像，只需要扫描原图像所有像素一遍。

图1 基于积分图求取W区域的图像能量

在求取窗口的灰度值总和或灰度平方总和时，如图1 (b)所示，不管窗口W大小如何均可以用积分图像的4个相应点(i1，j1)，(i2，j2)，(i3，j3)，(i4，j4)快速计算出来，即窗口W的灰度值或灰度值的平方总和为

与单纯计算像素总和的求和运算相比，该算法只需要3个加减运算就可以求出一定区域的图像能量，大大提高了计算速度。

1.2 构造DOM(difference-of-mean)尺度空间

利用积分图像，通过不同大小的窗口W来计算图像均值，构建尺度空间，如图2所示。

图2 尺度空间示意图

对DOM区域进行归一化处理

其中，s1、s2分别为最小和最大窗口的尺寸，sensitivity为s1内部区域内的灰度均值与外部区域s1－s2区域灰度均值的最小比值。

1.3 生成特征描述子

特征描述子的生成是特征匹配的关键，它的稳定与否直接关系到特征匹配的效果。

为了提高生成特征描述子的实时性，采用积分直方图的方法计算关键点方向。积分直方图是借用积分图像的思想，首先求取整幅图像的积分直方图，即每个像素的积分直方图都是其左上角所有像素的梯度直方图的和，那么任何位置和大小矩形区域的梯度直方图的和可以用类似图1的方法通过3次加法计算得来，提高了算法的实时性。

2 改进后的快速SIFT算法

在特征关键点周围，越靠近关键点的区域对关键点的特征描述影响越大，经典的SIFT算法对关键点周围4个特征区域的梯度方向进行了高斯加权，但Michael Grabner提出的快速SIFT算法中并没有这一步骤，稳定性有所下降。同时匹配搜索过程中，维数较高，K－D树搜索效率并不高，甚至接近穷举搜索的运算速度［8］。为此，为了满足跟踪实时性要求必须对特征描述子进行处理。

通过对特征区域进行分析可知，与关键点距离相同的点对关键点特征描述的影响是相同的，即若关键点周围以关键点为圆心划分不同的圆环，在同一圆环内的特征区域对对关键点的特征描述是相同的，越靠近特征关键点层数越多，这样就相当于对中心区域进行了加权。同时，圆形区域可以减少邻域角度归零的步骤，将矩形区域改为同心圆区域，还可以省去高斯的模糊的步骤，提高了算法的实时性。改进的SIFT算法特征描述子如图3所示。

图3 不同层数的分割方式

其特征描述子的描述方法为:

Step 1:提取以关键点为中心，直径为16的圆形窗口区域作为邻域，保证生成的特征描述子所需要计算的邻域范围和原算法基本一致;

Step 2:如图3，将半径为8的圆形邻域以2为间隔分为4个的同心圆，每个格子代表一个像素值;

Step 3:对于4个同心圆区域，分别求出其8个方向(45°、90°、135°、180°、225°、270°、315°、360°)的梯度累加值。由中心向外，取第一个圆环的8维向量作为特征向量的第1至第8个元素，取第二个圆环的8维向量作为特征向量的第9至第16个元素，以此类推。这样，特征点描述子即为4×8 =32维向量;

Step 4:为了确保旋转不变性，需对特征向量进行排序操作。设D是一个关键点的特征向量，D1、D2、D3、D4分别是从中心向外的4个圆环的特征向量，则D=(D1，D2，D3，D4)，其中Di=(di1，di2，…，di7，di8)，i∈［1，4］。首先标记半径最小的圈中最大值出现的位置，即d11，d12，…，d17，d18中的最大值，若d11为最大值，则不需做任何处理，若d11不是最大值，需进行如下操作:将D1、D2、D3、D4同时循环左移，直至D1中的最大值为特征向量D1中的第一位，例如d17为向量D1中的最大值，循环左移之后4个圆环的特征向量变为Di= (di7，di8，…，di1，di2，…，di6)。如果将每一个8维向量分别取向量的最大值并执行此步操作，则匹配的效果会大大降低。这样操作确保了4个圆环旋转相同的角度，等同于原算法中邻域归零的操作，从而保证了改进描述子具有选择不变性。

从图3中可以看出，当层数为1层时其特征区域只是一个半径为16的邻域，当层数为2层时，其特征区域一部分为关键点周围半径为8的邻域，另一部分为关键点周围半径为16的邻域，这样靠近关键点的部分就重复利用了2次，相当于对其进行了加权。以此类推，当层数为4层时，特征区域分为4部分，关键点周围半径为2的邻域相当于进行了4次加权。这样假设分为4层，梯度方向为8方向，这时特征关键点维数为4×8=32，提高了特征关键点匹配的速度。但这种方法由于减少了特征区域，算法稳定性大大降低，为此可以通过提高梯度直方图的方向数来提高算法的稳定性。

3 实验结果及分析

兼顾算法的稳定性与实时性，本文对目标T1、T2选择不同的加权层数和描述子方向数进行仿真对比。

3.1 特征描述子可行性分析

分别取目标T1和目标T2序列图中的40帧图像与其对应的间隔10帧后的图像进行匹配，图4(a)是对目标T1的40组图片在梯度方向个数不同的平均正确匹配率，图4(b)是对目标T2的40组图片在梯度方向个数不同的平均正确匹配率。横轴表示关键点周围邻域的分割层数，分割层数越多表明中心部分加权次数越多;纵轴表示特征关键点的匹配正确率。

图4 不同分割层数和方向数图像匹配正确率

从图4可以看出方向数为12，分割层数为2时，增加方向数目或分割层数其匹配精确度增加不明显。因此，为提高时效性选择最终的梯度方向为12，分割层数为2，如图5所示。这样就形成了12×2=24维描述子，降低了特征向量的维数，提高了匹配搜索效率。

虽然，在图5中当采用24维描述子时仍然只能维持在60%左右，图像的跟踪不同于图像的配准，图像跟踪只需要检测到正确的匹配点即可确定目标的位置，因此在后续跟踪中选用24维的特征描述子是可行的。

图5 改进后的分割层数和梯度方向

3.2 本文算法与原算法的实验对比

为了验证改进后的特征描述子的匹配性能，现分别从目标T1和目标T2的序列图像中选取4组图像分别采用快速SIFT算法和本文提出的改进快速SIFT算法进行了匹配试验，其中每组图像都是间隔10帧的2帧图像且其中加入了高斯噪声。其结果如图6和图7所示。

图6目标T1的4组采用快速SIFT算法和改进快速SIFT算法的匹配对比图片

图6 和图7为目标T1和目标T2在匹配阈值为0.7的情况下，分别采用快速SIFT算法和本文提出的改进快速SIFT算法的匹配结果图。图6和图7中(a1)、(b1)、(c1)、(d1)为采用快速SIFT算法的匹配图像，图6和图7中(a2)、(b2)、(c2)、(d2)为与之对应的采用改进快速SIFT算法的匹配结果图。为了能够更加直观地比较2种算法的优劣，现将2种算法的匹配时间和匹配正确率进行比较，如表1所示。

图7 目标T2的4组采用快速SIFT算法和改进快速SIFT算法的匹配对比图片

表1 快速SIFT算法和本文SIFT算法匹配性能对比

从表1中可以看出，本文的SIFT算法在匹配时间上缩短了近1/2，而匹配正确率只有小幅降低，对匹配结果影响不大，因此改进后的快速SIFT算法对图像进行实时跟踪是可行的。

3.3 鲁棒性分析

图8为采用上述的24维特征描述子进行匹配的结果，匹配关键点数目为20个，误匹配点为1个。

图8 目标模板与实时图匹配结果

为验证该算法的鲁棒性，现将目标模板分别旋转90°和缩小一倍再进行匹配，结果如图9和图10所示。

图9 目标模板旋转900后的匹配结果

图10目标模板缩小一倍后匹配结果

图9 为目标模板旋转90°后的匹配结果，匹配关键点数目为21个，误匹配点为1个;图10为目标模板缩小一倍后的匹配结果，匹配关键点数目为18个，误匹配点为0个。由此可知，当实时图与目标模板之间尺度、角度相差较大时该算法仍能准确地检测到目标，鲁棒性好。

4 结束语

快速SIFT(Scale Invariant Feature Transform)算法采用积分图像代替高斯滤波提高了算法速度，但去掉了高斯加权环节，算法稳定性有所下降。本文对快速SIFT算法中的特征描述子进行了改进，用圆形代替矩形并对区域进行分层，越靠近关键点层数越多，相当于对中心区域进行了加权，并通过仿真给出了最佳加权层数和特征描述子方向数。仿真实验表明:本文算不但具有很好的实时性和稳定性，而且具有较高的鲁棒性，能很好地满足目标实时跟踪要求。

［1］白廷柱，侯喜报.基于SIFT算子的图像匹配算法研究［J］.北京理工大学学报，2013，33(6):622－627.

［2］David G Lowe.Distinctive Image Features from Scale－Invariant Interest Points［J］.International Journal of Computer Vision，2004，60(2)，91－110.

［3］邢诚.基于简化SIFT算法的无人机影像重叠度分析［J］.哈尔滨工程大学学报，2012(2):221－225.

［4］Sinha SN，Frahm JM，Pollefeys M，et al.Feature Tracking and Matching in Video Using Programmable Graphics Hardware［J］.Machine Vision and Applications，2011，22(1): 207－217.

［5］Matas J，Chum OM U，Pajdla T.Robustwide baseline stereo from maximally stable extremal regions［J］.In:BMVC.，2002，257－263.

［6］Michael Grabner，Helmut Grabner，Horst Bischof.Fast approximated SIFT［C］//Asian Conference on Computer Vision.Hyderabad，India，2006:918－927.

［7］Paul Viola，Michael Jones.Rapid Object Detection Using a Boosted Cascade of Simple Features［J］.Computer Vision and Pattern Recognition，2001(1):511－518.

［8］何健，梁凤梅.改进SIFT算法在特征匹配中的应用［J］.科学技术与工程，2013(11):3016－3020.

(责任编辑杨继森)

Im proved Fast SIFT Algorithm Described in Domain-based Ring

QINai－xina，CAO Li－jiaa，YANG Xiao－gangb，ZHU Rui－qia
(a.The 304 Room，b.The 303 Room;the Second Artillery Engineering University，Xi’an 710025，China)

In the fast SIFT(scale invariant feature transform)algorithm，it removes Gaussian weighted links algorithm and the stability is decreased.For that question，we improved the feature descriptor of fast SIFT algorithm.In the improved algorithm，we stratified the area with circular instead of rectangular.Therefore，the closer to the key points，the more layers are.The algorithm which was equivalent to the central region wasweighted，and the optimum number of layers and feature descriptor weighted number of directions through simulation were given.The simulation results show that themethod not only content the request for correctmatching rate and real time，but also have high stability and robustnesswhich can meet the real time demand of target tracking.

fast SIFT algorithm;featurematching;target tracking;real time

:A

1006－0707(2014)07－0091－05

format:QINai－xin，CAO Li－jia，YANG Xiao－gang，et al.Improved Fast SIFT Algorithm Described in Domain－based Ring［J］.Journal of Sichuan Ordnance，2014(7):91－95.

本文引用格式:齐乃新，曹立佳，杨小冈，等.基于圆环域描述的改进快速SIFT算法［J］.四川兵工学报，2014(7):91－95.

10.11809/scbgxb2014.07.026

2014－03－09

国家自然科学基金项目(61203189)。

齐乃新(1989—)，男，硕士，主要从事视觉导航方面的研究;曹立佳，男，博士，讲师，主要从事精确制导方面的研究;杨小冈，男，博士后，副教授，主要从事图像领域的研究。

TP391