1、SIFT算法實現步驟：1關鍵點檢測、2關鍵點描述、3關鍵點匹配、4消除錯配點1關鍵點檢測1.1建立尺度空間L (x,y, d ),定根據文獻Scale-space theory: A basic tool for analysing structures at different scales 我們可知，高斯核是唯一可以產生多尺度空間的核，一個圖像的尺度空間,義為原始圖像l(x,y)與一個可變尺度的2維高斯函數 G(x,y, d )卷積運算。亠 1咼斯函數 G兇，2expL x,y, G x, y,高斯金字塔高斯金子塔的構建過程可分為兩步：(1) 對圖像做高斯平滑；(2) 對圖像做降采樣。為了

2、讓尺度體現其連續性，在簡單下采樣的基礎上加上了高斯濾波。一幅圖像可以產生幾組(octave)圖像，一組圖像包括幾層(interval )圖像。高斯圖像金字塔共 o組、s層，則有：(x 汀(yI x, yyj/LOctave 1Octave 5Octave 4Octave 3Octave 2s S. -o1(s)oC2 Sd尺度空間坐標；ssub-level層坐標；d 0初始尺度；S每組層數(一般為35)。當圖像通過相機拍攝時，相機的鏡頭已經對圖像進行了一次初始的模糊，所以根據高斯模 糊的性質：0initinitprepreinit -第0層尺度pre -被相機鏡頭模糊后的尺度高斯金字塔的組數：

3、o log2 min M , N 3 M、N分別為圖像的行數和列數高斯金字塔的組尺度與組間尺度：組尺度是指同一組(octave)的尺度關系，組相鄰層尺度化簡為：組間尺度是指不同組直接的尺度關系，相鄰組的尺度可化為：ss Ss(s)°g2Sod ” 2 o0S最后可將組和組間尺度歸為：2i 1( ,k ,k2 ,L kn 1 )k 2 Si 金字塔組數 n 每組層數上一組圖像的底層是由前一組圖像的倒數第二層圖像隔 點采樣生成的。這樣可以保持 尺度的連續性。差分高斯金字塔Lindeberg 在文獻Scale-space theory: A basic tool for analysing

4、 structures at different scales指出尺度規化的LoG算子具有真正的尺度不變性。LoG 算子即（Laplacion of Gaussian)，可以由高斯函數梯度算子 GOG構建尺度規化的GoG算子：2亠2g2g2g2 2x y尺度規化的LoG算子：2 2GLOG算子與高斯核函數的關系2 2 Gauss(x, y, k ) Gauss(x, y,) LOG(x,y, )GG x, y,k G x, y, k 12 2G通過推導可以看出，LOG算子與高斯核函數的差有直接關系，由此引入一種新的算子DOG ( Differenee of Gaussians )，即高斯差分算

5、子。DoG ( Differenee of Gaussian )函數：L x,y, G x, y, * I x, yD x, y, G x, y,k G x, y, * I x, yL x, y,k L x, y,DoG在計算上只需相鄰尺度高斯平滑后圖像相減，因此簡化了計算。對應DOG算子，我們要構建 DOG金字塔話 n DOG)我們可以通過高斯差分圖像看出圖像上的像素值變化情況。（如果沒有變化，也就沒有特征。特征必須是變化盡可能多的點。）DOG圖像描繪的是目標的輪廓。在Lowe的論文中，將第0層的初始尺度定為1.6，圖片的初始尺度定為 0.5,則圖像金 字塔第0層的實際尺度為1.6 1.6

6、0.5 0.51.521.2 DoG的局部極值點檢測關鍵點是由DOG空間的局部極值點組成的。為了尋找DoG函數的極值點，每一個像素點要和它所有的相鄰點比較，看其是否比它的圖像域和尺度域的相鄰點大或者小。中間的檢測點和它同尺度的8個相鄰點和上下相鄰尺度對應的9X2個點共26個點比較，以確保在尺度空間和二維圖像空間都檢測到極值點。在極值比較的過程中，每一組圖像的首末兩層是無法進行極值比較的，為了滿足尺度 變化的連續性，我們在每一組圖像的頂層繼續用高斯模糊生成了3幅圖像，高斯金字塔有每組S+3層圖像。DOG金字塔每組有 S+2層圖像。1.3關鍵點精確定位由于DoG值對噪聲和邊緣較敏感，因此，在上面D

7、oG尺度空間中檢測到局部極值點還要 經過進一步的檢驗才能精確定位為特征點。去除低對比度的極值點DoG函數進行曲線擬合。利用DoG函數為了提高關鍵點的穩定性，需要對尺度空間在尺度空間的 Taylor展開式:D X D-DX 其極值點：X x, y, T在計算過程中，分別對圖像的行、列及尺度三個量進行了修正，其修正結果如下:£TX求解得x 2XT 2DX為修正值。 將修正后的結果代入式DTX!xt2dtX2上式去除那些對比度較低的不穩定極值點。Lowe的試驗顯示，所有取值小于0.04的極值點均可拋棄（像素灰度值圍0, 1）。去除邊緣響應DoG函數僅僅去除低對比度的極值點對于極值點的對于特

8、征點穩定性是遠遠不夠的。在圖像邊緣有較強的邊緣響應，因此我們還需要排除邊緣響應DoG函數的（欠佳的）峰值點在橫跨邊緣的方向有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。主曲率可以通過計算在該點位置尺度的2X 2的Hessian矩陣得到，導數由采樣點相鄰差來估計:DxxDxyDxyDyy表示DOG金字塔中某一尺度的圖像 x方向求導兩次。D的主曲率和H的特征值成正比，為了避免直接的計算這些特征值，而只是考慮它們 的之間的比率。令為最大特征值，為最小的特征值，則Tr HDxx Dyy2Tr HDet H2Tr HDxxDyy2DxyrDxy21Det H在兩特征值相等時達最小，隨rr的增長而增長

9、。Lowe論文中建議r取10。2時將關鍵點保留，反之剔除。Det H2關鍵點描述2.1關鍵點方向分配通過尺度不變性求極值點，可以使其具有縮放不變的性質，利用關鍵點鄰域像素的梯 度方向分布特性，我們可以為每個關鍵點指定方向參數方向，從而使描述子對圖像旋轉具 有不變性。通過求每個極值點的梯度來為極值點賦予方向。像素點的梯度表示gradl x, y,x y/ 2 2梯度幅值：m x, yL x 1,y Lx 1, yL x, y 1 L x, y 11 L x, y 1 L x, y 1梯度方向：x, y tanLx 1, y L x 1,y方向直方圖的生成確定關鍵點的方向采用梯度直方圖統計法，統計

10、以關鍵點為原點，一定區域的圖像像 素點對關鍵點方向生成所作的貢獻。直方圖以每10度方向為一個柱，共 36個柱，柱所代表的方向為像素點梯度方向，柱 的長短代表了梯度幅值。根據Lowe的建議，直方圖統計半徑采用3*1.5* d在直方圖統計時，每相鄰三個像素點采用高斯加權，根據Lowe的建議，模板采用0.25,0.5,0.25，并連續加權兩次。關鍵點的主方向與輔方向關鍵點主方向：極值點周圍區域梯度直方圖的主峰值，也是特征點方向關鍵點輔方向：在梯度方向直方圖中，當存在另一個相當于主峰值80%能量的峰值時,則將這個方向認為是該關鍵點的輔方向。這可以增強匹配的魯棒性，Lowe的論文指出大概有 15%關鍵點

11、具有多方向，但這些點對匹配的穩定性至為關鍵。方向分配實現步驟1. 確定計算關鍵點直方圖的高斯函數權重函數參數；2. 生成含有36柱的方向直方圖，梯度直方圖圍0360度，其中每10度一個柱。由半徑為圖像區域生成；3. 對方向直方圖進行兩次平滑；4. 求取關鍵點方向（可能是多個方向）；5. 對方向直方圖的Taylor展開式進行二次曲線擬合，精確關鍵點方向;圖像的關鍵點已檢測完畢，每個關鍵點有三個信息：位置、尺度、方向；同時也就使 關鍵點具備平移、縮放、和旋轉不變性。2.2生成特征描述符描述的目的是在關鍵點計算后，用一組向量將這個關鍵點描述出來，這個描述子不但 包括關鍵點，也包括關鍵點周圍對其有貢獻

12、的像素點。用來作為目標匹配的依據，也可使 關鍵點具有更多的不變特性，如光照變化、3D視點變化等。通過對關鍵點周圍圖像區域分塊，計算塊梯度直方圖，生成具有獨特性的向量，這個 向量是該區域圖像信息的一種抽象，具有唯一性。下圖是一個SIFT描述子事例。其中描述子由2X 2X 8維向量表征，也即是 2X 2個8方向的方向直方圖組成。左圖的種子點由8X8單元組成。每一個小格都代表了特征點鄰域所在的尺度空間的一個像素，箭頭方向代表了像素梯度方向，箭頭長度代表該像素的幅值。 然后在4X4的窗口計算8個方向的梯度方向直方圖。繪制每個梯度方向的累加可形成一個 種子點，如右圖所示：一個特征點由4個種子點的信息所組

13、成。關鍵點描述子斗*斗*斗*Lowe實驗結果表明：描述子采用4X 4X 8= 128維向量表征，綜合效果最優（不變性與獨特性）。128維關鍵點描述子（就是特征描述符）生成步驟1.確定計算描述子所需的圖像區域描述子梯度方向直方圖由關鍵點所在尺度的模糊圖像計算產生。圖像區域的半徑通過 下式計算：_3 oct V2 d 11radius2oct是關鍵點所在組（octave）的組尺度,2.那么旋轉角度后新坐標為:x>3在圖像半徑區域對每個像素點求其梯度幅值和方向, 度幅值乘以高斯權重參數，生成方向直方圖。cossinsincosy然后對每個梯ykexp2 wdr1-dcdc1-drweight

14、grad I x, yxk該點與關鍵點的列距離 yk該點與關鍵點的行距離x直方圖列數（取4）的一半w等于描述子窗口寬度34在窗口寬度為 2X2的區域計算8個方向的梯度方向直方圖，繪制每個梯度方向的累 加值，即可形成一個種子點。然后再在下一個2X2的區域進行直方圖統計，形成下一個種子點，共生成16個種子點。5描述子向量元素門限化及門限化后的描述子向量規化。描述子向量元素門限化：方向直方圖每個方向上梯度幅值限制在一定門限值以下（門限一 般取0.2）。描述子向量元素規化：WLljW,W2丄，呵28丄128為得到的128描述子向量 為規化后的向量j 1,2 丄 128關鍵點描述子向量的規化正是可去除滿

15、足此模型的光照影響。對于圖像灰度值整體漂 移，圖像各點的梯度是鄰域像素相減得到，所以也能去除。3關鍵點匹配分別對模板圖（參考圖， referenee image ）和實時圖（觀測圖， observation image ）建 立關鍵點描述子集合。目標的識別是通過兩點集關鍵點描述子的比對來完成。具有128維的關鍵點描述子的相似性度量采用歐式距離。模板圖中關鍵點描述子:實時圖中關鍵點描述子：任意兩描述子相似性度量:SiSi1 , Si2 丄,si128d R,S2Sj要得到配對的關鍵點描述子，d R,Sj需滿足：Threshold實時圖中距離R最近的點S實時圖中距離R的次最近點Sp關鍵點的匹配可以采用窮舉法來完成，但是這樣耗費的時間太多，一般都采用一種叫 k-d樹的數據結構來完成搜索。搜索的容是以目標圖像的關鍵點為基準，搜索與目標圖像的特征點最鄰近的原圖像特征點和次鄰近的原圖像特征點。Kd樹是一個平衡二叉樹X3,1關鍵點匹配并不能標志著算法的結束，因為在匹配的過程中存在著大