基于特征匹配的算法.ppt

基于特征的匹配,一.特征匹配过程1特征提取2特征描述3特征匹配二.SIFT算法,LocalfeaturesDetection:,2x2matrixofimagederivatives(averagedinneighborhoodofapoint).,（1）平移Translation（2）欧几里德几何（平移+旋转）（3）相似性变换（平移+旋转+尺度）（4）仿射变换（5）投影变换,Theneedforinvariance,1.几何变换,2.光照变化,一.特征匹配过程1特征提取1.1HarrisandHessianDetector1.2尺度不变特征检测1.3仿射不变特征检测1.4特征提取总结2特征描述3特征匹配二.SIFT算法,（1）Harrisdetector(Harris,1988),Secondmomentmatrix/autocorrelationmatrix,公式由来说明,影像信号的局部自相关函数,给定点(x,y)及位移(x,y)，窗口为W，用差平方和(SSD)近似自相关函数，计算窗口W和位移窗口内灰度的差别。,位移后影像函数通过一阶泰勒展开式近似,重新计算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,小总结,HarrisdetectorRotationinvariant?YesTheeigenvaluesofMrevealtheamountofintensitychangeinthetwoprincipalorthogonalgradientdirectionsinthewindow.Scaleinvariant?NoHessiandetector,Rotationinvariant?Yes,Scaleinvariant?No,一.特征匹配过程1特征提取1.1HarrisandHessianDetector1.2尺度不变特征检测1.3仿射不变特征检测1.4特征提取总结2特征描述3特征匹配二.SIFT算法,1.2尺度不变特征检测,(1)尺度选择(2)TheLaplacian-of-Gaussian(LoG)Detector(3)TheDifference-of-Gaussian(DoG)Detector(4)TheHarris-LaplacianDetector(5)TheHessian-LaplaceDetector,1.2尺度不变特征检测,(1)尺度选择,1.2尺度不变特征检测,(1)尺度选择,1.2尺度不变特征检测,(2)TheLaplacian-of-Gaussian(LoG)Detector1LaplacianfilterLaplacian算子具有旋转不变性，但对噪声很敏感，因此常需进行平滑操作2LoGfilter高斯滤波平滑，然后拉普拉斯滤波。,Laplacian-of-Gaussian(LoG)尺度空间的局部极大值点,1.2尺度不变特征检测,(3)TheDifference-of-Gaussian(DoG)Detector可用高斯差分函数(DoG)近似LoG,ComputationinGaussianscalepyramid,LoGandDoGZerocrossings“Mexicanhat”,“Sombrero”Edgedetector!,LowesDoGkeypointsLoweEdgezero-crossingBlobatcorrespondingscale:localextremum!Lowcontrastcornersuppression:thresholdAssesscurvaturedistinguishcornersfromedgesKeypointdetection:,1.2尺度不变特征检测,(4)TheHarris-LaplacianDetector1初始化：多尺度下的Harris角点检测2基于Laplacian的尺度选择,Harrispoints,Harris-Laplacianpoints,1.2尺度不变特征检测,(5)TheHessian-LaplaceDetector思想与Harris-LaplacianDetector相同,图：Hessian-Laplace算子应用于具有尺度改变的影像结果,图：Harris-Laplace算子在同一场景下不同尺度的两幅影像上特征检测结果，圆的半径代表了特征尺度大小,一.特征匹配过程1特征提取1.1HarrisandHessianDetector1.2尺度不变特征检测1.3仿射不变特征检测1.4特征提取总结2特征描述3特征匹配二.SIFT算法,1.3仿射不变特征检测,Harris/HessianAffine,给定一组由Harris-Laplace算子得到其尺度特征的初始点，用椭圆形区域获得仿射不变性。具体处理步骤如下：(1)由Harris-Laplace算子获得兴趣点初始区域(2)由二阶矩矩阵估计区域仿射形状(3)归一化仿射区域成为圆形区域(4)在归一化的影像上重新检测新的位置和尺度(5)如果二阶矩矩阵的特征值在新的点上不相等，则转(2),图：利用二阶矩矩阵的特征值估计兴趣点区域的仿射形状，变换是用该矩阵的平方根进行的，经过归一化的图像XL和XR之间的变换是旋转变换关系，只取决于一个旋转因子，因子大小代表了特征值的比率,图：Harris-Affine算子检测的从不同视角得到的结果图,图：Hessian-Affine算子得到的不同视图下的影像检测结果,一.特征匹配过程1特征提取1.1HarrisandHessianDetector1.2尺度不变特征检测1.3仿射不变特征检测1.4特征提取总结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,一.特征匹配过程1特征提取2特征描述2.1概述2.2几种特征描述方法3特征匹配二.SIFT算法,2.1特征描述概述,Extractvectorfeaturedescriptorsurroundingeachinterestpoint.TheidealdescriptorshouldbeRepeatableDistinctiveCompactEfficientChallengesInvariant：IlluminationScaleRotationAffine,Illumination,Scale,Rotation,Affine,一.特征匹配过程1特征提取2特征描述2.1概述2.2几种特征描述方法3特征匹配二.SIFT算法,2.2几种特征描述方法,(1)Rawpatches(2)Momentinvariants(3)Filters(4)SIFTdescriptor(5)SURF,(1)Rawpatches描述特征点邻域的最简单方法是直接将邻域的像素灰度强度构成特征向量。用相关系数估计两个描述子的相似程度缺点：1对位置，尺度，姿态的变化敏感2弱区分性,(2)Momentinvariants1962年Hu提出了图像识别的不变矩理论，即图像的7个不变矩具有平移、旋转、比例不变性。为图像识别建立了一种统计特征提取方法，得到了广泛应用。以下7个对平移、旋转和尺度变换不变的矩是由归一化的二阶和三阶中心矩得到的：,(2)MomentinvariantsGeneralmomentsoforderp+qanddegreea:Centralmomentspq:invarianttotranslation,Normalizedcentralmoments,Translation,rotation,scaleinvariantmoments1.7Hu,Geometric/photometric,colorinvariantsvanGooletal.,Computingtheinvariantsreducesthenumberofdimensions,Moresuitableforcolorimages,(3)filters,complexfilters,differentialinvariants“localjet”(一系列导数向量)影像I在点X处的N阶localjet定义为：,steerablefilters,Whichsteerderivativesinaparticulardirectiongiventhecomponentsofthelocaljet,影像导数由高斯导数的卷积来获得。,(a)高斯导数到4阶,(b)6阶复数滤波(complexfilters),“localjet”,L(x,)是由高斯导数和影像卷积而成,旋转不变,(4)SIFTdescriptor,(5)SURF,ApproximateSIFTWorksalmostequallywellVeryfast,FastapproximationofSIFTideaEfficientcomputationby2Dboxfilters&integralimages6timesfasterthanSIFTEquivalentqualityforobjectidentification,见后面讲解,一.特征匹配过程1特征提取2特征描述3特征匹配二.SIFT算法,3特征匹配,3.1基于局部灰度信息的特征匹配方法局部区域灰度统计特性3.2基于特征向量的特征匹配方法特征向量之间的距离（1）欧氏距离（2）马氏距离,k-d树是二叉检索树的扩展，k-d树的每一层将空间分成两个。树的顶层结点按一维进行划分，下一层结点按另一维进行划分，以此类推，各个维循环往复。划分要使得在每个结点，大约一半存储在子树中的点落入一侧，而另一半落入另一侧。当一个结点中的点数少于给定的最大点数时，划分结束。,K-d树,一.特征匹配过程1特征提取2特征描述3特征匹配二.SIFT算法1SIFT思想与特点2算法流程,1SIFT思想与特点SIFT算法由D.G.Lowe1999年提出，2004年完善总结。SIFT算法是一种提取局部特征的算法，在尺度空间寻找局部极值点，提取基于的位置，尺度，旋转不变量。SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性。,2SIFT算法流程2.1Scale-spaceextremadetection,尺度空间的建立使用高斯核规范化LoG用DoG近似LoG所有DoG影像，检测极大或极小值（26邻域）,2.2Keypo