2016年12月里番磁力:SIFT~

0.前言   

    SIFT算法的本质其实是模式识别中的特征点提取后用多维距离空间来训练样本得到最佳匹配的数学模型。它利用尺度变化不变的特征来匹配两幅图片中的对应点，尽管两幅图中的对应物体可能发生了旋转，平移，放大，缩小，该算法仍有一定的鲁棒性，这里我拍了两张不同角度的农夫山泉的照片，绿色连线的两端点表示一对正确的匹配点对，最后匹配效果如下图所示：

    SIFT算法实现物体识别主要有三大工序，1、提取关键点；2、对关键点附加详细的信息（局部特征）也就是所谓的描述器；3、通过两方特征点（附带上特征向量的关键点）的两两比较找出相互匹配的若干对特征点，也就建立了景物间的对应关系，如图所示：

1.高斯金字塔

    关键点就是在不同尺度空间的图像下检测出的具有方向信息的局部极值点，这些点是一些十分突出的点不会因光照条件的改变而消失，比如角点、边缘点、暗区域的亮点以及亮区域的暗点，既然两幅图像中有相同的景物，那么使用某种方法分别提取各自的稳定点，这些点之间会有相互对应的匹配点。尺度空间理论最早在1962年提出，其主要思想是通过对原始图像进行尺度变换，获得图像多尺度下的尺度空间表示序列，对这些序列进行尺度空间主轮廓的提取，并以该主轮廓作为一种特征向量，实现边缘、角点检测和不同分辨率上的特征提取等。尺度空间中各尺度图像的模糊程度逐渐变大，能够模拟人在距离目标由近到远时目标在视网膜上的形成过程。我们引进高斯函数作为图像模糊处理的模板算子：

高斯核是唯一可以产生多尺度空间的核，一个图像的尺度空间为L等于原始图像I与一个可变尺度的2维高斯函数G作卷积运算：

为了让尺度体现其连续性，在简单采样的基础上加上了高斯滤波。一幅图像可以产生多组（octave）图像，一组图像包括多层（interval）图像。我们设构建高斯图像金字塔共有o组，每组有s层(一般为3-5之间)：

其中高斯金字塔的组数o为：

高斯金字塔的组内尺度与组间尺度之间的递归关系为（其中i是金字塔组数，n代表每一组的层数）：

接下来我们需要利用LoG算子的尺度不变性来把上面高斯模糊处理的多张图片作差分得到DoG高斯差分金字塔，DOG图像描绘的是目标的轮廓：

2.DoG的局部关键点

    关键点是由DOG空间的局部极值点组成的。为了寻找DoG函数的极值点，每一个像素点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的18个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点：

由于DoG值对噪声和边缘较敏感,因此,在上面DoG尺度空间中检测到局部极值点还要经过进一步的检验才能精确定位为特征点。为了提高关键点的稳定性，需要对尺度空间DoG函数进行曲线拟合。利用DoG函数在尺度空间Taylor展开式分别对图像的行、列及尺度三个分量进行修正：

去除那些对比度较低的不稳定极值点。一般取值小于0.04的极值点均可抛弃（灰度范围为0-1）。仅仅去除低对比度的极值点对于极值点的对于特征点稳定性是远远不够的。DoG函数在图像边缘有较强的边缘响应，因此我们还需要排除边缘响应。DoG函数的峰值点在横跨边缘的方向有较大的主曲率，而在垂直边缘的方向有较小的主曲率。主曲率可以通过计算在该点位置尺度的二阶Hessian矩阵得到，导数由采样点相邻差来估计：

D的主曲率和H的特征值成正比，为了避免直接的计算这些特征值，而只是考虑它们的之间的比率。我们设：

当满足下式时将关键点保留，反之则丢弃掉,r一般取为1.0f：

3.关键点方向

    通过尺度不变性求极值点，可以使其具有缩放不变的性质，利用关键点邻域像素的梯度方向分布特性，我们可以为每个关键点指定方向参数方向，从而使描述子对图像旋转具有不变性。确定关键点的方向采用梯度直方图统计法，统计以关键点为原点一定区域内的图像像素点对关键点方向所作的贡献。梯度幅值和方向的公式如下：

①直方图以每10度方向为一个柱，共36个柱，柱所代表的方向为像素点梯度方向，柱的长短代表了梯度幅值。
②在直方图统计时，每相邻三个像素点采用高斯加权，模板采用[0.25,0.5,0.25]，并连续加权两次。
③直方图统计半径采用3*1.5*σ。

我们认为极值点周围区域梯度直方图的主峰值,也是特征点方向；在梯度方向直方图中，当存在另一个相当于主峰值80%能量的峰值时，则将这个方向认为是该关键点的辅方向。这可以增强匹配的鲁棒性，大概有15%关键点具有多方向，但这些点对匹配的稳定性至为关键。于是图像的关键点已检测完毕，每个关键点有三个信息：位置、尺度、方向；同时也就使关键点具备平移、缩放、和旋转不变性。

4.关键点描述特征向量

描述子梯度方向直方图由关键点所在尺度的模糊图像计算产生。图像区域的半径通过下式计算：

然后将坐标移至关键点主方向，在图像半径区域内对每个像素点求其梯度幅值和方向，然后对每个梯度幅值乘以高斯权重参数，生成方向直方图：

最后在窗口宽度为2X2的区域内计算8个方向的梯度方向直方图，绘制每个梯度方向的累加值，即可形成一个种子点。然后再在下一个2X2的区域内进行直方图统计，形成下一个种子点，共生成16个种子点。描述子向量元素门限化及门限化后的描述子向量规范化。描述子向量元素门限化：方向直方图每个方向上梯度幅值限制在一定门限值以下（一般为0.2）。于是我们得到了128描述特征向量，接下来就只需对样本进行模式识别中的匹配了，至于用到PCA降维或者KDTree加速等都属于人工智能和图形学的范畴了。