Distinctive-Image-Features-from-Scale-Invariant-Ke

DistinctiveImageFeaturesfromScale-InvariantKeypointsDavidG.LoweComputerScienceDepartment,UniversityofBritishColumbia,Vancouver,B.C.,Canada摘要：本文提出了一种从图像中提取独特不变特征的方法，可用于不同视角之间目标或场景的可靠匹配的方法。这种特点对图像的尺度和旋转具有不变性。并在大范围的仿射变换，三维视点的改变，噪音和光照变化的图像匹配具有鲁棒性。特征是highlydistinctive的，使场景图像中的单一特征和许多图像中提取的大型特征数据库一样，有很高的正确匹配率。本文还介绍了一个使用该特征来识别目标的方法。通过将个别特征与由已知目标特征组成的数据库进行快速最近邻算法的匹配，然后使用Hough变换来识别属于单一目标的类簇(clusters)，最后通过执行一致的构成参数的最小二乘解来验证。这种识别方法可以在杂乱和遮挡的对象间鲁棒的识别目标并且具有接近线性的时间复杂度。关键词：不变特征，目标识别，尺度不变性，图像匹配1.Introduction图像匹配是计算机视觉领域中很多问题的关键，包括目标和场景识别、多幅影像的3Dstructure、stereocorrespondence、motiontracking等。本文描述的图像特征有很多特性使得它适合将一个目标或场景的不同影像进行匹配。这些特征对于图像尺度和旋转具有不变性，并在光照变化和三维相机视点变化的情况下具有部分的不变性。它在空间域和频率域具有很好的局部性，减少了遮挡（occlusion）、杂乱和噪音的影响。通过有效的算法，可以从典型的图像中提取海量的特征。另外，这些特征是highlydistinctive的，使场景图像中的单一特征和大型特征数据库一样，有很高的正确匹配率，为目标和场景识别提供了基础。通过一个级联滤波算法将minimized提取这些特征的cost，这样，昂贵的运算仅在通过初步测试的locations。下面是生成图像特征集的主要步骤：1.Scale-spaceextremadetection：第一阶段对所有尺度和图像locations进行搜索。通过使用difference-of-Gaussianfunction高斯差分函数来识别对于尺度和方向具有不变性的潜在兴趣点。2.Keypointlocalization：在每一个候选location，一个detailedmodel适合于确定位置和尺度。基于关键点的稳定性来选择关键点。3.Orientationassignment：基于局部图像的梯度方向，给每个keypointlocation指定一个或多个方向。后面所有操作的图像数据都是将每个特征的方向、尺度和位置进行相关变换得到的，因此特征对这些变换具有不变性。4.Keypointdescriptor：局部梯度是在所选尺度上每个关键点附近的区域测量得到的。这些局部梯度可以转化为允许强烈的局部形状扭曲和光照变化的图像表示法。这种方法被命名为ScaleInvariantFeatureTransform(SIFT)，把图像数据转换到对于局部特征尺度不变的坐标上。该方法的一个重要方面是它生成了大量特征，它们密集的覆盖了图像所有的尺度和locations。一幅500*500像素的典型图片可以产生约2000个稳定的特征（这个数字依赖于图像内容和几个参数的选择）。特征的数量对目标识别尤为重要，要检测杂乱背景下的小目标，至少要求每个目标有三个特征被正确匹配才是可靠的识别。对于图像匹配和识别，从一组参考图像中提取SIFTfeatures并存储在数据库中，通过将新图像中的各个特征与原有数据库进行对比并基于特征向量的欧氏距离找到候选匹配特征。本文将讨论可以在大型数据库中进行快速计算的fastnearest-neighboralgorithms。关键点描述子是highlydistinctive的，可以使单个特征在大型特征数据库中以很大概率进行正确匹配。然而，在杂乱的图像中，很多背景中的特征在数据库中不存在正确匹配，产生了很多错误的配对。通过标识与新图像在theobjectanditslocation、尺度和方向一致的关键点的子集，将正确的匹配从匹配的全集中过滤出来。几个特征的这些参数恰好一致的概率比任一个特征匹配错误的概率要小很多。可以通过一个高效的广义Houghtransform的散列表快速确定这些一致的类簇。每个拥有三个及三个以上与目标一致的特征的类簇的构成需进一步的更详细的验证。首先，最小二乘估计是theobjectpose(对象构成)的仿射近似。其他与此构成一致的图像特征被标识出来，而离群点被丢弃。最后，详细的计算可以认为是一个特定的特征集合表明目标存在的概率，给出匹配的准确率和可能的错误匹配数。通过这些测试的Objectmatches可以认为就是正确的匹配。2.RelatedResearch使用一组局部兴趣点来进行图像匹配的发展可以追溯到1981年Moravec在立体匹配中使用的cornerdetector(角点检测)。Moravec的detector在1988年被Harris和Stephens改进，在小的图像变动和近边缘区域具有了更高的可重复性。Harris还展示了它在高效运动追踪和从motionrecovery中进行3Dstructure的价值(Harris，1992)。此后，Harris角点检测被广泛运用于图像匹配工作中。尽管这些特征检测器被称为cornerdetectors，但它并不是只能选择角，还可以选择在一个尺度的各个方向上具有大的梯度的图像location。该方法的最初应用是立体和短距离运动追踪，而后来被扩展到解决一些更困难的问题。Zhang等人在1995年在每个角点周围的相关窗口来选择可能的匹配，使得大幅图像范围的Harris角点匹配成为可能。通过求解严格场景的两个视角间的几何约束的基础矩阵和移除与多数解不一致的配对来移除异常值。同年（1995），Torr提出了一种类似的方法来进行远程的运动匹配，使用几何约束来移除图像中rigidobjects的移动的离群点。1997年，Schmid和Mohr的开创性工作展示了不变的局部特征匹配可以被扩展到解决一般的图像识别问题，即使用一个特征与大型图像数据库进行匹配。他们还使用Harris角点检测来选择兴趣点，但他们使用一个图像局部区域旋转不变的描述子来代替相关窗口进行匹配。这些特征可以在两幅图像之间进行任意方向变化时进行匹配。此外，他们还证明多特征匹配可以通过标识一致的匹配的特征的类簇，在遮挡和混杂的情况下实现一般的识别。Harris角点检测对图像尺度的变化非常敏感。因此，对于不同尺度的图像匹配，Harris角点检测并不能提供很好的基础。本文作者（Lowe）在1999年的早期工作中扩展了这种局部特征方法来实现尺度不变性。该工作还阐述了一种新的局部描述子，给出一个moreDistinctive的特征，可以降低对局部图像变形的敏感度（如三维视点的变换）。本文提出了对这一方法更加深入的研究，并分析了这些早期的工作，在稳定性和特征不变性上进行了大量改进。在之前的研究中，关于在尺度变换下表征（representation）的稳定识别占了很大的篇幅。最早在这个领域进行研究的有Crowley和Parker，1984年，他们研究出一种表征法，标识峰和脊并把它们放入一个树结构中。树结构的匹配可以在任意尺度变换的图像间进行。在近期基于图的匹配工作中，Shokoufandeh等人在1999年使用小波系数提出了一种moredistinctive的特征描述子。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.DetectionofScale-SpaceExtrema引言中已经提到，我们使用高效的方法来标识候选位置然后再进一步详细检查的级联滤波方法来探测关键点。关键点检测的第一阶段是标识同一目标在不同视角下可被重复分配的位置和尺度。使用尺度连续函数(尺度空间Witkin，1983)，在所有可能的尺度中搜索稳定特征，检测图像中具有尺度变换不变性的locations。Koenderink和Lindeberg分别在1984年和1994年提出，在一系列合理的假设下，唯一的尺度空间核是高斯函数。因此，图像的尺度空间被定义为函数L(x,y,σ)，是由尺度可变的高斯函数G(x,y,σ)和输入图像I(x,y)的卷积生成的：()()()其中*为x和y之间的卷积运算，()()。为了高效地在检测尺度空间中稳定的关键点locations，我们(Lowe，1999)使用difference-of-Gaussian(高斯