SURF算法分析.ppt

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