多割问题的对偶分解和线性规划松弛：一个更有效的算法

1最小代价多割问题奥地利ISTpswoboda@ist.ac.atBjoern AndresMPI信息学andres@mpi-inf.mpg.de摘要提出了NP-难最小代价多割问题的对偶分解和线性规划松弛.与多割多面体的其他多面体松弛不同，它可以通过消息传递进行有效的像其他多面体松弛一样，它可以通过切割平面有效地收紧。我们定义了一个算法，交替消息传递和有效的分离周期和奇数轮不等式。该算法比基于线性规划的最新算法更有效，包括在领先的商业软件框架中编写的算法，正如我们在计算机视觉，生物医学图像分析和数据挖掘应用程序中的大型问题实例的实验中所示1. 介绍将图分解成有意义的簇是计算机视觉、生物医学图像分析和数据挖掘中的一个基本问题。在没有给出关于簇的数量或大小的信息，并且只给出关于节点的成对相似性或不相似性的信息的设置中，规范的数学抽象是最小成本多切（或相关聚类）问题[17]。这个问题的可行解，多割，与图的分解多割是跨越不同簇的边的多切割的成本是归因于其边缘的成本的总和。在计算机视觉领域，最小成本多切割问题已在[5，6，47，8]中应用于由BSDS数据集和基准定义的无监督图像分割任务[36]。在生物医学图像分析领域，最小成本多切割问题已被应用于连接组学的图像分割任务[7]。在数据挖掘领域，应用包括[9，40，15，16]。此外，最近许多计算机视觉问题， 作为构建块多切割问题已经被提出：图像和网格分割[31]，实例分离的语义分割[33]，多目标跟踪[44]，细胞跟踪[26]和关节式人体姿势估计[3]。此外，多标签Potts模型的最严格松弛之一是基于多割[30]。由于最小代价多割问题是NP难的[12，19]，即使对于平面图[10]，具有数百万条边的大型复杂实例，特别是连通组的实例，也对现有算法构成了挑战。相关工作。由于多割问题在实际应用中的重要性，人们提出了许多求解最小代价多割问题的算法它们分为以下三类：原始可行局部搜索算法、线性规划算法和融合算法。原始可行局部搜索算法[42，38，23，21，22]试图通过从可以有效索引或搜索的集合进行局部变换来改进初始可行解局部搜索算法对于大型实例是实用的，因为与一次解决整个问题的成本相比，所有操作的成本都很小。缺点是，输出的可行解通常取决于初始化。即使找到了解决方案，也不能证明最优性，因为没有计算下限。此外，多割问题可以转换为马尔可夫随机场，并在那里用原始算法求解线性规划算法[28，29，32，39，46]在可行集的外多面体松弛上操作。他们的输出是独立的初始化，并提供了一个下界。这个下限可以直接用于分支定界搜索中，以获得经认证的最优解。或者，LP松弛可以通过切割平面收紧。已知有几类平面定义了多切多面体的一个小平面，并且可以有效地分离[17]。缺点是，对于多割问题的结构不可知的一般LP的算法随着实例的大小超线性地扩展。融合算法试图将通过组合或随机过程获得的子问题融合过程可以依赖于列生成[47]，二进制二次规划[14]或用于求解整数LP的任何算法[13]。特别是，[47]提供了双下界16171618图1. 将图分解为三个分量（绿色）。对应的多重切割由跨越不同组件的边组成（红色）。v1v2v5uv3v4图2. 奇轮v1v2u2v5u1v3v4图3. 奇怪的自行车车轮但限于平面图。[14，13]以巧妙的方式探索原始解空间，但不输出对偶信息。纲要下面，一个讨论的martaries（第。2）其次是我们提出的分解（第二节）的定义。3）和算法（Sec.4）对于最小成本多-切的问题。我们的方法将局部搜索的效率与LP的下限和融合的子问题相结合，正如我们在实验中所展示的那样，该问题具有大量不同的实例（第二节）。（ 五 ） 。 所 有 代 码 和 数 据 都 可 以 在http://github.com/pawelswoboda/LP_MP上找到。2. 预赛2.1. 最小费用多割问题图G=（V，E）的分解（或聚类）通过用P<$[0，1]E代替x∈P的积分约束（4）得到LP松弛。 这导致了多割多面体的外部松弛，其是以下所有多割的特征函数的凸包：G.对于P：= [0，1]E获得的LP松弛，即，只有周期不等式，一般不会紧张。通过也执行奇轮不等式[17]获得更紧的LP松弛一个k轮是G中的一个圈，它有k个节点，所有这些节点都连接到一个额外的节点u∈V，这个节点不在圈中，被称为k轮的中心（参见图1）。图2）的情况。 对任意奇数k ∈ N，G的任意k-轮，圈C =（ v1v2，. . . ，vkv1）和k轮的中心u，G的多重割x −1（1）的每个特征函数x ∈ {0，1}E满足奇轮不等式是一个分区V1。. . Vk节点集V的，使得ΣkΣkx−x≤，k，与v：=v.（五）V i<$V j=<$<$ij并且每个聚类V i，i =1，. . . ，kvivi+1紫外线I 2k+ 11是有关联的分解引起的多割i=1i=1是跨越不同集群的那些边的子集（参见图1）。这样的边缘被称为切割。由G的任何分解引起的每个多割称为G的多割。G. 我们用MG表示G的所有多重割的集合。给定对每一条边e∈E，这条边被割的代价c∈ R，最小代价多割问题的例子w.r.t.这些代价是最优化问题（1），其可行解都是G.对于任何边缘{v，w}=e∈E，负成本θe0有利于节点v和w在不同的分量中。正成本θe>0有利于这些节点位于同一个分量中Σ为了完整性，我们注意到，已知进一步收紧LP松弛的其他不等式可以包括在我们的算法中，例如，定义在图上的自行车不等式[17]，如图1所示3 .第三章。然而，我们不考虑不等式以外的周期和奇数轮的算法，我们建议。2.2. 双松弛两两可分LP多割问题的LP松弛原则上可以用通用LP的算法来解决，这些算法可以在优秀的软件中找到，例如CPlex [2]和Guideline [25]。然而，这些算法的规模与大小超线性minM∈MG e∈Mθe（1）因此，对于大型实例来说是不切实际我们在SEC中定义图3多割的LP松弛这个问题是NP困难的[12，19]，即使是平面图[10]。下面，我们将其公式概括为二元LP，然后转向LP松弛：对于G的边的任何01-标记x∈ {0，1}E，标记为1的那些边的子集x−1（1）是G的多割当且仅当x满足循环不等式组（3）[17]。因此，（1）可以等价地以二进制LP（2）Σ问题的形式IRPS-LP（Def.①的人。IRPS-LP是对偶分解的特殊情况[24]。在定义1中，每个i ∈ V定义一个子问题，每个边ij ∈ E定义子问题的依赖关系。Def.1更具体的是，首先，子问题是二元的，其次，描述子问题依赖性的线性约束（9）由将01-向量映射到01-向量的01-矩阵定义IRPS-LP可通过消息进行有效优化minx∈REe∈Eθe xe（2）Σ在[43]的框架内。定义1（IRPS-LP [43]）。 设N ∈ N，G =（V，E）1619若∈C∈圈（G）：xe≤xe′（3）e′∈C{0，1}E（4）是具有V ={1，. . . ，N}。 对任意j ∈ V，设dj∈N，Xj <${0，1}dj，θ j∈Rdj.令Λ：= conv（X1）×···×conv（X N）。 对于每一个{j，k}= e ∈ E，令1620图 4. 由 三 个 三 角 形（红、绿、蓝）覆盖的三角形圈（黑色）me∈N，A（j，k）∈{0，1}me×dj和A（k，j）∈{0，1}me×dk使得对于每个j∈ {2，. . .，k−1}，我们为由三角形uv jv j+1和附加边uv1组成的棒棒糖图添加子问题uv j v j +1，v 1 ∈ V。棒棒糖图uvw，s的可行集X uvw，s有10个元素，三角形的5个可行多割乘以2以考虑额外的边。3.1. 依赖关系三角形子问题和边缘子问题之间的相关性它符合IRPS-LP的形式（9）。A（j，k）x∈ {0，1}me（6）A（k，j）x∈ {0，1}me（7）µuv=µuvwµ=µ（1，1， 0）+µ（1，1， 0）+µUVW（1，0， 1）+µ（0，1， 1）+µUVW（1、 1、1）（1、 1、1）然后，下面写的LP被称为整数松弛成对可分w.r.t.图G.J.J.µvw=µuvw（1，0，1）+µuvw（0，1，1）+µuvw（1，1，1）具有边集L={e1，e2，e3，e4}的棒棒糖子问题与具有边集L = {e1，e2，e3，e4}的三角形子问题之间的依赖关系min（8）集合T={e′，e′，e′}在下面被陈述为线性系统，µ∈Λ12 3j∈Vk=1服从<${j，k} ∈E：A（j，k）µj=A（k，j）µk（9）3. 对偶分解在L和T之间不共享的边上求和。该线性系统具有IRPS-LP的形式（9）Σ ΣμL ×L×T： μL（xL×T，xL\T）= μT（xT×L，xT\C）A straight-forward decomposition of the minimum costmulticut 1）由每条边的一个子问题组成，一个子问题xL\T3.2. 言论xT\L每个奇轮不等式对应一个子问题然而，从计算的角度来看，对循环和奇数轮进行三角测量，并考虑由此产生的较小的子问题是有利的下面，严格定义三类子问题。边子问题。对于每个边e∈E，我们考虑一个子问题e∈ V，其可行集Xe：={0，1}，编码边e是割（1）还是未割（0）。三角形子问题为每循环C={v1v2，v2v3，. . . vk v1}E，我们考虑三角形v1v2v3到vk−1vk v1，如图所示4.第一章如果三角形Ci的某条边uv不在E中，我们将其添加到E中，并带有成本零，即，我们对G中的循环进行三角测量。对于每个三角形uvw，我们引入一个子问题uvw∈ V，其可行集 由 三 角 形 的 五 个 可 行 多 割 组 成 ， 即 ， Xuvw ：={（0，0，0），（0，1，1），（1，0，1），（1，1，0），（1，1，1）}。对于任意奇数k∈ N和G的任意k-轮，其中u是中心点，v是圈点，1，. . .，v k，我们引入了两类子问题。对于图中所示的5轮。2，这些子问题被描绘在图。五、对于每个j ∈ {2，. . . ，k}，我们将三角形子问题uv1vj∈ V，如前一节所述v1v2v5v3v41621注1. 循环的三角测量可以理解为作为一个连接树的构造[45]以这样的方式，可以通过动态编程来解决周期上的最小成本多切割问题。圈的三角剖分也可以理解为多割多面体的外多面体松弛的收紧：循环不等式（3）定义了多割多面体的一个面，当且仅当循环是无弦的[17]。通过对一个圈进行三角剖分，我们得到了一组极小的无弦圈（三角形），它们的圈不等式合在一起就意味着整个圈的圈不等式。备注2. 从技术上讲，我们不需要包括奇数轮的三角形子问题。相反，我们可以在棒棒糖di之间引入依赖关系直接以IRPS-LP的形式。然而，通过引入三角形因素，并通过表达棒棒糖和三角形之间的依赖关系，我们耦合棒棒糖因素从不同的奇数轮更紧密，每当他们共享相同的三角形。4. 算法我们现在定义最小费用多目标问题（2）该算法将问题的一个实例作为输入，并在两个主要过程之间交替进行固定次数的迭代。第一个程序，定义在SEC。4.1，解决了在图4.1中定义的IRPS-LP松弛的对偶的16221+α1+α（k，j）（j，k）K（k，j）j（j，k）算法1：多割问题的消息传递数据：{i1，. . . ，ik}= V，（θ i）i∈V，（A（j，i），A（i，j））ij∈E对于i = i1，. . . ，i kdo如果i是边子问题uv：then接收消息：对于w∈V：uvw∈T，δ：= minxuw，xvwθuvw（1，xuw，xvw）-minxuw，xvwθuvw（0，xuw，xvw）图5. 图2中奇数轮的三角剖分。它能-三角形uv1v2，uv1v3，uv1v4，uv1v5和棒棒糖图（uv2v3，v1），（uv3v4，v1），（uv4v5，v1）的坐标系。上一节。的输出包括在一个下限和重新参数化的最小成本多割问题的实例作为输入。第二个过程通过增加当前解所违反的循环不等式（3）和奇轮不等式（5）的子问题来收紧IRPS-LP松弛分离程序发现这种违反不平等，更有效地比切割平面算法的原始[28，29，32]，定义在第二节。四点二。为了找到作为输入的最小成本多割问题的实例的可行解，我们在计算的重新参数化上应用最先进的局部搜索算法，该过程通常被称为四舍五入（Sec. 4.3）。4.1. 消息传递θuv+=δxuw，xvw：θuvw（1，xuw，xvw）=δ端发送消息：δ：=|{w ∈V：uvw ∈ T}|−1 θuvθ uv：= 0对于w∈V：uvw∈T，xuw，xvw：θuvw（1，xuw，xvw）+=δ结束结束如果i是边为C的三角形子问题uvw然后接收消息：对于棒棒糖L，其中L<$C/=δ（xL<$C）：= minxL\CθL（xL<$C，xL\C）θC（xL<$C，xC\L）+=δ（xL<$C）θL（xL<$C，xL\C）+=δ（xL<$C端发送消息：α：=|{L a lollipop：LC}|与其他基于对偶分解的算法一样，我们提出的算法不直接求解IRPS-LP，对于棒棒糖L，其中LC/=doδL（xLC）：=在原始域中，但是优化了（8）-（9）的对偶具体-从本质上讲，它是在一个空间上的重新参数化，minx C\L θuvw（xL<$C，xC\L）问题定义如下：对于任意两个相关子问题jk∈ E，我们可以根据更新规则将成本θj和θk改变任意向量θL（xL<$C，xL\C）+=1δL（xL<$C）端对于棒棒糖L，其中LC/= doθC（xL<$C，xC\L）+=1 δL（xLC）θ′：=θj+A′：=θk−A中国（10）∆。（十一）结束结束端我们参考根据规则（10）-（11）的θ的任何更新。传递信息消息传递不会改变任何原始可行解的成本，因为θ′，μjJK=θj+A，µj+θk−A，µk（12）L（θ）在所有成本上的最大值，通过线性方程，sage passing等于（8=θ，µ+θ，µ+，Aµ−A中文（简体）语法对偶我们试图改变成本θ，j jk k（九）（j，k）j（k，j）k以最大化下限L（θ）。 对于一般的IRPS-LP，v1v1v1v1v1v1 v1v2v5v2uuv5u u u u u uv3v3 v3v4v4 v4θ1623=θ j，μ j+ θ k，μ k。（十四）然而，消息传递确实将对偶下限L（θ）改变为（8），Σ这一目标在[43]中得到了明确对于最小代价多割问题，我们定义并实现了Alg。1、在这个框架内。下面讨论这种算法的一般L（ θ）：=minθ j，x j<$。（十五）j∈Vx∈XiIRPS-LP的消息传递特性在[43]中讨论。1624因子顺序。A l g . 1迭代所有边和三角形子问题。顺序指定如下：我们假设给定节点顺序。关于这个节点顺序，边uv∈E按字典序排序。对于每个三角形及其边集C={e1，e2，e3}∈E，其中e10。在这些子问题中，我们选择那些增加最大的子问题，并将它们添加到图（V，E）中。在[41]中，类似的双切割平面方法已被证明对图形模型有用。4.2.1循环不等式我们刻画了那些子问题使对偶下界L（θ）至少增加1/2的圈.1.提案 设C ={e1，. . . ，e k}是一个循环，θ e1 ≤− ε，θ el ≤ ε，其中l> 1。然后，对偶下界L（θ）可以通过包括C的三角测量来增加。为了找到这样的循环，我们应用Alg。二、该算法首先在不交集数据结构1中记录不同节点u，v∈V是否通过带权≥100% 。具体来说，算法2中的不交集运算union（u，v）连接u和v的连通分量。然后，我们访问所有的边uv∈E，θuv≤−θ。通过find（u）= find（v）查询不相交集数据结构，可以揭示u和v是否通过权重≥100的边连接。如果是这样，我们用广度优先搜索来搜索最短的一个在原始中，找到最大违反的循环不等式（3）更昂贵，需要对于每个边uv∈E，通过例如，Dijkstra4.2.2奇轮不等式我们刻画了那些其棒棒糖子问题使下界L（θ）至少增加1/2的奇轮。第二个提案 设O是一个中心节点为u，循环节点为v1，. . . ，vk. 如果每个三角形uv i v i+1的成本θ uv i v i +1使得任何边的最小成本1https://en.wikipedia.org/wiki/Disjoint-set_数据结构1625算法3：奇数轮不等式的分离（5）数据：三角形uvw，成本θuvw，θ≥0l：= 0对于u∈V，G′=（V′，E′），V′=，E′=，Connect=对于三角形uvw，如果（16）为真，则V′：=V′{v，v′，w，w′}E′：=E′{vw′，v′w}并（v，v′）并集（w，w′）结束结束对于v∈V′<$V，如果find（u）= find（v），则P′：=最短路径G′（u，v，n）C={uv ∈ E |uv ′∈ P ′ <$u ′ v ∈ P ′}如果C是G中的单圈，则01：={u，P}l：= l+ 1端结束结束端精确切割与u相关联的一条边的三角形的标记比切割与u相关联的0条或2条边的三角形的任何边标记的最小成本小1/2即：v′1v′2v′3v′4v′5v1v2v3v4v5图6.Alg. 3用于分离图中所示的5轮。二、第一次搜索原始的进一步复杂化来自于这样一个事实，即分离算法需要访问所有v∈V′以计算G′中的最短vv′-路。4.3. 舍入我们的信息传递给阿尔格。1改进了（2）的对偶下界，但没有提供（2）-（4）的可行解为了获得可行的多割，我们应用了[31]中定义的局部搜索算法，即贪婪加 性 边 缘 收 缩 （ GAEC ） ， 然 后 是 具 有 连 接 的Kernighan-Lin（KLj）。GAEC通过对那些连接最大限度地降低成本的边进行收缩来一旦没有任何边的收缩严格地降低成本，它就停止。KLj尝试通过应用来自三个类的转换来递归地改进给定的多切：(1)在两个组件之间移动节点，（2）将节点从给定组件移动到新形成的组件，或者(3)连接两个组件。GAEC和KLj是局部搜索算法，它们输出不需要是最优的可行多割。我们不仅适用于GAEC和KLj的最小成本的多割问题的实例作为输入，但也重新参数化的这个实例输出的Alg。1.一、{x：xminuvi+x uvi+1=1} θuvivi+1（x）+ θuvi v i +1（x）这样做的理由来自LP二元性：≤ min{x：xuvi+xuvi+1=1}θ uvivi+1（x）.（十六）3号提案假设θ最大化对偶下界L（ θ），松弛是紧的，即为了找到这种奇怪的车轮，我们应用Alg。3 .第三章。这个算法建立在我们的观察，我们只需要看看三角形的子问题已经被添加。L（θ）= min{x ∈{0，1} E|x−1（1）∈M G}θ，x（十七）因此，Alg。3访问每个节点u∈V，并建立一个二分图G′=（V′，E′）如下。（图中描绘了一个例子6为5轮和（16）保持为真的所有三角形进一步，设x∈{0，1}E使得x∈−1（1）是G的最优多重割. 然后，.车轮）。 对于每个三角形uvk，使得（16）成立，θ≤0，如果x=1（十八）四个节点v，v′，k，k′∈V′被添加到V′，每个原始节点的两个副本。它们由边uv′，u′v∈E′连接。若G′中存在从u到u′的路，则我们发现了一个违反的奇轮不等式（5）.由于G′是二部的，G′中的一条uu′-路对应于G中的一个奇圈.如前所述，路径搜索通过经由不相交集合数据结构的连通性测试来加速，并且通过广度优先搜索来执行在原始图中，找到一个最大违反的奇轮不等式（5）需要对每个节点u∈V构造相同的二分图G′[20]。然而，最短路径搜索边缘成本1− x vw+1（x uv+ x uw）需求1626e≥0， 如果x=0运行Alg。1，我们期望θ满足Prop的符号条件。大约3。因此，θe的符号将是边e被切割的良好暗示。因此，非正式地说，我们期望局部搜索算法的重新参数化的问题的实例上操作，以产生更好的可行的多割比局部搜索算法的给定实例上操作对于马尔可夫随机场中的MAP推理，已知[34，35]原始舍入可以大大改进2 2当应用于通过消息传递重新参数化的成本时，通过Dijkstra算法而不是广度来执行16275. 实验求解器我们比较了几个国家的最先进的算法。• 算法MC-ILP[29]是切割平面算法的有效实现，以切割平面方式使用循环不等式（3）求解（2）。CPlex[2]用于解决底层ILP问题。（4）中的积分条件直接提供给求解器。根据[29]，这是有益的，因为CPlex[2]具有出色的分支和切割能力。• Cut，Glue Cut [14]，缩写为CGC，是一种使用平面最大割子问题来改进多割的移动算法。• Fusion移动到相关聚类[13]，称为CC-Fusion，在辅助多割问题的帮助下融合各种建议生成器生成的多割，进而由MC-ILP解决。我们使用随机化的层次聚类和随机流域作为建议生成器，由后缀-RHC和-RWS我们使用建议生成器的参数作为作者推荐[13]。• MP-C表示当我们仅通过算法2分离循环不等式（3）时的算法1，而MP-COW表示我们通过算法3另外分离奇数轮不等式（5）。我们搜索三角形和棒棒糖添加每10次迭代。• KL是第4.3节中描述的用于计算多割的GAEC和KLj实现[31]我们让KL在当前重新参数化的边成本上运行MP-C和MP-COWMC-ILP、CGC和CC-Fusion是OpenGM 套件的一部分。 只有MC-ILP和我们的求解器MP-C和MP-C OW生成了一个更低的界。CGC输出平凡对偶下界e∈Emin（0，θe），其中边权重θe由问题给出已经表明CGC，CC-Fusion和KL优于其他原始算法[13]，因此我们不与任何其他算法进行比较此外，MC-ILP优于基于LP的求解器[39]，因为后者在内部使用较慢的COIN-OR CLP [18]求解器，因此我们也将其从比较中排除。所有求解器都在具有2.2 GHz和8 GB RAM的i5-5200CPU的笔记本电脑上运行数据集我们比较了8个不同来源的数据集。• image-seg由Berkeley分割数据集[36]的图像组成，用超像素预分割，已经如[6]中计算了其成对亲和度值。• 结-3d-{150| 300| 450| 550}数据集来自具有[150]3，[300]3，[450]3和[900]3体素的组织[ 7 ]的神经回路重建问题。数据被预先分割成超体素。• 模块化聚类旨在基于个人之间的亲和性将社交网络聚类为子组。• CREMI-{小|大型数据集[4]是CREMI [ 1 ]挑战的一部分，其目的是重建成年果蝇大脑的神经回路。图像由电子显微镜拍摄。-small 实例是-large实例的裁剪版本。据我们所知，CREMI大型数据集包含最大的基于LP的方法处理的多切割问题。image-seg，knott-3d和模块化聚类数据集来自OpenGM基准[27]，而CREMI数据集由其作者提供，尚未发表。数据集由100、8、8、8、8、6、3和3个实例组成数据集详情见表1。我们为所有算法设置了一个小时的时间限制，但是当原始/对偶间隙消失或再也看不到任何进展时，我们会提前退出在表1中，报告了特定数据集中所有实例的平均结果在图7中，针对运行时间绘制了特定数据集中所有实例的平均原始解能量和对偶下限（如适用）。从表1可以看出，原始舍入算法虽然更快，但从未给出比基于LP的方法MC-ILP、MP-C和MP-COW更好的原始能量。分支和切割求解器MC-ILP优于我们的算法，在 smallimag-seg 、 knott-3d-150 和 knott-3d-300实例上的MP-C和MP-COW算法，并且对于CREMI-small问题具有更高的下界。每当MC-ILP击败我们的算法时，它的优势非常小。另一方面，MC-ILP在所有问题上都要慢得多，在大型CREMI大型实例上完成单个迭代。在较大的knott-3d-450，knott-3d-550和CREMI-大型数据集上，我们的算法明显优于MC-ILP根据图7我们的对偶原始上下界通常比MC-ILP收敛得更快。我们推测MP-C和MP-COW在一个分支中-与定界求解器可以显著地扩展精确方法对多割问题的处理范围，并在较小的数据集上缩小与MC-ILP此外，不像MC-ILP，我们的重新参数化的成本可以用来改善启发式原始算法。这方面的一个例子可以在图1中看到8、在哪里重新参数化的成本改进了KL1628能源数据集/算法MP-CMP-COWCGCMC-ILPCC-Fusion-RWSCC-Fusion-RHC#我100UB4436.254435.944600.814434.914447.064436.33图像分割#V≤3764LB4434.174434.444129.704434.91‡‡#E≤10970时间9.0521.850.1411.891.191.30模块聚类#我#V#E6≤115≤6555UBLB时间-0.49-0.5487.02-0.49-0.521071.17-0.30-0.790.15-0.44-0.522911.100.00‡0.00-0.44‡17.78#我8UB-4571.21-4571.65-4220.66-4571.69-4534.76-4552.51Knott-3D-150#V≤972LB-4572.21-4571.72-4855.18-4571.69‡‡#E≤5656时间0.750.810.042.370.260.53#我8UB-27299.78-27301.97-24864.59-27302.78-27242.03-27247.29Knott-3D-300#V≤5896LB-27304.96-27303.16-28901.58-27302.78‡‡#E≤36221时间19.3334.272.73227.332.968.15#我8UB-78466.04-78472.24-70865.27-78391.32-78386.14-78381.06Knott-3D-450#V≤17074LB-78485.04-78481.01-83272.85-78522.51‡‡#E≤107060时间385.14598.6031.561840.4716.52119.23#我8UB-136517.72-136523.39-123841.47-135766.90-136464.05-136395.89Knott-3D-550#V≤31249LB-136570.96-136564.10-144703.64-136755.36‡‡#E≤195271时间1804.282218.64102.423683.2272.94594.60#我3UB-213189.20-213193.09-194616.60-209594.49-168905.17-213117.84CREMI-小型#V≤35523LB-213212.43-213209.67-215473.98-213208.94‡‡#E≤235966时间915.701238.59319.012775.813543.612555.48#我3UB-3887113.00-3887078.88††-3772597.37-3619190.20CREMI-大号#V≤623435LB-3888461.86-3888482.06††‡‡#E≤4172314时间4088.514093.91††5978.0823139.40表1. 原始解能量（UB）/对偶下限（LB）/在数据集的所有实例上平均的以秒为单位的运行时间。#I是数字#V和#E是多切割实例中的顶点和边的数量†表示方法在1小时后未完成‡意味着方法不输出对偶下界。粗体数字表示最低原始解能量、最高下限、最快运行时间。四千五百四千四百八十四千四百六十-0。3-0。4-4，000人-4，200-4，400-2。7-2。71-2。72·104四千四百四十四千四百二十10−210−1100101-0。510−210−110 0101102103-4，600-4，800-5，000人10−210−1100-2。73-2。74-2。7510−1 100 101 102-7。6-7。8−8·104运行时间图像分割·105-1。3-1。35-1。4运行时间模块聚类-2。06-2。08-2。1-2。12-2。14·105运行时间Knott-3D-150·106−3-3。2-3。4-3。6-3。8−4运行时间Knott-3D-30010−1 100 101 102运行时间Knott-3D-450-1。45100 101 102运行时间Knott-3D-550101 102运行时间CREMI-小型101 102 103运行时间CREMI-大号图7. 图像-seg、模块化聚类、knott-3d-150、knott-3d-300、knott-3d-450、knott-3d-550、CREMI-小型和CREMI-大型数据集的平均运行时间图实线表示对偶下界，虚线表示原始能量。值在数据集的所有实例上平均。X轴是对数的。·104-3。256. 致谢-3。3-3。35-3。4-3。45MP-CMP-COWCGCMC-ILPCC-Fusion-RWSCC-Fusion-RHCMP-CMP-COWCGCMC-ILPCC-Fusion-RWSCC-Fusion-RHC能源能源能源能源能源能源能源能源162910−210−1 100101运行时间图8.数据集中的实例gm_knott_3d_072Knott-3D-300，其中重新参数 化 成 本 改 进 了KL作 者 要 感 谢Vladimir Kolmogorov进行了有益的讨论，并 感 谢 Fred Ham-precht这项工作部分由欧盟研究委员会根据欧盟第七框架计划（ FP 7/2007-2013 ）/ERC 赠 款 协 议616160资助。我们感谢匿名评论者指出参考文献[37，11]。1630引用[1] CREMI MICCAI电子显微镜图像电路重建挑战赛。https://cremi.org网站。[2] IBM ILOG CPLEX Optimizer。http://www-01.ibm的网站。com/software/integration/optimization/cplex-optimizer/.[3] DeepCut：联合子集划分和标记用于多个体姿态估计.，2016年6月。[4] Multicut使自动神经突分割更接近人类的表现。NatureMethods，14：101[5] A. Alush和J.戈德伯格突破和征服：有效的相关聚类图像分割.在大肠R. Hancock和M. Pelillo，编辑，SIMPAD，计算机科学讲义第7953卷，第134-147页。Springer，2013.[6] B. Andres，J.H. Kappes，T.贝尔U.Köthe和F.A. 火腿酱。具有封闭性约束的概率图像分割。In D. N.梅塔克萨斯湖Quan、紫菀A. Sanfeliu，以及L. J. V. Gool，editors，ICCV，pages 2611-2618. IEEE计算机协会，2011年。[7] B. Andres，T.Kröger，K.L. Briggman，W.Denk，N.科罗戈德，G.诺特U Köthe和F. A.汉普雷希特连通组学的全局最优闭 曲 面 分 割 。 以 . W. Fitzgibbon ， S. Lazebnik ， P.Perona，Y. Sato和C. Schmid，editors，ECCV（3），Volume 7574 ofLecture Notes in Computer Science，pages778-791. Springer，2012.[8] B. 安德烈斯 J. Yarkony， B. S. Manjunath，S. 基尔霍夫E.图雷特肯角C. Fowlkes和H.菲斯特平面超像素邻接图的分割。非平面超像素亲和图。计算机视觉和模式识别中的能量最小化方法（EMMCVPR），2013年。[9] A. 阿拉苏角Ré和D.苏丘使用重复数据删除功能进行具有约束的大规模重复数据删除耶氏酵母中E. Ioannidis，D. L. Lee和R.T. Ng，editors，ICDE，pages 952IEEE计算机学会，2009年。[10] Y. 巴克拉奇山口科利河谷Kolmogorov和M.扎迪莫加德大坝。合作图博弈中的最优联盟结构生成。第27届AAAI人工智能会议论文集，2013年7月14日至18日，Belle-vue，华盛顿，美国。，2013年。[11] S. Bagon和M.加伦一个多尺度离散优化框架。NIPS，2012年。[12] N.班萨尔A。Blum和S.乔拉 相关聚类Machine Learning，56（1）：89[13] T. Beier、F. A. Hamprecht和J. H.卡佩斯融合移动相关聚类。在CVPR中，第3507IEEE计算机学会，2015年。[14] T. Beier，T. Kröger，J. H.卡佩斯大学Köthe和F. A. 火腿酱。切割，粘合切割：多切割分区的快速近似求解器。在CVPR中。会议记录，2014年。[15] Y. Chen，S. Sanghavi和H.徐聚类稀疏图。在公共图书馆Bartlett，F. C. N.佩雷拉角，巴西-地J. C.伯吉斯湖Bottou和K.Q. Weinberger，编辑，NIPS，第2213[16] F. Chierichetti，N.Dalvi，和R.库玛mapreduce中的相关第20届ACM SIGKDD知识发现和数据挖掘国际会议集，KDD'14，第641-650页，美国纽约州纽约市，2014年。ACM。