特征提取算法（3）——SIFT特征提取算子

前言

1、高斯尺度空间GSS

2、高斯差分DOG

用DoG检测特征点
GSS尺度选择

3、图像金字塔建立

用前一个octave中的倒数第三幅图像生成下一octave中的第一幅图像
每层octave为什么生成s+3幅图像

4、高斯核性质在SIFT中的应用

5、除去不好的特征点

6、给特征点赋值一个128维方向参数

7、根据SIFT进行Match

8、补充

前言

SIFT算子是一种检测局部特征的算法，通过求一幅图中的特征点及其有关尺寸scale和方向orientation的描述子得到特征，进行图像特征点匹配，获得了良好效果。每个特征点的SIFT特征是128维向量，因此计算量巨大。

不变性：具有尺寸和旋转不变性，即改变旋转角度、图像亮度、拍摄视角，仍然能够得到好的检测效果。

改进型：PCA-SIFT，如名称所说“主成分SIFT特征”，主要提取了128维特征向量中的20个特征，大大减少了计算。

高斯尺度空间（GSS - Gauss Scale Space）

这是一个初始化操作，尺度空间理论目的是模拟图像数据的多尺度特征。唯一能产生尺度空间的核为高斯核函数（高斯卷积核是实现尺度变换的唯一线性核），所以我们将图像的尺度空间表示成一个函数L(x,y,σ)，它是由一个变尺度的高斯函数G(x,y,σ)与图像I(x,y)卷积产生的。即：

其中 G(x,y,σ) 是尺度可变高斯函数：

（x，y）是空间坐标，是尺度坐标。σ大小决定图像的平滑程度，大尺度对应图像的概貌特征，小尺度对应图像的细节特征。大的σ值对应粗糙尺度(低分辨率)，反之，对应精细尺度(高分辨率)。

高斯差分（DOG - Difference of Gauss）

为了有效的在尺度空间检测到稳定的关键点，提出了高斯差分尺度空间（DOG scale-space）。利用不同尺度的高斯差分核与图像卷积生成。

不同σ下图像尺度空间：

关于尺度空间的理解说明：2kσ中的2是必须的，尺度空间是连续的。在 Lowe的论文中，将第0层的初始尺度定为1.6（最模糊），图片的初始尺度定为0.5（最清晰）。在检测极值点前对原始图像的高斯平滑以致图像丢失高频信息，所以 Lowe 建议在建立尺度空间前首先对原始图像长宽扩展一倍，以保留原始图像信息，增加特征点数量。尺度越大图像越模糊。

为什么用DoG来检测特征点？

Lindeberg证明用σ²标准化的高斯拉普拉斯(∇²G, LOG, Laplacian of Gauss)有着真正的尺度无关的特性，而Mikolajczyk发现，相比于其他一系列函数（比如梯度，Hessian，Harris角点函数等），用σ²标准化的高斯拉普拉斯(σ²∇²G)有着更稳定的图像特征，因此σ²∇²G函数是我们理想的寻找特征点的函数。而在此，我们利用DoG来近似σ²∇²G。

　　通过热传导方程也可以帮助我们理解DoG与σ²∇²G之间的近似关系。由热传导方程可知（通常用t=σ²）:

对上式进行有限差分运算得：

因此

DoG = G(x, y, kσ) − G(x, y, σ) ≈ (k − 1)σ²∇²G

而常数项(k - 1)并不会影响极值的位置。所以DoG是σ²∇²G的近似。

对于使用DoG来近似σ²∇²G，有如下优点：

σ²∇²G需要使用两个方向的高斯二阶微分卷积核，而DoG直接使用高斯卷积核，省去了对卷积核的生成的运算量。
DoG保留了各个高斯尺度空间的图像，这样，在生成某一空间尺度的特征时，可以直接尺度空间图像，而无需重新再次生成该尺度的图像。

GSS尺度选择

DoG近似于(k − 1)σ²∇²G，对于常数k，即为相邻高斯尺度空间的两幅图像的尺度倍数，Lowe在文中提到，The approximation error will go to zero as k goes to 1, but in practice we have found that the approximation has almost no impact on the stability of extrema detection or localization for even signiﬁcant differences in scale, such as k = √2. 文中提到k值大小对于极值的检测没有什么影响。那么k究竟取多大呢？　　

　　We choose to divide each octave of scale space (i.e., doubling of σ) into an integer number, s, of intervals, so k = 2^1/s. We must produce s + 3 images in the stack of blurred images for each octave, so that ﬁnal extrema detection covers a complete octave. Adjacent image scales are subtracted to produce the difference-of-Gaussian images shown on the right. Once a complete octave has been processed, we resample the Gaussian image that has twice the initial value of σ (it will be 2 images from the top of the stack) by taking every second pixel in each row and column. The accuracy of sampling relative to σ is no different than for the start of the previous octave, while computation is greatly reduced.

图像金字塔建立

对于一幅图像I,建立其在不同尺度(scale)的图像，也成为子八度（octave），这是为了scale-invariant，也就是在任何尺度都能够有对应的特征点，第一个子八度的scale为原图大小，后面每个octave为上一个octave降采样的结果，即原图的1/4（长宽分别减半），构成下一个子八度（高一层金字塔）。

用前一个octave中的倒数第三幅图像生成下一octave中的第一幅图像？

根据图像金字塔可以看出来，同一octave相邻图像之间尺度为k倍的关系。由图像看出每层octave产生了5副图像，所以s=2，令k = 2^1/s=2^1/2。完成一层octave的处理后，对2σ的高斯图像进行二分重采样，得到下一个octave的第一幅图像。尺度大小为2σ的高斯函数模糊的图像总是处于该octave的倒数第三幅，总共一层octave为s+3幅图像，第n层即为kⁿσ₀(其中 n = 0,1,...,s,s+1,s+2. k = 2^1/s)，当n等于s时，kⁿσ₀ = 2σ₀，第s层即为倒数第三层。

由图片size决定建几个塔，每塔几层图像(S一般为3-5层)。0塔的第0层是原始图像(或你double后的图像)，往上每一层是对其下一层进行Laplacian变换（高斯卷积，其中σ值渐大，例如可以是σ, k*σ, k*k*σ…），直观上看来越往上图片越模糊。塔间的图片是降采样关系，例如1塔的第0层可以由0塔的第3层down sample得到，然后进行与0塔类似的高斯卷积操作。

LoG近似DoG找到关键点（检测DOG尺度空间极值点）

为了寻找尺度空间的极值点，每一个采样点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。

如图所示，中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。一个点如果在DOG尺度空间本层以及上下两层的26个领域中是最大或最小值时，就认为该点是图像在该尺度下的一个特征点,如图所示。

同一组中的相邻尺度（由于k的取值关系，肯定是上下层）之间进行寻找

s=3的情况

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

由上图可以看出，是S=3的情况。因此GSS中倒数第三幅尺度与下一个octave第一幅尺度相同，由图中红色矩形中的尺度度应为DoG中极值检测的图像。将各层红色矩形框的尺度依次排序，可发现其为以k = 2^1/s（即k = 2^1/3）为等比的连续尺度。所以极值检测是在一个连续变化的尺度空间中进行的。

每层octave为什么生成s+3幅图像

假设s=3，也就是每个塔里有3层，则k=2^1/s=2^1/3，那么按照上图可得Gauss Space和DoG space 分别有3个（s个）和2个（s-1个）分量，在DoG space中，1st-octave两项分别是σ,kσ; 2nd-octave两项分别是2σ,2kσ;由于无法比较极值，我们必须在高斯空间继续添加高斯模糊项，使得形成σ,kσ,k²σ,k³σ,k⁴σ，这样就可以选择DoG space中的中间三项kσ,k²σ,k³σ（只有左右都有才能有极值），那么下一octave中（由上一层降采样获得）所得三项即为2kσ,2k²σ,2k³σ，其首项2kσ=2^i/3=2^4/3。刚好与上一octave末项k³σ=2^3/3尺度变化连续起来，所以每次要在Gaussian space添加3项，每组（塔）共S+3层图像，相应的DoG金字塔有S+2层图像。

高斯核性质在SIFT中的应用

对于二维高斯卷积，有如下性质：

距离高斯核中心3σ距离外的系数很小，相对于3σ内的系数值可以忽略不计，所以只用(6σ + 1)*(6σ + 1)的面积计算卷积即可。
线性可分，二维高斯核卷积（计算次数O(n²*M*N)）效果等于水平和竖直方向的两个一维高斯核（计算次数O(n*M*N) + O(n*M*N)））累积处理的效果。n*n为滤波器大小，M*N图像大小
对一幅图像进行多次连续高斯模糊的效果与一次更大的高斯模糊可以产生同样的效果，大的高斯模糊的半径是所用多个高斯模糊半径平方和的平方根。例如，使用半径分别为 6 和 8 的两次高斯模糊变换得到的效果等同于一次半径为 10 （勾股定理）的高斯模糊效果。根据这个关系，使用多个连续较小的高斯模糊处理不会比单个高斯较大处理时间要少。

其中，性质3有助我们更快速的生成GSS。虽然两个小半径处理时间并不会比单个高斯较大半径处理的时间少，但相对于原图像，我们已经有一个小半径模糊过的图像，即可用另一小半径在现成的图像上进行模糊得到较大半径的模糊效果。例如尺度为σ₀的图像已经存在，我们要得到尺度为kσ₀的图像，即可只使用尺度为[(kσ₀)²-(σ₀)²]^1/2的核在尺度为σ₀的图像上进行模糊，即可得到尺度为kσ₀模糊的图像，同理可得到高斯尺度空间各层的图像，使得高斯尺度空间生产得更快。

除去不好的特征点

去掉DoG局部曲率非常不对称的像素。通过拟和三维二次函数以精确确定关键点的位置和尺度（达到亚像素精度），同时去除低对比度的关键点和不稳定的边缘响应点(因为DoG算子会产生较强的边缘响应)，以增强匹配稳定性、提高抗噪声能力，在这里使用近似Harris Corner检测器。

空间尺度函数泰勒展开式：

泰勒公式：

对上式求导,并令其为0,得到精确的位置, 得：

去除低对比度的点，求极值点处函数值，只取前两项可得：

，则特征点就保留下来，否则丢弃。

去除不稳定的边缘响应点，一个定义不好的高斯差分算子的极值在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。主曲率通过一个2×2 的Hessian矩阵H求出：

导数由采样点相邻差估计得到。D的主曲率和H的特征值成正比，令α为较大特征值，β为较小的特征值，则：

令α=γβ，则：

(r + 1)²/r的值在两个特征值相等的时候最小，随着r的增大而增大，因此，为了检测主曲率是否在某域值r下，只需检测：

if (α+β)/ αβ> (r+1)²/r, throw it out. 在Lowe的文章中，取r＝10。

6、给特征点赋值一个128维方向参数

上一步中确定了每幅图中的特征点，为每个特征点计算一个方向，依照这个方向做进一步的计算，利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。

为(x,y)处梯度的模值和方向公式。其中L所用的尺度为每个关键点各自所在的尺度。

至此，图像的关键点已经检测完毕，每个关键点有三个信息：位置，所处尺度、方向，由此可以确定一个SIFT特征区域。

在实际计算时，我们在以关键点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向。梯度直方图的范围是0～360度，其中每45度一个柱，总共8个柱, 或者每10度一个柱，总共36个柱。Lowe论文中还提到要使用高斯函数对直方图进行平滑，减少突变的影响。直方图的峰值则代表了该关键点处邻域梯度的主方向，即作为该关键点的方向。

直方图中的峰值就是主方向，其他的达到最大值80%的方向可作为辅助方向

该步中将建立所有scale中特征点的描述子（128维）

关键点描述子的生成

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

首先将坐标轴旋转为关键点的方向，以确保旋转不变性。以关键点为中心取8×8的窗口。

16*16的图中其中1/4的特征点梯度方向及scale，右图为其加权到8个主方向后的效果。

图左部分的中央为当前关键点的位置，每个小格代表关键点邻域所在尺度空间的一个像素，利用公式求得每个像素的梯度幅值与梯度方向，箭头方向代表该像素的梯度方向，箭头长度代表梯度模值，然后用高斯窗口对其进行加权运算。

图中蓝色的圈代表高斯加权的范围（越靠近关键点的像素梯度方向信息贡献越大）。然后在每4×4的小块上计算8个方向的梯度方向直方图，绘制每个梯度方向的累加值，即可形成一个种子点，如图右部分示。此图中一个关键点由2×2共4个种子点组成，每个种子点有8个方向向量信息。这种邻域方向性信息联合的思想增强了算法抗噪声的能力，同时对于含有定位误差的特征匹配也提供了较好的容错性。

同理，计算keypoint周围的16*16的window中每一个像素的梯度，而且使用高斯下降函数降低远离中心的权重。

每个4*4的1/16象限中，通过加权梯度值加到直方图8个方向区间中的一个，计算出一个梯度方向直方图。

这样就可以对每个feature形成一个4*4*8=128维的描述子，每一维都可以表示4*4个格子中一个的scale/orientation. 将这个向量归一化之后，就进一步去除了光照的影响。

7、根据SIFT进行Match

生成了A、B两幅图的描述子，（分别是k1*128维和k2*128维），就将两图中各个scale（所有scale）的描述子进行匹配，匹配上128维即可表示两个特征点match上了。实际计算中，为了增强匹配的稳健性，Lowe建议对每个关键点使用4×4共16个种子点来描述，这样对于一个关键点就可以产生128个数据，即最终形成128维的SIFT特征向量。此时SIFT特征向量已经去除了尺度变化、旋转等几何变形因素的影响，再继续将特征向量的长度归一化，则可以进一步去除光照变化的影响。

当两幅图像的SIFT特征向量生成后，下一步我们采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。取图像1中的某个关键点，并找出其与图像2中欧式距离最近的前两个关键点，在这两个关键点中，如果最近的距离除以次近的距离少于某个比例阈值，则接受这一对匹配点。降低这个比例阈值，SIFT匹配点数目会减少，但更加稳定。

为了排除因为图像遮挡和背景混乱而产生的无匹配关系的关键点,Lowe提出了比较最近邻距离与次近邻距离的方法,距离比率ratio小于某个阈值的认为是正确匹配。因为对于错误匹配,由于特征空间的高维性,相似的距离可能有大量其他的错误匹配,从而它的ratio值比较高。Lowe推荐ratio的阈值为0.8。但作者对大量任意存在尺度、旋转和亮度变化的两幅图片进行匹配，结果表明ratio取值在0. 4~0. 6之间最佳，小于0. 4的很少有匹配点，大于0. 6的则存在大量错误匹配点。(如果这个地方你要改进，最好给出一个匹配率和ration之间的关系图，这样才有说服力)作者建议ratio的取值原则如下:

ratio=0. 4　对于准确度要求高的匹配；
ratio=0. 6　对于匹配点数目要求比较多的匹配；
ratio=0. 5　一般情况下。
也可按如下原则:当最近邻距离<200时ratio=0. 6，反之ratio=0. 4。ratio的取值策略能排分错误匹配点。

8、补充

（1）局部特征

局部特征从总体上说是图像或在视觉领域中一些有别于其周围的地方，通常描述一块区域，具有高度可区分性。

局部特征的好坏直接会决定着后面分类、识别是否会得到一个好的结果。

（2）局部特征需要具备的特性

重复性

可区分性

准确性

数量以及效率

不变性

（3）局部特征提取算法SIFT

SIFT算法由D.G.Lowe 1999年提出，2004年完善总结。后来Y.Ke将其描述子部分用PCA代替直方图的方式，对其进行改进。

在尺度空间寻找极值点，提取位置，尺度，旋转不变量；

SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性；

独特性好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配；

多量性，即使少数的几个物体也可以产生大量SIFT特征向量；

可扩展性，可以很方便的与其他形式的特征向量进行联合；

（4）尺度空间理论

目的是模拟图像数据的多尺度特征；

其基本思想是在视觉信息图像信息处理模型中引入一个被视为尺度的参数, 通过连续变化尺度参数获得不同尺度下的视觉处理信息, 然后综合这些信息以深入地挖掘图像的本质特征。

（5）描述子生成过程

以极值点为中心，以此点所处于的高斯尺度sigma值作为半径因子。对于远离中心点的梯度值降低对其所处区域的直方图的贡献，防止一些突变的影响。对于远离中心点的梯度值降低对其所处区域的直方图的贡献，防止一些突变的影响。

（6）归一化处理

在求出4*4*8的128维特征向量后，此时SIFT特征向量已经去除了尺度变化、旋转等几何变形因素的影响。而图像的对比度变化相当于每个像素点乘上一个因子，光照变化是每个像素点加上一个值，但这些对图像归一化的梯度没有影响。因此将特征向量的长度归一化，则可以进一步去除光照变化的影响。对于一些非线性的光照变化，SIFT并不具备不变性，但由于这类变化影响的主要是梯度的幅值变化，对梯度的方向影响较小，因此作者通过限制梯度幅值的值来减少这类变化造成的影响。

（7）PCA-SIFT算法

PCA-SIFT与标准SIFT有相同的亚像素位置，尺度和主方向。但在第4步计算描述子的设计，采用的主成分分析的技术。

下面介绍一下其特征描述子计算的部分：

用特征点周围的41×41的像斑计算它的主元，并用PCA-SIFT将原来的2×39×39维的向量降成20维，以达到更精确的表示方式。

它的主要步骤为，对每一个关键点：在关键点周围提取一个41×41的像斑于给定的尺度，旋转到它的主方向；计算39×39水平和垂直的梯度，形成一个大小为3042的矢量；用预先计算好的投影矩阵n×3042与此矢量相乘；这样生成一个大小为n的PCA-SIFT描述子。

（8）128维关键点描述子生成步骤

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

描述子梯度方向直方图由关键点所在尺度的模糊图像计算产生。图像区域半径为：