SIFT算法分析

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

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

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

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

5、果在DOG尺度空間本層以及上下兩層的26個(gè)領(lǐng)域中是最大或最小值時(shí),就認(rèn)為該點(diǎn)是圖像在該尺度下的一個(gè)特征點(diǎn)，如圖1所示。圖3DoG尺度空間局部極值檢測3）構(gòu)建尺度空間需確定的參數(shù)一尺度空間坐標(biāo)Ooctave坐標(biāo)5 sub-level坐標(biāo)和。S的關(guān)系（O,S）020s/S,OOmin0,O1,S0,S1其中0是基準(zhǔn)層尺度。ooctave坐標(biāo)，ssub-level坐標(biāo)。注：octaves的索引可能是負(fù)的。第一組索引常常設(shè)為0或者-1,當(dāng)設(shè)為-1的時(shí)候，圖像在計(jì)算高斯尺度空間前先擴(kuò)大一倍?？臻g坐標(biāo)x是組octave的函數(shù)，設(shè)x0是0組的空間坐標(biāo)，則x2X0,o,Xo0,No10,Mo1如果Mo,No是

6、基礎(chǔ)組o=0的分辨率，則其他組的分辨率由下式獲得：No注：在Lowe的文章中，Lowe#用了如下的參數(shù):1/S_n0.5,01.62,omin1,S3在組o=-1,圖像用雙線性插值擴(kuò)大一倍（對于擴(kuò)大的圖像n1)。4）精確確定極值點(diǎn)位置通過擬和三維二次函數(shù)以精確確定關(guān)鍵點(diǎn)的位置和尺度（達(dá)到亞像素精度），同時(shí)去除低對比度的關(guān)鍵點(diǎn)和不穩(wěn)定的邊緣響應(yīng)點(diǎn)（因?yàn)镈oG算子會產(chǎn)生較強(qiáng)的邊緣響應(yīng)），以增強(qiáng)匹配穩(wěn)定性、提高抗噪聲能力?？臻g尺度函數(shù)D（x,y,）DT7D(x,y,)Dx0,y0,XX0）泰勒展開式如下：DTD(x,y,)Dx,y,xxT2D-xx對上式求導(dǎo)，并令其為0曲到精確的位置,?2D1D在已

7、經(jīng)檢測到的特征點(diǎn)中，要去掉低對比度的特征點(diǎn)和不穩(wěn)定的邊緣響應(yīng)點(diǎn)。去除低對比度的點(diǎn)：把公式（4）代入公式（3）,只取前兩項(xiàng)可得：八1DTcD（x）Dx,y,W2x若D?0.03,該特征點(diǎn)就保留下來，否則丟棄邊緣響應(yīng)的去除一個(gè)定義不好的高斯差分算子的極值在橫跨邊緣的地方有較大的主曲率，而在垂直邊緣的方向有較小的主曲率。主曲率通過一個(gè)2x2的Hessian巨陣H求出：DxxDxyDxyDyy導(dǎo)數(shù)由采樣點(diǎn)相鄰差估計(jì)得到D的主曲率和H的特征值成正比，令為最大特征值，為最小的特征值,111Hi=Dit+=c+氏Det(H)D啦。g(Dry產(chǎn)=rtJ.令，M：TY(H產(chǎn)=(a+J產(chǎn)=(*3+戶(=(+1產(chǎn)D

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

9、直方圖的范圍是0360度，其中每10度一個(gè)柱，總共36個(gè)柱。直方圖的峰值則代表了該關(guān)鍵點(diǎn)處鄰域梯度的主方向，即作為該關(guān)鍵點(diǎn)的方向。圖4是采用7個(gè)柱時(shí)使用梯度直方圖為關(guān)鍵點(diǎn)確定主方向的示例。(窗口尺寸采用Lowef隹薦的0-xo-)圖4由梯度方向直方圖確定主梯度方向在梯度方向直方圖中，當(dāng)存在另一個(gè)相當(dāng)于主峰值80%能量的峰值時(shí)，則將這個(gè)方向認(rèn)為是該關(guān)鍵點(diǎn)的輔方向。一個(gè)關(guān)鍵點(diǎn)可能會被指定具有多個(gè)方向（一個(gè)主方向，一個(gè)以上輔方向），這可以增強(qiáng)匹配的魯棒性530至此，圖像的關(guān)鍵點(diǎn)已檢測完畢，每個(gè)關(guān)鍵點(diǎn)有三個(gè)信息：位置、所處尺度、方向。由此可以確定一個(gè)SIF%征區(qū)域（在實(shí)驗(yàn)章節(jié)用橢圓或箭頭表示）。6）特

10、征點(diǎn)描述子生成首先將坐標(biāo)軸旋轉(zhuǎn)為關(guān)鍵點(diǎn)的方向，以確保旋轉(zhuǎn)不變性穎域嚎表方司關(guān)鋌應(yīng)號征向量圖5由關(guān)鍵點(diǎn)鄰域梯度信息生成特征向量接下來以關(guān)鍵點(diǎn)為中心取8X8的窗口。圖5-4左部分的中央黑點(diǎn)為當(dāng)前關(guān)鍵點(diǎn)的位置，每個(gè)小格代表關(guān)鍵點(diǎn)鄰域所在尺度空間（和關(guān)鍵點(diǎn)是否為一個(gè)尺度空問）的一個(gè)像素，利用公式（5）求得每個(gè)像素i,j的梯度幅值mi,j與梯度方向i,j,箭頭方向代表該像素的梯度方向，箭頭長度代表梯度模值，然后用高斯窗口對其進(jìn)行加權(quán)運(yùn)算，每個(gè)像素對應(yīng)一個(gè)向量，長度為G,i,jm,G,i,j為該像素點(diǎn)的高斯權(quán)值，方向?yàn)閕,j,圖中藍(lán)色的圈代表高斯加權(quán)的范圍（越靠近關(guān)鍵點(diǎn)的像素梯度方向信息貢獻(xiàn)越大）。高斯參

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

12、影響。當(dāng)兩幅圖像的SIF節(jié)征向量生成后，下一步我們采用關(guān)鍵點(diǎn)特征向量的歐式距離來作為兩幅圖像中關(guān)鍵點(diǎn)的相似性判定度量。取圖像1中的某個(gè)關(guān)鍵點(diǎn)，并找出其與圖像2中歐式距離最近的前兩個(gè)關(guān)鍵點(diǎn)，在這兩個(gè)關(guān)鍵點(diǎn)中，如果最近的距離除以次近的距離少于某個(gè)比例閾值，則接受這一對匹配點(diǎn)。降低這個(gè)比例閾值，SIFTS配點(diǎn)數(shù)目會減少，但更加穩(wěn)定。為了排除因?yàn)閳D像遮擋和背景混亂而產(chǎn)生的無匹配關(guān)系的關(guān)鍵點(diǎn)，用比較最近鄰距離與次近鄰距離的方法，距離比率ratio小于某個(gè)閾值的認(rèn)為是正確匹配。因?yàn)閷τ阱e(cuò)誤匹配，由于特征空間的高維性，相似的距離可能有大量其他的錯(cuò)誤匹配，從而它的ratio值比較高。推薦ratio的閾值為。5

13、仿真結(jié)果分析將文件加入matlab目錄后，在主程序中有兩種操作：op1：尋找圖像中的Sift特征：image,discrips,locs=sift();Findingkeypoints.1021keypointsfound.showkeys(image,locs);DrawingSIFTkeypoints.5010015020025030035050100150200250300350400450500op2:對兩幅圖中的SIFTt征進(jìn)行匹配:match。,）；Findingkeypoints.1021keypointsfound.Findingkeypoints.882keypointsfo

14、und.Found98matches.501001502002506代碼1)%im=appendimages(image1,image2)%Returnanewimagethatappendsthetwoimagesside-by-side.functionim=appendimages(image1,image2)%Selecttheimagewiththefewestrowsandf川inenoughemptyrows%tomakeitthesameheightastheotherimage.rows1=size(image1,1);rows2=size(image2,1);if(rows

15、1rows2)image1(rows2,1)=0;elseimage2(rows1,1)=0;end%Nowappendbothimagesside-by-side.im=image1image2;2)%num=match(image1,image2)%Thisfunctionreadstwoimages,findstheirSIFTfeatures,and%displayslinesconnectingthematchedkeypoints.Amatchisaccepted%onlyifitsdistanceislessthandistRatiotimesthedistancetothe%s

16、econdclosestmatch.%Itreturnsthenumberofmatchesdisplayed.%Example:match(,);functionnum=match(image1,image2)%FindSIFTkeypointsforeachimageim1,des1,loc1=sift(image1);im2,des2,loc2=sift(image2);%ForefficiencyinMatlab,itischeapertocomputedotproductsbetween%unitvectorsratherthanEuclideandistances.Notethat

17、theratioof%angles(acosofdotproductsofunitvectors)isacloseapproximation%totheratioofEuclideandistancesforsmallangles.%distRatio:Onlykeepmatchesinwhichtheratioofvectoranglesfromthe%nearesttosecondnearestneighborislessthandistRatio.distRatio=;%Foreachdescriptorinthefirstimage,selectitsmatchtosecondimag

18、e.des2t=des2;%Precomputematrixtransposefori=1:size(des1,1)dotprods=des1(i,:)*des2t;%Computesvectorofdotproductsvals,indx=sort(acos(dotprods);%Takeinversecosineandsortresults%CheckifnearestneighborhasanglelessthandistRatiotimes2nd.if(vals(1)0)line(loc1(i,2)10c2(match(i),2)+cols1,.loc1(i,1)loc2(match(

19、i),1),Color,c);endendholdoff;num=sum(match0);fprintf(Found%dmatches.n,num);3)%showkeys(image,locs)%ThisfunctiondisplaysanimagewithSIFTkeypointsoverlayed.%Inputparameters:%image:thefilenamefortheimage(grayscale)%locs:matrixinwhicheachrowgivesakeypointlocation(row,%column,scale,orientation)functionsho

20、wkeys(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.TransformLine(imsize,10cs(i,:),;TransformLine(ims

21、ize,10cs(i,:),;TransformLine(imsize,10cs(i,:),;endholdoff;%Subroutine:TransformLine%Drawthegivenlineintheimage,butfirsttranslate,rotate,and%scaleaccordingtothekeypointparameters.%Parameters:%Arrays:%imsize=rowscolumnsofimage%keypoint=subpixel_rowsubpixel_columnscaleorientation%Scalars:%x1,y1;beginin

22、gofvector%x2,y2;endingofvectorfunctionTransformLine(imsize,keypoint,x1,y1,x2,y2)%Thescalingoftheunitlengtharrowissettoapproximatelytheradius%oftheregionusedtocomputethekeypointdescriptor.len=6*keypoint(3);%Rotatethekeypointsbyori=keypoint(4)s=sin(keypoint(4);c=cos(keypoint(4);%Applytransformri=keypo

23、int-len*(c*y1+s*x1);ci=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,rir2,Color,c);4)%image,descriptors,locs=sift(imageFile)%ThisfunctionreadsanimageandreturnsitsSIFTkeypoints.%Inputparameters:%imageFile:thefilenamefortheimage.%Returned:%image:

24、theimagearrayindoubleformat%descriptors:aK-by-128matrix,whereeachrowgivesaninvariant%descriptorforoneoftheKkeypoints.Thedescriptorisavector%of128valuesnormalizedtounitlength.%locs:K-by-4matrix,inwhicheachrowhasthe4valuesfora%keypointlocation(row,column,scale,orientation).The%orientationisintherange-

25、PI,PIradians.%Credits:ThanksforinitialversionofthisprogramtoD.Alvaroand%.Guerrero,UniversidaddeZaragoza(modifiedbyD.Lowe)functionimage,descriptors,locs=sift(imageFile)%Loadimageimage=imread(imageFile);%IfyouhavetheImageProcessingToolbox,youcanuncommentthefollowing%linestoallowinputofcolorimages,whichwillbeconvertedtograyscale.%ifisrgb(image)%image=rgb2gray(image);%endrows,cols=size(image);%ConvertintoPGMimagefile,readablebykeypointsexecutablef=fopen(,w);iff=-1error(Couldnotcreatefile.);endfp