馮文斌，劉寶華

1.燕山大學(xué) 河北省并聯(lián)機器人與機電系統(tǒng)實驗室，河北 秦皇島 066004

2.燕山大學(xué) 機械工程學(xué)院，河北 秦皇島 066004

1 引言

圖像匹配是指通過對圖像進行對比，得到不同圖像之間的相似度。圖像匹配在物體識別、影像縫合和追蹤、機器視覺[1]及虛擬現(xiàn)實等領(lǐng)域應(yīng)用廣泛。

目前圖像匹配算法主要分為兩大類：基于灰度的匹配方法和基于特征的匹配方法?；诨叶鹊钠ヅ浞椒ㄖ饕每臻g一維或二維滑動模板進行圖像匹配，此方法不需對圖像進行復(fù)雜的預(yù)處理，而是利用圖像本身具有的灰度信息來度量圖像的相似程度，具有操作簡單、匹配率高等特點，但是運算量巨大，耗時較長。基于特征的匹配方法是在原始圖像中提取出具有顯著特征的點、線、面等匹配單元，并將這些匹配單元用于特征匹配，一般匹配速度很快，但是精度較低[2]?，F(xiàn)在對圖像進行特征提取最好的方法是由哥倫比亞大學(xué)的Lowe教授于1999年提出的SIFT算法[3]。SIFT算法是將尺度不變特征子與梯度方向描述子相結(jié)合，從而能對旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性，對視角變化、仿射變換和噪聲也保持一定程度的穩(wěn)定性。但是SIFT的特征描述子向量是128維[4]的，導(dǎo)致運算量過大，計算過于復(fù)雜，這對于實時性要求比較高的情況，如目標(biāo)在線識別、機器人單目視覺等存在一定的局限性。為降低特征描述子維數(shù)并提高匹配精度，科研人員提出了多種基于SIFT的改進算法[5]。將主成分分析法（Principal Component Analysis，PCA）與SIFT算法相結(jié)合[6]，可以對SIFT算子進行降維，特征描述子的維數(shù)可以從128維降到20維，但是匹配精度較差；國外的Mikolajczyk等人[7]及國內(nèi)的戴金波等人[8]都認(rèn)為采用圓形進行區(qū)域劃分比矩形具有更好的定位功能，用扇形構(gòu)建272維的梯度位置方向直方圖描述符，并用主成分分析法將其降為128維，提高匹配精度。

本文將在SIFT算法的基礎(chǔ)上采用新的關(guān)鍵點鄰域劃分方法，用分級的放射狀分區(qū)代替棋盤格式的塊狀分區(qū)[9]，構(gòu)造新的特征描述子[10]。進行關(guān)鍵點匹配時用馬氏距離雙向匹配方法代替歐氏距離匹配[11]，并利用RANSAC方法[12]進行特征匹配的優(yōu)化，提高匹配率。

2 SIFT算法

SIFT算法是在尺度空間的基礎(chǔ)上建立的，在圖像的尺度空間上找出圖像的局部極值點作為待選關(guān)鍵點，這些極值點并不全是穩(wěn)定的關(guān)鍵點，需要剔除低對比度的關(guān)鍵點和不穩(wěn)定的邊緣響應(yīng)點，以增強匹配穩(wěn)定性，提高抗噪能力，然后為每個觀點分配方向，生成關(guān)鍵點的特征描述子，使每個關(guān)鍵點包含有位置、尺度和方向信息，最后用特征描述子向量之間的歐氏距離對兩幅圖像中關(guān)鍵點的相似性進行判定，當(dāng)距離小于預(yù)設(shè)的閾值時判定這兩個關(guān)鍵點已匹配成功。

2.1 高斯尺度空間的建立

尺度空間思想最早是由Iijima在1962年提出的，經(jīng)Witkin和Koenderink等的改進和推廣逐漸得到關(guān)注。尺度空間將傳統(tǒng)的單尺度圖像信息處理技術(shù)納入尺度不斷變化的動態(tài)分析框架中，易于獲取圖像的本質(zhì)特征，并且能夠模擬人在距離目標(biāo)由近到遠(yuǎn)時目標(biāo)在視網(wǎng)膜上的形成過程。尺度空間需要使用高斯模糊來獲取，高斯卷積核是實現(xiàn)尺度變換的唯一變換核，并且是唯一的線性核[13]。

二維圖像I(x ,y)的尺度空間L(x ,y,σ)是一個變化尺度的高斯函數(shù)G(x ,y,σ)與原函數(shù)I(x ,y)的卷積：

代表圖像的像素位置，σ是尺度空間因子，值越小，圖像被平滑越少。

2.2 尺度空間極值點檢測

為在尺度空間檢測穩(wěn)定的關(guān)鍵點，需要建立圖像的高斯差分（Difference-of Gaussian，DOG）金字塔D( )x,y,σ，它是兩個相鄰尺度圖像的差：

在尺度空間中，一個點與本層和上下兩層中相鄰尺度共8+9×2=26個點進行比較，如果該點是最大值或最小值，則該點就是圖像上的一個極值點，在圖像空間和尺度空間都能檢測到。

2.3 關(guān)鍵點定位及方向分配

2.3.1 精確定位關(guān)鍵點

通過擬合一個三維二次函數(shù)能夠更精確地確定關(guān)鍵點的位置和尺度，去掉對比度低的關(guān)鍵點，同時通過主曲率設(shè)定閾值去掉DOG算子產(chǎn)生的不穩(wěn)定的邊緣響應(yīng)點。

2.3.2 關(guān)鍵點方向分配

用與每個關(guān)鍵點相鄰的鄰域點的梯度方向為每個關(guān)鍵點分配方向信息，使特征描述子具備旋轉(zhuǎn)不變性，梯度值和方向如下：

將關(guān)鍵點鄰域像素的梯度方向繪制成直方圖，直方圖的峰值方向就代表該關(guān)鍵點的方向，使得每一個關(guān)鍵點都包含有位置、尺度及方向三種信息。

2.4 生成特征描述子

特征描述子是對關(guān)鍵點的描述，通過對關(guān)鍵點周圍的像素區(qū)域進行劃分并得到各個區(qū)域的梯度直方圖，進而生成關(guān)鍵點的特征描述子，其是對圖像信息的一種抽象，方便進行圖像匹配。Lowe教授推薦的特征描述子是一個128維的向量。在關(guān)鍵點周圍取一個16×16大小的區(qū)域，以4×4大小的區(qū)域為一個種子點，得到16個種子點，如圖1（a），在每個種子點區(qū)域劃分有8個方向（每45°取一個方向），如圖1（b），將8個方向的梯度值累加并繪制梯度方向直方圖，得到一個128維的描述子向量。

圖1 像素窗口劃分和關(guān)鍵點梯度方向分配

2.5 特征匹配

圖像之間的匹配也就是對得到的圖像關(guān)鍵點進行匹配，采用最近鄰算法計算得到的最近鄰關(guān)鍵點的特征向量的歐式距離與次近鄰關(guān)鍵點的特征向量的歐氏距離的比值，并與設(shè)定的閾值比較，若比值小于設(shè)定閾值，則關(guān)鍵點匹配成功。

3 算法改進

3.1 特征描述子簡化

原算法的特征描述子是128維的，因為維數(shù)太高，使得構(gòu)建特征描述子以及最后進行匹配都需要很長時間，而且隨著關(guān)鍵點的增加錯誤匹配概率上升，剔除錯誤匹配的耗時增加，這對實時性的要求是不利的。又因距離關(guān)鍵點越近的像素對關(guān)鍵點特征描述子的貢獻(xiàn)越大，所以還要考慮像素與關(guān)鍵點距離的影響，對各個區(qū)域與關(guān)鍵點的距離進行加權(quán)，得到新的特征描述子。

本文對特征描述子的改進是在關(guān)鍵點區(qū)域大小不變的前提下，重新劃分16×16大小的矩形像素區(qū)域，將以前的棋盤格式的塊狀分區(qū)變成分級的放射狀分區(qū)，減少劃分的區(qū)域（既是減少種子點數(shù)量）。首先將關(guān)鍵點周圍8×8的矩形鄰域劃分成1×4=4個三角子鄰域，以45°為單位取每個三角區(qū)域8個方向上的梯度累加值，得到4×8=32維的特征描述子。然后將16×16大小的矩形像素區(qū)域的外圍依據(jù)對角線劃分為1×4=4個梯形鄰域，計算每個梯形鄰域內(nèi)8個方向上的梯度累加值，得到4×8=32維的特征描述子。最后將得到的兩個描述子疊加起來，但因兩種鄰域形狀不同、大小不同、方向尺度也有大的差別，需對兩種描述子梯度值進行平衡，同時為突出距離關(guān)鍵點越近，作用越大的思想，對兩類鄰域的梯度值進行加權(quán)。這樣總的特征描述子由這兩部分描述子構(gòu)成，用放射狀鄰域代替棋盤格式的方形鄰域，并進行加權(quán)計算，與SIFT算法的特征描述子相比，這樣得到的特征描述子更加全面，更能體現(xiàn)關(guān)鍵點的特征，也即是對圖像造成的信息損失更小，具體劃分如圖2所示。從而得到一個32+32=64維的特征描述子，比原算法的128維特征描述子減少了50%，必能降低SIFT算法的計算復(fù)雜度。為了保證旋轉(zhuǎn)不變性，需將最大的梯度值移到所得的64維特征描述子向量的第一個元素。描述子生成具體流程如圖3所示。

圖2 關(guān)鍵點鄰域分級放射劃分

圖3 簡化的特征描述子生成流程

為了保證光照的不變性，需將生成的64維特征描述子進行歸一化處理，歸一化方法為：

3.2 匹配算法改進

原算法采用歐氏距離來進行關(guān)鍵點匹配，匹配是單向進行的，即是從待匹配圖像中尋找與匹配圖像關(guān)鍵點相對應(yīng)的點，這種匹配簡單、快捷，但易產(chǎn)生誤配點，同時由于一個關(guān)鍵點能有多個方向，匹配時可能產(chǎn)生重復(fù)匹配。歐氏距離計算公式為：

而馬氏距離考慮了特征向量間的相關(guān)性，匹配時性能優(yōu)于歐氏距離。因此擬采用馬氏距離二次匹配算法。二次匹配在初始匹配后進行，基本思想是：

（2）ai和 bj間距離為 L(ai,bj)，bj和ai間距離為L(bj,ai)。

（3）當(dāng)L(ai,bj) L(ai,bx)＜R1，1≤x≤n，并且L(bj,ai)/L(bj,ax)＜R2，1≤x≤m，x≠j，x≠i時R1為正向匹配閾值，R2為反向匹配閾值。

對有m個樣本的樣本空間S={s1,s2,…,sm}其任意的樣本點si=(xi,yi)(i =1,2,…,m)到樣本均值μ=(μx,μy)的馬氏距離表示為：

式中，S為協(xié)方差矩陣，μ為樣本均值，且

對比歐氏距離和馬氏距離計算公式可以看出馬氏距離計算較歐氏距離復(fù)雜。在一次計算中歐氏距離需要64次乘法和一次開平方，而在馬氏距離的一次計算中需要128次乘法和一次開平方，運算所用時間相對較長。但是馬氏距離排除了量綱的影響，具有尺度無關(guān)性，同時排除了特征向量之間相關(guān)性的干擾，在進行關(guān)鍵點匹配時不會產(chǎn)生一點多配現(xiàn)象，匹配準(zhǔn)確度提高，消除錯誤匹配時間減少，整體效果優(yōu)于歐氏距離匹配。

3.3 消除錯誤匹配

運用馬氏距離雙向匹配算法雖然提高了匹配率，但是仍有不少誤配點，為了進一步濾除錯誤匹配，采用RANSAC（隨機抽樣一致性）算法，其突出優(yōu)點是能魯棒地估計模型參數(shù)，即是能從包含大量局外點的數(shù)據(jù)中估計出高精度的參數(shù)。

3.3.1 RANSAC算法原理

RANSAC算法是一種魯棒估計模型參數(shù)算法，通過迭代方式估計數(shù)學(xué)模型參數(shù)，對一組觀測數(shù)據(jù)集進行數(shù)學(xué)模型擬合，去除不屬于模型的局外點及噪聲[14-15]。RANSAC算法消除錯誤匹配即是尋找一個大小為3×3的單應(yīng)性矩陣H，使?jié)M足該矩陣的數(shù)據(jù)點個數(shù)最多，有

對矩陣H進行歸一化時令h33=1。

此時的單應(yīng)性矩陣H有8個未知參數(shù)，至少需要8個線性方程來求解，對應(yīng)到匹配點上，因為一組點可得到2個方程，則至少需要4組點才能求出矩陣H，其對應(yīng)關(guān)系為：

其中(x ,y)表示原圖角點位置，(x ′,y′)表示匹配圖角點位置，σ為尺度系數(shù)。

RANSAC算法從數(shù)據(jù)集中隨機抽取4個不共線的樣本，計算出單應(yīng)性矩陣H并利用得到的模型測試所有數(shù)據(jù)，計算滿足模型數(shù)據(jù)點的個數(shù)及代價函數(shù)J（即投影誤差），若模型為最優(yōu)模型，則對應(yīng)代價函數(shù)J最小，其公式為：

3.3.2 RANSAC算法具體過程

RANSAC算法通過不斷選擇數(shù)據(jù)集中的一組隨機子集來計算模型參數(shù)，被選取的子集被假設(shè)為局內(nèi)點。具體過程為：

（1）估計一個適用于假設(shè)的局內(nèi)點的模型，使所有的未知參數(shù)都能在此模型下從假設(shè)的局內(nèi)點計算得到。

（2）用估計的模型去驗證數(shù)據(jù)集中的其他數(shù)據(jù)，如果某個點適用于估計模型，則該點也是局內(nèi)點。

（3）如果有足夠多的點被認(rèn)為是假設(shè)的局內(nèi)點，則估計的模型就是合適的。

（4）用所有假設(shè)的局內(nèi)點重新估計模型。

（5）估計局內(nèi)點與模型的錯誤率來評估模型。

（6）重復(fù)執(zhí)行上述過程，每次估計的模型如果局內(nèi)點太少，則被舍棄，如果比現(xiàn)有模型好，則保留。

迭代次數(shù)k可以從理論上進行推斷。用p表示算法產(chǎn)生有用結(jié)果的概率，用w表示從數(shù)據(jù)集中選取一個局內(nèi)點的概率。假設(shè)估計模型時需要n個點，則wn表示所有n個點均為局內(nèi)點的概率，1-wn表示n個點中至少有一個為局外點的概率，而(1 -wn)k則表示算法永遠(yuǎn)選不到n個點均為局內(nèi)點的概率，則有：

迭代次數(shù)k的標(biāo)準(zhǔn)偏差為：

4 結(jié)果與分析

本次實驗的計算機配置為：聯(lián)想G470筆記本電腦，Intel酷睿i5-2430M處理器，頻率2.4 GHz，內(nèi)存4 GB。程序編制與運行平臺是Matlab R2012a。

為保證實驗結(jié)果更加具有說服力，測試圖像選用牛津大學(xué)機器人實驗室圖像庫中的一組圖像，圖像庫中包含有模糊圖像、旋轉(zhuǎn)和縮放圖像、視角圖像、光照圖像和JPEG壓縮圖像等典型的變換圖像。為使實驗結(jié)果不受因圖像大小的不同而產(chǎn)生的影響，將各幅圖像大小均調(diào)整為320像素×240像素。

4.1 匹配性能測試

運用SIFT算法和改進的SIFT算法對測試圖像進行匹配，匹配結(jié)果如圖4所示，紅色為SIFT算法匹配結(jié)果，亮藍(lán)色為改進的SIFT算法匹配結(jié)果。

對各測試圖像匹配后得到的匹配點對進行統(tǒng)計、分析后得到圖5。

用正確匹配率作為評價算法好壞的一個標(biāo)準(zhǔn)，其計算公式為：

圖4 匹配結(jié)果對比

圖5 總匹配對數(shù)對比

計算用SIFT算法和改進的SIFT算法得到的匹配圖形的正確匹配率，繪制圖6。

圖6 正確匹配率對比

由圖4中的（a）、（b）、（c）、（d）及圖5可以看出，改進后的SIFT算法的匹配點對數(shù)量明顯少于原SIFT算法，這可以明顯簡化匹配時的計算復(fù)雜度，提高匹配速度。觀察圖4（e）和圖5可以看出改進的SIFT算法對壓縮圖像匹配點數(shù)量的減少效果并不明顯，這是由于圖像的壓縮并未對圖像的信息造成損失，只是改變了圖像本身的大小，兩種算法提取出的關(guān)鍵點的總匹配對數(shù)基本相同。

觀察圖6可以看出，由于對生成特征描述子方法的改進，使生成的特征描述子獨特性增強，更能進一步反應(yīng)圖像的局部特征信息。同時對匹配算法的改進使對待匹配的兩關(guān)鍵點的特征描述子相似性度量更加準(zhǔn)確，正確匹配率平均增加10%～15%。對于模糊圖像，盡管總匹配對數(shù)減少較多，但正確匹配率相差不大，如圖4（a）所示。這是由于特征描述子生成方法的改進使其能更準(zhǔn)確地對關(guān)鍵點進行描述，減少了無效關(guān)鍵點數(shù)量，使正確匹配對數(shù)減少，正確匹配率提高較小。對于旋轉(zhuǎn)和縮放圖像，因為只改變了圖像的角度和尺寸大小，改進的SIFT算法對正確匹配率的提高并不明顯，如圖4（b）所示。改進的SIFT算法對視角圖像和光照圖像的正確匹配率差異較大，如圖4（c）、（d）所示。這主要是由于本文算法在匹配時采用的是馬氏距離，計算時引入了特征向量之間的相關(guān)性，降低了對視角和光照變化的敏感性，從而顯著提高了正確匹配率。

4.2 匹配時間測試

比較SIFT算法和改進的SIFT算法在圖像模糊、旋轉(zhuǎn)和縮放、視角改變、光照變化和JPEG壓縮下的圖像匹配所耗時間。由圖7可以看出，改進后的SIFT算法由于特征描述子的簡化運行速度大幅度提高，是原算法的5～10倍。并且隨著待匹配點數(shù)目的減少，匹配耗時也在相應(yīng)較少，故減少關(guān)鍵點數(shù)能明顯減少匹配耗時。

圖7 匹配耗時對比

5 結(jié)束語

本文算法對SIFT算法的特征描述子進行改進，將原有棋盤格式塊狀分區(qū)變成分級放射狀分區(qū)，得到的特征描述子由128維降為64維，提高了特征描述子對圖像局部特征的描述。并通過對特征描述子應(yīng)用馬氏距離雙向匹配方法進行匹配及采用RANSAC方法消除誤配點，使改進的SIFT算法在繼承原SIFT算法對模糊、光照強度、視角、壓縮、旋轉(zhuǎn)和縮放等不變性優(yōu)勢外，又能提高正確匹配率，減少匹配耗時，匹配效果良好。但該改進算法在實際應(yīng)用時也有不足之處，對于壓縮圖像如何能有效減少匹配點數(shù)量，需進一步研究。

[1]王民，劉偉光.基于改進SIFT特征的雙目圖像匹配算法[J].計算機工程與應(yīng)用，2013，49（2）：203-206.

[2]孫正.數(shù)字圖像處理與識別[M].北京：機械工程出版社，2014：185-186.

[3]Lowe D G.Distinctive image features from scale invariant key points[J].International Journal of Computer Vision，2004，60（2）：581-588.

[4]白廷柱，侯喜報.基于SIFT算子的圖像匹配算法研究[J].北京理工大學(xué)學(xué)報，2013，33（6）：622-627.

[5]劉立，彭復(fù)員，趙坤，等.采用簡化SIFT算法實現(xiàn)快速圖像匹配[J].紅外與激光工程，2008，37（1）：181-184.

[6]Yan Y，Sukthankar R.PCA-SIFT：A more distinctive representation for local image descriptors[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition，Washington，USA，2004：506-513.

[7]Mikolajczyk K，Schmid C.A performance evaluation of local descriptors[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（10）：1615-1630.

[8]戴金波，趙宏偉，劉君玲，等.一種針對于描述子的SIFT簡化方法[J].儀器儀表學(xué)報，2012，33（10）：2255-2262.

[9]劉佳，傅衛(wèi)平，王雯，等.基于改進SIFT算法的圖像匹配[J].儀器儀表學(xué)報，2013，34（5）：1107-1112.

[10]曾巒，顧大龍.一種基于扇形區(qū)域分割的SIFT特征描述符[J].自動化學(xué)報，2012，38（9）：1513-1519.

[11]程德志，李言俊，余瑞星.基于改進SIFT算法的圖像匹配方法[J].計算機仿真，2010，28（7）：285-289.

[12]趙燁，蔣建國，洪日昌.基于RANSAC的SIFT匹配優(yōu)化[J].光電工程，2014，41（8）：58-65.

[13]Lindeberg T.Scale-space theory：A basic too for analyzing structures at different scales[J].Journal of Applied Statistics，1994，21：224-270.

[14]趙錄剛，吳成柯.基于隨機抽樣一致性的多平面區(qū)域檢測算法[J].計算機應(yīng)用，2008，28（12）：154-157.

[15]Hartley R，Zisserman A.Multiple view geometry in computer vision[M].Cambridge UK：Cambridge University Press，2003：121-126.