笔记：SIFT 和 SURF 特征提取总结

SIFT（Scale-invariant feature transform）是一种检测局部特征的算法，该算法通过求一幅图中的特征点（interest points, or corner points）及其有关 scale 和 orientation 的描述子得到特征并进行图像特征点匹配

什么是 SIFT

先看看上图利用 SIFT 进行匹配的结果：

这个结果应该可以很好地解释 SIFT 的尺度、旋转以及光照不变性。接下来就介绍一下这个神奇的算法的奥义。我把代码放在了 GitHub，感兴趣的同学自己下载下来试试。

算法描述

SIFT 特征具有尺度不变性、旋转不变性、光照不变性。

实现流程

构建尺度空间

尺度空间的目的是模拟图像的多尺度特性。高斯卷积核是实现尺度变换的唯一线性核，于是一幅二维图像的尺度空间定义为：

L (x, y, σ) = G (x, y, σ) * I (x, y)

其中的 $G (x, y, σ)$ 是尺度可以发生变化的高斯函数：

G (x, y, σ) = \frac{1}{2 π σ ^{2}} e^{- \frac{x ^{2} + y ^{2}}{2 σ ^{2}}}

$(x, y)$ 表示空间坐标， $σ$ 是尺度系数，描述了图像的模糊程度。为了能够更为有效地提取出特征点，提出了 DOG（高斯差分尺度空间）的概念。通过不同尺度下的高斯差分核与图像卷积形成：

D (x, y, σ) = (G (x, y, k σ) - G (x, y, σ)) * I (x, y) = L (x, y, k σ) - L (x, y, σ)

图像金字塔的建立：为了实现尺度不变特性，对于每一幅图像 $I (x, y)$ ，分成子八度（octave），第一个子八度的 scale 为原图大小，后面每个 octave 为上一个 octave 降采样的结果，即原图 size 的 1/4（长宽分别减半），构成下一个子八度（高一层金字塔）。此时要强烈注意 size 和尺度空间的概念。size 是图像大小，而尺度空间表示不同 $σ$ 的图像的集合。那么尺度空间的集合是：

2^{i - 1} (σ, k * σ, k^{2} * σ, k^{3} * σ, ..., k^{n - 1} * σ)

其中的 $k = 2^{1/ S}$ ， $S$ 表示尺度金字塔每个 octave 的层数， $n$ 表示尺度金字塔的总层数， $i$ 表示的是在某个 octave 的第 $i$ 层， $i \in [1, 2, 3, ... n]$ 。

由图片 size 决定建几个塔，每塔几层图像（S 一般为 3-5 层）。0 塔的第 0 层是原始图像（或你 double 后的图像），往上每一层是对其下一层进行 Laplacian 变换（高斯卷积，其中 σ 值渐大，例如可以是 σ, k*σ, k*k*σ……），直观上看来越往上图片越模糊。塔间的图片是降采样关系，例如 1 塔的第 0 层可以由 0 塔的第 3 层 down sample 得到，然后进行与 0 塔类似的高斯卷积操作。

在 DoG 空间找到关键点

为了寻找尺度空间的极值点，每一个采样点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。如图所示，中间的检测点和它同尺度的 8 个相邻点和上下相邻尺度对应的 9×2 个点共 26 个点比较，以确保在尺度空间和二维图像空间都检测到极值点。一个点如果在 DOG 尺度空间本层以及上下两层的 26 个邻域中是最大或最小值时，就认为该点是图像在该尺度下的一个特征点，如图所示。使用 Laplacian of Gaussian 能够很好地找到图像中的兴趣点，但是需要大量的计算量，所以使用 Difference of Gaussian 图像的极大极小值近似寻找特征点。DOG 算子计算简单，是尺度归一化的 LoG 算子的近似。

去除不好的点

这一步本质上要去掉 DoG 局部曲率非常不对称的像素。通过拟合三维二次函数以精确确定关键点的位置和尺度（达到亚像素精度），同时去除低对比度的关键点和不稳定的边缘响应点（因为 DoG 算子会产生较强的边缘响应），以增强匹配稳定性、提高抗噪声能力，在这里使用近似 Harris Corner 检测器。

给特征点赋值一个 128 维方向参数并描述

前面的几个步骤确定了特征点到底在哪里，此步骤是为了描述特征点。(x,y) 处梯度的模值和方向公式为：

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

θ (x, y) = t a n^{- 1} (\frac{L ( x , y + 1 ) - L ( x , y - 1 )}{L ( x + 1 , y ) - L ( x - 1 , y )})

利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。

其中 L 所用的尺度为每个关键点各自所在的尺度。至此，图像的关键点已经检测完毕，每个关键点有三个信息：位置、所处尺度、方向，由此可以确定一个 SIFT 特征区域。

在实际计算时，我们在以关键点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向。梯度直方图的范围是 0～360 度，其中每 45 度一个柱，总共 8 个柱，或者每 10 度一个柱，总共 36 个柱。Lowe 论文中还提到要使用高斯函数对直方图进行平滑，减少突变的影响。直方图的峰值则代表了该关键点处邻域梯度的主方向，即作为该关键点的方向。直方图中的峰值就是主方向，其他的达到最大值 80% 的方向可作为辅助方向。

计算 keypoint 周围的 16*16 的 window 中每一个像素的梯度，而且使用高斯下降函数降低远离中心的权重。图左部分的中央为当前关键点的位置，每个小格代表关键点邻域所在尺度空间的一个像素，利用公式求得每个像素的梯度幅值与梯度方向，箭头方向代表该像素的梯度方向，箭头长度代表梯度模值，然后用高斯窗口对其进行加权运算。

该图是 8*8 的区域计算得到 2*2 描述子向量的过程。但是在实际中使用的是在 16*16 的区域计算得到 4*4 的特征描述子，如下图：

这样就可以对每个 feature 形成一个 4*4*8=128 维的描述子，每一维都可以表示 4*4 个格子中一个的 scale/orientation。将这个向量归一化之后，就进一步去除了光照的影响。

SIFT 的缺点

SIFT 在图像的不变特征提取方面拥有无与伦比的优势，但并不完美，仍然存在：

实时性不高。
有时特征点较少。
对边缘光滑的目标无法准确提取特征点。

PS：论文见这里：Distinctive Image Features from Scale-Invariant Keypoints，这里是 David Lowe 大神做的一个 Demo Software: SIFT Keypoint Detector。

SURF 简介

参考了好友整理的一篇文章特征与匹配。

整体的思路就是将计算 DOG 的一整套东西来检测关键点的理论替换成了利用 Hessian 矩阵来检测关键点，因为当 Hessian 矩阵的判别式取得局部极大值时，判定当前点是比周围邻域内其他点更亮或更暗的点，由此来定位关键点的位置。上述过程要进行 Hessian 判别式的计算，可以采用 box filter 的方式进行加速。
构建尺度金字塔的方式不同，具体见下图：
SIFT 特征点方向分配是采用在特征点邻域内统计其梯度直方图，取直方图 bin 值最大的以及超过最大 bin 值 80% 的那些方向作为特征点的主方向。而在 SURF 中，采用的是统计特征点圆形邻域内的 Haar 小波特征。即在特征点的圆形邻域内，统计 60 度扇形内所有点的水平、垂直 Haar 小波特征总和，然后扇形以 0.2 弧度大小的间隔进行旋转并再次统计该区域内 Haar 小波特征值之和，最后将值最大的那个扇形的方向作为该特征点的主方向。该过程示意图如下：
生成特征点描述子：在 SIFT 中，是取特征点周围 4*4 个区域块，统计每小块内 8 个梯度方向，用这 4*4*8=128 维向量作为 SIFT 特征的描述子。SURF 算法中，也是在特征点周围取一个 4*4 的矩形区域块，但是所取的矩形区域方向是沿着特征点的主方向。每个子区域统计 25 个像素的水平方向和垂直方向的 Haar 小波特征，这里的水平和垂直方向都是相对主方向而言的。该 Haar 小波特征为水平方向值之和、垂直方向值之和、水平方向绝对值之和以及垂直方向绝对值之和 4 个方向。把这 4 个值作为每个子块区域的特征向量，所以一共有 4*4*4=64 维向量作为 SURF 特征的描述子，比 SIFT 特征的描述子减少了 2 倍。