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算法詳細1尺

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

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

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

5、6個領(lǐng)域中是最大或最小值時，就認為該點是圖像在該尺度下的一個特征點，如圖1所示。圖3DoG尺度空間局部極值檢測3)構(gòu)建尺度空間需確定的參數(shù)一尺度空間坐標Ooctave6Ssub-level坐標和0、S的關(guān)系(o,s)°2os/S,oomin0,.,O1,s0,.,S1其中o是基準層尺度。ooctave標，ssub-level坐標。注：octaves的索引可能是負的。第一組索引常常設(shè)為。或者-1,當(dāng)設(shè)為-1的時候，圖像在計算高斯尺度空間前先擴大一倍。oxo,o空間坐標x是組octave的函數(shù)，設(shè)x0是0組的空間坐標，如此,xoO,.,No10,.,M°1如果Mo,No是根底組

6、o=0的分辨率，如此其他組的分辨率由下式獲得:NoNo寸,MoMo注：在Lowe的文章中，Lowe使用了如下的參數(shù):no.5,o1.621/S,omin1,S3n1在組。=-1,圖像用雙線性插值擴大一倍對丁擴大的圖像4準確確定極值點位置通過擬和三維二次函數(shù)以準確確定關(guān)鍵點的位置和尺度達到業(yè)像素精度，同時去除低比照度的關(guān)鍵點和不穩(wěn)定的邊緣響應(yīng)點（因為DoG算子會產(chǎn)生較強的邊緣響應(yīng)），以增強匹配穩(wěn)定性、提高抗噪聲能力。 空間尺度函數(shù)D（x,y,）D(x,y,)Dx°,y。,泰勒展開式如下:D(x,y,)Dx,y,dtxx2Dxx對上式求導(dǎo)，并令其為o,得到準確的位置必,？2D1D 在已經(jīng)

7、檢測到的特征點中，要去掉低比照度的特征點和不穩(wěn)定的邊緣響應(yīng)點。去除低比照度的點：把公式（4）代入公式（3）,只取前兩項可得：D(?)Dx,y,1 Dt2 x假如Dx。.。3,該特征點就保存下來，否如此丟棄。 邊緣響應(yīng)的去除一個定義不好的高斯差分算子的極值在橫跨邊緣的地方有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。主曲率通過一個2x2的Hessiar巨陣H求出:HDxxDxyDxyDyy導(dǎo)數(shù)由采樣點相鄰差估計得到。D的主曲率和H的特征值成正比，令為最大特征值，為最小的特征值，如此TiIHi=DIX+D典=e+RDet(H)=DmDwrtJ.令，如此：TY(H)2=(己+疔=即+目F=(+1

8、尸Det(H)adrtPr(r+1)2/r的值在兩個特征值相等的時候最小，隨著r的增大而增大，因此,為了檢測主曲率是否在某域值r下，只需檢測在Lowe的文章中，取r=10。5關(guān)鍵點方向分配利用關(guān)鍵點鄰域像素的梯度方向分布特性為每個關(guān)鍵點指定方向參數(shù)，使算子具備旋轉(zhuǎn)不變性。用(工j)=£(工T/)'+(£(工J時板,y)=atan2(L(x,y+1)-A(x,>+l.y)-Z(r-1?)式(5)為(x,y)處梯度的模值和方向公式。其中L所用的尺度為每個關(guān)鍵點各自所在的尺度。在實際計算時，我們在以關(guān)鍵點為中心的鄰域窗口采樣，并用直方圖統(tǒng)計鄰域像素的梯度方向。梯度直

9、方圖的圍是0360度，其中每10度一個柱，總共36個柱直方圖的峰值如此代表了該關(guān)鍵點處鄰域梯度的主方向，即作為該關(guān)鍵點的方向。圖4是采用7個柱時使用梯度直方圖為關(guān)鍵點確定主方向的示例。bX°圖4由梯度方向直方圖確定主梯度方向在梯度方向直方圖中，當(dāng)存在另一個相當(dāng)丁主峰值80tt量的峰值時，如此將這個方向認為是該關(guān)鍵點的輔方向。一個關(guān)鍵點可能會被指定具有多個方向一個主方向，一個以上輔方向，這可以增強匹配的魯棒性53。至此，圖像的關(guān)鍵點已檢測完畢，每個關(guān)鍵點有三個信息：位置、所處尺度、方向。由此可以確定一個SIFT特征區(qū)域在實驗章節(jié)用橢圓或箭頭表示6特征點描述子生成首先將坐標軸旋轉(zhuǎn)為關(guān)鍵點

10、的方向，以確保旋轉(zhuǎn)不變性圖5由關(guān)鍵點鄰域梯度信息生成特征向量接下來以關(guān)鍵點為中心取8X8的窗口。圖5-4左局部的中央黑點為當(dāng)前關(guān)鍵點的位置，每個小格代表關(guān)鍵點鄰域所在尺度空間（和關(guān)鍵點是否為一個尺度空問）的一個像素，利用公式5求得每個像素i,j的梯度幅值m,j與梯度方向i,j,箭頭方向代表該像素的梯度方向，箭頭長度代表梯度模值，然后用高斯窗口對其進展加權(quán)運算，每個像素對應(yīng)一個向量，長度為G',i,jm,j，G',i,j為該像素點的高斯權(quán)值，方向為門，圖中藍色的圈代表高斯加權(quán)的圍越靠近關(guān)鍵點的像素梯度方向信息貢獻越大。高斯參數(shù)（T'取3倍特征點所在的尺度。然后在每4X4的

11、小塊上計算8個方向的梯度方向直方圖，繪制每個梯度方向的累加值，即可形成一個種子點，如圖5右局部所示。此圖中一個關(guān)鍵點由2X2共4個種子點組成，每個種子點有8個方向向量信息。這種鄰域方向性信息聯(lián)合的思想增強了算法抗噪聲的能力，同時對丁含有定位誤差的特征匹配也提供了較好的容錯性。實際計算過程中，為了增強匹配的穩(wěn)健性，對每個關(guān)鍵點使用4X4共16個種子點來描述，這樣對丁一個關(guān)鍵點就可以產(chǎn)生128個數(shù)據(jù)，即最終形成128維的SIFT特征向量。此時SIFT特征向量已經(jīng)去除了尺度變化、旋轉(zhuǎn)等幾何變形因素的影響，再繼續(xù)將特征向量的長度歸一化，如此可以進一步去除光照變化的影響。當(dāng)兩幅圖像的SIFT特征向量生成

12、后，下一步我們采用關(guān)鍵點特征向量的歐式距離來作為兩幅圖像中關(guān)鍵點的相似性判定度量。取圖像1中的某個關(guān)鍵點，并找出其與圖像2中歐式距離最近的前兩個關(guān)鍵點，在這兩個關(guān)鍵點中，如果最近的距離除以次近的距離少丁某個比例閾值，如此承受這一對匹配點。降低這個比例閾值，SIFT匹配點數(shù)目會減少，但更加穩(wěn)定。為了排除因為圖像遮擋和背景混亂而產(chǎn)生的無匹配關(guān)系的關(guān)鍵點，用比擬最近鄰距離與次近鄰距離的方法，距離比率ratio小丁某個閾值的認為是正確匹配。因為對丁錯誤匹配，由丁特征空間的高維性，相似的距離可能有大量其他的錯誤匹配，從而它的ratio值比擬高。推薦ratio的閾值為0.8。5仿真結(jié)果分析將文件參加mat

13、lab目錄后，在主程序中有兩種操作:op1：尋找圖像中的Sift特征：image,discrips,locs=sift('scene.pgm');Findingkeypoints.1021keypointsfound.>>showkeys(image,locs);DrawingSIFTkeypoints.5010015020025030035050100150200250300350400450500op2:對兩幅圖中的SIFT特征進展匹配:match('scene.pgm','book.pgm');Findingkeypoints.

14、1021keypointsfound.Findingkeypoints.882keypointsfound.Found98matches.1002003004005006007008006代碼%im=appendimages(image1,image2)%Returnanewimagethatappendsthetwoimagesside-by-side.functionim=appendimages(image1,image2)%Selecttheimagewiththefewestrowsandfillinenoughemptyrows%tomakeitthesameheightasthe

15、otherimage.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;%num=match(image1,image2)%Thisfunctionreadstwoimages,findstheirSIFTfeatures,andmatchisacceptedthedistancetothe%displayslinesconnectingthe

16、matchedkeypoints.A%onlyifitsdistanceislessthandistRatiotimes%secondclosestmatch.%Itreturnsthenumberofmatchesdisplayed.%Example:match('scene.pgm','book.pgm');functionnum=match(image1,image2)%FindSIFTkeypointsforeachimageim1,des1,loc1=sift(image1);im2,des2,loc2=sift(image2);%Forefficie

17、ncyinMatlab,itischeapertoputedotproductsbetween%unitvectorsratherthanEuclideandistances.Notethattheratioof%angles(acosofdotproductsofunitvectors)isacloseapproximation%totheratioofEuclideandistancesforsmallangles.%distRatio:Onlykeepmatchesinwhichtheratioofvectoranglesfromthe%nearesttosecondnearestnei

18、ghborislessthandistRatio.distRatio=0.6;%Foreachdescriptorinthefirstdes2t=des2'fori=1:size(des1,1)dotprods=des1(i,:)*des2t;vals,indx=sort(acos(dotprods);resultsimage,selectitsmatchtosecondimage.%Preputematrixtranspose%putesvectorofdotproducts%Takeinversecosineandsort%Checkifnearestneighborhasangl

19、elessthandistRatiotimes2nd.if(vals(1)<distRatio*vals(2)match(i)=indx(1);elsematch(i)=0;endend%Createanewimageshowingthetwoimagessidebyside.im3=appendimages(im1,im2);%Showafigurewithlinesjoiningtheacceptedmatches.figure('Position',100100size(im3,2)size(im3,1);colormap('gray');image

20、sc(im3);holdon;colsl=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');endendholdoff;num=sum(match>0);fprintf('Found%dmatches.n',num);%showkeys(image,locs)%ThisfunctiondisplaysanimagewithSIFTkeypoin

21、tsoverlayed.%Inputparameters:%image:thefilenamefortheimage(grayscale)%locs:matrixinwhicheachrowgivesakeypointlocation(row,%column,scale,orientation)functionshowkeys(image,locs)disp('DrawingSIFTkeypoints.');%Drawimagewithkeypointsfigure('Position',5050size(image,2)size(image,1);colorm

22、ap('gray');imagesc(image);holdon;imsize=size(image);fori=1:size(locs,1)%Drawanarrow,eachlinetransformedaccordingtokeypointparameters.TransformLine(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;%

23、Subroutine:TransformLine%Drawthegivenlineintheimage,butfirsttranslate,rotate,and%scaleaccordingtothekeypointparameters.%Parameters:%Arrays:%imsize=rowscolumnsofimage%keypoint=subpixel_rowsubpixel_columnscaleorientation%Scalars:%x1,y1;beginingofvector%x2,y2;endingofvectorfunctionTransformLine(imsize,

24、keypoint,x1,y1,x2,y2)%Thescalingoftheunitlengtharrowissettoapproximatelytheradius%oftheregionusedtoputethekeypointdescriptor.len=6*keypoint(3);%Rotatethekeypointsby'ori'=keypoint(4)s=sin(keypoint(4);c=cos(keypoint(4);%Applytransformr1=keypoint(1)-len*(c*y1+s*x1);cl=keypoint(2)+len*(-s*y1+c*x

25、1);r2=keypoint(1)-len*(c*y2+s*x2);c2=keypoint(2)+len*(-s*y2+c*x2);line(c1c2,r1r2,'Color','c');%image,descriptors,locs=sift(imageFile)%ThisfunctionreadsanimageandreturnsitsSIFTkeypoints.%Inputparameters:%imageFile:thefilenamefortheimage.%Returned:%image:theimagearrayindoubleformat%des

26、criptors:aK-by-128matrix,whereeachrowgivesaninvariant%descriptorforoneoftheKkeypoints.Thedescriptorisavector%of128valuesnormalizedtounitlength.%locs:K-by-4matrix,inwhicheachrowhasthe4valuesfora%keypointlocation(row,column,scale,orientation).The%orientationisintherange-PI,PIradians.%Credits:Thanksfor

27、initialversionofthisprogramtoD.Alvaroand%J.J.Guerrero,UniversidaddeZaragoza(modifiedbyD.Lowe)functionimage,descriptors,locs=sift(imageFile)%Loadimageimage=imread(imageFile);%IfyouhavetheImageProcessingToolbox,youcanunmentthefollowing%linestoallowinputofcolorimages,whichwillbeconvertedtograyscale.%if

28、isrgb(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);