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

摘 要:SIFT特征點是圖像的一種尺度不變局部特征點。首先給出了尺度空間的生成方法;接下來給出了SIFT特征點的提取步驟和精確定位方法，基于特征點鄰域像素的梯度和方向生成了關鍵點的描述向量;最后根據特征向量給出了匹配方法，提取了SIFT特征點，并將其應用于圖像匹配。實驗結果說明，使用SIFT特征點可以有效實現圖像匹配。關鍵詞:SIFT算法; 圖像匹配; 尺度空間; 高斯核

中圖分類號:TN919-34;TP391.4 文獻標識碼:A

文章編號:1004-373X(2010)18-0101-03

Image Matching Algorithm Based on SIFT Feature Point

GAO Feng1， WEI Shao-hua1， WANG Xue-tong2

(1. North Institute of Information Engineering， Xi’an Technological University， Xi’an 710025， China;

2. School of Computer Science and Engineering， Xi’an University of Technology， Xi’an 710048， China)

Abstract: SIFT feature point is a kind of feature which is invariant to scale. Method for generation scale space of image is presented， then steps for picking up sift key point are provided. Vectors for describing key point are generated based on the gradient magnitude and orientation of pixels neighboring to the key point. Matching algorithm is presented based on vectors. The experiment shows that it is efficient for image matching.Keywords: SIFT algorithm; image matching; scale space; Gaussian kernel

0 引 言

圖像匹配技術是圖像處理和計算機視覺領域的一項重要技術。圖像匹配，就是在機器識別事物的過程中，將已知圖像與陌生圖像的全部或部分在空間上對準，根據已知模式的圖像在一幅陌生圖像中尋找對應該模式的子圖像過程。圖像匹配所涉及的應用領域包括工業檢測、遙感地形匹配、光學和雷達圖像跟蹤、工業流水線自動監控、交通管理、醫療診斷、圖像檢索等諸多領域。

目前，圖像匹配技術有基于與像素灰度相關的匹配、基于圖像特征的匹配、基于語義網絡的匹配以及基于神經網絡和遺傳算法的匹配等多類方法。近年來，基于局部不變量描述符的方法在圖像匹配領域取得了顯著進展。SIFT[1](scale invariant feature transform)方法是Lowe在2004年提出的一種局部不變特征點的提取方法。SIFT特征是圖像的局部特征，對旋轉、尺度縮放和亮度變化保持不變，對視角變化、仿射變換和噪聲也保持一定程度的穩定性。SIFT還具有獨特性、多量性和可擴展性等多項特點。基于SIFT特征的算法目前在圖像拼接[2]、遙感圖像[3]的配準等很多領域都得到了應用。

1 SIFT算法

SIFT是通過在圖像的尺度空間內，將定位極值點作為匹配候選關鍵點，并提取極值點的方向參數，最后獲得匹配所需關鍵點描述符的一種算法。使用SIFT算法實現圖像匹配主要有以下幾個步驟:

1.1 檢測尺度空間極值點

尺度空間(Scale space)思想最早由Iijima于1962年提出，20世紀80年代Witkin和Koenderink[4]的奠基性工作使得尺度空間方法獲得較快發展。1994年Lindeberg等人建立的線性尺度空間方法被廣泛采用[5-6]。

尺度空間方法的基本思想是:在視覺信息的處理過程中引入一個尺度參數，通過連續變化的尺度參數獲得不同尺度下的視覺處理信息，然后綜合這些信息以便深入挖掘圖像的本質特征[5]。

給定圖像I(x，y)，其所對應的尺度空間表示L(x，y)可以由一個卷積核和圖像卷積得到[7]。

L(x，y;δ)=g(x，y;δ)*I(x，y)(1)

g(x，y;δ)=12πδ2e-(x2+y2)/(2δ2)(2)

式中:g(x，y;δ)是高斯卷積核，也是尺度變換惟一的線性核[8]，其中，δ是尺度參數，對應高斯核函數的方差，改變δ的值可以獲得一組圖像的尺度空間表示[2]。

對相鄰尺度的圖像做差分，可以獲得一組DoG(difference of gauss)圖像D(x，y;δ)。

D(x，y;δ)=[g(x，y;kδ)-g(x，y;δ)]*I(x，y)

=L(x，y;kδ)-L(x，y;δ)(3)

圖像的空間極值點是該點與其相鄰8個點及相鄰兩個尺度所對應位置的18個點共27個點中的最大值點[9]，如圖1所示。

圖1 DoG尺度空間局部極值檢測

1.2 精確定位極值點

DoG算子會產生較強的邊緣響應，且在1.1節中檢測到的極值點精度為像素級。

通過擬合三維二次函數可以將極值點插值定位到亞像素精度。將D(x，y;δ)Taylor展開可得:

D(x)=D+DTXX+12XT2DX2X(4)

式中:D及其導數是采樣點的估計值;X是距采樣點的偏移量。此時，極大值點的位置X′可以由下式確定:

X′=-D-1X2#8226;DX(5)

一個定義不好的高斯差分算子的極值在橫跨邊緣處有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。主曲率是通過一個2×2的Hessian矩陣H求出的。即:

H=DxxDxy

DxyDyy(6)

導數由采樣點相鄰差估計得到。主曲率由H的特征值計算得出，令α為最大特征值，β為最小特征值，令α=rβ，則主曲率由下式確定:

Tr(H)2Det(H)=(α+β)2αβ=(r+1)2r(7)

選取合適的主曲率閾值，可以去除不穩定的邊緣響應點，從而獲得精確定位的極值點作為關鍵點。

1.3 指定關鍵點方向參數

利用關鍵點鄰域像素的梯度方向分布特性為每個點指定方向參數，可以使算子具有旋轉不變性。

梯度m(x，y)和方向θ(x，y)可以由下面的公式計算:

m(x，y)=[L(x+1，y)-L(x-1，y)]2+[L(x，y+1)-L(x，y-1)]2

θ(x，y)=atan 2[(L(x，y+1)-L(x，y-1)]/[L(x+1，y)-L(x-1，y)]}(8)

實際計算時，在以關鍵點為中心的鄰域窗口內采樣，并用直方圖統計鄰域像素的梯度方向。梯度直方圖的范圍是0~360°，其中每10°為一個柱。直方圖的峰值代表了該關鍵點處鄰域梯度的主方向，即作為該關鍵點的方向。

當存在另一個相當于主峰值80%能量的峰值時，將這個方向認為是該關鍵點的輔方向。一個關鍵點可以被指定具有多個方向，這可以增強匹配的魯棒性。

至此，每個關鍵點已經檢測完畢，每個關鍵點具有3個信息:位置、所處尺度和方向，由此可以確定1個SIFT特征區域。

1.4 生成關鍵點描述符

先將坐標軸旋轉為關鍵點的方向，以確保旋轉不變性;再以關鍵點為中心取8×8的窗口，圖2左邊的中央黑點為當前關鍵點的位置，每個小格代表關鍵點鄰域所在尺度空間的一個像素，箭頭方向代表該像素的梯度方向，長度代表梯度模值，圓形區域為高斯加權范圍;然后在4×4的小區域上計算8個方向的梯度方向直方圖，繪制每個梯度方向的累加值，即可形成1個種子點，如圖的右部分所示。此圖中一個關鍵點由2×2共4個種子點組成，每個種子點共有8個方向向量信息。鄰域方向性信息聯合的思想增強了算法的抗噪聲能力，同時對于含有定位誤差的特征匹配提供了較好的容錯性。

圖2 關鍵點鄰域方向和方向特征向量

這樣，對于一個關鍵點就可以產生2×2×8共32個數據，形成一個32維的特征向量。此時的SIFT特征向量已經去除了尺度變化、旋轉等幾何變形因素的影響。再繼續將特征向量規一化，可以去除光照變化的影響。

1.5 匹配

生成2幅圖像的特征向量后，采用關鍵點特征向量的歐幾里德距離作為兩幅圖像中關鍵點相似性的判定度量。取一幅圖像中的某個關鍵點，并找出其與另一幅圖像中距離最近的前2個關鍵點，在這兩個關鍵點中，如果最近的距離除以次近距離小于某個閾值Th，則接受這一對匹配點。降低這個比例閾值，匹配點數量會減少，但匹配過程更穩定。反之，匹配點數量會增多，但穩定性隨之會變得稍差。

1.6 實驗及結果

在圖3(a)和圖3(b)中各包含了兩幅圖像，每幅圖像大小均為326×245像素。其中，右邊為待匹配物品的圖像，左邊為待匹配物品放入復雜場景后所形成的圖像。圖中連線的兩端是兩幅圖像中對應的匹配點。

圖3 SIFT匹配結果

為了增強匹配的穩健性，在匹配過程中，對每個關鍵點使用4×4共16個種子點描述，這樣對于一個關鍵點會產生一個128維的特征向量。匹配過程中采用閾值Th=0.6，在去除不穩定響應點時采用r=10。

在圖3(a)左邊的圖像中，除了匹配區域的尺度有變化外，被匹配的目標區域還發生了遮擋，但未遮擋部分仍與右側圖像中的模板圖像正確匹配。圖3(b)中的待匹配圖像區域是物體在發生約90°旋轉后所形成的，此時仍能正確匹配。

2 結 語

通過原理分析和實驗結果驗證，用SIFT算法提取的匹配關鍵點是一種局部描述符。使用SIFT算法實現圖像匹配具有對尺度變化、旋轉、光照和視角變化的穩定性。當發生部分遮擋時，仍可實現有效匹配。基于SIFT特征點實現圖像匹配是一種有效方法。SIFT可進一步應用于圖像檢索，視頻跟蹤等多個領域。

參考文獻

[1]LOWE D. Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision，2004;60(2):91-110.

[2]張朝偉，周焰，吳思勵，等.基于SIFT特征匹配的監控圖像自動拼接[J].計算機應用，2008，28(1):191-194.

[3]李曉明，鄭鏈，胡占義.基于SIFT特征的遙感影像自動配準[J].遙感學報，2006，10(6):885-891.

[4]WITKIN A P. Scale-space filtering[C]//Proc. 7th International Joint Conference on Artificial Intelligence.[S.l.]: IJCAI， 1993:1019-1022.

[5]孫劍，徐宗本. 計算機視覺中的尺度空間方法[J].工程數學學報，2005，22(6):951-962.

[6]LOWE D. Object recognition from local scale-invariant features[C]//International Conference on Computer Vision. Greece: ICCV，1999:1150-1157.

[7]LINDEBERG T P. Internal report TRI TA-NA-P8808[R]. Stockholm， Sweden: Royal Institute of Technology， 2000.

[8]BABAUD J， WITKIN AP， BAUDIN M， et al. Uniqueness of the Gaussian kernel for scale-space filtering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1986， 8(1): 26-33.

[9]LINDEBERG Tony. discrete derivative approximations with scale-space properties: a basis for low-level feature extraction[J].Journal of Mathematical Imaging and Vision， 1993， 3(4): 349-376.

[10]LINDEBERG T. Scale-space theory: abasic tool for analyzing structures at different scales[J].Journal of Applied Statistics，1994，21(2):225-270.