转自：http://www.jellon.cn/index.php/archives/374
一、综述
Scale-invariant feature transform(简称SIFT)是一种图像特征提取与匹配算法。SIFT算法由David.G.Lowe于1999年提出，2004年完善总结，后来Y.Ke(2004)将其描述子部分用PCA代替直方图的方式，对其进行改进。SIFT算法可以处理两幅图像之间发生平移、旋转、尺度变化、光照变化情况下的特征匹配问题，并能在一定程度上对视角变化、仿射变化也具备较为稳定的特征匹配能力。
二、SIFT特征提取算法
SIFT算法首先在尺度空间进行特征检测，并确定关键点的位置和关键点所处的尺度，然后使用关键点邻域梯度的主方向作为该点的方向特征，以实现算子对尺度和方向的无关性。
SIFT算法提取的SIFT特征向量具有如下特性：
a) SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性。
b) 独特性好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配。
c) 多量性，即使少数的几个物体也可以产生大量SIFT特征向量。
d) 高速性，经优化的SIFT匹配算法甚至可以达到实时的要求。
e) 可扩展性，可以很方便的与其他形式的特征向量进行联合。
一幅图像SIFT特征向量的生成算法总共包括4步：尺度空间极值检测、关键点位置及尺度确定、关键点方向确定、特征向量生成。最后通过特征向量完成特征点的匹配。
2.1尺度空间极值检测
机器人在环境中走动时，摄像机和环境中物体的相对位置会发生变化，导致图像上物体的特征的尺度发生变换。我们希望特征具有尺度不变性，即当特征尺度变化时，特征点检测器仍然能够准确的检测出特征点及其尺度。为满足以上条件，特征检测需要在多尺度空间的框架下进行。
尺度空间理论是检测不变特征的基础。Witkin(1983)提出了尺度空间理论，他主要讨论了一维信号平滑处理的问题。Koenderink(1984)把这种理论扩展到二维图像，并证明高斯卷积核是实现尺度变换的唯一变换核。
二维高斯函数定义如下：
一幅二维图像，在不同尺度下的尺度空间表示可由图像与高斯核卷积得到：
其中(x,y)为图像点的像素坐标，I(x,y)为图像数据。σ称为尺度空间因子，它也是高斯正态分布的方差，其反映了图像被平滑的程度，其值越小表征图像被平滑程度越小，相应尺度越小。L代表了图像的尺度空间。
为高效的在尺度空间内检测出稳定的特征点，Low使用尺度空间中DoG
(Difference -of-Gaussian)极值作为判断依据。DoG算子定义为两个不同尺度的高斯核的差分，是归一化LoG (Laplacian-of-Gaussian)算子的近似。设k为两相邻尺度间的比例因子，则DoG算子定义如下：
选择DoG算子作为检测函数有一定的原因。首先，DoG算子计算简单，只需要将两个高斯平滑后的图像L相减即能得到，执行效率较高；其次，DoG算子检测出的特征点稳定性较好，与LoG检测效果相近(Mikolajczyk 2002)。
Lowe采用的
构造方式如图1，其建立高斯图像（图中左列）与DoG（图中右列）两个金字塔。高斯图像金字塔分为多组，每组间又分为多层。一组中的多层间不同的是尺度，相邻层间尺度相差一个比例因子k。为在S个尺度间隔内变化尺度因子，如使σ加倍，则k应为
。而为了在整个金字塔内获取DoG极值，应在高斯金字塔中生成S+3层高斯平滑图像。下一组的图像的最底层由上一组中尺度为2σ的图像进行因子为2的降采样得到，其中σ为上一组中最底层图像的尺度因子。DoG金字塔由相邻的高斯图像金字塔相减得到。
图1 高斯图像金字塔（S=2）与DoG金字塔
金字塔中每个高斯图像的σ为：
其中
为基础尺度因子；o, s分别为图像所在的图像组坐标、组内层坐标，
，
，（实际应为
，为在整个金字塔内获取DoG极值，有S+3层高斯平滑图像）；
是第一个金字塔组的坐标，通常
取0或者-1，当设为-1的时候，则图像在计算高斯尺度空间前先扩大一倍。在Lowe的算法实现中以上参数分别取值如下：
，
，
。
另外，空间坐标x是组坐标o的函数。设
第o组内的空间坐标，则有：
其中
是第o组中图像的分辨率。设
为第0组中的图像分辨率，则其他组的分辨率为：
金字塔构造完后开始检测DoG局部极值。其中每个像素需要跟同一尺度的周围邻域8个像素和相邻尺度对应位置的周围邻域9*2个像素总共26个像素进行比较，如图2。仅当被检测点的DoG值大于此26个像素点或小于此26个像素点时才将该点判定为极值点并保存以进行后续计算。
图2 DoG空间局部极值检测
2.2关键点位置及尺度确定
通过拟和三维二次函数以精确确定关键点的位置和尺度（如图3），同时去除低对比度的关键点。其中Lowe使用了DoG函数的泰勒公式展开的方法(Brown and Lowe, 2002)。
图 3 精确确定关键点位置和尺度
去除不稳定的边缘响应点，以增强匹配稳定性、提高抗噪声能力。其使用的边缘相应检测算子为：
H为Hessian矩阵。Lowe在实现时取r=10。
2.3关键点方向确定
通过确定关键点的方向，可以使特征描述符以与方向相关的方式构造，从而使算子具有旋转不变性。关键点的方向利用其邻域像素的梯度分布特性确定。对每个高斯图像，每个点
的梯度的模
与方向
可以通过如下公式计算得到：
其中L所用尺度为关键点所在尺度。
对每个关键点，在以其为中心的邻域窗口内利用直方图的方式统计邻域像素的梯度分布。此直方图有36个柱，每柱10度，共360度。每个加入直方图的邻域像素样本的权重由该像素的梯度模与高斯权重确定。此高斯窗的σ为关键点的尺度的1.5倍，加入高斯窗的目的是增强离关键点近的邻域点对关键点的影响。
直方图的峰值反映了关键点所处邻域梯度的主方向。完成直方图统计后，找到直方图的最高峰值以确定关键点的方向。关键点的方向可以由离最高峰值最近的三个柱值通过抛物线插值精确得到。如图4。
图4 由梯度方向直方图确定主梯度方向
在梯度方向直方图中，当存在一个大于等于主峰值80%能量的峰值时，则添加一个新关键点，此关键点的坐标、尺度与当前关键点相同，但方向为由此峰值确定的方向。因此一个关键点可能产生多个坐标、尺度相同，方向不同的关键点。这样做的目的是增强匹配的鲁棒性。
至此，特征点检测完毕，特征描述前的准备工作已经完成。每个关键点含有三个信息：坐标、尺度、方向。
2.3特征向量生成
设特征点的方向是θ，则先将特征点的邻域旋转-θ角度，这样保证了旋转不变性。然后将邻域划分为4×4=16块,对每一块利用特征点方向确定时采用的方法统计一个梯度直方图，每个直方图有8个柱，如图5。这样得到一个4×4x8=128维的特征向量。此时SIFT特征向量已经去除了尺度变化、旋转等几何变形因素的影响。
图5 特征点的特征向量构造
最后要对特征向量进行处理以使其适应光照变化。首先要对特征向量进行归一化。图像发生对比度变化表现为每个像素点的值以及该点梯度方向的模均变为原来的常数倍，因此对特征向量进行归一化能消除图像对比度变化的影响。光照强度变化理论上不会对特征向量产生影响，因为光照强度变化表现为每个像素点的值增加了一个常数，因此像素点间的差值没有发生改变，梯度值即没有发生变化。至此特征向量已对光照的仿射变化具有了不变性。然而非线性的光照变化也可能发生，此时对像素点梯度方向产生影响相对较小，而对梯度的模产生较大影响。为了减小值较大的梯度的模的影响，我们可以设定一个阈值，使特征向量中的128项均小于等于该阈值，最后再对特征向量进行一次归一化即可。Lowe算法中设定此阈值为0.2。
2.4特征点匹配
当两幅图像的SIFT特征向量生成后，下一步将采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。
然而由于遮挡等原因，匹配可能出现错配的情况，需要采取一些措施降低错配率。为每对匹配特征点的特征向量欧式距离加阈值的方法并不合适，因为特征点可能有较强的独特性，其匹配点对特征向量的欧式距离较大是正常的。一种比较有效的方法是在匹配时比较与关键点的特征向量最近的和次近的关键点。取图像1中的某个关键点，并找出其与图像2中欧式距离最近的前两个关键点，在这两个关键点中，如果最近的距离除以次近的距离少于某个比例阈值，则接受这一对匹配点，如下式子：
降低这个比例阈值，SIFT匹配点数目会减少，但更加稳定。Lowe在实现过程中取r=0.8，此时虽然会去掉约5%的正确匹配，但同时会去掉约90%的错误匹配。
转自：http://bubblexc.com/y2011/163/
SIFT是我接触最早的图像局部特征描述子之一，其实最初，始终觉得局部特征描述子是些非常玄虚的东西。对于SIFT，这种感觉更是尤为强烈，“尺度空间”“拉普拉斯高斯算子（LoG）”“高斯差分金字塔”，一系列让人头痛的概念。不过，反反复复看了几次，渐渐也就有了感觉，在此总结一下。
物体识别的核心问题是将同一目标在不同时间、不同分辨率、不同光照、不同位姿情况下所成的像相相匹配。而为了进行匹配，我们首先要合理的表示图像。由于目标的自身状态、场景所处的环境的影响，同一类物体在不同的图像中所成的像往往会差别很大，但即使这样，人们所能通过同一物体的一些局部共性来识别出物体（正如我们能将不同国家民族的人区分出来）。所谓局部特征描述子就是用来刻画图像中的这些局部共性的，而我们也可以将一幅图像映射（变换）为一个局部特征的集合。理想的局部特征应具有平移、缩放、旋转不变性，同时对光照变化、仿射及投影影响也应有很好的鲁棒性。传统的局部特征往往是直接提取角点或边缘，对环境的适应能力较差。1999年British Columbia大学 David G.Lowe(http://www.cs.ubc.ca/~lowe/) 教授总结了现有的基于不变量技术的特征检测方法，并正式提出了一种基于尺度空间的、对图像缩放、旋转甚至仿射变换保持不变性的图像局部特征描述算子－SIFT（尺度不变特征变换），这种算法在2004年被加以完善。
SIFT算法的实质可以归为在不同尺度空间上查找关键点（特征点）的问题。所谓关键点，就是一些十分突出的点，这些点不会因光照条件的改变而消失，比如角点、边缘点、暗区域的亮点以及亮区域的暗点，既然两幅图像中有相同的景物，那么使用某种方法分别提取各自的稳定点，这些点之间就会有相互对应的匹配点。而在SIFT中，关键点是在不同尺度空间的图像下检测出的具有方向信息的局部极值点。涉及到的最重要的两步是：1.构建尺度空间 2.关键点检测
· 构建尺度空间
先来谈谈尺度的问题。我们要精确表示的物体都是通过一定的尺度来反映的。现实世界的物体也总是通过不同尺度的观察而得到不同的变化。比如说，对同一物体拍照，我们拍摄了一副近景，一副远景，虽然两幅图片中都有这个物体，但这个物体确是处于两个不同的尺度。SIFT特征具有尺度不变性，就是说即使同一物体处于两个不同的尺度的图像中，我们仍可以通过提取图像的SIFT特征匹配成功。
图像的尺度有多种表示方法（金字塔、八叉树等等），在SIFT中Lowe教授采用了尺度空间理论。其主要思想是通过对原始图像进行尺度变换，获得图像多尺度下的尺度空间表示序列，并检测这个序列中的关键点。这样图片就被映射为多个尺度上的关键点信息，尽管两幅图片是处于不同的尺度，但却可以提取出在尺度变换中没有改变的关键点，从而进行关键点匹配，进而识别出物体。
实际上，在尺度空间理论中，是通过对图像进行模糊来模拟多尺度下的图像。直观上，图像的模糊程度逐渐变大，模拟了人在距离目标由近到远时目标在视网膜上的形成过程。文献《Scale-space theory: A basic tool for analysing structures at differentscales》(http://www.csc.kth.se/~tony/abstracts/Lin94-SI-abstract.html)证明，高斯核是唯一可以产生多尺度空间的核（其它核会对图像造成模糊之外的其它影响）。一个图像的尺度空间， L (x, y , σ ) （ σ 可以代表尺度的大小），定义为原始图像 I ( x, y ) 与一个可变尺度的2维高斯函数 G (x, y , σ ) 卷积运算。高斯函数：
G (x, y , σ )=
1 /2 πσ 2 e[ − ( x 2 + y 2 )/( 2 σ 2 ) ]
L (x, y , σ )= G(x, y , σ ) ∗ I ( x, y )
需要的注意的是，图像的尺度是自然存在的，不是人为创造的！高斯卷积只是表现尺度空间的一种形式。（在SIFT的代码中，进行高斯模糊时，用到了高斯模糊的“勾股定理”：例如，使用半径分别为 6 和 8 的两次高斯模糊变换得到的效果等同于一次半径为 10 的高斯模糊效果）。
在SIFT中，构建了高斯金字塔（如图1所示），即分为两步：1）对图像做高斯平滑 2）对图像做降采样（减小计算量）。一幅图像可以产生几组（octave）图像，一组图像包括几层（interval）图像。为了让尺度体现出连续性，相邻两层图像间的尺度为k倍的关系，同时相邻两组的同一层尺度为2倍的关系（在SIFT算法中，Lowe教授假设初始图片已经是以一定 σ 模糊过得了）。
· 关键点检测
文献《Scale-spacetheory: A basic tool for analysing structures at different scales》(http://www.csc.kth.se/~tony/abstracts/Lin94-SI-abstract.html)指出尺度规范化的LoG算子具有真正的尺度不变性。即我们可以在不同尺度的图像（已经经过高斯卷积）上进行拉普拉斯运算（二阶导数），并求极值点，从而求出关键点。但这样做的运算量很大，于是SIFT中进行了近似处理：
∇ 2 G = ∂2 G ∂ x 2 + ∂2 G ∂ y 2
LOG (x, y , σ )= σ 2 ∇ 2 G ≈ Gauss (x, y , kσ )− Gauss (x, y , σ ) σ 2 ( k−1)
G ( x, y , kσ )− G( x, y , σ )≈( k−1) σ 2 ∇ 2 G
通过推导可以看出，LoG算子与高斯核函数的差有直接关系，由此引入一种新的算子DoG（Difference of Gaussians），即高斯差分算子：
D ( x, y , σ ) =[
G( x, y , kσ ) − G( x, y , σ ) ] ∗ I ( x, y ) = L( x, y , kσ )– L( x, y , σ )
可以看出，LoG算子和DoG算子指相差常数系数，而这并不会改变极值点的位置。因此我们在DoG算子中求得极值点就是LoG算子的极值点，也正是我们需要的关键点。而DoG在计算上只需相邻尺度高斯平滑后图像相减，因此简化了计算！
对应DOG算子，我们要构建DOG金字塔
如下图，我们可以通过高斯差分图像看出图像上的像素值变化情况。如果没有变化，也就没有特征。特征必须是变化尽可能多的点。本质上，DOG图像描绘的是目标的轮廓。
关键点是由DOG空间的局部极值点组成的。为了寻找DoG函数的极值点，每一个像素点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。具体来说，中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。
至此就可以检测出图像中尺度不变的关键点，然后我们为关键点赋予梯度方向，并利用关键点的周围的像素梯度方向直方图生成SIFT特征描述子。具体过程可以参考以下资料
1、SIFT的matlab程序，非常详细 http://www.vlfeat.org/~vedaldi/code/sift.html
2、SIFT tutorial http://www.aishack.in/2010/05/sift-scale-invariant-feature-transform/
3、一个非常详细ppt教程，可用作教学http://wenku.baidu.com/view/53021cf24693daef5ef73daf.html
