齊乃新，曹立佳，楊小岡，朱瑞奇

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

基于圓環(huán)域描述的改進快速SIFT算法

齊乃新a，曹立佳a，楊小岡b，朱瑞奇a

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

針對快速SIFT(Scale Invariant Feature Transform)算法去掉高斯加權環(huán)節(jié)，導致算法穩(wěn)定性下降的不足，對快速SIFT算法中的特征描述子進行了改進，用圓形代替矩形并對區(qū)域進行分層，越靠近關鍵點層數越多，相當于對中心區(qū)域進行了加權，并通過仿真給出了最佳加權層數和特征描述子方向數。仿真實驗表明:該算法不但滿足了匹配正確率和實時性的要求，而且具有很高的穩(wěn)定性和魯棒性，能夠滿足目標跟蹤的實時性要求。

快速SIFT算法;特征匹配;目標跟蹤;實時性

視覺跟蹤是計算機視覺和人工智能領域的重要研究課題之一，在視頻監(jiān)控、智能人機交互、精確制導武器成像制導等諸多領域具有廣闊的應用前景?；谔卣鼽c的SIFT (Scale Invariant Feature Transform)跟蹤算法，因其具有平移、旋轉、尺度縮放、亮度變化等的不變性，對視角變化、仿射變化、噪聲也保持一定程度的穩(wěn)定性等優(yōu)良特性，廣泛應用于視覺跟蹤中［1］。SIFT，即尺度不變特征變換，是David G Lowe在1999年首次提出，并于2004年進行了相應完善和總結［2］。SIFT是一種提取局部特征的算法，首先在尺度空間尋找極值點，提取出位置、尺度、旋轉不變特征量，然后根據2幅圖像特征量之間的距離實現(xiàn)圖像匹配。

SIFT算法提取的特征點具有尺度不變性，非常適合對尺度變化的目標進行跟蹤，但是由于所要計算的數據量較大，時間復雜度高，嚴重影響了跟蹤算法的執(zhí)行效率［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算法。它們雖然提高了算法速度，但算子描述質量都不是很高，算法的穩(wěn)定性有所下降。

本文在積分直方圖的框架下，兼顧算法的實時性和穩(wěn)定性，對快速SIFT算法中的特征描述子進行了改進，用圓形代替矩形并對區(qū)域進行分層，越靠近關鍵點層數越多，相當于對中心區(qū)域進行加權，并通過仿真給出最佳加權層數和特征描述子方向數。本文算法不但能夠保證匹配的實時性和穩(wěn)定性，而且具有較高的魯棒性，能夠滿足目標實時跟蹤的要求。

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)所示的原圖像斜線區(qū)域灰度值或灰度平方的總和，即:

或

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

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

圖1 基于積分圖求取W區(qū)域的圖像能量

在求取窗口的灰度值總和或灰度平方總和時，如圖1 (b)所示，不管窗口W大小如何均可以用積分圖像的4個相應點(i1，j1)，(i2，j2)，(i3，j3)，(i4，j4)快速計算出來，即窗口W的灰度值或灰度值的平方總和為

與單純計算像素總和的求和運算相比，該算法只需要3個加減運算就可以求出一定區(qū)域的圖像能量，大大提高了計算速度。

1.2 構造DOM(difference-of-mean)尺度空間

利用積分圖像，通過不同大小的窗口W來計算圖像均值，構建尺度空間，如圖2所示。

圖2 尺度空間示意圖

對DOM區(qū)域進行歸一化處理

其中，s1、s2分別為最小和最大窗口的尺寸，sensitivity為s1內部區(qū)域內的灰度均值與外部區(qū)域s1－s2區(qū)域灰度均值的最小比值。

1.3 生成特征描述子

特征描述子的生成是特征匹配的關鍵，它的穩(wěn)定與否直接關系到特征匹配的效果。

為了提高生成特征描述子的實時性，采用積分直方圖的方法計算關鍵點方向。積分直方圖是借用積分圖像的思想，首先求取整幅圖像的積分直方圖，即每個像素的積分直方圖都是其左上角所有像素的梯度直方圖的和，那么任何位置和大小矩形區(qū)域的梯度直方圖的和可以用類似圖1的方法通過3次加法計算得來，提高了算法的實時性。

2 改進后的快速SIFT算法

在特征關鍵點周圍，越靠近關鍵點的區(qū)域對關鍵點的特征描述影響越大，經典的SIFT算法對關鍵點周圍4個特征區(qū)域的梯度方向進行了高斯加權，但Michael Grabner提出的快速SIFT算法中并沒有這一步驟，穩(wěn)定性有所下降。同時匹配搜索過程中，維數較高，K－D樹搜索效率并不高，甚至接近窮舉搜索的運算速度［8］。為此，為了滿足跟蹤實時性要求必須對特征描述子進行處理。

通過對特征區(qū)域進行分析可知，與關鍵點距離相同的點對關鍵點特征描述的影響是相同的，即若關鍵點周圍以關鍵點為圓心劃分不同的圓環(huán)，在同一圓環(huán)內的特征區(qū)域對對關鍵點的特征描述是相同的，越靠近特征關鍵點層數越多，這樣就相當于對中心區(qū)域進行了加權。同時，圓形區(qū)域可以減少鄰域角度歸零的步驟，將矩形區(qū)域改為同心圓區(qū)域，還可以省去高斯的模糊的步驟，提高了算法的實時性。改進的SIFT算法特征描述子如圖3所示。

圖3 不同層數的分割方式

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

Step 1:提取以關鍵點為中心，直徑為16的圓形窗口區(qū)域作為鄰域，保證生成的特征描述子所需要計算的鄰域范圍和原算法基本一致;

Step 2:如圖3，將半徑為8的圓形鄰域以2為間隔分為4個的同心圓，每個格子代表一個像素值;

Step 3:對于4個同心圓區(qū)域，分別求出其8個方向(45°、90°、135°、180°、225°、270°、315°、360°)的梯度累加值。由中心向外，取第一個圓環(huán)的8維向量作為特征向量的第1至第8個元素，取第二個圓環(huán)的8維向量作為特征向量的第9至第16個元素，以此類推。這樣，特征點描述子即為4×8 =32維向量;

Step 4:為了確保旋轉不變性，需對特征向量進行排序操作。設D是一個關鍵點的特征向量，D1、D2、D3、D4分別是從中心向外的4個圓環(huán)的特征向量，則D=(D1，D2，D3，D4)，其中Di=(di1，di2，…，di7，di8)，i∈［1，4］。首先標記半徑最小的圈中最大值出現(xiàn)的位置，即d11，d12，…，d17，d18中的最大值，若d11為最大值，則不需做任何處理，若d11不是最大值，需進行如下操作:將D1、D2、D3、D4同時循環(huán)左移，直至D1中的最大值為特征向量D1中的第一位，例如d17為向量D1中的最大值，循環(huán)左移之后4個圓環(huán)的特征向量變?yōu)镈i= (di7，di8，…，di1，di2，…，di6)。如果將每一個8維向量分別取向量的最大值并執(zhí)行此步操作，則匹配的效果會大大降低。這樣操作確保了4個圓環(huán)旋轉相同的角度，等同于原算法中鄰域歸零的操作，從而保證了改進描述子具有選擇不變性。

從圖3中可以看出，當層數為1層時其特征區(qū)域只是一個半徑為16的鄰域，當層數為2層時，其特征區(qū)域一部分為關鍵點周圍半徑為8的鄰域，另一部分為關鍵點周圍半徑為16的鄰域，這樣靠近關鍵點的部分就重復利用了2次，相當于對其進行了加權。以此類推，當層數為4層時，特征區(qū)域分為4部分，關鍵點周圍半徑為2的鄰域相當于進行了4次加權。這樣假設分為4層，梯度方向為8方向，這時特征關鍵點維數為4×8=32，提高了特征關鍵點匹配的速度。但這種方法由于減少了特征區(qū)域，算法穩(wěn)定性大大降低，為此可以通過提高梯度直方圖的方向數來提高算法的穩(wěn)定性。

3 實驗結果及分析

兼顧算法的穩(wěn)定性與實時性，本文對目標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%左右，圖像的跟蹤不同于圖像的配準，圖像跟蹤只需要檢測到正確的匹配點即可確定目標的位置，因此在后續(xù)跟蹤中選用24維的特征描述子是可行的。

圖5 改進后的分割層數和梯度方向

3.2 本文算法與原算法的實驗對比

為了驗證改進后的特征描述子的匹配性能，現(xiàn)分別從目標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種算法的優(yōu)劣，現(xiàn)將2種算法的匹配時間和匹配正確率進行比較，如表1所示。

圖7 目標T2的4組采用快速SIFT算法和改進快速SIFT算法的匹配對比圖片

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

從表1中可以看出，本文的SIFT算法在匹配時間上縮短了近1/2，而匹配正確率只有小幅降低，對匹配結果影響不大，因此改進后的快速SIFT算法對圖像進行實時跟蹤是可行的。

3.3 魯棒性分析

圖8為采用上述的24維特征描述子進行匹配的結果，匹配關鍵點數目為20個，誤匹配點為1個。

圖8 目標模板與實時圖匹配結果

為驗證該算法的魯棒性，現(xiàn)將目標模板分別旋轉90°和縮小一倍再進行匹配，結果如圖9和圖10所示。

圖9 目標模板旋轉900后的匹配結果

圖10目標模板縮小一倍后匹配結果

圖9 為目標模板旋轉90°后的匹配結果，匹配關鍵點數目為21個，誤匹配點為1個;圖10為目標模板縮小一倍后的匹配結果，匹配關鍵點數目為18個，誤匹配點為0個。由此可知，當實時圖與目標模板之間尺度、角度相差較大時該算法仍能準確地檢測到目標，魯棒性好。

4 結束語

快速SIFT(Scale Invariant Feature Transform)算法采用積分圖像代替高斯濾波提高了算法速度，但去掉了高斯加權環(huán)節(jié)，算法穩(wěn)定性有所下降。本文對快速SIFT算法中的特征描述子進行了改進，用圓形代替矩形并對區(qū)域進行分層，越靠近關鍵點層數越多，相當于對中心區(qū)域進行了加權，并通過仿真給出了最佳加權層數和特征描述子方向數。仿真實驗表明:本文算不但具有很好的實時性和穩(wěn)定性，而且具有較高的魯棒性，能很好地滿足目標實時跟蹤要求。

［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，F(xiàn)rahm 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.

本文引用格式:齊乃新，曹立佳，楊小岡，等.基于圓環(huán)域描述的改進快速SIFT算法［J］.四川兵工學報，2014(7):91－95.

10.11809/scbgxb2014.07.026

2014－03－09

國家自然科學基金項目(61203189)。

齊乃新(1989—)，男，碩士，主要從事視覺導航方面的研究;曹立佳，男，博士，講師，主要從事精確制導方面的研究;楊小岡，男，博士后，副教授，主要從事圖像領域的研究。

TP391