CV-特征提取-SIFT算法

CV-特征提取-SIFT算法

基于Distinctive Image Features from Scale-Invariant Keypoints对SIFT算法的理论部分笔记。
There is nothing permanent except change. --Heracleitus

0. 信息

​ SIFT(尺度不变特征变换,Scale-invariant Feature Transform),是在图像中检测关键点的方法,是一种局部特征描述子。是由David Lowe在1999年提出,然后在2004年又重新整理完善的。

​ 从引用数可以很直接地看出该方法的重要性和价值。本文的内容主要基于04年的这篇论文的描述,然后使用OpenCV尝试实现。

1. 简介

【研究背景与概述】

  • 图像匹配是计算机视觉中许多问题的关键,如目标和场景识别、运动追踪、图像拼接等等。其中图像的特征提取很为重要,其中局部兴趣点(local interest points)的应用最早可以追溯到1981年Moravec在立体匹配中使用的角探测器(corner detector),之后被Harris和Stephens改进。
  • Harris角探测器不仅是能选择角,还能在一个确定尺度的各个方向上选择所有具有大的梯度的位置。但是,其对图像尺度的变化非常敏感,因此,对于不同尺度的图像匹配,Harris角探测器并不能提供很好的基础。
  • 而本文的SIFT方法虽然不具备完全的仿射不变性,但使用了一种独特的方法来使局部描述子可以随着很小的变化来显著地改变相关特征的位置,对图像的尺度和旋转具有不变性。这种方法不仅使描述子可以在相当大范围的仿射变形时进行可靠的匹配、跨越三位视点的变化,而且对添加的噪声和光照变化的图像匹配具有鲁棒性。
  • 另外本文还基于SIFT方法,通过将个别特征与由已知目标特征组成的数据库进行快速最近邻算法的匹配,然后使用Hough变换来识别属于单一目标的聚类,最后通过最小二乘解执行一致的参数核查确认。这种方法可以在有力确定对象之间的聚类和遮挡的同时实现近实时性能。

【SIFT概述】

​ 本文提出的SIFT特征检测方法主要包含以下四步:

  1. 尺度空间极值探测(Scale-space extrema detection):对整个尺度和图像位置进行搜索,通过高斯差分函数有效地识别对于尺度和方向具有不变性的可能的兴趣点。
  2. 关键点定位(Keypoint localization):在每一个候选区,确定一个详细模型的位置和尺度,并基于关键点的稳定性进行选择。
  3. 定向任务(Orientation assignment):基于局部图像的梯度方向,给每个关键点指定一个或多个方向。之后的所有图像操作都是将每个特征的方向、尺度和位置进行变换得到的,因此这些变换具有不变性。
  4. 关键点描述子(Keypoint descruptor):局部梯度是在每个关键点附近的区域所选尺度上测得的,这些梯度可以转化成一个允许显著的局部形状变化和光照变化的表示法。

​ SIFT方法可以基于局部特征把图像数据转换到尺度不变的坐标上,该方法生成了大量的特征,这些特征密集地覆盖了整个图像尺度和位置。

2. SIFT步骤一:尺度空间极值探测

【尺度空间】

  • 尺度空间

    • 关键点探测的第一步是识别统一目标在不同视角下可被重复分配的位置和尺度。
    • 使用被称为尺度空间的尺度连续函数,通过搜索对所有尺度的稳定特征,可以探测对图像尺度变换具有不变性位置的探测。
  • 高斯函数

    • Koenderink(1984)和Lindeberg(1994)通过一系列合理的假设,说明尺度空间的唯一可行核(kernel)是高斯函数(Gaussian function)。
    • 定义一幅图像尺度空间函数:$L(x,y,\sigma)=G(x,y,\sigma)*I(x,y)$

      • $G(x,y,\sigma)$:尺度可变的高斯函数,$G(x,y,\sigma)=\frac{1}{2\pi\sigma^2}e^{-(x^2+y^2)/2\sigma^2}$;
      • $I(x,y)$:输入图像;
      • $*$:卷积运算。
    • 为高效探测稳定的关键点位置,假设使用尺度空间在高斯差分中的极值与图像卷积,可以计算得到两个相邻的由常数乘系数$k$分离的尺度的差值:

      • $D(x,y,\sigma)=(G(x,y,k\sigma)-G(x,y,\sigma))*I(x,y)=L(x,y,k\sigma)-L(x,y,\sigma)$
    • 优点:

      • 计算高效 ($D$只需计算简单的图像减法,而$L$则需要计算尺度空间特征描述的任何情况);
      • 高斯差分函数可以提供高斯拉普拉斯的尺度规范化解的近似值。$k$越接近1,估计误差就越接近于0,但实际中发现估值对极值探测的稳定性和尺度差距的定位几乎没有影响,如$k=\sqrt{2}$ (这里作者给出了证明,有兴趣可以自行查看论文)。
  • 构建$D(x,y,\sigma)$的有效方法

    • 构建方法如图所示,初始图像与高斯函数递增地卷积形成图像,通过尺度空间的常系数$k$被分开。
    • 将尺度空间中的每个组(如$\sigma$的两倍)分为整数,间距为$s$,所以$k=2^{1/s}$。
    • 在每个组的堆中建立$s+3$幅模糊的图像才能完成覆盖全部组的极值探测,临近的图像尺度相减就形成了高斯差分图像。
    • 完成了所有组的处理后,使用$\sigma$代替初始值$2\sigma$(顶层的堆中会产生2幅图像),以每行每列的第二个像素对高斯图像进行重采样。
    • 相对于$\sigma$,采样的精度与第一个组没有差别,但计算量被很大程度上降低了。

01-01.png

【局部极值探测】

  • 为探测$D(x,y,\sigma)$的局部最大值和最小值,每个样本点需要和当前图像的八个邻域与上下尺度图像各自的九个邻域进行比较,只有当此样本点比所有近邻大或小时才选择,如图所示。(前几次探测中大多数点已被排除,所以探测代价相对较小)

    01-02.png

    • 对每个样本点检查26个近邻点

【采样频率】

  • 图像和尺度空间中采样的频率很重要,但无法找到可以探测到所有极值的最小采样间隔,所以需要有一个权衡效率和完整性的方法。而相邻近的极值对图像很小的变化是不稳定的,可以通过对很大范围内采样频率的研究和在匹配任务中的逼真模拟得到的结果来决定最好的选择。
  • 尺度采样的频率

    • 采样的尺度不是越高重复率越好,在很多被探测到的局部极值结果重,尺度高的结果稳定性较差,因此在转换图像中被探测到的概率就降低了。
    • 采样尺度越大关键点数越多,虽然成功与否依赖于正确匹配的数量,而不是关键点数量过,但总体而言,对很多应用,选择较大的尺度采样才是最佳选择(本文实验中选择每组3个采样尺度)。
  • 空间域采样的频率

    • $\sigma$越大,关键点探测的重复率越大;
    • 如果在极值探测前对图像进行预平滑处理,就有效地剔除了最高的空间频率(在创建第一组的尺度空间前,增加销量的平滑是必要的)。

3. SIFT步骤二:关键点定位

  • 在尺度空间极值探测完成后,可以得到关键点的候选值,下一步根据附近数据位置、尺度和主曲率的细节配置(detailed fit)去除低对比度(对噪音敏感)的点或沿边缘的点。

【去除低对比度的点】

  • 最开始的版本[Lowe, 1999]只是简单地实现了关键点在相对中心样本点的位置和尺度上的定位,但在最近的改版中[Brown and Lowe, 2002],则通过局部样本点的三维二次方程配置来决定最大值的插值位置。这一改变提高了匹配的准确性和稳定性。
  • 首先,对尺度空间方程$D(x,y,\sigma)$进行二阶泰勒级数展开,把样本点作为原点,有

    • $D(x)=D+\frac{\partial D^T}{\partial x}x+\frac{1}{2}x^T\frac{\partial^2 D}{\partial x^2}x$
    • $D$和其导数是样本点的估值;$x=(x,y,\sigma)^T$是距离此点的偏移。
  • 极值的位置$\hat x$,是通过取这个函数关于$x$的导数,并将导数设为0来确定的:

    • $\hat x=-\frac{\partial^2D^{-1}}{\partial x^2}\frac{\partial D}{\partial x}$
    • 通过Hessian法和对$D$求导来估计,都是对相邻样本点使用差分来估计值,可以在成本最小的情况下得到$3*3$的线性系统结果。
    • 如果偏离值(offset)$\hat x$在任何维度都大于0.5,则意味着极值与另一个样本点很接近。在这种情况下,就用插值替换该采样点。
    • 将最终的偏移值$\hat x$加到采样点的位置,获得的就是极值位置的插值估计值。
  • 极值处的函数值$D(\hat x)$对去除低对比度的不稳定极值很有用,

    • $D(\hat x)=D+\frac{1}{2}\frac{\partial D^T}{\partial x}\hat x$
    • 本实验中,$D(\hat x)$小于$0.03$的都被去除。

【去除边缘反应】

  • 除去低对比度的关键点后,对稳定性而言,仍是不足。即便位于边缘处的点有很差的决策性并对少量的噪声很不稳定,高斯差分函数仍是有很强的反应。
  • 在高斯差分函数中定义不好的峰值会对边缘处产生很大的曲率(curvature),而在垂直方向上产生很小的主曲率。主曲率可以通过一个$2*2$的Hessian矩阵来计算,在关键点的位置和尺度上计算$H$:

    • $H=\begin{bmatrix}D_{xx}&D_{xy}\\D_{xy}&D_{yy}\end{bmatrix}$
    • 通过对近邻样本点的差分来估计导数值。
  • $H$的特征值与$D$的主曲率成比例。使用Harris和Stephens的方法,可以避免特征值的计算,而只关心它们的比值。设$\alpha$为最大量级的特征值,$\beta$为最小量级的。可以根据$H$的迹来获得特征值的和,从行列式获得它们的积。

    • ${\rm Tr}(H)=D_{xx}+D_{yy}=\alpha+\beta$
    • ${\rm Det}(H)=D_{xx}D_{yy}-(D_{xy})^2=\alpha\beta$
    • 行列式不为负,曲率符号不同时,点不是极值,舍去。
  • 设$r$是最大量级特征值与最小特征值的比,$\alpha=r\beta$,有,

    • $\frac{{\rm Tr}(H)^2}{{\rm Det}(H)}=\frac{(\alpha+\beta)^2}{\alpha\beta}=\frac{(r\beta+\beta)^2}{r\beta^2}=\frac{(r+1)^2}{r}$
    • 只取决于特征值的比而不是它们的值。
    • 当两个特征值相同时,$(r+1)^2/r$最小,并随$r$的增加而增加。
  • 要看主曲率是否低于某个极限,只需要检查,是否:

    • $\frac{{\rm Tr}(H)^2}{{\rm Det}(H)}<\frac{(r+1)^2}{r}$
    • 这个计算很高效,对每个关键点只需进行小于20次的浮点运算检测。
    • 实验中使用的$r$值为10,关键点在主曲率间的比值大于10。

【效果展示】

  • 去除低对比度的点和边缘点的效果如下图所示,

    01-03.png

    • 图a为$233\times189$像素点的原图;
    • 图b为经过高斯差分函数后的最大值和最小值,共832个关键点;
    • 图c为对最小值对比设置阈值后的点,共729个关键点;
    • 图d为附加曲率极限后,共536个关键点。

4. SIFT步骤三:定向任务

  • 通过局部图像属性给每一个关键点制定一个方向,使得关键点描述子与这个方向相关,从而实现旋转不变性。
  • 关键点的尺度选择最接近的高斯平滑图像$L$的,使所有的计算都是在尺度不变下进行。
  • 对每个图像样本$L(x,y)$,在此尺度下,梯度量级$m(x,y)$和方向$\theta(x,y)$通过像素差算出:

    • $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)))$
    • 值得注意的是,这一方法是通过实验在众多方法中选择的最多稳定结果的方法。

5. SIFT步骤四:局部图像描述子

  • 定向任务步骤后,确定了图像的位置、尺度和各个关键点的方向。

    • 使用关键点的尺度来选择图像高斯模糊的程度;
    • 描述子的坐标和梯度方向都是随关键点方向进行旋转。
  • 为局部图像计算描述子,为另外的变化(如光照、视点变换)提供不变性。

【描述子表示】

  • 描述子的计算方法如下图所示,

    01-04.png

    • 首先,计算关键点位置附近的每个样本点的梯度大小和方向;
    • 然后,由高斯窗口给定权重,将结果汇成方向直方图,每$4\times4$个子区域合成一个;
    • 描述子由保存所有方向直方图的值得到,对应于右图中箭头的长度。
  • 实验表明,每个方框由八个方向的$4*4$阵列的直方图得到的结果最佳,本文所用的每个关键点有$4*4*8=128$个像素特征矢量的。
  • 光照不变性:

    • 将矢量标准化为单位长度;
    • 对图像对比度的改变将每个像素乘以一个常数,使得整个梯度乘上一个常数,最终被归一化抵消;
    • 而亮度改变则是将每个像素加上一个常数,不影响梯度值,所以具有光照不变性。
    • 对由于相机饱和度或光照变化影响三维表面带来非线性光照变化,使每个单位特征向量不大于0.2,然后再对单位长度重新进行归一化。

【测试与实验】

  • 接下来的部分中,作者对描述子的方向数、阵列宽,仿射变换敏感程度和大型数据库中匹配情况进行了实验,如有需要可以自行查看论文。

6. 非SIFT部分

  • 紧接下来的部分中,作者介绍了在SIFT外的其他部分,实现了一个完整的匹配过程(这些方法不做深入的记录了,可能会记载在其他笔记中)。
  • 关键点匹配

    • NN 最近邻;
    • NNDR 更有效的方法;
    • 最近邻:每个关键点的不变描述子矢量的最短欧式距离。
  • 有效的最近邻函数

    • 穷搜索法(exhaustive search);
    • k-d树:无法在多于10维的空间中提供比穷搜索法更快的性能;
    • 最优盒算法(Best-Bin-Fist, BBF):一种k-d树算法的改进算法。
  • 霍夫变换的聚类

    • RANSAC、最小平方中值:在正常值小于50%时运算结果较差;
    • 而在pose空间中使用Hough转换的聚类特征可以有好的表现。
  • 仿射参数的解决方法

    • 霍夫转换是用来识别箱中至少有三个实体的所有聚类。
    • 每一个这样的聚类都要进入一个用最小二乘法来计算与训练图像向新图像转换有关的最佳的仿射投影参数的几何验证程序。
​ 在整个学习过程中,关于数学部分和光学图像方面有很多的地方有些疑惑的,笔记中有不少直接的翻译,笔记也不够凝练,还请见谅。

参考资料:

  1. Object Recognition from Local Scale-Invariant Features, ICCV 1999
  2. Distinctive Image Features from Scale-Invariant Keypoints, IJCV 2004
  3. Distinctive Image Features from Scale-Invariant Keypoints-SIFT算法译文

评论

暂无评论