SIFT（尺寸不变特征变换匹配算法）

Magicmanoooo 3月 09, 2019

SIFT简介

传统的特征提取方法

成像匹配的核心问题是：将同一目标在不同时间、不同分辨率、不同光照、不同位姿情况下所成的像相对应。传统的匹配算法往往是直接提取角点或边缘，对环境的适应能力较差。

SIFT将一幅图像映射（变换）为一个局部特征向量集；特征向量具有平移、缩放、旋转不变性，同时对光照变化、仿射及投影变换也有一定不变性。

SIFT算法的特点

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

SIFT算法的适用场景

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

SIFT算法的实现

SIFT算法的实质可以归结为：在不同的尺度空间上查找特征点（关键点）的问题。

SIFT算法实现物体识别的主要步骤：

提取关键点
对关键点附加详细的信息（局部特征），即所谓的描述器
通过双方特征点（附带上特征向量的关键点）的两两比较，找出相互匹配的若干对特征点，即建立物景之间的对应关系

1. 关键点检测

哪些点是SIFT中需要进行查找的关键点（特征点）？

这些点是一些十分突出的点，不会因为关照条件的改变而消失。例如，角点、边缘点、暗区域的亮点以及亮区域的暗点。由于两幅图像中有相同的景物，那么使用某种方法分别提取各自的稳定点，这些点之间会有相互对应的匹配点。

关键点：在不同尺度空间的图像下检测出的具有方向信息的局部极值点。

特征点具有三个特征：

尺度
方向
大小

尺度空间

如果要精确地表示物体，都必须通过一定的尺度来反应。而尺度空间理论的主要思想是：**通过对原始图像进行尺度变换，获得图像多尺度下的尺度空间表示序列，对这些序列进行尺度空间主轮廓的提取，并以该主轮廓作为一种特征向量，实现边缘、角点检测和不同分辨率上的特征提取等。

尺度空间中各尺度图像的模糊程度逐渐变大，能够模拟人在距离目标由近到远时目标在视网膜上的形成过程。即，尺度越大图像越模糊。

高斯核是唯一可以产生多尺度空间的核，一个图像的尺度空间—L( x,y,σ)定义为原始图像I(x,y)与一个可变尺度的二维高斯函数G(x,y,σ) 进行卷积运算得到。

【注意】：尺度是自然存在的，不是人为创造的！高斯卷积只是表现尺度空间的一种形式。

高斯模糊（Gaussian Blur）通常用于减小图像噪声以及降低细节层次。

Gauss金字塔

图像金字塔是一种以多分辨率来解释图像的结构，通过对原始图像进行多尺度像素采样的方式，生成N个不同分辨率的图像。把具有最高级别分辨率的图像放在底部，以金字塔形状排列，往上是一系列像素（尺寸）逐渐降低的图像，一直到金字塔的顶部只包含一个像素点的图像，这就构成了传统意义上的图像金字塔。

获得图像金字塔一般包括二个步骤：

利用低通滤波器平滑图像
对平滑图像进行抽样（采样）

一般情况下，有两种采样方式——上采样（分辨率逐级升高）和下采样（分辨率逐级降低）。

为什么需要Gauss金字塔？

高斯金字塔其实模仿的是图像的不同的尺度。

尺度应该怎样理解？对于一副图像，近距离观察，与在一米之外观察，看到的图像效果是不同的，前者比较清晰，后者比较模糊；前者比较大，后者比较小；通过前者能看到图像的一些细节信息，通过后者能看到图像的一些轮廓的信息，这就是图像的尺度。图像的尺度是自然存在的，并不是人为创造的。

以前对一幅图像的处理还是比较单调的，因为我们的关注点只落在二维空间，并没有考虑到“图像的纵深”这样一个概念。如果将这些内容考虑进去，我们是不是会得到更多以前在二维空间中没有得到的信息呢？于是，高斯金字塔横空出世了，它就是为了在二维图像的基础之上，榨取出图像中自然存在的另一个维度：尺度。由于高斯核是唯一的线性核，也就是说使用高斯核对图像模糊不会引入其他噪声，因此就选用了高斯核来构建图像的尺度

高斯金字塔并不是一个金字塔，而是有很多组（Octave）金字塔构成，并且每组金字塔都包含若干层（Interval）。

Gauss金字塔的构建：

先将原图像扩大一倍之后，作为高斯金字塔的第1组第1层，将第1组第1层图像进行高斯卷积（高斯平滑或称高斯滤波）之后，作为第1组金字塔的第2层。其中，Guass卷积函数为：

其中，参数σ在SIFT算法中取固定值σ=1.6。

将σ乘以一个比例系数k，得到一个新的平滑因子σ=k*σ，用它来平滑第1组第2层图像，结果图像作为第3层。
如此重复，最后得到L层图像。在同一组中，每一层图像的尺寸都是一样的，只是平滑系数不一样。它们对应的平滑系数分别为：

图像的尺度空间解决的问题是如何对图像在所有尺度下描述的问题。

在高斯金字塔中一共生成o组、s层不同尺度的图像，这两个量合起来(o，s)就构成了高斯金字塔的尺度空间，也就是说以高斯金字塔的组o作为二维坐标系的一个坐标，不同层L作为另一个坐标，则给定的一组坐标(o,s)就可以唯一确定高斯金字塔中的一幅图像。

Gauss金字塔的尺度空间坐标计算方法为：

Gauss金字塔的初始尺度

当图像通过相机拍摄时，相机的镜头已经对图像进行了一次初始的模糊，所以根据高斯模糊的性质，可得第0层Gauss金字塔的尺度为：

金字塔的层数根据图像的原始大小和塔顶图像的大小共同决定，计算公式为：

为了让尺度体现其连续性，高斯金字塔在简单降采样的基础上加上了高斯滤波。如图下图所示，将图像金字塔每层的一张图像使用不同参数做高斯模糊，使得金字塔的每层含有多张高斯模糊图像，将金字塔每层多张图像合称为一组(Octave)，金字塔每层只有一组图像，组数和金字塔层数相等，每组含有多张(也叫层Interval)图像。另外，降采样时，高斯金字塔上一组图像的初始图像(底层图像)是由前一组图像的倒数第二张图像隔点采样得到的。

Gauss金字塔的组内尺度与组间尺度

组内尺度是指同一组（octave）内的尺度关系。组内相邻层尺度简化为：

组间尺度是指不同组直接的尺度关系。相邻组的尺度关系为：

由此可见，同一层相邻两组之间的尺度为2倍的关系。

总结，组内和组间尺度的关系：

DOG（Difference of Gaussian，高斯差分函数）

尺度规范化的LoG算子具有真正的尺度不变性。

LoG算子，即Laplacion of Gaussian，可以由高斯函数梯度算子GOG构建。

尺度规范化的GoG算子：

尺度规范化的LoG算子：

LoG算子与高斯核函数（Gaussian kernel function）的关系为：

Difference of Gaussian（高斯差分算子）

DoG在计算上只需将相邻尺度高斯平滑后的图像进行相减，因此简化了计算。

DoG金字塔（高斯差分金字塔）

对应DoG算子，需要构建Dog金字塔。在实际计算时，使用高斯金字塔每组中相邻上下两层图像相减，得到高斯差分图像。

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

空间极值点检测（关键点的初步探查）

关键点是由DoG空间的局部极值点组成的，关键点的初步探查是通过同一组内各DoG相邻两层图像之间比较完成的。为了寻找DoG函数的极值点，每一个像素点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。

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

由于要在相邻尺度进行比较，如果每组含4层的高斯差分金子塔，则只能在中间两层中进行两个尺度的极值点检测，其它尺度则只能在不同组中进行。为了在每组中检测S个尺度的极值点，则DoG金字塔每组需S+2层图像，而DoG金字塔由高斯金字塔相邻两层相减得到，则高斯金字塔每组需S+3层图像，实际计算时S在3~5。

关键点定位

通过拟合三维二次函数来精确确定关键点的位置和尺度，同时去除低对比度的关键点和不稳定的边缘响应点（因为DoG算子会产生较强的边缘响应），以增强匹配稳定性、提高抗噪声能力。

关键点的精确定位

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

由于DoG值对噪声和边缘较敏感，因此在上面DoG尺度空间中检测到的局部极值点还要经过进一步的检验才能精确定位为特征点。

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

其中，。求导并让方程等于零，可以得到极值点的偏移量为。

对应极值点，方程的值为：。

当在任一维度上的偏移量大于0.5时（即x或y或），意味着插值中心已经偏移到它的邻近点上，所以必须改变当前关键点的位置。同时在新的位置上反复插值直到收敛；也有可能超出所设定的迭代次数或者超出图像边界的范围，此时这样的点应该删除，在Lowe的论文中进行了5次迭代。另外，过小的点易受噪声的干扰而变得不稳定，所以将小于某个经验值(Lowe论文中使用0.03，Rob Hess等人实现时使用0.04/S)的极值点删除。同时，在此过程中获取特征点的精确位置(原位置加上拟合的偏移量)以及尺度(和)。

去除边缘响应

仅仅去除低对比度的极值点对于极值点的对于特征点稳定性是远远不够的。 DoG函数在图像边缘有较强的边缘响应，因此我们还需要排除边缘响应。

即，DoG函数的（欠佳的）峰值点在横跨边缘的方向有较大的主曲率，而在垂直边缘的方向有较小的主曲率。主曲率可以通过计算在该点位置尺度的2×2的Hessian矩阵得到，导数由采样点相邻差来估计：

表示DoG金字塔中某一尺度的图像在x方向求导两次。

H的特征值α和β代表x和y方向的梯度：

由于D的主曲率和H的特征值成正比，为了避免直接的计算这些特征值，故只是考虑它们的之间的比率。假设α为较大的特征值，而β为较小的特征值，所以令：。则有：

D的主曲率和H的特征值成正比，则的值在两个特征值相等时最小，随r的增长而增长。值越大，说明两个特征值的比值越大，即在某一个方向的梯度值越大，而在另一个方向的梯度值越小，而边缘恰恰就是这种情况。所以为了剔除边缘响应点，需要让该比值小于一定的阈值，因此，为了检测主曲率是否在某域值r下，只需时将关键点保留，反之剔除。在Lowe的文章中，取r＝10。

关键点方向分配

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

【注】：通过求每个极值点的梯度来为极值点赋予方向。

像素点的梯度表示：

梯度幅值：

梯度方向：

确定关键点的方向采用梯度直方图统计法，统计以关键点为原点，一定区域内的图像像素点对关键点方向生成所作的贡献。

关于方向直方图的几点说明：

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

如下图所示，直方图的峰值方向代表了关键点的主方向，(为简化，图中只画了八个方向的直方图)：

方向直方图的峰值代表了该特征点处邻域梯度的方向，以直方图中最大值作为该关键点的主方向。为了增强匹配的鲁棒性，只保留峰值大于主方向峰值80％的方向作为该关键点的辅方向。因此，对于同一梯度值的多个峰值的关键点位置，在相同位置和尺度将会有多个关键点被创建但方向不同。仅有15％的关键点被赋予多个方向，但可以明显的提高关键点匹配的稳定性。实际编程实现中，就是把该关键点复制成多份关键点，并将方向值分别赋给这些复制后的关键点，并且，离散的梯度方向直方图要进行插值拟合处理，来求得更精确的方向角度值。

方向分配实现步骤：

确定计算关键点直方图的高斯权重函数参数
生成含有36个柱的方向直方图，梯度直方图范围0~360度，其中每10度一个柱（由半径为图像区域生成）
对方向直方图进行两次平滑
求取关键点方向（可能是多个方向）
对方向直方图的Taylor展开式进行二次曲线拟合，精确关键点方向

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

关键点描述

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

SIFT描述子是关键点邻域高斯图像梯度统计结果的一种表示。描述的思路是：通过对关键点周围图像区域分块，计算块内梯度直方图，生成具有独特性的向量，这个向量是该区域图像信息的一种抽象，具有唯一性。

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

Lowe实验结果表明：描述子采用4×4×8＝128维向量表征，综合效果最优（不变性与独特性）。

`128`维关键点描述子生成步骤*

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

特征描述子与特征点所在的尺度有关。因此，对梯度的求取应在特征点对应的高斯图像上进行。将关键点附近的邻域划分为d*d(Lowe建议d=4)个子区域，每个子区域做为一个种子点，每个种子点有8个方向。每个子区域的大小与关键点方向分配时相同，即每个区域有个子像素，为每个子区域分配边长为的矩形区域进行采样。考虑到实际计算时，需要采用双线性插值，所需图像窗口边长为。在考虑到旋转因素(方便下一步将坐标轴旋转到关键点的方向)，如下图所示，实际计算所需的图像区域半径为：