基于尺度空间的不变关键点的不同图像特征大卫•罗加拿大范库弗峰大不列颠哥伦比亚大学计算机科学院lowe@cs.ubc.ca2004年1月5日简要本文旨在阐述一种方法,这种方法可以通过提取不同的不变特征来可靠地匹配不同物体或景象的图像。这些特征对于图像尺度变化和旋转来说是不变的,而且在通过在3D空间大范围的投射、扭曲变化,加噪处理,光照改变,进行的匹配仍表现出健壮性。就算只取其中一个特征也很可能从数幅图像的众多不同特征中找到其正确匹配,由此可见,这些特征具有很强的区分性。本文也阐释了一种利用这些特征点进行物体识别的方法。它是通过对已知物体大量特征中的各个不同特征进行匹配来达成识别的,它利用快速就近运算法则和霍夫变换来辨别单一物体特征群,并最终用最小二乘法来确定一致性参数。这种方法可以很好地识别出混杂和拥塞中的目标,并完成及时处理。于2004年授权国际计算机视觉杂志出版。1介绍图像匹配是计算机视觉领域中很多问题的基础,包括物体或景象识别,多重图像的3D结构复原,立体空间的一致性查找,还有运动跟踪。本文描述的图像特征,拥有很多适特性,它们可以用于匹配同一物体或景象的图像。这些特性在图像缩放和旋转情况下拥有不变性,在光照变化和3D的拍摄角度变化下拥有部分不变性。它们在时域和频域都拥有良好的适用性,可以有效排除混杂、拥塞、噪声带来的干扰。大量的特征可以利用一些高效的算法从一些典型图像中提取。补充一点,这些特征是具有高度区分性的,就算只取其中一个特征也很可能从数幅图像的众多不同特征中找到其正确匹配,这就为物体或景象的识别创造了条件。最开始先进行一次初始检测,然后只对通过检测的局部进行更精细的检测,这样就可以最大程度地减小运算的花费。下面是生成这些图像特征的主要步骤:1.尺度空间极值检测:算法的第一步是检测所有的尺度和整幅的图像。通过高斯函数变换来提取出潜在的具有尺度、方向不变性的兴趣点。2.在每个候选的位置上,通过一个拟合精细的模型来确定位置和尺度。关键点的选择依据于它们的稳定程度。3.方向的确定:基于图像局部的梯度方向,分配给每个关键点位置一个或多个方向。所有后面的对图像数据的操作都相对于关键点的方向、尺度和位置进行变换,从而提供对于这些变换的不变性。4.关键点描述:在每个关键点周围的邻域内,在选定的尺度上测量图像局部的梯度。这些梯度被变换成一种描述,这种描述允许比较大的局部形状的变形和光照变化。这种方法被命名为ScaleInvariantFeatureTransform(SIFT),它将图像数据变换成一系列对于尺度具有不变性的特征。这种配准方法的一个很重要的地方就是它在整幅图像的各个尺度和方位产生了大量的特征。一个典型的500×500像素的图像将会给出上至大约2000个稳定的特征(尽管这个数字取同时决于图像内容和变量参数选择)。所以对于图像识别,特征点选取得是否合适就尤为重要,为了更加可靠,就要求,要对一个微小物体辨认,至少要有3个特征被正确地匹配。对于图像配准和鉴别,首先从一组图像中提取SIFT特征并以此作为基准。然后把新的图像的每个特征点分别与前面基准图像中所提取的特征点进行比较,比较其特征向量的欧氏距离,从而找到候选匹配特征。本文将讨论面对大量数据,如何利用快速就近运算法则高效地进行这种配准。关键点描述符是具有很强的区分性的,它很有可能仅仅通过单一一个特征就从巨量特征中找到其正确的匹配。然而,在对于两幅不同图的配准,背景中许多特征是没有其正确匹配的,这就必将产生很多错误的匹配混杂于正确匹配中。而我们可以通过鉴别关键点参数,找出那些形状,位置,尺度,方向与新图一致的,把它们提取出来,这些就是正确的匹配了。好几个特征都是偶然的错误匹配的概率是远低于单一一个特征偶然错误匹配的概率的。所以这些完全匹配的匹配簇可以通过执行一个高效的哈希表的整体霍夫变换来迅速确定。每一个的3个或者更多的与实物或其形态一致的特征组成的特征簇将进行下一步更深层次的精细配准。首先,对大致的形态仿射使用最小二乘估计。任何其他的与该形态一致的图像特征将被鉴别,轮廓线被丢弃。最后,进行更精细的算法,计算特定特征的配准概率,给出确切的可能的错误匹配的匹配度和数量。那些通过所有这些检测的匹配将被认为具有较高的可信度。2相关研究通过用一组兴趣点来进行图像匹配的发展可以追溯到Moravec1981年用一个边沿探测器在立体匹配方面的研究。这个Moravec探测器后来被Harris和Stephens后来在1988年进行了发展,使得它在图像微小变化和区别不大情况下的配准更加有效。1992年,Harris还展示了它在运动复原中,高效动态捕捉和3D重建方面的价值,从此,Harris探测器被广泛应用于许多其他的图像配准方面的工作。尽管这些对特征进行探测的探测器被叫做边沿探测器,但它们并不只是寻找图像中的边沿部分,而是探测在各个方向和已定尺度上的所有的拥有较大梯度的部分。刚开始的应用主要是应用于立体合的短程移动捕捉,但是随后该研究扩展到了更复杂的领域。1995年Zhangetal.证明了即使在更大的图像变化下,也可以通过利用关联窗口选择待配准图中相似部分来对Harris边沿进行匹配。通过求解一个描述两幅刚性变换景象的几何约束的基础矩阵,移除掉与大多数匹配不相一致的错误匹配后,那些离群值就被去除了。其实,在Zhangetal.发表这个证明的同时,1995年Torr也发表了类似的关于大范围波动的运动图像配准的研究学说,在他的学说里,图像中刚性物体的运动被用来建立几何约束以促使去除掉离群值。其实在这方面研究上真正取得突破性进展的是1997年Schmid和Mohr所做的工作,他们展示了基于局部不变特征的匹配是可以通过将一个特征点与整幅图像进行比较而拓展到所有的图像识别领域的。他们也引用了Harris边沿来寻找关键点,但与开一个关联窗口进行匹配所不同的是,他们运用了局部图像的圆周不变描述符。更深一步,他们论证了复杂的特征匹配是可以通过鉴别匹配特征不变簇来实现混杂、拥塞图像的一般性匹配的。因为Harris边沿探测器对图像尺度的变化是非常敏感的,所以它是不能用来做不同大小图像的匹配的。本文作者Lowe在1999年的所做的早期工作就是使局部特征点在空间尺度变化下的也具有不变性。这些研究开发了一个新的局部描述符,它就可以提供更多的鲜明特征而却对参照图像类似3D视角的变化并不敏感。本论文对此进行了更加深入的探索和分析,也展示了许多在稳定性和特征不变性方面的改进。先前出现了大量的关于论证尺度变化稳定性的研究。最初是1984年Crowley和Parker所做的研究,他们陈述了在尺度空间中峰值的标识,然后把它们关联到一个树状结构中去。这个树状结构可以随后用来在任意尺度变化下的图像间做匹配。近期更多的Shokoufandeh,Marsic和Dickinson1999所做的基于图标来进行匹配的研究则是提供了更好的利用小波参数的特征描述符。而Lindeberg1993、1994年更加深入地对寻找恰当的、一致的尺度空间进行特征探测问题进行了探索。他把此问题描述为尺度选择,下面我们将要用到他的相关结论。近期出现了大量的关于拓展局部特征对于全仿射变换不变性的研究(Baumberg,2000;Tuytelaars和VanGool,2000;Mikolajczyk和Schmid,2002;Schaffalitzky和Zisserman,2002;Brown和Lowe,2002)。这是考虑到在3D正投影的变化下平滑表面特征不变性的匹配,在大多数情况下是对一个局部仿射标架下的图像进行重复采样。然而,这些研究中没有一个是具有完善的仿射不变性的,他们由于难以承受扫描整个仿射空间的花费,刚开始就只能用一种不具有仿射不变性的方式选择初始的特征尺度和坐标位置。另外,仿射结构比具有尺度不变性的特征对噪声要更加敏感,所以实际上仿射特征的可再现性比尺度不变特征的要小,除非仿射失真有超过平面的40度的倾斜(Mikolajczyk,2002)。广义仿射不变性可能对于许多应用领域并非十分重要,比如为了捕捉3D物体的非平面变化和拥塞影响,某些实验角度最好是每旋转30度一个(意味着辨识能力在最接近的实验角度的15度内)。本文所讲述的方法虽然也并没有完全的仿射不变性,但它已有突破,关联特征点在局部描述符微小变换下相应的会有重大变化。这种方法不仅使得描述符在各种程度的仿射失真下更可靠地匹配,而且使得特征在空间3D视角的变化下的拥有更强的健壮性。除此之外,还有更加有效的特征抽取、更多特征的提取能力等优点不尽详述。另一方面,在大的视角变化下的二维平面匹配的仿射不变性对我们来说是一个很宝贵的资源,参照它来对空间3D视角下不变性进行更深入的研究以提高效率和稳定性不失为一种好的思路。许多其他的已被用于图像识别的特征类型也可以添加到本文所论述的特征向量中用以在不同环境下进行更完善的匹配。一种特征是利用了图像中的轮廓或边缘,以使其不至于被背景中贴近物体边界的凌乱东西所干扰混淆。Matas等人在2002年证实了它们的最高稳定性的极值区域可以很可靠地提供大量的匹配特征。Mikolajczyk等人在2003年进一步开发出一种新的描述符,它利用了局部边界而忽略了不相关的临近边界,使其具有了即使在窄小区域的边界上叠加有背景中的杂乱物体也能稳定地发现有用特征的能力。Nelson和Selinger在1998年利用基于图像轮廓归类的局部特征得到了的良好结果。类似地,Pope和Lowe在2000年利用了基于图像轮廓按等级分类的特征,这对缺乏详尽细节的物体尤其有效。在关于视觉识别的研究历史上,所做的工作都是关于各种各样的可以被用来寻找特征的图像工具。Carneiro和Jepson在2002年描述了基于相位的局部特征来表示相位,而不是局部空间频率的级别,而这有可能提供更好的光照不变性。Schiele和Crowley在2000年提出了表示图像区域内检测分布的多维直方图的使用。这种类型的特征可能对于辨认复杂多变纹路物体尤其有效。Basri和Jacobs在1997年已经证明了提取局部区域边界对于视觉识别的价值。所纳入的其他有用属性还包括颜色,运动,图形背景辨别,区域的形状描述,以及立体纵深表示。局部特征的方法可以很容易吸收新的特征类型,因为额外的功能在它们提供了正确的匹配时,非常有助于提高健壮性,而没有提供这种正确匹配时除计算成本以外也不会有什么其他负作用。因此,未来的系统很可能会结合许多的特征类型。3尺度空间极值检测正如简介里所介绍的,我们将会用高效的小波滤波法检测关键点来寻求将来会被进一步详细检测的候选域。关键点检测的第一步是寻求可以被用来在同样物体的不同取景角度下重复标识的空间和尺度。探测对图像尺度变换具有不变性的区域可以通过在所有可能尺度寻找稳定特征点来实现,运用一个被称作尺度空间(Witkin,1983)的连续尺度函数。Koenderink(1984)和Lindeberg(1994)证明在一系列合理假定下唯一可能的尺度空间核是高斯卷积核。因此,图像的尺度空间(图像的尺度空间表达指的就是图像在所有尺度下的描述。)被定义成一个函数,L(x;y;σ),它是由一个变化尺度的高斯函数G(x;y;σ)与输入的图像I(x,y)卷积生成的:L(x;y;σ)=G(x;y;σ)*I(x;y),这里*代表卷积操作,其中2222/)(221),,(yxeyxG。为了高效地探测到尺度空间中稳定的关键点区域,我们提出了(Lowe,1999)利用尺度空间极值通过高斯函数的差分与图像D(x;y;σ)做卷积,即由两个临近的不同不变常数因子k确定的尺度相减求得:),,(),,(),(*)),,(),,((),,(yxLkyxLyxIyxGkyxGyxD。关于为何要选这个函数有多方面的原因。首先,它是一个计算效率极高的函数,例如对于平滑图像,L,需要在每一次尺度空间特征描述时被计算,而D在计算时仅仅是图像的简单相减。图1:对于尺度空间的每一层,原始图像都被高斯算子重复卷积来计算出如图左