基于特征匹配的算法.ppt
基于特征的匹配,一.特征匹配过程 1 特征提取 2 特征描述 3 特征匹配 二.SIFT算法,Local features Detection:,2 x 2 matrix of image derivatives(averaged inneighborhood 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=2Edge:significant gradient in 1 direction rank M=1Homogeneous region rank M=0,Harris detector 流程1.Image derivatives2.Square of derivatives3.Gaussian filter g()4.Cornerness function5.Non-maxima suppression cHarris tHarris,（2）Hessian detector(Beaudet,1978),Taylor二阶展开式,得到Hessian矩阵,I,Ixx,Ixy,Iyy,小总结,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?NoHessian 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 高斯滤波平滑，然后拉普拉斯滤波。,Laplacian-of-Gaussian(LoG)尺度空间的局部极大值点,1.2 尺度不变特征检测,(3)The Difference-of-Gaussian(DoG)Detector 可用高斯差分函数(DoG)近似LoG,Computation in Gaussian scale pyramid,LoG and DoGZero 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),图：利用二阶矩矩阵的特征值估计兴趣点区域的仿射形状，变换是用该矩阵的平方根进行的，经过归一化的图像XL和XR之间的变换是旋转变换关系，只取决于一个旋转因子，因子大小代表了特征值的比率,图：Harris-Affine算子检测的从不同视角得到的结果图,图：Hessian-Affine算子得到的不同视图下的影像检测结果,一.特征匹配过程 1 特征提取 1.1 Harris and Hessian Detector 1.2 尺度不变特征检测 1.3 仿射不变特征检测 1.4 特征提取总结 2 特征描述 3 特征匹配 二.SIFT算法,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 beRepeatableDistinctiveCompactEfficientChallenges 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 ideaEfficient computation by 2D box filters&integral images 6 times faster than SIFTEquivalent 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算法由 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),2.4 Keypoint Descriptor,Actual implementation uses 4*4 descriptors from 16*16 which leads to a 4*4*8=128 element vector,
