SIFT算法

SIFT是Scale-invariant feature transfor的首字母缩写，即尺度不变特征变换。在上一篇博客中（特征点检测（一）Harris角点检测），我们知道Harris角点检测不具有尺度不变性，而SIFT算法很好的解决了这一问题。

SIFT算法主要分为五个步骤：获得尺度空间、寻找极值点、去除边界效应、方向赋值和生成特征描述子。

获得尺度空间（尺度不变性）

获得尺度空间即高斯金字塔，是通过使用不同模糊系数的高斯函数卷积图像得到的。公式如下：


L(x,y,σ)是卷积后的图像；
G(x,y,σ)是高斯函数，σ是高斯模糊系数；值越小尺度也就越小；
I(x,y)是原图像。

寻找尺度空间内的极值点

先使用高斯金字塔每相邻两层相减得到高斯差分金字塔。如下图所示：

得到高斯差分金字塔后，中间的检测点和它同尺度的8个相邻点以及上下相邻尺度对应的9×2个点，一共26个点进行比较，从而获得极值点（即最大值或最小值）。因此高斯差分金字塔的最上层和最下层不做检测点。 具体表示如下图：

关键点精确定位

由上一步骤，我们知道，是在离散的情况下获得的极值点，位置信息不够准确。我们可以通过插值法和对高斯函数拟合，找到精确的极值点，即关键点。

去除边缘效应

高斯差分算子对边缘有很强的响应，所以落在边缘的点并不是稳定的特征点，需要去除。

方向赋值（旋转不变性）

以关键点为中心，计算一定范围内图像梯度的幅值和幅角。绘制梯度直方图，以幅角为x轴，没个10度为间隔，y为幅值。其中y值最大的为主方向，将坐标轴旋转到主方向上，关键点具有了旋转不变性。此时，每个关键点具有了位置、尺度、方向三个信息，由此可以确定一个SIFT特征区域。

生成特征描述子（光照不变性）

以关键点为中心选择邻近区域分成 4×4的窗口，计算各个窗口内的梯度，做出梯度方向直方图，以45度为间隔，每个窗口将得到8维描述向量。所以一个关键点将由448=128维的描述子唯一表示。将这些向量进行归一化处理，会去除光照变化的影响。

SIFT是十分稳定的特征提取方法，应用广泛。

优点

<1> 具有尺度、旋转、光照变换具有不变性；对仿射变换以及噪声也具有一定的稳定性；
<2> 即使少量的物体，也能产生很多SIFT特征；
<3> 可以在海量特征数据库中进行快速、准确的匹配；

缺点

<1> 计算量大，实时性不高；
<2> 对于模糊图像和边缘光滑图像，检测的特征点较少；

之后，有很多算法对SIFT进行了改进，例如SURF。SURF算法使用不同大小的盒子滤波器代替高斯函数卷积原图像，得到大小一致的滤波后图片，用来构成图像金字塔，从而减小了计算量，速度更快。