一種提高SIFT特征匹配效率的方法

楊幸芳 黃玉美 韓旭炤 楊新剛

1.西安理工大學，西安，710048 2.西安工程大學，西安，710048

0 引言

尺 度 不 變 特 征 變 換 （scale invariant feature transform，SIFT）是 Lowe［1－2］于1999年提出，并于2004年完善總結的一種特征點檢測與匹配算法，該算法提取的圖像特征（SIFT特征）不但對圖像的旋轉、尺度縮放和亮度變化保持不變性，而且對視角變化、仿射變換以及噪聲也能保持一定程度的穩(wěn)定性，故SIFT算法可用于處理兩幅圖像之間發(fā)生平移、旋轉、仿射變換、視角變換、光照變換等情況下的識別與匹配問題?；赟IFT特征的識別與匹配被用于很多領域，如目標識別［3－4］、圖像拼接［5］、移動機器人定位及地圖創(chuàng)建［6－7］等。

雖然SIFT算法被成功應用于許多領域，但由于SIFT特征點數(shù)量龐大，且SIFT特征描述符維數(shù)過高，這使得SIFT特征匹配計算量大、效率不高。針對這些問題，許多學者進行了研究［8－12］。文獻［8］提出的PCA－SIFT通過采用主成分分析法降低特征描述符的維數(shù)，以此減小算法的計算量及降低算法的復雜度，但由于PCA要求樣本數(shù)據(jù)呈橢圓分布，且建立的模型是線性的，所以對于非線性的高維數(shù)據(jù)，效果不好，準確性較SIFT差。文獻［9］通過修改原SIFT算法的采樣規(guī)則，同時針對簡單和復雜兩種環(huán)境下的圖像采用不同的采樣方式，減少了SIFT特征的數(shù)據(jù)量，使系統(tǒng)基本達到了實時的效果。但該算法在不同尺度間循環(huán)采樣，還需要分不同情況設定采樣數(shù)或待檢測的特征點數(shù)目，使得算法復雜。文獻［10－11］以基于圓形窗口的12維向量代替128維向量，該方法提高了算法的實時性，但同時削弱了原算法鄰域方向性信息聯(lián)合的思想，使得算法抗噪能力變?nèi)?。文獻［12］以街區(qū)距離和棋盤距離的線性組合代替歐氏距離作為特征描述符之間的相似性度量，并根據(jù)部分特征的計算結果逐步減少參與計算的特征點數(shù)，從而降低算法時間復雜度。線性組合系數(shù)和特征權重的選取均依賴于大量的實驗數(shù)據(jù)，且針對不同的圖像系數(shù)其取值范圍是變化的，因此，應用起來并不方便。本文以街區(qū)距離［13］代替歐氏距離作為特征描述符之間的相似性度量，提出了最近鄰、次近鄰假設算法，通過降低相似性度量公式的時間復雜度，以及減少相似性計算過程中特征點比較的次數(shù)來縮減算法的計算量。實驗結果表明，新算法在保持原SIFT算法魯棒性的同時，提高了算法的效率。

1 SIFT特征檢測與匹配算法

SIFT特征檢測與匹配算法主要包括以下步驟［1－2］：尺度空間極值檢測、特征點位置的確定、特征點方向的分配、特征描述符的生成以及特征匹配。

1.1 尺度空間極值檢測

尺度空間極值檢測的目的是確定局部極值點的位置及其所在的尺度。文獻［14］指出高斯卷積核是實現(xiàn)尺度變換的唯一線性核，于是一幅圖像I（x，y）的尺度空間定義為

式中，G（x，y，σ）為尺度可變的高斯函數(shù)；σ為尺度空間因子，其大小決定著圖像的平滑程度。σ越小表征圖像被平滑的越少，相應的尺度也就越小，因此大尺度對應圖像的概貌特征，小尺度對應圖像的細節(jié)特征。為了有效地在尺度空間檢測到穩(wěn)定的特征點，提出了高斯差分尺度空間DOG（difference of Gaussian），它由2個相鄰尺度空間函數(shù)之差計算得到，即

為了尋找某個尺度空間中的極值點，D OG尺度空間中間層（最底層和最頂層除外）的每個像素，除需要跟其同尺度的周圍相鄰的8個像素進行比較外，還需要跟其上下2個相鄰尺度的18個相鄰像素（上下兩個相鄰尺度各9個像素）進行比較，若該像素是該26個鄰域像素中的極值點（最大值或最小值），則認為該點是圖像在該尺度下的一個特征點，如圖1所示。

圖1 尺度空間極值檢測

1.2 特征點位置的確定

對極值檢測得到的所有候選特征點，還需要經(jīng)過兩步檢驗才能得到精確定位的特征點：一是利用尺度空間函數(shù)D（x，y，σ）的二階Taylor展開式進行最小二乘擬合，通過計算擬合曲面的極值來精確定位特征點，同時通過設置閾值剔除對比度低的點；二是通過Hessian矩陣剔除不穩(wěn)定的邊緣響應點［2］。二階Taylor展開式和Hessian矩陣的表達式分別為

1.3 特征點方向的分配

利用特征點鄰域像素梯度方向的分布特性，為每個特征點指定主方向，即鄰域內(nèi)各點梯度方向的直方圖中最大值所對應的方向。

點（x，y）處梯度的模以及方向的計算式為

1.4 特征描述符的生成

構造特征描述符時，首先將特征點周圍局部區(qū)域相對于特征點主方向旋轉θ°（調整至0°），以確保其旋轉不變性；然后以特征點為中心，選取16×16大小的鄰域（圖2僅顯示了8×8大小的鄰域），將此鄰域均勻地分成16個4×4的子區(qū)域，并在每個子區(qū)域計算8個方向（0°、45°、90°、135°、180°、225°、270°、315°、360°）的梯度累加值，繪制梯度方向直方圖，這樣16個子區(qū)域共生成16×8＝128個數(shù)據(jù)，1×128的向量被定義為一個特征點的描述符。

圖2 特征描述符的生成

1.5 特征匹配

為了各種應用的目的，需要對當前圖像和目標圖像進行特征匹配。這就需要首先存儲目標圖像（待匹配圖像）的SIFT特征點，然后從當前圖像中查找與之匹配的關鍵點。具體用歐氏距離度量兩幅圖像特征點間的相似性，即在待匹配圖像中找到與當前圖像中某個特征點m1歐氏距離最近的特征點m2和次近的特征點m3，設dist（mi，mj）表示2個特征點mi和mj之間的距離，若距離之比dist（m1，m2）/dist（m1，m3）小于某個閾值T（稱T為距離比閾值），則認為m1與m2相匹配，否則認為m1在待匹配圖像中沒有匹配點。

2 提高SIFT特征匹配效率的方法

SIFT特征具有良好的光照、旋轉和尺度不變性，其在許多基于圖像匹配的應用領域［15－16］獲得了成功的應用。SIFT特征匹配是通過計算一幅圖像中所有特征點與另外一幅圖像中所有特征點之間的歐氏距離來實現(xiàn)。由于每幅圖像的SIFT特征數(shù)目龐大，且每個SIFT特征是128維向量，故SIFT特征匹配的計算效率非常低。本文通過減小算法的計算量，從2個方面提高了SIFT特征匹配的效率：

（1）改造了特征描述符相似性度量的形式，用街區(qū)距離代替歐氏距離，降低了相似性度量公式的時間復雜度。

（2）提出了最近鄰－次近鄰假設算法，通過減少相似性計算過程中特征點比較的次數(shù)，縮減算法的計算量。

2.1 用街區(qū)距離代替歐氏距離

2個n維點x＝（x1，x2，…，xn）與y＝｛y1，y2，…，yn｝之間的歐氏距離定義為

這2個n維點之間的街區(qū)距離定義為

不難驗證，DJ（x，y）≥DO（x，y），且由定義可知，DJ（x，y）的計算比DO（x，y）的計算簡單。對每個SIFT特征點，計算歐氏距離需要128次減法運算，128次平方運算、127次加法運算和1次開平方運算；計算街區(qū)距離需要128次減法運算，128次絕對值運算和127次加法運算。顯然，就運算量而言，街區(qū)距離比歐氏距離少了開平方運算，對數(shù)目龐大的SIFT特征點，這樣減少的計算量也是相當可觀的。

為了排除因為圖像遮擋和背景混亂而產(chǎn)生的無匹配關系的特征點，SIFT特征匹配沒有利用最近鄰匹配（最近鄰定義為特征描述符之間的最小歐氏距離）作為最佳匹配，而是利用最近鄰與次近鄰的比來判定最佳匹配。若最近鄰與次近鄰的比小于某個閾值（稱為匹配閾值），則認為當前點與其最近鄰點是一對正確匹配，否則是錯誤匹配。由于正確匹配取決于距離的比，故距離的變化（DJ（x，y）≥DO（x，y））對匹配閾值的選取影響不大。

2.2 最近鄰－次近鄰假設算法

假設待匹配圖像中任意2個特征點分別為當前圖像中某個特征點的最近鄰點和次近鄰點。為方便起見，假設按在計算機中存儲的順序排列的前2個特征點分別為最近鄰點和次近鄰點。設待匹配圖像中按在計算機中存儲的順序排列的SIFT特征點用y1，y2，…，yn表示，當前圖像中按在計算機中存儲的順序排列的SIFT特征點用x1，x2，…，xn表示。根據(jù)式（8）計算當前圖像中第一個特征點x1分別與待匹配圖像中前2個特征點y1和y2之間的距離，根據(jù)這2個距離對y1和y2按距離大小排序，并將它們存入集合C中，集合C中的元素按位置編號分別稱為c1、c2。設

假設C中的元素是按距離大小升序排列的，則c1和c2分別是待匹配圖像2個特征點中相對于x1的最近鄰點和次近鄰點，即c1是dmin對應的點，c2是ds，min對應的點。

求x1與待匹配圖像中第3個特征點y3之間的距離DJ（x1，y3），若DJ（x1，y3）≥ds，min，放棄y3，直接進行待匹配圖像中下一個特征點的計算，即計算x1與y4之間的距離；否則，比較DJ（x1，y3）與dmin的大小，若DJ（x1，y3）≥dmin，用y3替換c2（y3成為新的c2），即y3成為待匹配圖像3個特征點中相對于x1的次近鄰點，此時ds，min＝DJ（x1，y3），若DJ（x1，y3）＜dmin，用y3替換c1（y3成為新的c1），即y3成為待匹配圖像3個特征點中相對于x1的最近鄰點，此時dmin＝DJ（x1，y3），然后進行待匹配圖像中下一個特征點的計算，即計算x1與y4之間的距離。重復上述x1與y3之間的匹配過程，直到考察完待匹配圖像中所有特征點為止，最終集合C中的2個元素分別是x1的最近鄰和次近鄰點。

求C中第一個特征點c1（最近鄰點）與第二個特征點c2（次近鄰點）對應的距離之比，即dmin/ds，min，若該值小于給定的匹配閾值，則認為x1與c1是一對正確匹配，否則認為x1在待匹配圖像中沒有匹配點。對當前圖像中的其他特征點x2，x3，…，xn重復上述x1尋找匹配點的過程，直到完成當前圖像中所有特征點尋找匹配點的過程為止，至此，匹配結束。

最近鄰－次近鄰假設算法通過假設待匹配圖像中任意2個特征點為最近鄰點和次近鄰點，避免了特征點之間許多不必要的比較，加快了特征點匹配的速度。

3 實驗結果與分析

為了驗證本文算法的有效性，分別用原SIFT算法和本文算法對2對圖像進行了SIFT特征匹配，結果分別如圖3和圖4所示。

圖3 零件匹配圖一（距離比閾值T＝0.6）

從圖3、圖4可以看到，與原SIFT特征匹配相比，本文算法對SIFT特征匹配的數(shù)量影響不大，原因在于本文算法雖然改變了特征點相似性度量的形式，但由于特征點匹配關系的確定最終取決于特征點與最近鄰以及次近鄰相似性度量值之比，故本文算法并未明顯改變特征點匹配的數(shù)量。實驗數(shù)據(jù)表明，在相同的匹配閾值下，本文算法所匹配的特征點數(shù)量比原SIFT算法所匹配的特征點數(shù)量略大。實驗數(shù)據(jù)同時表明，本文算法縮短了算法的運行時間，提高了算法的運算效率。

圖4 零件匹配圖二（距離比閾值T＝0.36）

在（AMD Athlon）CPU 為2.01GHz、內(nèi)存為512MB的微機平臺上，用MATLAB語言編寫的算法程序的運行結果如表1和表2所示。

表1 圖3實驗數(shù)據(jù)

表2 圖4實驗數(shù)據(jù)

4 結語

在分析SIFT特征匹配算法的基礎上，本文提出了一種提高SIFT特征匹配效率的方法。該方法通過降低特征點相似性度量公式的時間復雜度，以及減少相似性計算過程中特征點比較的次數(shù)來縮減算法的計算量，從而提高了算法的效率。由于該算法并沒有改變SIFT特征描述符的維數(shù)，所以該算法保持了原SIFT算法的魯棒性。與原SIFT算法相比，本文算法能夠為實時性要求較高的應用場合提供保障，具有廣闊的工業(yè)應用前景。

［1］Lowe D G.Object Recognition from Local Scaleinvariant Features［C］//Proceedings of the Seventh IEEE International Conference on Computer Vision.Kerkyra，Greece，1999：1150－1157.

［2］Lowe D G.Distinctive Image Features from Scaleinvariant Keypoints［J］.International Journal of Computer Vision，2004，60（2）：91－110.

［3］夏慶觀，盛黨紅，路紅，等.零件圖像特征提取和識別的研究［J］.中國機械工程，2005，16（22）：2031－2033.

［4］熊英，馬惠敏.三維物體SIFT特征的提取與應用［J］.中國圖像圖形學報，2010，15（5）：814－819.

［5］張朝偉，周焰，吳思勵，等.基于SIFT特征匹配的監(jiān)控圖像自動拼接［J］.計算機應用，2008，28（1）：191－194.

［6］Stephen S，Lowe D G，Little J J.Vision－based Global Localization and Mapping for Mobile Robots［J］.IEEE Transactions on Robotics，2005，21（3）：364－375.

［7］王彭林，石守東，洪小偉.基于SIFT算法的移動機器人同時定位與地圖創(chuàng)建［J］.寧波大學學報（理工版），2008，21（1）：68－71.

［8］Ke Y，Sukthankar R.PCA－SIFT：a More Distinctive Representation for Local Image Descriptors［C］//Proceedings of the Conference on Computer Vision and Pattern Recognition. Washington，USA，2004：511－517.

［9］夏桂華，王博，朱齊丹.改進SIFT用于全景視覺移動機器人定位［J］.計算機工程與應用，2010，46（18）：196－198.

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

［11］裴聰，戴立玲，盧章平.基于SIFT的簡化算法下圖像快速匹配［J］.制造業(yè)自動化，2010，32（1）：132－135.

［12］王曉華，傅衛(wèi)平，梁元月.提高SIFT特征匹配效率的方法研究［J］.機械科學與技術，2009，28（9）：1252－1260.

［13］賈云得.機器視覺［M］.北京：科學出版社，2000.

［14］Lindeberg T.Scale－space Theory：a Basic Tool for Analyzing Structures at Different Scales［J］.Journal of Applied Statistics，1994，21（2）：225－270.

［15］劉小軍，楊杰，孫堅偉，等.基于SIFT的圖像配準方法［J］.紅外與激光工程，2008，37（1）：156－160.

［16］王彥，傅衛(wèi)平，朱虹，等.結合小波變換與SIFT特征的工件圖像匹配［J］.機械科學與技術，2009，28（5）：638－642.