基于SIFT算法的圖像特征匹配

周穎

（四川大學計算機學院，成都 610065）

基于SIFT算法的圖像特征匹配

周穎

（四川大學計算機學院，成都 610065）

SIFT特征匹配算法的原理在于生成特征點的SIFT特征向量，通過對特征向量之間的匹配來實現(xiàn)圖像之間的匹配。SIFT特征是一種尺度不變的局部圖像特征，闡述生成SIFT特征向量的具體過程，包含尺度空間構(gòu)建、關(guān)鍵點的檢測和精確定位、關(guān)鍵點方向向量的確定和最終SIFT特征描述子的形成等步驟，以及根據(jù)形成的特征描述子進行圖像的匹配。根據(jù)實驗結(jié)果得出SIFT算法可以有效準確地實現(xiàn)圖像之間的匹配。

圖像匹配；SIFT特征匹配；尺度空間；方向向量；特征描述子

0 引言

隨著計算機行業(yè)的不斷發(fā)展，二十世紀七十年代末MARR提出計算機視覺理論，認為計算機視覺是一種信息處理的過程，經(jīng)過這一過程通過硬件計算機從圖像中了解和發(fā)現(xiàn)外部世界的信息。并提出信息處理的三個層次，第一個層次為信息進行處理所依據(jù)的理論，即研究對什么進行處理和為什么進行信息處理；第二個層次為實現(xiàn)處理的實現(xiàn)算法，即如何實現(xiàn)處理，為實現(xiàn)設(shè)計相應(yīng)的算法；第三個層次為研究實現(xiàn)這一處理過程所依賴的硬件設(shè)備，例如在人類的視覺系統(tǒng)中，這一層次的內(nèi)容為人類復(fù)雜的神經(jīng)網(wǎng)絡(luò)，即人類視覺系統(tǒng)對所獲取的信息進行處理依賴的硬件是人類的大腦神經(jīng)網(wǎng)絡(luò)，這一層次也是界定不同領(lǐng)域視覺系統(tǒng)的關(guān)鍵因素，計算機視覺系統(tǒng)依賴的硬件則是計算機。計算機視覺理論的發(fā)展極大地推動了圖像處理領(lǐng)域?qū)D像特征進行匹配的研究工作進展，使得圖像匹配問題成為計算機視覺和圖像處理領(lǐng)域的熱點，圖像匹配技術(shù)指的是把已知的圖像同未知的陌生圖像進行三維空間上的配準，根據(jù)某種規(guī)則在待匹配圖像上找尋對應(yīng)于已知圖像的子圖像。例如在雙目視覺系統(tǒng)中，根據(jù)左右攝像機拍攝到的同一三維物體不同角度的左右兩幅圖像，已知左圖像，在右圖像中按照某種匹配準則尋找對應(yīng)左圖像的特征的過程就是簡單的圖像匹配，兩幅圖像中的匹配對應(yīng)于三維空間物體的同一點或者圖像塊。

圖像匹配的技術(shù)現(xiàn)在被廣泛應(yīng)用在各個領(lǐng)域，包括了輔助醫(yī)療影像分析協(xié)助診斷、雷達跟蹤系統(tǒng)、工業(yè)分析檢測、智能交通管理系統(tǒng)、流水線智能監(jiān)控、圖像的檢索，等等。圖像匹配技術(shù)按照算法類別屬性的不同可以分為基于圖像像素灰度的匹配、基于圖像特征，基于神經(jīng)網(wǎng)絡(luò)和語義網(wǎng)絡(luò)[3]，基于各類遺傳算法等多種匹配算法。各種算法都有其適用的領(lǐng)域和環(huán)境。SIFT算法[1]是Lowe提出的一種基于局部特征不變的特征匹配算法，具有尺度不變的特點。SIFT算子對應(yīng)的是圖像的局部的特征描述，對圖像發(fā)生的各類變化，該特征都具有良好的穩(wěn)定性，圖像發(fā)生視角的變化、旋轉(zhuǎn)、圖像放大或者縮小，或者是由于客觀因素例如光照的變化，噪聲的干擾造成的圖像的變化，SIFT特征對這些變化都保持不變。所以在復(fù)雜情況下進行圖像之間的匹配，SIFT特征具有良好的魯棒性，對匹配表現(xiàn)出良好的效果。同時SIFT特征較其他圖像特征還具有獨特的特性[2]，并且具有很好的擴展特性。近年來，基于SIFT算法的圖像特征匹配在很多重要領(lǐng)域都取得了不錯的成績，得到了廣泛的應(yīng)用，包括了圖像的拼接技術(shù)、遙感圖像的匹配、物體的識別系統(tǒng)、機器人智能導(dǎo)航和定位、三維重建系統(tǒng)、運動目標提取和跟蹤，以及指紋識別、人臉識別等[3]。SIFT算子對圖像發(fā)生平移、旋轉(zhuǎn)、縮放，圖像發(fā)生視角變化、投影仿射變化、光照和噪聲條件改變，以及有目標遮擋等場景有較好的匹配效果。

1 SIFT特征描述子

SIFT特征具有尺度不變化特性，對圖像而言是圖像的局部特征，是計算機視覺中用來檢測和描述二維圖像中的局部性的特征[2]。SIFT特征匹配算法的原理就是通過構(gòu)建圖像尺度空間，在尺度空間中尋找極值點并且篩選出穩(wěn)定良好的極值點作為關(guān)鍵點，再對關(guān)鍵點加上方向參數(shù)的描述，進而構(gòu)建出SIFT特征描述子。匹配的過程即是通過對SIFT特征向量之間的歐氏距離進行求解的過程。歐氏距離越小表明兩個向量之間的相似度越高，即匹配程度越接近。因此使用SIFT算法來實現(xiàn)圖像之間的配準所需要的主要步驟包括了：尺度空間[4]的構(gòu)造、構(gòu)建圖像高斯金字塔以及圖像的高斯差分金字塔、尺度空間極值點的檢測、獲取穩(wěn)定可靠的極值點作為關(guān)鍵點，即對關(guān)鍵點的精確定位、為關(guān)鍵點分配方向向量并生成關(guān)鍵點的描述向量作為SIFT特征向量、利用SIFT特征向量進行特征匹配。

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

尺度空間的構(gòu)建在整個匹配算法中相當于是初始化的過程，尺度空間理論表明尺度空間模擬的是圖像的多尺度特征，并提出高斯核實唯一實現(xiàn)尺度變換的線性核，所以對一幅圖像的尺度空間進行定義，如下公式所表示：

其中G是高斯卷積函數(shù)，σ是度量尺度的因子。L則代表了圖像的尺度空間，I為二維圖像。尺度因子σ表征的是圖像的平滑程度，σ越大表明圖像的概貌特征越明顯，即圖像越模糊，對應(yīng)低的分辨率；σ越小表明圖像的細節(jié)特征越明顯，也就是圖像對應(yīng)高的分辨率，圖像的細節(jié)就越展現(xiàn)出來，對應(yīng)精確的尺度。

1.2 構(gòu)建高斯差分尺度空間

由于僅依靠尺度空間對極值點進行檢測，容易提取出不穩(wěn)定的、性能差的邊緣點，為了得到穩(wěn)定的性能優(yōu)良的極值點作為關(guān)鍵點，可以使用高斯差分尺度空間，利用不同尺度因子下的高斯差分卷積核與圖像進行計算[5]，即實現(xiàn)對不同尺度下的圖像卷積運算，高斯差分尺度空間的構(gòu)造公式如下所示：

不同尺度下的圖像尺度空間的理論描述可以用下圖1來表明：

圖1

上圖中顯示尺度空間中相鄰尺度之間的尺度因子關(guān)系表明了尺度空間是連續(xù)的這一結(jié)論。并且Lowe提出的尺度空間理論中初始的尺度定義為1.6[6]，這個尺度對應(yīng)的圖像是最不清晰的，而圖像的初始尺度對應(yīng)于最清楚的圖像信息，進行極值點檢測之前需要對圖像進行高斯濾波，這樣會引起高頻信號的丟失，基于這一點Lowe得出需要在尺度空間的構(gòu)建之前對圖像進行擴大一倍的處理，以此來保護圖像的原始信息，使得檢測過程中獲取的特征點的數(shù)目比較多。

1.3 構(gòu)建圖像金字塔

為了使圖像在各個不同的尺度下都有其對應(yīng)的特征點，需要構(gòu)建每一層的子八度圖像，即對一幅二維圖像I建立它在不同尺度下的圖像。子八度的第一個圖像都是原始圖像的大小，而之后的各個子八度則依次對自己的前一個八度進行降采樣，降采樣[7]指的是對長和寬分別都減一半的操作，因此每后一個子八度的圖像大小都是前面的1/4大小，如圖2所示。

圖2

子八度總的個數(shù)取決于圖像的大小，而每個子八度中的層數(shù)一般為3～5層，每一個八度中從下往上，上面一層的圖像是經(jīng)由下面一層相鄰圖像高斯卷積而來，對應(yīng)不同的卷積因子σ。從直接對圖像進行觀察可以看出，圖像是越來越模糊的。

1.4 檢測空間極值點

在構(gòu)建好的尺度空間中尋找極值點，該點不僅要在所在的二維圖像中是極值點，并且在相鄰的尺度空間比較中也必須是極值點，即該點不僅需要同二維圖像中的周圍相鄰的八個像素點進行比較，還需要同處于同一八度的上下兩個尺度的二維圖像周圍一共18個相鄰像素點進行比較，如圖3所示。只有同這些點都進行了比較確定是極值點，才可以作為初步的待選關(guān)鍵點。

圖3

在進行極值點的檢測，由于需要同上下相鄰兩層以及自身所在層進行比較，可以看出每一組八度中位于底部和頂部的兩層是沒有辦法按照條件進行比較的，然而尺度空間的變化是連續(xù)的，因此為了保證該空間的連續(xù)性，對每一個八度的圖像在頂部繼續(xù)進行高斯模糊多生成三幅圖像[8]，因此在高斯金字塔中每一個八度就多增加了三層，而對應(yīng)的高斯差分金字塔每一個子八度則多增加了兩層。假如初始每個子八度的層數(shù)為3，那么如圖4所示。

圖4

之所以選擇使用高斯差分金字塔代替高斯金字塔進行極值點的檢測，是因為高斯金字塔雖然可以找到比較多的特征點，但是計算量比較大，計算繁瑣，而使用高斯差分金字塔則可以很好地避免過多的計算，它是尺度歸一化的LOG算子[7]。

1.5 去除不穩(wěn)定的特征點

為了去除高斯差分金字塔中檢測出的對比度比較低、不穩(wěn)定的邊緣特征點，以及曲率不對稱的像素點，采用尺度空間函數(shù)泰勒展開，擬合三維二次函數(shù)來精確定位關(guān)鍵點到亞像素即確定關(guān)鍵點的對應(yīng)尺度位置[8]。由此精確定位來實現(xiàn)匹配算法的準確性和穩(wěn)定性。其中尺度空間的泰勒展開形式如下所示：

為了得到精確的位置信息，對泰勒展開形式進行求導(dǎo)運算并且取值為零可以得出：

結(jié)合兩式得出決策是否為低對比度以及不穩(wěn)定邊緣點的判定條件式：

比較特征點對應(yīng)的上式取值絕對值的大小與0.03之間的關(guān)系，若大于0.03，則該特征點作為保留特征點，否則丟棄該特征點。同樣對于橫跨在邊緣的像素而言，高斯算子具有比較大的曲率，垂直于邊緣有較小的主曲率[8]，求解主曲率的方式由下面的公式給出：

H矩陣稱為hessian矩陣，為2×2的一個矩陣。根據(jù)曲率與hessian矩陣特征值之間的正比例關(guān)系，假設(shè)α，β分別對應(yīng)于比較大的特征值和較小的特征值，有：

再將α=γβ代入上式：

Lowe提出的理論認為當（α+β）/αβ的值大于（r+1）2/r時視為主曲率不在閾值范圍內(nèi)，則丟棄該點。

1.6 為關(guān)鍵點加上方向

上面的步驟中最后剔除了不穩(wěn)定的、低對比度和邊緣的關(guān)鍵點，剩下精確關(guān)鍵點作為最后的特征點，為了保證這些特征算子對旋轉(zhuǎn)平移等變化的穩(wěn)定性，需要為特征點加上一個方向向量。具體的做法在于首先計算出每個特征點的方向，再通過統(tǒng)計該像素周圍領(lǐng)域內(nèi)一些像素的梯度方向信息，即繪制梯度直方圖，梯度直方圖的繪制方法在于，根據(jù)角度的取值范圍是0度到360度，選擇十度為一個單位，因此直方圖一共有36個統(tǒng)計柱。Lowe認為為了排除一些突然的變化帶來的干擾，可以首先對直方圖進行高斯平滑[9]。

根據(jù)領(lǐng)域梯度方向直方圖的統(tǒng)計結(jié)果確定一個方向參數(shù)賦予該特征點，由此來實現(xiàn)該特征點對于旋轉(zhuǎn)的不變性，由領(lǐng)域梯度方向決定該方向的圖示如下。

統(tǒng)計后取直方圖取值最大即峰值時對應(yīng)的方向值為該特征點的主要方向。

圖5

圖6

對于某一像素點，該點的梯度模值和對應(yīng)的方向的計算公式如下所示：

L代表的即為上面所述特征點所處在的尺度空間。所以最終得到的關(guān)鍵點的信息就由幾部分構(gòu)成：特征點的位置信息，特征點的方向信息以及特征點對應(yīng)的尺度信息。為了保證具有旋轉(zhuǎn)不變的特性，將坐標軸移到以特征點的方向為準的方向，這樣可以保證對旋轉(zhuǎn)的穩(wěn)定，并且以特征點為中心位置取周圍8×8區(qū)域的窗口空間，如圖7～8所示，每一個小方格內(nèi)的箭頭指向為該店所在像素即特征點的領(lǐng)域像素對應(yīng)的梯度方向，而箭頭長度的大小則對應(yīng)該像素梯度的模值大小，取帶權(quán)的圓形模板覆蓋的區(qū)域為需要進行高斯運算的范圍，再劃分的4×4的子區(qū)域內(nèi)統(tǒng)計領(lǐng)域像素梯度方向的直方圖，形成種子點，由此可知對于一個特征點而言對應(yīng)于四個種子點，而每一個種子點又含有八個方向信息[10]。這樣處理的目的在于使得匹配算法具有更好的匹配容錯能力，對于誤匹配的糾錯具有良好的效果，并且能夠很好地抵抗噪聲的干擾

1.7 使用特征描述子進行匹配

待匹配的兩幅圖像獲得各自的特征點以及對應(yīng)特征點的SIFT特征描述子后，要對兩幅圖像進行匹配，即是對兩幅圖的特征描述子進行匹配。由于特征描述子為多維的特征向量，向量之間的匹配方式，在于計算兩個向量之間的相似性。度量二者之間的相似程度往往通過構(gòu)造相似性測度函數(shù)，計算度量函數(shù)的最值，函數(shù)的取值反映的則是參與比較的二者之間的相似性程度。這里由于是對向量的相似性進行比較，因此可以采用幾何手段實現(xiàn)，歐氏距離則是反映向量之間距離的度量準則，歐氏距離值越小表明二者越接近，若二者的歐氏距離為0則表示兩個向量相同，否則歐氏距離越大，二者的相似程度越低。具體的匹配方法是對其中某一圖像的關(guān)鍵點的特征向量，在另外一幅圖中尋找與該特征向量歐氏距離最小的兩個特征向量對應(yīng)的關(guān)鍵點。在這兩個關(guān)鍵點中距離更小的值與距離次小的值、的比值在某個閾值范圍內(nèi)，則認為該關(guān)鍵點的對應(yīng)匹配點即為距離最小的特征向量對應(yīng)的關(guān)鍵點，二者構(gòu)成一對匹配點對，否則視為非匹配點對，丟棄。匹配結(jié)果與閾值大小具有密切的關(guān)系，閾值的確定影響匹配的效果，當閾值取值較大時，滿足匹配的點會增多，因此會有比較多的誤匹配出現(xiàn)，匹配的過程表現(xiàn)得不穩(wěn)定，反之如果降低閾值的取值，則會使得很多誤匹配的點被丟棄，匹配過程穩(wěn)定，此時滿足匹配條件的匹配點的數(shù)量則會減少。

圖7

1.8 實驗結(jié)果

實驗中使用平行的雙目視覺系統(tǒng)對同一時刻的三維空間物體進行拍攝，左、右攝像機由于視角的不同，拍攝到兩幅圖像分別如下圖所示：

圖9

圖10

對兩幅圖像進行SIFT算法特征匹配的結(jié)果為：

圖11

2 結(jié)語

根據(jù)理論描述以及實驗的結(jié)果顯示，SIFT特征是一種尺度不變的圖像局部特征，SIFT特征對于圖像的旋轉(zhuǎn)、平移、縮放以及對于光照條件的改變和噪聲的干擾都具有較好的魯棒性，對于實驗中視角發(fā)生變化的情況，也具有良好的匹配效果，即使是存在目標物體的遮擋，也是實現(xiàn)匹配的有效手段。SIFT在圖像匹配領(lǐng)域的優(yōu)勢使得它在圖像處理以及機器視覺等各個領(lǐng)域都有著重大的研究意義，越來越成為圖像檢索、智能交通管理系統(tǒng)、模式識別，甚至是工業(yè)應(yīng)用中的發(fā)展熱點。圖像匹配目前尚不存在可以適用于各種情況的通用匹配算法，各大算法都需要綜合匹配算法的計算量、運行所耗費的時間、匹配的準確性以及匹配效果等各方面的因素。多維的SIFT特征包含了圖像的很多信息，能夠滿足匹配效果的要求，并且SIFT算法的匹配時間較短，在一些對實時性要求比較高的應(yīng)用場合，可以滿足對時間性能的要求。SIFT特征匹配是一種快速而且較精準的匹配算法，具有良好的應(yīng)用價值和重大的研究意義。

[1] L0WE D．Object Recognition from Loca1 Sca1e-Invariant Features[C].Internationa1 Conference on Computer Vision．Greece：ICCV，1999：1150～1157

[2] LOWE D．Distinctive Image Features from Sca1e-Invariant Keypoints[J]．Internationa1 Journa1 of Computer Vision，2004，60（2）：91～110

[3] 張朝偉，周焰，吳思勵．基于SIFT特征匹配的監(jiān)控圖像自動拼接[J]．計算機應(yīng)用，2008，28（1）：191～194

[4] 孫劍，徐宗本．計算機視覺中的尺度空間方法[J]．工程數(shù)學學報，2005，22（6）：951～962

[5] LINDEBERG T P．Interna1 Report TRI TA-NA-P8808[R]．Stockho1m，Sweden：Roya1 Institute of Techno1ogy，2000

[6] 李曉明，鄭鏈，胡占義．基于SIFT特征的遙感影像自動配準[J]．遙感學報，2006，10（6）：885～891

[7] WITKIN A P．Sca1e-Space Fi1tering[C].Proc．7th Internationa1 Joint Conference on Artificia1 Inte11igence．[S．I．]：IJCAI，1993：1019～1022

[8] BABAUD J，W1TKIN AP，BAUDIN M，et a1．Uniqueness of the Gaussian Kerne1 for Sca1e-Space Fi1tering E J]．IEEE Transactions on Pattern Ana1ysis and Machine Inte11igence，1986，8（1）：26～33

[9] LINDEBERG Tony．Discrete Derivative Approximations with Sca1e-Space Properties：a Basis for Low-Leve1 Feature Extraction[J]．Journa1 of Mathematica1 Imaging and Vision，1993，3（4）：349～376

[10] LINDEBERG T．Sca1e-Space Theory：a Basic Too1 for Ana1yzing Structures at Different Sca1es EJ]．Journa1 of App1ied Statistics，1994，21（2）：225～270

Image Feature Matching Based on SIFT Algorithm

ZHOU Ying
（Co11ege of Computer Science，Sichuan University，Chengdu 610065）

The princip1e of SIFT feature matching a1gorithm is to generate SIFT feature vector of the characteristic points,through the matching of feature vector to rea1ize the matching of the images.SIFT feature is a kind of 1oca1 image characteristics which is invariant to image sca1e. Expounds the specific process of how SIFT feature vector is generated,inc1uding the bui1ding of the sca1e space,the detection of the key points and accurate1y positioning these points,determines the direction of the feature vector,and fina11y form the SIFT features vector and according to the vector to rea1ize the image matching.According to the experimenta1 resu1ts it is conc1uded that SIFT a1gorithm can effective1y and accurate1y rea1ize the matching of images.

Image Matching;SIFT Feature Matching;Sca1e Space;Direction Vector;Feature Descriptor

1007-1423（2015）05-0063-06

10.3969/j.issn.1007-1423.2015.05.014

周穎，女，四川成都人，研究方向為圖形圖像處理

2014-12-11

2015-01-20

國家自然科學基金（No.60903118、No.60832011）