SURF算法分析

用stitching算法进行图像拼接•第一部分：用surf算法提取特征点•第二部分：特征点匹配•第三部分：构建透视矩阵完成拼接•第四部分:图像融合1.SURF介绍SURF(SpeededUpRobustFeature)是一种高鲁棒性的局部特征点检测器。由HerbertBay等人在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.91.4构建金字塔构建尺度空间由于采用的盒子滤波和积分图像，不需要像SIFT算法那样去直接建立金字塔图像，而是采用不断增大的盒子滤波模板的尺寸的间接方法。通过不同尺寸盒子滤波模板和积分图像求取Hessian矩阵行列式的响应图像，然后，在响应图像上采用3D非最大值抑制，求取各种不同尺度的斑点。SIFT构建尺度空间SURF构建尺度空间模板图片1.5构建尺度空间构建尺度空间与SIFT相类似，SURF也将尺度空间划分成若干组(Octaves)。一个组代表了逐步放大的滤波模板对同一个输入图像进行滤波的一系列响应图像。每一组又有若干固定的层组成。915212715273951275175995199147195变化量n*6变化量6*nScaleOctaves1.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函数不足之处：在拼接过程中如遇到图像特征不明显，如一面墙的图片，则无法采集到有用的特征点，在采用此方法过程中会出现越界现象。•Thankyouforyourattention!