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

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

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

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

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

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

快速SIFT算法;特征匹配;目標(biāo)跟蹤;實時性

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

SIFT算法提取的特征點具有尺度不變性，非常適合對尺度變化的目標(biāo)進行跟蹤，但是由于所要計算的數(shù)據(jù)量較大，時間復(fù)雜度高，嚴重影響了跟蹤算法的執(zhí)行效率［3］。為此，很多學(xué)者對SIFT算法進行了改進，如SinhaSN［4］提出了一種基于圖形處理單元(GPU)的SIFT高效算法;Matas J等［5］采用積分直方圖和測定海森矩陣(Determination ofHessian matrix)對SIFT進行了加速，提出了SURF(Speeded Up Robust Features)算法，Michael Grabner［6］提出了利用積分圖像近似替代SIFT的算法步驟，提出了Fast Approximated SIFT算法。它們雖然提高了算法速度，但算子描述質(zhì)量都不是很高，算法的穩(wěn)定性有所下降。

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

1 快速SIFT算法

由于經(jīng)典的SIFT算子構(gòu)造尺度空間采用Gaussian卷積的方式，計算量大，不滿足實時性要求，2006年Michael Grabner［6］利用積分圖像來構(gòu)造尺度空間，大大提高了特征關(guān)鍵點的提取速度。

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個相應(yīng)點(i1，j1)，(i2，j2)，(i3，j3)，(i4，j4)快速計算出來，即窗口W的灰度值或灰度值的平方總和為

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

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

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

圖2 尺度空間示意圖

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

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

1.3 生成特征描述子

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

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

2 改進后的快速SIFT算法

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

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

圖3 不同層數(shù)的分割方式

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

Step 1:提取以關(guān)鍵點為中心，直徑為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:為了確保旋轉(zhuǎn)不變性，需對特征向量進行排序操作。設(shè)D是一個關(guān)鍵點的特征向量，D1、D2、D3、D4分別是從中心向外的4個圓環(huán)的特征向量，則D=(D1，D2，D3，D4)，其中Di=(di1，di2，…，di7，di8)，i∈［1，4］。首先標(biāo)記半徑最小的圈中最大值出現(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)旋轉(zhuǎn)相同的角度，等同于原算法中鄰域歸零的操作，從而保證了改進描述子具有選擇不變性。

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

3 實驗結(jié)果及分析

兼顧算法的穩(wěn)定性與實時性，本文對目標(biāo)T1、T2選擇不同的加權(quán)層數(shù)和描述子方向數(shù)進行仿真對比。

3.1 特征描述子可行性分析

分別取目標(biāo)T1和目標(biāo)T2序列圖中的40幀圖像與其對應(yīng)的間隔10幀后的圖像進行匹配，圖4(a)是對目標(biāo)T1的40組圖片在梯度方向個數(shù)不同的平均正確匹配率，圖4(b)是對目標(biāo)T2的40組圖片在梯度方向個數(shù)不同的平均正確匹配率。橫軸表示關(guān)鍵點周圍鄰域的分割層數(shù)，分割層數(shù)越多表明中心部分加權(quán)次數(shù)越多;縱軸表示特征關(guān)鍵點的匹配正確率。

圖4 不同分割層數(shù)和方向數(shù)圖像匹配正確率

從圖4可以看出方向數(shù)為12，分割層數(shù)為2時，增加方向數(shù)目或分割層數(shù)其匹配精確度增加不明顯。因此，為提高時效性選擇最終的梯度方向為12，分割層數(shù)為2，如圖5所示。這樣就形成了12×2=24維描述子，降低了特征向量的維數(shù)，提高了匹配搜索效率。

雖然，在圖5中當(dāng)采用24維描述子時仍然只能維持在60%左右，圖像的跟蹤不同于圖像的配準(zhǔn)，圖像跟蹤只需要檢測到正確的匹配點即可確定目標(biāo)的位置，因此在后續(xù)跟蹤中選用24維的特征描述子是可行的。

圖5 改進后的分割層數(shù)和梯度方向

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

為了驗證改進后的特征描述子的匹配性能，現(xiàn)分別從目標(biāo)T1和目標(biāo)T2的序列圖像中選取4組圖像分別采用快速SIFT算法和本文提出的改進快速SIFT算法進行了匹配試驗，其中每組圖像都是間隔10幀的2幀圖像且其中加入了高斯噪聲。其結(jié)果如圖6和圖7所示。

圖6目標(biāo)T1的4組采用快速SIFT算法和改進快速SIFT算法的匹配對比圖片

圖6 和圖7為目標(biāo)T1和目標(biāo)T2在匹配閾值為0.7的情況下，分別采用快速SIFT算法和本文提出的改進快速SIFT算法的匹配結(jié)果圖。圖6和圖7中(a1)、(b1)、(c1)、(d1)為采用快速SIFT算法的匹配圖像，圖6和圖7中(a2)、(b2)、(c2)、(d2)為與之對應(yīng)的采用改進快速SIFT算法的匹配結(jié)果圖。為了能夠更加直觀地比較2種算法的優(yōu)劣，現(xiàn)將2種算法的匹配時間和匹配正確率進行比較，如表1所示。

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

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

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

3.3 魯棒性分析

圖8為采用上述的24維特征描述子進行匹配的結(jié)果，匹配關(guān)鍵點數(shù)目為20個，誤匹配點為1個。

圖8 目標(biāo)模板與實時圖匹配結(jié)果

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

圖9 目標(biāo)模板旋轉(zhuǎn)900后的匹配結(jié)果

圖10目標(biāo)模板縮小一倍后匹配結(jié)果

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

4 結(jié)束語

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

［1］白廷柱，侯喜報.基于SIFT算子的圖像匹配算法研究［J］.北京理工大學(xué)學(xué)報，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］.哈爾濱工程大學(xué)學(xué)報，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算法在特征匹配中的應(yīng)用［J］.科學(xué)技術(shù)與工程，2013(11):3016－3020.

(責(zé)任編輯楊繼森)

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］.四川兵工學(xué)報，2014(7):91－95.

10.11809/scbgxb2014.07.026

2014－03－09

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

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

TP391