SIFT特征详详解

简介

打好基础。
本文综合转载以下文章:

SIFT概述

SIFT的全称是Scale Invariant Feature Transform,尺度不变特征变换,由加拿大教授David G.Lowe提出的。SIFT特征对旋转、尺度缩放、亮度变化等保持不变性,是一种非常稳定的局部特征。

SIFT算法具有的特点

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

SIFT特征检测的步骤

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

尺度空间

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

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

在一定的范围内,无论物体是大还是小,人眼都可以分辨出来。然而计算机要有相同的能力却不是那么的容易,在未知的场景中,计算机视觉并不能提供物体的尺度大小,其中的一种方法是把物体不同尺度下的图像都提供给机器,让机器能够对物体在不同的尺度下有一个统一的认知。在建立统一认知的过程中,要考虑的就是在图像在不同的尺度下都存在的特征点。

多分辨率图像金字塔

在早期图像的多尺度通常使用图像金字塔表示形式。图像金字塔是同一图像在不同的分辨率下得到的一组结果,其生成过程一般包括两个步骤:

  1. 对原始图像进行平滑
  2. 对处理后的图像进行降采样(通常是水平、垂直方向的1/2)
    降采样后得到一系列不断尺寸缩小的图像。显然,一个传统的金字塔中,每一层的图像是其上一层图像长、高的各一半。多分辨率的图像金字塔虽然生成简单,但其本质是降采样,图像的局部特征则难以保持,也就是无法保持特征的尺度不变性。

高斯尺度空间

在进入高斯尺度空间之前,我们需要了解一下用来构造该空间的高斯函数和高斯模糊。

高斯函数与高斯模糊

高斯在$N$维空间的分布函数为:

在二维空间的分布函数为:

其中$r$是模糊半径,$σ$是正态分布的标准偏差。在二维空间中,这个公式生成的曲面的等高线是从中心开始呈正态分布的同心圆。分布不为零的像素组成的卷积矩阵与原始图像做变换。每个像素的值都是周围相邻像素值的加权平均。

如果使用简单平均,显然不是很合理,因为图像都是连续的,越靠近的点关系越密切,越远离的点关系越疏远。因此,加权平均更合理,距离越近的点权重越大,距离越远的点权重越小。

实际应用中,在计算高斯函数的离散近似时,在大概3$σ$距离之外的像素都可以看作不起作用,这些像素的计算也就可以忽略。通常,图像处理程序只需要计算$(6\sigma+1)×(6\sigma+1)$的矩阵就可以保证相关像素影响。对于边界上的点,通常采用复制周围的点到另一面再进行加权平均运算。

对一幅图像进行多次连续高斯模糊的效果与一次更大的高斯模糊可以产生同样的效果,大的高斯模糊的半径是所用多个高斯模糊半径平方和的平方根。例如,使用半径分别为6和8的两次高斯模糊变换得到的效果等同于一次半径为10的高斯模糊效果,$\sqrt{6×6+8×8}=10$。根据这个关系,使用多个连续较小的高斯模糊处理不会比单个高斯较大处理时间要少。

为了计算权重矩阵,需要设定$σ$的值。假定$σ=1.5$,则模糊半径为1的权重矩阵如下:

这9个点的权重总和等于0.4787147,如果只计算这9个点的加权平均,还必须让它们的权重之和等于1,因此上面9个值还要分别除以0.4787147,得到最终的权重矩阵。

有了权重矩阵,就可以计算高斯模糊的值了。假设现有9个像素点,灰度值(0-255)如下:

每个点乘以自己的权重值:

得到

将这9个值加起来,就是中心点的高斯模糊的值。对所有点重复这个过程,就得到了高斯模糊后的图像。如果原图是彩色图片,可以对RGB三个通道分别做高斯模糊。

高斯尺度空间

使用高斯模糊,我们能对图像在分辨率不变的情况下进行不同程度的模糊效果,形成高斯尺度空间。

其中,$G(x,y,\sigma)$是高斯核函数。

$σ$称为尺度空间因子,它是高斯正态分布的标准差,反映了图像被模糊的程度,其值越大图像越模糊,对应的尺度也就越大。$L(x,y,\sigma)$代表着图像的高斯尺度空间。

高斯金字塔:双空间结合

为了让尺度体现其连续性,高斯金字塔在简单降采样的基础上加上了高斯滤波。如图所示,将图像金字塔每层的一张图像使用不同参数做高斯模糊,使得金字塔的每层含有多张高斯模糊图像,将金字塔每层多张图像合称为一组(Octave),金字塔每层只有一组图像,组数和金字塔层数相等,每组含有多张(也叫层Interval)图像。另外,降采样时,高斯金字塔上一组图像的初始图像(底层图像)是由前一组图像的倒数第三张图像隔点采样得到的。

注:由于组内的多张图像按层次叠放,因此组内的多张图像也称做多层,为避免与金字塔层的概念混淆,本文以下内容中,若不特别说明是金字塔层数,层一般指组内各层图像。

高斯差分金字塔

2002年Mikolajczyk在详细的实验比较中发现尺度归一化的高斯拉普拉斯函数$\nabla^2 G$(称为LoG)的极大值和极小值同其它的特征提取函数,例如:梯度,Hessian或Harris角特征比较,能够产生最稳定的图像特征。

而Lindeberg早在1994年就发现高斯差分函数(Difference of Gaussian ,简称DOG算子)与尺度归一化的高斯拉普拉斯函数非常近似。

朝着这个公式努力:$\sigma \nabla^2 G = \frac{\partial G}{\partial \sigma} \approx \frac{G(x,y,k\sigma)-G(x,y,\sigma)}{k\sigma-\sigma}$

首先求解$\nabla^2 G = \frac{\partial}{\partial x^2}G_\sigma(x,y)+\frac{\partial}{\partial y^2}G_\sigma(x,y)$

$\frac{\partial}{\partial x}G_\sigma(x,y)=\frac{\partial}{\partial x}e^{-(x^2+y^2)/2\sigma^2}=-\frac{x}{\sigma^2}e^{-(x^2+y^2)/2\sigma^2}$

$\frac{\partial^2}{\partial x^2}G_\sigma(x,y)=\frac{x^2}{\sigma^4}e^{-(x^2+y^2)/2\sigma^2}=\frac{x^2-\sigma^2}{\sigma^4}e^{-(x^2+y^2)/2\sigma^2}$

$y$的情况也类似,

$\frac{\partial^2}{\partial y^2}G_\sigma(x,y)=\frac{y^2}{\sigma^4}e^{-(x^2+y^2)/2\sigma^2}=\frac{y^2-\sigma^2}{\sigma^4}e^{-(x^2+y^2)/2\sigma^2}$

即,

$\nabla^2G=\frac{1}{2 \pi \sigma^2}e^{-\frac{x^2+y^2}{2\sigma^2}}(\frac{x^2+y^2-2\sigma^2}{\sigma^4})$

求解$\frac{\partial G}{\partial \sigma}=\frac{1}{2 \pi \sigma^2}e^{-\frac{x^2+y^2}{2\sigma^2}}(\frac{x^2+y^2-2\sigma^2}{\sigma^3})$

由此可以得到,$\sigma \nabla^2G=\frac{\partial G}{\partial \sigma}$,而$\frac{G(x,y,k\sigma)-G(x,y,\sigma)}{k\sigma - \sigma}$可以看作在$\sigma$处的微分。

由此可以得到,

其中,$L(x,y,\sigma)$是图像的高斯尺度空间。

使用高斯金字塔每组中相邻上下两层图像相减,得到高斯差分图像,如图所示,进行极值检测。

易知,高斯金字塔有多组,每组又有多层。一组中的多个层之间的尺度是不一样的(也就是使用的高斯参数$\sigma$是不同的),相邻两层之间的尺度相差一个比例因子$k$。。如果每组有$S$层,则$k=2^{\frac{1}{S}}$。这是因为上一组图像的最底层图像是由下一组中尺度为$2\sigma$的图像进行因子为$2$的降采样得到的(高斯金字塔先从底层建立),当相乘了$s$次时,将会成为下一次的比例因子$2k$。

高斯金字塔的组数一般是

$o$表示高斯金字塔的层数,$m$,$n$分别是图像的行和列。减去的系数$a$可以$0-\log_2min(m,n)$之间的任意值,和具体需要的金字塔的顶层图像的大小有关。

高斯模糊参数$σ$(尺度空间),可由下面关系式得到

其中$o$为所在的组,$s$为所在的层,$\sigma_0$为初始的尺度,$S$为每组的层数。

在Lowe的算法实现中$σ_0=1.6$,$o_{min}=−1$,$S=3$,$o_{min}=−1$就是首先将原图像的长和宽各扩展一倍。

高斯金字塔构建示例

以一个$512×512$的图像$I$为例,构建高斯金字塔步骤:(从$0$开始计数)

  1. 金字塔的组数,$log_2512=9$,减去因子$3$,构建的金字塔的组数为$6$。取每组的层数为$3$。
  2. 构建第$0$组,将图像的宽和高都增加一倍,变成$1024×1024$($I_0$)。第$0$层$I_0×G(x,y,σ_0)$,第1层$I_0×G(x,y,kσ_0)$,第2层$I_0×G(x,y,k^2σ_0)$
  3. 构建第1组,对$I_0$降采样变成$512×512$($I_1$)。第0层$I_1×G(x,y,2σ_0)$,第1层$I_1×G(x,y,2kσ_0)$……$I1×G(x,y,2k^2σ_0)$
  4. 构建第$o$组,第$s$层$I_o×G(x,y,2^ok^sσ_0)$

DoG空间极值检测

为了寻找尺度空间的极值点,每个像素点要和其图像域(同一尺度空间)和尺度域(相邻的尺度空间)的所有相邻点进行比较,当其大于(或者小于)所有相邻点时,改点就是极值点。如图所示,中间的检测点要和其所在图像的$3×3$邻域$8$个像素点,以及其相邻的上下两层的$3×3$领域$18$个像素点,共$26$个像素点进行比较。
从上面的描述中可以知道,每组图像的第一层和最后一层是无法进行比较取得极值的。为了满足尺度变换的连续性,在每一组图像的顶层继续使用高斯模糊生成$3$幅图像,高斯金字塔每组有$S+3$层图像,DoG金字塔的每组有$S+2$组图像。

尺度变化的连续性

设$S=3$,也就是每组有$3$层,则$k=2^{\frac{1}{S}}=2^{\frac{1}{3}}$,也就是有高斯金字塔每组有$(S−1)3$层图像,DoG金字塔每组有$(S-2)2$层图像。在DoG金字塔的第一组有两层尺度分别是$σ$,$kσ$,第二组有两层的尺度分别是$2σ$,$2kσ$,由于只有两项是无法比较取得极值的(只有左右两边都有值才能有极值)。由于无法比较取得极值,那么我们就需要继续对每组的图像进行高斯模糊,使得尺度形成$σ$,$kσ$,$k^2σ$,$k^3σ$,$k^4σ$,这样就可以选择中间的三项$kσ$,$k^2σ$,$k^3σ$。对应的下一组由上一组降采样得到的三项是$2kσ$,$2k^2σ$,$2k^3σ$,其首项$2kσ=2⋅2^{\frac{1}{3}}σ=2^{\frac{4}{3}}σ$,刚好与上一组的最后一项$k^3σ=2^{\frac{3}{3}}σ$的尺度连续起来。

删除不好的极值点(特征点)

通过比较检测得到的DoG的局部极值点实在离散的空间搜索得到的,由于离散空间是对连续空间采样得到的结果,因此在离散空间找到的极值点不一定是真正意义上的极值点,因此要设法将不满足条件的点剔除掉。可以通过尺度空间DoG函数进行曲线拟合寻找极值点,这一步的本质是去掉DoG局部曲率非常不对称的点。
要剔除掉的不符合要求的点主要有两种:

  1. 低对比度的特征点
  2. 不稳定的边缘响应点

剔除低对比度的特征点

候选特征点$x$,其偏移量定义为$Δx$,其对比度为$D(x)$的绝对值$∣D(x)∣$,对$D(x)$应用泰勒展开式

由于$x$是$D(x)$的极值点,所以对上式求导并令其为$0$,

得到

然后再把求得的$Δx$代入到$D(x)$的泰勒展开式中

设对比度的阈值为$T$,若$\mid D(\hat{x})\mid \ge T$,则该特征点保留,否则剔除掉。

剔除不稳定的边缘响应点

在边缘梯度的方向上主曲率值比较大,而沿着边缘方向则主曲率值较小。候选特征点的DoG函数$D(x)$的主曲率与$2×2$Hessian矩阵$H$的特征值成正比。

其中,$D_{xx},D_{xy},D_{yy}$是候选点邻域对应位置的差分求得的。
为了避免求具体的值,可以使用$H$特征值得比例。设$α=λ_{max}$为$H$的最大特征值,$β=λ_{min}$为$H$的最小特征值,则

其中,$Tr(H)$为矩阵$H$的迹,$Det(H)$为矩阵$H$的行列式。

设$\gamma = \frac{\alpha}{\beta}$表示最大特征值和最小特征值的比值,则

上式的结果与两个特征值的比例有关,和具体的大小无关,当两个特征值想等时其值最小,并且随着$γ$的增大而增大。因此为了检测主曲率是否在某个阈值$T_γ$下,只需检测

如果上式成立,则剔除该特征点,否则保留。(Lowe论文中取$T_γ=10$)

求取特征点的主方向

经过上面的步骤已经找到了在不同尺度下都存在的特征点,为了实现图像旋转不变性,需要给特征点的方向进行赋值。利用特征点邻域像素的梯度分布特性来确定其方向参数,再利用图像的梯度直方图求取关键点局部结构的稳定方向。

找到了特征点,也就可以得到该特征点的尺度$σ$,也就可以得到特征点所在的尺度图像

计算以特征点为中心、以$3×1.5σ$为半径的区域图像的幅角和幅值,每个点$L(x,y)$的梯度的模$m(x,y)$以及方向$θ(x,y)$可通过下面公式求得

计算得到梯度方向后,就要使用直方图统计特征点邻域内像素对应的梯度方向和幅值。梯度方向的直方图的横轴是梯度方向的角度(梯度方向的范围是0到360度,直方图每36度一个柱共10个柱,或者没45度一个柱共8个柱),纵轴是梯度方向对应梯度幅值的累加,在直方图的峰值就是特征点的主方向。在Lowe的论文还提到了使用高斯函数对直方图进行平滑以增强特征点近的邻域点对关键点方向的作用,并减少突变的影响。为了得到更精确的方向,通常还可以对离散的梯度直方图进行插值拟合。具体而言,关键点的方向可以由和主峰值最近的三个柱值通过抛物线插值得到。在梯度直方图中,当存在一个相当于主峰值80%能量的柱值时,则可以将这个方向认为是该特征点辅助方向。所以,一个特征点可能检测到多个方向(也可以理解为,一个特征点可能产生多个坐标、尺度相同,但是方向不同的特征点)。Lowe在论文中指出

15%的关键点具有多方向,而且这些点对匹配的稳定性很关键。

得到特征点的主方向后,对于每个特征点可以得到三个信息$(x,y,σ,θ)$,即位置、尺度和方向。由此可以确定一个SIFT特征区域,一个SIFT特征区域由三个值表示,中心表示特征点位置,半径表示关键点的尺度,箭头表示主方向。具有多个方向的关键点可以被复制成多份,然后将方向值分别赋给复制后的特征点,一个特征点就产生了多个坐标、尺度相等,但是方向不同的特征点。

生成特征描述

通过以上的步骤已经找到了SIFT特征点位置、尺度和方向信息,下面就需要使用一组向量来描述关键点也就是生成特征点描述子,这个描述符不只包含特征点,也含有特征点周围对其有贡献的像素点。描述子应具有较高的独立性,以保证匹配率。
特征描述符的生成大致有三个步骤:

  1. 校正旋转主方向,确保旋转不变性。
  2. 生成描述子,最终形成一个128维的特征向量
  3. 归一化处理,将特征向量长度进行归一化处理,进一步去除光照的影响。

为了保证特征矢量的旋转不变性,要以特征点为中心,在附近邻域内将坐标轴旋转$θ$(特征点的主方向)角度,即将坐标轴旋转为特征点的主方向。旋转后邻域内像素的新坐标为:

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

与求主方向不同,此时每个种子区域的梯度直方图在$0-360$之间划分为$8$个方向区间,每个区间为$45$度,即每个种子点有$8$个方向的梯度强度信息。
在实际的计算过程中,为了增强匹配的稳健性,Lowe建议

对每个关键点使用$4×4$共$16$个种子点来描述,这样一个关键点就可以产生$128$维的SIFT特征向量。

通过对特征点周围的像素进行分块,计算块内梯度直方图,生成具有独特性的向量,这个向量是该区域图像信息的一种抽象,具有唯一性。

归一化

如上统计的$4×4×8=128$个梯度信息即为该关键点的特征向量。特征向量形成后,为了去除光照变化的影响,需要对它们进行归一化处理。得到的描述子向量为$H=(h_1,h_2,…,h_{128})$,归一化后的特征向量为$L=(l_1,l_2,…,l_{128})$,则

匹配

生成了A、B两幅图的描述子,(分别是$k_1\ast 128$维和$k_2 \ast 128$维),就将两图中各个scale(所有scale)的描述子进行匹配,匹配上128维即可表示两个特征点match上了。

实际计算过程中,为了增强匹配的稳健性,Lowe建议对每个关键点使用$4×4$共16个种子点来描述,这样对于一个关键点就可以产生128个数据,即最终形成128维的SIFT特征向量。此时SIFT特征向量已经去除了尺度变化、旋转等几何变形因素的影响,再继续将特征向量的长度归一化,则可以进一步去除光照变化的影响。当两幅图像的SIFT特征向量生成后,下一步我们采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。取图像1中的某个关键点,并找出其与图像2中欧式距离最近的前两个关键点,在这两个关键点中,如果最近的距离除以次近的距离少于某个比例阈值,则接受这一对匹配点。降低这个比例阈值,SIFT匹配点数目会减少,但更加稳定。为了排除因为图像遮挡和背景混乱而产生的无匹配关系的关键点,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的取值策略能排分错误匹配点。

PCA-SIFT

PCA-SIFT与标准SIFT有相同的亚像素位置,尺度和主方向。但在第4步计算描述子的设计,采用的主成分分析的方法。

特征描述子计算部分的思想是用特征点周围的$41×41$的像斑计算它的主元,并用PCA-SIFT将原来的$2×39×39$维的向量降成$20$维,以达到更精确的表示方式。

它的主要步骤为,对每一个关键点:在关键点周围提取一个$41×41$的像斑于给定的尺度,旋转到它的主方向;计算$39×39$水平和垂直的梯度,形成一个大小为$3042$的矢量;用预先计算好的投影矩阵$n×3042$与此矢量相乘;这样生成一个大小为$n$的PCA-SIFT描述子。

总结

SIFT特征以其对旋转、尺度缩放、亮度等保持不变性,是一种非常稳定的局部特征,在图像处理和计算机视觉领域有着很重要的作用,其本身也是非常复杂的,下面对其计算过程做一个粗略总结。

  1. DoG尺度空间的极值检测。 首先是构造DoG尺度空间,在SIFT中使用不同参数的高斯模糊来表示不同的尺度空间。而构造尺度空间是为了检测在不同尺度下都存在的特征点,特征点的检测比较常用的方法是$Δ^2G$(高斯拉普拉斯LoG),但是LoG的运算量是比较大的,Marr和Hidreth曾指出,可以使用DoG(差分高斯)来近似计算LoG,所以在DoG的尺度空间下检测极值点。

  2. 删除不稳定的极值点。 主要删除两类:低对比度的极值点以及不稳定的边缘响应点。

  3. 确定特征点的主方向。 以特征点的为中心、以$3×1.5σ$z为半径的领域内计算各个像素点的梯度的幅角和幅值,然后使用直方图对梯度的幅角进行统计。直方图的横轴是梯度的方向,纵轴为梯度方向对应梯度幅值的累加值,直方图中最高峰所对应的方向即为特征点的方向。

一分一毛也是心意