基于局部尺度不变特征(SIFT特征)的物体识别
基于局部尺度不变特征的物体识别
David G. Lowe
Computer Science Department
University of British Columbia
Vancouver, B.C., V6T 1Z4, Canada
转发请注明出处：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
> 本站内容系网友提交或本网编辑转载，其目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请及时与本网联系，我们将在第一时间删除内容！
(参考CSDN博主cy513的分析内容) 首先,介绍一下人类是如何识别物体的: 人类是如何识别一个物体的呢,当然要对面前的这个物体为何物要有一个概念,人类一生下来就开始通过视觉获取世间万物的信息,包括一种物体形状.颜色.成分等,以及通过学习认识到这种物体的其他信息比如物理的.化学的特性,这些信息是不能通过观察得到的:就这样人对一种新物就有了把握,并且物体的各 ...
本文记录如何利用sift特征点进行人民币的识别.本文给出的matlab源码识别了1元与100元人民币的面额,相同思路,可以对各种币值的人民币进行面额.正反面的识别.但由于本程序采用串行,模板数的增多会导致运行时间线性增长,具体应用时你可以采取并行的方法加以优化,本文只给出思路. 本文的sift特征提取源码采用的是David G. Lowe(sift提出者)提 ...
本文记录如何利用sift特征点进行人民币的识别.本文给出的matlab源码识别了1元与100元人民币的面额,相同思路,可以对各种币值的人民币进行面额.正反面的识别.但由于本程序采用串行,模板数的增多会导致运行时间线性增长,具体应用时你可以采取并行的方法加以优化,本文只给出思路. 本文的sift特征提取源码采用的是David G. Lowe(sift提出者)提 ...
基于SIFT特征的全景图像拼接 分类: image Machine learning 13:33 2554人阅读 评论(3) 收藏
基于SIFT特征的全景图像拼接 分类: 计算机视觉/OpenCV 21:43 91人阅读 评论(0) 收藏
主要分为以下几个步骤: (1) 读入两张图片并分别提取SIFT特征 (2 ...
----------------------------------------------------------------------------- 已经提取的SIFT特征文件格式:
&N&:所有图片的数量
&M1&:每一张图片的SIFT特征数
&1&:第一个1个128维s ...
1.SIFT算法基本概念 Sift是David Lowe于1999年提出的局部特征描述子,可以处理两幅图像之间发生平移.旋转.仿射变换情况下的匹配问题,具有良好的不变性和很强的匹配能力.SIFT算法是一种提取局部特征的算法,也是一种模式识别技术,其基本思想是在尺度空间寻找极值点,提取位置,尺度,旋转不变量,它主要包括两个阶段,一个是Sift特征的生成,即从多 ...
SIFT 特征变换算法
David Lowe关于Sfit算法,2004年发表在Int. Journal of Computer Vision的经典论文中,对尺度空间(scal space)是这样定义的 :
It has been shown by Koenderink (1984) and Lindeberg (1994) that
转自:http://blog.csdn.net/v_JULY_v 作者:July改了点代码让它在VS2010上可以跑了,这么有营养的代码慢慢啃,慢慢分析~~ July真牛! #ifdef _CH_ #pragma package &opencv& #endif #ifndef _EiC #include &stdio.h& #incl ...IBM Bluemix
点击按钮，开始云上的开发！
developerWorks 社区
本文针对大型网站的特点，结合 Rational AppScan 的工作原理，分析从扫描策略选择，扫描设置，任务分解等角度来如果更有效使用 Rational AppScan 进行应用安全扫描。“知己知彼，百战不殆”，在第一部分，首先我们一起来讨论分析 Rational AppScan 的工作原理和并分析大型网站的特点；在后续的第二部分将结合一个案例，看如何使用 Rational AppScan 来完成对大型网站的安全检查。
, 客户技术专家, IBM
庄俊乾，是 IBM 中国有限公司软件部 Rational 客户技术专家。专著方向为软件自动化测试，性能测试，应用安全测试等领域。为电信金融行业等多家公司提供软件过程管理的咨询、技术和产品实施服务工作。当前的主要研究方向有软件质量管理/应用安全测试等。您可以通过 developerWorks 社区与进行交流。
下载试用版：
下载更多的 ，并加入 ，参与在线交流。Rational AppScan 工作原理Rational AppScan（简称 AppScan）其实是一个产品家族，包括众多的应用安全扫描产品，从开发阶段的源代码扫描的 AppScan source edition，到针对 Web 应用进行快速扫描的 AppScan standard edition，以及进行安全管理和汇总整合的 AppScan enterprise Edition 等。我们经常说的 AppScan 就是指的桌面版本的 AppScan，即 AppScan standard edition。其安装在 Windows 操作系统上，可以对网站等 Web 应用进行自动化的应用安全扫描和测试。来张 AppScan 的截图，用图表说话，更明确。图 1. AppScan 标准版界面请注意右上角，单击“扫描”下面的小三角，可以出现如下的三个选型“继续完全扫描”、“继续仅探索”、“继续仅测试”，有木有？什么意思？理解了这个地方，就理解了 AppScan 的工作原理，我们慢慢展开：还没有正式开始安全测试之前，所以先不管“继续”，直接来讨论“完全扫描”，“仅探索”，“仅测试”三个名词：AppScan 三个核心要素AppScan 是对网站等 Web 应用进行安全攻击来检查网站是否存在安全漏洞；既然是攻击，需要有明确的攻击对象吧，比如北约现在的对象就是卡扎菲上校还有他的军队。对网站来说，一个网站存在的页面，可能成千上万。每个页面也都可能存在多个字段（参数），比如一个登陆界面，至少要输入用户名和密码吧，这就是一个页面存在两个字段，你提交了用户名密码等登陆信息，网站总要有地方接受并且检查是否正确吧，这就可能存在一个新的检查页面。这里的每个页面的每个参数都可能存在安全漏洞，所有都是被攻击对象，都需要来检查。这就存在一个问题，我们来负责来检查一个网站的安全性，这个网站有多少个页面，有多少个参数，页面之间如何跳转，我们可能并不明确，如何知道这些信息？看起来很复杂，盘根错节；那就更需要找到那个线索，提纲挈领；想一想，访问一个网站的时候，我们需要知道的最重要的信息是哪个？网站主页地址吧？从网站地址开始，很多其他频道，其他页面都可以链接过去，对不对，那么可不可以有种技术，告诉了它网站的入口地址，然后它“顺藤摸瓜”，找出其他的网页和页面参数？OK，这就是“爬虫”技术，具体说，是“网站爬虫”，其利用了网页的请求都是用 http 协议发送的，发送和返回的内容都是统一的语言 HTML，那么对 HTML 语言进行分析，找到里面的参数和链接，纪录并继续发送之，最终，找到了这个网站的众多的页面和目录。这个能力 AppScan 就提供了，这里的术语叫“探索”，explorer，就是去发现，去分析，了解未知的，并记录之。在使用 AppScan 的时候，要配置的第一个就是要检查的网站的地址，配置了以后，AppScan 就会利用“探索”技术去发现这个网站存在多少个目录，多少个页面，页面中有哪些参数等，简单说，了解了你的网站的结构。“探索”了解了，测试的目标和范围就大致确定了，然后呢，利用“军火库”，发送导弹，进行安全攻击，这个过程就是“测试”；针对发现的每个页面的每个参数，进行安全检查，检查的弹药就来自 AppScan 的扫描规则库，其类似杀毒软件的病毒库，具体可以检查的安全攻击类型都在里面做好了，我们去使用即可。那么什么是“完全测试呢”，完全测试就是把上面的两个步骤整合起来，“探索”+“测试”；在安全测试过程中，可以先只进行探索，不进行测试，目的是了解被测的网站结构，评估范围；然后选择“继续仅测试”，只对前面探索过的页面进行测试，不对新发现的页面进行测试。“完全测试”就是把两个步骤结合在一起，一边探索，一边测试。AppScan 工作原理小结如下：通过搜索（爬行）发现整个 Web 应用结构根据分析，发送修改的 HTTP Request 进行攻击尝试（扫描规则库）通过对于 Respone 的分析验证是否存在安全漏洞图 2. AppScan 扫描原理：扫描规则库 + 爬行 + 测试步骤 1：探索（又叫爬行，爬网）图 3. 探索（爬网，爬行）步骤 2：测试（针对找到的页面，生成测试，进行安全攻击）图 4. 针对探索发现的页面和参数，进行安全测试所以，简言之，AppScan 的核心是提供一个扫描规则库，然后利用自动化的“探索”技术得到众多的页面和页面参数，进而对这些页面和页面参数进行安全性测试。“扫描规则库”，“探索”，“测试”就构成了 AppScan 的核心三要素。而在安全扫描过程中，如何进行优化，就要结合这三个要素，看哪些部分需要优化，应该如何优化。AppScan 结果文件同时，对于 AppScan 标准版来说，扫描的配置和结果信息都保存为后缀名为 Scan 文件，Scan 文件里面主要包括的内容如下：扫描配置信息：扫描配置信息，如扫描的目标网站地址，录制的登陆过程脚本等，选择的扫描设置等都保存在 Scan 文件中。所有访问到页面信息：针对每个发现的页面，即使没有进行测试，在探索过程也会访问该页面并纪录 http request/response 信息；所以如果探索的页面访问的时候返回的页面内容比较多，页面比较大，那么即使只做了探索根本没有扫描，整个 Scan 文件也会很大。测试阶段，记录测试成功的测试变体和页面访问信息：针对每个页面都会发送多次测试（测试变体），每次测试都会有 Request/response 信息，这些信息如果测试通过，即发现了一个安全问题，则会把该测试变体对应得 request/response 都会纪录下来，保存在 .scan 文件中；由于 AppScan 的扫描测试用例库全面，对于每种安全威胁漏洞，都会发送多个安全测试变体（Variant）进行测试，比如对于 XSS 问题，AppScan 发送了 100 个变体，其中 30 个执行失败，70 个变体执行成功，则会纪录 70 次执行成功的具体变体信息，以及每个变体对应的 Request/Response 信息。这就是一个很大的数据量。这些信息保存以后，就可以在不连接在网站的情况下进行结果分析，快速显示当时测试的页面快照等。我们以http://demo.testfire.net/bank/customize.aspx 为例，如下就有 74 个变体都发现了 Customize 页面的 Lang 参数存在跨站点脚本执行（XSS）类型的安全漏洞：图 5. 测试变体显示所以针对 AppScan 标准版来说，由于需要保存的信息比较多，结果文件是会比较大的，最根本的方法还是有针对性地进行扫描和测试，使用排除页面等排除冗余页面，把一个大的系统分解为多个小的扫描任务等。好的，了解了 AppScan 的原理，我们就结合原来讨论下为什么扫描大型网站时候可能遇到问题了。大型网站技术特点分析AppScan 扫描的对象是网站等 Web 应用，而网站规模的大小和使用的技术，都需要针对性的进行扫描设置，我们遇到的很多问题，都是在扫描规模比较大的网站时候遇到的，如一个网站页面数目超过 2000 个，需要执行的扫描用例是 50，000 个，在扫描这样的网站时候，默认情况下 AppScan 的扫描 scan 文件可能超过 100M 了，扫描效率就可能比较慢，需要长时间的扫描运行时间。下面，我们就来分析大型网站中存在的一些可能影响 AppScan 扫描的技术特点。网站页面多，页面参数多，则 AppScan 需要发送的测试用例多什么叫大型网站，顾名思义，网站规模大，提供内容多；具体说是页面很多，内容很全。比如 .cn，比如 /，网站中都有多个频道，包括上万个页面。而且除了页面多，可能还有一个特点 --- 页面参数多，即要填写的地方多，和用户的交互多；比如一个网站如果都是静态页面（.html、.jpg 等），没有让用户输入的地方，那么可以利用，可以作为攻击点的地方也就不多。如果页面到处都是有输入有查询，要求用户来参与的，你输入的越多，可能泄露的信息也越多，可能被别人利用的攻击点也就越多，所以和页面参数也是有关系的。AppScan 产生测试用例的时候，也是根据每个参数来产生的，简单说，如果一个参数，对应了 200 个安全攻击测试用例，那么一个登陆界面至少就对应 400 个了，为什么？登陆界面至少有用户名（username）和密码（password）两个字段吧？每个字段 200 个攻击用例。这个简单吧，还可以更复杂：如果遇到下面的两个地址，那要扫描多少次呢？/focus/satisfy/file.jsp?id=1
/focus/satisfy/file.jsp?id=2上面的两个地址有类似的，“?”号以前的 URL 地址完全一样，“?”号后面带的参数不同，这种可以认为是重复页面，那么对于重复页面，是否要重复测试呢？这取决于“冗余路径设置”，默认的是最多测试 5 次；即，这种类型 URL 出现的前 5 次，那么就是要测试 1000 个攻击用例了。如果再继续修改下：遇到下面的 URL 呢/focus/satisfy/file.jsp?id=&Item=open
/focus/satisfy/file.jsp?id=2&Item=close每个 URL 里面都有 2 个参数，测试的次数就更多了。想象下，如果这个网页里面的参数如果是 10 个，或者更多的呢？比如很多网站提交注册信息的时候，要填写的栏位就很多，要进行的安全测试用例也就随之不断增加…这是网站规模的影响，还有一个问题，就出在“每个参数，发送 200 个安全测试用例”这个假设上。这个假设的前提来源于哪里？来源于我们选择的扫描规则库。即你关心那些安全威胁，这个需要在测试策略里面选择。同样来参照杀毒软件，你会用杀毒软件来查找一些专用的病毒吗，比如 CIH、木马；应用安全扫描也是一样的道理，如果有明确的安全指标或者安全规则范围，那么就选择之。这些可能来源于企业的规范，来源于政府的法律法规。就要根据你的理解，在这里选择。图 6. 选择测试策略在实际工作中，我们也很难在最开始的阶段，就把扫描规范制定下来，按照项目经理们的口头禅“渐进明细”，“滚动式规划”，在实践中，更多时候也是摸着石头过河，选择了一个扫描策略，然后根据结果分析，看是否需要调整，不断优化。比如选择默认的“缺省值”扫描策略，对网站进行扫描，发现其“敏感信息”里面会去检查页面上是否含有 Email 地址，是否含有信用卡号码等，如果我们觉得这些信息，显示在页面上是正常的业务需要（比如这样的链接：&a href="mailto:admin@"&有问题请联系 admin@&/a&），我们就可以取消掉这些规则，所以扫描规则也很大程度上影响着我们的扫描效率。网站采用多种混合的技术，需要不同的扫描设置一些大型网站，往往是一个统一的入口，在里面提供不同的内容，而这些内容可能来源于不同的技术。如我们熟悉的门户网站，里面就有“财经”、“体育”、“娱乐”等多个频道；每个频道的内容，可能是采用不同的技术，对应不同的服务器。如一个网站的“论坛”频道，就有很多类似的页面：/bbs/showthread.php?id=1
/bbs/showthread.php?id=2
/bbs/showthread.php?id=3这里的 showthread.php 页面存在多次，每次都是参数值不同，访问后发现这些页面除了文本内容外，其他的页面结构等都相同，则这些页面只需要选择几个典型的扫描即可，没有必要全部扫描。而同时，在另外的一些频道，存在另外类型的页面：/default.aspx?content=inside_community.htm
/default.aspx?content=inside_press.htm
/default.aspx?content=inside_executives.htm这些动态页面，也是网址相同，参数相同，但是具有不同的参数值，访问时候发现每种类型的参数值都指向了完全不同的页面，则需要每种参数值都要测试到。这种情况经常存在跳转页面中。而这两个频道中，第一种情况，可以选择典型的页面扫描之，而第二种情况则需要进行完全的扫描，每种参数值都需要考虑到。这就需要不同的扫描设置。同时，可能大家也注意到了，第一种情况下的是 php 页面，而第二种情况下的则是 aspx 页面，对应不同的开发技术，这也可能需要不同的扫描设置。所以，总结下，AppScan 的扫描受到如下因素的影响：网站规模（页面个数，页面参数）扫描策略的选择扫描设置而对于大型的网站，我们经常需要从几个方面来优化配置选择合适的，最小化的扫描规则分解扫描任务，把一个大的扫描任务分解为多个小的扫描任务根据页面特点，设置可以过滤的类似页面（冗余页面）接下来工欲善其事，必先利其器，选择了 AppScan 这个专业的 Web 应用安全测试工具，那么接下来的第二部分，我们结合一个例子，来讨论么可以更好的优化设置，把工具充分利用起来。
参考资料 查看本系列的第二部分：“”。“”（developerWorks，2007 年 11 月）：您的 Web 应用安全吗？仅仅是防火墙能够保证 Web 应用的安全吗？如何避免遭受黑客利用跨站点脚本攻击（Cross Site Scripting Flaws）等由 OWASP所公布的 Web 应用安全漏洞入侵您的网站？本讲座将为您一一介绍这些关于 Web 应用安全的常见问题。同时，还将为您介绍专门面向 Web 应用安全检测的自动化工具 IBM Rational AppScan。并介绍如何运用 Rational AppScan 来自动化检测 Web 应用的安全漏洞，从网站开发的起始阶段就扫除 Web 应用安全漏洞。“”（developerWorks，2007 年 12 月）：本文将从对 Web 应用现状的分析入手，通过列举常见的攻击手段，阐明 Web 应用目前面临的挑战，同时，通过对 Rational AppScan 平台的介绍，协助企业制定 Web 应用安全解决方案，为企业的 Web 应用披上盔甲。在第一部分，将介绍 Web 安全与 Rational AppScan 的入门知识。在后续的 第二部分 将介绍如何使用 Rational AppScan 应对 Web 应用攻击。“”（developerWorks，2007 年 12 月）：本文将针对 Web 安全的现状、根源、以及 Rational AppScan 产品的技术细节做全面的介绍，最后阐述IBM解决方案给企业带来的深层次价值。“”（developerWorks，2008 年 6 月）：本次演示将帮助您了解一个面向 Web 应用程序与 Web 服务的黑箱安全扫描工具——Rational AppScan。利用 AppScan，应用程序开发团队在项目交付前，可以对所开发的应用程序与服务进行安全缺陷的扫描。“”（developerWorks，2008 年 9 月）：本文分为两部分，第一部分将从 Web 应用安全解决方案的演进入手，探究解决方案的发展之路，并对文中称之为“战略方法”的企业级解决方案及其特点进行深入分析。“”（developerWorks，2008 年 9 月）：本文分为两部分，第二部分中，将从开发人员、安全管理员、经理等角色出发，用实例的形式展示出使用统一的管理平台后，给企业安全管理带来的方便性、统一性和其它优势。“”（developerWorks，2010 年 2 月）：IBM Rational AppScan 是全面的 Web 应用安全解决方案，为 Web 及 Web 2.0 应用提供了扫描、报告和修复建议等功能，可以帮助开发者在项目起始阶段就能全面准确地发现并解决安全问题。本文从新手入门的角度，为您全面介绍了 Rational AppScan 的使用方法，帮助您了解并在实际应用中运用这一功能强大的自动化 Web 应用安全检测工具。查看演示：，本次演示将帮助您了解一个面向 Web 应用程序与 Web 服务的黑箱安全扫描工具——Rational AppScan。利用 AppScan，应用程序开发团队在项目交付前，可以对所开发的应用程序与服务进行安全缺陷的扫描。通过多媒体课堂“”，深入了解 Rational AppScan。访问 ，获得关于统一建模语言（Unified Modeling Language，UML）的入门知识、技术资源和最佳实践。访问 ，获得关于 IBM Rational 软件交付平台（Rational Software Delivery Platform）产品的技术资源和最佳实践。订阅 ，一份关于 developerWorks 指南、文章、下载、社区活动、网络广播和技术讲座的电子周刊。下载免费的 。访问 ，了解最新的 IBM Rational AppScan 产品文档和产品信息，获得关于 IBM Rational AppScan 及与 Web 应用安全相关的技术文档和参考资源，还可以查阅产品概览、产品手册、产品技术支持、试用版下载，以及相关文章、教程、多媒体课堂和产品演示等信息。获取免费的 ，了解最新的 IBM Rational 软件开发工具技术文档和资源。下载更多免费的 ，了解 IBM Rational 软件的最新特性。获取更多 ，并熟练掌握来自 DB2®、Lotus®、Tivoli®，以及 WebSphere® 的开发工具和中间件产品，用这些试用版软件开发您的下一个项目。这些试用版软件可以免费直接从 developerWorks 下载。加入 ，developerWorks 社区是一个面向全球 IT 专业人员，可以提供博客、书签、wiki、群组、联系、共享和协作等社区功能的专业社交网络社区。加入 ，参与在线交流。
developerWorks: 登录
标有星（*）号的字段是必填字段。
保持登录。
单击提交则表示您同意developerWorks 的条款和条件。 查看条款和条件。
在您首次登录 developerWorks 时，会为您创建一份个人概要。您的个人概要中的信息（您的姓名、国家/地区，以及公司名称）是公开显示的，而且会随着您发布的任何内容一起显示，除非您选择隐藏您的公司名称。您可以随时更新您的 IBM 帐户。
所有提交的信息确保安全。
选择您的昵称
当您初次登录到 developerWorks 时，将会为您创建一份概要信息，您需要指定一个昵称。您的昵称将和您在 developerWorks 发布的内容显示在一起。昵称长度在 3 至 31 个字符之间。
您的昵称在 developerWorks 社区中必须是唯一的，并且出于隐私保护的原因，不能是您的电子邮件地址。
标有星（*）号的字段是必填字段。
(昵称长度在 3 至 31 个字符之间)
单击提交则表示您同意developerWorks 的条款和条件。 .
所有提交的信息确保安全。
文章、教程、演示，帮助您构建、部署和管理云应用。
立即加入来自 IBM 的专业 IT 社交网络。
为灾难恢复构建应用，赢取现金大奖。
static.content.url=/developerworks/js/artrating/SITE_ID=10Zone=RationalArticleID=749977ArticleTitle=如何更有效使用 Rational AppScan 扫描大型网站，第 1 部分: 工作原理及技术分析publish-date=