图像处理经典算法--SIFT尺度不变特征转换

1. SIFT简介

SIFT（Scale-invariant feature transform 尺度不变特征变换）是一种传统的图像提取算法，由David G. Lowe于1999年发表，在修改完善后，2004年发表于IJCV上，论文名称是Distinctive Image Features from Scale-Invariant Keypoints，原文在这里。

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

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

1. 尺度空间极值检测 (scale-space extrema detection):通过使用高斯差分函数来搜索所有尺度上的图像位置，识别出其中对于尺度和方向不变的潜在兴趣点。

2. 关键点定位 (Keypoint localization):在每个候选位置上，利用一个拟合精细的模型确定位置和尺度，关键点的选择依赖于它们的稳定程度。

3. 方向匹配 (Orientation assignment，为每个关键点赋予方向):基于局部图像的梯度方向，为每个关键点位置分配一个或者多个方向，后续所有对图像数据的操作都是基于相对关键点的方向、尺度和位置进行变换，从而获得了方向与尺度的不变性。

4. 关键点描述符 (Keypoint descriptor):在每个关键点领域内，以选定的尺度计算局部图像梯度，这些梯度被变换成一种表示，这种表示允许比较大的局部形状的变形和光照变化。

2.  尺度空间极值检测

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

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

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

 

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

3. 关键点定位

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

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

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

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

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

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

然后去除低对比度以及边缘效应的极值点，就得到最终需要保留的所有极值点。

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

测试结果为

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

4. 方向匹配

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

5. 关键点描述符

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

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

6. SIFT应用举例