SIFT算法入门

本文基于OpenCV-SIFT官方帮助文档，简要介绍了SIFT算法的原理。

原文链接：OpenCV-Introduction to SIFT (Scale-Invariant Feature Transform)

多尺度空间极值点检测

多尺度空间极值点检测是指通过降采样构建图像金字塔，通过高斯差分（DOG）求极值点作为候选特征点。

多尺度图像金字塔由图片经过降采样形成不同尺度的图片（串联成金字塔形状），再通过高斯卷积使图像平滑、尺度变化连续。由于其卷积核和图片的尺度保持了一致，且特征点是基于每个尺度进行求解的，所以实现了“尺度不变性”，也就是无论近距离拍摄还是远距离拍摄，都可以有效提取到特征点。DOG方法代替高斯拉普拉斯算子（LOG）方法可以大大提高计算速度，通过将两层相邻的图片像素值相减（做差分）描述灰度值变化速度，从而提取出变化最大的点（极值点）作为候选特征点。

高斯图像金字塔&DOG金字塔

高斯图像金字塔的构建可以分为降采样和高斯模糊两个部分。降采样是将上一个Octave的倒数第3个scale的像素值去掉一半，以达到尺寸减半。高斯模糊是将每一个Octave上的不同scale采用不同的 $\sigma$ 进行高斯卷积， $\sigma$ 的值与Octave和scale有关，Octave序号越大，越处于金字塔顶端，图片尺度越小， $\sigma$ 越小。所以，一个金字塔中有多个Octave，每个Octave又含有多个scale。同一个Octave中的图片尺度相同，但平滑度不同。

DOG金字塔的构建是将每一Octave中的相邻scale相减，形成DOG金字塔。然后对每层寻找极值点，将每个点与其周围（2*9+8）个点的像素值进行比较，找到极值点作为候选特征点。

在scale中寻找极值点

特征点确定

从候选特征点中去除边缘点和低对比度点的过程，即特征点的确定。因为DOG方法只是检测灰度值变化较快的区域，所以会同时检测出边缘和角点。但是边缘往往难以作为一个物体的特征，所以这里引入Hessian矩阵，分别求出候选特征点两个方向的灰度梯度并作比值，对于边缘点，求出的比值必定很大或很小，此时通过设定阈值可以有效剔除边缘特征点。低对比度的特征点可以通过直接设定灰度阈值来剔除。

方向分配

梯度本质上是一个向量，所以自然有方向。根据像素点两个方向的梯度值，可以求得任意一点的梯度方向。为了更好地描述特征点信息，同时也为了保持特征的旋转不变性，我们需要求出特征点所在邻域的特征方向。具体求解方法是，取特征点周围16*16区域，以4*4为一小单元，共有16个小单元。初始梯度值有0~360°范围，以10°为区间长度划分为36个区间，在每个小单元内，求出每个像素点的梯度方向后，以梯度值和 $\sigma$ 加权，将该点的梯度方向归入相邻区间内。所以对于一个小单元，只有36个梯度方向，每个梯度方向对应不同的梯度值。取最大值作为主方向，然后将坐标系与主方向重合，以达到旋转不变性。