Normalized Cuts and Image Segmentation_Jianbo Shi and Jitendra Malik_规范化切割与图像分割.pdf

规范化切割与图像分割 摘要：我们提出了一种新的方法来解决视觉中的感知分组问题。这种方法的目的在于提取图像的总体印象，而不关 注局部特征或它们在图像数据中的一致性。我们将图像分割视为图的分割问题，并为分割图形提出了一个新的总体 准则——规范化切割。规范化切割准则既权衡了不同分组之间总体的差异，也权衡了分组之内的相似。我们说明了 一个基于广义特征值问题的高效计算方法可以用来最优化这个准则。我们已经将这个方法运用于静态图像和运动序 列的图像分割，结果令人鼓舞。 索引词：分组，图像分割，图分割 1 简介 将近75 年以前，韦特海默指出了视觉中感知分组和组织的重要性，并给出了几种关键因素，如相似点、邻近 性和良好连续性，这些都通往视觉分组。然而，时至今日，很多感知分组中的计算问题仍然没有得到解决。在本文 中，我们具体针对图像分割问题提出一种解决方法的总体框架。 图像域I 可以有多种分割方法，而我们又该如何选取正确的方法呢？我们需要考虑两个方面。第一，正确答案 不一定是唯一的。贝叶斯观点是适用的——在以往世界知识的背景下，存在着多种解释。难点当然在于如何具体说 明以往世界知识。其中一些是低级的，比如亮度、颜色、纹理或运动的一致性，而另一些同样重要的是关于物体或 物体模型的中级或高级的对称性。第二，分割是内在分级的。因此，有必要考虑一个与分级分割相一致的树形结构， 而不是简单的 “平面”分割。 这就说明基于低级线索的图像分割不能也不应该用于寻求完全的最终的“正确”的分割。运用低级的亮度、颜 色、纹理或者运动属性的相干性的目的在于寻求分级分割。中级或高级知识可以用来确认这些分组或者为深入考虑 选取一些分组。这些考虑应该能够得到更深层地再分配或分组。关键是在于图像的分割是从上而下完成的，而不像 一个画家在绘画时首先描绘主体部分再深入细节一样。 以往的相关文献中，聚类、分组和图像分割问题是巨大的。聚类群落给我们提供了聚集的可分的算法；在图像 分割中，我们有基于范围的合并和分离算法。我们倡导的分级分割方法构造了一个树——系统树图。这些思想来自 于二十世纪70 年代（或更早），80 年代开始运用马尔可夫随机场（MRF ）和变分公式。MRF 和变分公式也暴露了 两个基本问题： 1. 将要最优化的准则是什么。 2. 有没有高效的算法来实现最优化。 很多准则都因为无法运用高效的算法找到它的最小值而被放弃——贪心法或梯度下降法不能使这些高维度非线性 问题实现整体最优化。 我们的方法大部分与图论中的分组相关。任意特征空间中的点由一个加权无向图G= （V,E ）表示，其中的节点 是特征空间中的点，每对节点之间都有边。每边上的权重w （i，j ）是节点i 和j 之间相似性的函数。 在分组时，我们将顶点分为不相交的集合V ,V ,…,V , 使得在V 内各顶点之间的相似性最大，而不同的集合 1 2 m i V 和V 之间相似性最低。 i j 为了分割图，我们提出了两个问题： 1. 好的分割精确准则是什么。 2. 如何高效地计算得到这个分割。 在图像分割和数据分类社区中，很多先前的研究中运用了最小生成树和有限邻近集合的方法。虽然运用了高效 的计算方法，但分割准则大都基于图的局部特征。由于感知分组目的在于从图像场景中提取总体印象，就像我们以 前看到的，这个分割准则往往不能达到这一主要目的。 在本文中，我们提出了一个新的图论的准则——规范化切割，用于衡量一个图像分割的好坏。我们在第2 部分 中介绍和证明这个准则。这个准则的最小化可表示为广义特征值问题。可以运用特征向量为图像构造好的分割，而 且这个过程可以根据需要持续运用递归（2.1 节）。第3 部分给出了该算法各个步骤的详细解释。在第4 部分中给出 了实验结果。规范化切割准则的公式表示和最小化大量借鉴了频谱图论 （第5 部分）。其与计算机视觉研究的关系 将在第6 部分讨论。与基于特征向量分割方法的比较将在6.1 中给出。我们在第7 部分中得出总结。 2 按照图分割的分组 一个图G （V,E ）可以简单地去掉两部分之间的边，从而被分为两个不相交的集合A,B 。A ∪B=V ，A ∩B= Φ。 这两个部分之间的分离程度可由被去掉的边的权重来计算。运用图论的语言，这称为cut ： cut(A,