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 的顶点的相似程度低。
分割一个图像，我们必须提出以下的问题：
1. 好的分割应该有什么标准？2.这样的分割怎样有效的计算？
在图像分割和数据聚类社区，出现了许多前期工作，这些前期工作利用最小
生成树或有限邻域集合的变化。虽然那些使用了高效的计算方法，大部分使用的分割准则都是基于图形的局部特征。因为感知分组要提取场景的总体印象，正如我们前面所看到的，这一分割准则达不到这一主要目的。
在本文中，我们提出了一个新的图形理论标准，即规范化切割，用于测量图像分割的优良度。我们在第二部分介绍和验证这一标准。这一准则狭义上可以认为是一个广义特征值问题。特征向量可以用于构建良好的图像分区，这一过程可以按需要持续递归（3节）。在第4部分，我们会展示实验结果。规范化切割准则的制定和最小化借鉴了许多的理论和实践结论，这些结论来源于数据分析和理论计算科学社区。第5部分会讨论频谱分割问题的前期工作。我们将会在第6部分做出总结。
2.图形分割分组
图形G=（V，E）可以分割成两个不相交的集合A，B，A∪B=V，A∩B=Ø,只需一出连接两个集合的边缘。这两部分的相似度可以通过已经被移除边缘的权重计算。在图像理论语言中，它被称为切割：
（1）
对一个图形的最优分割是将切割值降到最低。尽管这样的分割有一个指数，找到图形的最小切割值是一个值得研究的问题，并且存在有效的算法可以解决这一问题。
吴和莱希提出了基于这个最小切割准则的一个聚类方法。特别是，他们将一个图像分割成K子图，从而子分组的最大切割值可以最小化。这一问题可通过递归查找平分现有部分的最小切割值得到有效的解决。在他们的研究中，这一全局优化准则可以用于产生好的分割图像。 图2
然而，他们在研究中还注意到，这一最小切割准则有利于切割图形中的孤立节点，这并不奇怪，因为（1）中定义的切割值随着两个分割部分的边缘数量而增加。图2说明了一个这种情况。假设边缘权重与两个节点之间的距离成反比，我们看到划分出节点n1或n2的切割值很小。事实上，任意划分右半部分孤立节点的切割值要小于将节点划分成左右两半的切割值。
为了避免切割成小集合中出现的不自然的偏见，我们提出了解除两分组关联的新方法。不是只看连接两部分的权重值，我们的方法是计算作为连接到图表中的所有节点的总的边缘的一小部分的切割成本。我们称解除关联的措施为规范化切割（Ncut）：
（2）
是从A中的节点到图形中的所有节点的总连接，assoc(B,V)类似定义。有了解除分组关联这一定义，划分小孤立点的切割值将不再有小的规范化切割值，因为切割值几乎会占从小集合到所有其他节点的所有连接的很大比例。图2所示情况，我们看到节点n1的切割值等于到该节点的总连接。相同情况下，对于一个给定的分割，我们可以定义一个组内规范化关联的测量值：
（3）
assoc(A,A)和assoac(B,B)分别是A和B内部边缘连接节点的全部权重。我们再次看到这是一个不偏倚的方法，这反映了组内节点互相连接的紧密程度。
一个分区的关联和非关联的定义的另一个重要特征是它们是自然相关的：

因此，在我们的分组算法中寻求的两个分组准则，使组内非关联最小化和使组内关联最大化，实际上是相似的，可以同时满足。在我们的算法中，我们将会使用规范化切割为分割准则。
已经定义了我们想要优化的图形分割准则，我们将要介绍这样的优化准则怎么高效的计算。
2.1 计算优化准则
给定一个分区的节点图V，将其分为A，B两个集合，x是N=|V|三维指示向量，节点i在A内时xi=1，否则等于-1。是从节点i到其它节点的总连接。有了x和d的定义，我们可以将Ncut(A,B)重新写为：

D是N×N的对角矩阵，d在对角线上，W是N×N的对称矩阵，W(i,j)=Wij,,i是N×1向量。和分别是xi>0和xi《0的指示向量，我们可以重写Ncut（x）：

令我们可以继续化简上面等式：
删除最后的常数项，在这种情况下等于0，我们得到：
令由于γ=0，式子变为：

令容易得到： （4）
由于，并且
将我们得到的放在一起： （5）
条件是。
上述表达式是瑞利商。如果y可以取实际值，我们可通过求解广义特征值系统使（5）最小化， （6）
然而，在相应的指标向量x条件下，对于y我们有两个约束。第一个是。我们可以得到广义特征系统的解决方案可以满足这一约束。我们将这样做，首先将（6）式转变成一个标准化特征系统，在此相应的条件已满足。将（6）式写为：, (7)
人们很容易验证是式（7）的特征向量，特征值是0。而且，是对称半正定，由于（D-W）也被称为拉普拉斯矩阵，是半正定矩阵。因此zo实际上是式（7）最小的特征向量，并且式（7）所有的特征向量是正交的。特别是，第二个最小特征向量z1与zo正交。将这种情况应用于广义特征系统（6），我们得到：（1）y0=（0，i）是最小的特征向量，（2），y1是（6）的第二个最小特征向量。
现在，回想起关于瑞利商的一个简单事实:使A是一个对称矩阵。X与j-1个最小特征向量x1，……,xj-1是正交的，在这一约束下，商通过下一个最小特征向量xj最小化，它的最小值是对应的特征值λj。
结果，我们得到： （8）
最终， （9）
因此广义特征系统的第二个最小特征向量是解决规范化切割问题的真正方案。解决我们最初的问题并不重要的唯一原因是对于y的第二个约束，即yi具有两个离散值，并不能得到自动满足。事实上，放宽限制使优化问题易处理放在首位。在第三部分，我们将展示如何将这一有价值的解决方案转变成离散的形式。
类似的说法表明，第三个最小特征向量是优化分割前两部分的有价值的解决方案。事实上，这种论点表明，利用每次的特征向量和下一个最小特征向量，可以细分现有的图形。然而，在实际中，从实际价值解决方案到离散价值解决方案的逼近误差随着每一个特征向量的使用而积累，并且每一个特征向量必须满足互相正交的约束，这种基于更高的特征向量的解决方案就变得不可靠。最好是重新单独解决每个子图的分割问题。
总之，我们建议利用规范化分割准则进行图形分割，并且，我们已经说明这一准则是怎样通过解决广义特征值问题而得到高效的计算。
3.分组算法
像我们之前看到的，（6）中的广义特征系统可以转化为标准特征值问题。解决所有特征向量的标准特征值问题需要O（n3）个步骤，n是图形的节点数。对于图像分割应用这是不可行的，其中n是图像中的像素数。幸运的是，我们的图像分割具有以下特征：（1）图形经常只是局部连接，由此产生的特征系统非常稀松，（2）图形分割只需少数的高特征变量，（3）特征向量的精度要求低，往往只需正确的符号位。我们问题的这些特殊属性可以被称为lanczos方法的特征求解器充分利用。Lanczos算法的计算时间为O(mn)+O(mM(n)),其中m是矩阵相量运算需要的最大数值，M(n)是矩阵向量计算的成本。在（D-W）矩阵稀松的情况下，矩阵向量只需要O(n)时间。m值取决于许多因素。在我们图像分割的实验中，m值一般小于。
计算特征向量时，我们可以利用第二个最小特征向量将图形分割成两部分。理想情况下，特征向量只有两个离散值，值得迹象会告诉我们怎样分割图形。让本人，我们的特征向量可以取连续的值，我们必须选择一个分割点将图形分为两部分。选择这一分割点有许多方法。可以取0值或中间值作为分割点，或者寻找一个分割点使结果有一个最合适的Ncut(A,B)值。我们在工作中采取了后者。现在，研究工作是检查等间隔的可能的分割点和计算Ncut最优值。在我们的实验中，特征向量的值一般分离，即使L值很小，这种选择分割点的方法也很可靠。
图形被分成两部分后，我们可以在两个分区第贵的运行我们的算法。或者等价的，我们可以利用其他高级特征向量的特殊属性，就像前面介绍的基于那些特征向量分割图形。当Ncut值超过一定限制时递归停止。
我们也对分割加了一个稳定准则，有一些类似于边缘检测的定位准则。我们可以通过一个准则区分真正的边缘与具有高梯度阴影的区域，这一准则是在高梯度阴影区域真正边缘位置不同会改变其强度，而在平滑阴影区域时假定边缘位置不同不影响其强度。在目前情况下，如果改变形成切割的图形边缘，Ncut值变化不大，我们将其视为不稳定切割。为了计算这一稳定值，我们围绕优化值改变切割点的值，并且引入两个不同分区，P1=(A1,B1)和P2=(A2,B2)。稳定值是其中。
我们的分组算法可以总结如下：
1.已知一组特征，设置一个加权图G=(V,E)，计算每个边缘的权重，并且将信息汇总到W和D。
2.利用最小特征向量解式的特征向量。
3.通过第二个最小特征向量的特征值划分图形找到切割点，从而使规范化切割值值最小化。
4.通过检查分割稳定性决定现在的划分是否需要细分，并且确保规范化切割值低于指定值。
5.如果有必要对分割部分再划分。
通过这种方法分割组的数量直接受最大规范化切割值的控制。
4.实验
我们已经将分组算法应用于基于亮度，颜色，质地和运动信息的图像分割。在每种情况下，我们通过将每个像素当做一个节点构建图形G=(V,E)，并且定义节点i和j的边沿权重wij为特征相似性术语和空间邻近性术语：
其中X(i)是节点i的空间位置，F(i)是基于强度，颜色，质地信息的节点的特征向量，定义为：（1）在分割点集的情况下，F(i)=1；（2）F(i)=I(i)，强度值，为了分割亮度图像；（3），h,s,v是HSV的值，用于颜色分割；（4），用于质地图像分割。需要注意的是任意节点i和j的权重wij=0已经超过分离的r像素。 图3
我们首先在类似于图2的空间点集合上测试算法。图3说明点集和分割结果。从图中可以看出，标准化切割准则确实可以用我们在第二部分讨论的理想方式切割点集。
图4，5，6是应用分割算法于不同亮度的图像。图4 是又添加噪声的合成图像。图5，6是自然图像。需要注意的是图6 的物体边界不明确，这将会是边界检测不佳。图7是颜色图像的分割，在这些处理中重现灰度。 图4
需要注意的是，在所有的例子中，算法可以提取场景的主要组成部分而忽略小的内部成分的变化。根据需要，递归分割可以用于进一步分解每个部分。
最后，我们用以斑马为背景的自然图像的质地分割的初步结果作为总结，看图8。需要注意的是我们的措施是变化方向的。因此，部分拥有不同条纹的斑马的皮肤应该标为单独区域。
在这些例子中，我们已经分别考虑了基于亮度，颜色和质地的分割。显然这些可以和视差，运动信息结合在一起。

图5
图6

图8
图7
5 相关分割算法
利用特征值问题解决图像分割的
观点最初是在多纳特，霍夫曼和
费德勒的作品中提到的。费德勒
认为的特征向量
的第二个最小特征值可以用于
分割图像。实际上第二个最小特
征值被称为费德勒值，相应的特
征向量是费德勒特征向量。这一
光谱分割的想法已经复兴，并且
通过一些研究者得到进一步发展，
特别是在并行科学计算领域。
在应用于其它领域时，与多做这表明光谱分割放吧确实提供了分割图形的好方法。在这个领域的理论工作集中于切割率和费德勒值之间的联系。区域A的切割率定义为。可以看出费德勒值越小，基于费德勒向量的图像分割会有较好的切割率。我们在2.1的推导表明费德勒向量是问题的解决方法，我们可以称之为平均分割。
尽管平均分割看起来与规范化分割相似，但平均分割没有平均相关这一属性，可以定义为。因此，不可以同时减小非相关和增大组内相关。当我们将所有技术都用于图像分割，范县在实际中规范化分割效果更好。
广义特征值方法通过平衡并行计算机的计算负载而第一次应用于图像分割。
在计算机社区，有一些相关的图像分割方法。吴和莱希利用最小切割准则进行分割。Cox寻求减小，其中weight（A）是点集A的函数。Cox假设图形是一个平面，利用搞笑的离散算法解决了优化问题。
萨卡和博耶利用的具有最大特征值的特征向量，找到边界图最连贯的区域。尽管他们的特征系统钰图形分割没有直接关系，利用2.1的推导，我们可以看到他们的系统接近。
6.总结
在本文中，我们提出一个分组算法，该算法基于的观点是感知分组是一个旨在提取场景的总体印象和提供分层描述的过程。通过将分组问题看成图形分割问题，我们提出了规范化切割准则。规范化切割解决子图非相关行的好方法，并且有一个较好的特性是减小切割将增大相关性，这对于子组内部的总相关是公平的。在为了计算最小切割值而找有效算法过程中，我们又提出广义特征值系统对于我们的问题提供了一个还得解决方案。
基于这种观点的计算方法已得到发展，并且应用于亮度，颜色，质地图像的分割。对于真实和合成图像的实验结果是令人鼓舞的，并且说明了这一规范化切割准则确实满足我们提取场景的大图像的最初目标。