SIFT算法分析

1、SIFT算法分析1SIFT主要思想SIFT算法是一種提取局部特征的算法，在尺度空間尋找極值點，提取位置,尺度，旋轉(zhuǎn)不變量。2SIFT算法的主要特點:a）SIFT特征是圖像的局部特征，其對旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性，對視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性。b）獨特性（Distinctiveness）好，信息量豐富，適用于在海量特征數(shù)據(jù)庫中進行快速、準確的匹配。c）多量性，即使少數(shù)的幾個物體也可以產(chǎn)生大量SIFT特征向量。d）高速性，經(jīng)優(yōu)化的SIFT匹配算法甚至可以達到實時的要求。e）可擴展性，可以很方便的與其他形式的特征向量進行聯(lián)合。3SIFT算法流程圖:輸入圖像4SIFT算法

2、詳細1)尺度空間的生成尺度空間理論目的是模擬圖像數(shù)據(jù)的多尺度特征。高斯卷積核是實現(xiàn)尺度變換的唯一線性核，于是一副二維圖像的尺度空間定義為：L(x,y,)G(x,y,)I(x,y)22c其中G(x,y,)是尺度可變圖斯函數(shù)，G(x,y,)2e(y)/22(x,y)是空間坐標，是尺度坐標。大小決定圖像的平滑程度，大尺度對應圖像的概貌特征，小尺度對應圖像的細節(jié)特征。大的值對應粗糙尺度(低分辨率)，反之，對應精細尺度(高分辨率)。為了有效的在尺度空間檢測到穩(wěn)定的關(guān)鍵點，提出了高斯差分尺度空間(DOGscale-space。利用不同尺度的高斯差分核與圖像卷積生成。D(x,y,)(G(x,y,k)G(x,

3、y,)I(x,y)L(x,y,k)L(x,y,)DOG算子計算簡單，是尺度歸一化的LoG算子的近似。圖像金字塔的構(gòu)建：圖像金字塔共。組，每組有S層，下一組的圖像由上一組圖像降采樣得到。圖1由兩組高斯尺度空間圖像示例金字塔的構(gòu)建，第二組的第一副圖像由第一組的第一副到最后一副圖像由一個因子2降采樣得到。圖2DoG算子的構(gòu)建：Octave JOctave 電圖1TwooctavesofaGaussianscale-spaceimagepyramidwiths=2intervals.Thefirstimageinthesecondoctaveiscreatedbydownsamplingtolasti

4、mageinthepreviousOctave1DoGOctave1圖2ThedifferenceoftwoadjacentintervalsintheGaussianscale-spacepyramidcreateanintervalinthedifference-of-Gaussianpyramid（showningreen）.2）空間極值點檢測為了尋找尺度空間的極值點，每一個采樣點要和它所有的相鄰點比較，看其是否比它的圖像域和尺度域的相鄰點大或者小。如圖3所示，中間的檢測點和它同尺度的8個相鄰點和上下相鄰尺度對應的9X2個點共26個點比較，以確保在尺度空間和二維圖像空間都檢測到極值點。一

5、個點如果在DOG尺度空間本層以及上下兩層的26個領域中是最大或最小值時，就認為該點是圖像在該尺度下的一個特征點，如圖1所示。圖3DoG尺度空間局部極值檢測3）構(gòu)建尺度空間需確定的參數(shù)一尺度空間坐標Ooctave6標Ssub-level坐標和O、S的關(guān)系（o,s）02os/S,oomin0,.,O1,s0,.,S1其中0是基準層尺度。ooctav整標,ssub-level坐標。注：octaves的索引可能是負的。第一組索引常常設為0或者-1,當設為-1的時候，圖像在計算高斯尺度空間前先擴大一倍。oXo,0空間坐標x是組octave的函數(shù)，設x0是0組的空間坐標，則,x00,.,N010,.,M0

6、1如果M°,N。是基礎組o=0的分辨率，則其他組的分辨率由下式獲得:N。No20 ,MoM。注：在Lowe的文章中，Lowe使用了如下的參數(shù):n0.5,01.621/S,omin1,S3n 1) o在組o=-1,圖像用雙線性插值擴大一倍（對于擴大的圖像4）精確確定極值點位置通過擬和三維二次函數(shù)以精確確定關(guān)鍵點的位置和尺度（達到亞像素精度），同時去除低對比度的關(guān)鍵點和不穩(wěn)定的邊緣響應點（因為DoG算子會產(chǎn)生較強的邊緣響應），以增強匹配穩(wěn)定性、提高抗噪聲能力?？臻g尺度函數(shù)D（x,y,）DT、,D(x, y, ) D Xo, y0, XX 02xT 2D）泰勒展開式如下：DTD(x, y,

7、 ) D x,y, xx2D-x x對上式求導，并令其為0,得到精確的位置父權(quán)2D 1 Dx2 x在已經(jīng)檢測到的特征點中，要去掉低對比度的特征點和不穩(wěn)定的邊緣響應點。去除低對比度的點：把公式（4）代入公式（3）,只取前兩項可得：D(幻 Dx, y,1 DT2 x若 D 2 0.03,該特征點就保留下來，否則丟棄。邊緣響應的去除一個定義不好的高斯差分算子的極值在橫跨邊緣的地方有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。主曲率通過一個2x2的Hessian巨陣H求出:DxxDxyDxyDyy導數(shù)由采樣點相鄰差估計得到。D的主曲率和H的特征值成正比，令為最大特征值，為最小的特征值,Tr(H)D

8、xx+=a+民Det(H)DXIDvy(Dry)2-ad-2=8+31=(r:+尸產(chǎn)=(+1產(chǎn)Det(H)adrtPr(r+1)7r的值在兩個特征值相等的時候最小，隨著r的增大而增大，因此,為了檢測主曲率是否在某域值r下，只需檢測R(H)2(+IDet(H)<r在Lowe的文章中，取r=10。5)關(guān)鍵點方向分配利用關(guān)鍵點鄰域像素的梯度方向分布特性為每個關(guān)鍵點指定方向參數(shù)，使算子具備旋轉(zhuǎn)不變性。冽(苞)=(£(工+1M一應+任(工1+1)71)產(chǎn)My)=atan2(£(x,y+1)-L(x,y+ty)-L(x式(5)為(x,y)處梯度的模值和方向公式。其中L所用的尺度為

9、每個關(guān)鍵點各自所在的尺度。在實際計算時，我們在以關(guān)鍵點為中心的鄰域窗口內(nèi)采樣，并用直方圖統(tǒng)計鄰域像素的梯度方向。梯度直方圖的范圍是0360度，其中每10度一個柱，總共36個柱。直方圖的峰值則代表了該關(guān)鍵點處鄰域梯度的主方向，即作為該關(guān)鍵點的方向。圖4是采用7個柱時使用梯度直方圖為關(guān)鍵點確定主方向的示例。(窗口尺寸采用Lowe隹薦的1.5(TX1.5(T)圖4由梯度方向直方圖確定主梯度方向在梯度方向直方圖中，當存在另一個相當于主峰值80喊長量的峰值時，則將這個方向認為是該關(guān)鍵點的輔方向。一個關(guān)鍵點可能會被指定具有多個方向（一個主方向，一個以上輔方向），這可以增強匹配的魯棒性53。至此，圖像的關(guān)鍵

10、點已檢測完畢，每個關(guān)鍵點有三個信息：位置、所處尺度、方向。由此可以確定一個SIFT特征區(qū)域（在實驗章節(jié)用橢圓或箭頭表示）。6）特征點描述子生成首先將坐標軸旋轉(zhuǎn)為關(guān)鍵點的方向，以確保旋轉(zhuǎn)不變性。穎域嗦宣方司關(guān)鋸點特征向最圖5由關(guān)鍵點鄰域梯度信息生成特征向量接下來以關(guān)鍵點為中心取8X8的窗口。圖5-4左部分的中央黑點為當前關(guān)鍵點的位置，每個小格代表關(guān)鍵點鄰域所在尺度空間（和關(guān)鍵點是否為一個尺度空間）的一個像素，利用公式（5）求得每個像素i,j的梯度幅值mi,j與梯度方向i,j,箭頭方向代表該像素的梯度方向，箭頭長度代表梯度模值，然后用高斯窗口對其進仃加權(quán)運算，每個像素對應一個向重，長度為G,i,j

11、mi,j,G,i,j為該像素點的高斯權(quán)值，方向為i圖中藍色的圈代表高斯加權(quán)的范圍（越靠近關(guān)鍵點的像素梯度方向信息貢獻越大）。高斯參數(shù)J取3倍特征點所在的尺度。然后在每4X4的小塊上計算8個方向的梯度方向直方圖，繪制每個梯度方向的累加值，即可形成一個種子點，如圖5右部分所示。此圖中一個關(guān)鍵點由2X2共4個種子點組成，每個種子點有8個方向向量信息。這種鄰域方向性信息聯(lián)合的思想增強了算法抗噪聲的能力，同時對于含有定位誤差的特征匹配也提供了較好的容錯性。實際計算過程中，為了增強匹配的穩(wěn)健性，對每個關(guān)鍵點使用4X4共16個種子點來描述，這樣對于一個關(guān)鍵點就可以產(chǎn)生128個數(shù)據(jù)，即最終形成128維的SIF

12、T特征向量。此時SIFT特征向量已經(jīng)去除了尺度變化、旋轉(zhuǎn)等幾何變形因素的影響，再繼續(xù)將特征向量的長度歸一化，則可以進一步去除光照變化的影響。當兩幅圖像的SIFT特征向量生成后，下一步我們采用關(guān)鍵點特征向量的歐式距離來作為兩幅圖像中關(guān)鍵點的相似性判定度量。取圖像1中的某個關(guān)鍵點，并找出其與圖像2中歐式距離最近的前兩個關(guān)鍵點，在這兩個關(guān)鍵點中，如果最近的距離除以次近的距離少于某個比例閾值，則接受這一對匹配點。降低這個比例閾值，SIFT匹配點數(shù)目會減少，但更加穩(wěn)定。為了排除因為圖像遮擋和背景混亂而產(chǎn)生的無匹配關(guān)系的關(guān)鍵點，用比較最近鄰距離與次近鄰距離的方法，距離比率ratio小于某個閾值的認為是正確

13、匹配。因為對于錯誤匹配,由于特征空間的高維性，相似的距離可能有大量其他的錯誤匹配，從而它的ratio值比較高。推薦ratio的閾值為0.8。5仿真結(jié)果分析將文件加入matlab目錄后，在主程序中有兩種操作:op1：尋找圖像中的Sift特征：image,discrips,locs=sift('scene.pgm');Findingkeypoints.1021keypointsfound.>>showkeys(image,locs);DrawingSIFTkeypoints.501001502002503003505010015020025030035040045050

14、0op2:對兩幅圖中的SIFT特征進行匹配:match('scene.pgm','book.pgm');Findingkeypoints.1021keypointsfound.Findingkeypoints.882keypointsfound.Found98matches.50 b1001502002506代碼1) appendimages.m%im=appendimages(image1,image2)%Returnanewimagethatappendsthetwoimagesside-by-side.functionim=appendimages(ima

15、ge1,image2)%Selecttheimagewiththefewestrowsandf川inenoughemptyrows%tomakeitthesameheightastheotherimage.rows1=size(image1,1);rows2=size(image2,1);if(rows1<rows2)image1(rows2,1)=0;elseimage2(rows1,1)=0;end%Nowappendbothimagesside-by-side.im=image1image2;2) match.m%num=match(image1,image2)%Thisfunct

16、ionreadstwoimages,findstheirSIFTfeatures,andmatch is acceptedthe distance to the%displayslinesconnectingthematchedkeypoints.A%onlyifitsdistanceislessthandistRatiotimes%secondclosestmatch.%Itreturnsthenumberofmatchesdisplayed.%Example:match('scene.pgm','book.pgm');functionnum=match(im

17、age1,image2)%FindSIFTkeypointsforeachimageim1,des1,loc1=sift(image1);im2,des2,loc2=sift(image2);%ForefficiencyinMatlab,itischeapertocomputedotproductsbetween%unitvectorsratherthanEuclideandistances.Notethattheratioof%angles(acosofdotproductsofunitvectors)isacloseapproximation%totheratioofEuclideandi

18、stancesforsmallangles.%distRatio:Onlykeepmatchesinwhichtheratioofvectoranglesfromthe%nearesttosecondnearestneighborislessthandistRatio.distRatio=0.6;image, select its match to second image.% Precompute matrix transpose% Computes vector of dot products% Take inverse cosine and sort%Foreachdescriptori

19、nthefirstdes2t=des2'fori=1:size(des1,1)dotprods=des1(i,:)*des2t;vals,indx=sort(acos(dotprods);results%CheckifnearestneighborhasanglelessthandistRatiotimes2nd.if(vals(1)<distRatio*vals(2)match(i)=indx(1);elsematch(i)=0;endend%Createanewimageshowingthetwoimagessidebyside.im3=appendimages(im1,im

20、2);%Showafigurewithlinesjoiningtheacceptedmatches.figure('Position',100100size(im3,2)size(im3,1);colormap('gray');imagesc(im3);holdon;cols1=size(im1,2);fori=1:size(des1,1)if(match(i)>0)line(loc1(i,2)loc2(match(i),2)+cols1,.loc1(i,1)loc2(match(i),1),'Color','c');end

21、endholdoff;num=sum(match>0);fprintf('Found%dmatches.n',num);3) showkeys.m%showkeys(image,locs)%ThisfunctiondisplaysanimagewithSIFTkeypointsoverlayed.%Inputparameters:%image:thefilenamefortheimage(grayscale)%locs:matrixinwhicheachrowgivesakeypointlocation(row,%column,scale,orientation)func

22、tionshowkeys(image,locs)disp('DrawingSIFTkeypoints.');%Drawimagewithkeypointsfigure('Position',5050size(image,2)size(image,1);colormap('gray');imagesc(image);holdon;imsize=size(image);fori=1:size(locs,1)%Drawanarrow,eachlinetransformedaccordingtokeypointparameters.TransformLi

23、ne(imsize,locs(i,:),0.0,0.0,1.0,0.0);TransformLine(imsize,locs(i,:),0.85,0.1,1.0,0.0);TransformLine(imsize,locs(i,:),0.85,-0.1,1.0,0.0);endholdoff;%Subroutine:TransformLine%Drawthegivenlineintheimage,butfirsttranslate,rotate,and%scaleaccordingtothekeypointparameters.%Parameters:%Arrays:%imsize=rowsc

24、olumnsofimage%keypoint=subpixel_rowsubpixel_columnscaleorientation%Scalars:%x1,y1;beginingofvector%x2,y2;endingofvectorfunctionTransformLine(imsize,keypoint,x1,y1,x2,y2)%Thescalingoftheunitlengtharrowissettoapproximatelytheradius%oftheregionusedtocomputethekeypointdescriptor.len=6*keypoint(3);%Rotat

25、ethekeypointsby'ori'=keypoint(4)s=sin(keypoint(4);c=cos(keypoint(4);%Applytransformr1=keypoint(1)-len*(c*y1+s*x1);c1=keypoint(2)+len*(-s*y1+c*x1);r2=keypoint(1)-len*(c*y2+s*x2);c2=keypoint(2)+len*(-s*y2+c*x2);line(c1c2,r1r2,'Color','c');4) sift.m%image,descriptors,locs=sift(i

26、mageFile)%ThisfunctionreadsanimageandreturnsitsSIFTkeypoints.%Inputparameters:%imageFile:thefilenamefortheimage.%Returned:%image:theimagearrayindoubleformat%descriptors:aK-by-128matrix,whereeachrowgivesaninvariant%descriptorforoneoftheKkeypoints.Thedescriptorisavector%of128valuesnormalizedtounitleng

27、th.%locs:K-by-4matrix,inwhicheachrowhasthe4valuesfora%keypointlocation(row,column,scale,orientation).The%orientationisintherange-PI,PIradians.%Credits:ThanksforinitialversionofthisprogramtoD.Alvaroand%J.J.Guerrero,UniversidaddeZaragoza(modifiedbyD.Lowe)functionimage,descriptors,locs=sift(imageFile)%

28、Loadimagefollowingimage=imread(imageFile);%IfyouhavetheImageProcessingToolbox,youcanuncommentthe%linestoallowinputofcolorimages,whichwillbeconvertedtograyscale.%ifisrgb(image)%image=rgb2gray(image);%endrows,cols=size(image);%ConvertintoPGMimagefile,readableby"keypoints"executablef=fopen('tmp.pgm','w');iff=-1error('Couldnotcreatefiletmp.pgm.');endfprintf(f,'P5n%dn%dn255n',cols,rows);fwrite(f,image','uint8');fclose(f);%Callkeypoint