本文最后更新于：14 天前

概述

  • SIFT的全称是Scale Invariant Feature Transform（尺度不变特征变换），是由加拿大教授David G.Lowe在1999年在会议文章中提出，2004年发表在IJCV上。
  • 是计算机视觉界近二十年来引用率最高的文章之一。
  • SIFT特征对旋转、尺度缩放、亮度变化等保持不发性，是一种稳定的局部特征。
  • SIFT的特征提取方面对计算机视觉近年来的发展影响深远，特别是几乎影响到了后续所有的角点提取和匹配算法。

算法特点

  • 图像的局部特征，对旋转、尺度缩放、亮度变化保持不变，对视角变化、仿射变换、噪声也保持一定程度的稳定性。
  • 独特性好，信息量丰富，适用于海量特征库进行快速、准确的匹配。
  • 多量性：即使是很少几个物体也可以产生大量的SIFT特征
  • 高速性：改进的SIFT匹配算法甚至可以达到实时性
  • 扩展性：可以很方便的与其他的特征向量进行联合。

尺度空间

概述

  • 人眼可自动调节尺度，完成对物体的检测和识别
  • 模仿人的视觉认知，把物体不同尺度下的图像都提供给机器，让机器能够对物体在不同的尺度下综合信息识别。
  • 因此，首先需要建立尺度空间。
  • 通过高斯函数与原图像卷积，并经过下采样，可建立原始图像的尺度空间模型。

理论

  • 在图像信息处理模型中引入一个被视为尺度的参数，通过连续变化尺度参数获得多尺度下的尺度空间表示序列，对这些序列进行尺度空间主轮廓的提取，并以该主轮廓作为一种特征向量，实现边缘、角点检测和不同分辨率上的特征提取等。
  • 尺度空间方法将传统的单尺度图像信息处理技术纳入尺度不断变化的动态分析框架中，更容易获取图像的本质特征。尺度空间中各尺度图像的模糊程度逐渐发大，能够模拟人在距离目标由近到远时目标在视网膜上的形成过程。

定义

  • 高斯卷积核是实现尺度变换的唯一变换核
  • 一幅图像的尺度空间被定义为：高斯卷积核与该图像的卷积，它是高斯卷积核中的参数$\sigma$的函数，这里用到“空间”这个词，是因为$\sigma$是可以连续变化的，具体地，图像$I(x,y)$的尺度空间为： $L(x,y,\sigma) = G(x,y,\sigma)*I(x,y)$
    • $G(x,y,\sigma) = \frac{1}{2\pi\sigma^2}*e^{-\frac{x^2+y^2}{2\sigma^2}}$ 是高斯核函数。
    • $\sigma$是尺度因子，$\sigma$的大小决定图像的平滑程度，大尺度对应图像的概貌特征，小尺度对应图像的细节特征。大的$\sigma$值对应粗糙尺度(低分辨率)，小的$\sigma$值对应精细尺度(高分辨率)。
    • *是卷积操作。
    • $L(x,y,\sigma) $就是输入图像$I(x,y)$的尺度空间。

栗子

​ 比如要观察一棵树，所选择的尺度应该是“米”级；如果观察树上的树叶，所选择的尺度则应该是“厘米”级。一般来说，摄像设备所能呈现的画面分辨率是固定的。要以同样的分辨率分别观察树和树叶，我们需要调整摄像设备的摄像位置。因此，视觉问题中的“尺度”概念也可以被形象地理解为摄像设备与被观察物体之间的距离：较远的距离对应较大的尺度，较近的距离对应较小的尺度。

概况的说：“尺度空间”的概念就是在多个尺度下观察目标，然后加以综合的分析和理解。

特征提取

一幅图像的SIFT特征提取，分为4个步骤：

  • 尺度空间极值检测.
  • 关键点位置及尺度确定
  • 关键点方向确定
  • 特征向量生成

尺度空间极值检测

SIFT特征点其实就是尺度空间中稳定的点/极值点，那么，为了得到这些稳定点：

  • 首先，需要对输入图像建立尺度空间（通过图像高斯金字塔）
  • 然后，需要从建立得到的尺度空间中检测极值点（转换为图像差分高斯金字塔中极值点的检测）
    • 获取差分高斯金字塔
    • DoG中极值点的检测
【构建高斯金字塔】
  • 尺度空间在实现时使用高斯金字塔表示，高斯金字塔的构建分为两部分：
    • 对图像做不同尺度的高斯模糊；
    • 对图像做降采样(隔点采样)。
  • 图像的金字塔模型是指，将原始图像不断降阶采样，得到一系列大小不一的图像，由大到小，从下到上构成的塔状模型。

高斯金字塔

​ 对于一幅输入图像，为了进行sift特征检测、实现scale-invariant（任何尺度下都能够有对应的特征点），需要对该图像的尺度空间进行分析，即建立高斯金字塔图像、得到不同scale的图像，这里的高斯金字塔与最原始的高斯金字塔稍微有点区别，因为它在构造尺度空间时，将这些不同尺度图像分为了多个Octave、每个Octave又分为了多层。下图左侧框内给出了Sift中的高斯金字塔的结构图。

结构图

  • 高斯金字塔分为S组（即S个塔、或者称为S个octave），每个塔中有s层；具体有几个塔、每个塔包含几层由输入图像的尺寸决定！对于上图而言：有S=2组，每组由s=5层；
  • 同一塔中图像尺寸相同但尺度不同、不同塔中图像尺寸和尺度都不同（注意：这里的尺寸和尺度概念不同！尺寸对应图像分辨率、尺度为高斯核大小）
    • 每一个塔中图像尺寸确定方法为：第一个塔的尺寸为原图大小，后面每个塔的尺寸为上一个塔的降采样的结果（即长宽分别减半的结果）
    • 每个塔中各层图像的尺度不同，即$\sigma$取值不同，各层之间相差一个k值。例如：上图中第一个塔中各层的尺度因子分别为$\sigma、k\sigma、 k^2\sigma、k^3\sigma、k^4\sigma$；而第二个塔中各层的尺度因子分别为$2\sigma、2k\sigma、 2k^2\sigma、2k^3\sigma、2k^4\sigma$
  • 如何确定相邻层之间的比例因子k呢？下图是同一Octave中不同层和不同Octave之间的尺度大小关系，为了满足尺度变化的连续性，即某一组的最后一层对应的尺度与下一组的第一层对应的尺度应该相差一个k倍，所以应该有$k^{s-1}\sigma_0 k = 2\sigma_0$， 所以$k^s=2$，即$k=2^{1/2}$， 其中，$\sigma_0$为基础尺度因子。

1

2

3

注意：关于尺度变化的连续性应该就是指：金字塔图像中所有图像之间的尺度因子都相差一个k倍：每个octave中相邻图像之间尺度因子相差一个k，相邻2个octave的最后一层与第一层的图像之间尺度因子相差一个k！
注2：英文Octave是音乐上一个八度的意思，在这里指的是一组图像。这一组图像的分辨率是相同的，但是采用了不同尺度的高斯函数进行滤波，因此从模糊程度上看（或者说从关注的尺度上看）是有区别的。而不同组的图像具有不同的分辨率，在尺度上的差别就更大。

​ 得到了图像的尺度空间后，需要在尺度中间内检测稳定特征点，从而需要比较不同尺度图像之间的差别，实现极值点的检测，实际上，Laplacian of Gaussian和Difference of Gaussian都能够实现这样的目的，但LoG需要大量的计算，而DoG的计算相对简单。

【建立图像差分高斯金字塔（DoG）】

​ 对于高斯金字塔中的每一个塔的不同层，可以计算得到相邻层之间的差值，从而可以得到差分高斯，对高斯金字塔中每一个塔都进行同样的操作，从而得到差分高斯金字塔，如下图右侧所示，即显示了由左侧的高斯金字塔构造得到的差分高斯金字塔，该差分高斯金字塔包含2个塔，每个塔都有四层

1

差分高斯表征了相邻尺度的高斯图像之前的差别，大值表示区别大，小值表示区别小，后续的特征点检测都是差分高斯图像金字塔中进行的！

【尺度空间中特征点的检测（DoG中极值点的检测）】

构造完尺度空间（差分高斯金字塔）后，接下来的任务就是“在尺度中间中检测出图像中的稳定特征点”.

​ 对于DoG中每一个采样点（每一个Octave中每一层），将其与它邻域内所有像素点（8+18=26）进行比较，判断其是否为局部极值点（极大或者极小），更加具体地：如下图所示，中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。 一个点如果在DOG尺度空间本层以及上下两层的26个领域中是最大或最小值时，就认为该点是图像在该尺度下的一个特征点。但要注意：这种相邻层之间的极值点的寻找是在同一Octave中的相邻尺度之间进行寻找的，而不要跨组！

同时，应该注意到一个问题，在极值比较的过程中，每一Octave图像的首末两层是无法进行极值比较的，为了满足尺度变化的连续性，需要进行一些修正：在高斯金字塔中生成S+3层图像，具体解释如下：假设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σ;

    1

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

    1

关键点位置及尺度确定

​ 通过拟和“三维二次函数”可以精确确定关键点的位置和尺度（达到亚像素精度），具体方法还未知，可以得到一系列的SIFT候选特征点集合，但由于这些关键点中有些具有较低的对比对，有些输属于不稳定的边缘响应点(因为DoG算子会产生较强的边缘响应)，所以，为了增强匹配稳定性、提高抗噪声能力，应该将这2类关键点去除，实现对候选SIFT特征点集合的进一步净化：

  • 剔除对比度低的点
  • 剔除边缘点

关键点方向确定

  • 算关键点的方向，需要利用以该关键点为中心的某邻域窗口内所有像素点的梯度分布特性（目的是为了使的sift算子具备旋转不变性），所以，下面首先给出计算尺度空间中每个像素点的梯度模值和方向的方法，按照下面公式计算

    1

    • 其中L所用的尺度为每个关键点各自所在的尺度。

      2

  • 接下来，对于每个关键点（假设尺度为sigma），利用直方图统计其相邻窗口内的像素的梯度分布，从而，确定该关键点的方向，具体方法如下：

    • 分别计算以该关键点为中心的相邻窗口中像素点的梯度方向和模值.

    • 为该窗口内每一个像素点赋予一个权值：由每个像素点对应的梯度模值和以关键点为中心尺度为1.5sigma的高斯核决定

    • 设定某种规则，开始统计直方图，例如，这里将方向（0~360°）分为8份，那么，梯度方向直方图将有8个柱，窗口内每个像素到底属于哪个柱由该像素点的梯度方向确定（见下图右侧子图所示）

      1
      3

    • 在该关键点对应的梯度方向直方图中，找到包含像素点最多的那个方向作为该关键点的方向，对于上图而言，方向角(0.25π,0.5π)这个区间内的像素点最多，所以，以(0.25π+0.5π)/2 = 0.375π作为该关键点的方向 。

至此，得到了图像中所有关键点的方向！实际上，关键点方向的确定是为了接下来的特征向量生成中的坐标旋转使用的！

特征向量生成

上面只是得到了每个关键点的方向，接下来，需要确定每个关键点的特征向量，具体方式如下：

  • 将坐标轴旋转到关键点的方向

    1

  • 对于某一个关键点，取其周围窗口，如下图绿色区域所示，其中，窗口内每个小矩形框为一个像素，箭头表示该像素位置的梯度方向和模值

  • 在该$88$窗口对应的4个（称为4个种子点）$44$的小块儿上，分别计算该小块儿包含的16个像素点的梯度直方图（8个柱），并进行累加（每个柱对应的所有像素点的梯度模值累加），每个小块儿可以得到8个特征（8个方向对应的模值的累加），从而，4个种子点将得到关键点的4*8=32个特征，如下图右侧所示，4个种子点，每个种子点产生8个特征 .

    2

  • 实际中，Lowe建议使用$44$个子块儿（称为16个种子点）进行特征计算，那么，每个关键点将具有16\8=128个特征，如下图所示，此时，需要在特征点周围取$1616$的窗口，分割为$44$个子块儿（这样做的目的是为了增强后续匹配的稳健性）。

    3

至此，关键点特征向量完全确定！此时SIFT特征向量已经去除了尺度变化、旋转等几何变形因素的影响，再继续将特征向量的长度归一化，则可以进一步去除光照变化的影响。

特征匹配

现有A、B两幅图像，分别利用上面的方法从各幅图像中提取到了k1个sift特征点和k2个特征点及其对应的特征描述子，即$k1128$维和$k2128$维的特征，现在需要将两图中各个scale（所有scale）的描述子进行匹配。

接下来采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。

  • 取图像A中的某个关键点，并找出其与图像B中欧式距离最近的前两个关键点
    • 在这两个关键点中，如果最近的距离除以次近的距离少于某个比例阈值，则接受这一对匹配点。降低这个比例阈值，SIFT匹配点数目会减少，但更加稳定。
    • 利用2个近邻点比较的目的是为了排除因为图像遮挡和背景混乱而产生的无匹配关系的关键点，所以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的取值策略能排分错误匹配点。

总结

  • 尺度空间的核心思想是通过不同分辨率看同一个图像，可通过不同尺度的高斯函数不原始图像卷积实现
  • 极大值点的精确定位可通过解含有二阶寻数项的方程得到
  • 借助在关键点附近区域的梯度方向统计不直方图生成，SIFT最终可得到对应每个关键点的128维向量描述。

代码实例

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2019/1/18 22:04
# @Author  : Seven
# @File    : surfDemo.py
# @Software: PyCharm

import cv2
import numpy as np

img1 = cv2.imread('csdn.png')
img2 = np.rot90(img1)
# 特征点检测和提取特征点描述子
surf = cv2.xfeatures2d.SURF_create(50)
kp1, des1 = surf.detectAndCompute(img1, None)
kp2, des2 = surf.detectAndCompute(img2, None)

# 创建 BFMatcher 对象
bf = cv2.BFMatcher(cv2.NORM_L2)
# 根据描述子匹配特征点.
matches = bf.match(des1, des2)
# 画出50个匹配点
img3 = cv2.drawMatches(img1, kp1, img2, kp2, matches[:50], None, flags=2)

cv2.imshow("img", img3)

cv2.waitKey(0)

机器视觉
SIFT

本博客所有文章除特别声明外，均采用 CC BY-SA 3.0协议 。转载请注明出处！

【十二】ORB角点检测 上一篇
【十】Harris角点检测 下一篇