搜索
从尺度不变的关键点选择可区分的图像特征1DavidG.Lowe温哥华不列颠哥伦比亚省加拿大英属哥伦比亚大学计算机科学系摘要本文提出了一种从图像中提取有特点的具有不变性的特征的方法，可用于完成不同视角之间目标或场景的可靠匹配。这种特征点对图像的尺度和旋转具有不变性，并且可以看到，可以跨越很大范围的对仿射变换、三维视点的变化、添加的噪音和光照变化等情况下的图像匹配具有鲁棒性。这种特征是非常有代表性的，对于一个单一的特征点来说可以和一个由许多图像组成的大型特征数据库也有很高的概率进行正确匹配。本文还介绍了一个使用该特征来进行目标识别的方法。该方法通过将个别特征与由已知目标特征组成的数据库进行快速最近邻算法的匹配，然后使用Hough变换来识别每一簇（clusters）属于哪一个单一的物体，最后通过最小二乘解执行一致的姿态参数的核查确认。这种识别方法可以在杂乱和遮挡的情况下鲁棒的识别目标同时实现近实时性能。关键词：不变特征，目标识别，尺度不变性，图像匹配1原文出处及作者：DistinctiveImageFeaturesfromScale-InvariantKeypoints,DAVIDG.LOWE1引言图像匹配是计算机视觉领域中很多问题的关键，包括目标和场景识别、多幅影像进行三维构建、立体对应（correspondence）、运动追踪等。本文描述的图像特征很实用，因为它具备很多可以将一个目标或场景的不同影像进行匹配的特性。这些特征对于图像尺度和旋转具有不变性，并在光照变化和三维相机视点变化的情况下具有部分的不变性。它在空间域和频率域都可以很好地定位，减少了遮挡（occlusion）、聚类和噪音的影响。有了有效的算法，海量的特征就可以从典型的图像中提取出来。另外，这些特征是非常鲜明的，使一个单一特征可以无误地与大型数据库中的特征进行匹配，为目标和场景识别提供了基础。通过一个层叠的过滤算法将提取这些特征的代价最小化，这样，最昂贵的运算仅在最初测试通过的部分执行。下面是生成图像特征集计算的一些主要步骤：1）尺度空间极值探测：第一阶段对整个尺度和图像位置进行搜索。通过使用高斯差分函数来有效地识别对于尺度和方向具有不变性的可能的兴趣点。2）关键点定位：在每一个候选位置，一个详细的模型被给定来决定位置和尺度。基于每个关键点的稳定性，最终的关键点被筛选出来。3）定向任务：基于局部图像的梯度方向，给每个关键点指定一个或多个方向。所有随后的操作都在依据每个特征被分配的方向、尺度和位置变化后的图像数据上进行，因此这些变换具有不变性。4）关键点描述子：局部梯度是在每个关键点附近的区域所选尺度上测量得到的。这些可以转化成为一个允许显著的局部形状变化和光照变化的表示法。这种方法被命名为尺度不变的特征转换法（SIFT），因为它可以基于局部特征把图像数据转换到尺度不变的坐标上。该方法的一个重要方面是它生成了大量特征，它们密集的覆盖了整个图像尺度和位置。一幅500*500像素的典型图片可以产生约2000个稳定的特征（这个数字依赖于图像内容和几个参数的选择）。特征的数量对目标识别尤为重要，要具备探测杂乱背景下的小目标的能力，要求每个目标至少有三个特征被正确匹配才是可靠的识别。对于图像匹配和识别，SIFT特征被第一个从一组参考图像中提取并存储在数据库中。一个新的图像通过将这幅新图像中的各个特征与原有数据库进行一一对比并基于欧氏距离找到候选的匹配特征。本文将讨论可以在大型数据库中快速执行的快速近邻算法。关键点描述子是非常鲜明的，可以使单个特征在大型特征数据库中以很大概率进行正确匹配。然而，在杂乱的图像中，很多背景中的特征不能与数据库进行正确匹配，产生了很多错误的配对。通过确定与新图像在目标、目标的位置、尺度和定向一致的关键点的子集，可以将正确的匹配从匹配的全集中过滤出来。多种功能恰好与这些参数一致的可能性比任一个特征匹配错误的可能性要小很多。确定这些一致的聚类，可以通过一个高效的广义Hough变换的散列表快速执行。每个拥有三个及三个以上特征与目标一致的聚类，它们的姿态都要进行下一步更精细的确认。首先，最小二乘估计是用于目标姿态的仿射近似。其他已识别的与此姿态相一致的图像特征以及异常值都忽略不计。最后，通过一个精细的计算可以得出一组可以表明目标存在的详细特征，并给出符合的准确度和可能的错误匹配数。经过所有的这些实验，可以得出这个结论：目标匹配的成功率很高。2.相关研究使用一组局部兴趣点来进行图像匹配的发展可以追溯到1981年Moravec在立体匹配中使用的角探测器。Moravec的探测器在1988年被Harris和Stephens改进，在小的图像变动和近边缘区域具有了更高的重复性。Harris还展示了它在高效运动追踪和由运动恢复进行三维建模中的价值（Harris，1992），Harris的角探测器自此在很多其他的图像匹配工作中被广泛的使用。尽管这个特征探测器被称为角探测器，但它并不是只能选择角，而是可以在一个确定尺度的各个方向上选择所有具有大的梯度的图像位置。该方法的最初应用是立体或短距离运动追踪，而后来被扩展到解决一些更困难的问题。Zhang等人在1995年在每个角的周围使用相关窗口来选择可能的匹配，使得Harris的角进行大幅图像范围的匹配成为可能。计算精确场景中两个视角间的几何约束的基础矩阵，移除异常值，同时移除那些与多数方法不一致的配对。同年（1995），Torr研发了一种类似的方法来进行大间距的运动匹配，使用几何约束来移除图像中移动刚体的异常值。1997年，Schmid和Mohr的开创性工作展示了不变的局部特征匹配可以被扩展到解决一般的图像识别问题，即使用一个特征与大型图像数据库进行匹配。他们还使用Harris角探测器来选择兴趣点，但他们使用的是一个图像局部区域的旋转不变的描述子来代替相关窗口。这是特征可以在两幅图像之间进行任意方向变化时进行匹配。此外，他们还证明多特征匹配可以通过识别一致的匹配特征聚类，在遮挡和混杂的情况下完成一般的识别工作。Harris角探测器对图像尺度的变化非常敏感。因此，对于不同尺度的图像匹配，Harris的角反射器并不能提供很好的基础。本文作者（Lowe）在1999年的早期工作中扩展了这种局部特征方法来实现尺度不变性。这个工作还阐述了一种新的局部描述子，可以降低对局部图像变形的敏感度（如三维视点的变换），同时找到更加鲜明的特征。本文提出了对这一方法更加深入的研发，并分析了这些早期的工作，在稳定性和特征不变性上进行了大量改进。在之前的研究中，关于在尺度变换下表征（representation）的稳定识别占了很大的篇幅。最早在这个领域进行研究的有Crowley和Parker，1984年，他们在尺度空间发现了一种表征可以识别峰和脊，并把它们与树结构联系起来。然后，就可以在任意尺度变换的图像间进行树结构的匹配。在近期基于图像匹配的工作中，Shokoufandeh等人在1999年使用小波系数提出了一种更加鲜明的特征描述子。Lindeberg在1993-1994年对为特征探测识别一个合适并且一致的尺度这一问题进行了深入研究。他称之为尺度选择问题，我们在下面使用了这一结论。最近，有了大量令人印象深刻的将局部特征扩展为全局仿射变换不变量的工作（Baumberg，2000；Tuytelaars和VanGool，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.尺度空间极值的发现引言中已经提到了，我们使用一种高效的先识别候选位置然后进一步确认的层叠过滤方法来探测关键点。关键点探测的第一步是识别同一目标在不同视角下可被重复分配的位置和尺度。使用被称为尺度空间的尺度连续函数，通过搜索所有可能尺度上的稳定特征，可以完成对图像尺度变换具有不变性的位置的探测。（Witkin，1983）。Koenderink和Lindeberg分别在1984年和1994年提出，在一系列合理的假设下，唯一可行的尺度空间核就是高斯函数。因此，一幅图像的尺度空间被函数L(x,y,σ)所定义，它是由尺度可变的高斯函数G(x,y,σ)和输入图像I(x,y)的卷积产生的：),(),,(),,(yxIyxGyxL其中*为x和y之间的卷积运算符。而为了在尺度空间中高效地探测出稳定的关键点位置，我们提出（Lowe，1999）使用difference-of-Gaussianfunction（高斯差分函数）与原图像进行卷积形成的结果，),,(Dyx中的尺度空间的极值的方法。),,(Dyx可以通过由常数乘系数k分离的两个不同的相邻尺度的差值计算得到：),,(),,(),(*)),,(),,((),,(yxLkyxLyxIyxGkyxGyxD（1）有很多选择这个函数的理由。首先，这是一个高效计算的函数，因为平滑图像L需要计算尺度空间特征描述的任何情况，而D只需计算简单的图像减法。另外，Lindeberg于1994年研究表明，高斯差分函数可以提供高斯拉普拉斯的尺度规范化解得近