基于局部尺度不变特征的物体识别
David G. Lowe
Computer Science Department
University of British Columbia
Vancouver, B.C., V6T 1Z4, Canada
lowe@cs.ubc.ca
转发请注明出处：hewei0241的csdn博客
摘要
一个采用一种新的类别的局部图像特征的物体识别系统已经被开发出来。这些特征是与图像尺度，平移，旋转无关的，且与光照变化，仿射变换或者3D投影部分无关。这些特征与在灵长类动物视觉中用作物体识别的低等的暂时的大脑皮层神经元具有相似的性质。特征通过一个识别尺度空间内稳定的点的多级的滤波方法被有效地检测出来。图像的关键点被允许以通过表示在多个方向平面和多个尺度的模糊图像梯度的局部几何学变形的方式创建。这些关键点被用作识别候选物体匹配的最近邻索引方法的输入。每一个匹配的最终验证是通过找到一个对未知模型参数的低残余最小二乘解来完成。实验结果显示稳定的物体识别能在杂乱的部分闭塞的图片集中以低于2秒的计算时间被完成。
1. 介绍
在杂乱的真实世界场景中的物体识别需要不受附近的杂乱或者部分闭塞的影响的局部图像特征。这些特征必须至少能对光照，3D投影变换以及通常物体变化部分无关。另一方面，这些特征必须也要在用作在许多可供选择的物体之间辨认特定的一些物体时足够显著。物体识别问题在大部分情况在发现这样的特征方面缺乏成功而遇到的困难是必然的。然而，最近的关于利用密集局部特征的研究（例如Schmid
& Mohr [19]）已经显示有效地识别能通过利用在大量的可重复的位置上采样的局部图像描述符被完成。
这篇论文展示了一种被称作尺度无关图像变换（SIFT）的图像特征产生的新方法。这种方法将一幅图像转换到一个局部特征向量的大集合，每一个特征向量都是与图像平移，尺度，旋转无关而且与光照变化，放射变化或者3D投影部分无关。以前的局部特征生成方法缺乏对于尺度的无关性并且对于投影变形和光照变化过于敏感。SIFT特征与在灵长类动物视觉中低等的暂时的大脑皮层神经元响应具有相似的性质。这篇论文还描述了索引和模型验证的改进方法。
尺度无关的特征通过使用一个多级的滤波方法能被有效地鉴别。第一级识别的关键在于在尺度空间寻找高斯差分函数的最大值和最小值。每一个用作描述了局部图像区域采样的生成特征向量的点与它对应的尺度空间同等的帧是相关的。
这种特征能利用模糊图像梯度位置做到对于例如仿射变换和3D投影的局部变换的部分无关。这种方法是基于哺乳动物大脑皮层内的复合单元的一个行为模型。生成的特征向量被称作SIFT关键点。在现在的实现里，一个进程只需要消耗不到1秒的计算时间为每一个图像生成近似1000个SIFT关键点。
来源于图像的SIFT关键点被用作最近邻方法索引去识别候选物体模型。在可能性模型姿势上达成一致的关键点的集合是通过霍夫变换哈希表，然后通过最小二乘适配到一个最终的模型参数估计的方法最先被识别。当至少3个关键点在带有低残余的模型参数上达成一致，就存在出现了这个物体的强有力的证据。因为图像中一个典型物体可能有数十个SIFT特征，有可能在图像中存在大量等级的闭塞然而还是保持了高度的可靠性。
现在的物体模型是被描述成能承受仿射投影的SIFT特征点的2D位置。在特征位置的充分变化能被允许做离开相机大于60度旋转的平面形状或者大于20度的3D物体旋转的透视投影法。
2. 相关研究
物体识别被广泛应用于以检查，登记，处理为目的的机器视觉工业。然而，现在的物体识别的商业系统依靠差不多都是专用的基于相关性的模板匹配。虽然这样在物体形态和光照都严格控制的情况下的确定的工程环境非常有效，但是当物体旋转，尺度，光照和3D形态都允许变化的情况下模板匹配就变得不可行，而且当处理部分可见和大模型数据库的时候更是如此。
一个让机器搜索全部图像位置的可供的选择是从至少与只对于那些特征的图像构造进程和机器部分无关的图像抽取特征。很多候选特征类型已经被提议和探索，包括线段[6]，边的分组[11,14],和区域[2]以及很多其他的提议。尽管这些特征已经在能在确定的物体类型方面发挥很好的效果，但是它们经常不能足够频繁地检测或者具有足够的稳定性用来形成可靠识别的基础。
最近已经有了很多工作投入在研发更加密集的图像特征集合。有一种方法利用一个拐角检测器（更精确地说，是一个局部图像变化的峰值点检测器）去识别可复验的局部图像特征能被测量的图像局部。Zhang et al.[23]使用了Harris角点算子去识别特征位置为了做到来自不同视角的极线校准。宁可通过只匹配每一幅图像中以拐角点为中心的局部区域的方式节省大量计算时间，也不要尝试去对一幅图像中的局部区域与第二幅图像中所有可能的局部区域做相关运算。
为了物体识别问题，Schmid & Mohr[19]也使用了Harris角点算子去识别特征点，而且之后在每一个特征点上通过一个高斯差分图像尺度的方向无关的向量创建了一种局部描述符号。这些图像描述符被以寻找多次匹配满足基于物体的方向和位置的约束的描述符的方式用作粗野的物体识别。这个工作在大量数据库的识别速度和处理杂乱图片的能力两方面都令人印象深刻。
角点算子被用在以前的方法中有一个重大的缺陷，那就是它们只能在图像的一个单一尺度上检测图像。当尺度发生重大变化的情况下，这些算子就会响应不同的图像点。另外，这些算子没有提供一个物体尺度的指示，所有有必要创建图像描述符并且尝试在很多歌不同的尺度上进行匹配。这篇论文描述了一种能在尺度空间里识别稳定关键点的有效方法。这意味着一个图像的不同的尺度对于被选择的关键点位置的集合将是没有影响的。此外，通过每一个点确定了一个明确的尺度，这使得点的图像的描述向量会在每一个图像的相同尺度上被采样。一个典型方向被每一个位置决定，这样匹配可以通过对一个始终不变的2D坐标帧做相关运算完成。这使得可以使用比Schmid和Mohr用过的旋转无关的描述符更加显著的图像描述符，而且描述符可以被进一步地被修改用来提高在改变仿射投影和光照改变的情况下的稳定性。
其他基于外观的识别的方法还包括特征空间匹配[13]，颜色直方图[20]以及感受域直方图[18]。这些方法已经全部被证明能成功地分隔物体或者初步分割。但是由于它们的较多的全局特征很难被扩展到杂乱的和被遮挡的图像。Ohba
& Ikeuchi [15]通过使用多个小的局部特征窗口成功将特征空间的方法应用到杂乱的图像，但是这样在新的图像中的每一个窗口的模板匹配上需要很高代价。
3. 关键点定位
我们希望在图像尺度空间中识别的位置是与图像平移，尺度，旋转无关的，而且尽量少地受到噪声和小失真的影响。Lindeberg [8]已经表明了在一些相当普通的关于尺度无关的假想里，高斯核心以及它的差分是唯一可能在尺度空间分析中平滑核心的。
为了达到旋转无关和高效率，我们已经选择了在尺度空间里应用高斯差分函数取得最大值和最小值的位置作为关键点。
这能通过构建一个图像金字塔在每一个级别重新采样很有效地计算。此外，它把关键点位置确定在高速变化的尺度和区域，使得这些位置的特征抽取过程非常稳定。Crowley & Parker [4] andLinde-berg [9]以前出于其他目的在其他特征空间里使用过高斯差分。接下来，我们描述一种特别有效和稳定的方法来检测和描述这个函数的最大值和最小值。
因为2D高斯函数是可分离的，它和输入的卷积能通过应用2趟在1D高斯函数分别在水平和竖直方向上进行有效地计算：
在关键点定位中，所有的平滑操作都是使用σ=，这样能通过使用带有7个采样点的1D核心逼近有效精度。输入图像会首先和σ=的高斯函数卷积得到图像A，然后使用σ=的高斯函数做进一步增量的平滑第二次重复刚才的过程得到图像B。这样现在就有了一个σ=
2的平滑效果。高斯函数的差分是通过从A减去B来得到，结果是介于两者之间的2 / =
的比率。
为了产生下一个金字塔级别，我们使用在每个方向上间隔1.5个像素点的空间的双线性插值重新采样已经平滑过的图像B。尽管它可能看起来更自然是以作为相关尺度的重采样。唯一的约束是重采样的频率必须足够检测到峰值。1.5的间隔意味着每一个新的样本都将是一个周围4个像素值的常系数线性组合。这样能很有效计算而且最小化由改变重采样系数而引起的混淆现象。
尺度空间函数的最大值和最小值是由比较每一个像素点在金字塔周围的邻居决定的。首先，一个像素与与它位于同一级金字塔的周围的8点像素点进行比较。如果它是这一级的一个最大值或最小值，那么考虑到1.5倍的采样率，最近的像素的位置会在低一级的金字塔中计算。如果像素相比周围的8个邻居像素保持较高（或者较低），然后这个测试会重复到以上的级。因为大部分的像素将在几次比较之内被排除，所以检测的代价是很小的，远低于构建金字塔的过程。
如果第一级的金字塔和输入图像具有相同的采样率，那么最高空间频率将被忽略。这是因为初始的平滑为了粗略检测需要提供峰值点的隔离。因此，我们以2为系数扩展输入图像，使用双线性插值仙域构建金字塔。这样给出了一张典型的512*512像素的图片的1000个关键点的顺序，相比之下没有进行初始化扩展的就只有1/4那么多了。
3.1 SIFT关键点的稳定性
为了描述图像中每一个关键点的位置，被平滑的图像A在金
字塔的每一个级别都被处理抽取梯度和方向。在每一个像素点，图像梯度的大小Mij和方向Rij采用像素差分计算：
像素的差分对于计算和提供足够的精确度是有效的因为之前平滑的实质级别。在决定关键点位置的时候有效的的半像素位置移位是补偿的。
光照变化的健壮性是通过采用将梯度大小的阈值设定最大的可能的梯度值来提高。这样减少了带有3D减轻的表面光照方向的改变的效果。因为光照变化可能会导致梯度大小的剧烈变化但是有可能在梯度方向上只有较小的影响。
每一个关键点的位置被分配到一个典型方向因此图像的描述符是与旋转无关的。为了使得这个对于照明和对比度尽可能的稳定，典型方向是由局部图像梯度方向的直方图中的峰值决定的。
这个方向直方图是使用带有当前的平滑尺度的σ的3倍的高斯权值窗口创建。这些权值是通过阈值梯度值和直方图在对应方向Rij的位置的累积相乘得到的。这个直方图有36个箱子覆盖了360度的旋转角度范围，而且在峰值选择之前会被平滑。
生成的关键点的稳定性能通过使正常图片转换到仿射投影，对比度，光照变化，噪声添加来测试。每一个被检测的关键点的在第一张图片的位置能在变换后的图片中被预测通过知道变换的参数。这个框架曾经被使用来选择以上给出的不同的采样和平滑参数，因此最大效率能通过保持对改变的稳定性来达成。
图片1表明一个相关的少量的关键点经过超过2个8度的只有大尺度的范围（为了避免过多的杂乱）被检测出来。每一个特征点以方块的形式展示，带有一条线从中心到方块的一条边代表方向。在图片的第二张中，图像被旋转了15度，尺度乘上了09的因子，而且以1.1为因子进行了水平方向拓宽。像素的强度，在0-1的范围，亮度值减少了0.1，对比度以0.9为参数乘性降低。然后加上少于5位/每像素的信号的随机的像素噪声。尽管这些变化，第一张图中78%的关键点紧密地匹配了第二张图在预测位置，尺度，和方向的关键点。
关键点对于图像变换的稳定性总的来说能从表2中判断。表里面的每一项是从20张不同的测试图像的结果结合生成，简而言之匹配了大约15000个关键点。表中的每一行表明了一张特定图像变换。第一张图给出了进行尺度上因子为1.5的变换后的图像匹配的关键点占关键点的百分比。第2列给出了匹配这些标准的百分比只要有一个方向在20度之内的预测。
4. 局部图像描述
对每一个关键点给出一个固定的位置，尺度和方向，那么现在就可能可以以一种与这些变换无关的方式描述局部图像区域。此外，能做到对于小的局部几何移位，比如从仿射变换或者3D投影中上升表现出健壮性是令人满意的。一个能做到这样的方法是被视觉皮层的复杂神经元的响应性质暗示的，也就是特征位置允许超出小区域变化然而方向和空间频率特异性是被保持的。Edel-man,
Intrator& Poggio [5]已经进行了实验，内容是模仿合成神经元对计算机立体模型的不同的3D视角的响应，并且发现了合成细胞输出比起简单的基于相关的匹配提供了好得多的鉴别能力。这样看以看出，例如，如果一个仿射投影在一个方向上拉伸一张图像而与另一张做相关运算，这样改变了梯度特征的相关位置尽管只是很少地改变了方向和空间频率。
对于局部几何失真的稳定性能通过用带有表示大量方向（被引用为方向平面）中的每一个方向的多张图像的局部图像区域做到。每一个方向平面只包括梯度对应的那个方向，中间方向会用到线性插值。考虑到梯度位置的大量移动因而每一个方向平面会被模糊和重采样。
这种方法能通过对被用作方向选择的金字塔的每一个级别使用相同的预先计算的梯度和方向被有效地实现。对于每一个关键点，我们使用从特征被检测的金字塔级别进行像素采样。落入一个以关键点位置为中心的半径为8个像素的圆的像素会被插入到方向平面。这些方向通过与减去关键点的主方向被测量因而有与之有关联。在我们的实验中我们采用的是8个方向平面，利用用作梯度检测的像素空间4倍大小的一个采样空间在每一个在4*4的位置网格上采样。模糊通过配置在采样网格中紧邻的8个像素中每一个像素的梯度达成，这个过程会在方向和两个空间维度上用到线性插值。这种实现会比执行显式模糊和重采样要有效得多，但仍然能得出几乎等效的结果。
为了对一个大尺度的图像进行采样，相同的过程可能在金字塔的高一个八度的第二个级别被重复。然而，这一次是2*2而不是4*4的采样区域被使用。这意味着近似地相同的图像区域将被在两个尺度被检测，因此任意附近闭塞将不会影响超过一个尺度。因此，在SIFT特征向量中样本的总数，来自两个尺度共有8*4*4+8*2*2或者是160个元素，给高度特异性以足够的度量标准。
5. 索引和匹配
为了索引，我们需要存储SIFT特征以备用样本图像去从新的图像中识别匹配关键点。为高维向量的识别最相似的关键点的问题众所周知是具有很高的复杂度如果需要精确解。然而，平衡二叉树的算法改版叫做最优搜索方法，能仅以有限数量的计算以最大的概率找到最近的邻居。为了进一步改善最优算法的效率，相对于以小规模生成的SIFT关键点样本，以大规模生成的关键点样本被赋予了两倍的权值。这就意味着大规模的关键点样本能有效的过滤最有可能的邻居为了最小规模关键点的检查。通过赋予更多的权值给最小噪声尺度可以提高认知功能。在我们的实验中，与找到一个精确的解决方案相比，用一个几乎没有任何功能损失的30，000关键点向量概率性最优搜索来检测之多200个邻居，很可能有个切断。
一个高效的方法使一个可靠的模型假设集群，就是用霍夫变换一个统一一个特殊模型构成的关键点，数据库中的每个模型关键点都包含了一个与模型坐标系统相关的关键点参数记录。因此，通过匹配假设，我们可以在哈希表中创造一个入口，用来预测模型的位置，方向，和规模。我们用一个30度容器尺寸来预测方向，用一个2因子来预测规模，用一个为最大模型面积的0.2倍的数来预测位置。即使在大量的几何图行的变形，这些相当宽的容器尺寸可以容许集群。比如3D观点的变化.可以避免散列过程的边界效应。每个假设在每个容积中被散列成两个最近的容器。为每个假设赋予了总共16个散列表的入口。
6. 仿射参数的解决方案
搜索散列表用来确定所有集群容器的至少三个入口。这些容器按照尺寸的减少的顺序来分类。每个集群隶属于一个核查程序，它为了一个与图像模型有关的仿射工程参数而执行的一个最小二乘的解决方案。
这个仿射变换的模型点对应到图像点可以写作
而模型转换是，仿射旋转，尺度以及伸缩等变换由mi参数表征。
我们希望能解出变换参数，所以以上等式可以重写为：
这个等式说明了一个简单的匹配，但是一些数字的进一步匹配需要加入，每一个匹配贡献更多的两行加到矩阵的第一行和最后一行。为了提供一个解决方案至少需要3个匹配。
我们可以把这个线性系统写成：
最小二乘解参数x能被对应的等式决定：
这种解法减少了从图像位置到对应的投影模型平方距离的总和。这个方法能容易地被扩展至解决3D姿势和铰接的和弹性的对象的内部参数。
异常值现在能通过检测图像特征和模型之间的一致性，给出参数解的方式删除。每一个匹配必须满足在15度以内的方向，在尺度方面改变倍，而且根据位置相差在0.2倍最大模型大小。如果少于3个点在丢弃异常点之后保留下来，那么这个匹配就被拒绝了，如果任何一个异常值被拒绝，那么最小二乘解法将使用剩下的点重计算一次。
7. 实验
仿射变换解法提供了一个很好的近似到平面的透视图投影。所以平面模型为这种方法提供了一个很好的初始测试。图3的顶行展示了3个物体的矩形平面表面的模型图像。这张图也显示了杂乱的图像，包括平面物体，和在用作识别的模型的层上面的相同图像。这些模型的被显示出来的关键点都是用作识别和最后的最小二乘解。这些和图像中平面区域的真实边界高度一致，除了由于透视投影引入的小错误。还利用很多平面物体的图像做了相似的实验，证明识别能健壮得维持到从远离相机的任何一个方向至少60度的物体旋转。
虽然模型图像和仿射参数对于3D物体的深度是没有作用的，但是它们对于3D物体从每一个模型角度在20度之内的深度偏离的旋转仍然能有效地运行。一个3模型图像的在图4的顶行被显示，这个模型是在一个黑暗的背景下拍摄的，而且物体轮廓在背景区域分割中被提取出来。一个识别的例子在同一张图中显示出来，再一次展示了被用作识别的SIFT关键点。将物体轮廓使用仿射参数解投影，但是这一次一致性并不是很接近因为解法没有考虑到在深度方面的旋转。图5显示了有效的空间局部遮挡。
在这些例子中图像的大小是384*512像素的，对于在每一张图片中所有的对象在Sun Sparc10处理器上运行，识别时间大约是1.5秒，其中0.9秒需要构建尺度空间金字塔和识别SIFT关键点，大约0.6秒作为运行索引和最小二乘验证。这不包括预处理每一张模型图片的时间，可能每张图片也需要1秒钟，但是只需要再作为初始项加入到模型数据库而运行一次。
SIFT关键点的光照不变性在图6中展示，这两张图像是在同一个视角的相同场景，除了第一张图像的光照来自左上方而第二张的光照来自右方中心，整个识别系统运行把第一张图片作为模型去识别第二张图片，而第二张图片匹配了第一张图片被正确识别，只有部分用作识别的SIFT特征被显示出来了。有273个特征点被证实了是最终匹配的一部分，这意味着每一个情况下不但同一个关键点在同一个位置被检测出来，而且是最近匹配到正确对应的关键点，任何3个这样的关键点对于识别都是有效的。当匹配关键点在一些焦点和阴影的改变（例如照相机闪光点的改变）的区域没有被发现，一般情况下关键点表现出对于光照改变的良好不变性。
8. 与生物学视觉的联系
人类视觉的性能显然远胜于现在的计算机视觉系统，所以这里可能更多地从仿效生物学处理过程而获得启发。幸运地是，已经存在过去的一些年里在理解在动物和人类的视觉中物体识别是怎么做到的动态改进。
最近在神经科学的研究显示物体识别在灵长类利用大量都是和尺度，位置，光照变化无关（Tanaka[21],Perret&Oram[16]）中间复杂度的特征。一些被发现在低等暂时性脑皮层里（IT）的这样的中间特征的例子是神经元对于一个黑暗五边形的响应，一个带有细小突出部分的圆圈或者在一个三角边界内水平纹理的响应。这些神经元对于出现在任何地方带有大部分视觉区域超过尺度的范围（Ito et.al[7]）的形状特征保持高度特异性响应。很多这样的特征的复杂度显示出粗略和现在的SIFT特征相同，尽管存在一些神经元对于更多复杂的形状响应更多，比如人脸。很多神经元对于颜色和纹理性质的响应比形状要强。这些特征响应表明是依靠最近视觉学习来自特殊物体暴露部分包含特征（Logothetis,
Paul&Poggio）。这些特征好像是在大脑中通过高速计算敏感的并行计算被推断，这与这篇文章中介绍的分期滤波方法有很大不同。然而，结果却很相似，一个图像转换到一个本地图像的大集合中，每一个匹配少数的很大程度上与一般视觉变换无关的潜在物体。
众所周知在大脑中物体识别依靠一个注意力绑定特征解释，决定姿势，将物体从背景中分割的串行过程。这个过程可能和在这篇文章使用的确认参数解和轮廓检测扮演着相同的角色，因为解释的精度经常依靠实施一个简单的视角约束。
9. 结论和评论
SIFT特征很大程度上改进了之前方法，使之对于尺度，光照，局部仿射畸变无关，大量的特征在一张典型图片上考虑到在杂乱图片中的布局遮挡的健壮的识别。一个最终阶段为仿射模型参数考虑到比依赖于索引的方法具有更精确的验证和姿势决定的解决方案。
一个为了深入研究的重要领域是从代表物体3D结构的多视角构建模型。这会有更进一步的优点因为关键点从多视角条件下能被组合成为一个模型，因此增加了发现在新的视角上匹配的可能性。这个模型能被基于动作和结构解决方案的真3D表示，或者能表示根据自动化聚簇或者插值在空间里表示出外观（Pope&Lowe[17]）。后者的方法的一个优点是能让模型非刚性变形。
识别性能通过增加新的SIFT特征类型到混合颜色，纹理，边缘群组，还有改变特征大小和偏移等方式能进一步提高。尺度无关的群组关系使得局部图背景鉴别对背景杂乱可以混淆其他特征的物体边缘会特别有用。索引和验证框架使得全部种类的尺度和旋转不变的特征将被合并到一个单一的模型表示。最大的健壮性将被通过检测许多不同特征类型和依靠索引和聚簇在详细图片中选择那些寻找最有用的来实现。
参考文献
_001_SIFT_ICCV 1999_David Lowe_Objectrecognition from local scale-invariant features