基于形状上下文的形状匹配和目标识别--大学毕业设计论文.doc

基于形状上下文的形状匹配和目标识别摘要：我们提出了一种测量图形间相似性的新方法，并开发它来做目标识别。 在我们的架构下，相似性的度量之前：1）解决两种形式下点与点的对应性2）利用这种对应性来估计一个对齐变换。为了解决对应问题，我们为每一个点附上一个形状上下文的描述。一个参考点的形状上下文能捕捉剩下与之相关的点的分布情况，从而提供全面的可识别的描述。两个相似图形上的对应点会有相似的形状语境，使我们将解决对应问题看做最优分配问题。给出点与点的对应，我们估计最佳匹配两种形状的变换，为这个用途，正则化薄板样条函数提供了灵活的图类转换。两个形状间的不同通过对应点间的匹配误差总和与测量对齐变换的大小项一起来计算。我们把最近邻分类架构下的识别当作在图像上查找最大限度相似的存储原型问题，结果是轮廓线、商标、手写数字和线圈数据集。关键词:形状，目标识别，数字识别，对应性问题，MPEG7标准，图像配准，变形模板1 绪论考虑图1中的两个手写体数字。视为像素亮度值的向量使用二级规范相比，他们有很大的不同。但是，视为形状，它们显得和人类的观察员类似。我们在本文的目的是实施形状相似这一概念，其最终目的是用它作为概念层次识别的基础。我们通过一个三阶段的过程来实现：1、 解决这两个图形间的对应问题2、 使用对应关系来估算对齐变换3、 用对应点之间的匹配误差的总和，加上测量对齐变换的大小，来计算两个形状之间的距离我们的做法的关键是传统的形状匹配变形，可至少追溯到达西汤普森。在他的经典作品中，对增长和形式55，汤普森指出，相关但不相同的形状，往往可以使用简单的坐标变换对齐，如图2所示的变形。在计算机视觉文献，费什勒和Elschlager15实施了在质量弹簧模型中使用mini-mization能源这一想法。Grenander等21在概率设置中发展了这个想法，Yuille61通过使用梯度下降的图像域下的手工制作的拟合参数化模型，如眼睛，来发展变形模板概念的另一变体。另一个众所周知的这一脉的计算方法是由Lades31等人通过lastic图匹配发展而来。我们在这项工作的主要贡献是发现形状之间对应关系的强大和简单的算法。形状代表了一系列形状轮廓（通常为100左右从边缘探测器输出采样的像素位置）采样点。这里没有什么特别的点，它们不需标记或曲率极值等，使用的样本越多，我们获得越好的近似的基本形状。我们引进一个形状描述符，形状上下文，来描述对于给定一个的点的形状的其他部分的粗分布。两个形状之间的对应关系则相当于为一个形状上每个采样点找到其他形状上的最相似形状上下文。最大化的相似性和执行的独立性，导致一个二分图的匹配（等效，最优分配）问题。根据需要，我们可以很容易结合其他匹配的信息来源，例如在对应点的本地外观的相似性。给出采样点的对应关系，我们通过估计反应一个形状到另一个形状的映射的关系的对齐变换来延长通信完整的形状。图2提供了这个想法的一个经典说明。转换可以从许多的家系中挑选，在各种应用中，我们已经使用了欧氏，仿射和正则化薄板样条函数。对齐形状，简单定义，就是形状相似性的衡量。两个形状之间的相异现在用对应点之间的匹配误差的总和，加上一个变形转换的幅度来测量。图1.两个手写体数字的例子。就像素到像素比较而言，这两个图像是相当不同的，但是人类的观察者看到的形状是相似的。针对这一差异性措施，我们可以使用最近邻技术来进行目标识别。哲学上，最邻近技术与Rosch4748等人开发的基于原型的识别有关。它们具备的优势，向量空间结构不是只需要一个成对相异的措施。我们证明了各种各样设置下的目标识别。我们处理2D对象，例如，手写数字的MNIST数据集（图8），轮廓线（图11和13），以及使用多个视图建模的哥伦比亚线圈数据集中的3D对象（图10）。这些广泛使用的基准和我们的方法原来在其中有数据比较的问题中是领先的。我们还开发了一种基于视觉复杂性的为每个对象类选择其存储视图的技术。作为说明，我们在COIL-20数据集中的3D对象中表现了，能够获得低至2.5%的错误分类误差，只使用每个目标对象的4个视图的平均（见图9和10）。本文的结构如下：我们在第二部分讨论相关的工作，在第三部分详细描述形状匹配的方法，在第四部分展示变换模型。然后，我们在第五部分讨论形状相似性的度量，并在第六部分引用包括手写体数字和3D物体图片在内的一系列数据集证明我们提出的方法。我们在第七部分进行总结。2 形状匹配的已有工作数学家通常定义形状为一群变换下的一个等价类。这个定义在视觉分析上下文中是不完全的。这只能告诉我们两个形状何时是完全相同的。至于形状相似或形状距离理论，我们需要的更多。统计学上定义的形状，Bookstein6或Kendall29，假定对应关系是已知的，致力于形状距离的问题。其它关于形状对应的统计学方法不需要对应关系，例如，人们可以比较包括描述符号的特征向量，但是这类技术经常在这个过程中丢弃详细的形状信息。形状相似性也还在心理学文献中被研究过，Goldmeier20就是早期的一个例子。关于计算机视觉方面的形状匹配的广泛调查能够在5822中找到。概括地说，有两种方法：1）基于特征的，这个包括提取特征的空间安排，如边缘元素或连接点2）基于亮度的，这使得更直接的使用像素的亮度。2.1 基于特征的方法通过使用轮廓线图像的边界，已经做了大量关于形状相似性的研究。由于轮廓线没有孔或内部标记，相关边界可以方便的用弧长参数表示一个单一的封闭曲线来表示。早期的工作中使用傅里叶描述符，例如，6243。Blum的中轴变换，导致试图捕捉在Kimia，Zucker和Sharvit53等合作者的图形结构骨架中的形状的部分结构。1D轮廓线曲线的性质自然地导致动态规划方法的匹配，例如，17，它采用曲线间的编辑距离。对包括一些清晰度和闭塞的几种变换，该算法是快速和不变的。做为MPEG-7标准的活动的一部分33，综合比较了不同形状描述符来比较的轮廓线，用由于Latecki等33和Mokhtarian39等领先的方法。图2.从D Arcy汤普森的生长形式55，有关坐标变换的两条鱼的例子。汤普森观察到类似的可能与生物形式之间的同源简单的数学变换手段（即对应）功能。同源功能的例子包括眼中心，背鳍尖端等。轮廓线是从根本上作为一般物体的性质描述的限制；他们忽视了内部的轮廓，很难从真实的图像中提取。更有前景的方法是把形状当作一套在二维图像里的点。从一张图像上提取这些算不了什么问题，例如，可以只使用一个边缘检测器。Hutten-locher等开发基于Hausdorff距离23的方法，这可扩展到处理部分匹配和杂波。我们的目的的一个缺点是，该方法不返回对应关系。基于距离变换的方法，如16，在实践中的精神和行为是相似的。Sclaroff和彭特兰的工作50代表特征向量或基于模式匹配的方法，见525157。在这种方法中，图像中的样本点转换为有限元弹簧-质点模型，对应关系通过比较振动模式发现。和我们的做法最密切相关的是Gold et al.19，Chui和Rangarajan9的工作，这将在第3.4部分讨论。有几种基于空间结构的一小部分要点或界标的方法可以进行形状识别。在几何哈希32中，这些配置用于投票给没有明确解决对应关系的模型。阿米特1等人通过学习有判别力的空间配置关键点来训练识别决策树。Leung35等人，Schmid和Mohr49此外使用在关键点的灰度级的信息以提供更大的辨别力。应该指出，并不是所有的对象都有可分辨的关键点（例如考虑一个圆），单独使用关键点牺牲了在对象轮廓平滑部分可利用的形状信息。2.2 基于亮度的方法基于亮度（或外观）的方法提供了一个基于特征的方法的互补。与其侧重于咬合轮廓的形状或其他提取的特征，这些方法在对象的可见部分直接使用灰度值。人们可以在两个框架之一使用亮度信息。在第一类中，我们有方法使用灰度值来明确地对应关系/对齐。Yuille61提出了一个非常灵活的方法，特定种类变换的不变性可以构造成衡量模型的相似性，但当通过梯度下降搜寻时，它需要人类设计的模板和对初始化的敏感性。Lades31等人使用弹性图匹配，这种方法涉及基于高斯衍生以局部描述符形式的几何和光学特性。Vetter59等人和Cootes10等比较亮度值，但是首次尝试使用密集的对应关系领域变形到另一个图像。第二类包括没有明确找到对应关系的建立分类的方法。这种方法，依赖于一个有足够的例子的学习算法获得相应的不变性。在人脸识别领域，特别是在概率框架下使用，采用主成分分析（PCA）5456，获得了好的效果。Murase和Nayar将这些想法应用到3D物体识别。一些作者已经在基于外观的形状匹配框架下应用有判别力的分类方法。 3 带形状上下文的匹配在我们的方法中，我们把一个对象作为一个点集（可能是无限的），我们假设物体的形状基本上是由其点的一个有限子集捕获。实际上，一个形状可用其内部或外部轮廓采样点的离散集合来表示。这些可获得边缘探测器发现的边缘像素的位置，已给我们一套n个点，p=p,p, pR。他们不需要，通常不会对应关键点，如极大地曲率或拐点。我们宁愿样品形状大致均匀间距的，虽然这也不是关键。图3a和3b显示两个形状的采样点。假设轮廓分段光滑，只要挑选的n足够大，我们可以如愿得到一个良好的逼近底层的连续形状。3.1 形状上下文对于第一个形状上的每一个点p，我们要在第二个形状上找到最佳匹配点q，这是一个类似立体的对应问题。经验也表明，如果使用丰富的局部描述符号，例如，灰度窗口或滤波器输出的矢量27，而不是仅仅是单个像素的亮度或边缘的位置，匹配更容易。丰富的描述符减少模棱两可的匹配。作为一个重要的贡献，我们提出了一个新的描述符，形状上下文，可以在形状匹配中发挥这样的作用。考虑从始发点到形状所有其他采样点的向量。这些向量表达了相对参考点的整个形状的配置。显然，这n-1个向量是一个丰富的描述，因为n变大，形状的表示形式越确切。作为形状描述符，全套的向量过于详细，因为在一个类别中形状和采样的表示形式可能会有所不同。作为一个更强大、紧凑且有高度判别力的描述符，我们确定相对位置分配。对于形状上的一个点p，我们计算出余下n-1个点的相对坐标粗的直方图h， . (1)这个直方图被定义为点 p的形状上下文。我们使用统一的2维对数极坐标箱，使得附近样本点的位置描述符比更远样本点的位置描述符更为敏感。图3c就是一个例子。图3.形状上下文计算和匹配。（a）和（b）采样两个形状的边缘点。（c）计算形状上下文的对数极坐标直方图图解。我们是有5种log r和12种。（d）(e)(f)在（a）（b）中以标记的采样点的形状上下文范例。每个形状上下文是一个以参考点为原点，测量其余点的对数极坐标坐标系直方图。（暗=大值）注意和形状上下文的视觉相似性，这用于两个形状上相对相似点的计算。作为对比，的形状上下文完全不同。（g）对应使用二分匹配，由直方图之间的x距离定义成本。考虑第一个形状上的点p和第二个形状上的点q。设C=C（p，q）表示符合这两点的成本。由于形状上下文作为直方图代表的分布，很自然地使用x检验统计： ,这里，h(k)和h(k)分别表示p和q的K-bin正则化直方图。匹配点的成本可以包括一个在点p和q基于局部外观相似性的额外项。当我们比较的形状来自灰度级图像而不是线条图形时，这是特别有用的。例如，可 以添加以p和q为中心的小灰度曲线之间的基于归一化相关分数的成本，点p和q处滤波器输出向量之间的距离，点p和q之间切线方向的不同，以此类推。选择这个外观相似项依赖于应用，由必要的不变性和鲁棒性要求驱动，例如，不同的照明条件使依赖于灰度的亮度值冒险。3.2 二分图匹配鉴于所有成对的第一个形状上的点p和第二个形状上的点q的成本集，我们想尽量减少匹配的总成本， (2)受约束的匹配是一对一的匹配，即，是一个排列。这是一个平方配置（或加权二部图匹配）问题的实例，使用Hungarian方法42可以在时间复杂度O(n)内解决。在我们的实验中，我们使用更有效地算法28。配置问题的输入是一个包含C条目的平方成本矩阵，结果是使式（2）最小化的一个排列。为了有强大的离群值处理能力，在匹配成本恒定的情况下，为每个点添加“虚拟”点集。在这种情况下，不论有没有真正匹配的比更小的成本，一个点将被匹配到一个“虚拟”。因此可视为一个门槛异常检测参数。同样，当两个形状上的采样点数目不同时，成本矩阵可通过给点数目较少的形状增加虚拟节点来创造。3.3 不变性和鲁棒性一个匹配的方法应为1）缩放和平移不变性2）小几何变形、闭塞和存在离群值的鲁棒性。在些应用中，可能要完成旋转不变性，或者甚至全组的仿射变换。我们现在用这些标准来评估形状上下文匹配。平移不变性是形状上下文内在的定义，因为所有的测量是对对象上的点采取的。为实现模型的不变性，我们用形状上n对点之间的平均距离归一化径向距离。由于形状上下文是极为丰富的描述符，他们本质上对形状上的部分小扰动不敏感。虽然我们这里没有理论保证，小的非线性变换，闭塞和存在离群值的鲁棒性在第4.2部分被通过实验评估。在形状上下文框架，如果这是应用需求的，我们可以提供完整的旋转不变性。取代使用绝对框架计算每个点的形状上下文，我们可以使用相对框架，基于将每个点的切向量当做正x轴。这样，参照系根据切线角度转动，结果是一个完全旋转不变描述符。在附录A中，我们在实验上证明了这一点。应该强调，在许多应用中，完全的不变性妨碍识别性能，例如，区分6、9时，旋转不变性将会完全不恰当。另一个缺点是，许多点不会有明确界定的或可靠地切线。此外，如果不是在同一坐标系测量，许多局部外观特征将失去辨别力。附加到离群值的鲁棒性，可以通过从它的形状上下文计算中排除估计离群值来获得。更具体地说，考虑一个被贴上给定迭代的点集。我们提供这些“隐形”的点，不允许它们为直方图做出任何贡献。但是，我们仍然分配给他们形状上下文，考虑到只有周围内层的点，使它们在以后的迭代中有机会作为内层再度出现。3.4 相关工作在这个一般设置中，关于形状对应的最综合的工作是Gold等人19和Rangarajan9的工作。他们开发了一个迭代优化算法，以确定点对应关系和连带的底层图像转换，通常假设一些通用转换；类，如仿射或薄板样条。最小化的成本函数是第一个形状上的点和转换的第二个形状之间的欧式距离的总和。这将产生一个鸡和蛋的问题：只有当至少有一个形状的粗校准，距离才有意义。联合估计的对应关系和形状转换导致一个难的高度非凸优化问题，这用确定性退火19可以解决。形状上下文是一个非常有判别力的点描述符，通过将全部形状信息纳入本地描述符来促进简单和可靠地对应关系恢复。据我们所知，形状上再问和其用于2D形状匹配是新颖的，在过去的工作中关系最密切的想法是约翰逊和赫伯特 26在范围图像的工作。他们提出了一个表示3D点的致密匹配云，被称为“自旋图像”。自旋图像是一个2D直方图，由在一个平面上旋转的对象表面的法线向量和计数下跌在平面内的点个数组成。由于这个平面的规模相对较小，由此产生的有特征的符号不如作为用于恢复对应关系的形状上下文内容丰富。然而这个特性，可能有额外的鲁棒性闭塞的权衡。另一项相关的工作，Carlsson8为表征局部形状配置，利用了秩序结构的概念。在这项工作中，点和形状的切线之间的关系用于恢复对应关系。4 建模转换提供有限的两个形状的点之间的对应关系集，就可以得到一个平面转换估计，可以用来将任一点映射到另一个形状。这个想法由图2 中扭曲的网格线说明，这里指定的对应关系包括少量的标记点，如眼中心，背鳍的尖端等，并且T延伸到任意点的对应。我们需要从一个合适的转换家系选择T。一个标准的选择是仿射模型，即 (3)一些矩阵A和一个平移偏移向量o参数化所有允许转换集。然后，最小二乘解=(,)可通过以下获得 , (4) , (5)其中，P和Q包含P和Q的齐次坐标，即 . (6)这里，Q代表Q的伪逆。在这个工作中，我们大多使用薄板样条（TPS）模型1437，这通常用于较灵活的坐标转换。Bookstein6发现它可以高效模拟生物形式的变化。Powell应用TPS模型以恢复曲线44之间的转换。薄板样条是三次样条的2D推广。TPS模型包括作为特殊情况的仿射模型，其正则化的形式将在下面讨论。现在，我们将提供TPS模型的一些背景资料。我们从一维差值问题开始。让v表示在平面上相应位置p=（x,y）的目标函数值，其中i=1,2,n。特别的，我们将设置v等于x和y以反过来为每个坐标获取一个连续的转换。我们假定位置（x,y）全都不相同而且不共线。TPS插值函数f(x,y)最大限度的减少弯曲的能量并且有以下形式：,其中核心函数U（r）被定义为U(r)=rlog r且U(0)=0。为了使f(x,y)的二阶导数平方可积，我们需要 and . (7)连同插值条件f(x,y)= v,将生成TPS系数线性系统： (8)其中，K=U（）,P的第i行是（1，x,y），w和v是分别从w和v形成的列矢量，a是含有元素a，a和a的列向量。我们将用L表示这个系统（n+3）*(n+3)的矩阵。讨论，例如，在44，L是奇异地，我们可以. (9)通过反转L找到解决方法。如果我们用A表示左上部L的n*n块，然后可以表示：4.1 正则化和标度行为当在指定的值v处有噪声，不妨通过正则化放宽确切的插值要求。这通过最小化下式完成 . (10) 正则化参数是一个正标量，控制平滑量；=0的极限情况将减少确切的插值。1860表明，在正则化情况下，我们可以通过用K+I替代K来解决TPS系数，其中I是n*n的恒等矩阵。值得注意的是，高度正则化的TPS模型简并最小二乘仿射模型。为解决数据集上的依赖关系，假设用（x,y）（x,y）分别替代（x,y）（x,y）,积极地常数。然后，它表明，如果改为，最优薄板样条的参数w,a和I不受影响。这个简单的缩放行为表明了正则化参数的归一化定义。让再次代表该点的规模，设置为集中的两个点之间的平均边长度的估计。然后，我们可以通过和定义一个独立于规模的正则化参数，有简单的关系=。我们使用两个单独的TPS函数来进行坐标变换建模， （11）其中产生的位移场，从第一个图像的任何位置映射到第二个图像的插值位置。在许多情况下，对应关系的初步估计包含了一些错误，这可能会降低转换估计的质量。为了解决这个问题，可以迭代对应关系恢复和估算的步骤。我们通常使用固定数量的迭代，通常是三个，但在大规模的实验中可能有更精细的计划。不过，实验性经验表明算法的性能独立于详细信息。图4是迭代算法的一个示例。4.2 经验鲁棒性评估为了研究我们提出的方法的鲁棒性，我们进行了如9中所述的合成点匹配实验。实验分为三个部分的设计来衡量变形、噪声和离群值的鲁棒性（后来的每个测试都包括一个“适度”变形量）。在每个测试中，我们用含上述扭曲的模型点集创建一个“目标”点集，见图5。然后，我们运行我们的算法，在模型和目标之间找到最佳的翘曲。最后，性能通过计算扭曲模型和目标之间的平均距离来量化。结果如图6所示。在测试离群值实验最具挑战性的部分，我们的方法表明鲁棒性甚至达到了100%的离群值对数据的比例水平。在实践中，我们将需要只在一个完整的识别系统中探索的闭塞和分割错误的鲁棒性，但这些实验至少提供一些指导。4.3 计算需求我们实行定期的奔腾 III/500 MHz 工作站，一个包括3个周期的100个采样点的形状上下文的计算、建立全部的匹配矩阵、二分图匹配、TPS系数计算和图像变形的比较大约需要200毫秒。运行时间主要是受控于每个形状的采样点数目，与二次、三次缩放行为之间表现的算法的大多数组件。一旦形状大致对齐，整个使用稀疏表示，复杂性可以接近线性。图4 应用于图1中的匹配过程图示。第一行：1级迭代，底部行：5级迭代。左列：估计相对于转换模型的对应关系，用切向量显示。 中间列：显示相对于未转换模型的估计对应关系。右列：基于当前对应关系的模型转换结果，这是下一次迭代的输入。网格上的IR说明插值的转换，在这里，我们使用一个=1的正则化的TPS模型。5 目标识别和原型选择给定形状之间的差异性测量，我们即将对其进行精确地测量，我们可以继续把它应用于对象识别的任务。我们的方法属于基于原型的识别。在这一框架下，由Rosch48等人率先，类别由理想的例子来代表，而不是一套正式的逻辑规则。作为一个例子，麻雀可能是鸟类别的原型，不太可能的选择是企鹅。原型的想法允许软类别的成员资格，这意味着在一些适当定义的相似性空间，一旦移动的远离理想例子，与原型的关联便脱落。当离原型足够远时，距离就变得毫无意义，但最有可能接近一个不同的原型。作为一个例子，我们可以说好或马马虎虎的红颜色的例子，但当颜色变得足够不同，相异饱和度水平会达到一些最大水平，而不是无限期的继续。基于原型的识别很容易转化为使用多个存储的试图的最近邻方法计算框架。当训练集中的例子n趋于无穷大，最近邻分类器具有1-NN错误汇聚为一个不大于E的2倍的值的属性，其中E是贝叶斯风险（对于K-NN，K趋于无穷大，K/n趋于0，错误趋于E）。这是有趣的，因为它表明了最近邻分类器是渐进最优的，属性不具有几种更为复杂的技术。当然，在实践中，重要的是小n的性能，这给了我们一个比较不同的相似性/距离措施的方法。5.1 形状距离在本节中，我们进行精确地形状距离的定义，并将其应用到几个实际问题。我们用正则化的TPS和三个形状上下文匹配迭代和TPS重估。匹配后，我们估计形状距离的加权和的三个方面：形状上下文距离，图像外观距离和弯曲能量。我们衡量形状P和Q之间的最佳匹配点对称形状上下文匹配的成本总和的形状上下文距离，即, (12)其中，T()表示TPS 形状转换的测量。图5.根据Chui和Rangarajan9，经验鲁棒性估计的测试数据。在第一列显示模型的点集。2-4列分别显示目标点集的变形，噪声和离群点测试。图6.比较我们的结果（）与Chui和Rangarajan的结果（*），分别迭代鱼和中文字符的最近点（）。误差线显示100个随机实验的错误的标准偏差。这里，我们使用了=1.0情况下的5次迭代。在变形和噪声测试中没有添加虚拟节点。在离群值测试中，虚拟节点被添加到模型点集中，这样节点总数和目标是相同的。在这种情况下,的值不影响解决方法。在许多应用中有额外的我们的形状概念不捕获的外观信息可用，例如，在灰度图像中的纹理和颜色信息修补周围对应的点。外观信息的可靠性往往由于几何图像扭曲受损。然而，建立图像对应关系和恢复底层2D图像变换后，扭曲的图像可以被扭回成一个正常的形式，从而可以纠正牛武的图像外观。我们使用D(P,Q)表示外观成本，定义为相应的图像点周围的高斯窗口亮度差异平方的总和，, (13)其中，I和I分别表示对应P和Q的灰度级图像。表示一些差矢量偏移，G是一个窗口函数，通常选择高斯，因此强调附近的像素。因此，我们总和窗口中相应点的平方差，得到加权灰度级相似性分数。这个分数是薄板样条变换T已经应用到最好的变形图像对齐后计算的。第三项相当于需要对齐形状的变换的“量”。在TPS情况下，弯曲能量（9）是一种固有的措施（见5）。5.2 原型选择 在基于原型的方法中，关键的问题是：我们应该存储哪些例子？不同的类别需要不同的视图。例如，某些手写体数字比其它的有更多的可变性，如，人们通常认为4比0有更多的变化。在3D对象的类别中，一个领域只需要一个视图，例如，电话电话需要若干视图以捕捉各种视觉外观。这个想法与在30中讨论的“层面”概念有关。现在我们将讨论如何处理原型选择问题。在最近邻分类的文献中，典范选择问题就是所谓的编辑。最近邻的编辑方法的广泛审查可以在Ripley46和Dasarathy12发现。我们已经开发处一种基于形状距离和K-medoids聚类的新颖的编辑算法。K-medoids可以看作是根据数据点限制原型位置的K-means的变形。首先计算所有可能原型之间的成对相似性矩阵。对于一个给定K原型数，K-medoids算法迭代两个步骤：1）对于一个给定的点（抽象）来聚簇一个新原型，集群中的所有元素，通过最小化原型平均距离来选择 2）给定原型集，然后点被重新分配到最近的原型。更正式的是，c(P)表示形状P的（抽象）集群，例如，一些数字1，k表示形状P，p(c)表示相关的原型。这样，我们有一个类映射 (14)和一个原型映射. (15)这里，S和S是所有潜在的形状S的集合的一些子集。通常，S=S=S。K-medoids由迭代两个步骤进行：1、 S类组成原型p(c)2、 为集群中元素的每个类确定一个有代表性的原型图7.MNIST数据集上的手写体数字识别。左边：使用SSD和形状距离（SD）措施的的1-NN分类测试集错误。右边：详细的形状距离的性能曲线，包括结果，用大小15000和20000的训练集。至于K=1,3,5的最近邻的结果显示在半对数-x标尺上。基本上，通过分配每个形状PS到最近的原型解决第一项，因此， （16）对于给定的类，在第二项，基于最小平均相异性选择新的原型，即 （17）由于这两个步骤最小化相同的成本函数， （18）该算法必然收敛到一个（局部）最小。与大多数的聚类方法一样，k-medoids必须要有一个战略来选择k。我们使用一个贪婪的分裂策略选择原型的数量，从每个类别一个原型开始。我们基于相关的整体分类误差来选择集群进行分裂。这将一直持续到整体分类误差低于标准水平。因此，原型是自动分配到不同的对象类，因此，优化使用现有的资源。在6.2部分探讨这一程序在3D对象的一套视图中的应用，并在图10所示。6 案例研究6.1 数字识别在此，我们给出MNIST数据集上手写体数字的结果，其中包括60000训练和10000测试数字34。在实验中，我们使用100个Canny边缘的采样点来代表各数字。当计算二分匹配的C时，我们包括了表示局部切线角度差异的一项。具体地说，我们定义匹配成本为C=（1-）C+C，其中C是形状上下文成本，C=0.5(1-cos(度量切线角度差异，且=0.1。为了识别，我们使用一个K-NN分类器，其距离函数为. (19)式（19）中的权重由训练数据上的一个3000*3000的子集的leave-one-out过程得到了优化。已经比较了MNIST数据集上的近30种算法。这时候公布的最低的测试集错误率是提升LeNet-4的0.7%，每个训练数字有大小为60000*10的合成扭曲的训练集。我们使用20000训练例子和3-NN的错误率是0.63%。图8显示63个错误。如前所述，在最近邻方法的实际应用中最重要的是小n时的性能，这给了我们一个比较不同相似性/距离措施的方法。图7（左），形状距离与SSD（像素亮度值的平方差的总和）相比。图7（右），比较不同K值的分类率。6.2 3D目标识别我们的下一个实验涉及来自COIL-20 数据库40的20种常见的家用物品。每个对象都被放在一个转盘上，并每隔5共拍下72个视图。我们通过为每个对象选择一些等距的视图来准备训练集，剩下的视图用于测试。匹配算法和数字完全相同。回想一下，Canny边缘检测器响应外部和内部的轮廓，因此100个采样点不局限于轮廓的外部边界。图9显示比较使用包括如（19）所示的距离函数D的1-NN和直接使用平方差的总和（SSD）的性能。由于光照下变化不足，SSD在这个简单的数据库上表现非常好。图10所示的是原型选择算法。正如所看到的，视图主要用于类别变异性高的更复杂的类别。图9中标记SC-proto的曲线显示了改善的分类性能，使用这个原型选择策略而不是等距的观点。请注意我们获得了2.4%的错误率，平均每个3维对象只有4个2维视图，多亏了匹配算法的灵活性。图8.用我们的方法，所有错误分类的MNIST测试数字。每个数字上面的文本表示真正的标签和分配的标签后的示例数。图9.使用COIL-20数据集的3D目标识别。比较SSD，形状距离（SD）和与原型视图相对的以k-medoids为原型的形状距离（SD-proto）的测试集错误。对于SSD和SD，我们统一改变了所有对象的原型数量。对于SD-proto，每个对象的原型数量取决于对象内和对象间的相似性。6.3 MPEG7标准的形状轮廓线数据库图10.使用5.2部分描述的算法，为COIL数据集中的两个不同的3维对象选择原型视图。通过这个方法，视图的分配取决于一个对象关于视角的视觉复杂度。我们的下一个实验涉及MPEG-7形状轮廓数据库，特别是核心实验CE-Shape-1的B部分，衡量基于相似性恢复25的性能。该数据库包括1400个图形：70个形状类别，每个类别20个图像。使用所谓的“靶心测试”衡量性能，其中每个图像作为一个查询，然后在前40个匹配中计数正确的图像。图11.MPEG7数据库中三个不同类别的形状的例子。由于本实验涉及复杂的形状，样本数量从100增加到300。在某些类中，形状出现了旋转和翻转，我们通过使用一个修改后的距离函数来解决。参考形状R和一个查询形状Q之间的距离dist(R,Q)定义为，其中，R，R和R表示R的三个方面：不变，垂直翻转和水平翻转。这些变化的地方，但以其它的方式使用MNIST数字实验中同样的方法，我们获得76.51%的检索速度。目前公布的最佳性能由Latecki33等人实现，检索率为76.45%，随后是Mokhtarian等的75.44%。6.4 商标检索商标在视觉上往往最好描述它们的形状信息，而且在许多情况下，形状提供了唯一的信息来源。自动识别商标侵权是有趣的工业应用，因为目前的艺术商标根据Vienna编码大致分类，然后再根据它们的感知相似性手动分类。即使形状上下文匹配不提供商标相似性问题（其他潜在的线索是文字和纹理）的完整解决方案，但它仍可以很好的说明我们的方法捕捉形状相似性的本质的能力。在图12，我们描述了300个商标的数据库的检索结果。在这个实验中，我们依靠式（3）给定的仿射模型，并且在前面的例子中，我们使用了300个样本点。我们尝试用8个不同的查询商标，每个数据库至少包含一个潜在的侵权。我们描绘了前4个命中以及它们的相似性得分。可以清楚的看到，潜在的侵权行为很容易发现，尽管实际形状有很大变化，在队伍的顶端以最相似的显示。它已被手工验证，没有视觉上类似的商标被错过。图12.基于300个不同的真实世界的商标数据库的商标检索结果。我们使用仿射变换模型、加权组合的形状上下文相似度D和局部切线方向差异的总和。7 总结我们已经介绍来了一个形状匹配的新方法。这个方法的主要特点是形状相似性估计和基于一个新描述符-形状上下文-的对应关系的估计。我们的做法简单而且易于应用，还提供了一个点集的丰富描述符，大大提高了点集的登记、形状匹配和形状识别。在我们的实验中，我们已经证明了几种常见的图像变换，包括现实世界对象的显著3D旋转图13.Kimia数据集：每一行显示一个不同对象类的的一个差异实例。性能是以有正确的分类标签的最接近匹配的数量来衡量。注意为了有效地识别，几个类别需要旋转不变匹配。用我们的方法，所有排名第一的最接近匹配是正确的。排名第二的匹配，8个中发生1个错误。排名第三的匹配，2对8,8对1和15对17出现混乱。附录A完整的旋转不变识别本附录中，我们说明在我们的方法中使用的相对框架，一种为获得完整的旋转不变性的手段。为证明这个想法，我们用Sharvit53等人提供的数据库，如图13所示。在这个实验中，我们使用n=100采样点，如上文所述，计算形状上下文时，我们使用相对框架（3.3部分）。本实验及本文中的所有其他实验，我们使用5箱范围从0.125到2的log(r)和12个等距径向箱。没有用任何的转换模型。作为一个相似性得分，一次迭代后，我们使用匹配成本函数，没有转换步骤。因此，这个实验式专门设计的，纯粹是为了评估在面对旋转时形状描述符的能力。在53和17，作者通过第1、2、3最近邻属于正确分类的数目来总结他们对此数据集的结果。我们的结果是25/25，24/25，22/25。在53和17，分别引用的结果是23/25，21/25，20/25和25/25，21/25，19/25。附录B抽样考虑在我们的方法中，形状由一组来自对象内部和外部的轮廓点来表示。应用中，在灰度图像上运行一个边缘检测器，并选择发现的边缘像素的一个子集。选择内容可能会随机均匀，但我们发现它在确保样本点之间有确定的最小距离方面有利，这可以确保沿轮廓采样在某种程度上是统一的。（这相当于从一个硬核模型45采样的过程）由于采样点都随机和独立的来自这两个形状，匹配算法的结果中必然有抖动噪声，这可发现两组采样点之间的对应关系。然而，当两个形状间的转换以正则化的薄板样条函数来估计，此抖动的影响将消失。谢辞这项研究受到美国军队研究办公室（ARO）DAAH04-96-1-0341支持，数码图书馆授予IRI 9411334、美国全国科学基金会研究生奖学金S.Belongie，由德意志德国研究基金会授予PU-165/1。3和2提到了部分的这个工作。作者要感谢H.Chui和A.Rangarajan，因为他们提供了4.2部分所使用的合成的测试数据。我们还要感谢他们和伯克利分校计算机视觉组的成员，特别是A.Berg，A.Efros,D.Forsyth，T.Leung，J.Shi和 Y.Weiss，因为有用的讨论。作者在加利福尼亚大学伯克利分校计算机科学部电气工程系进行的这项工作。