SURF特征提取算法原文翻译与理解（上）
SURF的优点以及与其他特征提取算法的比较前面总结过了，而且通过实际的使用发现算法的稳定性着实很好，这里分享一下对Speeded Up Robust Features原文的翻译和理解，文章是去年翻译的，那时候刚开始看特征提取所以翻译的比较细，才疏学浅，有的地方可能理解的不对，欢迎大家拍砖。分成两部分，第一部分是特征点的提取，第二部分是特征点的描述，以及整个方法的总结。正文开始：
1.引言
文章提出一种具有尺度和旋转不变性特点的特征点提取和描述方法，称作SURF算法。该算法对比与当前的算法具有相似甚至更好的可重复性、鲁棒性，并且计算的更快。具体实现:先使用积分图来计算卷积；然后使用Hessian响应来衡量某点是否为特征点，并创建描述子来描述该特征；以及对整个流程进行一定的优化。以上流程就得到了关于特征提取、描述和匹配的一整套的步骤。本文最后附上使用通用评价集的实验结果。
在左右两幅图中寻找对应的点是个重要的环节。匹配点对的寻找可以分为三个步骤：1.找到兴趣点，这些兴趣点是有特色的（便于区分），评价一个寻找兴趣点的算法优劣的重要指标是它的可重复性；2.每个兴趣点的邻域点能使用特征向量（描述子）来表达，这个特征向量要对噪声有鲁棒性；3.特征向量在不同图像中进行匹配，这个匹配一般是基于距离的，比如马氏距离或欧氏距离，且特征向量的维度和计算时间非常相关，维度小的特征向量更好。
目标是找到一种特征的检测和描述方法，这种方法要求计算速度快，但是还要保持性能性能。为了实现这个目标，就要在性能和速度之间取一个平衡，既降低描述子的维度，又要保证足够的区分度。
2.现有研究
2.1兴趣点检测
使用最广泛的兴趣点检测算子是Harris角点检测算子（Harris算子对于L型角点检测精度高，稳定性好，但是角点信息有丢失和偏移的情况，且角点提取有聚簇现象），但其不具有尺度不变性。（尺度不变性的意义：当分析未知场景时，计算机无法预知物体的尺度，因此需要同时考虑图像在多尺度下的描述。比如在Harry特征检测人脸时，因为并不知道人脸的尺寸，所以需要生成一个不同大小的图像构成的金字塔，扫描其中的每一副图像来寻找可能的人脸。）后面这段研究现状就不翻译了，再翻译就真是献丑了。
通过对现有的兴趣点检测算法的比较，可以得到结论：1.Hessian矩阵相比于基于Harris的方法，具有更加稳定和可重复性更强的特点；2.使用一些近似方法，比如DoG等方法，可以提高速度，又不至于造成较大的精度损失，这就说明近似计算的可行性。
2.2特征描述子
SIFT算子区分性比较好，但是它的描述子维度很高，因此匹配环节非常耗时，如果用在普通计算机实时性场合，难以满足要求。有的研究采取措施降低匹配的耗时，但是会损失精度。
2.3本文的方法
本文提出的方法基于Hessian矩阵，然后使用非常基础的近似方法，然后使用积分图来降低运算量。本方法的描述子是基于兴趣点的邻域内点的Harr-小波响应（下面会细讲）。最后得到的特征点的描述向量，维度是64，可以大大降低匹配时间。为了使文章的理论更自足，文章还将简单的介绍积分图的概念。
3.基于Hessian响应的特征检测算子
对于图像中某点X=(x,y)，下面的公式H(X,σ)代表在X点的σ尺度下的Hessian矩阵。其中Hessian矩阵的四项分别代表高斯二阶微分IxxIyyIxy与图像I的对应点进行卷积得到的结果。注意σ代表尺度系数，其含义下面还会讲，一个点会有多个σ值下的Hessian矩阵。
高斯滤波器可以用在不同尺度下的分析中，实践中要求先对高斯二阶微分进行离散化和截断再使用。但是即使是用了高斯滤波器，当图像进行降采样时，仍然会发生混淆的情况。高斯滤波器的另外一个问题是，当进行降采样时，并不会出现新的特征，因此，高斯滤波器的重要性就没那么明显了，而它速度又不快，所以考虑使用另外的滤波器来近似这个高斯滤波器。而Lowe成功的使用DoG来近似LoG，这也给了作者启发，作者使用更进一步的近似方法，即盒滤波器。
如图1的左边的两幅图，是对高斯二阶微分yy和xy离散化得到的LyyLxy，通过盒滤波器近似后得到右边的结果记为DyyDxy，可以看出，把高斯二阶微分滤波器使用盒滤波器来近似，也就是相当于把高斯滤波器进一步的只分成几块，这样下一步可以使用积分图进行快速计算，而后面的结果也证明，这么做的检测效果并没有太大的损失，但时间大大提升了。
这就是说Hessian矩阵的求法，本来是需要与高斯二阶微分进行卷积，现在近似成与盒滤波器进行卷积。
本来是根据Hessian矩阵的判别式来判断某点是否为特征点，现在Hessian已经做了近似，那么Hessian的计算也就要做相应的变换推导，重新推导得到Hessian矩阵的行列式的公式为公式2，此时就需要根据盒滤波器得到的DxxDxyDyy。
此外，filter响应还要根据滤波器的尺寸进行归一化处理，以保证不同滤波器下Hessian矩阵的F范数相同。
由于特征点需要具有尺度不变性，所以要进行多尺度下的计算。多尺度计算常见的方式是图像金字塔。一般来说，大多数人的方法是使用同样的滤波器对图像进行高斯平滑，然后对图像降采样，得到金字塔中上一层的图，然后不断进行。但是SURF算法为了使用盒子滤波器和积分图像，采用的方法是不改变图像大小，每次加大滤波器核的大小，这个措施保证了速度进一步提升。
关于滤波器的尺寸的分多少情况，是先按组（也就是有几组金字塔），每组内又分层，滤波器尺寸大小=(2ctave*interval+1)*3,其中octave是组号，interval是组内的层号，也就是第1组的第1层尺寸为9*9，第1组第2层尺寸为15*15；第2组第1层尺寸为15，第2组第2层尺寸为27，即每组的组内各层的尺寸间隔组加倍。
改变了每层的滤波器的尺寸以后，对应的尺度系数s也要更改，该系数与高斯二阶微分的系数σ是同一个。怎么改呢，9*9对应s=1.2，则27*27对应s=1.2*3，成比例增加。也就是说，不同的层数下，滤波器的尺寸不同，σ也不同，这样就生成不同的高斯滤波器。
完成以上的步骤后，就可以求出Hessian矩阵的判别式，也叫Hessian响应。对于某个点，可以得到它在很多个层上面的Hessian响应值，那么哪一个才能代表这个点呢？对于某一组，其内部分成几层，也就是一个图像金字塔，如果某点的Hessian响应在其同层的8邻域点以及上一层和下一层的各9个点，即一共26个三维邻域点内，属于最大或者最小，那么该点就是该区域内的特征点。（这一点论文里面没写，我是参考《OpenCV编程入门》自己理解的，不知道对不对）。
最后，对于得到的Hessian响应，当达到设定的阈值时，就确定这个点为特征点，这就完成了特征点的检测，接下来的步骤就是特征点的描述。