SIFT算法小結(jié)

1、SIFT算法小結(jié)1 SIFT發(fā)展歷程SIFT算法由D.G.Lowe1999年提出，200的完善總2后來Y.Ke將其描述子部分用PC微替直方圖的方式，對其進(jìn)行改進(jìn)。2 SIFT主要思想SIFT算法是一種提取局部特征的算法，在尺度空間尋找極值點(diǎn)，提取位置，尺度，旋轉(zhuǎn)不變量。3 SIFT算法的主要特點(diǎn)：a)SIFT特征是圖像的局部特征，其對旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性，對視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性。b)獨(dú)特性(Distinctiveness)好，信息量豐富，適用于在海量特征數(shù)據(jù)庫中進(jìn)23 3行快速、準(zhǔn)確的匹配。c)多量性，即使少數(shù)的幾個物體也可以產(chǎn)生大量SIFT特征向量。d

2、)高速性，經(jīng)優(yōu)化的SIFT匹配算法甚至可以達(dá)到實時的要求。e)可擴(kuò)展性，可以很方便的與其他形式的特征向量進(jìn)行聯(lián)合。24 SIFT算法步驟：1)檢測尺度空間極值點(diǎn)2)精確定位極值點(diǎn)3)為每個關(guān)鍵點(diǎn)指定方向參數(shù)4)關(guān)鍵點(diǎn)描述子的生成25 SIFT算法詳細(xì)尺度空間的生成尺度空間理論目的是模擬圖像數(shù)據(jù)的多尺度特征。高斯卷積核是實現(xiàn)尺度變換的唯一線性核口，于是一副二維圖像的尺度空間定義為：L(x,y,)G(x,y,)I(x,y)(1)22、其中G(x,y,)是尺度可變高斯函數(shù)，G(x,y,)-2e(xy)/2(2)(x,y)是空間坐標(biāo)，是尺度坐標(biāo)。為了有效的在尺度空間檢測到穩(wěn)定的關(guān)鍵點(diǎn)，提出了高斯差分尺

3、度空間(DOGscale-space。利用不同尺度的高斯差分核與圖像卷積生成。D(x,y,)(G(x,y,k)G(x,y,)I(x,y)L(x,y,k)L(x,y,)(3)DOG算子計算簡單，是尺度歸一化的LoG算子的近似。圖像金字塔的構(gòu)建：圖像金字塔共。組，每組有S層，下一組的圖像由上一組圖像降采樣得到。圖1由兩組高斯尺度空間圖像示例金字塔的構(gòu)建，第二組的第一副圖像由第一組的第一副到最后一副圖像由一個因子2降采樣得到。圖2DoG算子的構(gòu)建：JOctave見圖1TwooctavesofaGaussianscale-spaceimagepyramidwiths=2intervals.Thefir

4、stimageinthesecondoctaveiscreatedbydownsamplingthesecondtolastimageinthepreviousOctave1DoGOctave1圖2ThedifferenceoftwoadjacentintervalsintheGaussianscale-spacepyramidcreateanintervalinthedifference-of-Gaussianpyramid(showningreen).空間極值點(diǎn)檢測為了尋找尺度空間的極值點(diǎn)，每一個采樣點(diǎn)要和它所有的相鄰點(diǎn)比較，看其是否比它的圖像域和尺度域的相鄰點(diǎn)大或者小。如圖3所示，中間的

5、檢測點(diǎn)和它同尺度的8個相鄰點(diǎn)和上下相鄰尺度對應(yīng)的9X2個點(diǎn)共26個點(diǎn)比較，以確保在尺度空間和二維圖像空間都檢測到極值點(diǎn)。圖3DoG尺度空間局部極值檢測構(gòu)建尺度空間需確定的參數(shù)一尺度空間坐標(biāo)Ooctave坐標(biāo)Ssub-level坐標(biāo)和O、S的關(guān)系（O,S）o2oS/S,0品.0,O1,S0,S1其中0是基準(zhǔn)層尺度。ooctave坐標(biāo)，ssub-level坐標(biāo)。注：octaves的索引可能是負(fù)的。第一組索引常常設(shè)為0或者-1,當(dāng)設(shè)為-1的時候，圖像在計算高斯尺度空間前先擴(kuò)大一倍?？臻g坐標(biāo)x是組octave的函數(shù)，設(shè)x0是0組的空間坐標(biāo)，則x2oX0,o,X00,N°10,M°1

6、如果M0,N0是基礎(chǔ)組o=0的分辨率，則其他組的分辨率由下式獲得：注：在Lowe的文章中，Lowe使用了如下的參數(shù):1/S_n0.5,o1.62,omin1,S3在組。=-1,圖像用雙線性插值擴(kuò)大一倍（對于擴(kuò)大的圖像n1）。精確確定極值點(diǎn)位置通過擬和三維二次函數(shù)以精確確定關(guān)鍵點(diǎn)的位置和尺度（達(dá)到亞像素精度），同時去除低對比度的關(guān)鍵點(diǎn)和不穩(wěn)定的邊緣響應(yīng)點(diǎn)（因為DoG算子會產(chǎn)生較強(qiáng)的邊緣響應(yīng)），以增強(qiáng)匹配穩(wěn)定性、提高抗噪聲能力。邊緣響應(yīng)的去除一個定義不好的高斯差分算子的極值在橫跨邊緣的地方有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。主曲率通過一個2x2的Hessian矩陣H求出：(4)Dxx

7、DxyDxyDyy導(dǎo)數(shù)由采樣點(diǎn)相鄰差估計得到。D的主曲率和H的特征值成正比，令為最大特征值，為最小的特征值，則TriH=Dxx+。判=a+8：Det(H)DxxDyy(P±v)2=%工令，則：Tr(H產(chǎn)=(n+,3-=("3+3)2=(丁+產(chǎn)Det(H)a3rtPr(r+1)2/r的值在兩個特征值相等的時候最小，隨著r的增大而增大，因此，為了檢測主曲率是否在某域值r下，只需檢測Tt(H)2(r+1產(chǎn)Det(H)<-r-在Lowe的文章中，取r=10。關(guān)鍵點(diǎn)方向分配利用關(guān)鍵點(diǎn)鄰域像素的梯度方向分布特性為每個關(guān)鍵點(diǎn)指定方向參數(shù)，使算子具備旋轉(zhuǎn)不變性。那GM=+l,y)-&

8、#163;(工一>?)、+1)-依y-D尸佻腦力=Qtan2(aa,y+1)-川-1)/(“工+1/)-上(工-1/)(尺度空間，見式：1)式(5)為(x,y)處梯度的模值和方向公式。其中L所用的尺度為每個關(guān)鍵點(diǎn)各自所在的尺度。在實際計算時，我們在以關(guān)鍵點(diǎn)為中心的鄰域窗口內(nèi)采樣，并用直方圖統(tǒng)計鄰域像素的梯度方向。梯度直方圖的范圍是0360度，其中每10度一個柱，總共36個柱。直方圖的峰值則代表了該關(guān)鍵點(diǎn)處鄰域梯度的主方向，即作為該關(guān)鍵點(diǎn)的方向。圖4是采用7個柱時使用梯度直方圖為關(guān)鍵點(diǎn)確定主方向的示例。圖4由梯度方向直方圖確定主梯度方向在梯度方向直方圖中，當(dāng)存在另一個相當(dāng)于主峰值80%能量

9、的峰值時，則將這個方向認(rèn)為是該關(guān)鍵點(diǎn)的輔方向。一個關(guān)鍵點(diǎn)可能會被指定具有多個方向（一53個主方向，一個以上輔方向），這可以增強(qiáng)匹配的魯棒性。至此，圖像的關(guān)鍵點(diǎn)已檢測完畢，每個關(guān)鍵點(diǎn)有三個信息：位置、所處尺度、方向。由此可以確定一個SIFT特征區(qū)域（在實驗章節(jié)用橢圓或箭頭表示）。特征點(diǎn)描述子生成首先將坐標(biāo)軸旋轉(zhuǎn)為關(guān)鍵點(diǎn)的方向，以確保旋轉(zhuǎn)不變性。穎域梯度方可關(guān)避直號征同量圖5由關(guān)鍵點(diǎn)鄰域梯度信息生成特征向量接下來以關(guān)鍵點(diǎn)為中心取8X8的窗口。圖5-4左部分的中央黑點(diǎn)為當(dāng)前關(guān)鍵點(diǎn)的位置，每個小格代表關(guān)鍵點(diǎn)鄰域所在尺度空間的一個像素，箭頭方向代表該像素的梯度方向，箭頭長度代表梯度模值，圖中藍(lán)色的圈代表

10、高斯加權(quán)的范圍（越靠近關(guān)鍵點(diǎn)的像素梯度方向信息貢獻(xiàn)越大）。然后在每4X4的小塊上計算8個方向的梯度方向直方圖，繪制每個梯度方向的累加值，即可形成一個種子點(diǎn)，如圖5右部分所示。此圖中一個關(guān)鍵點(diǎn)由2X2共4個種子點(diǎn)組成，每個種子點(diǎn)有8個方向向量信息。這種鄰域方向性信息聯(lián)合的思想增強(qiáng)了算法抗噪聲的能力，同時對于含有定位誤差的特征匹配也提供了較好的容錯性。實際計算過程中，為了增強(qiáng)匹配的穩(wěn)健性，Lowe建議對每個關(guān)鍵點(diǎn)使用4X4共16個種子點(diǎn)來描述，這樣對于一個關(guān)鍵點(diǎn)就可以產(chǎn)生128（=16*8個方向）個數(shù)據(jù)，即最終形成128維的SIFT特征向量。此時SIFT特征向量已經(jīng)去除了尺度變化、旋轉(zhuǎn)等幾何變形因

11、素的影響，再繼續(xù)將特征向量的長度歸一化，則可以進(jìn)一步去除光照變化的影響。當(dāng)兩幅圖像的SIFT特征向量生成后，下一步我們采用關(guān)鍵點(diǎn)特征向量的歐式距離來作為兩幅圖像中關(guān)鍵點(diǎn)的相似性判定度量。取圖像1中的某個關(guān)鍵點(diǎn)，并找出其與圖像2中歐式距離最近的前兩個關(guān)鍵點(diǎn)，在這兩個關(guān)鍵點(diǎn)中，如果最近的距離除以次近的距離少于某個比例閾值，則接受這一對匹配點(diǎn)。降低這個比例閾值，SIFT匹配點(diǎn)數(shù)目會減少，但更加穩(wěn)定。（比值越小，則區(qū)分度越好）SIFT后來有兩種擴(kuò)展，都用到PCA的概念。1PCA-SIFTPCA-SIFT與標(biāo)準(zhǔn)SIFT有相同的亞像素位置(sub-pixel)，尺度(scale)和主方向(dominant

12、orientations),但在第4步計算描述子的時候，它用特征點(diǎn)周圍的41X41的像斑計算它的主元，并用PCA-SIFT將原來的2X39X39維的向量降成20維，以達(dá)到更精確的表示方式。創(chuàng)建PCA-SIFT描述子的步驟：1 )計算或者載入投影矩陣2 )檢測關(guān)鍵點(diǎn)3 )通過與投影矩陣相乘投影關(guān)鍵點(diǎn)周圍的像斑PCA-SIFT投影矩陣的產(chǎn)生選擇一系列有代表性的圖像并且檢測這些圖像的所有關(guān)鍵點(diǎn)對每一個關(guān)鍵點(diǎn)：1在它的周圍選擇一個大小為41X41象素的像斑2>計算垂直和水平的梯度，形成一個大小為39X39X2=3042的矢量3)將這些矢量放入一個kX3042大小的矩陣A,k是所檢測的關(guān)鍵點(diǎn)數(shù)目。

13、4>計算矩陣A的協(xié)方差：A=AmeanAcovA=ATA5計算covA的特征值和特征矢量6選擇前n個特征向量，投影矩陣是一個由這些特征向量組成的nX3042的矩陣7n可以是一個根據(jù)經(jīng)驗設(shè)置的固定值，也可以基于特征值動態(tài)選擇。8投影矩陣只計算一次，并且存儲建立描述子 輸入：在尺度空間關(guān)鍵點(diǎn)的位置和方向 在關(guān)鍵點(diǎn)周圍提取一個41X41的像斑于給定的尺度，旋轉(zhuǎn)到它的主方向 計算39X39水平和垂直的梯度，形成一個大小為3042的矢量 用預(yù)先計算好的投影矩陣nX3042與此矢量相乘 這樣生成一個大小為n的PCA-SIFT描述子SIFT和PCA-SIFT的比較SIFT：維數(shù)：128缺點(diǎn)：維數(shù)高、不完全的仿射不變優(yōu)點(diǎn)：需要較少的經(jīng)驗主義知識，易于開發(fā)PCA-SIFT：維數(shù)：可變，推薦20或者更少缺點(diǎn)：不完全的仿射不變；投影矩陣需要一系列有代表性的圖像