SIFT算法原文翻译

1、基于尺度空间的不变关键点的不同图像特征大卫罗加拿大范库弗峰大不列颠哥伦比亚大学计算机科学院lowecs.ubc.ca2004年1月5日简要本文旨在阐述一种方法，这种方法可以通过提取不同的不变特征来可靠地匹配不同物体或景象的图像。这些特征对于图像尺度变化和旋转来说是不变的，而且在通过在3D空间大范围的投射、扭曲变化，加噪处理，光照改变，进行的匹配仍表现出健壮性。就算只取其中一个特征也很可能从数幅图像的众多不同特征中找到其正确匹配，由此可见，这些特征具有很强的区分性。本文也阐释了一种利用这些特征点进行物体识别的方法。它是通过对已知物体大量特征中的各个不同特征进行匹配来达成识别的，它利用快速就近运算

2、法则和霍夫变换来辨别单一物体特征群，并最终用最小二乘法来确定一致性参数。这种方法可以很好地识别出混杂和拥塞中的目标，并完成及时处理。于2004年授权国际计算机视觉杂志出版。1 介绍图像匹配是计算机视觉领域中很多问题的基础，包括物体或景象识别，多重图像的3D结构复原，立体空间的一致性查找，还有运动跟踪。本文描述的图像特征，拥有很多适特性，它们可以用于匹配同一物体或景象的图像。这些特性在图像缩放和旋转情况下拥有不变性，在光照变化和3D的拍摄角度变化下拥有部分不变性。它们在时域和频域都拥有良好的适用性，可以有效排除混杂、拥塞、噪声带来的干扰。大量的特征可以利用一些高效的算法从一些典型图像中提取。补充

3、一点，这些特征是具有高度区分性的，就算只取其中一个特征也很可能从数幅图像的众多不同特征中找到其正确匹配，这就为物体或景象的识别创造了条件。最开始先进行一次初始检测，然后只对通过检测的局部进行更精细的检测，这样就可以最大程度地减小运算的花费。下面是生成这些图像特征的主要步骤：1. 尺度空间极值检测：算法的第一步是检测所有的尺度和整幅的图像。通过高斯函数变换来提取出潜在的具有尺度、方向不变性的兴趣点。2. 在每个候选的位置上，通过一个拟合精细的模型来确定位置和尺度。关键点的选择依据于它们的稳定程度。3. 方向的确定：基于图像局部的梯度方向，分配给每个关键点位置一个或多个方向。所有后面的对图像数据的

4、操作都相对于关键点的方向、尺度和位置进行变换，从而提供对于这些变换的不变性。4. 关键点描述：在每个关键点周围的邻域内，在选定的尺度上测量图像局部的梯度。这些梯度被变换成一种描述，这种描述允许比较大的局部形状的变形和光照变化。这种方法被命名为Scale Invariant Feature Transform (SIFT)，它将图像数据变换成一系列对于尺度具有不变性的特征。这种配准方法的一个很重要的地方就是它在整幅图像的各个尺度和方位产生了大量的特征。一个典型的500×500像素的图像将会给出上至大约2000个稳定的特征（尽管这个数字取同时决于图像内容和变量参数选择）。所以对于图像识别

5、，特征点选取得是否合适就尤为重要，为了更加可靠，就要求，要对一个微小物体辨认，至少要有3个特征被正确地匹配。对于图像配准和鉴别，首先从一组图像中提取SIFT特征并以此作为基准。然后把新的图像的每个特征点分别与前面基准图像中所提取的特征点进行比较，比较其特征向量的欧氏距离，从而找到候选匹配特征。本文将讨论面对大量数据，如何利用快速就近运算法则高效地进行这种配准。关键点描述符是具有很强的区分性的，它很有可能仅仅通过单一一个特征就从巨量特征中找到其正确的匹配。然而，在对于两幅不同图的配准，背景中许多特征是没有其正确匹配的，这就必将产生很多错误的匹配混杂于正确匹配中。而我们可以通过鉴别关键点参数，找出

6、那些形状，位置，尺度，方向与新图一致的，把它们提取出来，这些就是正确的匹配了。好几个特征都是偶然的错误匹配的概率是远低于单一一个特征偶然错误匹配的概率的。所以这些完全匹配的匹配簇可以通过执行一个高效的哈希表的整体霍夫变换来迅速确定。每一个的3个或者更多的与实物或其形态一致的特征组成的特征簇将进行下一步更深层次的精细配准。首先，对大致的形态仿射使用最小二乘估计。任何其他的与该形态一致的图像特征将被鉴别，轮廓线被丢弃。最后，进行更精细的算法，计算特定特征的配准概率，给出确切的可能的错误匹配的匹配度和数量。那些通过所有这些检测的匹配将被认为具有较高的可信度。2 相关研究通过用一组兴趣点来进行图像匹配

7、的发展可以追溯到Moravec 1981年用一个边沿探测器在立体匹配方面的研究。这个Moravec 探测器后来被Harris 和Stephens后来在1988年进行了发展，使得它在图像微小变化和区别不大情况下的配准更加有效。1992年，Harris 还展示了它在运动复原中，高效动态捕捉和3D重建方面的价值，从此，Harris 探测器被广泛应用于许多其他的图像配准方面的工作。尽管这些对特征进行探测的探测器被叫做边沿探测器，但它们并不只是寻找图像中的边沿部分，而是探测在各个方向和已定尺度上的所有的拥有较大梯度的部分。刚开始的应用主要是应用于立体合的短程移动捕捉，但是随后该研究扩展到了更复杂的领域。

8、1995年Zhang et al. 证明了即使在更大的图像变化下，也可以通过利用关联窗口选择待配准图中相似部分来对Harris边沿进行匹配。通过求解一个描述两幅刚性变换景象的几何约束的基础矩阵，移除掉与大多数匹配不相一致的错误匹配后，那些离群值就被去除了。其实，在Zhang et al.发表这个证明的同时，1995年Torr也发表了类似的关于大范围波动的运动图像配准的研究学说，在他的学说里，图像中刚性物体的运动被用来建立几何约束以促使去除掉离群值。其实在这方面研究上真正取得突破性进展的是1997年Schmid和 Mohr 所做的工作，他们展示了基于局部不变特征的匹配是可以通过将一个特征点与整幅

9、图像进行比较而拓展到所有的图像识别领域的。他们也引用了Harris边沿来寻找关键点，但与开一个关联窗口进行匹配所不同的是，他们运用了局部图像的圆周不变描述符。更深一步，他们论证了复杂的特征匹配是可以通过鉴别匹配特征不变簇来实现混杂、拥塞图像的一般性匹配的。因为Harris边沿探测器对图像尺度的变化是非常敏感的，所以它是不能用来做不同大小图像的匹配的。本文作者Lowe在1999年的所做的早期工作就是使局部特征点在空间尺度变化下的也具有不变性。这些研究开发了一个新的局部描述符，它就可以提供更多的鲜明特征而却对参照图像类似3D视角的变化并不敏感。本论文对此进行了更加深入的探索和分析，也展示了许多在稳

10、定性和特征不变性方面的改进。先前出现了大量的关于论证尺度变化稳定性的研究。最初是1984年Crowley 和Parker所做的研究，他们陈述了在尺度空间中峰值的标识，然后把它们关联到一个树状结构中去。这个树状结构可以随后用来在任意尺度变化下的图像间做匹配。近期更多的Shokoufandeh，Marsic 和 Dickinson1999所做的基于图标来进行匹配的研究则是提供了更好的利用小波参数的特征描述符。而Lindeberg1993、1994年更加深入地对寻找恰当的、一致的尺度空间进行特征探测问题进行了探索。他把此问题描述为尺度选择，下面我们将要用到他的相关结论。近期出现了大量的关于拓展局部特

11、征对于全仿射变换不变性的研究 （Baumberg，2000；Tuytelaars 和 Van Gool，2000；Mikolajczyk 和 Schmid，2002；Schaffalitzky 和 Zisserman，2002；Brown和 Lowe，2002）。这是考虑到在3D正投影的变化下平滑表面特征不变性的匹配，在大多数情况下是对一个局部仿射标架下的图像进行重复采样。然而，这些研究中没有一个是具有完善的仿射不变性的，他们由于难以承受扫描整个仿射空间的花费，刚开始就只能用一种不具有仿射不变性的方式选择初始的特征尺度和坐标位置。另外，仿射结构比具有尺度不变性的特征对噪声要更加敏感，所以实际上

12、仿射特征的可再现性比尺度不变特征的要小，除非仿射失真有超过平面的40度的倾斜（Mikolajczyk，2002）。广义仿射不变性可能对于许多应用领域并非十分重要，比如为了捕捉3D物体的非平面变化和拥塞影响，某些实验角度最好是每旋转30度一个（意味着辨识能力在最接近的实验角度的15度内）。本文所讲述的方法虽然也并没有完全的仿射不变性，但它已有突破，关联特征点在局部描述符微小变换下相应的会有重大变化。这种方法不仅使得描述符在各种程度的仿射失真下更可靠地匹配，而且使得特征在空间3D视角的变化下的拥有更强的健壮性。除此之外，还有更加有效的特征抽取、更多特征的提取能力等优点不尽详述。另一方面，在大的视角

13、变化下的二维平面匹配的仿射不变性对我们来说是一个很宝贵的资源，参照它来对空间3D视角下不变性进行更深入的研究以提高效率和稳定性不失为一种好的思路。许多其他的已被用于图像识别的特征类型也可以添加到本文所论述的特征向量中用以在不同环境下进行更完善的匹配。一种特征是利用了图像中的轮廓或边缘，以使其不至于被背景中贴近物体边界的凌乱东西所干扰混淆。Matas等人在2002年证实了它们的最高稳定性的极值区域可以很可靠地提供大量的匹配特征。 Mikolajczyk等人在2003年进一步开发出一种新的描述符，它利用了局部边界而忽略了不相关的临近边界，使其具有了即使在窄小区域的边界上叠加有背景中的杂乱物体也能稳

14、定地发现有用特征的能力。Nelson 和Selinger 在1998年利用基于图像轮廓归类的局部特征得到了的良好结果。类似地，Pope和Lowe在2000年利用了基于图像轮廓按等级分类的特征，这对缺乏详尽细节的物体尤其有效。在关于视觉识别的研究历史上，所做的工作都是关于各种各样的可以被用来寻找特征的图像工具。Carneiro和Jepson在2002年描述了基于相位的局部特征来表示相位，而不是局部空间频率的级别，而这有可能提供更好的光照不变性。Schiele和Crowley在2000年提出了表示图像区域内检测分布的多维直方图的使用。这种类型的特征可能对于辨认复杂多变纹路物体尤其有效。Basri和

15、Jacobs在1997年已经证明了提取局部区域边界对于视觉识别的价值。所纳入的其他有用属性还包括颜色，运动，图形背景辨别，区域的形状描述，以及立体纵深表示。局部特征的方法可以很容易吸收新的特征类型，因为额外的功能在它们提供了正确的匹配时，非常有助于提高健壮性，而没有提供这种正确匹配时除计算成本以外也不会有什么其他负作用。因此，未来的系统很可能会结合许多的特征类型。3 尺度空间极值检测正如简介里所介绍的，我们将会用高效的小波滤波法检测关键点来寻求将来会被进一步详细检测的候选域。关键点检测的第一步是寻求可以被用来在同样物体的不同取景角度下重复标识的空间和尺度。探测对图像尺度变换具有不变性的区域可以

16、通过在所有可能尺度寻找稳定特征点来实现，运用一个被称作尺度空间（Witkin，1983）的连续尺度函数。Koenderink（1984）和Lindeberg（1994）证明在一系列合理假定下唯一可能的尺度空间核是高斯卷积核。因此，图像的尺度空间（图像的尺度空间表达指的就是图像在所有尺度下的描述。）被定义成一个函数，L(x; y; )，它是由一个变化尺度的高斯函数G(x; y; )与输入的图像I(x, y)卷积生成的：L(x; y; ) = G(x; y; ) * I(x; y)，这里*代表卷积操作，其中。为了高效地探测到尺度空间中稳定的关键点区域，我们提出了(Lowe, 1999) 利用尺度空

17、间极值通过高斯函数的差分与图像D(x; y; )做卷积，即由两个临近的不同不变常数因子k确定的尺度相减求得：。关于为何要选这个函数有多方面的原因。首先，它是一个计算效率极高的函数，例如对于平滑图像，L，需要在每一次尺度空间特征描述时被计算，而D在计算时仅仅是图像的简单相减。图1：对于尺度空间的每一层，原始图像都被高斯算子重复卷积来计算出如图左所示的尺度空间图像。临近的高斯图像被相减得出高斯图像的差分图像，如图右边所示。在每一层图像被计算得出后，高斯图像则被2倍降采样，而后步骤类似。需要补充说明的是，高斯差分函数是归一化的高斯拉普拉斯函数的近似，是Lindeberg (1994)研究得出的。Li

18、ndeberg验证了因子为的拉普拉斯算子的归一化要求完全的尺度不变性。在更详细的实验比较中， Mikolajczyk (2002)发现通过的最大最小值，相比于很多其它的这类函数，可以得到最稳定的图像特征，比如梯度、Hessian， 以及Harris边沿函数等。D 和 的关系可以从热传导等式推知（参数用代替通常所用的t=）：。从这里我们能够看到可以通过无限差分计算逼近，即利用相邻尺度 k 和 的差分：因此，。这体现了当高斯差分函数的尺度因一个常量变化而不同时，它本身已经满足了尺度不变性的拉普拉斯算子的尺度的归一化的要求。等式中的因子(k-1)是一个在所有尺度都不变的常量，因此不影响极值点的位置。

19、近似误差也会随着k接近于1而趋于0，但是在实践中我们发现这种近似即使在尺度的很大变化下对极值点的探测和分布的稳定性仍然基本没有影响，例如取。图2高斯差分尺度空间极值点图2：高斯差分图像的最大最小值的检测是通过比较该像素点（如图中X）与其当前和临近尺度周围33范围内26个点（用圆圈表示）比较所得。图1展示了一个计算D(x; y; )的高效方法。初始图像递增地卷积于高斯算子得出在尺度空间由k所分离出的图像，如图左列所示。我们选择把每一层尺度空间（例如将翻倍）分成整数阶，s，因此 。我们必须为每一层计算s+3幅图像，这样最终的极值检测就能覆盖到整层图像了。相邻图像尺度相减来得到高斯差分图像，如图右列

20、所示。第一层图像计算完成后，接着对第一层图像中的2倍尺度图像（相当于该层第一幅图像的2倍尺度）以每一行列的2倍像素距离进行降采样。关于采样的精度与先前初始层相比是没有区别的，然而计算量却大大减少了。3.1 局部极值检测为了检测出D(x; y; )的最大最小值，每一个采样点都要分别与其当前层周围8个相邻点，前一尺度、后一尺度的各自的9个点作比较（见图2）。只有与周围相比最大或最小的点才能被选作候选点。由于绝大多数采样点将被开始的几次检测淘汰，所以此次检测的计算量会非常小。一个值得注意的地方是，采样的频率对于图像和尺度区域的极值检测要确实可靠。然而，我们证明得知是不存在这样的能检测出所有极值的最小

21、采样间距的，尽管这些极值可以被无限逼近。我们可以设想一个画着一个白圈的黑板，它将会有唯一的一个尺度空间极大值对于的高斯差分函数圆心区域匹配于这个圆的大小和位置。而对于一个狭窄的椭圆，则将会有两个极大值分布在椭圆的两端。因为极大值的分布是一个关于图像的连续函数，所以对于某些中间拉长的椭圆，最大值就会由一个逐渐转换为两个。转换中最大值点则将各自逼近。图3：第一张图的上面一条线显示了在同一位置和尺度随着每层采样数量的变化，重复检测的关键点的百分比随之的变化走向。下面一条线显示了其描述符正确匹配于基准库的关键点的百分比。第二幅图像展示了在典型图像中所检测到的关键点的总数量对于尺度采样数量的函数。因此，

22、我们必须解决精度换效率的问题。事实上，作为可见预期，再加上我们的实验证实，极值的逼近对于图像的小扰动干扰是相当不稳定的。我们可以通过试验一系列采样频率，利用实验数据确定最佳选择，在仿真匹配模拟中找到最可靠的试验结果。3.2 尺度的采样频率实验测定的最稳定极值采样频率如图3、图4所示。这些数字（还有本文中很多其他的模拟）的得出都基于一个真实的匹配任务，该任务围绕着一个集合了32幅从不同范围，包括外景，人脸，航拍照片，工业图像等真实图像的图像集进行（发现图像类型对结果几乎没有任何影响）。每个图像，都进行了一系列变换，包括旋转，缩放，仿射拉伸，改变亮度对比度，以及添加图像噪声。因为变化是合成的，所以

23、就可以的准确地预测出原始图像中每个特征应该出现在转化后的图像的位置，使得测量每个特征点的正确再现性和定位精度成为可能。图3显示了这些模拟结果，这些结果都曾用来检测每层尺度数目变化的影响，这里图像函数的采样先于极值检测。在这种情况下，每幅图像都是在任意角度、原始图像的0.2到0.9倍之间任意缩放比例中随机抽样的。降采样图像中的关键点是可以匹配到原始图像中去的，所以所有关键点的尺度都将能够出现在匹配图像中。此外，增加了1的图像噪声，这意味着每个像素添加一个取自均匀分布-0.01,0.01中的随机数，而从其中像素值的范围是0,1（相当于提供略少于6bit的图像像素精度）。图4：图中的最上面一条线表示

24、了在转换图像中可以被重复检测的关键点的百分比，作为每层图像的第一幅图像的前一图象平滑性的函数。下面一条线表示了相对于基准库正确匹配的描述符的百分比。图3中的第一幅图的上面一条线表示了在转换图像中匹配的区域和尺度的被检测的关键点的百分比。对于本文所有的例子，我们定义匹配尺度为正确尺度的倍范围内，定义匹配位置为在像素范围内，这里是关键点尺度（定义方程式（1）高斯差分函数的最小高斯核的标准差）。图中的下面一条线展示了第六章中所讲的利用临近匹配法所求得的正确匹配于基准库40000个关键点的关键点数量（这表示了一旦关键点被可重复性定位，它就很有可能会被以后的识别和匹配所用到）。所有的这些都证明了，当每层

25、图像取3个尺度时，就可以获得最高的可重复性，这也是通用于全文的所有实验的尺度采样数。这可能看起来不可思议，可重复性不随着尺度采样数目的增加而继续提高。原因就是它导致了更多的局部极值点被探测，但是这些极值点在总体上会趋于不稳定，因此在转换图像中就更不容易被检测。这点在图3中表现了出来，它展示了在每幅图象中被检测和正确匹配的关键点的平均数目。关键点的数目随着尺度采样的数目增加而增加，总的正确匹配的数目也随之增加。由于物体的识别成功与否一般情况下都更多的取决于正确配准的关键点的数目，而不是正确匹配所占的比例，所以对于很多应用，用更多数量的尺度采样将会达到更好效果。然而，运算的花费也会随着这个数目的增

26、加而增加，所以对于本文提到的各个实验，我们选择了每一层3次的尺度采样数。总之，这些实验展示了尺度空间高斯差分函数会产生大量的极值点，而检测所有的这些点必将开销巨大。所幸的是，我们即使只是对尺度进行粗采样也能探测到最稳定和最有用的关键点子集。3.3 空间区域的采样频率正如我们所确定尺度空间每层的采样频率一样，我们必须确定关于平滑性尺度的图像区域的采样频率。我们已知极值可以被无限逼近，所以同样的，我们还需要做一个采样频率和检出率之间的权衡。图4展示了一个实验结论，初始平滑性值，是适用于建造尺度空间前每层图像中的每阶图像的。需要再次强调的是，上面一条线表示了关键点检测的可重复性，结果证明，这种可重复

27、性会跟着持续增长。然而，就效率而言，用一个较大的会产生很大开销，所以我们选择使用=1.6，它能提供接近于最优的采样率。这个值应用于本文全文，也被作为图3的结论。当然，如果我们在极值检测前对图像进行预平滑化，我们将很可能会错过最高的空间频率。因此，为了更好的利用输入图像，该图可以被拓展产生比原始图像本应产生的更多的采样点。我们在建造金字塔第一级之前利用线性插值方法2倍化输入图像。类似的，利用对原始图像补偿像素点的方法也同样行之有效，图像的倍化将会使匹配效果更好。我们假设原始图像的模糊度至少为=0.5（为了不出现明显的混淆现象的最小值），因此，由于倍化的图像中其新产生的像素间隔，=1.0。这意味着

28、在尺度空间第一层建造之前，需要添加一些平滑性。图像倍化基本上是以因子4的程度增加了稳定关键点的数目，但是在进行更大扩展时却没有发现其有更显著的改善。4关键点的精确定位一旦一个关键候选点通过与邻近像素点比较而被选出，第二步就是进行所在区域、尺度、主曲率的邻近数据的精确配准。这些信息将使拥有较低对比度（因此对噪声是非常敏感的）或者集中分布在边沿附近的点被淘汰。这种方法初步的实施（Lowe，1999）只是对于分布在中央采样点位置和尺度的关键点。然而，最近，Brown已改进了这种方法（Brown和Lowe，2002）使它可以适应于对局部采样点的3D二次函数，从而确定内插值最大分布，他的实验结论展示了这

29、将会给匹配和稳定性带来实质性进展。他的研究利用了尺度空间函数的Taylor展开（展开到二次）， D(x; y; )，变换使得起始点在采样点上：这里D及其派生函数在采样点被计算，是这一点的余项。极值的分布，被这个x的函数的派生函数，设x为0而得到，给出：。图5：此图显示了关键点的选择阶段。 （a）233x189像素的原始图像。（b）最初的由高斯差分函数的最大值和最小值确定的832个关键点的分布。关键点显示为向量，表示的尺度，方向和位置。（c）通过最低对比度阈值，剩余729个关键点。（d）再经过主曲率的阈值淘汰，最后剩下的536关键点。正如布朗说提到的，Hessian和D的派生函数就是近似地在对相

30、邻采样点差分。由此产生的3x3的线性系统可以以最低的成本解决问题。如果偏移在任何尺度上大于0.5，那么就意味着极值是临近于另外一个不同的采样点。在这种情况下，就改变采样点，来代替此点。最终偏移被添加到采样点的位置上，以得到极值点位置的内插值估计。在极值点，函数值D()用于淘汰低对比度的不稳定极值。这可以通过将等式（3）替换为（2）而得到，如下。对于本文中的实验，所有极值点的值小于0.03的都将被舍弃（前面，我们假设图像像素值取值范围为0,1）。图5展示了在一幅自然图片上的关键点选择的效果。为了避免太多的凌乱干扰，我们用了一张233×189的低分辨率图像，关键点以向量形式给出，指示其位

31、置，尺度以及每一个关键点的主方向（方向的确定将会在下面详细给出）。图5（a）展示了原始的图像以作为后面图像的对比参照。图5（b）展示了所有检测到的由高斯差分函数最大最小值所确定的832个关键点，而（c）展示了经过值小于0.03条件淘汰后的剩余的729个关键点。最后（d）部分的工作下面章节将会讲述。4.1消除边缘反应为了稳定，单单只是淘汰掉低对比度的关键点是不够的。高斯差分函数会产生较强的边缘响应，即使边缘确定得很差，所以对于少数量的噪声也是不稳定的。在高斯差分函数的中有一个不好的峰值它在横跨边界时有一个重大的曲率变化，但在顺延边界方向的却只是一个小的曲率。主曲率可以在关键点的位置和尺度上通过一

32、个2x2的海森矩阵计算得出，H：派生函数的估计可以通过相邻采样点的求差得出。H的特征值与D的主曲率是成比例的。借用Harris和Stephens（1988）所使用的方法，我们可以避免完全计算出其特征值，因为我们只关注他们的比率。设是最大特征值，而是最小特征值。然后，我们可以计算出特征值的总和算出H的迹，计算其行列式：，。行列式在某些极少数情况下会出现负值，这时曲率会出现奇异的特点，所以该点将会因为不是一个极值点而被舍弃。设r是最大特征值与最小特征值之比，因此， = r。然后，只取决于两个特征值的比率，而不是它们各自的值。当两个特征值相等时，上式取得最小值；随着r的增加，上式的值也增加。因此，要

33、检查主曲率的比率是否在某一阈值r之下，仅需要检查 。这是非常高效的计算，测试每一个关键点只要求进行少于20个的浮点计算。在本文的实验中，使用的r=10，从而消除了那些主曲率比值大于10的关键点。从图5（c）到（d）的过渡显示了此操作的效果。5统计主方向根据局部图像特性，利用统一标准给每个关键点分配一个与其相适应方向，这些关键点描述符可以与表示出与这个方向的联系，从而对于图像的旋转变化具有了不变性。这种方法与Schmid和Mohr（1997年）的方向不变性描述符形成强烈反差，在他们的方法中，每一个图像属性都是基于旋转不变量度而来的。他们这种方法的缺点是，它限制了可以使用的描述语，并且由于它没有要

34、求所有的测量都满足旋转一致性，从而丢弃了一些图像信息。通过用许多用各种方法标识局部方向的试验，找到下面这种方法能够给出最稳定的结果。关键点的尺度用于选择尺度最接近的高斯平滑的图像L，以便使所有的计算都在尺度不变的方式下进行。而对于每个图像样本L（x，y），在这个尺度上，梯度，m（x，y），和方向，（x，y），则是根据像素差异被预先计算的：然后利用高斯空间中每个特征点一定邻域内采样点的梯度方向创建一个方向直方图。直方图以10度为一个单位将360度分成36个柱。根据每个采样点的梯度值以及一个 等于其本身尺度1.5倍的高斯判定圆形窗将其归入适当的柱。方向直方图中最大峰值作为特征点梯度的主方向。直方图

35、中的最大峰值是要被检测的，然后直方图中量值达到主峰值80%以上的局部峰值方向也创建一个特征点。因此，对于拥有相似显著性的多峰值特征点就会有多个在同一位置统一尺度而方向却不同的特征点。虽然仅有15%的位置会产生这种情况，但这种多方向特征点的方法对匹配的稳定性贡献很大。最终，依据近似代表每个峰值的3个柱状图值拟合一条图线来修正峰值位置以达到更好的精确性。图6显示了在不同数额的图像噪声下的位置，尺度，定向分配的实验稳定性。如同之前的图像以随机的数值进行旋转和尺度变换。顶曲线显示了关键点的位置和尺度分配的稳定性。第二曲线则显示了当要求方向分配在每15度算一分度时的配准稳定性。正如前两行之间的差距所展现

36、的，即使在增加±10像素噪声（相当于一个提供小于3位精度的摄像头），方向分配仍然保持着95的准确性。测量的方向正确匹配的方差是2.5度左右，增加10的噪音后上升到3.9度。图6中的最底下的图线显示了对于一个40000关键点库的关键点描述符正确匹配的最终精度（下面即将讨论）。由图可知，SIFT特征是可以忍受大量像素噪音的，而所出现的匹配错误则主要是由于初始位置和尺度的检测。图6：图中的顶线显示了一个关于像素噪声的函数，它表示了可重复探测关键点的位置与尺度的百分比。次线显示了对方向一致性也有要求的可重复性。而底线则显示了对于大型库最终所能正确匹配的描述符的百分比。6局部图像描述符先前的操

37、作为每个关键点指定了图像的位置、尺度和方向。这些参数利用一个可重复的局部二维坐标系统来描述局部图像区域，因此这些区域对这些参数具有不变性。下一步是计算得出局部图像区域的具有强区分性的描述符，使其尽可能地对于光照和3D视角的改变保持不变性。一个显而易见的方法是在适当尺度的关键点周围对局部图像强度进行采样，利用一个相关性归一化方法去匹配它们。然而，简单的图像碎片的相关关系对于仿射或3D的视角变化或者非刚性变形是非常敏感的，这就导致了图像配准的失败。而一个更好的方法被Edelman、Intrator 和Poggio（1997）论证。他们提出图像是基于生物视觉模型的，特别是初级视觉皮层的复杂的神经元。

38、这些复杂的神经元会对特定的方向和空间频率的梯度产生响应，但此梯度的位置在视网膜上是允许小范围波动的，而并非精确定位。Edelman等人推测，这些复杂的神经元的功能就是使3D物体在一系列的视角上都能被匹配和识别。他们已经利用各种物体和动物形状的3D计算机模型进行了详细的实验，证明了在允许位置的小范围波动情况下的梯度配准对3D变换会产生良好的辨认效果。例如，通过使用复杂的细胞模型，在以20度为旋转深度的三维物体的识别精度，其梯度相关性从35增加至94。我们下面所描述的实施方法就是受这种思想的启发，但允许使用不同的运算机制进行位置转变。图7：创建一个关键点描述符，首先要对关键点周围的每一个采样点进行

39、梯度幅值和方向的计算，如左图所示。它们通过高斯窗口进行加权，覆盖一个圆圈来表示。然后将这些采样点累加到方向直方图中来描述这个4×4区域的内容，如右图所示，每个箭头的长度与相应方向的附近区域内的梯度幅度的总和相一致。此图显示了从8×8的采样点组计算成2×2的描述符阵列，而在本文的实验中使用的是从一个16×16的采样点组阵列计算成4×4的描述符阵列。6.1广义的代表性图7说明了关键点描述符的计算过程。首先从关键点的位置周围对图像梯度的大小和方向进行采样，用关键点的尺度为图像选择高斯模糊水平。为了实现方向不变性，描述符的坐标和梯度的方向与关键点的方向

40、是旋转相关的。为了提高效率，如第5章所述，金字塔各级的梯度将被预先计算。而后，如图7所示，在每个采样位置用小的箭头来代表它们。高斯加权函数的参数等于描述符窗口宽度的一半，用于给每个采样点的幅度分配权重。这点用图7左边的圆形窗口中进行了说明，当然，权重是连续递减的。此高斯窗口的目的是为了避免在窗口区域小的变动会引起描述的突然变化，同时也使远离描述符中心的梯度能够不被过分强调，因为就是这些在很大程度上导致了匹配的错误。图7右侧展示了关键点描述符。通过在一个4×4区域创建方向直方图，关键点描述符便能够容忍梯度位置上的显著变化。该图为每个直方图显示了8个方向，而直方图的显著程度用分别每个小箭

41、头的长度表示。左侧的梯度采样可以用于4个样品位置，同时作用于如右图所示的4个柱状图，从而实现容忍更大局部位置变动的目标。非常重要的一点是要避免所有边界描述符突然变动的影响，因为采样从一个柱状图到另一个柱状图，从一个方向到另一个方向的变化是连续的。因此，使用了三线性插值来把每个梯度采样值分配到各个相互临近的柱状图格子中。换句话说，每个格子中的项都乘了对应各自程度的1-d的权重，其中d是在每个柱状图格子单元中采样点到格子中心的距离。该描述符是由一个向量形成的，该向量包含了所有的方位直方图项值，对应于图7右侧的箭头的长度。这个图像展示了一个2×2阵列的方位直方图，而下面的实验表明最好的结果

42、，是在每个4×4的8方向直方图列阵上达到的。因此，本文中的实验采用了一个4×4×8=128维的特征向量来表示每个关键点。最后，我们来改进特征向量以减少光照变化的影响。首先，向量被归一化。图像对比度中每个像素值都乘了一个常量，因此，图像对比度的变化也会给梯度乘上一个相同的常量，所以这种对比度的变化将会被向量的归一化所取消。如果一个图像的每个像素都添加了一个常量，那么它的亮度变化不会导致梯度值的变化，因为它们计算的是像素间的差异。因此，在光照仿射变化中的描述符是不变的。然而，非线性光照变化也会由于相机饱和度或者光照变化在不同方向不同程度对3D表面施以影响而引起。这些影

43、响可能会导致某些梯度值的大的变化，但很少会影响梯度的方向。因此，我们可以设定一个阈值，让单位特征向量的幅度不大于0.2，然后再把它归一化，以此来降低对梯度值的大的影响，这意味着为大梯度值的匹配已不再是那么重要，转而去重视其方向的分布。0.2的值是我们通过利用同一物体不同光照强度的图像进行实验而确定的。6.2描述测试我们可以利用两个参数来表示这个描述符的各种复杂情况：直方图中的取向数量，r，n×n方向直方图中的宽度，n。描述矢量的最终大小是r×n×n。随着描述符复杂程度的增长，在大型的数据库中它们将会被更好地区分，但这也会导致其在形状扭曲和闭塞上更加敏感。图8给出了

44、方向数量和描述符大小变化下的实验结果。图像生成于视角的转换，平面相对于离观察者倾斜出50度角，并添加4的图像噪声。这已接近了可靠匹配的极限，因为只有在这些更为困难的情况下，才更能显示出描述符是最重要的。结果显示了在40000关键点的库中，找到正确的匹配的单一最接近的关键点的百分比。图表显示一个单一方向的直方图（n= 1）在分辨力方面做的很差，但紧接着，我们又对8方向的4×4阵列直方图进行试验，结果改善了很多。此后，再加入更多的方向或更大的描述符则实际上会损害匹配，因为它会使得描述符更对失真更加敏感。对于其他的视角改变程度和噪声程度来说，结果是相似的，尽管在一些简单的情况下，如果我们用

45、5×5阵列直方图和更高的描述符的大小，区分性会继续改善（已有很高的水平）。我们在本文通篇使用一个8方向4×4阵列直方图来描述符，生成128维的特征向量。虽然描述符的维数似乎看起来很高，但我们发现在一系列的匹配任务上，它总是能够比低维的描述符表现得更好，并且当我们利用了下文将要讲的大致最近匹配方法后，计算量仍能维持在较低的水平。 图8：该图表示的函数是以n×n描述符的阵列宽度和以每个柱状图的方向数作为自变量的能够在具有40000关键点库的图像中正确匹配的关键点百分比的函数。该图所计算的图像是具有50度仿射视角变化和添加4噪音后的图像。6.3仿射变化的敏感性 图9测试

46、了描述符对仿射变化的敏感性。图表显示了随着观察者观察角度的变化，关键点位置和尺度选择，以及方向分配，还有最接近描述符与图像的配准可靠性的变化。可以看出，每次计算的所得的可重复性随着仿射失真的增加而降低，但在变化角度超过五十50度时，最终匹配精度仍保持在50以上。为了在更高程度的角度变化下实现可靠的匹配， 一种仿射不变的探测器应该可用于在图像区域进行选择和重复取样，正如在第2章讨论的那样。如前所述，这些方法都不是真正的仿射不变，因为它们一开始都是通过非仿射不变的方式确定的初始特征的位置。最接近于仿射不变的方法，是Mikolajczyk（2002年）提出和详细实验的Harris仿射探测器。他发现，

47、在超出大约50度的角度变化下该探测器的关键点可重复性是低于这里所给的方法的，但是在超出70度角时，它仍保留了接近40的可重复性，即在极端的仿射变化下会有更好的表现。而其缺点是计算成本更高、关键点数量的很少，由于噪声干扰下不变仿射标架的错误分配，在小的仿射变化下的稳定性较差。在实践中，三维物体的旋转允许的范围是绝不只是平面的，所以仿射不变性通常不是视角变化下配准的限制因素。如果需要广泛的仿射不变性，如已知一个表面是平面的，那么一个简单的解决办法就是采用Pritchard 和 Heidrich (2003年)的方法，额外的SIFT特征从配准图像的4次仿射转换描述中产生，相当于60度的视角变化。这使

48、得图像识别能够运用标准的SIFT特征而不需要额外开销，但结果是特征库的大小将会增加3倍。 图9：该图表示仿射变化下，检测关键点位置方向并最终匹配数据库的稳定性的变化关系。仿射失真度是用平面的角度旋转来实现的。6.4匹配大型库 剩下的一个探测显著特征的重要问题就是匹配质量的可靠性作为库中已匹配特征数量的函数是如何变化的。本文中的例子大部分都是使用大约40,000个关键点的32幅的图像库生成的。图10展示的就是匹配的可靠性是如何因特征库的大小而变化的。而此图是使用的是更大的112幅的图像库生成的，除了一般的随机图像旋转和尺寸变化外还添加了30度的视角旋转和2%的图像噪声。虚线表示在数据库中达到正确

49、匹配的部分图像特征，作为数据库大小的函数用对数刻度表示。最左边的点匹配的只是单一图像中的特征，而最右边的点是从112幅图所有特征的库中选择合适的匹配。它可以看出，匹配的可靠性会随着错误匹配数量的增加而降低，但所有迹象都表明，巨大的库下将会继续发现更多正确的匹配。实线是在转换图像中位置和方向上都正确配准的被识别的关键点的百分比，所以只有这些点才可能在库中有其匹配的描述符。这条线之所以是平的原因是这项测试覆盖了整个数据库的每一个值，而仅有的不同的部分是错误的匹配。有趣的是两条线之间的差距很小，表明匹配失败是更多的由于初始特征位置和方向分配的问题而不是特征的独特性，甚至对于大容量库也是这样。 数据库

50、中的一些关键点点（对数标度）图10:虚线表示的是正确匹配于库的关键点的百分比的关于库容量的函数(使用一个对数标度)。实线表示的是被分配到正确的位置、尺度、和方向的关键点的百分比。该图像拥有随机尺度和角度的变化，一个30度的仿射变化，还有匹配前予其添加的2%的图像噪声。7目标识别的应用本论文的主要目的是具有独特性的不变关键点，如上文所描述的。要阐述其应用价值，我们现在将会做一个简短的描述，描述其用于混杂和拥塞环境中的图像识别。更多关于应用这些特征进行识别的详细描述可在其他文件中找到（Lowe，1999；Lowe，2001；Se，Lowe and Little，2002）。执行目标识别，第一步要把

51、各关键点独立地与配准图像所提取的关键点的库进行匹配。最初这些匹配，可能因模棱两可的特征或背景杂波产生的特征，而使得其中许多匹配是不正确的。因此，至少3个特点的特征簇能够一致地匹配于一个物体或形态则是第一个需要被鉴定的，因为这样的集群的正确匹配概率比单个的高得多。然后，每个群集通过一个具体的几何变化模型进行检测，决定是接受还是拒绝这个匹配。7.1 关键点匹配为了给每个关键点寻找其最好的候选点，我们需要在配准图像关键点库中鉴别出它的最接近项。关于最接近项我们可以这样来解释，即对于第6章讲到的不变描述符向量，欧氏距离最小的关键点。距离的比率（最近/次最近）图11：一个点的匹配是正确的可能性可以通过计

52、算其与最近项距离和与次近项距离的比值来确定。对于一个40000关键点的库，实现表示的是正确匹配比率的概率分布函数，而虚线表示的是错误匹配比率的概率分布函数。然而，图像中的许多特征在配准库中是没有任何的正确的匹配，因为它们或来自背景杂波或在配准图像中未被检测到。因此，找一种方法来丢弃掉在库中没有的任何好的匹配的特征是有用的。在与最接近的特征的欧氏距离上整体设置阈值并不十分有效，因为一些描述符的区分性比其他的要高得多。一个更有效的措施是比较最近项的距离与第二近项的距离。如果同一个的对象有多幅配准图像，已知最接近项是来自不同的对象，那么我们定义第二接近项作为最接近项，例如只使用已知的图像来抑制不同的

53、对象。这个措施很有效，因为正确的匹配需要的最接近项要比错误匹配的最接近项更加接近以实现可靠的匹配。对于错误的匹配，由于特征维数较高，很有可能还能找到一些其他有类似的欧氏距离的错误匹配。我们可以认为第二接近的匹配提供了一个在此特征空间区域错误匹配密度的估计，同时也证实了特征模糊性的具体实例。图11展示了把真实图像数据代入此法的所得值。正确或者不正确匹配的可能性密度函数通过每一个关键点最近与次接近比值的形式表现出来。最接近项匹配正确的匹配比上错误匹配，概率分布函数中间的比率更低。在我们的目标识别中，我们拒绝了所有大于0.8的距离比率，这样最终丢弃了大约90%的错误匹配和少于5%的正确匹配。这一图表

54、是通过匹配拥有随机尺度方向变化，30度深度旋转，再加2%的画面噪音，拥有40000个关键点的图像生成的。7.2 高效的临近点标定现在已知的没有哪个算法能比穷举搜索更有效地在大尺寸的空间中精确探测到最接近特征点。我们关键点描述符有一个128特征向量，最好的算法，例如k-d树（Friedman 等，1977年）对于超过10维空间的穷举搜索也不能提供加速。因此，我们采取了一个近似算法，叫做Best-Bin-First（BBF）算法（Beis和Lowe，1997年）。这是一种近似，意味着他返还的最接近项是具有很高可能性的。BBF算法用了一个改良k-d树排序方式的搜索算法以使得在特征空间内的块是以与目标

55、位置距离最近的顺序而被搜索。这个优先寻找排序是Arya和Mount1993年首次试验的，并且他们对它的计算方法进行了进一步的研究（Arya 等，1998）。为了快速决定搜索顺序，这种排序方法用了一个堆的优先排队法。当搜索到的最接近块达到一定数量后，我们就放弃更进一步的搜索，这样，我们就可以以低成本寻找到近似的答案。我们在实际计算时，在找到200个最近项后就停止搜索了。在一个100000关键点的库中，这样的方法在最近项的搜索中提供了两个数量级的加速，而同时丢失了少于5%的正确匹配。BBF算法的有效性原因之一是我们只考虑最接近点与第二接近点距离比率小于0.8匹配（如前一章所讲的那样），而且因此没有

56、必要精确处理那些相邻点距离十分接近的最困难情况。7.3 霍夫变换集簇为了最大限度地对小的和高阻塞的对象进行识别，我们希望能通过尽可能少的特征匹配来辨别目标。我们发现最少可以通过3个特征就可能进行可靠地识别。一个典型的图像会包括2000或者更多的特征，这些特征可能来自于许多不同的目标或者背景杂波。在7.1章节中所描述的距离比率测试可以让我们摒弃掉背景杂波中产生的许多错误的匹配，但却不能移除来自其他正常物体的匹配，所以我们通常仍需要去判别在99%的外来特征中少于1%的内部特征的正确匹配子集。许多著名的拥有良好健壮性的方法，比如RANSAC或者平方最小中位数，在内部特征比例下降到明显低于50%时候，就表现得非常糟糕了。幸运的是，在空间形态上通过利用霍夫变换将特征集簇可以取得好得多的效果（Hough，1962；Ballard，1981；Grimson，1990）。霍夫变换通过一致性描述来鉴别特征簇，它让每个特征对所有的物体形态进行选择，选出与该特征一致的物体。当发现特征的集