基于特征匹配的算法.ppt

基于特征的匹配,一.特征匹配過(guò)程1特征提取2特征描述3特征匹配二.SIFT算法,LocalfeaturesDetection:,2x2matrixofimagederivatives(averagedinneighborhoodofapoint).,（1）平移Translation（2）歐幾里德幾何（平移+旋轉(zhuǎn)）（3）相似性變換（平移+旋轉(zhuǎn)+尺度）（4）仿射變換（5）投影變換,Theneedforinvariance,1.幾何變換,2.光照變化,一.特征匹配過(guò)程1特征提取1.1HarrisandHessianDetector1.2尺度不變特征檢測(cè)1.3仿射不變特征檢測(cè)1.4特征提取總結(jié)2特征描述3特征匹配二.SIFT算法,（1）Harrisdetector(Harris,1988),Secondmomentmatrix/autocorrelationmatrix,公式由來(lái)說(shuō)明,影像信號(hào)的局部自相關(guān)函數(shù),給定點(diǎn)(x,y)及位移(x,y)，窗口為W，用差平方和(SSD)近似自相關(guān)函數(shù)，計(jì)算窗口W和位移窗口內(nèi)灰度的差別。,位移后影像函數(shù)通過(guò)一階泰勒展開式近似,重新計(jì)算f(x,y):,“secondmomentmatrixM”,Autocorrelation(secondmoment)matrix,Mcanbeusedtoderiveameasureof“cornerness”Independentofvariousdisplacements(x,y)Corner:significantgradientsin1directionsrankM=2Edge:significantgradientin1directionrankM=1HomogeneousregionrankM=0,Harrisdetector流程1.Imagederivatives2.Squareofderivatives3.Gaussianfilterg()4.Cornernessfunction5.Non-maximasuppressioncHarristHarris,（2）Hessiandetector(Beaudet,1978),Taylor二階展開式,得到Hessian矩陣,I,Ixx,Ixy,Iyy,小總結(jié),HarrisdetectorRotationinvariant?YesTheeigenvaluesofMrevealtheamountofintensitychangeinthetwoprincipalorthogonalgradientdirectionsinthewindow.Scaleinvariant?NoHessiandetector,Rotationinvariant?Yes,Scaleinvariant?No,一.特征匹配過(guò)程1特征提取1.1HarrisandHessianDetector1.2尺度不變特征檢測(cè)1.3仿射不變特征檢測(cè)1.4特征提取總結(jié)2特征描述3特征匹配二.SIFT算法,1.2尺度不變特征檢測(cè),(1)尺度選擇(2)TheLaplacian-of-Gaussian(LoG)Detector(3)TheDifference-of-Gaussian(DoG)Detector(4)TheHarris-LaplacianDetector(5)TheHessian-LaplaceDetector,1.2尺度不變特征檢測(cè),(1)尺度選擇,1.2尺度不變特征檢測(cè),(1)尺度選擇,1.2尺度不變特征檢測(cè),(2)TheLaplacian-of-Gaussian(LoG)Detector1LaplacianfilterLaplacian算子具有旋轉(zhuǎn)不變性，但對(duì)噪聲很敏感，因此常需進(jìn)行平滑操作2LoGfilter高斯濾波平滑，然后拉普拉斯濾波。,Laplacian-of-Gaussian(LoG)尺度空間的局部極大值點(diǎn),1.2尺度不變特征檢測(cè),(3)TheDifference-of-Gaussian(DoG)Detector可用高斯差分函數(shù)(DoG)近似LoG,ComputationinGaussianscalepyramid,LoGandDoGZerocrossings“Mexicanhat”,“Sombrero”Edgedetector!,LowesDoGkeypointsLoweEdgezero-crossingBlobatcorrespondingscale:localextremum!Lowcontrastcornersuppression:thresholdAssesscurvaturedistinguishcornersfromedgesKeypointdetection:,1.2尺度不變特征檢測(cè),(4)TheHarris-LaplacianDetector1初始化：多尺度下的Harris角點(diǎn)檢測(cè)2基于Laplacian的尺度選擇,Harrispoints,Harris-Laplacianpoints,1.2尺度不變特征檢測(cè),(5)TheHessian-LaplaceDetector思想與Harris-LaplacianDetector相同,圖：Hessian-Laplace算子應(yīng)用于具有尺度改變的影像結(jié)果,圖：Harris-Laplace算子在同一場(chǎng)景下不同尺度的兩幅影像上特征檢測(cè)結(jié)果，圓的半徑代表了特征尺度大小,一.特征匹配過(guò)程1特征提取1.1HarrisandHessianDetector1.2尺度不變特征檢測(cè)1.3仿射不變特征檢測(cè)1.4特征提取總結(jié)2特征描述3特征匹配二.SIFT算法,1.3仿射不變特征檢測(cè),Harris/HessianAffine,給定一組由Harris-Laplace算子得到其尺度特征的初始點(diǎn)，用橢圓形區(qū)域獲得仿射不變性。具體處理步驟如下：(1)由Harris-Laplace算子獲得興趣點(diǎn)初始區(qū)域(2)由二階矩矩陣估計(jì)區(qū)域仿射形狀(3)歸一化仿射區(qū)域成為圓形區(qū)域(4)在歸一化的影像上重新檢測(cè)新的位置和尺度(5)如果二階矩矩陣的特征值在新的點(diǎn)上不相等，則轉(zhuǎn)(2),圖：利用二階矩矩陣的特征值估計(jì)興趣點(diǎn)區(qū)域的仿射形狀，變換是用該矩陣的平方根進(jìn)行的，經(jīng)過(guò)歸一化的圖像XL和XR之間的變換是旋轉(zhuǎn)變換關(guān)系，只取決于一個(gè)旋轉(zhuǎn)因子，因子大小代表了特征值的比率,圖：Harris-Affine算子檢測(cè)的從不同視角得到的結(jié)果圖,圖：Hessian-Affine算子得到的不同視圖下的影像檢測(cè)結(jié)果,一.特征匹配過(guò)程1特征提取1.1HarrisandHessianDetector1.2尺度不變特征檢測(cè)1.3仿射不變特征檢測(cè)1.4特征提取總結(jié)2特征描述3特征匹配二.SIFT算法,Harris-Laplace(HRL)scale-adaptedHarris(rotationinvariant)Laplacian-of-Gaussianscale-space(scaleinvariant)detectscornerlikestructuresHessian-Laplace(HSL)Hessiandetector(rotationinvariant)Laplacian-of-Gaussianscale-space(scaleinvariant)blob-likestructureshigherlocalizationaccuracythanDoGhigherscaleselectionaccuraythanHRLLaplacekernelfitsbettertoblobsthantocornersDifference-of-Gaussian(DoG)localscale-spacemaximaoftheDoGblob-likestructuresrespondtoedges(unstable)Harris-Affine(HRA)localizationandscaleestimatedbyHRLaffineadaptationprocessbasedonsecondmomentmatrixHessian-Affine(HSA)HSL+affineadaptationprocess,一.特征匹配過(guò)程1特征提取2特征描述2.1概述2.2幾種特征描述方法3特征匹配二.SIFT算法,2.1特征描述概述,Extractvectorfeaturedescriptorsurroundingeachinterestpoint.TheidealdescriptorshouldbeRepeatableDistinctiveCompactEfficientChallengesInvariant：IlluminationScaleRotationAffine,Illumination,Scale,Rotation,Affine,一.特征匹配過(guò)程1特征提取2特征描述2.1概述2.2幾種特征描述方法3特征匹配二.SIFT算法,2.2幾種特征描述方法,(1)Rawpatches(2)Momentinvariants(3)Filters(4)SIFTdescriptor(5)SURF,(1)Rawpatches描述特征點(diǎn)鄰域的最簡(jiǎn)單方法是直接將鄰域的像素灰度強(qiáng)度構(gòu)成特征向量。用相關(guān)系數(shù)估計(jì)兩個(gè)描述子的相似程度缺點(diǎn)：1對(duì)位置，尺度，姿態(tài)的變化敏感2弱區(qū)分性,(2)Momentinvariants1962年Hu提出了圖像識(shí)別的不變矩理論，即圖像的7個(gè)不變矩具有平移、旋轉(zhuǎn)、比例不變性。為圖像識(shí)別建立了一種統(tǒng)計(jì)特征提取方法，得到了廣泛應(yīng)用。以下7個(gè)對(duì)平移、旋轉(zhuǎn)和尺度變換不變的矩是由歸一化的二階和三階中心矩得到的：,(2)MomentinvariantsGeneralmomentsoforderp+qanddegreea:Centralmomentspq:invarianttotranslation,Normalizedcentralmoments,Translation,rotation,scaleinvariantmoments1.7Hu,Geometric/photometric,colorinvariantsvanGooletal.,Computingtheinvariantsreducesthenumberofdimensions,Moresuitableforcolorimages,(3)filters,complexfilters,differentialinvariants“l(fā)ocaljet”(一系列導(dǎo)數(shù)向量)影像I在點(diǎn)X處的N階localjet定義為：,steerablefilters,Whichsteerderivativesinaparticulardirectiongiventhecomponentsofthelocaljet,影像導(dǎo)數(shù)由高斯導(dǎo)數(shù)的卷積來(lái)獲得。,(a)高斯導(dǎo)數(shù)到4階,(b)6階復(fù)數(shù)濾波(complexfilters),“l(fā)ocaljet”,L(x,)是由高斯導(dǎo)數(shù)和影像卷積而成,旋轉(zhuǎn)不變,(4)SIFTdescriptor,(5)SURF,ApproximateSIFTWorksalmostequallywellVeryfast,FastapproximationofSIFTideaEfficientcomputationby2Dboxfilters&integralimages6timesfasterthanSIFTEquivalentqualityforobjectidentification,見(jiàn)后面講解,一.特征匹配過(guò)程1特征提取2特征描述3特征匹配二.SIFT算法,3特征匹配,3.1基于局部灰度信息的特征匹配方法局部區(qū)域灰度統(tǒng)計(jì)特性3.2基于特征向量的特征匹配方法特征向量之間的距離（1）歐氏距離（2）馬氏距離,k-d樹是二叉檢索樹的擴(kuò)展，k-d樹的每一層將空間分成兩個(gè)。樹的頂層結(jié)點(diǎn)按一維進(jìn)行劃分，下一層結(jié)點(diǎn)按另一維進(jìn)行劃分，以此類推，各個(gè)維循環(huán)往復(fù)。劃分要使得在每個(gè)結(jié)點(diǎn)，大約一半存儲(chǔ)在子樹中的點(diǎn)落入一側(cè)，而另一半落入另一側(cè)。當(dāng)一個(gè)結(jié)點(diǎn)中的點(diǎn)數(shù)少于給定的最大點(diǎn)數(shù)時(shí)，劃分結(jié)束。,K-d樹,一.特征匹配過(guò)程1特征提取2特征描述3特征匹配二.SIFT算法1SIFT思想與特點(diǎn)2算法流程,1SIFT思想與特點(diǎn)SIFT算法由D.G.Lowe1999年提出，2004年完善總結(jié)。SIFT算法是一種提取局部特征的算法，在尺度空間尋找局部極值點(diǎn)，提取基于的位置，尺度，旋轉(zhuǎn)不變量。SIFT特征是圖像的局部特征，其對(duì)旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性，對(duì)視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性。,2SIFT算法流程2.1Scale-spaceextremadetection,尺度空間的建立使用高斯核規(guī)范化LoG用DoG近似LoG所有DoG影像，檢測(cè)極大或極小值（26鄰域）,2.2Keypo