sift

..

.v.

一，SIFT简介

1，产生历史

在1999年提出了尺度不变的特征(Scale-InvariantFeature)，用来进展

物体的识别和图像匹配等[1]，并于2004年进展了更深入的开展和并加以完善[2]。SIFT

〔Scale-InvariantFeatureTransform〕算子是一种图像的局部描述子，具有尺度、旋转、

平移的不变性，而且对光照变化、仿射变换和3维投影变换具有一定的鲁棒性[1]。在

Mikolajczyk对包括SIFT算子在内的十种局部描述子所做的不变性比照实验中，SIFT及其

扩展算法已被证实在同类描述子中具有最强的强健性。

2，算法思想

算法的主要思想是在尺度空间寻找极值点，然后对极值点进展过滤，找出稳定的特征点。

最后在每个稳定的特征点周围提取图像的局部特性，形成局部描述子并将其用在以后的匹配

中。SIFT算法是基于Lindeberg[4]的理论解决了尺度不变性的问题，本文会对尺度空间理

论做一些介绍。

3，算法优点及应用

特征除具有前面所述的优点外，还具有很好的独特性，适于在海量特征数据库中进展快

速、准确的匹配；另外，算法产生的特征点在图像中的密度很大，速度可以到达实时要求；

由于SIFT特征描述子是向量的形式，它可以与其他形式的特征向量进展联合。SIFT的应用

十分广泛，包括目标识别、机器人视觉、图像检索、图像拼接、3D建模、手势识别、视频

跟踪和运动匹配等。

二，尺度空间理论

SIFT算法提取的特征点具有尺度不变性，也就是说，同一物体在图片上不管尺度大小，都

能根据SIFT算法提取到一样的特征点。这种尺度不变性是根据尺度空间理论得来的。

1，尺度思想提出

对于计算机来说，一个根本的问题是一副图片中哪些点是相互关联的以及哪些点对应着

图片场景中的一个物体。这就是原始分组和知觉组织的问题。从认知学的角度讲，在一幅图

像中，即使对一个事物没有概念，或者并不熟悉它，人仍然能够感知此物体的构造。对于人

脑来说，即使不知道为什么，也能推测场景中什么是重要的，什么仅是背景而已。

多尺度表示的概念很容易理解，举例说明，绘制地图时会有比例尺的概念。世界地图中

就只能够显示大洲大洋，以及较大的地域和国家；而一个城市地图，甚至可以详细的显示出

每条街道。

2，多尺度表示

在进展图像处理和图像理解时，从图像中提取何种信息，对图像进展何种操作，都是要

考虑的根本问题。为了有效的答复这些根本问题，可以对图像分阶段处理，前一阶段处理得

到的信息可供后续的处理使用。

多尺度表示事先并不知道到底要使用哪些尺度，所以要计算得出所有的尺度以供后面的

步骤使用。一个多尺度表示的示意图如图1所示。

..

.v.

实现多尺度表示有多种方式，比方，早期会采用四分树或者八分树，以及图像金字塔。

金字塔是结合降采样操作和平滑操作的一种图像表示方式。它的一个很大的好处是，自下而

上每一层的像素数都不断减少，这会大大减少计算量；而缺点是自下而上金字塔的量化变得

越来越粗糙，而且速度很快。〔需要强调的是，这里的金字塔构造方法和小波金字塔的构造

方法是类似的，对某一层的图像进展平滑之后，再做降采样，平滑目的是为了降采样后的像

素点能更好的代表原图像的像素点，与多尺度表示中的平滑完全不是一个目的〕。图2是金

字塔表示法的一个例如。

金字塔表示法

上面提到的四分树或者八分树以及金字塔表示法，在获得多尺度时所采取的步骤是相当

粗略的，尺度与尺度之间的“间隔〞太大。而这里要提到的“尺度空间〞〔Scale-Space〕表

示法是多尺度表示的另外一种有效方法，它的尺度参数是连续的，并且所有尺度上空间采样

点个数是一样的〔实际上，一个尺度上得到的就是一幅图像，尺度空间采样点也就是该尺度

上图像的像素点。也就是说，尺度空间表示法在各个尺度上图像的分辨率都是一样的〕。

..

.v.

尺度空间表示和金字塔表示的比照。由此也可以形象的看出多尺度和多分辨率的区别。

多尺度在所有尺度上像素数是一样的，细节通过平滑逐步丧失。

三，SIFT方法介绍

SIFT特征的优点在前面已经做了说明，下面将对SIFT方法做详细的介绍。SIFT算法有以

下几个步骤：

1.检测尺度空间的极值点。

2.抽取稳定的关键点。

3.为每个关键点指定一个或者多个方向。

4.生成特征点描述子。

3.1尺度空间的极值检测

提取尺度不变的特征点，其主要思想是提取的特征点出现在任何一个尺度上。这样不管

图像的尺度如何变化，总能够提取出这种特征点。检测尺度无关的特征点可以通过搜索所有

可能的尺度，这可以基于尺度空间理论来解决。

在一些合理的假设之下，高斯函数是得到图像尺度空间唯一可用的核函数。将图像I(x,y)

的尺度定义为一个函数),L(x,y,σ)它由高斯函数G(x,y,σ)和图像I(x,y)卷积得到：

为了在尺度空间中高效的检测稳定关键点的位置，提出在高斯差分函数与图像卷积得到的空

间D(x,y,σ)中寻找极值点，

..

.v.

其中，相邻两个尺度由一个常数k分开。

前面已经论述，为了求尺度无关的特征点，首先需要计算相邻尺度图像的差分，得到一

系列图像并在该图像空间中求极值点。采用金字塔可以高效的计算高斯差分图像，如下图：

构造金子塔，计算高斯图像的差分。

金子塔自下而上分为多层，在第一层中，对原始图像不断用高斯函数卷积，得到一系列逐渐

平滑的图像。在这一层中，相邻的高斯图像差分得到高斯差分图像。这一组进展完毕后，从

中抽取一幅图像A进展降采样，得到图像B的面积变为A的1/4，并将B作为下一层的初

始图像，重复第一层的过程。选取A的原那么是，得到A所用的尺度空间参数σ为初始尺

度空间参数的2倍。设在s个尺度中寻找极值点，那么每层要有s+3幅图像，

生成s+2幅高斯差分图像。如下图：

..

.v.

〔1〕为图像金字塔，〔2〕为生成的高斯差分图像。

上一步中已经生成了高斯差分图像，这一步中要计算该空间中的极值点。如下图：

计算极值点。每一幅高斯差分图像中的一个像素点，要和它所在图像的八邻域像素比拟，

而且要和它所在图像的上一层和下一层的各九个邻近的像素点比拟。

3.2准确定位以及抽取稳定的特征点

..

.v.

上一步已经求出了极值点，但由于在金子塔中存在降采样的图像，在这些图像中提取

的极值点还需要进一步进展更准确的定位以准确确定特征点的位置和尺度。另外，由于DOG

值对噪声和边缘较敏感，在要对这些极值点进展筛选，去除去除低比照度和不稳定的点，以

增强特征点匹配时的稳定性、提高抗噪声能力。

3.2.1准确定位特征点

通常对局部极值点进展三维二次函数拟和以准确确定特征点的位置和尺度,尺度空

间函数D(x,y,σ)在局部极值点处的泰勒展开式如公式(4)所示。

〔式4〕

通过对公式(4)求导,并令其为0,得出准确的极值位置,如公式(5)所示:

3.3.2去除低比照度的特征点

把公式(5)代到公式(4)中,只要前两项,得到公式(6):

通过式(6)计算出D(Xmax),假设|D(Xmax)|≥0.03,那么该特征点就保存下来,否那

么就丢弃。

3.2.3去除不稳定的边缘响应点

通过2×2的Hessian矩阵H来计算主曲率,由于D的主曲率与H矩阵的特征值成比例,不具体求特

征值,求其比例ratio。设α是最大幅值特征,β是次小的，r=α/β，那么ratio如公式(8)所示。通过公

式(8)求出ratio,常取r=10,假设ratio≤(r+1)2/r,那么保存该特征点,否那么就丢弃。

..

.v.

3．3确定特征点主方向

利用特征点邻域像素的梯度方向分布特性为每个特征点指定方向参数,使算子具备

旋转不变性。公式(9)为(x,y)处的梯度值和方向。L所用的尺度为每个特征点各自

所在的尺度,(x,y)要确定是哪一阶的哪一层。

在实际计算过程中,在以特征点为中心的邻域窗口内采样,并用梯度方向直方图统计

邻域像素的梯度方向。梯度直方图的范围是0～360°,其中每10°一个柱,总共36

个柱。梯度方向直方图的峰值那么代表了该特征点处邻域梯度的主方向,即作为该

特征点的方向。在梯度方向直方图中,当存在另一个相当于主峰值80%能量的峰值

时,那么将这个方向认为是该特征点的辅方向。一个特征点可能会被指定具有多个方

向(一个主方向,一个以上辅方向),这可以增强匹配的鲁棒性。通过上面的3步,图

像的特征点已检测完毕,每个特征点有3个信息:位置、对应尺度、方向。

图：由梯度方向直方图确定的梯度主方向

3.4生成SIFT特征向量

首先将坐标轴旋转为特征点的方向,以确保旋转不变性。接下来以特征点为中心取8×8

的窗口(特征点所在的行和列不取)。在下列图左图中,中央黑点为当前特征点的位置,每个小

格代表特征点邻域所在尺度空间的一个像素,箭头方向代表该像素的梯度方向,箭头长度代表

梯度模值,图中圈内代表高斯加权的范围(越靠近特征点的像素,梯度方向信息奉献越大)。

然后在每4×4的图像小块上计算8个方向的梯度方向直方图,绘制每个梯度方向的

累加值,形成一个种子点,如下列图右图所示。此图中一个特征点由2×2共4个种子点组成,

每个种子点有8个方向向量信息,可产生2×2×8共32个数据,形成32维的SIFT特征向量即

..

.v.

特征点描述器,所需的图像数据块为8×8。这种邻域方向性信息联合的思想增强了算法抗噪

声的能力,同时对于含有定位误差的特征匹配也提供了较好的容错性。

实际计算过程中,为了增强匹配的稳健性,建议对每个特征点使用4×4共16个种子点

来描述,每个种子点有8个方向向量信息,这样对于一个特征点就可以产生4×4×8共128个

数据,最终形成128维的SIFT特征向量,所需的图像数据块为16×16。此时SIFT特征向量

已经去除了尺度变化、旋转等几何变形因素的影响,再继续将特征向量的长度归一化,那么可

以进一步去除光照变化的影响。

3.5SIFT特征向量的匹配

首先,进展相似性度量。一般采用各种距离函数作为特征的相似性度量,如欧氏

距离、马氏距离等。通过相似性度量得到图像间的潜在匹配。本文中采用欧氏距离

作为两幅图像间的相似性度量。

取图像1中的某个关键点，并找出其与图像2中欧式距离最近的前两个关键

点，在这两个关键点中，如果最近的距离除以次近的距离少于某个比例阈值，那么

承受这一对匹配点。降低这个比例阈值，SIFT匹配点数目会减少，但更加稳定。

采用优先k-d树近似BBF搜索算法进展优先搜索来查找每个特征点的2个近

似最近邻特征点。

其次,消除错配。通过相似性度量得到潜在匹配对,其中不可防止会产生一些错

误匹配,因此需要根据几何限制和其它附加约束消除错误匹配,提高鲁棒性。常用的去

外点方法是RANSAC随机抽样一致性算法,常用的几何约束是极线约束关系。

4SIFT匹配实验

..

.v.

该组实验测试了算法对尺度和视角变化的适应能力。两幅图的车牌号尺度差距大，同

时具有旋转，而且图像的背景也有较大的差异，两幅图像中的对应SIFT特征点被成功匹配

出，SIFT特征保持了较好的方向性，表达出该算法的稳健性。

下一组实验使用SIFT算法将不同方位、不同焦距拍摄的、具有一定倾斜角的、亮度

不同的人体照片与复杂场景中的人体进展特征点匹配。可见本例中SIFT算法表现出较好的

目标定位能力，且能够在一定程度上排除亮度差异、视角变化和复杂场景中其他物体的影响。

..

.v.

5.总结与思考

5.1SIFT性能总结

SIFT算子可以较稳健的对发生几何形变、退化、受噪声干扰的图像局部特征进展准确

的匹配。而且由于SIFT算法在计算关键点方向时充分利用了邻域信息，这样在一定程度上

可以防止在小运动物体上匹配特征点，因为小运动物体的邻域信息即使去除了尺度和旋转的

因素后也仅是具备较少的梯度方向相似性；同时SIFT算法在计算关键点处的梯度方向时使

用了直方图统计和高斯加权的思想，这就对存在定位偏差的特征点匹配提供了更好的适应

性。

5.2算法的优越性：

SIFT之所以如此流行，一方面是由于用到的根底较为成熟，在前人的根底上进展了创

新、改良和集成；另一方面主要是由于该方法效果很好，对之前方法关键性的缺乏做了有效

的改良；其他方面，比方公开源码等开放作风也获得了诸多青睐。

5.3问题：

由于SIFT算法需要在各个尺度上进展计算，其时间复杂度相对较高，而且经

RANSAC算法后得到的有效匹配点数目往往不是很理想。对照顾、仿射变换并不是完全鲁

棒，对弹性形变更是无法适应。

5.4SURF：

SIFT算法的高时间复杂度让该算法的实际应用受到一定的障碍，为了解决该算法运行

速率问题，外国学者于2008年提出SURF〔Speeded-UpRobustFeatures〕算法。

5.5SIFTVSSURF

算法的区别：

SURF使用Hessian矩阵代替DOG算子来确定特征的尺度和位置。

SURF通过改变高斯函数核大小来得到不同尺寸的影像而不用建立影像金子塔。

SURF使用了积分图，同时改用Haar小波响应值Σdx,Σ|dx|,Σdy,Σ|dy|作为特征描述子。

从计算速度上讲，SURF明显居优。由于SURF采用了更多的近似，所以从准确度和

鲁棒性上讲，应该是SIFT更好。而学术界里，只要是涉及准确度评估的相关应用，大都会

选用SIFT，尽管SIFT有专利限制，尽管SURF是开展自SIFT的。

另外，OpenCv1.1之后的版本提供了surf算子的库函数。

RobHess写的SIFT算子源代码也可以通过下载。