Distinctive Image Features from Scale-Invariant Keypoints (SIFT)全文翻译

本文主要是介绍Distinctive Image Features from Scale-Invariant Keypoints (SIFT)全文翻译，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

pdfl链接：https://pan.baidu.com/s/1Z-HY0Pr8pn11hJqQbfPAWw
提取码：yyds

Distinctive Image Features from Scale-Invariant Keypoints

DavidG.Lowe Computer Science Department, University of British Columbia, Vancouver, B.C., Canada

摘要

本文提出了一种从图像中提取独特不变特征的方法，可用于不同视角之间目标或场景的可靠匹配的方法。这种特点对图像的尺度和旋转具有不变性。并在大范围的仿射变换，三维视点的改变，噪音和光照变化的图像匹配具有鲁棒性。特征是highly distinctive的，使场景图像中的单一特征和许多图像中提取的大型特征数据库一样，有很高的正确匹配率。本文还介绍了一个使用该特征来识别目标的方法。通过将个别特征与由已知目标特征组成的数据库进行快速最近邻算法的匹配，然后使用Hough变换来识别属于单一目标的类簇(clusters)，最后通过执行一致的构成参数的最小二乘解来验证。这种识别方法可以在杂乱和遮挡的对象间鲁棒的识别目标并且具有接近线性的时间复杂度。
关键词：不变特征，目标识别，尺度不变性，图像匹配

1.Introduction

图像匹配是计算机视觉领域中很多问题的关键，包括目标和场景识别、多幅影像的3Dstructure、stereo correspondence、motion tracking等。本文描述的图像特征有很多特性使得它适合将一个目标或场景的不同影像进行匹配。这些特征对于图像尺度和旋转具有不变性，并在光照变化和三维相机视点变化的情况下具有部分的不变性。它在空间域和频率域具有很好的局部性，减少了遮挡（occlusion）、杂乱和噪音的影响。通过有效的算法，可以从典型的图像中提取海量的特征。另外，这些特征是highly distinctive的，使场景图像中的单一特征和大型特征数据库一样，有很高的正确匹配率，为目标和场景识别提供了基础。

通过一个级联滤波算法将minimized提取这些特征的cost，这样，昂贵的运算仅在通过初步测试的locations。下面是生成图像特征集的主要步骤：

1.Scale-space extrema detection：第一阶段对所有尺度和图像locations进行搜索。通过使用difference-of-Gaussian function高斯差分函数来识别对于尺度和方向具有不变性的潜在兴趣点。

2.Keypointlocalization：在每一个候选location，一个detailed model适合于确定位置和尺度。基于关键点的稳定性来选择关键点。

3.Orientationassignment：基于局部图像的梯度方向，给每个keypoint location指定一个或多个方向。后面所有操作的图像数据都是将每个特征的方向、尺度和位置进行相关变换得到的，因此特征对这些变换具有不变性。

4.Keypointdescriptor：局部梯度是在所选尺度上每个关键点附近的区域测量得到的。这些局部梯度可以转化为允许强烈的局部形状扭曲和光照变化的图像表示法。这种方法被命名为Scale Invariant Feature Transform(SIFT)，把图像数据转换到对于局部特征尺度不变的坐标上。

该方法的一个重要方面是它生成了大量特征，它们密集的覆盖了图像所有的尺度和locations。一幅500*500像素的典型图片可以产生约2000个稳定的特征（这个数字依赖于图像内容和几个参数的选择）。特征的数量对目标识别尤为重要，要检测杂乱背景下的小目标，至少要求每个目标有三个特征被正确匹配才是可靠的识别。对于图像匹配和识别，从一组参考图像中提取SIFT features并存储在数据库中，通过将新图像中的各个特征与原有数据库进行对比并基于特征向量的欧氏距离找到候选匹配特征。本文将讨论可以在大型数据库中进行快速计算的fast nearest-neighbor algorithms。

关键点描述子是highly distinctive的，可以使单个特征在大型特征数据库中以很大概率进行正确匹配。然而，在杂乱的图像中，很多背景中的特征在数据库中不存在正确匹配，产生了很多错误的配对。通过标识与新图像在the object and its location、尺度和方向一致的关键点的子集，将正确的匹配从匹配的全集中过滤出来。几个特征的这些参数恰好一致的概率比任一个特征匹配错误的概率要小很多。可以通过一个高效的广义Hough transform的散列表快速确定这些一致的类簇。

每个拥有三个及三个以上与目标一致的特征的类簇的构成需进一步的更详细的验证。首先，最小二乘估计是the object pose(对象构成)的仿射近似。其他与此构成一致的图像特征被标识出来，而离群点被丢弃。最后，详细的计算可以认为是一个特定的特征集合表明目标存在的概率，给出匹配的准确率和可能的错误匹配数。通过这些测试的Object matches可以认为就是正确的匹配。

2.Related Research

使用一组局部兴趣点来进行图像匹配的发展可以追溯到1981年Moravec在立体匹配中使用的corner detector(角点检测)。Moravec的detector在1988年被Harris和Stephens改进，在小的图像变动和近边缘区域具有了更高的可重复性。Harris还展示了它在高效运动追踪和从motion recovery中进行3Dstructure的价值(Harris，1992)。此后，Harris角点检测被广泛运用于图像匹配工作中。尽管这些特征检测器被称为cornerdetectors，但它并不是只能选择角，还可以选择在一个尺度的各个方向上具有大的梯度的图像location。

该方法的最初应用是立体和短距离运动追踪，而后来被扩展到解决一些更困难的问题。Zhang等人在1995年在每个角点周围的相关窗口来选择可能的匹配，使得大幅图像范围的Harris角点匹配成为可能。通过求解严格场景的两个视角间的几何约束的基础矩阵和移除与多数解不一致的配对来移除异常值。同年（1995），Torr提出了一种类似的方法来进行远程的运动匹配，使用几何约束来移除图像中rigid objects的移动的离群点。1997年，Schmid和Mohr的开创性工作展示了不变的局部特征匹配可以被扩展到解决一般的图像识别问题，即使用一个特征与大型图像数据库进行匹配。他们还使用Harris角点检测来选择兴趣点，但他们使用一个图像局部区域旋转不变的描述子来代替相关窗口进行匹配。这些特征可以在两幅图像之间进行任意方向变化时进行匹配。此外，他们还证明多特征匹配可以通过标识一致的匹配的特征的类簇，在遮挡和混杂的情况下实现一般的识别。

Harris角点检测对图像尺度的变化非常敏感。因此，对于不同尺度的图像匹配，Harris角点检测并不能提供很好的基础。本文作者（Lowe）在1999年的早期工作中扩展了这种局部特征方法来实现尺度不变性。该工作还阐述了一种新的局部描述子，给出一个more Distinctive的特征，可以降低对局部图像变形的敏感度（如三维视点的变换）。本文提出了对这一方法更加深入的研究，并分析了这些早期的工作，在稳定性和特征不变性上进行了大量改进。在之前的研究中，关于在尺度变换下表征（representation）的稳定识别占了很大的篇幅。最早在这个领域进行研究的有Crowley和Parker，1984年，他们研究出一种表征法，标识峰和脊并把它们放入一个树结构中。树结构的匹配可以在任意尺度变换的图像间进行。在近期基于图的匹配工作中，Shokoufandeh等人在1999年使用小波系数提出了一种more distinctive的特征描述子。Lindeberg在1993-1994年对为特征提取找到一个合适并且一致的尺度这一问题进行了深入研究。他称之为尺度选择问题，我们在下面使用了这一结论。

最近，有了大量令人印象深刻的将局部特征扩展为全局仿射变换不变量的工作（Baum berg，2000；Tuytelaars和Van Gool，2000；Mikolajczyk和Schmid，2002；Schaffalitzky和Zisserman，2002；Brown和Lowe,2002）。这使得在变化的正射三维投影平面上的特征匹配具备了不变性，多数情况下采用对图像局部仿射框架进行重采样的方法。然而，还没有一个方法实现了完全的仿射不变性，由于充分勘探仿射空间的成本过高，因此他们用一个非仿射不变的方式对最初的特征尺度和位置进行选择。仿射框架与尺度不变的特征相比，对噪音更加敏感，因此，实践中除非在仿射变形与平面倾斜程度大于40度时（Mikolajczyk，2002），仿射特征比尺度不变的特征重复率要低。对于很多应用，更宽的仿射不变性可能并不重要，因为为了获得三维目标的非平面变化和遮挡的影响，瞄准视角至少每30度旋转一下视点（也就是说对于最靠近的瞄准视角，识别也是在15度以内进行的）。

尽管本文中的方法不具备完全的仿射不变性，但它使用了一种独特的方法来使局部描述子可以随着描述子很小的变化来显著地改变相关特征的位置。这种方法不仅使描述子可以在相当大范围的仿射变形时进行可靠地匹配，还可以使特征在非平面的三维视点变化时具有更好的鲁棒性。另一个优点是它可以更高效地提取特征，并可以标识更多特征。另一方面，在非常大的视角变化下，仿射不变性是匹配平面非常有价值的属性，以后的研究应该以高效而稳定的方式将这一点与非平面的三维视点不变性结合。

许多其他的特征被提出用于识别，其中一些可以加入到本文所述特征中以在不同环境中的进行进一步匹配工作。其中一类特征是利用图像轮廓或区域边缘的特征，这可以减少特征在目标边界附近混乱背景的干扰。Matas等人在2002年提出他们的最稳定极值区域可以产生大量具有良好稳定性的匹配特征。Mikolajczyk等人在2003年使用局部边缘（edge）而忽略附近的无关边缘，提出一种新的描述子，即使在与杂乱的背景上狭窄形状的重叠的目标边界附近也可以在寻找稳定的特征。Nelson和Selinger在1998年使用基于图像轮廓分组的局部特征得到了很好的结果。类似的，Pope和Lowe在2000年使用的是基于图像轮廓的层级分组的特征，尤其是对于缺少纹理细节的目标非常有用。

对于视觉识别的研究历史包括一组可被用作特征测量的多样的其他图像属性数集的工作。Carneiro和Jepson在2002年描述了一种基于相位的局部特征来表示相位来而不是局部空间频率的量级，提高了特征的光照不变性。Schiele和Crowley在2000年建议使用多维直方图来概括图像区域内的测量值的分布。这种特征对于纹理明显的形状畸变的目标识别尤为有效。Basri和Jacobs在1997年证明了提取局部区域边界对于识别的价值。其他可以合并的有用属性如颜色、运动、图形-背景差异、区域形状描述子和立体深度信息等。局部特征方法可以轻易吸纳新的特征类型，因为其他特征提供正确的匹配来提高鲁棒性，并且除了它们的计算成本外(对正确率)影响较小。因此，以后的系统可能会由很多特征类型组合而成。

3.Detection of Scale-Space Extrema

引言中已经提到，我们使用高效的方法来标识候选位置然后再进一步详细检查的级联滤波方法来探测关键点。关键点检测的第一阶段是标识同一目标在不同视角下可被重复分配的位置和尺度。使用尺度连续函数(尺度空间Witkin，1983)，在所有可能的尺度中搜索稳定特征，检测图像中具有尺度变换不变性的locations。

Koenderink和Lindeberg分别在1984年和1994年提出，在一系列合理的假设下，唯一的尺度空间核是高斯函数。因此，图像的尺度空间被定义为函数L(x,y,σ)，是由尺度可变的高斯函数G(x,y,σ)和输入图像I(x,y)的卷积生成的：

其中*为x和y之间的卷积运算，

为了高效地在检测尺度空间中稳定的关键点locations，我们(Lowe，1999)使用difference-of-Gaussian(高斯差分)函数中的尺度空间极值与图像进行卷积。()可由两个由常数乘系数k分离的相邻尺度的差值计算得到：

有很多选择这个函数的理由。首先，这是一个计算起来相当高效的函数，因为平滑图像L需要计算尺度空间特征描述的所有情况，而D只需由简单的图像减法计算。

另外，Lindeberg于1994年研究表明，高斯差分函数可以给出尺度规一化的高斯拉普拉斯(LOC)算子的近似解。Lindeberg(1994)提出参数归一化的拉普拉斯算账需要真正的尺度不变性。在详细的实验对比中，Mikolajczyk 2002年发现，与其他可能的图像函数如梯度法、Hessian法和Harris角点函数相比，的最大值和最小值产生了最稳定的图像特征。

所以，

这表明，高斯差分函数被常系数区分为各个尺度后，它就包含了尺度不变的拉普拉斯算子要求的尺度归一化。在所有尺度下，等式中的系数(k-1)是一个常数，因此不影响极值的位置。k越接近1，逼近误差就越趋于0，但是实践中我们发现，即使是显著的尺度差异如，近似值对极值检测的稳定性和或定位几乎没有影响。

D(x,y,σ)的构建方法如图1所示。初始图像与高斯算子卷积形成图像，通过常数系数k在尺度空间中将图像分开，如左图中堆放的层。我们将尺度空间的每个octave组(如的两倍)分为一个整数，间隔为s，即我们必须为每个octave组在模糊图像堆中建立s+3幅图，所以最后的极值检测覆盖一个完整的octave组。相邻的图像尺度相减生成高斯差分图像，如右图所示。一旦一个完整的octave处理完成，我们就以每行或每列两个像素对初始值为σ的两倍的高斯图像(即堆顶的两幅图像)进行重采样。相对于σ，采样的精度与之前的octave没有差别，但计算量被大大地减小了。

图1.对于每个尺度空间的组，初始图像与高斯函数多次卷积所得尺度空间如图像左边所示。相邻的高斯图像相减产生了右边的差分高斯图像。每个组后，高斯图像被系数2降采样，重复该过程

3.1 Local Extrema Detection

为检测D(x,y,sigma)的局部最大值和最小值，每个样本点都要和它当前图像的八个近邻点以及上下尺度上的各九个近邻点进行比较(如图2)。比所有近邻点都大或小的点才会被选择。因为前几次检查中大多数的样本点会被排除，这个检查的代价相对较小。

图2.，通过将一个像素(记为叉)与其在当前的尺度和邻近尺度近邻的3*3区域内的26个像素(记为圆)进行对比，检测高斯差分图像中的最大值和最小值

确定图像和尺度域中的采样频率非常重要，需要对极值进行可靠地检测。但是，不存在可以检测所有极值的最小采样间隔，因为极值可以随意的靠近。可以想象有一个白色的圆圈在黑色背景中，会有一个单尺度空间的极大值，在高斯差分函数的正中心与圆的大小和位置匹配。对于一个细长的椭圆，椭圆的每一端(end)附近有两个极大值。极大值的locations是图像的一个连续函数，对于中间被拉长的椭圆会有从一个极值到两个极值的过渡，极值会任意的彼此接近。

因此，我们必须使用一个权衡效率和完整性的方案。实际上，正如预期的并且经过实验证实，相邻近的极值对图像很小的变动是不稳定的。通过对一个范围内的采样频率研究并使用在匹配任务的模拟中提供最可靠结果的采样频率来选择最好的极值点。

3.2 Frequency of Sampling in Scale

图3.第一幅图上一条线是关键点在一幅被转换的图像的同一位置和尺度被重复探测的百分率，是每个octave组采样的尺度数的函数。下面的线是关键点的描述子与大型数据库正确匹配的百分率。第二幅图表示的是在一幅典型图像中被探测到的关键点总数，是尺度采样数的函数

如图3和图4所示为采样频率所决定的取极大值的稳定性实验。这些图(以及本文中的大多数模拟)是基于一组32幅不同范围的真实图像的匹配工作，图像包括外景、人脸、航空影像和工业图像(经研究发现图像域对结果无任何影响）。每幅图像都经过了一系列的变换，包括旋转、缩放、仿射拉伸、明亮度对比度变化和增加图像噪声。改变是综合的，这样才有可能精确地推断初始图像的每个特征在转换后的图像中如何呈现，从而可以对每个特征测量正确的重复率和位置的准确性。

图4.图中顶部的线是关键点位置在转换的图像中被重复探测到的百分率，是每个octave组第一层的先验图像的平滑函数

图3所示为用于检查在极值探测前采样的图像函数每个组尺度数变化的效果。在这个情况下，每幅图像都经过随机角旋转和初始图像0.2-0.9倍的随机缩放，然后被重采样。降分辨率图像的关键点与初始图像进行匹配，因此所有关键点的尺度将被呈现在匹配图像中。另外，添加了1%的图像噪声，也就是说在[0,1]范围内变化的像素值将被随机添加一个在[-0.01,0.01]内等间距变化的随机数字(相当于降低图像像素6比特的准确度)。

图3中的首行为关键点在一幅转换后图像进行匹配，位置和尺度被探测到的百分率。本文中所有的例子，我们都将匹配尺度定义为正确尺度的根2倍，匹配位置为σ个像素以内，σ为关键点的尺度(定义为高斯差分函数中使用的最小高斯函数的标准差)。图中下面的行为使用最近邻匹配法，与有40,000个关键点的大型数据库正确匹配的关键点数，详细过程在第六章讲述(表明关键点被重复定位对识别和匹配工作非常有利)。这幅图表示当每个组采样3个尺度时，重复率最高，这也是本文中其它实验所使用的采样尺度数。

采样的尺度是不是越高重复率就越好，这一点可能让人觉得有些奇怪。这是因为在很多被探测到的局部极值结果中，这些(尺度高的)结果稳定性较差，因此在转换图像中被探测到的几率也就降低了。可以由图3中的第二幅图看出，关键点被探测出来的平均数以及每幅图像中正确的匹配数。关键点数随采样尺度增加而提高。由于目标识别成功与否更多的是依赖于关键点正确匹配的数量，而不是它们匹配的正确率，因此对于很多应用而言，选择较大的尺度采样才是最佳选择。然而，计算成本也会随之增大，因此本文中的实验我们选择使用每个组3个采样尺度。

总而言之，这些实验表明尺度空间的高斯差分函数有很多的极值，但是将它们都检测出来成本很高。幸运的是，即使只使用较粗的尺度采样页可以检测到最稳定且有用的极值子集。

3.3 Frequency of Sampling in the Spatial Domain

正如我们确定尺度空间中每octave组的采样频率，我们必须确定与平滑尺度相关的图像域的采样频率。极值可能任意程度上的接近彼此，会有一个类似的采样频率和检测率的权衡。图4所示为优先平滑的数目的决策实验，σ在建立一octave组的尺度空间表示前被应用于每个图像层。同样，图中顶部的那条线表示关键点探测的重复性，结果显示重复性随σ的增大而增大。然而，使用大的σ在效率方面有影响，我们取σ=1.6来实现接近最优的重复性。这个值在本文中(包括图3中的结果)被普遍应用。

当然，如果在极值检测前对图像进行预平滑处理，我们就有效地剔除了最高的空间频率。因此，要充分利用输入，图像可以被扩展来产生比初始图像提供的更多的采样点。在建立金字塔第一层之前，我们使用线性插值使输入图像的大小加倍。等价操作可以通过对原始图像使用亚像素补偿滤波实现，但图像加倍的实现更加有效。我们假设原始图像有至少σ=0.5的模糊(防止显著混淆现象的最小值)，因此加倍的图像相对其新的像素空间来说应该有σ=1.0模糊。这意味着在创建尺度空间的第一octave组前，增加适度的平滑是必要的。图像加倍使稳定的关键点数增加了近4倍，但使用更大的扩展系数没有更大的提高。

4.Accurate Key point Localization

通过一个像素与其近邻的比较可以得到关键点的候选值，下一步就是对关键点临近点的数据(位置、尺度和主曲率)进行细节匹配(fit)。这些细节匹配信息使低对比度(对噪音敏感)或定位在边缘上的点被淘汰。

该方法原本(Lowe,1999)是简单地定位在中心样本点的位置和尺度上的关键点。但是Brown最近改进了此方法(BrownandLowe,2002)，通过将一个三维二次方程嵌合局部样本点上来决定最大值的插值位置，实验表明这一改进很大程度地提高了匹配和稳定性。他的方法使用了尺度空间方程D(x,y,σ)的泰勒展开(到二阶)式，把样本点作为原点。

图5所示为在自然图像上进行关键点选择的结果。为防止过于杂乱，用一个233*189像素的低分辨率图像，关键点表现为矢量形式，给出了每个关键点的位置、尺度和方向(方向的赋值见下文)。图5(a)所示为原始图像，后面的图像对其进行了降对比度。图5(b)所示为高斯差分函数检测到的所有极大值和极小值上的832个关键点。而(c)

图5.本图表示的是关键点选择的阶段。(a)233*189个像素的初始图像。(b)高斯差分公式最大值和最小值确定出的832个关键点位置，关键点被显示为矢量形式，表示尺度，方向和位置。(c)对最小对比度值对比设置阈值后，还剩下729个关键点。(d)附加一个主曲率阈值后，最终剩下的536个关键点

4.1 Eliminating Edge Responses

对稳定性而言，只去除低对比度的关键点是不够的。即便在边缘处的点只有很小的决策性，高斯差分函数会在边缘处有很强的反应，因此对很小的噪声也不稳定。

高斯差分函数中一个不好的峰值将会对边缘处产生很大的主曲率，而在垂直方向上产生很小的主曲率。主曲率可以通过一个2*2的Hessian矩阵H来计算，在关键点的位置和尺度上计算H：

通过对近邻样本点的差分来估计导数值。

H的特征值与D的主曲率成正比。借用Harris和Stephens(1988)的方法，可以明确地避免特征值的计算，因为我们只关心它们的比值。设为最大的特征值，为最小的，我们可以通过求H的迹来获得特征值的和，从行列式获得它们的积：

这个计算非常高效，当对每个关键点只需进行小于20次的浮点运算。本文实验使用的r=10，排除主曲率间的比值大于10的关键点。图5中(c)到(d)的即为这个操作的结果。

5.Orientation Assignment

基于局部图像属性给每个关键点指定一个一致的方向，关键点描述子可以与这个方向相关，从而实现图像旋转的不变性。本文方法与Schmid和Mohr（1997）的方向不变描述子算法做对比，他们的算法中，每个图像属性都是基于一个旋转不变测度，缺点是它限制了可用的描述子，且因为没有要求所有测量都基于一个一致的旋转而丢失了图像信息。

实验使用了很多方法来指定局部方向，下面的方法为找到最多稳定结果的。关键点的尺度是用来选择尺度最接近的高斯平滑图像L的，这样所有的计算都是在一个尺度不变条件下进行的。对于每个图像样本L(x,y)，在该尺度下，梯度量级m(x,y)和方向θ(x,y)是用像素差预计算出来的：

关键点周围区域的样本点的梯度方向组成一个方向直方图，方向直方图有36bins，覆盖360度方位角。每个加到直方图的样本都由它的梯度量级定权，再被该处关键点尺度1.5倍的σ的高斯圆形窗口定权。

方向直方图的峰值相当于局部梯度的主方向。首先检测直方图中的最高峰值，然后占最高峰80%以上的局部峰值也会在该方向建立一个关键点。因此，对于有多个相似量级的峰值的位置，在同一位置和尺度上会有多个不同向的关键点。只有15%的点会被指定多个方向，但它们对匹配的稳定性意义很大。最后，一个适应于与每个峰值最近的3个直方图值的抛物线值插入峰值位置来达到更高的精度。

图6所示为在不同数量的图像噪声下，位置、尺度和方向赋值的实验的稳定性。如前，图像被随机地旋转和缩放。顶端的线为关键点位置和尺度赋值的稳定性。第二条线为当方向赋值限制在15度以内的匹配稳定性。上面两条线之间的差距可以看出，即使加了10%的像素噪声。方向指定保留了时间95%的准确性(相当于小于3位精度的相机)。正确匹配的方向测量方差大概为2.5度左右，当有10%的噪声时，升为3.9度。图6最下面一条线为一个关键点描述子与一个有40,000个关键点的数据库匹配正确的最终准确率(下文讨论)。如图所示，SIFT特征对大量的像素噪声具有抵抗性，而错误的主要原因在初始位置和尺度的检测。

图6.图中顶行显示的百分率为像素噪声的函数，是可重复检测的关键点的位置和尺度。第二行显示的之后的重复率，同样要求方向一致。最下一行为最后与大型数据库正确匹配的描述子的百分率

6.The Local Image Descriptor

之前的操作已经指定了每个关键点在图像的位置，尺度和方向。这些参数利用一个可复验的局部二维坐标系统，在里面描述局部图像区域，从而为这些参数提供不变式。下一步就是为局部图像区域计算描述子，它highly distinctive，对于其他的变化(如光照或三维视点的改变)尽可能的保持不变性。

一个常用的方法是在合适的尺度下对关键点周围的局部图像亮度进行采样，使用归一化的相关法进行匹配。然而，图像块的简单相关性对变化非常敏感，从而导致样本的误匹配，如仿射变化或三维视点变化或非刚性变形。Edelman等人在1997年提出了一个更好的基于生物视觉的方法，尤其是主视觉皮层中复杂的神经细胞。这些复杂的神经细胞对某个方向和空间频率的梯度变化反应，但梯度在视网膜上的位置却是在一个可以接受的范围内变化而不是精确地固定。Edelman等人假设这些复杂神经细胞的函数使得我们进行匹配和一定视点范围内三维目标的识别。他们使用物体和动物形状的3D计算机模型进行了详细的实验，结果表明，在允许位置移动的情况下，匹配梯度可以在3D旋转下更好地分类。比如说，在使用复杂的细胞模型后，三维目标在20度景深下旋转的识别准确率从35%的梯度相关性升为94%。我们的下面的实践正是受这个思想的启发，但使用的是另一种计算机制来允许位置变化。

图7.要创建一个关键点描述子首先要计算关键点位置附近区域的每个图像样本点的梯度大小和方向，如左图所示。它们由高斯窗口定权，由重叠的圆形表示。然后如右图所示，将这些样本聚集为方向直方图，每4*4个子区域概括为一个。这里的每个箭头的长度均为该区域内这个方向附近梯度模值的总和相对应。图中所示的2*2的描述子箭头就是由8*8的样本集计算出来的，本文所使用的是由16*16的样本集中计算出来的4*4的描述子

6.1 Descriptor Representation

图7表明关键点描述子的计算过程。首先，在关键点周围对图像的梯度量级和方向进行采样，使用关键点的尺度来选择图像高斯模糊的程度。为了达到方向不变性，描述子的坐标和梯度方向都是随关键点方向进行旋转的。为了性能，如第五章中描述的，预先计算出金字塔中所有等级的梯度。在图7的左边，它们在每个样本位置处以小箭头标出。

参数为(等于描述子窗口宽度一半)的高斯权重公式的用来指定每个样本点的权重。如图7左边的圆形窗口所示，权重平滑的减小。高斯窗口的目的是为了避免描述子在窗口位置发生微小变化时发生突变，并且给远离描述子中心的梯度更少的权重，这些梯度对误匹配影响最大。

关键点描述子如图7右侧所示，在4*4的样本区域建立方向直方图使得梯度位置可以发生较大的变化。每个方向直方图有八个方向，每个箭头的长度与该直方图entry的量级有关。一个左边的梯度样本可以上升到四个样本位置，并且仍加入到右边的直方图中，从而实现了允许更大的局部位置变化的目的。

防止所有描述子发生突变造成的边缘影响很重要，突变是因为从一个直方图平滑地改变到另一个直方图或从一个方向转变到另一个方向。因此，用三线性插值来把每个梯度样本的值分配给邻近的直方图bins。即为每个维度的每个bins中的entry都乘以权值1-d，其中d为以直方图bin空间为单位度量的样本到中心bin的值距离。

描述子由一个包含所有方向直方图entries的值的矢量构成的，对应于图7右边图中箭头的长度。图像显示了一个2*2阵列的方向直方图，下面的实验表明每个方框中有八个方向bins的直方图的4*4阵列时结果最优。因此，本文中每个关键点有4*4*8=128个元素特征矢量。

最后，修改特征矢量来减弱光照变化的影响。首先，矢量被归一化为单位长度，对图像对比度的改变就是每个像素值乘以一个常数，这样整个梯度也会乘上同一个常数，这种对比度变化会被矢量归一化抵消掉。图像里的每个像素都加一个常数的亮度变化不会影响到梯度值，因为梯度值是像素值之差。因此，描述子对光照的仿射变化是具有不变性的。然而，由于相机饱和度或光照变化引起的非线性光照变化也可能存在，影响了不同数量不同方向的三维表面。这些影响可能会造成一些梯度的相关量级的巨大变化，但对梯度方向影响很小。因此，我们通过每个单位特征矢量不大于0.2的阈值化来减少大的梯度量级的影响，然后进行重归一化到单位长度。这意味着大梯度量级匹配不再重要，而更加强调方向的分布。值0.2是通过图像对相同的三维目标保留不同光照的实验得到的。

6.2 Descriptor Testing

有两个参数可被用为变化描述子的复杂度：在直方图中的方向数r和nxn方位直方图阵列的宽n。最终描述子矢量的大小为rn2。当描述子的复杂度增加时，在大型数据库中的区分度更好，但它对形状畸变和闭塞也更为敏感。

图8所示的实验结果，其中方向数和描述子大小为变化的。图是用一个视点变换得到的，其中平面相比观察者倾斜了50度，并添加了4%的噪声。这接近了可靠匹配的极限，也是在这种更加困难的情况下，描述子的表现才更为重要。结果为在40000个关键点的数据库在找到正确匹配的最近邻单点的关键点百分数。图中显示所得，单个方向的直方图（n=1）的区分度很差，但增加直至一个4*4阵列的八方向直方图的过程中结果一直在改善。这之后，再增加方向或加大描述子只对匹配造成了影响，使得描述子对畸变更加的敏感。在其他视角角度变化和噪声情况下，结果是相似的。尽管在一些简单的情况下，区分度（从最高级）继续提高直至5*5和更高的描述子大小。但我们在本文中仍使用4*4的8方向描述子，可产生128维的特征矢量。尽管描述子的维数好像很高，但我们发现这在一系列匹配任务中比低维度表现更好，而且匹配的计算成本在使用如下介绍的近似的最近邻方法中也很低。

图8.本图描述的为宽为n*n的关键点描述子以及每个直方图方向数的函数，是关键点与数据库中40,000个关键点正确匹配的百分率

6.3 Sensitivity to Affine Change

描述子对仿射变化的敏感度如图9所示。图中所示为关键点位置和尺度选择、方向分配和与一个与远离观察者的平面中进行深度旋转函数的数据库进行最近邻匹配的可靠性。可以看出，每个计算阶段中，随着仿射畸变的增加，重复率的下降，但在最后，对于一个视点变化50度时，匹配的准确度仍是保持在50%之上。

图9.本图所示为关键点位置、方向和最终与数据库匹配的探测的稳定度，作为仿射变换的一个函数。仿射变换的程度由平面内一组等视点景深旋转来表示

为了实现大视点角情况下可靠的匹配，如第二章所讲，可以使用一种仿射不变的探测器来对图像区域进行选择和重采样。那里提到，由于这些方法都是起源于一个非仿射不变的图像的初始特征位置，所以它们并不具有真正的仿射不变性。在看起来最具有仿射不变性的方法中，Mikolajczyk（2002）对Harris仿射探测器假设并执行了详细的实验。他发现，它的关键点重复率比这里给出的50度的视点角要低，但在角度为70度时，保持在接近40%的重复率上，在极值仿射变换中表现更好。缺点是计算成本高，关键点数量少和在噪声下设定一致仿射变换框架误差对小的仿射变换稳定性差。实际上，三维目标允许的范围是远少于对平面的，所以仿射不变性在匹配视点变化时并不是限制因素。如果要求大范围的仿射不变性，如要求表面为平面，那么一个简单的解决方案就是去采用Pritchard和Heidrich（2003）的方法，生成由训练图像的4仿射变换的版本到60度视点的变化的附加SIFT特征。这使得标准SIFT特征的使用在图像识别处理中没有增加新的运算成本，但在因素为3的特征数据库的大小增加了。

6.4 Matching to Large Databases

一个测量特征鲜明性的重要遗留问题是匹配重复率如何作为一个匹配数据库中的特征数的函数变化。本文中大多数的例子是使用一个32幅图像，40,000个关键点的数据库而生成的。图10所示匹配重复率如何作为一个数据库大小的函数变化的。这幅图像是使用一个更大的有112幅图像的数据库生成的，视点旋转深度为30度，添加了2%的噪声，图像进行了随机地尺度变化和旋转

图10.虚线表明关键点与数据库正确匹配的百分率，为数据库大小的一个函数（使用对数尺度）。实线为关键点分配正确的位置、尺度和方向。图像有随机尺度和旋转变换，30°的仿射变换和2%的图像噪声被预先加入匹配中

虚线表明数据库中以最近邻为正确匹配的图像特征的部分，它作为数据库大小的函数以对数的形式显示出来。最左端的点是与由一张图像中得到的特征进行匹配而最右端的点是从含有112幅图像的数据库的所有特征中选择的匹配。可以看出匹配的可靠性在以干扰项数目为函数时降低了，而所有的显示表明在更大的数据库大小下更多的正确匹配将继续被找到。

实线为关键点在转换图像的正确匹配的位置和方向被识别的百分率，所以只有这些点在数据库中有机会有匹配的描述子。这条线平缓（flat）的原因是测试在整个数据库中运行了每个值，但只改变了数据库中一部分用来干扰的部分。有趣的是，两条线之间的间隔很小，表明匹配失败更多的是因为初始特征定位和方向分配的问题，而不是特征鲜明性的问题，而不是大型数据库大小的问题。

7.Application to Object Recognition

如上所示，本文主要讨论的是鲜明不变性关键点的派生。为了展示它们的应用，我们给出它们在目标遮挡和聚类情况下进行识别的应用。更多关于这些特征的识别应用参见其它文献（Lowe，1999；Se等人，2002）。

目标识别首先要将每个关键点独立的与从训练图像中提取的关键点进行匹配。由于模糊的特征和从背景聚类中得到的特征，很多这些最初的匹配是不正确的。因此，首先识别那些与一个目标或其姿态一致的至少有三个特征的聚类，因为他们比那些独立特征有更高的可能被正确匹配。接下来，通过履行一个与模型合适的精细几何来检查每个聚类，并判断结果，决定采纳还是放弃解译。

7.1 Keypoint Matching

通过在由训练图像得到的关键点数据库中识别最近邻，我们找到了每个关键点的最佳候选匹配。如第六章所述，最近邻定义为每个关键点的不变描述子矢量之间的最短欧氏距离。

然而，图像中的很多特征与训练数据库可能没有任何正确的匹配，因为它们是从背景聚类中提出的或没有在训练图像中被探测到。因此，有一种方法来丢弃与数据库没有很好地匹配的特征很有用。对最近距离特征的全局限值执行的并不尽如人意，因为一些描述子比其他的要鲜明很多。更有效的方法是使用最近距离与次近距离的比值。如果有同一目标的很多训练图像时，我们定义与第一个来自不同目标的次近距离为最近距离，就像使用含有不同目标的已知图像一样。这个方法执行很好，因为正确匹配需要最近邻显著地接近那些最接近的错误匹配来达到可靠性匹配。对于错误的匹配，由于特征空间的高维度，相似距离内会有很多其他的错误匹配。我们可以把次近距离匹配作为对特征空间的这一部分错误匹配密度的一个估计并同时识别特征不明确的特殊实例。

图11.匹配的正确性可由距离比率决定，即用最近邻距离除以次近邻的距离得到。使用一个有40,000个关键点的数据库，实线显示的为正确匹配距离比率的概率密度函数，而点线为错误的概率密度函数

图11表明用这种方法对真实图像数据的测量值。正确和不正确匹配的可能性密度函数以每个关键点最近邻与次近邻之比表示。最近邻为正确匹配的概率密度函数的中心比错误匹配的比率低很多。对于我们的目标识别的执行，我们丢弃那些距离比值大于0.8的匹配，这样可以在仅仅丢弃5%的正确匹配的前提下，减少90%的错误匹配。图像是在一个40,000关键点的数据库中，以随机尺度和方向变化下匹配图像生成的，旋转深度为30度，添加了2%的噪声。

7.2 Efficient Nearest Neighbor Indexing

没有一个现行算法可以在识别高维空间点的准确最近距离时优于穷搜索法（exhaustivesearch）。我们的关键点描述子有128维的特征矢量，而最好的算法，如k-d树（Friedman等人，1977年）也无法在多于10维的空间中提供比穷搜索法更快速的性能。因此，我们用了一种近似的算法，叫做最优盒优先（BBF）算法（Beis和Lowe，1997）。这是在场景中近似的返回具有最高可能性的最近邻。BBF算法使用了一种k-d树算法的改进算法，使得特征空间中的箱是以它们在队列位置中最的近距离的顺序被检索。这种优先顺序最早是由Arya和Mount（1993）实践的，他们在Arya等人（1998）的文献中对其计算性能提供了更进一步的研究。这个搜索顺序要求使用一种基于堆优先的队列来实现搜索顺序的高效决策。在检索了特定量的最近箱之后，中断进一步的搜索可以低计算成本的返回一个近似结果。在我们的实现中，我们在检查了最开始的200个最近邻候选值后，中断了搜索。对于一个有100,000个关键点的数据库，它比准确的最近邻搜索加速了约两个数量级，而正确匹配的结果只损失了不到5%。BBF算法运行如此良好的一个原因是我们只考虑了最近邻比次近邻小于0.8以内的这些匹配（如前面章节中提到的），因此无需考虑那些很多近邻距离非常接近的困难情况。

7.3 Clustering with the Hough Transform

对小而高度遮挡的目标识别实现最大化，我们希望以最少的可能的特征匹配数进行目标识别。我们发现在最少使用3个特征的情况下可靠识别是可能的。一个有着2000个或更多特征的典型图像可能会有很多不同的目标和聚类背景。而第七章中所述的距离比率实验允许我们从聚类背景中丢弃大量的错误匹配，而这并不减少其他有效目标的匹配。通常，我们仍需要从含有99%异常值的匹配中找到那少于1%的正常值识别正确的子集。很多众所周知的稳健地配置（fitting）方法，如RANSAC或最小平方中值，在正常值小于50%时运算结果就会很差。幸运的是，在姿态（pose）空间使用Hough转换（Hough，1962；Ballard，1981；Grimson，1990）的聚类特征可以很好的表现。

霍夫转换通过每个特征与所有目标中特征一致的姿态进行投票通过（votefor）的一致性解译来识别聚类。当发现特征聚类与一个目标投票通过了同一姿态，这种解译正确的可能性比任何单一特征要高很多。我们的每个关键点都有4个参数：二维位置，尺度和方向，而数据库中每个匹配的关键点都有这个关键点与找到的训练图像相关联的记录。因此，我们可以建立一个霍夫变换，由匹配假设输入预计的模型位置，方向和尺度。这个预计有很大的误差界限，因为这四个参数的相似变换只是一个三维目标全六自由度的姿态空间的估计值，并且没有做任何非刚性的变换。因此，我们30度方向的宽箱大小，2因素的尺度以及投影训练图像位置维数（使用预计的尺度）最大值的0.25倍。为了防止边界效应在箱指定中的问题，每个关键点匹配在每个维度中都指定（votefor）了两个最近的箱，这个假设共有16个输入，姿态范围扩宽更多。

在多数霍夫转换的实现中，用多维阵列来表现箱。然而，很多潜在的箱保持为空，由于它们共有的依赖性，很难计算箱值可能的范围（比如说，选择范围上可能的位置离散值的依赖性）。这些问题可通过使用箱值的伪随机散列函数向一维散列表中插入投票（votes），从而可以简单的探测到冲突。

7.4 Solution for Affine Parameters

霍夫转换是用来识别箱中至少有三个实体的所有聚类。每一个这样的聚类都要进入一个用最小二乘法来计算与训练图像向新图像转换有关的最佳的仿射投影参数的几何验证程序。

在正射投影下，仿射变换可以正确求解（accountfor）一个平面的三维旋转，但对于非平面的目标的三维旋转估值就很差了。更普遍的方法是解基础矩阵（Luong和Faugeras，1996；Hartley和Zisserman，2000）。然而，与仿射法只需要3个点匹配相比，一个基础矩阵式要求至少7个，而实际中，为了更好的稳定性，需要更多的匹配。我们希望只用三个特征匹配就完成识别，因此仿射变换就提供了一个很好的起始点，我们可以通过将允许的残差值增大来计算（accountfor）仿射估计中的误差。想象在目标周围放了一个球形，然后将球形旋转30度，球内的任意点不会移动超过球形投影直径的0.25倍。对于本文中的一个典型三维目标的例子，在我们允许残差不大于目标投影维数的最大值的0.25倍时，仿射方法可以很好地解决问题。Brown和Lowe（2002）提出了一种更普遍的方法，初值由相似变换得到，然后计算已经找到足够匹配数的基础矩阵。

我们希望解出变换参数，因此，上式可以被重写为将未知量变为列向量的形式：

这个等式表示的是一个单独的匹配，但可以添加后续匹配的数值，每个匹配都要在第一个和最后一个矩阵中加两行。要解这个式子，至少需要三对匹配。

我们可以把这个线性系统写为：

参数x的最小二乘法可以通过解对应的法方程得到，

它为投影模型的位置到图像位置的距离平方和的最小值。这个最小二乘法可以扩展来解决铰接的灵活的目标的三维姿态和内部参数(Lowe1991)。

通过检查每个图像特征和模型之间的一致度就可以移除异常值。有了更加准确的最小二乘法，我们要求每个匹配要在霍夫转换箱(bin)中的参数的误差一半的范围以内。如果排除异常值后少于三个点，则这次匹配失败。当排除异常值后，要用最小二乘法再次计算留下的点，依次迭代下去。另外，自上而下的进行相位(phase)是为了增加与投影模型位置一致的匹配。可能会在霍夫转换箱时丢失的一些匹配是由于转换的相似性或其它错误。

最后是否接受这个假设取决于之前文章中提到过的精细概率模型(Lowe，2001)。这个方法首先用来在给出模型的投影大小，区域中的特征数和配置(fit)的准确度的情况下，解决模型姿态的错误匹配期望数。贝叶斯分析给出了目标基于实际找到的匹配特征被表现出来的可能性。如果最终正确解译出的可能性大于0.98，我们就接收这个模型。对于投影到图像很小的区域的情况，3个特征就足够进行可靠地识别了。对于纹理较多的大面积目标，错误匹配的期望值较高，可能会需要是个特征匹配这么多。

8. Recognition Examples

图12所示为一个从包含三维目标的聚类遮挡图像中进行目标识别的例子。如左图所示，测试图像为一个玩具火车和青蛙。中图(大小为600*480像素)为含有被遮蔽的测试目标，并有大量聚类背景的图片。因此，即使是人眼也很难立即发现。右图所示为最后正确识别后叠加在一个降对比度版本下的图像。用于识别的关键点显示为小方形，有一条线来指示方向。方形的大小与用于构建描述子的图像区域对应。在每个识别目标的外围有一个外包的平行四边形，它的边界是测试图像在识别过程中在仿射变换下的投影。

图 12. 左图所示为两目标的测试图片。它们可以在大量遮挡的聚类图片中被识别出来，见中图。识别结果见右图。每个识别目标周围都画有一个平行四边形来显示初始测试图像的边界，识别过程中解决了仿射变换问题。小方形为用于进行识别的关键点

另一个潜在的方法应用是位置识别，这样运动的车辆和设备就可以通过识别熟悉的位置来确定位置了。图13给出了这个应用的一个例子，其中训练图像是从场景中很多地方拍摄的。如左上图所示，这些目标看起来都不太显眼，如木墙或是垃圾桶旁的树。而右上方的测试图像(大小为640*315像素)是将初始图像场景旋转30度后的视点拍摄的，但是，训练图像还是很容易的被找到了。

识别的全部过程都被高效完成，所以图12和图13的所有目标在一台2GHz的奔腾4处理器上的识别总用时少于0.3秒。我们在一台笔记本上用一台摄影照相机实施该算法，并在多种环境下广泛的测试了它们。一般来说，有纹理的平面在被旋转50度以内，在提供做够光亮的或不是过度强烈的几乎任何光照条件下，都可以被可靠地识别。对于三维目标，可靠识别的任意向深度旋转范围只有30度，而光照变化的干扰性也更明显。因此，三维目标的识别最好是从多视角的综合特征入手，如局部特征视角聚类法（Lowe，2002）。这些关键点还被用于解决机器人定位和制图的问题，这个在其他文章中有详细的阐述（Se等人，2001）。在这个应用中，一个三目的立体系统被用来决策关键点定位的三维估计决策。关键点只有同时出现在三幅图像中，并有一致的不同性时才被使用，这样可以保证出现较少的异常值。机器人运动时，它通过与现有的三维地图进行特征匹配来确定自己的位置，然后在更新它们的三维位置时，使用卡尔曼滤波来递增地向地图添加特征。这为机器人在一个位置环境中定位提供了一种具有鲁棒性和准确性的解决方案。这项工作还处理了位置识别的问题，这样，机器人可以在一幅大型地图中被转换到可以识别自己的位置的状态（Se等人，2002），相当于目标识别的三维实现。

图13.这个例子表明在复杂场景中的位置识别。用于定位的测试图像为左上方640*315像素的图像，是从右上角图像的不同视角拍摄的。识别区域如下图所示，小的方形为识别的关键点，外围的平行四边形为仿射变换后初始测试图像的边界

9. Conclusions

中所述的 SIFT 关键点基于它的 distinctiveness 很有应用价值，可以使从大型数据库中选出的一个关键点与其他关键点正确匹配。这一 distinctiveness 由汇集图像局部区域内图像梯度的高维矢量来实现。关键点对图像旋转、尺度变换具有不变性并且在大尺度的仿射变形、噪声、光照变化的具有鲁棒性。从典型图像中可以提取大量的关键点，从而使在混杂背景下提取小目标具有更好的鲁棒性。可以从所有的尺度范围提取关键点意味着小的局部特征可以用于匹配高度遮挡的小目标，而大的关键点则在图像噪音和模糊时具有了更好的表现。它们的计算很高效，在标配的 PC 机上，从典型图像中提取出几千个关键点可以实现近乎实时性能。

还提出了一种用关键点进行目标识别的方法。这种方法使用近似的近邻查找，用Hough 变换标识与目标构成一致的类簇，用最小二乘法确定其构成，最后进行核查。其他可能的应用包括三维重建、运动跟踪和分割、机器人定位、全景图像组合、核线校准以及其他需要标识图像间匹配位置的视角匹配。

对于图像特征的不变性和 distinctive 的进一步研究可以由有很多方向。全三维视点和光照变化数据集需要进行系统的测试。所述特征只使用了单色亮度的图像，因此，进一步的 distinctiveness 可以从光照不变的颜色描述子中得出(Funt and Finlayson, 1995; Brown and Lowe, 2002)。同样，局部纹理测量在人类视觉中也具有重要作用，合并在描述子中后，可以比当前这个从单个空间频率进行研究的描述子更具有普遍的形式。局部特征不变量匹配方法一个吸引人的地方在于这里无需挑选一个特征类型，因为最好的结果往往是使用很多不同特征得到的，因此，本方法可以贡献于获得有用的匹配并提高整体的鲁棒性。

另一个未来的研究方向是研究可以识别的目标分类的特征。这对类属目标尤为重要，分类必须包含所有可能的外形，这是一个巨大的范围。 Weber 等人的研究（2000）和 Fergus等人的研究（2003）显示通过学习小型数据集的适合识别目标类属的局部特征，这种方法有实现的可能性。从长远角度来看，特征集应该包含预先指定的和自学习的特征，这些特征将基于对大量目标分来有效的训练数据的数量来使用。

Acknowledgments

我要尤其感谢 Matthew Brown，他对在内容和表述上给了我很多改进的建议，而他本人在特征定位和不变性上的工作也对本方法有贡献。另外，我想谢谢大家宝贵的建议，他们是 Stephen Se， Jim Little， Krystian Mikolajczyk， Cordelia Schmid， Tony Lindeberg 和 Andrew Zisserman。这个研究是由加拿大国家科学工程研究协会(NSERC)、机器人学与智能系统协会(IRIS)和 Excellence 网络中心支持完成的。