规范化切割和图像分割
摘要：为解决在视觉上的感知分组的问题，我们提出了一个新的方法。我们目的是提取图像的总体印象，而不是只集中于局部特征和图像数据的一致性。我们把图像分割看成一个图形的划分问题，并且提出一个新的分割图形的全球标准，规范化切割。这一标准衡量了不同组之间的总差异和总相似。我们发现基于广义特征值问题的一个高效计算技术可以用于优化标准。我们已经将这种方法应用于静态图像和运动序列，发现结果是令人鼓舞的。
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=?,只需一出连接两个集合的边缘。这两部分的相似度可以通过已经被移除边缘的权重计算。在图像理论语言中，它被称为切割：
cut(A,B)??w(u,v) （1）
u?A,v?B对一个图形的最优分割是将切割值降到最低。尽管这样的分割有一个指数，找到图形的最小切割值是一个值得研究的问题，并且存在有效的算法可以解决这一问题。
吴和莱希提出了基于这个最小切割准则的一个聚类方法。特别是，他们将一个图像分割成K子图，从而子分组的最大切割值可以最小化。这一问题可通过递归查找平分现有部分的最小切割值得到有效的解决。在他们的研究中，这一全局优化准则可
以用于产生好的分割图像。 图2
然而，他们在研究中还注意到，这一最小切割准则有利于切割图形中的孤立节点，这并不奇怪，因为（1）中定义的切割值随着两个分割部分的边缘数量而增加。图2说明了一个这种情况。假设边缘权重与两个节点之间的距离成反比，我们看到划分出节点n1或n2的切割值很小。事实上，任意划分右半部分孤立节
点的切割值要小于将节点划分成左右两半的切割值。
为了避免切割成小集合中出现的不自然的偏见，我们提出了解除两分组关联的新方法。不是只看连接两部分的权重值，我们的方法是计算作为连接到图表中的所有节点的总的边缘的一小部分的切割成本。我们称解除关联的措施为规范化切割（Ncut）：
Ncut(A,B)?cut(A,B)assoc(A,V)?cut(A,B)assoc(B,V) （2）
assoc(A,V)??u?A,t?Vw(u,t)是从A中的节点到图形中的所有节点的总连接，
assoc(B,V)类似定义。有了解除分组关联这一定义，划分小孤立点的切割值将不再有小的规范化切割值，因为切割值几乎会占从小集合到所有其他节点的所有连接的很大比例。图2所示情况，我们看到节点n1的切割值等于到该节点的总连接。相同情况下，对于一个给定的分割，我们可以定义一个组内规范化关联的测量值：
Nasso(A,B)?asso(A,A)asso(A,V)?asso(B,B)asso(B,V) （3）
assoc(A,A)和assoac(B,B)分别是A和B内部边缘连接节点的全部权重。我们再次看到这是一个不偏倚的方法，这反映了组内节点互相连接的紧密程度。
一个分区的关联和非关联的定义的另一个重要特征是它们是自然相关的：
Ncut(A,B)?cut(A,B)asso(A,V)?cut(A,B)asso(B,V)
asso(B,V)?asso(B,B)asso(B,V))?2?Nasso(A,B)
?asso(A,V)?asso(A,A)asso(A,V)asso(A,A)asso(A,V)?
?2?(?asso(B,B)asso(B,V)因此，在我们的分组算法中寻求的两个分组准则，使组内非关联最小化和使组内关联最大化，实际上是相似的，可以同时满足。在我们的算法中，我们将会使用规范化切割为分割准则。
已经定义了我们想要优化的图形分割准则，我们将要介绍这样的优化准则怎么高效的计算。
2.1 计算优化准则
给定一个分区的节点图V，将其分为A，B两个集合，x是N=|V|三维指示向量，
节点i在A内时xi=1，否则等于-1。d?i???jw(i,j)是从节点i到其它节点的总
连接。有了x和d的定义，我们可以将Ncut(A,B)重新写为：
Ncut(A,B)?cut(A,B)assoc(A,V)?cut(B,A)asso(B,V)
??(xi?0,xj?0)?wijxixjdii?x2?di??(xi?0,xj?0)?wijxixjdi
xi?0?i?x2xi?0D是N×N的对角矩阵，d在对角线上，W是N×N的对称矩阵，W(i,j)=Wij,k???xi?0idi,i是N×1向量。和分别是xi>0和xi《0的指示
向量，我们可以重写Ncut（x）：
?(i?x)(D?W)(i?x)kiDiTT?(i?x)(D?W)(i?x)(1?k)iDiTT?(x(D?W)x?i(D?W)i)k(1?k)iDiTTT?2(1?2k)i(D?W)xk(1?k)iDiTT
令?(x)?xT(D?W)x,?(x)?iT(D?W)x,??iT(D?W)i,M?iTDi,我们可以继续化简上面等式：
?(?(x)??)?2(1?2k)?(x)k(1?k)M?(?(x)??)?2(1?2k)?(x)k(1?k)M?2(?(x)??)M?2?(x)M?2?M删除最后的常数项，在这种情况下等于0，我们得到：
(1?2k?2k)?(1?2k?2k)(?(x)??)?2(1?2k)?(x)k(1?k)Mk1?k22?2?(x)M?(1?k)2(?(x)??)?k1?kM2(1?2k)(1?k)2?(x)?2?(x)M令b?,由于γ=0，式子变为：
令y?(i?x)?b(i?x),容易得到：yTDi??dxi?0i?b?di?0 （4）
xi?0由于b?k1?k?d?xi?0i?dxi?0i，并且yTDy??di?b2?di?b?di?b2?di?b(?di?b?di)?biTDi
xi?0xi?0xi?0xi?0xi?0xi?0将我们得到的放在一起：minxNcut(x)?miny(D?W)yyTyDyT, （5）
条件是yi?{1,?b},yTDi?0。
上述表达式是瑞利商。如果y可以取实际值，我们可通过求解广义特征值系统使（5）最小化，(D?W)y??Dy （6）
然而，在相应的指标向量x条件下，对于y我们有两个约束。第一个是
ydi?0。我们可以得到广义特征系统的解决方案可以满足这一约束。我们将这
T样做，首先将（6）式转变成一个标准化特征系统，在此相应的条件已满足。将（6）式写为：D?12(D?W)D1?121Z??Z, (7) z?D2y
?12人们很容易验证zo?D2i是式（7）的特征向量，特征值是0。而且，D(D?W)D?12是对称半正定，由于（D-W）也被称为拉普拉斯矩阵，是半正定矩阵。因此zo实际上是式（7）最小的特征向量，并且式（7）所有的特征向量是正交的。特别是，第二个最小特征向量z1与zo正交。将这种情况应用于广义特征系统（6），我们得到：（1）y0=（0，i）是最小的特征向量，（2）0?z1Tz0?y1TDi，y1是（6）的第二个最小特征向量。
现在，回想起关于瑞利商的一个简单事实:使A是一个对称矩阵。X与j-1个最小特征向量x1，??,xj-1是正交的，在这一约束下，商小特征向量xj最小化，它的最小值是对应的特征值λj。
结果，我们得到：z1?arg.minTxAxxxTT通过下一个最
zDzz0?0TT?12(D?W)DzzT?12z （8）
最终，y1?arg.miny(D?W)yyDi?0TyDyT （9）
因此广义特征系统的第二个最小特征向量是解决规范化切割问题的真正方案。解决我们最初的问题并不重要的唯一原因是对于y的第二个约束，即yi具有两个离散值，并不能得到自动满足。事实上，放宽限制使优化问题易处理放在首位。在第三部分，我们将展示如何将这一有价值的解决方案转变成离散的形式。
类似的说法表明，第三个最小特征向量是优化分割前两部分的有价值的解决