SIFT算法

介绍了这么久的SIFT相关的一些理论基础和方法，今天就给大家介绍一下这个传说中的算法（千呼万唤始出来。。。），因为该算法包含好几个步骤，我们之间介绍的都是最开始的步骤，也是最难理解的步骤，有了这些基础，SIFT算法理解起来就不会那么复杂了，所以我们今天直接把算法从头到尾介绍一下，如果有问题的话咱们再讨论。

SIFT算法的全称是尺度不变特征转换（Scale-invariant feature transform，SIFT），该算法是一种用来侦测与描述影像中的局部性特征计算机视觉（Computer Vision，CV）的算法，它在尺度空间（由高斯图像做差得到的DoG近似的LoG金字塔）中寻找极值点，并提取出其位置、尺度、旋转不变量，此算法由 David Lowe在1999年所首次发表，并在2004年得到完善总结。此算法已申请专利，拥有者为英属哥伦比亚大学。

局部影像特征的描述与侦测可以帮助辨识物体，SIFT 特征是基于物体上的一些局部外观的兴趣点而与影像的大小和旋转无关。对于光线、噪声、些微视角改变的容忍度也相当高。基于这些特性，它们是高度显著而且相对容易撷取，在母数庞大的特征数据库中，很容易辨识物体而且鲜有误认。使用 SIFT特征描述对于部分物体遮蔽的侦测率也相当高，甚至只需要3个以上的SIFT物体特征就足以计算出位置与方位。在现今的电脑硬件速度下和小型的特征数据库条件下，辨识速度可接近即时运算。SIFT特征的信息量大，适合在海量数据库中快速准确匹配。

SIFT算法的特点有：

1. SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性；

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

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

4. 高速性，经优化的SIFT匹配算法甚至可以达到实时的要求；

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

SIFT算法的应用范围包含物体辨识、机器人地图感知与导航、影像缝合、3D模型建立、手势辨识、影像追踪和动作比对。同时，SIFT算法可以在一定程度上可解决以下这些问题：

1. 目标的旋转、缩放、平移（RST）

2. 图像仿射/投影变换（视点viewpoint）

3. 光照影响（illumination）

4. 目标遮挡（occlusion）

5. 杂物场景（clutter）

6. 噪声

Lowe大神将SIFT算法分解为四个步骤：

1.尺度空间极值检测：通过高斯滤波操作构造不同尺度和参数的DoG金字塔，搜索所有尺度上的图像位置。通过DoG差分模拟高斯微分函数来识别极值点，这些点就是潜在的对于尺度和旋转不变的兴趣点。

2.关键点定位：为了寻找尺度空间的极值点，每一个采样点要和它所有的相邻点比较。如图所示，中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。

一个点如果在DOG尺度空间本层以及上下两层的26个领域中是最大或最小值时，就认为该点是图像在该尺度下的一个特征点。为了得到更加精确的结果，可以通过对尺度空间DoG函数进行曲线拟合寻找极值点来减小这种误差。最后，按照Lowe大神的论文，还要删除边缘效应。边缘效应的删除能够更进一步的得到稳定的特征点。因为一个物体的边缘在不同的图像中或者在同一副图像中都可能会有变化。

3.方向赋值：为了使描述符具有旋转不变性，需要利用图像的局部特征为给每一个关键点分配一个基准方向。使用图像梯度的方法求取局部结构的稳定方向。对于在DOG金字塔中检测出的关键点点，采集其所在高斯金字塔图像3σ邻域窗口内像素的梯度和方向分布特征。在完成关键点的梯度计算后，使用直方图统计邻域内像素的梯度和方向。为了简化，一般只用八个方向的直方图。

4.关键点描述子生成：SIFT描述子是关键点邻域高斯图像梯度统计结果的一种表示。通过对关键点周围图像区域分块，计算块内梯度直方图，生成具有独特性的向量，这个向量是该区域图像信息的一种抽象，具有唯一性。Lowe建议描述子使用在关键点尺度空间内4*4的窗口中计算的8个方向的梯度信息，共4*4*8=128维向量表征。也就是说每一个关键点都可以使用一个128维的向量表示。这就是SIFT的精髓所在，有了描述子向量代表关键点之后，就可以使用向量进行一系列操作，包括匹配等。

这里附上Lowe编写的SIFT算法的demo，http://www.cs.ubc.ca/~lowe/keypoints/，是第四版。关于该demo中的代码，有人做了代码解析，链接http://blog.csdn.net/joyce19920920/article/details/43644821。下载下来之后是这样。使用的方法可以阅读README。

这里面有几个.m文件，我也粘贴一个下match.m文件中的内容（CSDN中人家的排版就是好看^_^）。

根据README中的例子，使用第一个红框中的命令得到如下的结果

>> [image, descrips, locs] = sift('scene.pgm');

showkeys(image, locs);

Finding keypoints...

1021 keypoints found.

Drawing SIFT keypoints ...

这个命令是显示图片中的关键点的，图像可以是常见的任意格式（jpg,bmp,png,tif,...），最后得到的图像如下

使用第二个红框中命令得到的结果如下：

>> match('scene.pgm','book.pgm');

Finding keypoints...

1021 keypoints found.

Finding keypoints...

882 keypoints found.

Found 98 matches.

该命令是用来匹配两幅图片中相同内容的部分，并连线，最后得到的图像如下：

至此，SIFT算法介绍完毕，至于没有介绍的细节基本都是计算的，所以比较容易理解，感兴趣的同学可以深入了解。之后还是继续介绍优化算法。

以上就是今天推送的内容，欢迎讨论。