normalized-cuts-and-image-segmentation翻译.docx

算法进行优化？很多有吸引力的准则已经注定无法找到一个有效的算法，找出它的故小贪欲或者梯度卜降方法，无法找到找到高雄非线性问题的全局优化。我们的方法与图的理论分组制定最仃关。随意特征空间的点集可以表示为加权无向图G=(V,E),特征空间的点是图的节点，每对双节点之间形成一个边缘.每个节点的权盎，w(i.j).Si和j两个节点之间的功能相像性.在分组中，我们将定点集分割成不相交的点集VV2.Vm,在某种程度上，在Vi点集中的顶点相像程度较高，不同点集ViV)的顶点的相像程度低。分割一个图像,我们必需提出以下的问题：1 .好的分割应当有什么标准？2.这样的分割怎样有效的计算？在图像分割和数据聚类社区，出现了很多前期工作，这些前期工作利用最小生成树或有限邻域集合的变更。虽然那些运用了高效的计算方法，大部分运用的分割准则都是基丁图形的局部特征,因为感知分组要提取场景的总体印象，正如我们前面所看到的，这一分割准则达不到这一主要H的。在本文中，我们提出了一个新的图形理论标准，即规范化切割，用于测量图像分割的优良度。我们在其次部分介绍和验证这标准.这准则狭义上可以认为是一个广义特征值问题.特征向量可以用于构建良好的图像分区，这一过程可以按须要持续递归(3节)。在第4部分，我们会展示试验结果。规范化切割准则的制定和最小化借鉴了很多的理论和实践结论，这些结论来源于数据分析和理论计算科学社区。第5部分会探讨频谱分割问题的前期工作。我们将会在第6部分做出总结.2 .图形分割分组图形G=(V,E)可以分割成两个不相交的集合,B.AUB=V,ACB=0,只需一出连接两个集合的边缘.这两部分的相像度可以通过已经被移除边缘的权重计算。在图像理论语言中，它被称为切割:cut(A,B)=ZMa,v)(1)"A.ve8对一个图形的最优分割是将切割值降到最低。尽管这样的分割有一个指数，找到图形的最小切割值是一个值得探讨的问题，并且存在有效的算法可;以解决这一问题“;吴和莱希提出了基于这个最小92切割准则的一个聚类方法。特殊是，:他们将一个图像分割成K子图，从而子分组的最大切割值可以最小化。这H一问题可通过递归杳找平分现有部"(分的最小切割值得到有效的解决。在他们的探讨中，这全局优化准则可以用于产生好的分割图像.图2然而，他们在探讨中还留意到，这一最小切割准则有利于切割图形中的孤立节点，这并不惊奇，因为(1)中定义的切割值随着两个分割部分的边缘数量而增加。图2说明白个这种状况。假设边绿权重与两个节点之间的距离成反比，我们看到划分出节点、或n：的切割值很小。事实上，随意划分右半部分孤立节点的切割值要小于招节点划分成左右两半的切割值，为了避开切割成小集合中出现的不自然的偏见，我们提出了解除两分组关联的新方法。不是只看连接两部分的权重值，我们的方法是计算作为连接到图表中的全部节点的总的边缘的一小部分的切割成本.我们称解除关联的措施为规范化切割(Ncut):.,“n.cut(,A,B)cut(A,R)Nctt(A,B)=+(2)assoc(A.V)assoc(B.V)assoc(A,V)=ZyNM是从A中的节点到图形中的全部节点的总连接，sa48.刃类似定义。有了解除分组关联这肯定义,划分小孤立点的切割值将不再有小的规范化切割值，因为切割值几乎会占从小集合到全部其他节点的全部连接的很大比例。图2所示状况，我们看到节点m的切冽值等于到该节点的总连接。相同状况卜.，对于一个绐定的分割，我们可以定义一个组内规范化关联的测量值:v,Amasso(A,A)asso(B.B)NaSSo(A.ti)=+(3)asso(A,V)asso(B,V)“ssgAA)和ssod8.8)分别是和B内部边缘连接节点的全部权重。我们再次看到这是一个不偏倚的方法，这反映了组内节点相互连接的紧密程度。一个分区的关联和非关联的定义的另一个全要特征是它们是自然相关的：,.»、cut(A,B)cu(A,B)Ncul(A.B)=+asso(A.V)asso(B.V)asso(V)-asso(.)asso(H.V)-asso(8.B)=+asso(A.V)asso(B.V)、asso(A.A)asso(B,B)=2-(+)=2-NaSso(A,B)ass<>(AV)asso(B,V)因此，在我们的分组算法中寻求的两个分组准则，使组内非关联最小化和使组内关联最大化，事实上是相像的，可以同时满意.在我们的算法中，我们将会运用规位化切割为分割准则。已经定义了我们想要优化的图形分割准则，我们将要介绍这样的优化准则怎么高效的计算。2.1 计算优化准则给定一个分区的节点图V,将其分为,B两个集合，X是N=IY三维指示向量,节点i在A内时x,=l,否则等于-1。d(i)=Ej0J)是从节点i到其它节点的总连接。有了X和d的定义，我们可以将NymA舟)全新写为:、，“八、eul(.B),cut(B.)Ncut(.B)+s0C(A.V)asso(B.V)V-WipCiXjV-WijXiXj=乙(.四四+ZSOdEIXyOdiD是NXN的对角矩阵，1在对角线上，W是NXN的对称矩阵，WfiJ)=W如&=今色，iN×l向量。*和占分别是,0和X：00的指示22向量，我们可以重写My”(x)：(i+x),(D-W)(i+x)(i-x)r(£)-W)(i-x)2(l-2k)if(D-W)xki,Di(I-JlMzDfk(l-k)i,Di-k(-k)i,Di令(x)=x(D-W)x,(x)=i(D-W)x,=i(D-W)i,M=iDi,我们可以接若化简上面等式：=(a*)+y)+2(l-2Q/?*)=(aCv)+y)+2(l-2A)Q(x)_2(x)+y)+2(M+2/k(-k)MA(1-*)/MMM删除最终的常数项，在这种状况下等于0,我们得到：Q-2+22)zz,、2()-2*)z、,(x)+7),(x)二(I-2£+2A-Xa(X)+7)+2(1-2«)夕2a(x)=(I-*尸(I-+2a(x)k(l-k)MMkMF三I令人=JT.由于y=o,式子变为：I-Ar_(1+62)9任)+)+2(1-6?)讥2),纵(N)6f+bM=(l+3)(N)+)2(1一出)0(N)26(z)2%bMbMbMbM_(1+/)(NT(D-W)Z+J(D-W、)6D2(l-62)(D-W)®+bD/6"(D-W)N26(D-W)+应7Di6,TDI(x*n)T(D-W)(a+x)一,V(I-N)T(D-W)(一)斯京26(-z)T(D-W)(+n)61ToI=幽+N)-6('二蓟T(D-WX(I+N)-6(1-嘲6Di令y=(i+A)-仇i-x),简洁得到：y'D=Zd-Zd=O(4)>O»<0.AH由于=,并II)J0=24+卜24=2一.+/>£4=机21+/>24)=*/力'k/tdQOD¥<JXOIKtQei<O将我们得到的放在起：min.NcuHx)=min包*也,<5)yy条件是HGU,-/H,/次=0。上述表达式是瑞利商“假如y可以取实际值，我们可通过求解广义特征值系统使(5)最小化，(。-W)，=),(6)然而，在相应的指标向量X条件下，对于y我们有两个约束。第个是ydi=().我们可以得到广义特征系统的解决方案可以满意这一约束.我们将这样做，首先将(6)式转变成一个标准化特征系统，在此相应的条件已满意。将2II(6)式写为：。3(o-w)。3z=z,(7)=Dy人们很简洁验证z。=Ji是式(7)的特征向此特征值是0。而且，OT(O-W)O3是对称半正定，由于(D-W)也被称为拉普拉斯矩阵，是半正定矩阵。因此z<,事实上是式(7最小的特征向量，并且式(7)全部的特征向垃是正交的“特殊是,其次个战小特征向量。与ZO正交。将这种状况应用于广义特征系统(6),我们得到：(I)yo=<0,i)是最小的特征向此(2)0=zo=y1rZ.y1½(6)的其次个最小特征向量.现在，回想起关于瑞利商的一个简洁事实:使A是一个对称矩阵。X与j“个最小特征向量Xi,凶是正交的，在这一约束下，商学通过下一个最XX小特征向量XJ最小化，它的最小值是对应的特征值j,-J1.1i,tu,.z1>rj三lZ,D(D-W)D-Z.结果,我们得到：Z=a瑙.minJ-H-<8)ZZ最终'X=argmi11,-v号/v(9)-因此广义特征系统的其次个最小特征向量是解决规范化切割问题的真正方案。解决我们最初的问题并不重要的唯一缘由是对于y的其次个约束，即y,具有两个离散值，并不能得到自动满意。事实上，放宽限制使优化问题易处理放在首位。在第三部分,我们将展示如何将这有价值的解决方案转变成离散的形式.类似的说法表明，第:个最小特征向量是优化分割前两部分的有价值的解决方案。事实上，这种论点表明，利用每次的特征向量和下一个最小特征向量，可以细分现有的图形。然而，在实际中，从实际价值解决方案到离散价值解决方案的施近误差随着每个特征向房的运用而积累，并旦每个特征向量必需满意相互正交的约束，这种基丁更面的特征向量的解决方案就变得不行靠.最好是重新单独解决每个子图的分割I问题。总之，我们建议利用规范化分割准则进行图形分割，并且，我们已经说明这准则是怎样通过解决广义特征值问题而得到高效的计算。3.分组算法像我们之前看到的，(6)中的广义特征系统可以转化为标准特征值问题。解决全部特征向量的标准特征值问题须要O(I?)个步骤，n是图形的节点数。对于图像分割应用这是不行行的，其中n是图像中的像索数“幸运的是,我们的图像分割具有以下特征：“)图形常常只是局部连接，由此产生的特征系统特别稀松，(2)图形分割只需少数的高特征变量，(3)特征向量的精度要求低，往往只需正确的符号位。我们问题的这些特殊属性可以被称为Ianczos方法的特征求解罂充分利用。IanC7qs算法的计算时间为O(mn)+O(mM(n),J匕中m是矩阵相送运算须要的最大数值，M(n)是矩阵向量计算的成本。在(D-W)矩阵稀松的状况下，矩阵向量只须要0(g时间。m值取决于很多因素。在我们图像分割的试验中，m值一般小于。(，5)。计免特征向量时，我们可以利用其次个圾小特征向量将图形分割成两部分。志向状况卜.，特征向量只有两个离散值，值得迹象会告知我们怎样分割图形。让本人，我们的特征向鱼可以取连续的值，我们必需选择一个分割点将图形分为两部分.，选择这一分割点有很多方法“可以取。值或中间值作为分割点，或者找寻一个分割点使结果有一个最合适的NCUt(AB)值。我们在工作中实行了后者。现在，探讨工作是检查等间隔的可能的分割点和计算NCUt最优值。在我们的试验中，特征向量的值般分别，即使1.值很小，这种选择分割点的方法也很牢苑。图形被分成两部分后，我们可以在两个分区第贵的运行我们的算法。或者等价的，我们可以利用其他蛊级特征向量的特殊属性，就像前面介绍的基于那些特征向量分割图形。当NCUl值超过肯定限制时递以停止。我们也对分割加了个稳定准则，有些类似于边缘检测的定位准则。我们可以通过一个准则区分真正的边缘与具有高梯度阴影的区域，这一准则是在高梯度阴影区域或正边缘位置不同会变更其强度，而在平滑阴影区域时假定边缘位置不同不影响其强度。在目前状况卜:假如变更形成切割的图形边缘，Ncut值变更不大，我们将其视为不稳定切割。为了计算这稳定值，我们围绕优化值变更切割点的值,并且引入两个不同分区，PI=(Al,Bl)和P2=(A2,B2)o稔定值是,其中Q(H,P2)川Y2)cui(P.P2)DiP.P2)我们的分组算法可以总结如下：1 .已知一组特征，设巴一个加权图G=(V,E),计算每个边缘的权重：，并且将信息汇总到W和D.2 .利用最小特征向量解式(D-W)X=XDX的特征向量。3 .通过其次个最小特征向量的特征值划分图形找到切割点，从而使规范化切割价值圾小化。4 .通过检查分割科定性确定现在的划分是否须要细分，并且确保规范化切割值低于指定值.5 .假如有必要对分割部分再划分。通过这种方法分割组的数量干脆受域大规范化切割值的限制。4.试骐一X()X(,)1)T尸()F()h我们已经聘分组算法应用于战于亮度，颜色，质地和运动信息的图像分割。在每种状况卜.，我们通过将每个像素当做一个节点构建图形G=(V,E),并且定义节点i和j的边沿权重明,为特征相像性术语和空间邻近性术语：ifIlXa)-X(训2<rotherwise其中X。)是节点i的空间位理，Fd)是基强度,颜色，质地信息的节点的特征向量，定义为：(1)在分割点集的状况下，F(i)=l:(2)l(i)=I(i)f强度值，为了分割亮度图像:F(0=v,V-jsin().vscos()K»h,s,v是HSV的值,用于藤色分割：(4)F(=*lu-,nab,用于质地图像分割。:<?:.须要留意的是随意节z.：；：.支云笠点i和j的权重WU=Q三>¾-.V"IZ*.-*'.''.已经超过分别的r像归:不TA325:素Q图3我们首先在类似r图2的空间点集合上测试算法。图3说明点集和分割结果.从图中可以看出，标准化切割准则的确可以用我们在其次部分探讨的忐向方式切割点集。图4,5,6是应用分割算法于不同亮度的图像>>图4是又添加噪声的合成图像。图5,6是臼然图像，须要留意的是图6的物体边界不明幽，这将会是边界检测不佳。图7是颜色图像的分割，在这些处理中重现灰度“须要留意的是，在全部的例子中，算法可以提取场强的主要组成部分而忽视小的内部成分的变更。依据须要，递归分割可以用于进一步分解每个部分。最终，我们用以国马为背景的自然图像的J贞地分割的初步结果作为总结，看图8.须要留意的是我们的措施是变更方向的.因此，部分拥有不同条纹的斑马的皮肤应当标为单独区域。在这些例子中，我们已经分别考虑了基于亮度，颜色和质地的分割。明显这些可以和视差，运动信息结合在起。H11图5图75相关分割算法利川特征值问题解决图像分割的观点最初是在多纳特，霍夫及和费铿勒的作品中提到的。费德勒认为（D-W）X=Zr的特征向很的其次个最小特征值可以用于分割图像。事实上其次个最小特征值被称为费德勒值，相应的特征向信是费德勒特征向信.这一光谱分割的想法已经更兴，并且通过一些探讨者得到进一步发展，特殊是在并行科学计算领域。在应用于其它领域时，与多做这表明光谱分割放吧的确供应了分割图6图8图形的好方法。在这个领域的理论工作集中于切割率和费德勒值之间的联系。R域A的切割率定义为CM¥一A。可以看出费德勒值越小，必于费德勒向mindAUV-AD量的图像分割会有较好的切割率。我们在2.1的推导表明费镌勒向量是inCM”A）+WA）问题的解决方法,我们可以称之为平均分割。miIy-Al尽管平均分割看起来与规范化分割相像，但平均分割没有平均相关这一属性，可以定义为竺架。因此，不行以同时减小非相关和增大组内相关。当我们将全部技术部用丁图像分割，范县在实际中规范化分割效果更好。广义特征值方法通过平衡并行计算机的计算负载而第一次应用于图像分割。在计算机社区，有些相关的图像分割方法。吴和莱希利用最小切割准则进行分割。COX寻求减小空当二”.AuY,其中WCight（八）是点集A的函数,Wetahl（八）COX假设图形是个平面，利用搞笑的离散算法解决了优化问题。萨卡和博耶利用WC=Zr的具有最大特征值的特征向量，找到边界图最连贯的区域。尽管他们的特征系统桂图形分割没有干眼关系，利用2.1的推导，我们可以看到他们的系统接近minACV经$2(也立.IAl6 .总结在本文中，我们提出个分组算法，该算法基于的观点是感知分组是个自在提取场景的总体印望和供应分U描述的过程.通过将分组问题看成图形分割问题，我们提出了规范化切割准则。规范化切割解决子图非相关行的好方法，并且有一个较好的特性是减小切割将增大相关性，这对于子组内部的总相关是公允的。在为了计算最小切割值而找有效算法过程中，我们乂提出广义特征值系统对于我们的问题供应r一个还得解决方案。施于这种观点的计算方法已得到发展，并且应用于亮度，颜色，质地图像的分割。对于真实和合成图像的忒验结果是令人鼓舞的，并且说明白这一规范化切割准则的确满意我们提取场景的大图像的最初目标。