vSLAMNet（三）-特征点-SIFT算法

发表于 | 分类于 ，

1. 概述

  • SIFT（Scale Invariant Feature Transform）算法由Lowe于1999年提出并于2004年得到了改善。其是一种局部特征描述算子，称为尺度不变特征变换。SIFT算子把图像中检测到的特征点用一个128维的特征向量进行描述。因此一幅图像经过SIFT算法后表示为一个128维的特征向量集。该特征向量集具有对图像缩放，平移，旋转不变的特征，对于光照、仿射和投影变换也有一定的不变性，是一种非常优秀的局部特征描述算法

  • 文献

    • Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International journal of computer vision, 2004, 60(2): 91-110.

  • 主要思想

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

  • 主要步骤

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

2. 尺度空间理论

2.1 尺度空间定义

  • 尺度空间(scale space)思想最早是由Iijima于1962年提出的，后经witkin和Koenderink等人的推广逐渐得到关注，在计算机视觉邻域使用广泛。

  • 基本思想

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

尺度空间应满足视觉不变性：

  • 灰度不变性
    • 图像的亮度水平
  • 对比度不变性
    • 图像的对比度水平
  • 平移不变性、尺度不变性、欧几里德不变性以及仿射不变性
    • 相对于某一固定坐标系，当观察者和物体之间的相对位置变化时，视网膜所感知的图像的位置、大小、角度和形状是不同的，因此要求尺度空间算子对图像的分析和图像的位置、大小、角度以及仿射变换无关

2.2 尺度空间的表示

经过前人证明，尺度空间内核是高斯函数。

假设$I(x, y)$为原图像，$G(x, y, \sigma)$为尺度空间可变的高斯函数，那么该图像的尺度空间可由下式计算：

,

其中，$*$表示卷积运算，$\sigma$表示尺度空间的大小，越大表示越模糊，显示图像的概貌，越小图像越清晰，显示图像的细节，$(x, y)$表示图像的像素位置。高斯函数定义如下：

.

关于图像的高斯狙击操作参考XXX。

3. 关键点检测

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

image-20200328175119836

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

image-20200328175459744

（图片来源：https://cloud.tencent.com/developer/article/1081140）

4. 消除错配点

  • 由于DoG值对噪声和边缘较敏感，因此，在上面DoG尺度空间中检测到局部极值点还要经过进一步的检验才能精确定位为特征点
  • 为了提高关键点的稳定性，需要对尺度空间DoG函数进行曲线拟合
  • 利用DoG函数在尺度空间的Taylor展开式

$D(X) = D + \frac{\partial D^T}{\partial X} + \frac{1}{2}X^T\frac{\partial^2 D}{\partial X^2}X$.

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

$\hat{x} = -\frac{\partial^2 D^{-1}}{\partial x^2}\frac{\partial D}{\partial x}$.

  • 在已经检测到的特征点中,要去掉低对比度的特征点和不稳定的边缘响应点。去除低对比度的点：把上式代入其中，即在DoG Space的极值点处D(x)取值，只取前两项可得

$D(\hat{x}) = D + \frac{1}{2}\frac{\partial D^T}{\partial x}\hat{x}$.

  • 如果$|D(\hat{x})| \geq 0.03$，该特征点就保留下来，否则丢弃

5. 边缘响应的去除

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

$H = \left[\begin{matrix} D_{xx} & D_{xy} \\ D_{xy} & D_{yy} \end{matrix}\right]$.

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

6. 特征点的主方向

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

$m(x, y) = \sqrt{(L(x + 1, y) - L(x - 1, y)^2 + (L(x, y + 1) - L(x, y - 1))^2}$,

$\theta(x, y) = \tan^{-1}((L(x, y + 1) - L(x, y - 1)) / (L(x + 1, y) - L(x - 1, y)))$.

其中，$m(x, y)$表示梯度赋值，$\theta(x, y)$表示梯度朝向。

  • 其中L所用的尺度为每个关键点各自所在的尺度。
  • 图像的关键点已经检测完毕，每个关键点有三个信息：位置，所处尺度、方向，由此可以确定一个SIFT特征区域
  • 在实际计算时，我们在以关键点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向。梯度直方图的范围是0～360度，其中每45度一个柱，总共8个柱, 或者每10度一个柱，总共36个柱。Lowe论文中还提到要使用高斯函数对直方图进行平滑，减少突变的影响。直方图的峰值则代表了该关键点处邻域梯度的主方向，即作为该关键点的方向
  • 直方图中的峰值就是主方向，其他的达到最大值80%的方向可作为辅助方向，通过对关键点周围图像区域分块，计算块内梯度直方图，生成具有独特性的向量，这个向量是该区域图像信息的一种抽象，具有唯一性。首先将坐标轴旋转为关键点的方向，以确保旋转不变性。以关键点为中心取8×8的窗口
  • 得到特征点的主方向后，对于每个特征点可以得到三个信息$(x, y, \sigma, \theta)$，即位置、尺度和方向。由此可以确定一个SIFT特征区域，一个SIFT特征区域由三个值表示，中心表示特征点位置，半径表示关键点的尺度，箭头表示主方向。具有多个方向的关键点可以被复制成多份，然后将方向值分别赋给复制后的特征点，一个特征点就产生了多个坐标、尺度相等，但是方向不同的特征点

7. 生成特征描述

  • 这个描述符不只包含特征点，也含有特征点周围对其有贡献的像素点
  • 描述子应具有较高的独立性，以保证匹配率
  • 特征描述符的生成
    • 校正旋转主方向，确保旋转不变性
    • 描述子，最终形成一个128维的特征向量
    • 归一化处理，将特征向量长度进行归一化处理，进一步去除光照的影响
  • 为了保证特征矢量的旋转不变性，要以特征点为中心，在附近邻域内将坐标轴旋转θθ（特征点的主方向）角度，即将坐标轴旋转为特征点的主方向。旋转后邻域内像素的新坐标为

$\left[\begin{matrix} x’ \\ y’ \end{matrix}\right]= \left[\begin{matrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{matrix}\right]\left[\begin{matrix} x \\ y \end{matrix}\right] $.

  • 旋转后以主方向为中心取8×8的窗口。下图所示，左图的中央为当前关键点的位置，每个小格代表为关键点邻域所在尺度空间的一个像素，求取每个像素的梯度幅值与梯度方向，箭头方向代表该像素的梯度方向，长度代表梯度幅值，然后利用高斯窗口对其进行加权运算。最后在每个4×4的小块上绘制8个方向的梯度直方图，计算每个梯度方向的累加值，即可形成一个种子点，如右图所示。每个特征点由4个种子点组成，每个种子点有8个方向的向量信息。这种邻域方向性信息联合增强了算法的抗噪声能力，同时对于含有定位误差的特征匹配也提供了比较理性的容错性

image-20200328181819566

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

image-20200328184403372

  • 如上统计的4×4×8=128个梯度信息即为该关键点的特征向量。特征向量形成后，为了去除光照变化的影响，需要对它们进行归一化处理

8. 匹配

  • 生成了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

9. 总结和讨论

  • DoG尺度空间的极值检测
  • 删除不稳定的极值点
  • 确定特征点的主方向
  • 生成描述子

10. 代码实现

  • OpenCV
1
2
3
4
5
6
7
8
9
10
11
12
13
import cv2
import numpy as np

img = cv2.imread('1.jpg')
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
sift = cv2.xfeatures2d.SIFT_create()

kp = sift.detect(gray,None)

img = cv2.drawKeypoints(gray, kp, img)

cv2.imshow('Image', img)
cv2.waitKey(0)

11. 参考