IT小白

这个屌丝很懒，什么也没留下！

热门标签

如何快速入门sift算法_离散空间极值点与连续空间极值点

作者：IT小白 | 2024-02-23 08:14:14

踩

离散空间极值点与连续空间极值点

SIFT：即尺度不变特征变换（Scale-invariant feature transform，SIFT），是用于图像处理领域的一种描述。这种描述具有尺度不变性，可在图像中检测出关键点，是一种局部特征描述子。

该算法将斑点检测和特征矢量生成、特征匹配搜索等其他步骤完整结合在一起进行优化!

一、DoG尺度空间生成

将图像的尺度空间表示成一个函数L(x,y,σ)，它是由一个高斯滤波器与原图像卷积而生成的图像，即L(x,y,σ)=G(x,y,σ)⊗I(x,y)。一系列的σi，则可以生成一系列L(x,y,σi)图像，此时我们把这一系列的L(x,y,σ)图像称为原图像的一个尺度空间表示。

下图是5*5的高斯模板卷积计算示意图。高斯模板是中心对称的。

----------->>>>何为尺度空间，快点我去了解？

I(x,y)表示原图像。

G(x,y,σ)表示高斯滤波器

在sift算法中，提议在某一个尺度上对斑点的检测，可以通过两个相邻高斯尺度空间的图像相减，得到一个DoG的响应值图像D(x,y,σ)

(3.4)

上面特别值得注意的是尺度为σ的高斯差分图像由于尺度为kσ与尺度为σ的L图像生成的。k为两相邻尺度空间倍数的常数。

然后参照LoG的方法，对响应值图像D(x,y,σ)进行非极大值抑制（局部最大值搜索）；在位置空间和尺度空间定位斑点；

事实上DoG是对LoG（高斯拉普拉斯方法）方法的一种近似，DoG的响应值是对

的一种近似，可以通过两者的二维曲线看出；如下图3.2

然后通过热传导方程可知：t = σ^2

然后在上式的基础上进行有限差分运算，得到

其中k-1是个常数，并不影响极值点位置的求取。

在实际计算时，使用高斯金字塔每组中相邻上下两层图像相减，得到高斯差分图像；如下图3.3所示，进行极值检测得到DoG

DoG通过构建图像高斯金字塔实现；将图像金字塔共分为O组（octave），每组有S层（level），下一组的图像是由上一组的图像按照隔点降采样（就是对图像降2倍分辨率）得到，这样做可以减少计算量，有点类似于卷积神经网络中的池化层的操作！

上述图中每个组由五层不同尺度空间的图像组成，相邻两层图像相减后得到四层的DoG结果；然后斑点检测就是在这四层DoG上进行的；其中的图像相减就是简单的减法操作，别想太复杂了！

使用DoG对LoG近似带来的好处有哪些呢？

LoG是使用两个方向的高斯二阶微分卷积核，而DoG是直接使用高斯卷积和，省去了对卷积和的生成的运算量；
DoG保留了各个高斯尺度空间的图像，这样在生成某一空间尺度的特征时，可以直接使用L(x,y,σ)=G(x,y,σ)⊗I(x,y)产生尺度空间图像。无需再次生成该尺度的图像；
LoG对斑点检测较其他检测方法来说比较稳定，抗噪声能力强，DoG是对LoG的近似和简化，因此和LoG有相同的性质；

具体如何构建高斯差分金字塔呢？我们继续往下面看！

二、高斯差分金字塔构建

在构建高斯金字塔时首先要确定尺度空间的各种参数；

尺度空间参数：σ

octave组数：O

每组的层数：S

在尺度空间中σ和O、S的关系如下：

其中σ0表示基准层尺度，O为组octave的索引，S为组内层的索引。关键点的尺度坐标就是按关键点所在的组和组内的层

第一组第一张图像是如何生成的？

这里要分两种情况：其一是把第一组的索引定为0；其二是把第一组的索引定为-1。

1、当索引为0时，我们知道第一组第一层的图像是由原图像与σ0（一般设置为1.6）的高斯滤波器卷积生成，那么原图像是谁呢？是I(x,y)吗？不是！为了图像反走样的需要，通常假设输入图像是经过高斯平滑处理的，其值为σn=0.5，即半个像元。意思就是说我们采集到的图像I(x,y)，已经被σ=σn=0.5的高斯滤波器平滑过了。所以我们不能直接对I(x,y)用σ0的高斯滤波器平滑，而应该用 $\sigma = \sqrt{\sigma_0^2 - \sigma_n^2}$ 的高斯滤波器去平滑I(x,y)，即

$FirstLayer(x,y) = I(x,y)\otimes G(x,y,\sqrt{\sigma_0^2 - \sigma_n^2})$

其中FirstLayer(x,y)表示整个尺度空间为第1组第1层的图像，σo一般取1.6，σn=0.5。

2、第一组的索引定为-1的情况。那么首先第一个问题便是为什么要把索引定为-1。如果索引为0，如上面那种情况所示，整个尺度空间的第1组的第1层图像已经是由原图像模糊生成的了，那么也就是说已经丢失了细节信息，那么原图像我们完全没有利用上。基于这种考虑，我们先将图像放大2倍，这样原图像的细节就隐藏在了其中。由上面一种情况分析，我们已经知识了I(x,y)看成是已经被σn=0.5模糊过的图像，那么将I(x,y)放大2倍后得到Is(x,y)，则可以看为是被2σn=1的高斯核模糊过的图像。那么由Is生成第1组第1层的图像用的高斯滤波器的 $\sigma = \sqrt{\sigma_0^2 - (2_\sigma_n)^2}$ 可以表示为。

$FirstLayer(x,y) = I_s(x,y)\otimes G(x,y,\sqrt{\sigma_0^2 - (2\sigma_n)^2})$

其中FirstLayer(x,y)表示整个尺度空间为第1组第1层的图像，Is(x,y)是由I(x,y)用双线性插值放大后的图像。σo一般取1.6，σn=0.5。

对上述总结：octave索引可能为负值，第一组索引通常设为0或者-1，当设为-1时，图像在计算高斯空间前先将尺度扩大一倍。为了图像反走样的需要，通常假设输入图像是经过高斯平滑处理的，其中sigma_n=0.5，即半个像元，但在组O=-1，图像使用双线性插值扩大一倍，此时的sigma_n=1.0

取式(3.4)中的k为组内总层数的倒数，即

3.6

在构建高斯金字塔时，组内每层的尺度坐标按如下公式计算：

3.7

其中初始尺度，lowe取，s为组内的层索引，不同组相同层的组内尺度坐标相同。组内下一层图像是由前一层图像按进行高斯模糊所得。式(3.7)用于一次生成组内不同尺度的高斯图像，而在计算组内某一层图像的尺度时，直接使用如下公式进行计算：

3.8

该组内尺度在方向分配和特征描述时确定采样窗口的大小。

由上，式(3.4)可记为

(3.9)

图3.5为构建DOG金字塔的示意图，原图采用128*128的jobs图像，扩大一倍后构建金字塔。

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

取上一张的倒数第3张图像隔行采样后作为下一组的第一张图像？

为什么用第i-1层的图像生成第i层的图像？

请看这位博主的讲解：尺度空间生成了多少幅图像？

三、特征点的搜索与定位

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

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

图4.6 在DoG中极值点的搜索与定位

以上极值点的搜索都是在离散空间中进行的，检测到的极值点并不是真正意义上的极值点。如下图4.7所示

图4.7 离散空间极值点与连续空间极值点之间的关系

利用已知的离散空间点插值得到连续空间极值点的方法叫做子像元插值。

如何进行子像元插值？

请看这位博主的讲解：子像元插值

如何删除边缘效应？

一个定义不好的高斯差分算子的极值在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。

DOG算子会产生较强的边缘响应，需要剔除不稳定的边缘响应点。获取特征点处的Hessian矩阵，主曲率通过一个2x2 的Hessian矩阵H求出：

(4-4)

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

(4-5)

表示矩阵H对角线元素之和，表示矩阵H的行列式。假设是α较大的特征值，而是β较小的特征值，令，则

(4-6)

导数由采样点相邻差估计得到,在下一节中说明。

D的主曲率和H的特征值成正比，令为α最大特征值，β为最小的特征值，则公式的值在两个特征值相等时最小，随着的增大而增大。值越大，说明两个特征值的比值越大，即在某一个方向的梯度值越大，而在另一个方向的梯度值越小，而边缘恰恰就是这种情况。所以为了剔除边缘响应点，需要让该比值小于一定的阈值，因此，为了检测主曲率是否在某域值r下，只需检测

(4-7)

式(4-7)成立时将关键点保留，反之剔除。

在Lowe的文章中，取r＝10。图4.2右侧为消除边缘响应后的关键点分布图。

四、特征点方向分配

为了使描述符具有旋转不变性，需要利用图像的局部特征为给每一个关键点分配一个基准方向。使用图像梯度的方法求取局部结构的稳定方向。对于在DOG金字塔中检测出的关键点点，采集其所在高斯金字塔图像3σ邻域窗口内像素的梯度和方向分布特征。梯度的模值和方向如下：

(5-1)

L为关键点所在的尺度空间值，按Lowe的建议，梯度的模值m(x,y)按的高斯分布加成，按尺度采样的3σ原则，邻域窗口半径为。

在完成关键点的梯度计算后，使用直方图统计邻域内像素的梯度和方向。梯度直方图将0~360度的方向范围分为36个柱(bins)，其中每柱10度。如图5.1所示，直方图的峰值方向代表了关键点的主方向，(为简化，图中只画了八个方向的直方图)。

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

至此，将检测出的含有位置、尺度和方向的关键点即是该图像的SIFT特征点。

关键点特征描述

通过以上步骤，对于每一个关键点，拥有三个信息：位置、尺度以及方向。接下来就是为每个关键点建立一个描述符，用一组向量将这个关键点描述出来，使其不随各种变化而改变，比如光照变化、视角变化等等。这个描述子不但包括关键点，也包含关键点周围对其有贡献的像素点，并且描述符应该有较高的独特性，以便于提高特征点正确匹配的概率。

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

Lowe建议描述子使用在关键点尺度空间内4*4的窗口中计算的8个方向的梯度信息，共4*4*8=128维向量表征。表示步骤如下：

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

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

(6-1)

计算结果四舍五入取整。

2. 将坐标轴旋转为关键点的方向，以确保旋转不变性，如6.2所示。

旋转后邻域内采样点的新坐标为：

(6-2)

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

旋转后的采样点坐标在半径为radius的圆内被分配到的子区域，计算影响子区域的采样点的梯度和方向，分配到8个方向上。

旋转后的采样点落在子区域的下标为

(6-3)

Lowe建议子区域的像素的梯度大小按的高斯加权计算，即

(6-4)

其中a，b为关键点在高斯金字塔图像中的位置坐标。

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

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