(完整版)SIFT算法原理

1、3.1.1尺度空間極值檢測尺度空間理論最早出現(xiàn)于計算機視覺領域，當時其目的是模擬圖像數(shù)據(jù)的多尺度特征。隨后Koendetink利用擴散方程來描述尺度空間濾波過程，并由此證明高斯核是實現(xiàn)尺度變換的唯一變換核。Lindeberg,Babaud等人通過不同的推導進一步證明高斯核是唯一的線性核。因此，尺度空間理論的主要思想是利用高斯核對原始圖像進行尺度變換，獲得圖像多尺度下的尺度空間表示序列,對這些序列進行尺度空間特征提取。二維高斯函數(shù)定義如下：1G(x,y,c)二e-(x2+y2)/26(5)2kc2一幅二維圖像,在不同尺度下的尺度空間表示可由圖像與高斯核卷積得到：L(x,y,c)=G(x,yq)*

2、I(x,y)(6)其中(x,y)為圖像點的像素坐標，I(x,y)為圖像數(shù)據(jù),L代表了圖像的尺度空間。°稱為尺度空間因子,它也是高斯正態(tài)分布的方差,其反映了圖像被平滑的程度,其值越小表征圖像被平滑程度越小，相應尺度越小。大尺度對應于圖像的概貌特征，小尺度對應于圖像的細節(jié)特征。因此，選擇合適的尺度因子平滑是建立尺度空間的關鍵。在這一步里面，主要是建立高斯金字塔和DOG(DifferenceofGaussian)金字塔，然后在DOG金字塔里面進行極值檢測，以初步確定特征點的位置和所在尺度。(1)建立高斯金字塔為了得到在不同尺度空間下的穩(wěn)定特征點，將圖像I(x,y)與不同尺度因子下的高斯核G

3、(x,y,c)進行卷積操作，構成高斯金字塔。高斯金字塔有o階，一般選擇4階，每一階有s層尺度圖像，s一般選擇5層。在高斯金字塔的構成中要注意，第1階的第l層是放大2倍的原始圖像，其目的是為了得到更多的特征點;在同一階中相鄰兩層的尺度因子比例系數(shù)是k，則第1階第2層的尺度因子是kc，然后其它層以此類推則可；第2階的第l層由第一階的中間層尺度圖像進行子抽樣獲得，其尺度因子是k2c，然后第2階的第2層的尺度因子是第1層的k倍即k3c。第3階的第1層由第2階的中間層尺度圖像進行子抽樣獲得。其它階的構成以此類推。(2)建立DOG金字塔DOG即相鄰兩尺度空間函數(shù)之差，用D(x,y,c)來表示，如公式(3)

4、所示：D(x,y,c)=(G(x,y,kc)-G(x,y,c)*I(x,y)=L(x,y,kc)-L(x,y,c)(7)DOG金字塔通過高斯金字塔中相鄰尺度空間函數(shù)相減即可，如圖1所示。在圖中，DOG金字塔的第l層的尺度因子與高斯金字塔的第l層是一致的，其它階也一樣。Gaussiangm(TirptEMEailGaussimn(DOGf圖1高斯圖像金字塔(S=2)與DOG金字塔(3)DOG空間的極值檢測在上面建立的DOG尺度空間金字塔中，為了檢測到DOG空間的最大值和最小值,DOG尺度空間中中間層(最底層和最頂層除外)的每個像素點需要跟同一層的相鄰8個像素點以及它上一層和下一層的9個相鄰像素點

5、總共26個相鄰像素點進行比較，以確保在尺度空間和二維圖像空間都檢測到局部極值，如圖2所示。圖2DOG空間局部極值檢測在圖3中，標記為叉號的像素若比相鄰26個像素的DOG值都大或都小，則該點將作為一個局部極值點，記下它的位置和對應尺度。3.1.2精確定位特征點位置由于DOG值對噪聲和邊緣較敏感，因此，在上面DOG尺度空間中檢測到局部極值點還要經過進一步的檢驗才能精確定位為特征點。下面對局部極值點進行三維二次函數(shù)擬和以精確確定特征點的位置和尺度，尺度空間函數(shù)D(x,y,b)在局部極值點(x,y,q)處的泰勒00展開式如公式(8)所示。QDt1d2DDx，y，b)=D(x0，y°，b)+!

6、FX+2XTX8)其中X二(x,yQ)T,6DdxdD_dDdXdydDd2Dd2Dd2Ddx2dxydxbd2Dd2Dd2Ddyxdy2dybd2Dd2Dd2Ddbxdbydb2。公式(4)中的一階和二階導數(shù)是通過附近區(qū)域的差分來近似求出的，列出其中的幾個，其它的二階導數(shù)以此類推。通過如公式(9)所示：對公式(8)求導，并令其為0，得出精確的極值位置XmaxXmax'd2D丫1dDdx2丿dx9)在上面精確確定的特征點中，同時要去除低對比度的特征點和不穩(wěn)定的邊緣響應點，以增強匹配穩(wěn)定性、提高抗噪聲能力。去除低對比度的特征點：把公式(9)代到公式(8)中，只要前兩項，得到公式(10)：

7、D(X)max2dX10)通過式(6)計算出D(X)，若|D(X)|>0.03，則該特征點就保留下來，否則就丟棄。maxmax去除不穩(wěn)定的邊緣響應點：海森矩陣如公式(11)所示，其中的偏導數(shù)是上面確定的特征點處的偏導數(shù)，它也是通過附近區(qū)域的差分來近似估計的。11)DDH_xxxyDDxyyy通過2x2的海森矩陣日來計算主曲率，由于D的主曲率與H矩陣的特征值成比例，根a據(jù)文獻5,不具體求特征值，求其比例ratio。設a是最大幅值特征，0是次小的，r_-則radio如公式(12)所示。tr(H)_D+D_a+-xxyyDet(H)_DD-(D)_a-(12)xxyyxytr(H)2(a+0)

8、2(Y-+-)2(y+1)2radio_Det(H)a-y-2y(r+1)2由公式(12)求出radio，常取r_10，若radio<則保留該特征點，否則就丟棄。r3.1.3確定特征點主方向利用特征點鄰域像素的梯度方向分布特性為每個特征點指定方向參數(shù)，使算子具備旋轉不變性。m(x,y)=(L(x+1,y)-L(x-1,y)2+(L(x,y+1)-L(x,y-1)2L(x+1,y)L(x1,y)(13)0(x,y)=arctanL(x,y+1)-L(x,y-1)公式(13)為(x,y)處的梯度值和方向。L為所用的尺度為每個特征點各自所在的尺度，(x,y)要確定是哪一階的哪一層。在實際計算過

9、程中，在以特征點為中心的鄰域窗口內采樣，并用梯度方向直方圖統(tǒng)計鄰域像素的梯度方向。梯度直方圖的范圍是0°360。，其中每10。一個柱，總共36個柱。梯度方向直方圖的峰值則代表了該特征點處鄰域梯度的主方向，即作為該特征點的方向。在梯度方向直方圖中，當存在另一個相當于主峰值80能量的峰值時，則將這個方向認為是該特征點的輔方向。一個特征點可能會被指定具有多個方向(一個主方向，一個以上輔方向)，這可以增強匹配的魯棒性。通過上面的3步，圖像的特征點已檢測完畢，每個特征點有3個信息：位置、對應尺度、方向。3.1.4生成SIFT特征向量首先將坐標軸旋轉為特征點的方向，以確保旋轉不變性。接下來以特征

10、點為中心取8X8的窗口(特征點所在的行和列不取)。在圖3左邊，中央黑點為當前特征點的位置，每個小格代表特征點鄰域所在尺度空間的一個像素，箭頭方向代表該像素的梯度方向，箭頭長度代表梯度模值，圖中圈內代表高斯加權的范圍(越靠近特征點的像素，梯度方向信息貢獻越大)。然后在每4X4的圖像小塊上計算8個方向的梯度方向直方圖，繪制每個梯度方向的累加值，形成一個種子點，如圖3右邊圖所示。此圖中一個特征點由2X2共4個種子點組成，每個種子點有8個方向向量信息，可產生2X2X8共32個數(shù)據(jù)，形成32維的SIFT特征向量，即特征點描述器，所需的圖像數(shù)據(jù)塊為8X8。這種鄰域方向性信息聯(lián)合的思想增強了算法抗噪聲的能力

11、，同時對于含有定位誤差的特征匹配也提供了較好的容錯性。實際計算過程中，為了增強匹配的穩(wěn)健性，文獻5建議對每個特征點使用4X4共16個種子點來描述，每個種子點有8個方向向量信息，這樣對于一個特征點就可以產生4X4X8共128個數(shù)據(jù)，最終形成128維的SIFT特征向量，所需的圖像數(shù)據(jù)塊為16X16。此時SIFF特征向量已經去除了尺度變化、旋轉等幾何變形因素的影響，再繼續(xù)將特征向量的長度歸一化，則可以進一步圖3像梯度（左）及特征點描述器（右）當兩幅圖像的SIFT特征向量，即特征描述器生成后,下一步就是進行特征向量的匹配。3.1.4SIFT特征向量的匹配首先，進行相似性度量。一般采用各種距離函數(shù)作為特征的相似性度量，如歐氏距離、馬氏距離等。通過相似性度量得到圖像間的潛在匹配。本文中采用歐氏距離作為兩幅圖像問的相似性度量。獲取SIFT特征向量后，采用優(yōu)先kd樹進行優(yōu)先搜索來查找每個特征點的2近似最近鄰特征點。