《SURF算法分析》PPT课件.ppt

用 stitching算法 进行图像拼接 第一部分：用 surf算法提 取特征点 第二部分：特征点匹配 第三部分：构建透视矩阵 完成拼接 第四部分 : 图像融合 1.SURF 介绍 SURF (Speeded Up Robust Feature)是一种高鲁棒性的局 部特征点检测器。由 Herbert Bay 等人在 2006年提出。该算法 可以用于计算机视觉领域例如物体识别或者三维重建。根据 作者描述该算法比 SIFT更快更加具有鲁棒性。该算法中采用 积分图像、 Haar小波变换和近似的 Hessian矩阵运算来提高时 间效率 ,采用 Haar小波变换增加鲁棒性。 一 .用 SURF算法 提取特征点 1.1积分图像 B C 积分图像 A D 1.2Hessian矩阵 快速 Hessian 在 SURF中，采用近似的 Hessian矩阵的行列式的局部 最大值来定位感兴趣点的位置。当 Hessian行列式的局部值 最大的时候，所检测出来的就是感兴趣点。感兴趣点的特 征为比周围邻域更亮或者更暗一些。 给定图像 f(x,y)中一个点 (x,y)，其 Hessian矩阵 H(x,o) 定义如下： 位置 尺度 Lxx(x, )是高斯二阶微分在点 X=(x,y)处与图像 I的卷积 。 Bay指出，高斯函数虽然是最佳的尺度空间分析工具， 但由于在实际应用中总要对高斯函数进行离散化和剪 切处理，从而损失了一些特性（如重复性）。这一因 素为我们用其他工具代替高斯函数对尺度空间的分析 提供了可能，只要误差不大就可以。所以就引入了盒 装滤波器。 如下图所示第一行图像就是经过离散化，被剪切成 9X9方格， =1.2的沿 x 方向、 y方向和 xy方向的高斯二阶微分算子，即 Lxx,Lxy,Lyy模板，这些 微分算子可以用 9x9的盒装滤波器 Dxx模板、 Dxy模板、 Dyy模板替代 ，即图中第二行图像。盒装滤波器中白色部分权值为 1，灰色部分权值为 0， Dxx和 Dyy模板黑色部分的权值为 -2， Dxy模板黑色部分权值为 -1，白 色部分和黑色部分统称突起。 SURF 提取特征点 1.3盒子滤波器 下面介绍利用积分图像求 Dxx、 Dyy、 Dxy的方法首先用前面的积分公式 把输入图像转化为积分图像，然后应用和状滤波器逐一对积分图像进行 处理，盒装滤波器灰色部分权值为 0，不参与计算， Dxx模板和 Dyy模板 各有两个白色部分和一个黑色部分，因此他们的盒装滤波器共有三个突 起部分，而 Dxy模板有两个白色部分和两个黑色部分，因此它的盒装滤 波器共有四个突起部分，利用盒装滤波器对图像进行滤波处理得到响应 值得一般公式为： N表示突起部分总和，对于 Dxx模板和 Dyy模板来说， N=3，对于 Dxy模 板来说， N=4;Sn表示突起部分的面积，如对于 9x9的 Dxx模板和 Dyy模板 来说，突起部分的面积都是是 15（即像素数量），而对于 9x9的 Dxy模板 来说，突起部分面积都是 9，除以 Sn的作用是对模板进行归一化处理； Wn表示第 n个突起部分的权值；而后面的括号部分就是前面的公式，求 模板的每个突起部分对应于图像四个点 A、 B、 C、 D所组成的矩阵区域 的灰度之和。 SURF 提取特征点 快速 Hessian 加权系数 Lxx是高斯模板与图像卷积 Dxx是盒子模板与图像卷积 用 Dxx近似代替 Lxx 如果行列式的结果符号为负，则特征值有不同的符号，则 不是局部极值点。 如果行列式的符号为正，则该行列式的两个特征值同为正 或负，所以该点可以归类为极值点。 Hessian矩阵的行列式的极值处即为特征点 而盒装滤波器代替高斯二阶微分算子要加 一定的权值 w，作用是平衡因近似所带来的 误差 ,w约为 0.9 1.4构建金字塔 构建尺 度空间 由于采用的盒子滤波和积分图像，不需要像 SIFT算法 那样去直接建立金字塔图像，而是采用不断增大的盒子滤 波模板的尺寸的间接方法。通过不同尺寸盒子滤波模板和 积分图像求取 Hessian矩阵行列式的响应图像，然后，在 响应图像上采用 3D非最大值抑制，求取各种不同尺度的斑 点。 SIFT构建尺度空间 SURF构建尺度空间 模板 图片 1.5构建尺度空间 构建尺 度空间 与 SIFT相类似， SURF也将尺度空间划分成若干组 (Octaves)。一个组代表了逐步放大的滤波模板对同一个 输入图像进行滤波的一系列响应图像。每一组又有若干 固定的层组成。 9 15 21 27 15 27 39 51 27 51 75 99 51 99 147 195 变化量 n*6 变 化 量 6*n Scale Oct aves 1.6极值点抑制 极值点 抑制 为了在目标影像上确定 SURF特征点，我们使用了 3*3*3的模板在 3维尺度空间进行非最大化抑制，根据 预设的 Hessian阈值 H，当 h大于 H，而且比临近的 26 个点的响应值都大的点才被选为兴趣点。 最后进行插 值精确。 特征点 方向分配 为 了保证旋转不变性，需要对每一个特征点分配一个主要 方向。需要以特征点为中心，以 6s（ s为特征点的尺度）为半 径的圆形区域内，对图像进行 Haar小波响应运算。这样做实 际就是对图像进行了梯度运算，但是利用积分图像，可以提 高计算图像梯度的效率。为了求取主方向值，需要设计一个 以方向为中心，张角为 PI/3的扇形滑动窗口，以步长为 0.2弧 度左右，旋转这个滑动窗口，并对窗口内的图像 Haar小波的 响应值进行累加。 主方向为最大的 Haar响应累加值对应的方 向 。 旋转窗口 1.7.特征点方向分配 1.8生成特征描述符 生成特 征描述符 生成特征点的特征描述符需要计算图像的 Haar小波响 应。在一个矩形的区域内，以特征点为中心，沿主方向将 20s*20s的图像划分成 4*4个子块，每个子块利用尺寸 2s 的 Haar小波模板进行响应计算，然后对响应值进行统 计 ， ， ， 形成的特征矢量 。 dx dx dy dy 主方向 5s*5s 旋转到主方向 Hear小波模板 每个子块中又有 25个采样像素，对于每 个区域内，我们需要累加所有 25个采样 像素的 dx和 dy，这样形成描述符的一部 分，而为了把强度变化的极性信息也包 括今描述符中，我们还需要对 dx和 dy的 绝对值进行累加。这样每个区域就可以 用一个 4维特征矢量表示，把所有 4x4子 区域组合起来，就形成了一个 64维特征 矢量，即 surf描述符。 标出特征点的图像 二 .特征点 匹配 特征点匹配 特征点 匹配 步骤 1. 在检测特征点的过程中，计算了 Hessian 矩阵 的行列式，与此同时，计算得到了 Hessian 矩阵的迹，矩 阵的迹为对角元素之和。 按照亮度的不同，可以将特征点分为两种，第一种为 特征点及其周围小邻域的亮度比背景区域要亮， Hessian 矩阵的迹为正；另外一种为特征点及其周围小邻域的亮度 比背景区域要暗， Hessian 矩阵为负值。根据这个特性， 首先对两个特征点的 Hessian 的迹进行比较。如果同号， 说明两个特征点具有相同的对比度；如果是异号的话，说 明两个特征点的对比度不同，放弃特征点之间后续的相似 性度量。 特征点匹配 特征点 匹配 步骤 2.对于两个特征点描述符的相似性度量，我们采用 欧式距离进行计算： 式中， Xik表示待配准图中第 i 个特征描述符的第 k 个元素， Xjk是参考图中第 j个特征描述子的第 k 个元素， n表示特征向量的维数。 。 对于待配准图上的特征点，计算它到参考图像上所有 特征点的欧氏距离，得到一个距离集合。通过对距离集 合进行比较运算得到小欧氏距离和次最小欧式距离。设 定一个阈值，一般为 0.8，当最小欧氏距离和次最小欧式 距离的比值小于该阈值时，认为特征点与对应最小欧氏 距离的特征点是匹配的，否则没有点与该特征点相匹配。 阈值越小，匹配越稳定，但极值点越少。 特征点匹配 特征点 匹配 特征点匹配后图像 三 .构建透视矩 阵完成拼接 三 .构建透视矩阵完成拼接 在参考图像和待拼接图像的重叠区域中提取到相应的 特征点集后，就需要构造变换透视矩阵，通过特征点 集不断进行迭代对透视矩阵求精，然后根据求得的透 视变换矩阵将待拼接图像变换到了参考图像的坐标。 但是从透视变换矩阵求得的变换坐标并不是整数，所 以还需要对求得的坐标进行灰度插值计算，以使图像 变换到正确的坐标系中。 透视变换矩阵是由 Szeliski提出的图像变换法，首先通 过建立图像序列之间的变换模型，然后通过迭代算法 求出模型的变换参数，实现对图像序列的拼接，这就 是著名的 8参数透视变换模型。对于相邻两幅图像之间 的变换关系，可以用一个具有 8个参数的变换模型来描 述： （ 3.1） （ 3.2） 其中， I(x,y)和 I(x,y)分别为两幅图像的对应点坐标， 可以看出，计算透视变换矩阵 H，实质上就是计算矩阵 中的 8个参数。将 (3.1)模型的矩阵形式进行改写，得到 （ 3.3） （ 3.4） 对于所有的对应点对，如果要确定 8个未知参数，需要使 下式的值达到最小： （ 3.5） 通过 (3.3)式和 (3.4)式可以知道，选取 4组对应点，就能够 计算出透视变换模型的 8个参数，但是随机选取的对应 点不一定就能够得到模型的准确参数，所以在求其最 小值的过程中采用 Levenberg Marguqrdt迭代非线性 最小化方法对透视变换矩阵进行求精。 首先对于 8个未知参数 m，求偏导数，即 ： （ 3.6） 式中的 Di是 (3.3）和 (3.4)式的分母，然后计算两个矩阵 A和 b，其中 A中的元素为： （ 3.7） 总结：采用这种变换矩阵的方法可以处 理图像之间存在平移、旋转、缩放等变 化条件下的拼接。 四 .图像融合 四：图像融合 通过图像匹配将两幅图像变换到了同一坐标系后，得 到了两幅图像的拼接结果。但是，由于图像采集所带 来的光照、视野等的差异，拼接好的两幅图片在相结 合的部分会出现明显的拼接缝隙，图像融合技术就是 为了去除这种拼接缝隙的有力工具。图像融合应当满 足几个方面的要求：首先，为了消除图像的拼接缝隙 ，就必须采用一种渐变的方法来将拼接的缝隙部分像 素转变为从第一副图片渐变为第二幅图片；其次，图 像的融合应当只针对于拼接的结合部分有效，对于图 像的其他部分不能够产生影响；最后， 融合算法在算法的复杂度上不能太高，不能影响了图 像拼接的整体速度。 加权平均法对于重叠部分的像素值不是简单的叠加求 平均值，而是先进行加权后，再进行叠加平均。假设 现在有两幅图像中的重叠部分分别定义一个权值，取 为 d1和 d2,并且 d1和 d2都满足条件属于（ 0， 1），且 d1+d2=1。那么选择合适的权值，就能够使得重叠区 域实现平滑的过度。在重叠部分中， d1由 1渐渐过渡到 0，到由 0渐渐过渡到 1。通过这样的监渐进变化进行融 合，其公式为： 最后总结 Stitching函数不足之处：在拼接过程中 如遇到图像特征不明显，如一面墙的图 片，则无法采集到有用的特征点，在采 用此方法过程中会出现越界现象。 Thank you for your attention!