Sift算子特征点提取、描述及匹配全流程解析

Sift之前的江湖

在Sift横空出世之前，特征点检测与匹配江湖上占据霸主地位的是角点检测家族。先来探究一下角点家族不为人知的恩怨情仇。

角点家族的族长是Moravec在1977年提出的Moravec角点检测算子，它是一种基于灰度方差的角点检测方法，该算子计算图像中某个像素点沿水平、垂直方向上的灰度差异，以确定角点位置，Moravec是第一个角点检测算法，也是角点家族的开山鼻祖。

角点家族的九袋长老是Chris Harris & Mike Stephens在1988年提出的Harris角点检测算子。Harris不止是考察水平、垂直4个方向上的灰度差异，而是考察了所有方向上的灰度差异，并且具有旋转不变性和对部分仿射变换的稳定性。Harris是整个角点检测家族的颜值担当。

角点家族的大护法是J.Shi和C.Tomasi在1994年提出的Shi-Tomasi角点检测算子，它是对Harris角点算子的改进，并且有一个直接“叫嚣”Harris算子的名字——“Good Features to Track”，在Opencv中实现函数是goodfeaturesToTrack。它通过考察自相关矩阵M的两个特征值中的较小者来确定就角点，大部分情况下，有比Harris更好的检测效果。

角点家族洪兴堂堂主是E.Rosten和T.Drummond在2006年提出的FAST(Feature from Accelerated Segment Test)算子。它通过考察像素点与其邻域内16个像素点的差异来确定特征点（角点），并且通过分割测试算法对检测效率做了极大的提升。它信奉“天下武功，唯快不破”的真理，在快的道路上锐意进取，基本可以满足实时检测系统的要求，在现今计算机视觉领域赚足了眼球。

角点家族这种群雄逐鹿的局面一直持续了很多年，大家你追我赶，在群主Moravec的带领下家族基于日渐殷实。直到20多年后的1999年的某天拂晓，一个叫Sift的后生叩响了角点家族的鎏金铁门。

Sift闪亮登场

1999年，大不列颠哥伦比亚大学的David G.Lowe教授在现有基于不变量技术的特征检测方法基础上，提出了一种基于尺度空间的，对图像缩放、旋转、甚至仿射变换保持不变性的图像局部特征描述算子——Sift（尺度不变特征变换），全称是Scale Invariant Feature Transform，并且在2004年，又对Sift算法做了更为系统的完善。下边这位老爷子就是Lowe。

Sift提取图像的局部特征，在尺度空间寻找极值点，并提取出其位置、尺度、方向信息。Sfit的应用范围包括物体辨别、机器人地图感知与导航、影响拼接、3D模型建立、手势识别、影响追踪等。

Sift特征的特点：

1. 对旋转、尺度缩放、亮度变化保持不变性，对视角变化、噪声等也存在一定程度的稳定性；

2. 独特性，信息量丰富，适用于在海量特征数据中进行快速，准确的匹配；

3. 多量性，即使少数几个物体也可以产生大量的Sfit特征向量；

4. 可扩展性，可以很方便的与其他形式的特征向量进行联合；

Sfit算法的实质是在不同的尺度空间上查找关键点（特征点），计算关键点的大小、方向、尺度信息，利用这些信息组成关键点对特征点进行描述的问题。Sift所查找的关键点都是一些十分突出，不会因光照，仿射便函和噪声等因素而变换的“稳定”特征点，如角点、边缘点、暗区的亮点以及亮区的暗点等。匹配的过程就是对比这些特征点的过程，这个流程可以用下图表述：

Sfit特征提取和匹配具体步骤

1. 生成高斯差分金字塔（DOG金字塔），尺度空间构建

2. 空间极值点检测（关键点的初步查探）

3. 稳定关键点的精确定位

4. 稳定关键点方向信息分配

5. 关键点描述

6. 特征点匹配

以下对这6个步骤逐一说明。

1. 生成高斯差分金字塔（DOG金字塔），尺度空间构建

主要思想是通过对原始图像进行尺度变换，获得图像多尺度下的尺度空间表示序列，对这些序列进行尺度空间主轮廓的提取，并以该主轮廓作为一种特征向量，实现边缘、角点检测不同分辨率上的关键点提取等。

各尺度下图像的模糊度逐渐变大，能够模拟人在距离目标由近到远时目标物体在视网膜上的形成过程。

尺度空间构建的基础是DOG金字塔，DOG金字塔构建的基础是高斯金字塔，关于尺度空间、高斯金字塔、DOG金字塔的相关说明，可以参看前一篇博文《Sift中尺度空间、高斯金字塔、差分金字塔（DOG金字塔）、图像金字塔》。贴一下高斯金字塔的实例图像：

归一化的DOG金字塔实例图像：

2. 空间极值点检测（关键点的初步查探）

为了寻找DOG函数的极值点，每一个像素点要和它所有的相邻点比较，看其是否比它的图像域和尺度空间域的相邻点大或者小，如下图所示：

在二维图像空间，中心点与它3*3邻域内的8个点做比较，在同一组内的尺度空间上，中心点和上下相邻的两层图像的2*9个点作比较，如此可以保证检测到的关键点在尺度空间和二维图像空间上都是局部极值点。

3. 稳定关键点的精确定位

DOG值对噪声和边缘比较敏感，所以在第2步的尺度空间中检测到的局部极值点还要经过进一步的筛选，去除不稳定和错误检测出的极值点，另一点就是在构建高斯金字塔过程中采用了下采样的图像，在下采样图像中提取的极值点对应在原始图像中的确切位置，也是要在本步骤中解决的问题。

4. 稳定关键点方向信息分配

稳定的极值点是在不同尺度空间下提取的，这保证了关键点的尺度不变性。为关键点分配方向信息所要解决的问题是使得关键点对图像角度和旋转具有不变性。方向的分配是通过求每个极值点的梯度来实现的。

对于任一关键点，其梯度幅值表述为：

梯度方向为：

分配给关键点的方向并不直接是关键点的梯度方向，而是按照一种梯度方向直方图的方式给出的。

具体的方法是：计算以关键点为中心的邻域内所有点的梯度方向，当然梯度方向一定是在0~360°范围内，对这些梯度方向归一化到36个方向内，每个方向代表了10°的范围。然后累计落到每个方向内的关键点个数，以此生成梯度方向直方图。

将梯度方向直方图中纵坐标最大的项代表的方向分配给当前关键点作为主方向，若在梯度直方图中存在一个相当于主峰值80%能量的峰值，则将这个方向认为是关键点的辅方向。辅方向的设计可以增强匹配的鲁棒性，Lowe指出，大概有15%的关键点具有辅方向，而恰恰是这15%的关键点对稳定匹配起到关键作用。

5. 关键点描述

对关键点的描述是后续实现匹配的关键步骤，描述其实就是一种以数学方式定义关键的过程。描述子不但包含关键点，也包括关键点周围对其有贡献的邻域点。

描述的思路是：对关键点周围像素区域分块，计算快内梯度直方图，生成具有独特性的向量，这个向量是该区域图像信息的一种抽象表述。

如下图，对于2*2块，每块的所有像素点的荼毒做高斯加权，每块最终取8个方向，即可以生成2*2*8维度的向量，以这2*2*8维向量作为中心关键点的数学描述。

David G.Lowed的实验结果表明：对每个关键点，采用4*4*8共128维向量的描述子进项关键点表征，综合效果最佳：

6. 特征点匹配

特征点的匹配是通过计算两组特征点的128维的关键点的欧式距离实现的。欧式距离越小，则相似度越高，当欧式距离小于设定的阈值时，可以判定为匹配成功。

Sift特征匹配效果：