基于特征匹配的算法.ppt

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,基于特征的匹配,一,.,特征匹配过程,1,特征提取,2,特征描述,3,特征匹配,二,.SIFT,算法,Local features Detection:,2 x 2 matrix of image derivatives(averaged in,neighborhood of a point).,（,1,）平移,Translation,（,2,）欧几里德几何（平移,+,旋转）,（,3,）相似性变换（平移,+,旋转,+,尺度）,（,4,）仿射变换,（,5,）投影变换,The need for invariance,1.,几何变换,2.,光照变化,一,.,特征匹配过程,1,特征提取,1.1 Harris and Hessian Detector,1.2,尺度不变特征检测,1.3,仿射不变特征检测,1.4,特征提取总结,2,特征描述,3,特征匹配,二,.SIFT,算法,（,1,）,Harris detector(Harris,1988),Second moment matrix/autocorrelation matrix,公式由来说明,影像信号的局部自相关函数,给定点,(x,y),及位移,(x,y),，窗口为,W,，用差平方和,(SSD),近似自相关函数，计算窗口,W,和位移窗口内灰度的差别。,位移后影像函数通过一阶泰勒展开式近似,重新计算,f(x,y),:,“second moment matrix,M,”,Autocorrelation(,second moment),matrix,M can be used to derive a measure of“,cornerness,”,Independent of various displacements(,x,y,),Corner:significant gradients in 1 directions,rank,M,=2,Edge:significant gradient in 1 direction,rank,M,=1,Homogeneous region rank,M,=0,Harris detector,流程,1.Image derivatives,2.Square of derivatives,3.Gaussian filter g(),4.,Cornerness,function,5.Non-maxima suppression,c,Harris,t,Harris,（,2,）,Hessian detector(Beaudet,1978),Taylor,二阶展开式,得到,Hessian,矩阵,I,I,xx,I,xy,I,yy,小总结,Harris detector,Rotation invariant?Yes,The,eigenvalues,of,M,reveal the amount of intensity change in the two principal orthogonal gradient directions in the window.,Scale invariant?No,Hessian detector,Rotation invariant?Yes,Scale invariant?No,一,.,特征匹配过程,1,特征提取,1.1 Harris and Hessian Detector,1.2,尺度不变特征检测,1.3,仿射不变特征检测,1.4,特征提取总结,2,特征描述,3,特征匹配,二,.SIFT,算法,1.2,尺度不变特征检测,(1),尺度选择,(2)The,Laplacian,-of-Gaussian(,LoG,)Detector,(3)The Difference-of-Gaussian(,DoG,)Detector,(4)The Harris-,Laplacian,Detector,(5)The Hessian-Laplace Detector,1.2,尺度不变特征检测,(1),尺度选择,1.2,尺度不变特征检测,(1),尺度选择,1.2,尺度不变特征检测,(2)The,Laplacian,-of-Gaussian(,LoG,)Detector,1,Laplacian,filter,Laplacian,算子具有旋转不变性，但对噪声很敏感，因此常需进行平滑操作,2,LoG,filter,高斯滤波平滑，然后拉普拉斯滤波。,Smooth,Laplacian,I(x,y,),O(x,y,),Laplacian,-of-Gaussian(,LoG,),尺度空间的局部极大值点,1.2,尺度不变特征检测,(3)The Difference-of-Gaussian(,DoG,)Detector,可用高斯差分函数,(,DoG,),近似,LoG,s,Original image,S,ampling with,step,s,4,=2,s,s,s,Computation in Gaussian scale pyramid,LoG,and,DoG,Zero crossings,“Mexican hat”,“Sombrero”,Edge,detector!,Lowes,DoG,keypoints,Lowe,Edge zero-crossing,Blob at corresponding scale:local,extremum,!,Low contrast corner suppression:threshold,Assess curvature distinguish corners from edges,Keypoint,detection:,1.2,尺度不变特征检测,(4)The Harris-,Laplacian,Detector,1,初始化：多尺度下的,Harris,角点检测,2,基于,Laplacian,的尺度选择,Harris points,Harris-,Laplacian,points,1.2,尺度不变特征检测,(5)The Hessian-Laplace Detector,思想与,Harris-,Laplacian,Detector,相同,图：,Hessian-Laplace,算子应用于具有尺度改变的影像结果,图：,Harris-Laplace,算子在同一场景下不同尺度的两幅影像上特征检测结果，圆的半径代表了特征尺度大小,一,.,特征匹配过程,1,特征提取,1.1 Harris and Hessian Detector,1.2,尺度不变特征检测,1.3,仿射不变特征检测,1.4,特征提取总结,2,特征描述,3,特征匹配,二,.SIFT,算法,1.3,仿射不变特征检测,Harris/Hessian Affine,给定一组由,Harris-Laplace,算子得到其尺度特征的初始点，用椭圆形区域获得仿射不变性。具体处理步骤如下：,(1),由,Harris-Laplace,算子获得兴趣点初始区域,(2),由二阶矩矩阵估计区域仿射形状,(3),归一化仿射区域成为圆形区域,(4),在归一化的影像上重新检测新的位置和尺度,(5),如果二阶矩矩阵的特征值在新的点上不相等，则转,(2),图：利用二阶矩矩阵的特征值估计兴趣点区域的仿射形状，变换是用该矩阵的平方根进行的，经过归一化的图像,X,L,和,X,R,之间的变换是旋转变换关系，只取决于一个旋转因子，因子大小代表了特征值的比率,图：,Harris-Affine,算子检测的,从不同视角得到的结果图,图：,Hessian-Affine,算子得到的不同视图下的影像检测结果,一,.,特征匹配过程,1,特征提取,1.1 Harris and Hessian Detector,1.2,尺度不变特征检测,1.3,仿射不变特征检测,1.4,特征提取总结,2,特征描述,3,特征匹配,二,.SIFT,算法,Detector,Illumination,Rotation,Scale,Affine,Harris corner,Yes,Yes,No,No,DoG,Yes,Yes,Yes,No,Harris_Laplacian,Yes,Yes,Yes,No,Harris_Affine,Yes,Yes,Yes,Yes,Harris-Laplace(HRL),scale-adapted Harris(rotation invariant),Laplacian,-of-Gaussian scale-space(scale invariant),detects,cornerlike,structures,Hessian-Laplace(HSL),Hessian detector(rotation invariant),Laplacian,-of-Gaussian scale-space(scale invariant),blob-like structures,higher localization accuracy than,DoG,higher scale selection,accuray,than HRL,Laplace kernel fits better to blobs than to corners,Difference-of-Gaussian(,DoG,),local scale-space maxima of the,DoG,blob-like structures,respond to edges(unstable),Harris-Affine(HRA),localization and scale estimated by HRL,affine adaptation process based on second moment matrix,Hessian-Affine(HSA),HSL+affine adaptation process,一,.,特征匹配过程,1,特征提取,2,特征描述,2.1,概述,2.2,几种特征描述方法,3,特征匹配,二,.SIFT,算法,2.1,特征描述概述,Extract vector feature descriptor surrounding each interest point.,The ideal descriptor should be,Repeatable,Distinctive,Compact,Efficient,Challenges,Invariant,：,Illumination,Scale,Rotation,Affine,Illumination,Scale,Rotation,Affine,一,.,特征匹配过程,1,特征提取,2,特征描述,2.1,概述,2.2,几种特征描述方法,3,特征匹配,二,.SIFT,算法,2.2,几种特征描述方法,(1)Raw patches,(2)Moment invariants,(3)Filters,(4)SIFT descriptor,(5)SURF,(1)Raw patches,描述特征点邻域的最简单方法是直接将邻域的像素灰度强度构成特征向量。,用相关系数估计两个描述子,的相似程度,缺点：,1,对位置，尺度，姿态的变化敏感,2,弱区分性,(2)Moment invariants,1962,年,Hu,提出了图像识别的不变矩理论，即图像的,7,个不变矩具有平移、旋转、比例不变性。为图像识别建立了一种统计特征提取方法，得到了广泛应用。,以下,7,个对平移、旋转和尺度变换不变的矩是由归一化的二阶和三阶中心矩得到的：,(2),Moment invariants,General moments of order,p+q,and degree a,:,Central moments,pq,:invariant to,translation,Normalized central moments,Translation,rotation,scale invariant moments,1.,7 Hu,Geometric/photometric,color invariants vanGool et al.,Computing the invariants reduces the number of dimensions,More suitable for color images,(3)filters,complex filters,differential invariants “local jet”(,一系列导数向量,),影像,I,在点,X,处的,N,阶,local jet,定义为：,steerable filters,Which steer derivatives in a particular direction given the components of the local jet,影像导数,由高斯导,数的卷积,来获得。,(a),高斯导数到,4,阶,(b)6,阶复数滤波,(complex filters),“,local jet”,L(x,),是由高斯导数和影像卷积而成,旋转不变,(4)SIFT descriptor,(5)SURF,Approximate SIFT,Works almost equally well,Very fast,Fast approximation of SIFT idea,Efficient computation by 2D box filters&integral images,6 times faster than SIFT,Equivalent quality for object identification,见后面讲解,一,.,特征匹配过程,1,特征提取,2,特征描述,3,特征匹配,二,.SIFT,算法,3,特征匹配,3.1,基于局部灰度信息的特征匹配方法,局部区域灰度统计特性,3.2,基于特征向量的特征匹配方法,特征向量之间的距离,（,1,）欧氏距离,（,2,）马氏距离,k-d,树是二叉检索树的扩展，,k-d,树的每一层将空间分成两个。树的顶层结点按一维进行划分，下一层结点按另一维进行划分，以此类推，各个维循环往复。划分要使得在每个结点，大约一半存储在子树中的点落入一侧，而另一半落入另一侧。当一个结点中的点数少于给定的最大点数时，划分结束。,K-d,树,一,.,特征匹配过程,1,特征提取,2,特征描述,3,特征匹配,二,.SIFT,算法,1 SIFT,思想与特点,2,算法流程,1 SIFT,思想与特点,SIFT,算法由,D.G.Lowe,1999,年提出，,2004,年完善总结。,SIFT,算法是一种提取局部特征的算法，在尺度空间寻找局部极值点，提取基于的位置，尺度，旋转不变量。,SIFT,特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性。,2 SIFT,算法流程,2.1,Scale-space,extrema,detection,尺度空间的建立使用高斯核,规范化,LoG,用,DoG,近似,LoG,所有,DoG,影像，检测极大或极小值（,26,邻域）,2.2,Keypoint,localization,关键点位置不精确,三维曲面拟合,Taylor,展开式,过滤低对比度点,过滤边缘响应点,(a),原始影像,(b),在,DoG,检测的初始关键点,(c),用对比度限制,(d),用对比度和边缘响应去除,2.3 Orientation assignment,计算高斯平滑影像的梯度和方向,选主方向,平滑直方图的峰值,旋转到主方向,建方向直方图,(36 bins),0,2,p,2.4,Keypoint,Descriptor,Actual implementation uses 4*4 descriptors from 16*,16,which leads to a 4*4*8=128 element vector,