反复将Speed-up Robust Feature 这篇文章看了几遍，现在总算是拨开迷雾了，索性赶紧记录一下~~

SURF，一种能进行特征检测与描述的方法，其主要的创新点在于基于积分图进行盒式滤波，相比于传统的滤波方式，其计算量可以独立于滤波器的尺寸，这一思想在论文中有两处体现，一是构建尺度空间金字塔时，保持原始图像的尺寸不变，只改变滤波器的尺寸，用于特征点的检测；二是在进行Haar wavelet的时候，也是基于积分图进行卷积，用于形成特征描述子。需要注意的是，之所以可以在积分图的基础上进行卷积操作，这与滤波器的类型有关，也就是滤波其需要是盒式滤波器，如图1，2所示这类滤波其，这样在计算时则只需利用各个顶点进行两次减法和一次加法再后再乘上对应的系数即可。这种方式极大地提升了算法的运行效率。

图1，（左）用对应积分图上的八个点，（右）用对应区域的四个点计算后再相加即可得出对应区域积分的结果

图2，用对应积分图上的六个点即可得出对应区域积分的结果

下面具体来说明SURF从特征点检测到描述子形成以及快速匹配的具体方法:

1、特征点检测：

文章利用每个像素点Hessian矩阵对应的行列式的值作为每个像素点的强度响应值大小，像素点的Hessian矩阵表示如下：

图3 Hessian矩阵

可以看到，每个点的Hessian矩阵取决于利用对应尺度sigma进行二阶高斯卷积（Laplacian卷积）操作后各个方向上的值构成，但是gaussian卷积的缺点在于在构建尺度空间时不够鲁棒，为此作者进行了一个近似用盒式滤波器（如图1）来代替二阶高斯滤波器（如图4）：

图4 高斯二阶滤波器

之后利用该滤波器对原图像（灰度图像）进行卷积操作，以构建尺度空间金字塔，其构建方式为：只改变滤波器的尺寸，原图像尺寸不变，不同于SIFT中尺度空间的构建方式，即：下层的输出结果需要依赖上层的图像，SURF的这种方式可以很好地实现并行化操作，即每张图像的操作可以同时进行，以此极大地提升效率。如图5所示：

图5 SIFT与SURF尺度空间构建图

同SIFT类似，该尺度空间也分为若干octave，每个octave中有若干层，需要注意的是，每个octave中的实际层数为原有层数+2，用于在进行上下层极值的比较，这与SIFT中的+3是同一个思想。同时，为了加速，不同组滤波时的步伐间隔的关系可以设置为2倍的关系，即第一个octave的step=1，第二个octave的step=2，第三个octave的step=4……，每个octave中每层的step相同。每一层的box filter的尺寸的关系为：

每个size下对应与Gaussian卷积中的一个sigma，其对应关系为：1.2x（L/9）,其中L为滤波器的size，故有9x9对应的s=1.2; 如下图6所示：

图6

分别利用x，y和xy三个方向的盒式滤波器进行卷积后，即可得到该点对应的Hessian矩阵，由此可以求出该Hessian矩阵对应的行列式作为该像素点的响应值：

之所以有0.9这个系数，是为了平衡盒式滤波近似带来的误差。

需要说明的时，随着octave的增加，越高层次的octave其能检测得到的特征点数会明显减少。

构建完成尺度空间金字塔后，与SIFT中队DoG结构进行相邻三层的局部非极大值抑制相同，比较某点上下相邻的26个点的Hessian行列式的值，若该点的值大于一个阈值且是局部最大值，则该点为特征点。

2、特征点描述子生成

在SIFT中，是通过统计特征点邻域的梯度信息来得到特征点的向量描述子，在SURF中则是通过Haar小波的方式得到x，y方向上的信息进行统计。

特征点主方向确定：首先，以特征点为中心，以6s为半径（s为该特征点所在曾的scale）的区域为该特征点的邻域，以s为滤波步伐，通过Haar小波滤波器（长度为4s）（如图2）在积分图上进行卷积操作，之后以特征点为中心，为了增加鲁棒性，利用Gaussian滤波（sigma=2s）确定每个点所对应的权重。之后，以某一角度（默认为pi/3）的扇形区域，计算各点Harr小波dx，dy之和作为该扇形区域内的方向，以这个角度的扇形区域为窗口对整个原型区域进行扫描，得到对应窗口下的方向，则特征点的方向即为这些窗口对应的方向中最大的那一个。如图7：

图7 特征点主方向确定

注：文中说明了，很多情况下图像时不需要考虑特征的旋转不变情况的，所以在生成特征点描述子时可以忽略到上面特征点主方向的确定这一步，即为U-SURF(upright-SURF)。

描述子生成：在确定了特征点的主方向后，下面就是生成描述子（即该点的特征向量），以特征点为中心，在垂直于主方向的方向构建一个矩形区域（大小为20s），将该区域划分成4x4的子区域，对每个区域计算（5x5个）点的Harr小波（size=2s）响应值，统计得到每个子区域的四个特征量，如下图8所示（图右侧是以2x2个点为例进行说明）：

图8 特征点描述子生成

同样地，为了增加鲁棒性，所计算的dx，dy的值也会以特征点为中心，通过Gaussian（sigma=3.3s）来赋予一定的权重。于此，便可以生成一个大小为：4x4x4=36维度大小的特征向量。可以通过改变子区域的大小改变特征点描述子的大小，如：3x3x4=36。

注：利用Harr小波响应相对于梯度信息的响应，其优点在于SURF是结合了子带的梯度信息而非某个点的单独梯度信息，因而其更鲁棒，也更稳定。

3、快速配准

文中提出了通过像素点Hessian矩阵的迹（即Laplacian滤波后的符号——对比度信息）来作为检测blob的匹配信息，若两幅图上特征点的迹值不同，则可以明确地确定这两个特征点不能配对，由此只需要通过对迹值相同的特征点进行匹配即可，又一次提升了算法效率。如下图9所示：

图9

至此，便完成了整个SURF特征检测及特征描述子生成的步骤，可以看到，这个方法极大地提升了效率同时能够产生鲁棒的特征信息。另外需要注意的是，在构建金字塔时，随着octave数的增加，特征点会明显减少，所以在自己利用该方法进行试验时，可以增加通过增加层数减少octave数的方法来找到更多的特征点。