surf算法详解
SURF学习笔记
Speed-Up Robust Features(SURF)
SURF 是一种尺度，旋转不变的detector和descriptor.最大的特点是快！在快的基础上保证性能（repeatability,distinctiveness 和robustness）。
SURF采用有效策略的主要有：1）积分图（用于对图像卷积）2）detector是基于Hessian矩阵，descriptor是基于分布的
下面是SURF算法的具体实现：
1.兴趣点检测
SURF 对于兴趣点的检测是基于最基本的Hessian近似矩阵。
1.1积分图像
（由于不会在这里编辑公式，直接截图了）
PS：这里加一点自己的一点个人理解：关于矩形区域内像素点的求和应该是一种简单重复性运算，采用这种思路总体上提高了效率。为什么这么说呢？假设一幅图片共有n个像素点，则计算n个位置的积分图总共的加法运算有n-1次（注意：可不是
次哦，要充分利用递推思想），将这些结果保存在一个跟原图对应的矩阵M中。当需要计算图像中某个矩形区域内的所有像素之和是直接像查表一样，调出A,B,C,D四点的积分图值，简单的加减法（注意只需要三次哦）即可得到结果。反之，如果采用naive的方式直接在原图像
中的某个矩形区域内求和，你想想，总共可能的矩形组合有多少？！！且对于一幅图像n那是相当大啊，所以2^n
那可是天文数字，而且这里面绝大部分的矩形有重叠，重叠意味着什么？在算求和的时候有重复性的工作，其实我们是可以有效的利用已经计算过的信息的。这就是积分图法的内在思想：它实际上是先计算n个互不重叠（专业点说是不相交）的矩形区域内的像素点求和，充分利用这些值（已有值）计算未知值，有点类似递推的味道...这就完全避免了重复求和运算。
1.2 用于检测兴趣点的Hessian矩阵
作者Herbert Bay利用Hessian矩阵来检测兴趣点，具体是用Hessian矩阵行列式的最大值标记斑状结构（blob-like structure）的位置。同时，行列式值也作为尺度选择的依据，这里，作者是参考了Lindeberg的做法（'Feature detection with automatic scale selection'我还没有拜读原文！！）。
说一下Hessian矩阵的定义：
中得到启发，采用了盒子型滤波器（box filter）对上面的滤波器进行近似。盒子型滤波器见图1.3.
补充一点：filter的响应还要根据filter的大小做一个归一化。这样做就可以保证对于任意大小的filter其F范数是统一的（这对于尺度不变性是有必要的）。
有了前面的着一些准备工作，就可以对一幅图像I计算每个点的近似Hessian矩阵的行列式值，将这些值存储，备用！
1.3尺度空间表示
算法的尺度不变性主要靠不同尺度下寻找感兴趣点。谈到不同尺度就不得不说‘金字塔’。Lowe在其SIFT大作中是这样构造尺度空间的：对原图像不断地进行Gauss平滑+降采样。得到金字塔图像后，有进一步得到了DoG图，边和斑状结构就是通过DoG图得到其在原图的位置。
SURF中的做法与SIFT是有所不同的。SIFT算法在构造金字塔图层时Gauss滤波器大小
不变，改变的是图像的大小；而SURF则恰恰相反：图像大小保持不变，改变的是滤波器的大小。
PS：之所以这么做的目的考虑的主要目的还是效率问题（这样可以利用积分图有关的快速计算，用不同size的Mask进行卷积运算，复杂度是一样的，仅仅是三个加减法而已）。而且，由于没有对图像进行降采样，所以不存在混叠现象。
与SIFT类似，SURF的尺度空间也是按组（Octaves）划分的。每一个Octave里是对输入图像用size不断增加的filter进行滤波后得到的一系列响应。总的来说，一组包含了一个缩放因子2（）。每一组内的层数是一个常量。由于积分图像的离散特性（不懂），两个连续尺度间的最小尺度差分取决于二阶偏导在导数方向（x或y）上正的或负的波瓣（即不同的颜色块，见Fig.1.5）长度L0，实际中，L0设为filter边长的1/3。例如，对于9*9的filter，L0值为3.对于连续的level，采用的filter的size大小增加的最小量是2，以保证filter的边长始终是奇数，（奇数可以保证filter有中心点）。这样使得Mask以6个像素为单位进行扩充。
以图1.5，1.6为例对上面的叙述做一解释：图1.5左边是9*9大小y方向的二阶偏导计
算模板。Y方向共有3个波瓣（两正（白的），一负（黑的）），则的值即任意一个波瓣的宽度。右边是对每个波瓣各扩充2个像素后的filter，注意先是对波瓣扩充，即先扩宽，扩完后置于长怎么办，还没有搞懂.....貌似整体上最外的边（灰色的）是扩两个像素。
Fig.1.6
对于Fig.1.6左边是x-y方向的大小为9*9的filter，每个对角方向各有两个波瓣（2个黑的，2个白的），对波瓣扩两个像素，得到右边的filter。
尺度空间的构造具体对于第一组（Octave）而言开始所用的是大小为9*9的filter（最小的scale），接下来的filter大小依次为15*15，21*21，27*27，采用这些模板可以达到多于两个像素的尺度变化。作者说这么做是有必要的，原因是要对空域和相邻的尺度附近进行一个三维的非极大值抑制。（什么是非极大值抑制呢？字面意思：不是极大值就抑制。非极大值抑制通常用于边缘检测中边的进一步精简。举个简单例子，如果要从一些边缘中进一步提出水平边缘，那么就这么做：逐个检测边缘图中在水平方向的梯度值，如果不是局部极大值（非极大值），则就把该梯度值置0（抑制））。
由于要采用三维的非极大值抑制，那么Hessian响应图的首尾两个实际上是不包含极值信息的（这里跟SIFT算法里每一Octave里尽管有层，实际上只能利用中间的7层是一个
道理）。因此，经过内插后（后面会讲到），可能的最小的尺度应该是，
由于组之间较大尺度的变化（从9到15变化倍数是1.7）会带来较为粗糙的尺度采样，所以作者主张对尺度进行更为精细的采样来构造尺度空间。具体做法是：先用内插将图像大小加倍，然后用一个size为15的filter对加倍的图像进行滤波得到第一个Octave中的第一个响应图，随后用到的filter的size依次是21,27,33和39.第二组类似，只不过此时相邻的两个filter的size差为12个像素，是第一组的两倍。第三组...类似。这样，两个filter之间的尺度变化就会相对变小了（15到21变化倍数降为1.4：21/15）。
由于对任何size的filter，F范数模值是一个常量（？？？？）已经做了尺度上的归一化，所以对滤波器的响应不需要在加权了。
1.4 兴趣点的定位
作者采用的是在3*3*3的邻域内进行非极大值抑制。具体是采用了文章'Efficient Non- maxmum Supprerssion '中的做法（需要再进一步参考）。检测到的Hessian矩阵的行列式极大值还要在尺度和图像空间内做个内插，采用的方法可参见文章'Invatiant Features from Interest Point Groups'.之所以要做内插，是因为每一组（Octave）的第一层（layer）的尺度（scale）差分是很大的。
2 兴趣点描述和匹配
原文采用的descriptor跟SIFT类似也是基于兴趣点的邻域分布。具体是计算了x 和y方向上的Harr小波值分布（具体的Harr小波也要研究一下），而不是梯度值分布。这样做同样是因为可以借助积分图加速运算，同时只用了64维信息。同时，根据Laplacian 的符号，作者想出了一个新的indexing方法，既提高了鲁棒性，同时也加快了匹配过程。
2.1方向分配
为了具有方向不变性，作者为每个感兴趣点指定了一个可再复制（reproducible）的方向。做法如下：
①再以6s为半径的圆形邻域计算在x,y方向的Harr小波响应，这里s指的是所要检测的兴趣点所处的尺度。
②采样步长设为s,小波的size设为4s,(这样又可以利用积分图进行快速滤波了)
图2.1分别是用来计算x,y方向上响应的Haar小波滤波器。
2.2基于Haar小波响应的Descriptor
对于Descriptor的提取，第一步是构造一个中心点在兴趣点附近，带方向（方向即前面所估计的方向）的方框。方框的大小设为20s。方框具体形式课参考图2.3.
Fig.2.3 不同scale下的方框
这一步具体是怎样实现的呢？先把区域分成16个（4*4）子域。对每个子域我们计算25（5*5）个空间归一化的采样点的Haar小波响应。假定我们用dx表示水平方向上的Haar小波响应，dy表示垂直方向上的（滤波器的size为2s），这里可参考2.1.注意，这里的“水平”和“垂直”是相对于兴趣点的方向而言的（参见图2.4）。.为了增加鲁棒性，可对dx,dy，进行高斯
滤波(sigma=3.3s),滤波器中心为兴趣点。
Fig. 2.4
PS：通过图2.4进一步解释：左边大的方框即图2.3中的方框，将该大方框分成16块，每一小块如右图，又分为4个小快，这里的小块就是实际中descriptor的基本元，2.1节所提到的加法求和就是对这些元进行的，形式如图2.4右上角。
Fig.2.5的例子只是说采用四个量描述区域更加的具有区分度（more distinctive），置于有没有更好的表示形式呢？可以好好考虑一下（不过要结合算法的速度，复杂性综合考虑）。作者在这方面也是做了很多的实验，包括更多的和更少的小波特征，二阶偏导，高阶小波，PCA，中值，均值等等。总的来考虑上面的矢量表示形式得到的结果最好。同时，将大块区域分成16块也是最好的选择。分成9块的话结果差一些，但是在匹配时速度会更快，
而且跟其它的descripto r也是有可比性的。
2.3 快速建立索引用于匹配
前面说过，为了加速匹配过程，作者借助Laplacian（比如Hessian矩阵的迹）的符号使匹配过程索引加快。这样可以将下面的情况区分开（Fig.2.6）：
Fig.2.6
左右两幅图尽管contrast值是相同的，但符号不同，所以采用带符号的匹配，两者匹配
不成功。
PS:本文仅仅是把作者的论文算是翻译了一遍，还需要结合OpenCV里的SURF源码对某些细
节仔细研究https://www.sodocs.net/doc/ef14581155.html,e on!
图像匹配之surf算法
上面这段文字的大体意思就是说： SURF意指加速的具有鲁棒性的特征，由Bay在2006年首次提出，这项技术可以应用于计算机视觉的物体识别以及3D重构中。SURF算子由SIFT算子改进而来，一般来说，标准的SURF算子比SIFT算子快好几倍，并且在多幅图片下具有更好的鲁棒性。SURF最大的特征在于采用了harr特征以及积分图像integral image的概念，这大大加快了程序的运行时间。 surf提出算法参见http://www.vision.ee.ethz.ch/~surf/papers.html有paper下载地址。 1、提取特征点 2、提取特征描述符 1. 特征点的提取 1）利用Hessian矩阵，计算特征值α 其中Lxx(x, σ)是高斯滤波后图像g(σ)的在x方向的二阶导数,其他的Lyy(x, σ)、Lxy(x, σ)都是g(σ)的二阶导数。为了减小计算量，原文使用了一个简单的方法，并利用了积分图像的优势（大大的减少计算量），方法其实很简单就是在模糊的基础上将原本的模块近似下。 总所周知，一般计算图像的二阶导时，利用下面的公式 d2f(x)/dx2=(f(x+1)-f(x))-(f(x)-f(x-1))=-2*f(x)+f(x+1)+f(x-1)。但是f(x)=g(h(x))【h(x)为图像的灰度值，f(x)
是将h(x)高斯滤波处理的灰度函数】 图一模板近似 以9X9滤波器为例，如上图所示，左边两幅图分别为灰度图像在中心点（黑色点）处的二阶导数d2f(x)/dx2和 d2f(x)/dxdy的模板对应的值, 近似后变成右边的两幅图，图中灰色部分像素值为0。可是这样计算特征值不是也很复杂么？当然，所以作者提供了一种新思路--使用积分图像。 积分图像，顾名思义，即指当前像素点所在位置距原点（0,0）所包围面的所有灰度之和。 绿色的部分为当前像素点，红色为积分区域。 这样计算图像中任意一块矩形区域的灰度之和Sx只需要利用矩形4个顶点(Xi,Yi)(i=1,2,3,4 顺序为从上之下，先左后右)的积分值S（x,y）即可。 Sx=S(X1,Y1)+S(X4,Y4)-S(X2,Y2)-S(X3,Y3) 至此，大家应该知道近似二阶导数的高斯模板并引入积分图像的好处了吧，只需要在函数定义之前计算各个坐标点的积分图像，然后就能方便的求出hessian的特征值。 不过由于函数模板的近似，这里需要修正下特征值α的求解公式： 这里Dxx和Dxy就是根据图一得到的，而Dyy和Dxx类似，只需要导致一下模板即可。 2）根据是否为领域极大值判断特征点
视觉里程计原理(一)特征提取(SURF算法)
MPIG Seminar0045 Feature Extraction 陈伟杰 Machine Perception and Interaction Group (MPIG) https://www.sodocs.net/doc/ef14581155.html, cwj@https://www.sodocs.net/doc/ef14581155.html,
Feature Extraction Refined based on the book: Mastering OpenCV with Practical Computer Vision Projects_full.pdf and Bay H, Tuytelaars T, Van Gool L. Surf: Speeded up robust features [M]. Computer vision–ECCV 2006. Springer. 2006: 404-417.
or F for [R|t]Drawing path The main steps of Visual Odometry images parameters Feature Extraction Feature matching Compute E
First Feature Extraction What feature is? Characteristics can be easily identified in images Edges Corners Blobs lines points
Harris SIFT SURF Commonly used algorithm: ?Corner extractor ?Fast operation ?Poor resolution ?Not applicable when scale changes ?Blobs extractor ?Slow operation ?Good resolution ?Scale invariance ?Upgrade from SIFT ?Speed up ?More robust
SURF算法
SURF算法 SURF是一种尺度、旋转不变的detector和descriptor。最大的特点是快！在快的基础上保证性能（repeatability,distinctiveness 和robustness）。 SURF采用有效策略的主要有：1）积分图像（用于对图像卷积）2）detector 是基于Hessian矩阵，descriptor是基于分布的。 下面是SURF算法的具体实现： 1.兴趣点检测 SURF对于兴趣点的检测是基于最基本的Hessian近似矩阵。 1.1积分图像
1.2 用于检测兴趣点的Hessian矩阵 中得到启发，采用了盒子型滤波器（box filter）对上面的滤波器进行近似。盒子型滤波器见图1.3.
再根据filter的大小做一个归一化。这对于尺度不变性是有必要的。 有了前面的着一些准备工作，就可以对一幅图像I计算每个点的近似Hessian矩阵的行列式值，将这些值存储，备用！ 1.3尺度空间表示 算法的尺度不变性主要靠不同尺度下寻找感兴趣点。谈到不同尺度就不得不说‘金字塔’。Lowe在其SIFT大作中是这样构造尺度空间的：对原图像不断地进行Gauss平滑+降采样。得到金字塔图像后，又进一步得到了DOG图，边和斑状结构就是通过DOG图得到其在原图的位置。SURF中的做法与SIFT是有所不同的。SIFT算法在构造金字塔图层时Gauss滤波器大小不变，改变的是图像的大小；而SURF则恰恰相反：图像大小保持不变，改变的是滤波器的大小。 之所以这么做的目的考虑的主要目的还是效率问题（这样可以利用积分图有关的快速计算，用不同size的Mask进行卷积运算，复杂度是一样的，仅仅是三个加减法而已）。而且，由于没有对图像进行降采样，所以不存在混叠现象。 与SIFT类似，SURF的尺度空间也是按组（Octaves）划分的。每一个Octave 里是对输入图像用size不断增加的filter进行滤波后得到的一系列响应。总的来说，一组包含了一个缩放因子。每一组内的层数是一个常量。
SURF算法介绍
蒙娜丽莎的图像匹配---SURF算法 1.图像匹配 1.1.图像匹配的概念 图像匹配成为计算机视觉和图像处理中的一个重要技术。其方法思想就是根据己知的图像在其他图像中查找出含有己知图像的过程。图像匹配的架构流程如图1.1。该技术的研究涉及到许多相关的知识领域,如图像预处理、图像采样、特征提取等,同时将计算机视觉、多维信号处理和数值计算等紧密结合在一起。图像匹配技术还与图像融合、图像匹配等研究方向系系相关,为图像理解和图像复原等相关领域的研究提供基础。 图1.1 图像匹配流程图 图像匹配技术作为图像处理的关键技术之一，在国防领域和医学领域等得到广泛的研究和应用[2]。如果在不同视角，或是不同时间，或是使用了不同的传感器获取到的两幅或多幅图像间存在共同区域，如何寻找到图像间的共同区域，就是图像匹配需要解决的问题。 1.2.图像匹配的算法组成 图像匹配技术的分支很多，对图像匹配提出的构架也是千姿百态，根据布朗提出了图像匹配的组成要素，将图像匹配的要素主要分为四个方面，分别是图像的特征空间，为求取变换参数定义的搜索空间和搜索策略，图像匹配的相似性度量。 特征空间是指在待配图像和参考图像上提取到的一系列特征集合。将提取到的特征进行描述后参与最后的匹配，因此特征选取的好坏直接影响匹配的可行性和匹配的效果。好的特征是满足自动匹配的前提，因此选取的特征一般包含图像的关键信息，此类特征存在以下特性：首先，此类特征具有公有性、唯一性和显著性，保证匹配的顺利进行和匹配的精度；其次，此类特征具有多量性，而且分布合理，保证匹配的稳定性。合理的特征空间会降低匹配算法的计算量，提高算法的性能。 相似性度量是指评判待匹配图像和参考图像上特征的相似程度，它很大程度上决定了参与匹配的因素，一般采用某种代价函数或者是距离函数来进行度量。好的相似性度量不仅可以减少算法的计算量，而且对于算法的匹配性能和鲁棒性起着重要的作用。 搜索空间为求取图像变换参数的空间。它为图像间可能存在的所有变换组合的空间。搜索空间的组成取决于图像畸变的类型，而搜索空间的取值围取决于图像畸变的强度。假如图像间只存在平移和旋转变换，那么搜索空间为简单的二维
Surf算法流程
一、原理： Sift算法的优点是特征稳定，对旋转、尺度变换、亮度保持不变性，对视角变换、噪声也有一定程度的稳定性；缺点是实时性不高，并且对于边缘光滑目标的特征点提取能力较弱。 Surf（Speeded Up Robust Features）改进了特征的提取和描述方式，用一种更为高效的方式完成特征的提取和描述。 二、Surf实现流程如下： 1. 构建Hessian（黑塞矩阵），生成所有的兴趣点，用于特征的提取 黑塞矩阵（Hessian Matrix）是一个多元函数的二阶偏导数构成的方阵，描述了函数的局部曲率。由德国数学家Ludwin Otto Hessian于19世纪提出。 surf构造的金字塔图像与sift有很大不同，Sift采用的是DOG图像，而surf采用的是Hessian矩阵行列式近似值图像。Hessian矩阵是Surf算法的核心，构建Hessian矩阵的目的是为了生成图像稳定的边缘点（突变点），为下文的特征提取做好基础。 每一个像素点都可以求出一个Hessian矩阵。 Hessian矩阵的判别式为： 当Hessian矩阵的判别式取得局部极大值时，判定当前点是比周围邻域内其他点更亮或更暗的点，由此来定位关键点的位置。 在SURF算法中，图像像素l(x，y)即为函数值f(x，y)。但是由于我们的特征点需要具备尺度无关性，所以在进行Hessian 矩阵构造前，需要对其进行高斯滤波，选用二阶标准高斯函数作为滤波器。 通过特定核间的卷积计算二阶偏导数。通过特定核间的卷积计算二阶偏导数，这样便能计算出H矩阵的三个矩阵元素L_xx, L_xy, L_yy从而计算出H矩阵： 由于高斯核是服从正态分布的，从中心点往外，系数越来越低，为了提高运算速度，Surf使用了盒式滤波器来近似替代高斯滤波器，提高运算速度。 盒式滤波器（Boxfilter）对图像的滤波转化成计算图像上不同区域间像素和的加减运算问题，只需要简单几次查找积分图就可以完成。 每个像素的Hessian矩阵行列式的近似值： 在Dxy上乘了一个加权系数0.9，目的是为了平衡因使用盒式滤波器近似所带来的误差： 2. 构建尺度空间 同Sift一样，Surf的尺度空间也是由O组L层组成，不同的是，Sift中下一组图像的尺寸是上一组的一半，同一组间图像尺寸一样，但是所使用的高斯模糊系数逐渐增大；而在Surf中，不同组间图像的尺寸都是一致的，但不同组间使用的
C#+EmguCV实现SURF算法
C#+EmguCV中SURF算法的实现 EmguCV的官方网站上的例子中，有SURF算法的实现，其实现的时候利用的GPU的加速，看着比较复杂。此外，官网上例子的实现并没有做界面，看着不舒服，加载图片也不是很方便，因此，为了学习，我将官网上的例子进行了修改，去掉了GPU加速的部分，然后在做了显示界面，操作起来更友好些。 我是在Vs2012下使用2.9 Alpha版本的EmgucV做的。 首先显示界面如下图所示，显示界面是两个窗体，第一个如下： 窗体上有两个PictureBox控件，一个用来显示待匹配的源图像，一个用来显示匹配的目标图像。 然后相对应的有三个Button控件，第一个用来打开源图像，第二个用来打开目标图像，第三个用来匹配，当点击第三个Button控件实现匹配，匹配的图像显示在新的窗体上，新的窗体很简单，就一个窗体，图像我们使用窗体的Paint 事件绘制在上面，第二个窗体如下：
其中button1实现的是打开源图像，代码如下： private void buttonSrc_Click(object sender, EventArgs e) { //Create open dialog; OpenFileDialog opnDlg = new OpenFileDialog(); opnDlg.Filter = "All Image files|*.bmp;*.gif;*.jpg;*.ico;*png"; //Seting the title of dialog; opnDlg.Title = "Open Src image files"; opnDlg.ShowHelp = true; if (opnDlg.ShowDialog() == DialogResult.OK) { curFileNameSrc = opnDlg.FileName; try { curBitmapSrc = new Bitmap(curFileNameSrc); pictureBoxSrc.Image = curBitmapSrc; } catch { MessageBox.Show("programe error");
surf算法详解
SURF学习笔记 Speed-Up Robust Features(SURF) SURF 是一种尺度，旋转不变的detector和descriptor.最大的特点是快！在快的基础上保证性能（repeatability,distinctiveness 和robustness）。 SURF采用有效策略的主要有：1）积分图（用于对图像卷积）2）detector是基于Hessian矩阵，descriptor是基于分布的 下面是SURF算法的具体实现： 1.兴趣点检测 SURF 对于兴趣点的检测是基于最基本的Hessian近似矩阵。 1.1积分图像 （由于不会在这里编辑公式，直接截图了）
PS：这里加一点自己的一点个人理解：关于矩形区域内像素点的求和应该是一种简单重复性运算，采用这种思路总体上提高了效率。为什么这么说呢？假设一幅图片共有n个像素点，则计算n个位置的积分图总共的加法运算有n-1次（注意：可不是 次哦，要充分利用递推思想），将这些结果保存在一个跟原图对应的矩阵M中。当需要计算图像中某个矩形区域内的所有像素之和是直接像查表一样，调出A,B,C,D四点的积分图值，简单的加减法（注意只需要三次哦）即可得到结果。反之，如果采用naive的方式直接在原图像 中的某个矩形区域内求和，你想想，总共可能的矩形组合有多少？！！且对于一幅图像n那是相当大啊，所以2^n 那可是天文数字，而且这里面绝大部分的矩形有重叠，重叠意味着什么？在算求和的时候有重复性的工作，其实我们是可以有效的利用已经计算过的信息的。这就是积分图法的内在思想：它实际上是先计算n个互不重叠（专业点说是不相交）的矩形区域内的像素点求和，充分利用这些值（已有值）计算未知值，有点类似递推的味道...这就完全避免了重复求和运算。 1.2 用于检测兴趣点的Hessian矩阵 作者Herbert Bay利用Hessian矩阵来检测兴趣点，具体是用Hessian矩阵行列式的最大值标记斑状结构（blob-like structure）的位置。同时，行列式值也作为尺度选择的依据，这里，作者是参考了Lindeberg的做法（'Feature detection with automatic scale selection'我还没有拜读原文！！）。 说一下Hessian矩阵的定义：