SURF Speeded Up Robust Features¶
SURF算法是对SIFT算法的改进，其基本结构、步骤与SIFT相近，但具体实现的过程有所不同。SURF算法的优点是速度远快于SIFT且稳定性好。
算法描述¶
特征点的提取¶
- 在SURF算法中，特征点的判据为某像素亮度的Hessian矩阵的行列式（Dxx*Dyy-Dxy*Dxy）为一个极值。由于Hessian矩阵的计算需要用到偏导数的计算，这一般通过像素点亮度值与高斯核的某一方向偏导数卷积而成；在SURF算法里，为提高算法运行速度，在精度影响很小的情况下，用近似的盒状滤波器（0，1，1组成的box filter）代替高斯核。因为滤波器仅有0，-1,1，因此卷积的计算可以用积分图像（Integral image）来优化（O(1)的时间复杂度），大大提高了效率。每个点需计算Dxx，Dyy，Dxy三个值，故需要三个滤波器；用它们滤波后，得到一幅图像的响应图（Response image，其中每个像素的值为原图像素的Dxx*Dyy-Dxy*Dxy）。对图像用不同尺寸的滤波器进行滤波，得到同一图像在不同尺度的一系列响应图，构成一个金字塔（该金字塔无需像SIFT中的高斯一样进行降采样，即金字塔每组中的每层图像分辨率相同）。
- 特征点的检测与SIFT一致，即若某点的Dxx*Dyy-Dxy*Dxy大于其邻域的26个点（与SIFT一致）的Dxx*Dyy-Dxy*Dxy，则该点为特征点。特征点的亚像素精确定位与SIFT一致。
描述子的建立¶
- 为保证特征点描述子的旋转不变性，需对每个特征点计算主方向。计算主方向的过程如下：
- 统计以特征点为中心，正比于特征点尺度的某个数位半径，张角为60°的扇形区域内所有像素点的 sumX=（y方向小波变换响应）*（高斯函数），sumY=（x方向小波变换响应）*（高斯函数）， 计算合成向量角度θ=arctan(sumY/sumX)，模长sqrt(sumy*sumy+sumx*sumx)。
- 将扇形沿逆时针旋转（一般取步长为0.1个弧度），以同样方法计算合成向量。
- 求出各方向扇形的合成向量模长最大值，其对应的角度即特征点主方向。
- 描述子的建立过程如下：
- 选定以特征点为中心的一块正方形区域，将其旋转与主方向对齐。
- 将正方形分为4x4的16个子区域，对每个区域进行Haar 小波变换（同样用积分图像加速），得到4个系数。
- 由上述两步，生成4x4x4=64维向量，即描述子，用它可以进行匹配等工作。
创新点¶
算法的创新点在于大量合理使用积分图像降低运输量，而且在运用的过程中并未降低精度（小波变换，Hessian矩阵行列式检测都是成熟有效的手段）。
结果比较¶
在时间上，SURF运行速度大约为SIFT的3倍；在质量上，SURF的鲁棒性很好，特征点识别率较SIFT高，在视角、光照、尺度变化等情形下，大体上都优于SIFT。