1、简介

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

类别：特征描述子。

介绍：SIFT是一种电脑视觉的算法用来侦测与描述影像中的局部性特征，它在空间尺度中寻找极值点，并提取出其位置、尺度、旋转不变量，此算法由 David Lowe在1999年所发表，2004年完善总结。局部影像特征的描述与侦测可以帮助辨识物体，SIFT 特征是基于物体上的一些局部外观的兴趣点而与影像的大小和旋转无关。对于光线、噪声、些微视角改变的容忍度也相当高。

特点：

1. SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性；
2. 独特性（Distinctiveness）好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配；
3. 多量性，即使少数的几个物体也可以产生大量的SIFT特征向量；
4. 高速性，经优化的SIFT匹配算法甚至可以达到实时的要求；
5. 可扩展性，可以很方便的与其他形式的特征向量进行联合。

作用：SIFT算法可以解决的问题

1. 目标的旋转、缩放、平移（RST）
2. 图像仿射/投影变换（视点viewpoint）
3. 光照影响（illumination）
4. 目标遮挡（occlusion）
5. 杂物场景（clutter）
6. 噪声

　　　SIFT算法的实质是在不同的尺度空间上查找关键点(特征点)，并计算出关键点的方向。SIFT所查找到的关键点是一些十分突出，不会因光照，仿射变换和噪音等因素而变化的点，如角点、边缘点、暗区的亮点及亮区的暗点等。

SIFT方法步骤：

1. 尺度空间极值检测：搜索所有尺度上的图像位置。通过高斯微分函数来识别潜在的对于尺度和旋转不变的兴趣点。
2. 关键点定位：在每个候选的位置上，通过一个拟合精细的模型来确定位置和尺度。关键点的选择依据于它们的稳定程度。
3. 方向确定：基于图像局部的梯度方向，分配给每个关键点位置一个或多个方向。所有后面的对图像数据的操作都相对于关键点的方向、尺度和位置进行变换，从而提供对于这些变换的不变性。
4. 关键点描述：在每个关键点周围的邻域内，在选定的尺度上测量图像局部的梯度。这些梯度被变换成一种表示，这种表示允许比较大的局部形状的变形和光照变化。

2、高斯模糊

　　SIFT算法是在不同的尺度空间上查找关键点，而尺度空间的获取需要使用高斯模糊来实现。

2.1二维高斯函数

　　高斯模糊是一种图像滤波器，它使用正态分布(高斯函数)计算模糊模板，并使用该模板与原图像做卷积运算，达到模糊图像的目的。二维高斯函数如公式2.1所示，其中$sigma$是正态分布的标准差,$sigma$值越大，图像越平滑（模糊）：

$G(x,y)=\frac{1}{\sqrt{2\pi\sigma^{2}}}e^{-\frac{x^{2}+y^{2}}{2\sigma^{2}}}$  ，（2.1）

　　在二维空间中，这个公式生成的曲面的等高线是从中心开始呈正态分布的同心圆，如下图所示。分布不为零的像素组成的卷积矩阵与原始图像做变换。每个像素的值都是周围相邻像素值的加权平均。原始像素的值有最大的高斯分布值，所以有最大的权重，相邻像素随着距离原始像素越来越远，其权重也越来越小。这样进行模糊处理比其它的均衡模糊滤波器更高地保留了边缘效果。

　　理论上来讲，图像中每点的分布都不为零，这也就是说每个像素的计算都需要包含整幅图像。在实际应用中，在计算高斯函数的离散近似时，在大概$3sigma$距离之外的像素都可以看作不起作用，这些像素的计算也就可以忽略。通常，图像处理程序只需要计算$（6\sigma+1）\times（6\sigma+1）$的矩阵就可以保证相关像素影响。假设我们用$3\times3$的矩阵模糊图像，当中心点的坐标是（0,0）时，那么距离它最近的8个点的坐标如下：

　　为了计算权重矩阵，需要设定σ的值，高斯模板是中心对称的。假定σ=1.5，则模糊半径为1的权重矩阵如下：

　　这9个点的权重总和等于0.4787147，如果只计算这9个点的加权平均，还必须让它们的权重之和等于1，因此上面9个值还要分别除以0.4787147，得到最终的权重矩阵。这是归一化的过程。目的是让滤镜的权重总值等于1。否则的话，使用总值大于1的滤镜会让图像偏亮，小于1的滤镜会让图像偏暗。

有了权重矩阵，将该权重矩阵与图像矩阵卷积就可以计算高斯模糊的值了。卷积如公式2.2所示：

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

2.2 分离高斯模糊

　　根据高斯函数的可分离性，可对二维高斯模糊函数进行改进。高斯函数的可分离性是指使用二维矩阵变换得到的效果也可以通过在水平方向进行一维高斯矩阵变换加上竖直方向的一维高斯矩阵变换得到。主要作用是降低了计算复杂度，这种方法只需要$O(n\times M\times N)+O(m\times M\times N)$次计算，而二维不可分矩阵需要$O(n\times m\times M\times N)$次计算，其中，m、n是高斯矩阵的维数；M、N是二维图像的维数。

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

$=\frac{1}{\sqrt{2\pi\sigma^{2}}}e^{-\frac{x^{2}}{2\sigma^{2}}}\times\frac{1}{\sqrt{2\pi\sigma^{2}}}e^{-\frac{y^{2}}{2\sigma^{2}}}$

$=G(x) \times G(y)$

　　另外，两次一维的高斯卷积将消除二维高斯矩阵所产生的边缘。(关于消除边缘的论述如下图所示， 对用模板矩阵超出边界的部分——虚线框，将不做卷积计算。下图中x方向的第一个模板1*5，将退化成1*3的模板，只在图像之内的部分做卷积。)

3、尺度空间极值检测

　　尺度空间使用高斯金字塔表示。Tony Lindeberg指出尺度规范化的LoG(Laplacion of Gaussian)算子具有真正的尺度不变性，Lowe使用高斯差分金字塔近似LoG算子，在尺度空间检测稳定的关键点。

3.1 尺度空间理论

      尺度空间理论的基本思想是：在图像信息处理模型中引入一个被视为尺度的参数，通过连续变化尺度参数获得多尺度下的尺度空间表示序列，对这些序列进行尺度空间主轮廓的提取，并以该主轮廓作为一种特征向量，实现边缘、角点检测和不同分辨率上的特征提取等。

      高斯函数中$\sigma$即为尺度空间因子，值越小表示图像被平滑的越少，相应的尺度也就越小。大尺度对应于图像的概貌特征，小尺度对应于图像的细节特征。

3.2 高斯差分金字塔

尺度空间在实现时使用高斯金字塔表示，高斯金字塔的构建分为两部分：

1. 对图像做不同尺度的高斯模糊；

2. 对图像做降采样(隔点采样)。

　　图像的金字塔模型是指，将原始图像不断降阶采样，得到一系列大小不一的图像，由大到小，从下到上构成的塔状模型。原图像为金字塔的第一层，每次降采样所得到的新图像为上一个Octave的倒数第三张图像。每个金字塔共n层。金字塔的层数根据图像的原始大小和塔顶图像的大小共同决定，其计算公式如下：

$n=\log_{2}{\left\{min(M,N)\right\}-t}$

$t\epsilon[0,\log_{2}{min(M,N)})$

　　其中M，N为原图像的大小,t为塔顶图像的最小维数的对数值。如，对于大小为512*512的图像，当塔顶图像为4*4时，n=7，当塔顶图像为2*2时，n=8。

　　为了让尺度体现其连续性，高斯金字塔在简单降采样的基础上加上了不同尺度的高斯滤波。

3.2.1 尺度空间生成了多少幅图像

　　S是我们最终构建出来的用来寻找关键点的图像，也就是上幅图像中的最后一部分，而关键点的寻找需要查找的是空间局部极小值，即在某一层上查找局部极值点的时候需要用到上一层与下一层的高斯差分图像，所以如果我们需要查找S层的特征点，需要S+2层高斯差分图像，然后查找其中的第2层到第S+1层，即利用高斯差分图像中每一个Octave中除了最上面一层与最底下一层的图像。

　　假设我们在每一个Octave中需要三幅图像来查找关键点，即S=3，而每一个高斯差分图像$G(x,y,\sigma)$G(x,y,σ)">都需要两幅尺度空间的图像$L(x,y,k\sigma)$L(x,y,kσ)">与$L(x,y,\sigma)$L(x,y,σ)">进行差分生成，则我们需要的高斯差分图像有S+2 = 5张，分别为$G(x,y,\sigma)$，$G(x,y,k\sigma)$，$G(x,y,k^{2}\sigma)$，$G(x,y,,k^{3}\sigma)$，$G(x,y,,k^{4}\sigma)$G(x,y,σ),G(x,y,kσ),G(x,y,k2σ),G(x,y,k3σ),G(x,y,k4σ)">。其中的$G(x,y,k\sigma)$，$G(x,y,k^{2}\sigma)$，$G(x,y,,k^{3}\sigma)$G(x,y,kσ),G(x,y,k2σ),G(x,y,k3σ)">这三张图像是我们用来查找局部极值点的图像。那么我们则需要$S+3=6$张尺度空间图像来生成上面那些高斯差分图像，它们分别为：$L(x,y,\sigma)$，$L(x,y,k\sigma)$，$L(x,y,k^{2}\sigma)$，$L(x,y,,k^{3}\sigma)$，$L(x,y,k^{4}\sigma)$，$L(x,y,,k^{5}\sigma)$。

 　　所以，高斯金字塔有几层取决于最上面一层图像的大小；金字塔中每一个Octave中有几个不同尺度的模糊图像取决于最后要用几幅图来查找关键点。

3.2.2 为什么要做降采样

　　当用一个机器视觉系统分析未知场景时，计算机没有办法预先知识图像中物体尺度，因此，我们需要同时考虑图像在多尺度下的描述，获知感兴趣物体的最佳尺度。

3.2.3 为什么是倒数第3张

　　为了保证尺度空间的连续性。

　　对于尺度空间第$o$组，第$s$层的图像，它的尺度为：

$\sigma=\sigma_{0}k^{o+s/S}$，其中，$k=1/2,o \in [0,1,2,...,n-1],s\in[0,1,2,...,S+2]$，$n$是高斯金字塔的层数，$S$是生成关键点需要的图的数量。那么我们从第0组开始，看它各层的尺度。

　　第0组：$\sigma_{0}\rightarrow 2^{1/3}\sigma_{0}\rightarrow 2^{2/3}\sigma_{0}\rightarrow 2^{3/3}\sigma_{0}\rightarrow 2^{4/3}\sigma_{0}\rightarrow 2^{5/3}\sigma_{0}$

　　第1组：$2\sigma_{0}\rightarrow 2*2^{1/3}\sigma_{0}\rightarrow 2*2^{2/3}\sigma_{0}\rightarrow 2*2^{3/3}\sigma_{0}\rightarrow 2*2^{4/3}\sigma_{0}\rightarrow 2*2^{5/3}\sigma_{0}$

　　我们只分析2组便可以看出，第1组的第0层图像恰好与第0组的倒数第三幅图像一致，尺度都为$2\sigma_{0}$2σ0">，所以我们不需要再根据原图来重新卷积生成每组的第0张图像，只需采用上一层的倒数第3张来降采样即可。

　　我们也可以继续分析，第0组尺度空间得到的高斯差分图像的尺度为：$\sigma_{0}\rightarrow 2^{1/3}\sigma_{0}\rightarrow 2^{2/3}\sigma_{0}\rightarrow 2^{3/3}\sigma_{0}\rightarrow 2^{4/3}\sigma_{0}$

　　而第1组尺度空间得到的高斯差分图像的尺度为：$2\sigma_{0}\rightarrow 2*2^{1/3}\sigma_{0}\rightarrow 2*2^{2/3}\sigma_{0}\rightarrow 2*2^{3/3}\sigma_{0}\rightarrow 2*2^{4/3}\sigma_{0}$

　　如果我们把它们的中间三项取出来拼在一起，则尺度为：$2^{1/3}\sigma_{0}\rightarrow 2^{2/3}\sigma_{0}\rightarrow 2^{3/3}\sigma_{0}\rightarrow2*2^{1/3}\sigma_{0}\rightarrow 2*2^{2/3}\sigma_{0}\rightarrow 2*2^{3/3}\sigma_{0}$，正好连续！！这一效果带来的直接的好处是在尺度空间的极值点确定过程中，我们不会漏掉任何一个尺度上的极值点，而是能够综合考虑量化的尺度因子。

3.3 空间极值点检测(关键点的初步探查)

　　关键点的搜索是通过同一组内各DoG相邻层之间比较完成的。为了寻找尺度空间的极值点，每一个采样点要和它所有的相邻点进行比较，看其是否比它的图像域和尺度域的相邻点大或小。对于其中的任意一个检测点都要和它同尺度的8个相邻点和上下相邻尺度对应的$9\times 2$9×2">个点共26个点比较，以确保在尺度空间和二维图像位置空间都检测到极值点。也就是，比较是在一个$3\times 3\times 3$3×3">的立方体内进行。

　　搜索过程从每组的第二层开始，以第二层为当前层，对第二层的DoG图像中的每个点取一个$3\times 3\times 3$3×3">的立方体，立方体上下层为第一层与第三层。这样，搜索得到的极值点既有位置坐标（DoG的图像坐标），又有空间尺度坐标（层坐标）。当第二层搜索完成后，再以第三层作为当前层，其过程与第二层的搜索类似。当S=3时，每组里面要搜索3层。

4、关键点定位

　　以上方法检测到的极值点是离散空间的极值点，以下通过拟合三维二次函数来精确确定关键点的位置和尺度，同时去除低对比度的关键点和不稳定的边缘响应点(因为DoG算子会产生较强的边缘响应)，以增强匹配稳定性、提高抗噪声能力。

4.1关键点的精确定位

　　离散空间的极值点并不是真正的极值点，下图显示了二维函数离散空间得到的极值点与连续空间极值点的差别。利用已知的离散空间点插值得到的连续空间极值点的方法叫做子像素插值。

　　首先我们来看一个一维函数插值的例子。$f(x)$f(x)">上几个点的函数值 $f(-1)=1,f(0)=6,f(1)=5$ f(−1)=1,f(0)=6,f(1)=5">，求$f(x)$ f(x)">在$[−1,1]">[?1,1]$上的最大值。

　　如果我们只考虑离散的情况，那么只用简单比较一下，便知最大值为$f(0)=6$ f(0)=6">，下面我们用子像元插值法来考虑连续区间的上情况：

f(0)=6">　　利用泰勒级数，可以将 $f(x)$f(x)">在 $f(0)$ f(0)">附近展开为：f(x)">f(0)">$f(x)\approx f(0)+f^{'}(0)x+\frac{f^{''}(0)}{2}x^{2}$

　　另外我们知道$f(x)$f(x)">在$x$x">处的导数写成离散的形式为$f^{'}(x)=\frac{f(x+1)-f(x-1)}{2}$f′(x)=f(x+1)–f(x)2">，二阶导数写成离散形式为$f^{''}(x)=f(x+1)+f(x-1)-2f(x)$f″(x)=f(x+1)+f(x−1)−2f(x)">。

　　所以，我们可以算出$f(x)\approx 6+2x-3x^{2}$

　　求取函数$f(x)$f(x)">的极大值和极大值所在的位置：

 $f^{'}(x)=2-6x=0, \widehat{x}=\frac{1}{3}$

 $f(\widehat{x})=6+2\times \frac{1}{3}-3\times (\frac{1}{3})^{2}=6\frac{1}{3}$

　　现在回到我们SIFT点检测中来，我们要考虑的是一个三维问题，假设我们在尺度为$\sigma$σ">的尺度图像$D(x,y)">D(x,y)$上检测到了一个局部极值点，空间位置为$(x,y,\sigma)$(x,y,σ)">，由上面的分析我们知道，它只是一个离散情况下的极值点，连续情况下，极值点可能落在了$(x,y,\sigma)$(x,y,σ)">的附近，设其偏离了$(x,y,\sigma)$(x,y,σ)">的坐标为$D(\triangle x,\triangle y,\triangle \sigma)$(Δx,Δy,Δσ)">。则对$D(\triangle x,\triangle y,\triangle \sigma)$D(Δx,Δy,Δσ)">可以表示为在点$(x,y,\sigma)$(x,y,σ)">处的泰勒展开：

　　可以将上式写成矢量形式如下：$D(x)=D+\frac{\partial D^{T}}{\partial x}\triangle x+\frac{1}{2}\triangle x^{T}\frac{\partial^{2}D^{T}}{\partial x^{2}}\triangle x$

　　令上式的一阶导数等于0，可以求得$\triangle x=-\frac{\partial^{2}D^{-1}}{\partial x^{2}}\frac{\partial D(x)}{\partial x}$

　　通过多次迭代(Lowe算法里最多迭代5次)，得到最终候选点的精确位置与尺度$\widehat{x}$x^">，将其代入公式求得$D(\widehat{x})$D(x^)">，求其绝对值得\mid D(\widehat{x})\mid|D(x^)|">。绝对值低于阈值（Lowe论文中使用0.03，Rob Hess等人实现时使用0.04）的极值点将被删除。

5、总结

到这里就不想写下去了，真的好长，需要了解更清楚地参考以下两篇博客，这两篇博客写的非常详细。本文参考了其他博客，仅用于学习，侵删。

参考博客：

https://blog.csdn.net/zddblog/article/details/7521424

https://www.cnblogs.com/ronny/p/4028776.html