为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划surf算法学习心得(一)算法原理SURF学习笔记Speed-UpRobustFeatures(SURF)SURF是一种尺度，旋转不变的detector和descriptor.最大的特点是快！在快的基础上保证性能。SURF采用有效策略的主要有：1）积分图2）detector是基于Hessian矩阵，descriptor是基于分布的下面是SURF算法的具体实现：1.兴趣点检测SURF对于兴趣点的检测是基于最基本的Hessian近似矩阵。积分图像PS：这里加一点自己的一点个人理解：关于矩形区域内像素点的求和应该是一种简单重复性运算，采用这种思路总体上提高了效率。为什么这么说呢？假设一幅图片共有n个像素点，则计算n个位置的积分图总共的加法运算有n-1次，将这些结果保存在一个跟原图对应的矩阵M中。当需要计算图像中某个矩形区域内的所有像素之和是直接像查表一样，调出A,B,C,D四点的积分图值，简单的加减法即可得到结果。反之，如果采用naive的方式直接在原图像中的某个矩形区域内求和，你想想，总共可能的矩形组合有多少？！且对于一幅图像n那是相当大啊，所以2n那可是天文数字，而且这里面绝大部分的矩形有重叠，重叠意味着什么？在算求和的时候有重复性的工作，其实我们是可以有效的利用已经计算过的信息的。这就是积分图法的内在思想：它实际上是先计算n个互不重叠的矩形区域内的像素点求和，充分利用这些值计算未知值，有点类似递推的味道.这就完全避免了重复求和运算。用于检测兴趣点的Hessian矩阵作者HerbertBay利用Hessian矩阵来检测兴趣点，具体是用Hessian矩阵行列式的最大值标记斑状结构的位置。同时，行列式值也作为尺度选择的依据，这里，作者是参考了Lindeberg的做法。说一下Hessian矩阵的定义：中得到启发，采用了盒子型滤波器对上面的滤波器进行近似。盒子型滤波器见图补充一点：filter的响应还要根据filter的大小做一个归一化。这样做就可以保证对于任意大小的filter其F范数是统一的。有了前面的着一些准备工作，就可以对一幅图像I计算每个点的近似Hessian矩阵的行列式值，将这些值存储，备用！尺度空间表示算法的尺度不变性主要靠不同尺度下寻找感兴趣点。谈到不同尺度就不得不说金字塔。Lowe在其SIFT大作中是这样构造尺度空间的：对原图像不断地进行Gauss平滑+降采样。得到金字塔图像后，有进一步得到了DoG图，边和斑状结构就是通过DoG图得到其在原图的位置。SURF中的做法与SIFT是有所不同的。SIFT算法在构造金字塔图层时Gauss滤波器大小不变，改变的是图像的大小；而SURF则恰恰相反：图像大小保持不变，改变的是滤波器的大小。PS：之所以这么做的目的考虑的主要目的还是效率问题。而且，由于没有对图像进行降采样，所以不存在混叠现象。与SIFT类似，SURF的尺度空间也是按组划分的。每一个Octave里是对输入图像用size不断增加的filter进行滤波后得到的一系列响应。总的来说，一组包含了一个缩放因子2。每一组内的层数是一个常量。由于积分图像的离散特性，两个连续尺度间的最小尺度差分取决于二阶偏导在导数方向上正的或负的波瓣长度L0，实际中，L0设为filter边长的1/3。例如，对于9*9的filter，L0值为3.对于连续的level，采用的filter的size大小增加的最小量是2，以保证filter的边长始终是奇数，。这样使得Mask以6个像素为单位进行扩充。以图，为例对上面的叙述做一解释：图左边是9*9大小y方向的二阶偏导计算模板。Y方向共有3个波瓣，一负），则的值即任意一个波瓣的宽度。右边是对每个波瓣各扩充2个像素后的filter，注意先是对波瓣扩充，即先扩宽，扩完后置于长怎么办，还没有搞懂.貌似整体上最外的边是扩两个像素。SURF特征提取分析背景引言计算机视觉中，引入尺度不变的特征，主要的思想是每个检测到的特征点都伴随着对应的尺寸因子。当我们想匹配不同图像时，经常会遇到图像尺度不同的问题，不同图像中特征点的距离变得不同，物体变成不同的尺寸，如果我们通过修正特征点的大小，就会造成强度不匹配。为了解决这个问题，提出一个尺度不变的SURF特征检测，在计算特征点的时候把尺度因素加入之中。SURF与SIFT算法相似，SIFT算法比较稳定，检测特征点更多，但是复杂度较高，而SURF要运算简单，效率高，运算时间短一点。相关SIFT算法请详见博文【图像分析】尺度不变特征变换(SIFT)特征提取分析。本节介绍SURF算法相关知识。基本介绍首先，我们引用3中对SURF描述为：“SURF(SpeededUpRobustFeatures)isarobustlocalfeaturedetector,firstpresentedbyHerbertBayetal.inXX,thatcanbeusedincomputervisiontaskslikeobjectrecognitionor3Dreconstruction.ItispartlyinspiredbytheSIFTstandardversionofSURFisseveraltimesfasterthanSIFTandclaimedbyitsauthorstobemorerobustagainstdifferentimagetransformationsthanSIFT.SURFisbasedonsumsof2DHaarwaveletresponsesandmakesanefficientuseofintegralusesanintegerapproximationtothedeterminantofHessianblobdetector,whichcanbecomputedextremelyquicklywithanintegralimage(3integeroperations).Forfeatures,itusesthesumoftheHaarwaveletresponsearoundthepointofinterest.Again,thesecanbecomputedwiththeaidoftheintegralimage.从上述对SURF描述，可知：第一、SURF算法是对SIFT算法加强版，同时加速的具有鲁棒性的特征。第二、标准的SURF算子比SIFT算子快好几倍，并且在多幅图片下具有更好的鲁棒性。SURF最大的特征在于采用了harr特征以及积分图像integralimage的概念，这大大加快了程序的运行时间。算法描述为了实现尺度不变性的特征点检测与匹配，SURF算法则先利用Hessian矩阵确定候选点，然后进行非极大抑制，计算复杂度降低多了。整个算法由以下几个部分组成。黑森矩阵构建我们知道：SIFT算法建立一幅图像的金字塔，在每一层进行高斯滤波并求取图像差(DOG)进行特征点的提取，而SURF则用的是HessianMatrix进行特征点的提取，所以黑森矩阵是SURF算法的核心。假设函数f(x,y)，Hessian矩阵H是由函数偏导数组成。首先来看看图像中某个像素点的HessianMatrix的定义为：从而每一个像素点都可以求出一个HessianMatrix.Hessian矩阵判别式为：判别式的值是H矩阵的特征值，可以利用判定结果的符号将所有点分类，根据判别式取值正负，从来判别该点是或不是极点的值。在SURF算法中，通常用图像像素I(x,y)取代函数值f(x,y)。然后选用二阶标准高斯函数作为滤波器。通过特定核间的卷积计算二阶偏导数，这样便能计算出H矩阵的三个矩阵元素Lxx,Lxy,Lyy，从而计算出H矩阵公式如下：但是由于我们的特征点需要尺度无关性，所以在进行Hessian矩阵构造前，需要对其进行高斯滤波。这样，经过滤波后在进行Hessian的计算，其公式如下：L(x,t)是一幅图像在不同解析度下的表示，可以利用高斯核G(t)与图像函数I(x)在点x的卷积来实现，其中高斯核G(t)为：其中g(t)为高斯函数，t为高斯方差。通过这种方法可以为图像中每个像素计算出其H矩阵的决定值，并用这个值来判别特征点。为此HerbertBay提出用近似值现代替L(x,t)。为平衡准确值与近似值间的误差引入权值。权值随尺度变化，则H矩阵判别式可表示为：其中为何式中呢.请详见1。因求Hessian时要先高斯平滑，然后求其二阶导数，这在离散的像素是用模板卷积形成的。这比如说y方向上的模板Fig1(a)和Fig1(c).Fig1(a)即用高斯平滑后在y方向上求二阶导数的模板。为了加快运算用了近似处理，其处理结果如Fig1(b)所示，这样就简化了很多。并且可以采用积分图来运算，大大的加快了速度。同理，x和y方向的二阶混合偏导模板Fig1(b)与Fig1(d)。2.尺度空间生成图像的尺度空间是这幅图像在不同解析度下的表示。上面讲的这么多只是得到了一张近似Hessian行列式图，这类似SIFT中的DOG图，但是在金字塔图像中分为很多层，每一层叫做一个octave，每一个octave中又有几张尺度不同的图片。在SIFT算法中，同一个octave层中的图片尺寸(即大小)相同，但是尺度(即模糊程度)不同，而不同的octave层中的图片尺寸大小也不相同，因为它是由上一层图片降采样得到的。在进行高斯模糊时，SIFT的高斯模板大小是始终不变的，只是在不同的octave之间改变图片的大小。而在SURF中，图片的大小是一直不变的，不同的octave层得到的待检测图片是改变高斯模糊尺寸大小得到的，当然了，同一个octave中个的图片用到的高斯模板尺度也不同。算法允许尺度空间多层图像同时被处理，不需对图像进行二次抽样，从而提高算法性能。上图左边是传统方式建立一个如图所示的金字塔结构，图像的寸是变化的，并且运算会反复使用高斯函数对子层进行平滑处理，上图右边说明SURF算法使原始图像保持不变而只改变滤波器大小。SURF采用这种方法节省了降采样过程，其处理速度自然也就提上去了(注：上图片来自于网络)。3.利用非极大值抑制初步确定特征点和精确定位特征点将经过hessian矩阵处理过的每个像素点与其3维领域的26个点进行大小比较，如果它是这26个点中的最大值或者最小值，则保留下来，当做初步的特征点。检测过程中使用与该尺度层图像解析度相对应大小的滤波器进行检测，以33的滤波器为例，该尺度层图像中9个像素点之一.如下图中检测特征点与自身尺度层中其余8个点和在其之上及之下的两个尺度层9个点进行比较，共26个点，图中标记?x?的像素点的特征值若大于周围像素则可确定该点为该区域的特征点。然后，采用3维线性插值法得到亚像素级的特征点，同时也去掉那些值小于一定阈值的点，增加极值使检测到的特征点数量减少，最终只有几个特征最强点会被检测出来。4.选取特征点主方向确定为了保证旋转不变性，在SURF中，不统计其梯度直方图，而是统计特征点领域内的Harr小波特征。即以特征点为中心，计算半径为6s(S为特征点所在的尺度值)的邻域内，统计60度扇形内所有点在x(水平)和y(垂直)方向的Haar小波响应总和(Haar小波边长取4s)，并给这些响应值赋高斯权重系数，使得靠近特征点的响应贡献大，而远离特征点的响应贡献小，然后60度范围内的响应相加以形成新的矢量，遍历整个圆形区