SIFT算法原理解析

首先找到图像中的一些“稳定点”，这些点是一些十分突出的点不会因光照条件的改变而消失，比如角点、边缘点、暗区域的亮点以及亮区域的点，既然两幅图像中有相同的景物，那么使用某种方法分别提取各自的稳定点，这些点之间会有相互对应的匹配点，正是基于这样合理的假设，SIFT算法的基础是稳定点。SIFT算法找稳定点的方法是找灰度图的局部最值，由于数字图像是离散的，想求导和求最值这些操作都是使用滤波器，而滤波器是有尺寸大小的，使用同一尺寸的滤波器对两幅包含有不同尺寸的同一物体的图像求局部最值将有可能出现一方求得最值而另一方却没有的情况，但是容易知道假如物体的尺寸都一致的话它们的局部最值将会相同。SIFT的精妙之处在于采用图像金字塔的方法解决这一问题，我们可以把两幅图像想象成是连续的，分别以它们作为底面作四棱锥，就像金字塔，那么每一个截面与原图像相似，那么两个金字塔中必然会有包含大小一致的物体的无穷个截面，但应用只能是离散的，所以我们只能构造有限层，层数越多当然越好，但处理时间会相应增加，层数太少不行，因为向下采样的截面中可能找不到尺寸大小一致的两个物体的图像。有了图像金字塔就可以对每一层求出局部最值，但是这样的稳定点数目将会十分可观，所以需要使用某种方法抑制去除一部分点，但又使得同一尺度下的稳定点得以保存。（此段文字来自http://blog.csdn.net/cy513/article/details/4414352）

一、尺度空间的构建

1、图像尺度空间

2、高斯差分尺度空间(DOG scale-space)

利用不同尺度的高斯差分核与图像卷积生成:

3、高斯金字塔

图像的金字塔模型是指，将原始图像不断降阶采样，得到一系列大小不一的图像，由大到小，从下到上构成的塔状模型。原图像为金子塔的第一层，每次降采样所得到的新图像为金字塔的一层(每层一张图像)，每个金字塔共n 层。为了让尺度体现其连续性，高斯金字塔在简单降采样的基础上加上了高斯滤波。高斯金字塔上一组图像的初始图像(底层图像)是由前一组图像的倒数第三张图像隔点采样得到的。

4、DOG金字塔

2002年Mikolajczyk在详细的实验比较中发现尺度归一化的高斯拉普拉斯函数的极大值和极小值同其它的特征提取函数，例如：梯度，Hessian 或Harris 角特征比较，能够产生最稳定的图像特征。而Lindeberg 早在1994 年就发现高斯差分函数（Difference of Gaussian ，简称DOG 算子）与尺度归一化的高斯拉普拉斯函数非常近似。
下图反应了两者的关系:

DOG的计算可以由相邻尺度高斯平滑后的图像相减得到:

二、检测DOG尺度空间极值点

SIFT关键点是由DOG空间的局部极值点组成的.以中心点进行3X3X3的相邻点比较,检测其是否是图像域和尺度域的相邻点的极大值或极小值.

在极值比较的过程中,每一组图像的首末两层是无法进行极值比较的,为了满足尺度变化的连续性,在每一组图像的顶层继续用高斯模糊生成了 3 幅图像，高斯金字塔有每组S+3层图像。DOG金字塔每组有S+2层图像:

三、精确定位关键点
1、位置的插值

下图是二维函数离散空间得到的极值点与连续空间极值点的差别:

利用已知的离散空间点插值得到的连续空间极值点的方法叫做子像素插值（Sub-pixel Interpolation）.对尺度空间DOG函数进行曲线拟合(子像素插值),利用DOG函数在尺度空间的泰勒展开式:

公式推导如下：

极值点的偏移量的求解如下：

2、去除边缘响应

一个定义不好的高斯差分算子的极值在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。 DOG 算子会产生较强的边缘响应，需要剔除不稳定的边缘响应点。获取特征点处的Hessian 矩阵，主曲率通过一个2x2 的Hessian 矩阵H 求出：

四、特征点方向分配

对上面提取的每个关键点，围绕该点选择一个窗口（圆形区域），窗口内各采样点的梯度方向构成一个方向直方图，根据直方图的峰值确定关键点的方向。关键点的尺度用来选择哪个高斯滤波图像参与计算，还用来决定窗口的大小——为了保证不同尺度下的同一关键点的方向都包含相同的信息量，那么窗口的大小必然不一样：同一个原始图像，尺度越大，窗口应该越大；反之，如果窗口大小不变，尺度越大的图像，该窗口内的信息越少.

做一个梯度方向的直方图，范围是0～360度，其中每10度一个柱，总共36个柱。每个采样点按照其梯度方向θ(x,y)加权统计到直方图，权值为幅度m(x,y )和贡献因子的乘积。贡献因子是采样点到关键点（窗口中心）距离的量度，距离越大，贡献因子越小.直方图的峰值代表了该关键点处邻域梯度的主方向.

Lowe指出，直方图的峰值确定以后，任何大于峰值80%的方向（柱）创建一个具有该方向的关键点，因此，对于多峰值（幅值大小接近）的情形，在同一位置和尺度就会产生多个具有不同方向的关键点。虽然这样的点只占15%，但是它们却能显著地提高匹配的稳定性。用每个峰值和左右两个幅值拟合二次曲线，以定位峰值的实际位置（抛物线的最高点）。峰值方向的精度高于10度。

所以,关键点的方向分配步骤如下:

五、描述符的生成

SIFT 描述子是关键点领域高斯图像梯度统计结果的一种表示。通过对关键点周围图像区域分块，计算块内梯度直方图，生成具有独特性的向量，这个向量是该区域图像信息的一种抽象，具有唯一性。 Lowe 建议描述子使用在关键点尺度空间内4×4的窗口中计算的8 个方向的梯度信息，共4×4×8 =128维向量表征.

1、确定计算描述子所需的图像区域

计算结果四舍五入取整。

2、将坐标轴旋转为关键点的方向，以确保旋转不变性

旋转后领域内采样点的新坐标为:

3、将领域内的采样点分配到对应的子区域内，将子区域内的梯度值分配到8 个方向上，计算其权值

4、插值计算每个种子点八个方向的梯度

如上图所示，将所得采样点在子区域中的下标(x'',y'')(图中蓝色窗口内红色点)线性插值，计算其对每个种子点的贡献。如图中的红色点，落在第0 行和第1 行之间，对这两行都有贡献。对第0 行第3 列种子点的贡献因子为dr，对第1 行第3 列的贡献因子为1-dr，同理，对邻近两列的贡献因子为dc 和1-dc，对邻近两个方向的贡献因子为do 和1-do。则最终累加在每个方向上的梯度大小为：

5、描述符向量元素门限化

即把方向直方图每个方向上梯度幅值限制在一定门限值一下（门限一般取0.2）

6、描述符向量元素归一化

特征向量形成后，为了去除光照变化的影响，需要对它们进行归一化处理，对于图像灰度值整体漂移，图像各点的梯度是邻域像素相减得到，所以也能去除。

六、匹配

采用关键点描述子的欧式距离来作为两幅图像的关键点的相似性度量。

七、SIFT算法的缺陷

(1)SIFT在求主方向阶段太过于依赖局部区域像素的梯度方向，有可能使得找到的主方向不准确，后面的特征向量提取以及匹配都严重依赖于主方向，即使不大偏差角度也可以造成后面特征匹配的放大误差，从而匹配不成功；
(2)图像金字塔的层取得不足够紧密也会使得尺度有误差，后面的特征向量提取同样依赖相应的尺度，发明者在这个问题上的折中解决方法是取适量的层然后进行插值。
(3)我们知道同样的景物在不同的照片中可能出现不同的形状、大小、角度、亮度，甚至扭曲；计算机视觉的知识表明通过光学镜头获取的图像，对于平面形状的两个物体它们之间可以建立射影对应，对于像人脸这种曲面物体在不同角度距离不同相机参数下获取的两幅图像，它们之间不是一个线性对应关系，就是说我们即使获得两张图像中的脸上若干匹配好的点对，还是无法从中推导出其他点的对应。

八、SIFT的后续发展