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

1.西安理工大學(xué)，西安，710048 2.西安工程大學(xué)，西安，710048

0 引言

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

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

1 SIFT特征檢測與匹配算法

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

1.1 尺度空間極值檢測

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

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

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

圖1 尺度空間極值檢測

1.2 特征點(diǎn)位置的確定

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

1.3 特征點(diǎn)方向的分配

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

點(diǎn)（x，y）處梯度的模以及方向的計(jì)算式為

1.4 特征描述符的生成

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

圖2 特征描述符的生成

1.5 特征匹配

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

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

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

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

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

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

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

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

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

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

2.2 最近鄰－次近鄰假設(shè)算法

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

假設(shè)C中的元素是按距離大小升序排列的，則c1和c2分別是待匹配圖像2個(gè)特征點(diǎn)中相對(duì)于x1的最近鄰點(diǎn)和次近鄰點(diǎn)，即c1是dmin對(duì)應(yīng)的點(diǎn)，c2是ds，min對(duì)應(yīng)的點(diǎn)。

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

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

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

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

為了驗(yàn)證本文算法的有效性，分別用原SIFT算法和本文算法對(duì)2對(duì)圖像進(jìn)行了SIFT特征匹配，結(jié)果分別如圖3和圖4所示。

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

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

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

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

表1 圖3實(shí)驗(yàn)數(shù)據(jù)

表2 圖4實(shí)驗(yàn)數(shù)據(jù)

4 結(jié)語

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

［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］夏慶觀，盛黨紅，路紅，等.零件圖像特征提取和識(shí)別的研究［J］.中國機(jī)械工程，2005，16（22）：2031－2033.

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

［5］張朝偉，周焰，吳思勵(lì)，等.基于SIFT特征匹配的監(jiān)控圖像自動(dòng)拼接［J］.計(jì)算機(jī)應(yīng)用，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算法的移動(dòng)機(jī)器人同時(shí)定位與地圖創(chuàng)建［J］.寧波大學(xué)學(xué)報(bào)（理工版），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］夏桂華，王博，朱齊丹.改進(jìn)SIFT用于全景視覺移動(dòng)機(jī)器人定位［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46（18）：196－198.

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

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

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

［13］賈云得.機(jī)器視覺［M］.北京：科學(xué)出版社，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］劉小軍，楊杰，孫堅(jiān)偉，等.基于SIFT的圖像配準(zhǔn)方法［J］.紅外與激光工程，2008，37（1）：156－160.

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