尺度不变特征变换-Scale Invariant Feature Transform-SIFT

思想：在不同尺度空间上寻找特征点，并加以描述

问题链

什么是SIFT？
为什么要提出来这种方法，解决什么问题？
这个方法的思想是什么？
方法的具体内容有哪些？
前提是什么？局限性有哪些？
效果怎么样？

什么是SIFT？

1999年British Columbia大学大卫.劳伊（David G.Lowe）教授提出了一种基于尺度空间的、对图像缩放、旋转甚至仿射变换保持不变性的图像局部特征描述算子－SIFT（尺度不变特征变换），这种算法在2004年被加以完善。

为什么要提出来这种方法，解决什么问题？

在目标检测领域，识别杂乱的真实场景中的物体是一个很困难的任务，需要找到一些不受遮挡、光照、变形等因素影响的特征点。传统的方法如角点、边缘检测，鲁棒性、适应性差。

Lowe提出来的SIFT方法一定程度上能够解决这些问题：在图像上寻找一些特殊的特征点，这些特征点对光照、仿射变换具有一定程度的不变性，因此可以拿来做特征匹配，目标识别。

这个方法的思想是什么？

在不同尺度空间上寻找具有方向信息的局部极值点作为特征点。

方法的具体内容有哪些？

SIFT算法实现物体识别主要有三大工序：

提取关键点；
对关键点进行描述，生成关键点的描述器；
关键点匹配，通过两方特征点的两两比较找出相互匹配的若干对特征点，也就建立了景物间的对应关系。

什么是尺度空间？如何构造

尺度空间是用来模拟人在距离目标由近到远时，目标在视网膜上的投影情况。尺度是自然存在的，不是人为创造的。在数学上，可以利用不同大小的高斯卷积核来描述不同的尺度空间。
高斯核：

$G(x_i, y_i,\sigma) = \frac{1}{2\pi \sigma^2}(- \frac{(x-x_i)^2+(y-y_i)^2)}{2\sigma^2})$

和高斯核卷积后的图像：

$L(x,y,\sigma) = G(x,y,\sigma)*I(x,y)$

高斯金字塔

高斯金子塔的构建过程可分为两步：

对图像做高斯平滑；
对图像做降采样。

为了让尺度体现其连续性，在简单下采样的基础上加上了高斯滤波。一幅图像可以产生几组（octave）图像，一组图像包括几层（interval）图像。

如何寻找特征点？

所有特征点的检测都是基于尺度不变的特性。Lindeberg[Lindeberg, Tony, “Scale-space theory: A basic tool for analysing structures at different scales”, Journal of Applied Statistics, 21, 2 (1994), pp. 224–270.]指出尺度规范化的LoG算子具有真正的尺度不变性。
LoG算子即（Laplacion of Gaussian）,可以由高斯函数梯度算子GOG构建。

尺度规范化的GoG算子：

$\nabla^2G = \frac{\partial ^2G}{\partial x^2} + \frac{\partial ^2G}{\partial y^2}$

尺度规范化的LoG算子：

$\sigma ^2\nabla ^2G$

高斯差分算子

LOG算子与高斯核函数的关系如下：

$\nabla^2G = \frac{\partial ^2G}{\partial x^2} + \frac{\partial ^2G}{\partial y^2}$ $LOG(x,y,\sigma) = \sigma ^2\nabla ^2G \approx \frac{Gauss(x,y,k\sigma)-Gauss(x,y,\sigma)}{\sigma ^2(k-1)}$ $G(x,y,k\sigma) - G(x,y,\sigma) \approx (k-1)\sigma ^2\nabla ^2G$

通过推导可以看出，LOG算子与高斯核函数的差有直接关系，由此引入一种新的算子DOG（Difference of Gaussians），即高斯差分算子。高斯差分算子(DoG)能够近似代替拉普拉斯高斯算子(LoG)[Mikolajczyk K., Schmid C. (2002) An Affine Invariant Interest Point Detector. ]

构建高斯差分金字塔

对应DoG算子，我们要构建DOG金字塔：

我们可以通过高斯差分图像看出图像上的像素值变化情况。如果没有变化，也就没有特征。特征必须是变化尽可能多的点。DoG图像描绘的是目标的轮廓。

DoG局部极值检测

关键点是由DOG空间的局部极值点组成的。为了寻找DoG函数的极值点，每一个像素点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。

中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。

关键点精确定位

为了提高关键点的稳定性，需要对尺度空间DoG函数进行曲线拟合。利用DoG函数在尺度空间的Taylor展开式：

$D(X) = D + \frac{\partial D^T}{\partial X}X + \frac{1}{2}X^T\frac{\partial ^2D^T}{\partial X^2}X$

其极值点为：

$\hat{X} = (x,y,\sigma)^T = -\frac{\partial D^T}{\partial X}(\frac{\partial ^2D^T}{\partial X^2})^{-1}$

关键点方向分配

通过尺度不变性求极值点，可以使其具有缩放不变的性质，利用关键点邻域像素的梯度方向分布特性，我们可以为每个关键点指定方向参数，从而使描述子对图像旋转具有不变性。
我们通过求每个极值点的梯度来为极值点赋予方向。
像素点的梯度表示：

$\nabla I(x,y) = (\frac{\partial I}{\partial x}, \frac{\partial I}{\partial y})$

梯度幅值：

$m(x,y) = \sqrt{(L(x+1,y)-L(x-1,y))^2+(L(x,y+1)-L(x,y-1))^2}$

梯度方向：

$\theta(x,y) = tan^{-1}[\frac{L(x,y+1)-L(x,y-1)}{L(x+1,y)-L(x-1,y)}]$

确定关键点的方向时采用直方图统计法，统计以关键点为中心，一定区域内的梯度分布情况。

直方图以每10度方向为一个柱，共36个柱，柱所代表的方向为像素点梯度方向，柱的长短代表了梯度幅值。
根据Lowe的建议，直方图统计半径采用$3 \ast 1.5 \ast \sigma$。
在直方图统计时，每相邻三个像素点采用高斯加权，根据Lowe的建议，模板采用[0.25,0.5,0.25]，并连续加权两次。

如何对关键点描述？

图像的关键点已检测完毕，每个关键点有三个信息：位置、尺度、方向；同时也就使关键点具备平移、缩放、和旋转不变性。

描述的目的

描述的目的是在关键点计算后，用一组向量将这个关键点描述出来，这个描述子不但包括关键点，也包括关键点周围对其有贡献的像素点。用来作为目标匹配的依据，也可使关键点具有更多的不变特性，如光照变化、3D视点变化等。

描述的思路

通过对关键点周围图像区域分块，计算块内梯度直方图，生成具有独特性的向量，这个向量是该区域图像信息的一种抽象，具有唯一性。

关键点描述

下图是一个SIFT描述子事例。其中描述子由2×2×8维向量表示，其实也是2×2个8方向的直方图。左图的种子点由8×8单元组成。每一个小格都代表了特征点邻域所在的尺度空间的一个像素，箭头方向代表了像素梯度方向，箭头长度代表该像素的幅值。然后在4×4的窗口内计算8个方向的梯度方向直方图。绘制每个梯度方向的累加可形成一个种子点，如右图所示：一个特征点由4个种子点的信息所组成。