基于特征匹配的算法.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 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 ? 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 高斯滤波平滑，然后拉普拉斯滤波。,Laplacian-of-Gaussian (LoG)尺度空间的局部极大值点,1.2 尺度不变特征检测,(3) The Difference-of-Gaussian (DoG) Detector 可用高斯差分函数(DoG)近似LoG,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),图：利用二阶矩矩阵的特征值估计兴趣点区域的仿射形状，变换是用该矩阵的平方根进行的，经过归一化的图像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 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 树,一.