SIFT（Scale-invariant feature transform）尺度不变特征变换。这是一种传统的图像特征提取算法，由David G. Lowe于1999年发表，在修改完善后，于2004年发表于IJCV。

论文名称：Distinctive Image Features from Scale-Invariant Keypoints。

SIFT算法是一种基于局部兴趣点的算法，正如其名称那样，SIFT对于「图像的尺度与图像的旋转不敏感」，而且算法对于光照、噪声等影响也具有较好的鲁棒性。

SIFT算法专利于2000年申请，经过20年，已于2020年3月到期。opencv中已经重新集成了这种算法。

最近两年一直在搞深度学习，对于本科时候看的SIFT算法已经忘得差不多了，最近重新学习梳理一下这个经典的图像特征提取算法。

SIFT算法主要分为四个步骤：

1. 「尺度空间极值检测（Scale-space extrema detection）」：通过使用「高斯差分函数」来搜索所有尺度上的图像位置，识别出其中对于尺度和方向不变的潜在兴趣点。
2. 「关键点定位（Keypoint localizatio）」：在每个候选位置上，利用一个拟合精细的模型确定位置和尺度，关键点的选择依赖于它们的稳定程度。
3. 「方向匹配（Orientation assignment，为每个关键点赋予方向）」：基于局部图像的梯度方向，为每个关键点位置分配一个或多个方向，后续所有对图像数据的操作都是基于相对关键点的方向、尺度和位置进行变换，从而获得了方向于尺度的不变性。
4. 「关键点描述符（Keypoint descriptor）」：在每个关键点领域内，以选定的尺度计算局部图像梯度，这些梯度被变换成一种表示，这种表示允许比较大的局部形状的变形和光照变化。

接下来分别介绍这四个步骤。

1. 尺度空间极值检测（Scale-space extrema detection）

利用高斯核构建高斯金字塔，每个尺度层包含一组尺度的图像。这里不同组的特征金字塔的获取采用隔点取样获得。

在每个组内（octave）两两做差，构建高斯差分金字塔。

在高斯差分金字塔中，每个3x3x3的立方体，比较中心点与其他的26个点的大小，如果中心点最大或者最小，那么这个中心点就是极值点。

s表示我们要在高斯差分金字塔中求得的特征层的数目，那么需要s+2层的高斯差分金字塔，需要s+3层的高斯金字塔。因此每组的octave中需要s+3层图像。

2. 关键点定位（Keypoint localizatio）

上边的步骤所检测到极值点是「离散空间的极值点」，这些极值点并不是十分准确，我们需要来精确确定关键点的位置和尺度，同时去除低对比度的关键点和不稳定的边缘点(因为DoG算子会产生较强的边缘响应)，从而增强稳定性。

离散空间的极值点并不是真正的极值点，正如下图所示，利用离散空间的极值点的插值可以得到「连续空间的极值点」。

因此，这里对于图像极值点进行二阶泰勒展开近似：

求导，让其为0，求得连续空间的极值点：

将极值点代入上述泰勒近似公式，得到在极值点位置的值：

由此，即可得到真正的连续空间的极值点。

然后去除低对比度以及边缘效应的极值点（这部分的细节可以看原始论文），就得到最终需要保留的所有极值点。

边缘效应的去除，采用hassian阵的特征值，hassian阵实际为二阶偏导数。在高斯差分图像中，如果其边缘特征点，那么其垂直于边缘的方向，值变化较大（对应于hassian阵中较大的特征值），沿边缘方向，值变化较小（对应于hassian阵中较小的特征值）。因此采用hassian阵中的较大特征值与较小特征值的比例超过阈值的特征点去除，就去除了边缘效应。（文章中采用矩阵的迹与行列式近似计算）

文中取r=10.

a图是原图像，b图是直接进行关键点检测得到的效果图，c图是舍弃对比度较小的极值点得到的效果图。d图是去除边缘效应极值点后得到的效果图。

3. 方向匹配（Orientation assignment，为每个关键点赋予方向）

对于每个极值点，统计以该特征点所在的?斯图像的尺度的1.5倍为半径的圆内的所有的像素的梯度方向及其梯度幅值。得到下图所示的直方图（论文中以每10度为一个范围，也就是有36个方向）。直方图峰值所对应的方向为主方向，任何大于峰值80%的方向为特征点的辅方向。

4. 关键点描述符（Keypoint descriptor）

前边三个步骤，我们找到了所有的特征点的位置，并且每个特征点都有方向，尺度信息。接下来就是计算在局部区域内这些特征点的描述符。

如下图，左边是图像梯度图像，右边是关键点描述符。描述符与特征点所在的尺度图像有关，因此在某个高斯尺度图像上，以特征点为圆心，将其附近邻域划分为4x4个子区域，每个区域统计特征点的方向以及尺度，每个子区域获得8个方向的梯度信息，因此每个特征点共有4x4x8=128维的特征。

?

原文首发于「小哲AI」公众号，公众号主要分享人工智能前沿算法解读，AI项目代码解析，以及编程、互联网求职等技术资料文章，偶尔也会分享个人读书笔记、工作学习心得，欢迎关注，一起学习。

?