王金龍, 周志峰

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

0 引言

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

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

1 特征點(diǎn)提取算法(SIFT)

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

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

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

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

(1)

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

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

(2)

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

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

1.2 檢測(cè)DOG空間的極值點(diǎn)

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

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

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

1.3 精確定位特征點(diǎn)

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

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

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

(3)

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

(4)

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

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

(5)

1.4 確定特征點(diǎn)的方向

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

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

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

(6)

(7)

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

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

圖4 特征點(diǎn)方向的確定示意圖

1.5 生成SIFT特征描述子

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

圖5 16X16的特征點(diǎn)描述子

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

(8)

2 特征匹配最近鄰算法FLANN

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

圖6 特征匹配的一般步驟

(9)

如果D值越小，這就表明了這些特征點(diǎn)對(duì)之間的距離越”近”，也就是說(shuō)它們相似程度越高。

2.1 快速近似NN匹配

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

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

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

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

2.1.2 層次聚類(lèi)樹(shù)

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

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

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

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

2)樹(shù)的節(jié)點(diǎn)就選層次化的聚類(lèi)中心;

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

4)從根節(jié)點(diǎn)N開(kāi)始檢索;

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

3.1 光照變化

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

3.2 縮放變化

通過(guò)對(duì)匹配的物體進(jìn)行縮放，檢測(cè)縮放前后特征點(diǎn)匹配情況，實(shí)驗(yàn)結(jié)果如圖9所示。

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

圖9 物體縮放前后匹配對(duì)比圖

3.3 旋轉(zhuǎn)變化

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

3.4 SIFT與SURF對(duì)比

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

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

圖11 SIFT與SURF提取匹配對(duì)比

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

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

4 結(jié)論

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

[1] 譚博怡. 圖像特征提取與匹配[D]. 北京: 中國(guó)科學(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. 實(shí)時(shí)極端及圖形學(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] 劉樹(shù)勇, 楊超慶, 位秀雷，等, 鄰近點(diǎn)快速搜索方法在混沌識(shí)別中的應(yīng)用[J]. 華中科技大學(xué)學(xué)報(bào), 2012, 40(11): 89-92.

[11] 崔江濤, 劉衛(wèi)光. 一種多分辨率高維圖像特征匹配算法[J]. 光子學(xué)報(bào), 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.