normalized cuts and image segmentation翻译.doc

规范化切割和图像分割 摘要：为解决在视觉上的感知分组的问题，我们提出了一个新的方法。我们目的是提取图像的总体印象，而不是只集中于局部特征和图像数据的一致性。我们把图像分割看成一个图形的划分问题，并且提出一个新的分割图形的全球标准，规范化切割。这一标准衡量了不同组之间的总差异和总相似。我们发现基于广义特征值问题的一个高效计算技术可以用于优化标准。我们已经将这种方法应用于静态图像和运动序列，发现结果是令人鼓舞的。 1简介 近75年前，韦特海默推出的“格式塔”的方法奠定了感知分组和视觉感知组织的重 要性。我的目的是，分组问题可以通过考虑图（1）所示点的集合而更加明确。 通常人类观察者在这个图中会看到四个对象，一个圆环和内部的一团点以及右侧两个松散的点团。然而这并不是唯一的分割情况。有些人认为有三个对象，可以将右侧的两个认为是一个哑铃状的物体。或者只有两个对象，右侧是一个哑铃状的物体，左侧是一个类似结构的圆形星系。如果一个人倒行逆施，他可以认为事实上每一个点是一个不同的对象。 这似乎是一个人为的例子，但每一次图像分割都会面临一个相似的问题—将一个图像的区域D划分成子集Di会有许多可能的划分方式（包括极端的将每一个像素认为是一个单独的实体）。我们怎样挑选“最正确”的呢？我们相信贝叶斯的观点是合适的，即一个人想要在较早的世界知识背景下找到最合理的解释。当然，困难在于具体说明较早的世界知识—一些低层次的，例如亮度，颜色，质地或运行的一致性，但是关于物体对称或对象模型的中高层次的知识是同等重要的。 这些表明基于低层次线索的图像分割不能够也不应该旨在产生一个完整的最终的正确的分割。目标应该是利用低层次的亮度，颜色，质地，或运动属性的一致性继续的提出分层分区。中高层次的知识可以用于确认这些分组或者选择更深的关注。这种关注可能会导致更进一步的再分割或分组。关键点是图像分割是从大的图像向下进行，而不是像画家首先标示出主要区域，然后再填充细节。 先前关于聚类，分组，图像分割问题的文献是很多的。聚类社会为我们提供了聚合和分裂算法；在图像分割中我们有基于区域合并和分割算法。我们提倡的层次分裂方法会产生一个树形图。尽管许多观点都要追溯到20世纪70年代或更早，20世纪80年代带来马尔可夫随机域和变分公式的应用。马尔可夫随机域和变分公式也暴露出两个基本问题：(1)要优化的准则是什么？（2）是否有有效的算法进行优化？许多有吸引力的准则已经注定无法找到一个有效的算法，找出它的最小贪婪或者梯度下降方法，无法找到找到高维非线性问题的全局优化。我们的方法与图的理论分组制定最有关。任意特征空间的点集可以表示为加权无向图G=（V，E），特征空间的点是图的节点，每对双节点之间形成一个边缘。每个节点的权重，w(i,j),是i和j两个节点之间的功能相似性。 在分组中，我们将定点集分割成不相交的点集V1,V2,…Vm，在某种程度上，在Vi点集中的顶点相似程度较高，不同点集ViVj 的顶点的相似程度低。 分割一个图像，我们必须提出以下的问题： 好的分割应该有什么标准？2.这样的分割怎样有效的计算？ 在图像分割和数据聚类社区，出现了许多前期工作，这些前期工作利用最小 生成树或有限邻域集合的变化。虽然那些使用了高效的计算方法，大部分使用的分割准则都是基于图形的局部特征。因为感知分组要提取场景的总体印象，正如我们前面所看到的，这一分割准则达不到这一主要目的。 在本文中，我们提出了一个新的图形理论标准，即规范化切割，用于测量图像分割的优良度。我们在第二部分介绍和验证这一标准。这一准则狭义上可以认为是一个广义特征值问题。特征向量可以用于构建良好的图像分区，这一过程可以按需要持续递归（3节）。在第4部分，我们会展示实验结果。规范化切割准则的制定和最小化借鉴了许多的理论和实践结论，这些结论来源于数据分析和理论计算科学社区。第5部分会讨论频谱分割问题的前期工作。我们将会在第6部分做出总结。 2.图形分割分组 图形G=（V，E）可以分割成两个不相交的集合A，B，A∪B=V，A∩B=?,只需一出连接两个集合的边缘。这两部分的相似度可以通过已经被移除边缘的权重计算。在图像理论语言中，它被称为切割： （1） 对一个图形的最优分割是将切割值降到最低。尽管这样的分割有一个指数，找到图形的最小切割值是一个值得研究的问题，并且存在有效的算法可以解决这一问题。 吴和莱希提出了基于这个最小切割准则的一个聚类方法。特别是，他们将一个图像分割成K子图，从而子分组的最大切割值可以最小化。这一问题可通过递归查找平分现有部分的最小切割值得到有效的解决。在他们的研究中，这一全局优化准则可以用于产生好的分割图像。 图2 然而，他们在研究中还注意到，这一