基于SIFT圖像特征提取與FLANN匹配算法的研究

王金龍, 周志峰

(上海工程技術(shù)大學(xué)，上海 201600)

0 引言

特征點的檢測和匹配是計算機(jī)視覺中非常重要的技術(shù)之一，在物體檢測、視覺跟蹤、三維重建等領(lǐng)域都有非常廣泛的應(yīng)用。

目前特征提取方法可以分為3種：一是基于所制定模板的特征檢測，二是基于圖形邊緣的特征檢測，三是基于亮度變化特征檢測[1]。第一種由于設(shè)計的模板會隨著檢測圖像的變化而變化，所以遇到復(fù)雜的圖像時就顯得不適用，第二種必須先進(jìn)行邊緣化處理之后才可以進(jìn)行特征檢測，第三種就是目前的研究熱點，Harris[2]、SIFT、SURF均屬于這種類型。目前國內(nèi)外學(xué)者已經(jīng)在這方面做了大量的研究。圖像的特征匹配技術(shù)主要分為兩類，一是基于灰度值的圖像匹配，二是基于特征的圖像匹配方法，其中基于灰度值的匹配方法，主要是利用空間中一維或者二維的滑動模板實現(xiàn)圖像的匹配，這樣做的優(yōu)點在于匹配率高，然后計算量太大，所以匹配時間會比較長。而基于特征的圖像匹配的這種方法，主要是通過提取出圖像的一些顯而易見的穩(wěn)定的特征，將不同圖像中的一些相同性質(zhì)關(guān)聯(lián)起來，由于不需要窮舉匹配，所以匹配速度較快。本文將SIFT特征提取與FLANN匹配算法結(jié)合在一起，實現(xiàn)了對兩幅圖像的特征匹配，并通過VS2015與Opencv庫結(jié)合，用C++語言進(jìn)行特征提取與匹配算法的實現(xiàn)，并驗證了在旋轉(zhuǎn)，亮度變化的情況下仍然能實現(xiàn)較精確的匹配結(jié)果。

1 特征點提取算法(SIFT)

SIFT(Scale-invariant feature transform)是一種檢測局部特征的算法，該算法通過求一幅圖中的特征點及其有關(guān)的scale和orientation的描述子得到特征并進(jìn)行圖像特征點匹配，SIFT特征不僅僅具有尺度不變性，即使改變旋轉(zhuǎn)角度，圖像的亮度等條件，也能實現(xiàn)很好的檢測效果。文章會針對SIFT特征做相應(yīng)的理論分析，并驗證這一結(jié)論，并與FLANN匹配算法結(jié)合，實現(xiàn)快速準(zhǔn)確的匹配。大致分為以下幾個步驟：構(gòu)建尺度空間，LOG近似DOG找到關(guān)鍵點及檢測DOG尺度空間的極值點，精確定位特征點，確定特征點的方向，最后生成SIFT特征描述子。

1.1 構(gòu)建尺度空間

尺度空間理論就是利用高斯核函數(shù)對圖像進(jìn)行尺度變換來模擬圖像數(shù)據(jù)的多尺度特征。獲得圖像在尺度空間下的多尺度序列表示。高斯卷積核是實現(xiàn)尺度變換的唯一線性核，如式1所示，一幅二維圖像的尺度空間可以表示為[3]：

L(x,y,σ)=G(x,y,σ)*I(x,y)

(1)

其中：G(x,y,σ)是尺度可變高斯函數(shù)，隨著尺度因子σ不同，將會產(chǎn)生不同尺度下的一組圖像L(x,y,σ)，稱為高斯尺度空間，σ大小決定圖像的平滑程度，大尺度主要展示了圖像的大致的外貌特征，小尺度主要展示圖像的細(xì)節(jié)部分[4]。大的σ值表示是圖像比較粗糙的尺度(低分辨率)，反之，對應(yīng)精細(xì)的尺度(高分辨率)，圖1顯示了Gaussian尺度空間中隨著的值的變化圖像變的越來越模糊。為了有效地在尺度空間檢測到穩(wěn)定的關(guān)鍵點，提出了高斯差分尺度空間(DOGscale-space)。如式2所示，采用了不同尺度的高斯差分核與圖像卷積生成，如圖1所示。

圖1 DOG產(chǎn)生的原理圖

(2)

對于尺度空間而言，在Lowe的論文中，他將第0層的初始尺度定義為1.6，也就是說最模糊的，圖片的初始尺度定義為0.5(最清晰)，在檢驗極值點之前，Lowe建議在建立尺度空間之前，需要對原圖進(jìn)行長寬的擴(kuò)展，以保留更多的圖片信息，增加特征點的數(shù)量。

對于圖像金字塔的建立問題，對于一幅圖像，建立其在不同尺度(scale)的圖像，也成為子八度，這是為了保證其尺度不變性(scale-invariant)，也就是在任何尺度都能夠有對應(yīng)的特征點，第一個子八度的scale為原圖大小(金字塔的最底端)，后面每個octave為上一個octave降采樣的結(jié)果，即原圖的1/4(長寬分別減半)，構(gòu)成下一個子八度(高一層金字塔)。每上一層是對下一層做Laplacian變換。

1.2 檢測DOG空間的極值點

為了檢測出高斯差分尺度空間中的存在的極值點，所選中的每一個采樣點均要和周圍的26個鄰域點比較，即同尺度中相鄰的8個像素點和上下相鄰尺度的各9個像素點，總共26個像素點相比較，當(dāng)采樣點比這26個鄰域點大或者小時，則將此點看作是候選的關(guān)鍵點[5]，如圖2所示。

圖2 極值點查找 圖3 離散空間極值與連續(xù)極值

在進(jìn)行極值比較的過程中，每一組圖像中的首末兩層是無法進(jìn)行極值比較的，為了滿足尺度變化的連續(xù)性，對每組圖像的頂層使用高斯模糊生成3幅圖像，高斯金字塔每一組有S+3層圖像，DOG金字塔有S+2層。

1.3 精確定位特征點

如圖3所示，展示了二維函數(shù)在離散空間里面所求出來的極值點與連續(xù)空間中的極值點區(qū)別。

通過擬合三維二次函數(shù)以準(zhǔn)確的確定關(guān)鍵點的位置和尺度(達(dá)到亞像素要求)，同時去除一些不穩(wěn)定的邊緣特征點，提高匹配的準(zhǔn)確度和穩(wěn)定性，主要分為以下幾個步驟：

1)使用子像素插值的方法，通過對離散的空間點不斷的插值可以求出連續(xù)的空間中的極值點，對尺度空間DOG函數(shù)進(jìn)行子像素插值也就是數(shù)學(xué)上的曲線擬合[6]，運(yùn)用DOG函數(shù)在尺度空間里面的泰勒級數(shù)展開式，如式(3)所示：

(3)

對式(3)求導(dǎo)，然后讓這個導(dǎo)數(shù)等于0，即可解出相對極值的偏移量，這樣可以得到相應(yīng)極值點:

(4)

所得到極值點xmax的亞像素的位置。如果偏移值大于0.5這個條件成立，這就說明靠近另一側(cè)的像素點，這時候讓另一側(cè)的像素選為候選的特征點，循環(huán)重復(fù)上面的計算，這樣就可以獲得新的亞像素的位置，之后在用該亞像素精度的位置取代所有尺度之前的候選的特征點位置[7]。

2)在已經(jīng)檢測出的所有的特征點中，需要去去除一些無關(guān)的響應(yīng)點，比如一些低對比度的特征點和一些不穩(wěn)定的邊緣響應(yīng)點。把公式(4)代入公式(3)，即在DOG Space的極值點處取值，只取前兩項可得，如式(5)所示：

(5)

1.4 確定特征點的方向

關(guān)鍵點領(lǐng)域像素的梯度方向是不同的，根據(jù)他們分布特性的不同為每一個關(guān)鍵點指定一個確定的方向，使其可以具備旋轉(zhuǎn)不變性。這也是判斷特征子優(yōu)越性的一個重要因素。

針對于窗口的每一個采樣點L(x,y)，其梯度方向的幅值和方向分別可以用m(x,y)和θ(x,y)公式表示，分別如式(6)和式(7)：

(L(x,y+1)-L(x,y-1))2

(6)

(7)

每一個關(guān)鍵點需要3個信息：位置，尺度，方向，這樣可以確定一個SIFT特征區(qū)域。

做一個包含所有梯度方向的分布直方圖，取值范圍是一個圓周0～360°，劃分每10°為一個bin，這樣可以分為36個bin。每個采樣點根據(jù)其梯度方向θ(x,y)加權(quán)統(tǒng)計到分布直方圖中，取幅度m(x,y)與貢獻(xiàn)因子的乘積為規(guī)定的權(quán)值。貢獻(xiàn)因子定義為采樣點到關(guān)鍵點即窗口中心的距離長度，距離的量度遵循以下原則：如果距離越大，那么貢獻(xiàn)因子就會越小反之則會越大，選擇分布直方圖的最大值為所選關(guān)鍵點在此鄰域梯度方向中的主要方向[8]，如圖4所示。

圖4 特征點方向的確定示意圖

1.5 生成SIFT特征描述子

SIFT描述子是關(guān)鍵點領(lǐng)域高斯圖像統(tǒng)計結(jié)果的一種表示，特征描述子意味著特征點的一切信息包括梯度方向、幅值等等，為了能夠提高穩(wěn)定性，優(yōu)秀的特征描述子應(yīng)當(dāng)包括此特征點的位置和灰度信息，除此之外，還需要反映這個特征點的一些局部的灰度變化信息。SIFT特征描述子就是一個高維向量，它包含著特征點的領(lǐng)域的所有信息，生成特征描述子之前，首先應(yīng)該確定特征點鄰域內(nèi)像素的主方向，我們可以選擇0度作為主方向，這樣就可以消除旋轉(zhuǎn)變換所帶來的影響，其次在每個4×4的16個區(qū)域中統(tǒng)計每個領(lǐng)域中的8個方向的梯度方向分布直方圖。圖5中，選取了16×16的鄰域，要統(tǒng)計16個分布直方圖，所選擇的每個直方圖均代表了該領(lǐng)域內(nèi)8個方向的信息，這樣就構(gòu)成了128維的特征點描述子。

圖5 16X16的特征點描述子

特征描述子需要具有光照不變性，我們可以將特征向量通過式(8)歸一化為單位長度，下文的實驗表現(xiàn)出很好的匹配效果。

(8)

2 特征匹配最近鄰算法FLANN

在現(xiàn)代化的機(jī)器學(xué)習(xí)中，訓(xùn)練一個高維特征數(shù)據(jù)，然后找到訓(xùn)練數(shù)據(jù)中的最近鄰計算是需要花費(fèi)很高的代價的。對于一個高維特征，目前來說最有效的方法是The randomized k-d forest和The priority search k-means tree，而對于二值特征的匹配multiple hierarchical clustering trees則比LSH方法更加有效[9]。圖6顯示了特征匹配的一般步驟，目前來說，fast library for approximate nearest neighbors(FLANN)可以很好地解決這些問題，Muja和Lowe于2009年提出FLANN算法，F(xiàn)LANN算法模型的特征空間一般是n維實數(shù)向量空間，該算法的核心是通過使用歐式距離來尋找與實例點的最鄰近的點，歐式距離的定義如式(9)所示。

圖6 特征匹配的一般步驟

(9)

如果D值越小，這就表明了這些特征點對之間的距離越”近”，也就是說它們相似程度越高。

2.1 快速近似NN匹配

2.1.1 隨機(jī)K-d樹算法

1)Classic k-d tree求取出數(shù)據(jù)中方差最高的那個維度，然后利用這個維度的數(shù)值將數(shù)據(jù)劃分成2個部分，接著對每個子集重復(fù)上述的相同的計算步驟。

2)Randomized k-d tree通過創(chuàng)建許多顆隨機(jī)樹，然后從那些具有最高方差的N-d維中隨機(jī)選取一些維度，并用這些維度來對數(shù)據(jù)進(jìn)行劃分。另外在對隨機(jī)K-d森林進(jìn)行搜索時，所有K-d均屬于同一個優(yōu)先級。從理論上說，如果增加樹的數(shù)量，就能提高搜索速度[10]，提高效率，但由于硬件方面的種種限制，樹的數(shù)量需要控制在一定的范圍內(nèi)，如果超出了速度不會增加甚至?xí)兟瑢崿F(xiàn)原理如圖7所示。

圖7 隨機(jī)K-d森林的實現(xiàn)原理

2.1.2 層次聚類樹

層次聚類樹采用的是K-medoids的聚類方法，而不是K-means，在本算法中，并沒有像在K-medoids聚類算法中直接求最小化方差求聚類中心，而是在輸入數(shù)據(jù)中隨機(jī)選取聚類中心，這種建立方式顯得更加簡單，也可以保持各個樹之間的獨(dú)立性，在建立多棵樹的同時，這個方法的搜索性能就提高了很多，這主要是因為隨機(jī)選取的聚類中心，而不需要多次迭代計算聚類中心。建立多顆隨機(jī)數(shù)的方法在K-d tree中比較有效，在K-means tree中卻不適用。

2.1.3 優(yōu)先搜索K-means樹算法

隨機(jī)k-d森林適用范圍比較廣，在很多情況下均有不錯的搜索效果，然后如果對精度要求比較高，這樣k-means樹效果會更加好一點。K-means tree充分挖掘了數(shù)據(jù)本身所固有的一些機(jī)構(gòu)特征，原理則是將數(shù)據(jù)的所有維度進(jìn)行聚類處理，與之前的隨機(jī)k-d tree只使用了一次維度劃分[11]。本文采用的是K-means樹的搜索原理，算法描述如下：

1)建立層次化的K-means樹;

2)樹的節(jié)點就選層次化的聚類中心;

3)如果某個duster內(nèi)的點的數(shù)量小于K時，在這樣的前提下就選擇這些數(shù)據(jù)節(jié)點為葉子節(jié)點;

4)從根節(jié)點N開始檢索;

5)如果N是葉子節(jié)點，則將處于相同層次的葉子節(jié)點添加到搜索結(jié)果中去，此時count + = |N|;

6)相反，如果N不是葉子節(jié)點，則將它的子節(jié)點與queryQ比較，找出最近的那個節(jié)點Cq，并將同層次的其他節(jié)點加入到我們所考慮的優(yōu)先隊列中;

7)對Cq節(jié)點進(jìn)行遞歸搜索;

8)如果優(yōu)先隊列不為空和count

在匹配的過程中難免會出現(xiàn)錯誤的匹配對，通過K-mean算法處理之后，匹配的精度達(dá)到很高，速度也比較快。

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

本次實驗中，通過對兩幅圖像分別進(jìn)行旋轉(zhuǎn)，縮放以及改變光照條件，檢測該組合算法的抗干擾性以及匹配的成功率，檢查匹配的準(zhǔn)確率和速度。

3.1 光照變化

通過改變匹配時某個圖片的光照情況(圖片的亮度)，檢測特征描述子對光照變化的適應(yīng)情況，實驗結(jié)果如圖8所示。

3.2 縮放變化

通過對匹配的物體進(jìn)行縮放，檢測縮放前后特征點匹配情況，實驗結(jié)果如圖9所示。

圖8 不同光照情況的結(jié)果圖

圖9 物體縮放前后匹配對比圖

3.3 旋轉(zhuǎn)變化

同一場景下，對物體進(jìn)行不同角度的旋轉(zhuǎn)，通過對比，得出文章中組合算法對旋轉(zhuǎn)變化的適應(yīng)能力，結(jié)果如圖10所示。

3.4 SIFT與SURF對比

本文采用SIFT特征提取與FLANN匹配算法結(jié)合的方法，對匹配圖像進(jìn)行了綜合性的實驗，并與SURF特征提取與匹配進(jìn)行了對比，對比結(jié)果圖11所示。

圖10 不同旋轉(zhuǎn)角度圖像間匹配圖

圖11 SIFT與SURF提取匹配對比

特征提取的方法特征點個數(shù)匹配點運(yùn)行時間/s成功率/%SIFT120901.375SURF115890.977

從實驗結(jié)果中可以看出SIFT算法的匹配準(zhǔn)確度比SURF高很多，但是由于SIFT算法的復(fù)雜性，在特征點提取的過程中，時間較長。通過實驗SIFT和SURF特征匹配的數(shù)據(jù)如表1所示。

4 結(jié)論

特征點提取是圖像處理領(lǐng)域重要的一個環(huán)節(jié)，是接下來的圖像匹配的前提，本文采用SIFT算法提取的圖像的特征點，并與SURF特征點進(jìn)行了簡單的對比，SURF算法的準(zhǔn)確性較SIFT高很多，SIFT對特征細(xì)節(jié)的表達(dá)也比SURF高很多，通過本次實驗分析，可以得出SIFT特征算子對縮放、旋轉(zhuǎn)、亮度變化的適應(yīng)能力較強(qiáng)。雖然存在一些誤差，但整體準(zhǔn)確度比較高，滿足一定的匹配要求。本文所采用的FLANN匹配算法的K-means tree匹配的準(zhǔn)確率高，應(yīng)用場景較廣。本文的算法組合缺點也很明顯，問題主要是在SIFT特征提取的時間比較長不能很好的應(yīng)用到實時性處理中，但可以將SIFT與LBP特征結(jié)合[12]，可以提高效率，改善算法。實驗結(jié)果表明，本文的組合算法對圖像的亮度，旋轉(zhuǎn)，縮放等各個方面都有較強(qiáng)的適應(yīng)性。可以應(yīng)用與圖像識別，三維重建等熱門領(lǐng)域，在后續(xù)的研究中，提高SIFT算法的效率是關(guān)鍵，可以通過改進(jìn)SIFT特征提取的步驟來提高提取速度。

[1] 譚博怡. 圖像特征提取與匹配[D]. 北京: 中國科學(xué)院研究生院, 2008.

[2] Harris C, Stephens M. A combined corner and edge detector [A].Manchester: Proceedings of the 4thAlvey Vision Conference[C]. Manchester, UK, 1988: 147-151.

[3] Lowe D G. Object Recongnition from Local Scale-Invariant Keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[4] Schmid C, Mohr R, Bouckhage C. Evaluation of interest point detectors[J]. International Journal of Computer Vision, 2000, 37(2): 151-172.

[5] Bay H, Tuytelaars T, Van Gool L. SURF: speeded up roubst features [A].Proceedings of European Conference on Computer Vision[C]. Graze, Austria, 2006: 404-407.

[6] Marius Muja, Lowe D G. Scalable Nearest Neighbor Algorithms for High Dimensional Data[J].

[7] Brown M, Lowe D. Invariant features from interest point groups[A].British Machine Vision Conference[C]. Cardiff, Wales, 2002: 656-665.

[8] Moller T, Haines E, Akenine-Moller T. 實時極端及圖形學(xué)[M]. 普建濤,譯. 北京:北京大學(xué)出版社.

[9] Muja M, Lowe D G. Fast approximate nearest neighbors with automatic algorithm configuration [A].Proceedings of IEEE Conference on Computer Vision Theory and Applications[C]. Lisbon, Portugal: IEEE Computer Society, 2009: 331-340

[10] 劉樹勇, 楊超慶, 位秀雷，等, 鄰近點快速搜索方法在混沌識別中的應(yīng)用[J]. 華中科技大學(xué)學(xué)報, 2012, 40(11): 89-92.

[11] 崔江濤, 劉衛(wèi)光. 一種多分辨率高維圖像特征匹配算法[J]. 光子學(xué)報, 2005, 34(1):138-141.

[12] Zhao G, Pietikainen M. Dynamic texture recognition using local binary patterns with an application for facial expressions[A]. Asia Conference on Computer Vison(ACCV)[C]. 2011(3):281-292.