SIFT算法与OpenCV源码详解（一）

本文为原创文章，未经允许不得转载。

尺度不变特征转换(Scale-invariant feature transform, SIFT)是目前最经典的特征提取算法之一，由David G. Lowe博士在其2004年的论文 Distinctive Image Features from Scale-Invariant 中提出。

这篇博客将介绍博主结合OpenCV源码学习SIFT算法时的一些心得体会。

01. 概述

SIFT算法作为一个非常经典和常用的特征提取算法，在网上已经有非常多的应用实例和第三方实现代码。

SIFT算法不仅是一种特征点搜寻算法，也是一种特征点描述算法。具有尺度、旋转、光照、平移不变性。提取的特征点数量较多（相较于SURF、ORB算法），计算时间略长（相较于SURF、ORB算法）。

02. 原理及步骤

SIFT算法一共分为四个步骤：

创建初始化图像 将原始图像变为32位灰度图，并利用双立方插值将尺寸放大两倍，进行最初的高斯模糊处理。

具体地，初始化图像的过程如下：

① 将原图转化为32为灰度图。

② 利用双立方插值法将灰度图放大两倍；

③ 将图像归一化；

④ 进行初始的高斯模糊处理。

高斯/差分金字塔建立 使用不同尺度的高斯卷积核对初始图像进行模糊化处理，缩小图像尺寸再不断进行高斯模糊，模拟物体离人眼距离变远的视觉效果。

具体地，建立高斯金字塔的过程如下：

① 确定金字塔的级数(Octave)： $o=\log(\min(w, h))-2$ ，其中 $w$ 和 $h$ 分别表示图像的宽和高。通常一张 $1920*1080$ 的图像生成的金字塔有8层。

② 确定金字塔每级的层数(Layer)：通常这个参数是自定义的，一般取值为3。每级高斯金字塔的层数为 $Layer+3$ 层。

③ 利用高斯卷积核对图像进行模糊处理，层数越大，高斯卷积核的方差越大，图像越模糊。

高斯卷积核

$G\left(x,y,\sigma\right)=\frac{1}{2\pi}\exp\left\{-\frac{x^2+y^2}{2\sigma^2}\right\}$

输入图像 $I\left(x,y\right)$ ，输出图像

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

每一层的尺度为

$k=2^{\frac{1}{Layer}}$

④ 调整图像大小，构建新一级图像，该级的每一层同样进行高斯模糊处理。

⑤ 直至构建所有高斯金字塔级数。最后的高斯金字塔尺寸为

$Octave\times\left(Layer+3\right)$

建立高斯差分金字塔：

① 每一级金字塔两幅相邻图像两两相减：

$\begin{align}D\left(x,y,\sigma\right)=&L\left(x,y,k\sigma\right)-L\left(x,y,\sigma\right)\\=&\left[G\left(x,y,k\sigma\right)-G\left(x,y,\sigma\right)\right]*I\left(x,y\right)\end{align}$

其中 $G\left(x,y,k\sigma\right)-G\left(x,y,\sigma\right)\approx\left(k-1\right)\sigma^2\nabla^2G$ ，相当于利用高斯金字塔的差分实现了拉普拉斯金字塔的效果，就可以在这个金字塔上检测极值点了。

② 最终得到尺寸为 $Octave\times\left(Layer+2\right)$ 的高斯差分金字塔。

图1. 高斯金字塔和高斯差分金字塔示意图。图中左侧高斯金字塔中展示了两级，每级5层，即定义layer=2，每层之间相减得到右侧的高斯差分金字塔。（图片来源：Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International journal of computer vision, 2004, 60(2): 91-110.）

特征点检测 特征点的检测是SIFT中最核心的步骤，借助2.中生成的高斯差分金字塔，在每一级金字塔中有 $\left(Layer+2\right)$ 层，只在中间的 $Layer$ 层寻找极值点。

具体地，寻找极值点的过程可以分为：确定极值点的位置、尺度和方向三个步骤。

3.1 确定极值点的位置

① 只考虑每一级金字塔中间 $Layer$ 层的图像，即 $1\leq l\leq Layer$ 。若当前像素点是周围8个像素点和上下层各9个像素点（共26个像素点）的极值时，认为该点为极值点。

图2. 当前像素点与其周围8个像素点和上下级相同位置及周围各9个像素点进行比较。（图片来源：Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International journal of computer vision, 2004, 60(2): 91-110.）

② 由于图像像素位置是离散的，缩小尺寸的图像上找到极值点的位置在放大之后并不一定对应着原图极值点的位置，因此还需要利用插值算法迭代计算寻找真实的极值点位置。

令 ${\mathbf x} =\left(x,y,\sigma\right)$ ，差分图像的泰勒二级展开为

$\begin{equation}\mathbf D\left(\mathbf x\right) = {\mathbf D}+ \frac{\partial {\mathbf D}^T }{\partial {\mathbf x} }{\mathbf x} +\frac{1}{2} {\mathbf x}^T \frac{\partial^2 {\mathbf D}^T }{\partial {\mathbf x}^2 }{\mathbf x} \end{equation}$

上式对 $\begin{equation}\mathbf x\end{equation}$ 求导并令 $\begin{equation} \frac{\partial \mathbf D^T }{\partial \mathbf x } =0 \end{equation}$ ，得到

$\begin{equation} \hat{\mathbf x}= - \frac{\partial^2 {\mathbf D} ^{-1} }{\partial \mathbf x ^2 } \frac{\partial \mathbf D }{\partial \mathbf x} \end{equation}$

在论文中定义如果 ${\hat{\mathbf x}}$ 的偏移量小于0.5则认为极值点得到正确插值。

3.2 确定极值点的尺寸

① 极值点的尺寸由发现极值点的级和层决定：
$scale = \sigma_0 * 2^{o+\frac{l+\Delta l}{Layer}}$
其中 $\sigma_0$ 为初始尺度因子， $\Delta l$ 为3.1中极值点位置插值时层数的偏移量。

② 由于在初始化图像时原始图像被放大了两倍，计算特征点尺寸后需要除以2。

3.3 确定极值点的方向

在高斯差分金字塔中获得极值点的确切位置后，极值点的方向在高斯金字塔中计算。

① 确定搜寻半径，搜寻半径与极值点的尺寸有关。

② 统计在搜寻半径内的像素点的提取方向，以 $10°$ 为一格，共划分为36个bins的直方图，以梯度模值进行叠加。

③ 平滑直方图，采用下列式子对得到的直方图进行平滑处理：
$i = i + 0.5 * \frac{h\left[i-1\right]-h\left[i+1\right]}{h\left[i-1\right]-2*h\left[i\right]+h\left[i+1\right]}$
需要注意 $i$ 的取值范围限制在 $[0,36)$ 之间。

④ 找到直方图中最大值的横坐标，即对应的角度。若直方图某个bin的值为局部极值点且大于0.8倍最大值，则认为是该极值点候选的方向，一个极值点可以有多个候选方向。

⑤ 对候选方向进行插值处理，插值算法为：
$i = i + 0.5 * \frac{h\left[i-1\right]-h\left[i+1\right]}{h\left[i-1\right]-2*h\left[i\right]+h\left[i+1\right]}$
需要注意 $i$ 的取值范围限制在 $[0,36)$ 之间。

⑥ 若极值点有多个候选方向，则在相同位置拆成多个极值点。

4. 特征点描述。

① 为了实现旋转不变性，首先根据特征点的方向将图像进行旋转。

② 计算旋转之后的半径范围，并分成一个 $4\times 4$ 的区域。

图3. 以特征点为中心划分搜索半径子区域，上图划分2×2子区域，每个区域统计梯度直方图信息，得到关键点描述子共2×2×8=32维向量描述子。

③ 计算每一个区域内像素的梯度分布，以 $45°$ 为间隔，即8个bins构建梯度直方图。

④ 得到 $4\times 4\times 8$ 的向量，并进行插值处理。

⑤ 减少光照强度对特征点描述的影响，对上述128维向量进行归一化处理。

至此，SIFT算法的基本原理及实现过程介绍完毕。

03. 总结

SIFT算法通过构建高斯差分金字塔近似拉普拉斯金字塔计算图像中的极值，由于构建了图像金字塔，SIFT算法具有良好的尺度不变性。另一方面，高斯差分金字塔的建立和逐层级寻找极值点极大地增强了SIFT算法的时空消耗。

通过确定特征点的主方向，根据主方向旋转再计算特征点的描述子，使SIFT算法具有旋转不变性，在物体发生旋转时也具有良好的效果。

此外，由于SIFT建立初始化图像时对图像进行了灰度化处理，丢失了颜色信息，结构纹理相近但颜色不同的像素可能表现出一致的描述分布，在某些特定的情况下会造成错误的估计和描述。并且当图像出现较大仿射变换时SIFT算法也会出现明显地检测和描述不一致。

SIFT算法作为一种经典算法，衍生出了许多变体，包括ASFIT，改善SIFT算法仿射不变性，CSIFT，改善SIFT的没有考虑颜色信息等。

最后更新于2021年11月28日

感谢阅读！

SIFT算法与OpenCV源码详解（一）

01. 概述

02. 原理及步骤

03. 总结

推荐阅读更多精彩内容