多切割算法通过GPU实现的高速多切割算法

81930RAMA：GPU上的快速多切割算法0Ahmed Abbas Paul Swoboda0马克斯∙普朗克信息学研究所，萨尔兰信息学校园0摘要0我们提出了一种高度并行的原始-对偶算法，用于多切割（又称相关聚类）问题，这是一种在机器学习和计算机视觉中广泛使用的经典图聚类问题。我们的算法由三个递归执行的步骤组成：（1）找到与底层多切割松弛对应的冲突循环，（2）在边缘和循环之间进行消息传递，优化来自找到的违反循环的拉格朗日松弛，产生降低的成本，和（3）通过矩阵-矩阵乘法收缩具有高降低成本的边缘。我们的算法产生估计到最优解的原始解和下界。我们在GPU上实现了我们的算法，并显示出与在CPU上运行的传统顺序算法相比，执行速度提高了一到两个数量级，而不会牺牲解决方案质量。我们可以在几秒钟内解决具有O（10^8）个变量的非常大规模基准问题，具有较小的原始-对偶间隙。我们的代码可在https://github.com/pawelswoboda/RAMA找到。01. 引言0将图分解为有意义的簇是组合优化中的一个基本问题。多切割问题[15]（也称为相关聚类[10]）是一种基于节点之间的亲和力将图分解为任意数量簇的流行方法。多切割问题及其扩展，如高阶多切割[27,32]，提升多切割[30]，（非对称）多路切割[14,36]，提升不相交路径[21]和联合多切割和节点标记[41]在机器学习，计算机视觉，生物医学图像分析，数据挖掘等领域中找到了许多应用。示例包括无监督图像分割[4, 5, 7,58]，实例分离语义分割[2, 33]，多目标跟踪[21,53]，细胞跟踪[25]，关节人体姿态估计[22]，运动分割[31]，图像和网格分割[30]，连接组学[6, 13, 48]等等。0多切割及其扩展问题是NP难解的[10,18]。由于通常会出现具有数百万甚至数十亿个变量的大型问题实例，因此已经开发了强大的近似算法[11, 12, 30, 39,52]。然而，即使是简单的启发式算法，如[30]，对于非常大的实例也需要非常长的运行时间。特别是，一些实例，如[48]中研究的实例，无法在可接受的时间内解决（因此使用了临时分解技术）。在其他场景中，非常快的运行时间是必要的，例如在端到端训练中使用多切割[2,49]。因此，需要并行化，最好在GPU上进行。由于不规则的数据结构和大多数组合优化算法固有的顺序性质，GPU提供的并行性通常很难利用。这使得在GPU上设计组合优化算法具有挑战性。在将我们的算法运行在GPU上的另一个好处是，在深度学习流水线中使用时，可以避免CPU和GPU之间的内存传输。我们的贡献是一种新的原始-对偶方法，可以进行大规模并行化并在GPU上运行。这导致比以前的多切割求解器更快的运行时间，同时在目标方面计算出与基于CPU的求解器相似或更好的解。然而，我们的方法根源于解决一个有原则的多面体松弛，并且产生了原始解和对偶下界。特别是，原始解和近似对偶求解是交错进行的，以便我们算法的两个组成部分都可以从彼此中受益。更详细地说，我们的算法贡献可以归类如下0原始：边缩减：寻找原始解与[30]类似，依赖于缩减高度可能最终处于最终聚类的同一组件中的边。为此，我们提出使用线性代数方法，将边缩减表示为稀疏矩阵乘法。这使我们能够通过利用高度并行的矩阵乘法GPU原语来加速边缩减。0双重：拉格朗日松弛和消息传递：为了找到好的边缩减候选集，我们考虑通过搜索冲突循环来近似解决多面体松弛，并将其添加到拉格朗日松弛中。̸�.(1)81940通过消息传递迭代地更新由此产生的Lagrange乘子。我们提出了一种新的消息传递方案，既可以进行大规模并行化，又可以对双重目标产生单调递增，从而将[52]的方案加速数个数量级。0递归原始-双重：我们交替进行查找和解决拉格朗日松弛和边缩减的操作，得到最终的图分解。因此，我们的算法超越了只考虑原始图的经典多面体方法[26,44,52]。0在实验方面，我们获得的原始解的质量与已建立的高质量启发式方法[30,38]相当或更好，但执行时间仅为它们的一小部分，并且具有帮助估计解质量的附加双重下界。我们对包含多达O(10^8)个变量的2D和3D实例分割问题进行实验，用于场景理解[17]和连接组学[48]。02. 相关工作0预处理和内部处理：为了在优化之前或之中将变量固定到其最佳值并缩小问题，已经提出了持久性或部分最优性方法[3,37,38]。这些方法应用了一系列的标准，当通过时，证明任何解都可以在其值与持久性固定变量不一致时得到改进。0原始启发式方法：为了获得没有最优性保证或与最优解的距离估计的原始解，已经提出了大量具有不同执行时间/解质量权衡的方法。多割问题的第一个启发式方法，经典的Kernighan&Lin移动算法最初在[29]中提出，并在[30]中稍作推广。该算法尝试各种移动，如合并两个组件，将一个节点从一个组件移动到下一个组件等，并执行降低目标的移动序列。更快但更简单的贪婪加法边缩减（GAEC）启发式算法，一个只能合并单个组件的移动算法，在[30]中提出。它在[30]中用于初始化更复杂的Kernighan&Lin算法。在[28]中提出了涉及不同连接选择策略的变体。贪婪边固定算法[30]在GAEC的基础上进行了推广，它还可以将边标记为切割，将其端点约束为不同的组件。更复杂的剪切、粘合和剪切（CGC）移动启发式算法[12]通过交替对图进行二分，并交换成对聚类中的节点来工作。后一种操作通过将其约化为完美匹配，在平面子图上计算最大割来执行。CGC被扩展为更多的0在[11]中给出了“融合移动”的一般类。在[46]中给出了一个更简单的无权相关聚类问题的并行算法。在[40]中对上述一些原始启发式方法进行了比较调查。0基于LP的算法：为了获得估计到最优解的距离甚至证明解的最优性的双重下界，已经提出了许多基于LP松弛的算法。这些算法可以在分支定界中使用，并且它们的计算结果可以用来指导原始启发式方法以提供越来越好的解。令人惊讶的是，[26,32]已经证明，中等规模的多割问题可以使用商业整数线性规划（ILP）求解器如Gurobi[19]在一个切割平面框架中以合理的时间达到全局最优解。基于解决完美匹配子问题的列生成已经在[42,58]中提出。然而，当需要解决真正大规模的问题时，上述方法会失效，因为底层的LP松弛仍然由传统的LP求解器求解，这些求解器的规模与问题规模不成线性关系，并且没有明确地适应多割问题。此外，违反的不等式分离（切割平面）需要求解加权最短路径问题，这在线性时间内是不可能的。消息传递算法[50]比传统的LP求解器更快地近似解决了双重LP松弛，并且具有比原始LP求解器更快的分离例程，从而可以扩展到更大的问题。在[38]中提出了一个更快但功能较弱的近似循环打包算法。0其他高效的聚类方法：互斥分水岭[57]及其推广[9]与贪婪加法边固定启发式多切割[40]密切相关。与CPU上的多切割算法相比，相应的算法可以更快地执行，但是是顺序执行的。提出了用于聚合聚类的快速GPU方案[8]。最后，谱聚类可以在GPU上实现，具有运行时的增益[24,43]。然而，所有这些方法都不基于任何能量最小化问题，因此不具备优化公式提供的理论优势。03. 方法0图G = (V, E)的分解（或聚类）是节点集的一个划分{V1, . . ., Vk}，使得V1 ∪ . . . , ∪ Vk = V且Vi ∩ Vj = � �i ≠j。由分解引起的割δ(V1, . . . ,Vk)是跨越不同簇的边的子集。这样的边被称为割。参见图1，其中示例了将图划分为三个分量的割。所有多切割的空间是0M G = � δ(V1, . . . , Vk): k ∈ N V1 ˙ ∪ . . . ˙∪ Vk = Vminy∈MG⟨c, y⟩,(2)̸prsqt1−2−31341pq1−2−3 + 13 + 4 + 181950图1.将图分解为三个分量（绿色）。相应的割由跨越不同分量的虚线边组成（红色）。0相关的最小成本多切割问题由附加的边成本向量c ∈RE定义。对于任意的边uv ∈ E，负成本cuv <0有利于节点u和v属于不同的分量。正成本cuv >0有利于这些节点位于同一个分量中。最小成本多切割问题是0其中yuv表示边uv ∈E的情况，如果u和v属于不同的（相同的）分量，则为1（0）。下面我们详细介绍算法的关键组成部分：从每个节点都是一个簇的图开始，原始更新包括通过连接操作迭代地进行边收缩，将簇合并。双重更新通过消息传递优化拉格朗日松弛来获得更好的边成本和下界。原始更新和双重更新交替进行，得到我们的原始-双重多切割算法。我们还详细介绍了如何以高度并行的方式执行每个操作。03.1. 原始：并行边收缩0边收缩算法的思想是迭代选择具有较大正成本的边。这些边更喜欢它们的端点在同一个分量中，因此它们被收缩并最终位于同一个簇中。直到找不到收缩候选者为止，执行边收缩。贪婪加法边收缩（GAEC）[30]是边收缩的特殊情况，它在每次迭代中选择具有最大边权重的边进行收缩，并在收缩图中的每条边的权重为负时停止。以下引理描述了边收缩的操作。0引理1. 给定一个无向图G = (V, E, c)和要收缩的边集合S �E。假设G' = (V', E', c')是在边收缩后得到的图。0(a) 与之对应的满射收缩映射f: V →V'将节点集V映射到收缩节点集V'，通过f(u) = f(v) ���uv-路径(V, S)唯一定义。收缩边集由E' = {f(u)f(v): f(u) ≠f(v), uv ∈ E}给出。0r'0图2. 使用收缩集合S = {rs,st}对图进行收缩，其中顶点r、s和t合并形成一个簇r'。相应的收缩映射是f(p) = p，f(q) = q，f(r) = f(s) = f(t) =r'。请注意，收缩后的图中的边qs和qt变成了平行边，并且它们的成本被相加。还请注意，收缩图中存在表示簇内相似性的自环。0(b) 收缩边的权重为c'ij =0对于uv ∈ E：f(u) = i，f(v) = j c_uv，�ij0引理1(a)将收缩映射f与要收缩的边集S相关联。如果两个节点在f中具有相同的值，则它们之间必须存在一条路径在图(V,S)中。此外，未收缩的端点的边将保留在E'中。引理1(b)提供了通过求和并行边的成本来获得的收缩边的成本。引理的示例见图2。为了快速进行边收缩，我们将使用线性代数表示，以便使用高度并行（稀疏）矩阵-矩阵乘法。0定义2（邻接矩阵）：给定加权图G = (V, E, c)，其（对称）邻接矩阵A ∈ RV×V0由A_uv定义：0c_uv，uv ∈E；0，否则。0我们将使用以下定义的边收缩矩阵来进行边收缩。0定义3（边收缩矩阵）：给定加权图G = (V, E,c)和要收缩的边集S �E，设f为收缩映射，V'为收缩后的节点集。边收缩矩阵KS ∈{0, 1}V×V'0(KS)uu' =01，f(u) = u'00，否则。0引理4：给定加权图G = (V, E, c)，要收缩的边集S �E和相关的边收缩映射f0(a) 收缩图的邻接矩阵等于K�SAKS -diag(K�SAKS)，其中diag(∙)是矩阵的对角部分。0(b) 对于对角元素(K�SAKS)u'u' =0对于uv ∈ E：u' = f(u) =f(v) c_uv。(5)81960引理4(a)通过稀疏矩阵-矩阵乘法提供了一种并行计算收缩图的方法。引理4(b)允许有效地判断新形成的聚类是否降低了多切割目标。具体来说，如果对角线包含所有正项，则收缩后的多切割目标也将减少。算法1给出了一种执行边收缩的原始更新迭代。0算法1：并行边收缩0数据：图G = (V, E, c) 结果：收缩图G' = (V', E', c')，收缩映射f：V→ V'01  计算收缩集S � E02  从G计算邻接矩阵A03  构建收缩映射f：V → V'04  构建收缩矩阵KS05  A' = K�SAKS - diag(K�SAKS)06  从A'计算收缩图G' = (V', E', c')0寻找收缩边集S：确保良好的原始更新的关键步骤是在算法1中选择收缩的边集S。一方面，我们希望以保守的方式选择边，以避免错误的收缩。另一方面，为了效率，我们需要尽可能多地收缩边。我们提出了两种方法，使我们能够同时满足这两个标准。0最大匹配：使用Luby-Jones握手算法[16]的GPU版本在正边上执行快速最大匹配，并选择匹配的边进行收缩。0不冲突的最大生成森林：使用快速GPU版本的Boruvka算法[55]在正边上计算最大生成森林，以找到初始收缩候选集。然后，迭代所有负边ij，在森林中找到i和j之间的唯一路径（如果存在），并删除最小的正边。我们利用GPU连接组件[23]来检查这些路径的存在性并计算最终的收缩映射。0上述两种策略都确保了结果的连接操作降低了多割目标。我们首先通过最大匹配找到收缩边。如果找到的边不足（即少于0.1 | V|），则切换到基于生成森林的方法。请注意，如果我们只选择一个最大的正边进行收缩，算法1就会专门用于GAEC[30]。由于我们的算法依赖于许多同时边缩减以提高效率，因此我们不使用此策略。03.2.对偶：冲突循环和消息传递0求解多割问题（2）的对偶可以帮助获得目标值的下界，并且可以得到边缘成本的重新参数化，从而有助于更好的原始更新。我们的对偶算法基于多割问题的循环松弛[15]。我们提供了用于搜索最有用的违反约束的大规模并行不等式分离例程以及用于优化所得松弛的高效对偶块坐标上升过程。03.2.1循环不等式和拉格朗日松弛0由于多割问题是NP困难的[10,18]，我们无法希望获得conv（MG）的可行多面体描述。对于大多数实际问题，循环不等式给出了一个很好的松弛。给定一个循环C = {e1，...，el} �E，一个可行的多割要么不包含任何切割边，要么应该包含至少两个切割边。这个约束可以表示为0�C∈cycles（G）：�e∈C：ye≤�0e'∈C\{e}ye'。（3）0循环不等式和二进制约束ye∈{0, 1}实际上定义了MG[15]。换句话说，当放松ye∈[0,1]时，我们得到一个线性规划松弛到conv（MG），其中所有整点都是有效的多割。虽然循环不等式（3）给出了多割问题（2）的多面体松弛，但我们的算法将在通过La-grange变量连接在一起的拉格朗日分解上操作，该分解是在[50]中提出的。它由两种类型的子问题组成：（i）每个边e∈E的边子问题和（ii）三角形子问题（即长度为3的循环）0三角形的子集T�E30循环的三角剖分0为了得到定义与具有所有可能的循环不等式（3）相同的多面体松弛的三角形，需要对长度大于三的循环进行处理，而不会丧失一般性[15]。我们将三角形图上的可行多割集定义为0（4），这是（3）的一个特例，表示要么所有边都被切割/连接，要么刚好有两条边被切割。给定一组边和三角形子问题，我们的拉格朗日分解是0max λ0uv ∈ E min y ∈{ 0 , 1λ uv ∙  y  + �0t ∈ T min y0LB（λ） =：（λ）0其中重新参数化的边缘成本cλuv∈R和三角形mt→e(cλt ) = minye=1y∈MT⟨cλt , y⟩ − minye=0y∈MT⟨cλt , y⟩(7)|t∈T :e∈t|3t9λt,ik+ = 12mt→ik(cλt )10λt,jk+ = mt→jk(cλt )11λt,ij+ = 12mt→ij(cλt )12λt,ik+ = mt→ik(cλt )13λt,ij+ = mt→ij(cλt )81970三角形t = {ij，jk，ki} ∈ T的成本cλt∈R3为0cλuv = cuv 0t ∈ T：uv ∈ t λ t,uv（6a）0cλt = -（λt,ij，λt,jk，λt,ki）（6b）0LB（λ）在（5）中是任意λ的最优多割成本的下界。（5）的最优目标值等于多面体松弛问题的目标值[52]。03.2.2循环不等式分离0对于对偶问题（5），需要枚举所有可能的循环不等式（3）。然而，正如[38]中提到的，为了提高效率，我们可以仅限于包含恰好一个斥力边的冲突循环。如果一个循环包含恰好一个斥力边，则称其为冲突循环。0定义5（冲突循环）。令吸引边的集合为  E + =  { c e  >  0:  � e  ∈  E } ，排斥边的集合为  E − =  { c e  <  0 :  � e  ∈E } 。那么G的冲突循环是集合  { C  ∈  cycles ( G ) :  | C  ∩ E − |  = 1 } 。0引理6. 对于每个  ij  ∈  E − ，可以并行地在图  G  = ( V, E+ ) 中找到从  i  到  j的最短路径（跳数），充分利用GPU的并行化能力。03.2.3 双块协调上升（DBCA）0DBCA（也称为消息传递）在多切割中已经研究过[50]。然而，由于这些方案的有效性取决于先前的方案是否被执行，所以这些结果的消息传递方案不容易并行化。我们提出了一种多切割的消息传递方案，该方案对消息传递的顺序不变，因此允许并行计算。与[50]一样，我们的方案通过边和三角形之间的消息传递来迭代地改进下界（5）。对于每个消息传递操作，我们需要计算最小边际，即通过将指定的变量固定为1和0得到的子问题的最优成本的差异。对于边成本，最小边际就是重新参数化的边成本。对于三角形子问题，它的计算如下0定义7（三角形子问题的边际化）。令 t  ∈  T  是包含边  e的三角形。0称为三角形  t  和边  e  的最小边际。0消息传递算法首先对边子问题设置最小边际为零，然后对0在算法2中，通过来回传递消息，子问题之间的通信可以使它们的局部最优解收敛，并且最小边际收敛于一致（即它们对应的边标签  y是一致的）。在[52]中证明了每个这样的操作在对偶目标值上是非递减的，从而产生了整体的单调收敛。消息从边传递到三角形在第2-5行中进行。在这一步之后，重新参数化的边成本  c λ e变为零。我们执行多个三角形到边的消息传递更新（第8-13行），类似于[54]中的方法，将消息均匀分布在包含该边的所有三角形之间。在此操作之后，  c λ t的最小边际变为零。0算法 2: 并行消息传递0数据：图  G  = ( V, E, c ) ，三角形  T，拉格朗日乘子  λ 。0结果：更新的拉格朗日乘子  λ // 边到三角形的消息01  对于  e  ∈  E  并行执行02 α  =  c λ e 3 对于  t  ∈ T  :  e  ∈  t  执行05 结束06  结束0// 从三角形到边的消息07  对于  t  =  { ij, jk, ki } ∈  T  并行执行014  结束0消息传递的收敛性。算法2收敛于固定点，类似于其他用于图模型的DBCA方案[34，35，54，56]。这些固定点通过弧一致性来刻画，并不一定与最优对偶解重合，但通常接近最优解。下面，我们刻画这些固定点。0定义8（局部最优解）。将边e ∈ E的局部最优解定义为0cλe := {x ∈ {0, 1} : x ∙ cλe = min(0, cλe)} (8)0对于三角形t ∈ T也类似地定义为0cλt := {x ∈ MT : �cλt, x� = min x' ∈MT �cλt, x'�} (9)MessagepassingEdgecontraction81980a b0c0d e0a b0c0d e0abc0de0图3.我们的原始-对偶多切割求解器在具有斥力和吸引力边的图上的示例迭代。边的宽度表示绝对成本。首先，我们检测冲突循环并三角化以获得三角形（用�表示）。接下来，对偶更新重新参数化边成本，从而解决了冲突循环。最后，通过缩减吸引力边进行原始更新。0将三角形解的投影定义为0Πe(cλt) := {x ∈ {0, 1} : �x' ∈ cλt s.t. x'e = x} (10)0定义9（弧一致性）。拉格朗日乘子λ在所有t ∈ T和e �t的情况下，如果Πe(cλt) = cλe，则它们是弧一致的。0然而，需要注意的是，弧一致性对于对偶最优性并非必要条件。必要的条件是边-三角形一致性。0定义10（边-三角形一致性）。如果存在非空子集ξe �cλe（对于所有e ∈ E）和ξt � cλt（对于所有t ∈T），使得ξ是弧一致的，即对于所有t ∈ T和e � t，ξe =Πe(ξt)。0换句话说，边-三角形一致性表示存在一组局部最优解（在[56]中也称为核心）是弧一致的。0定理11. 算法2收敛到边-三角形一致性。03.3. 原始-对偶更新0尽管我们的多切割求解器的两个构建块，即边缩减和带有消息传递的循环分离，可以单独使用来计算原始解和下界，但我们提出了一种交替的原始-对偶求解器（算法3）。在每次迭代中，我们分离循环并执行消息传递以获得重新参数化的边成本。我们使用这些重新参数化的边成本来执行并行边缩减。这种交替过程一直持续到找不到边缩减候选项为止。这种方案具有以下优点0更好的边缩减成本：第6行的重新参数化产生的边成本cλ更能指示边在最终解中是否被缩减，从而在第8行产生更好的原始更新。在某些情况下，这种方法可以使松弛（5）紧致，cλe的符号完美预测边e是否分离两个聚类还是在一个聚类中。0算法3：原始-对偶多切割0数据：图G = (V，E，c) 结果：缩减映射f：V → V'0// 将每个节点初始化为单独的聚类01 f = V → V, f(v) = v � v ∈ V02 while G has positive edges without conflicts do0// 寻找冲突循环（引理6）0)04 for iter = 1, ..., k do05 λ = Parallel-Message-Pass.(G, T) // 重新参数化边成本06 c e = c λ e � e ∈ E by (6a)08 G，f' = 并行边缩减（G）// 更新缩减映射09 f(v) = f'(f(v)) � v ∈ V010 结束0松弛（5）是紧致的，cλe的符号完美预测边e是否分离两个聚类还是在一个聚类中。0更好的循环分离：为了快速执行，我们停止对长度大于给定长度（在我们的情况下为5）的循环进行分离。由于在边缩减后再次执行循环分离，这相当于在原始图中找到更长的循环。这种方法减轻了执行更详尽和耗时的初始搜索的需求。0请注意，可以通过在原始图上进行循环分离和消息传递后记录(5)来获得有效的下界。04. 实验0我们在果蝇大脑[48]的神经元分割和Cityscapes[17]上进行无监督图像分割的多割问题上评估求解器。除非另有说明，我们使用一块NVIDIA VoltaV100（16GB）GPU进行求解，使用AMD EPYC7702进行CPU求解。我们的求解器使用CUDA [45]和Thrust[20] GPU编程框架实现。0数据集：我们选择了三个包含我们所知最大多割问题实例的数据集。这些实例可以在[51]中获取。0Connectomics-SP：包含来自果蝇大脑[48]的神经元分割问题。原始数据来自CREMI挑战[1]，由[59]获取，并由[48]转换为多个多割实例。在此转换中，[48]还通过创建超像素来减小问题规模。其中大部分实例是一个全局问题的不同裁剪。共有3个实例。110100101002505007501,00012s22s36s∫⊎different cropsell as com-81990小型（40-60万条边），中型（400-500万条边）和大型（2.8-6.5亿条边）多割实例。对于最大的问题，我们使用NVIDIA RTX 8000（48GB）GPU。0Connectomics-Raw：我们使用CREMI挑战[1]中的3个测试体积（样本A+，B+，C+）进行像素级别的直接分割，而不进行超像素转换。使用[47]将其转化为多割实例。我们报告了两种类型的实例的结果：（i）三个完整问题，底层体积的大小为1250×1250×125，约有7亿条边；（ii）通过将每个体积减半并创建相应的多割实例，创建的六个裁剪问题，每个实例包含近3.4亿条边。对于所有这些实例，我们使用NVIDIA RTX 8000（48GB）GPU。0Cityscapes：在验证集[17]中获取的59张高分辨率图像（2048×1024）上进行无监督图像分割。通过在4连通性的网格图上计算[2]产生的边亲和力，并额外对粗略采样的长程边进行计算，将其转化为多割实例。每个实例包含约200万个节点和900万条边。0算法：作为基准方法，我们选择了据我们所知，文献中最快的原始启发式方法。0GAEC[30]：贪婪加法边收缩对应于算法2，选择一条最高的边进行收缩。我们使用自己的CPU实现，比作者提供的实现快1.5倍左右。0KLj [30]：Kernighan&Lin withjoins算法执行局部移动操作，可以改善目标函数。为避免运行时间过长，使用GAEC的输出进行初始化。0GEF[40]：贪婪边固定算法类似于GAEC，但额外访问负值（斥力）边，并在它们的端点之间添加非连接约束。0BEC[28]：平衡边收缩，GAEC的一种变体，根据两个端点的大小归一化的成本选择要收缩的边。0ICP[38]：迭代循环打包算法搜索循环并贪婪地解决一个近似解决多割对偶问题的打包问题（5）。0P：我们的纯原始算法1使用最大匹配和基于生成森林的边收缩策略。0PD：我们的原始对偶算法3还额外利用了对偶信息。我们在原始图上找到长度为5的冲突循环，并在缩减图的后续迭代中找到长度为3的冲突循环。0-2.5 -2 -1.5 -1 -0.50∙10^60目标值（越低越好）0运行时间[s]0BEC GEF GAEC PD+ PD P0图4.Cityscapes数据集的原始解比较。我们的纯原始算法（P）比GAEC[30]和GEF[40]快30倍，尽管目标值较差。结合双重信息使我们的求解器（PD，PD+）在目标上甚至超过顺序求解器，同时速度快一个数量级。误差棒标记了0.25、0.75分位数。（由于运行时间过长，KLj未显示）。0∙10^6 10下界0运行时间[s]0ICP D0图5.Cityscapes数据集的下界比较。我们的并行消息传递方案（D）比ICP[38]快一个数量级，并且给出稍微更好的下界。误差棒标记了0.25、0.75分位数。00B 0.1B 0.2B 0.3B 0.4B 0.5B0实例大小|E|0运行时间[s]0GAEC PD0图6.在不同的CREMI测试数据裁剪上计算的运行时间比较，显示RAMA相对于GAEC [30]在问题规模增加方面的良好扩展性0PD+：PD的变体，始终考虑长度为5的冲突循环进行重新参数化，这可以导致更好的原始解，尽管运行时间更长。0D：我们的双循环分离算法，然后通过算法2在原始图上进行消息传递，产生下界。30%7%43%20%82000Connectomics-SP Connectomics-Raw Cityscapes0Small (3) Med. (3) Large (5) Crops (6) Full (3) (59)0方法C（×10^5）t(s) C（×10^5）t(s) C（×10^5）t(s) C（×10^8）t(s) C（×10^8）t(s) C（×10^6）t(s)0原始解0KLj [30] -1.794 3.8 -9.225 125 †††††† -1.858 5e4 GAEC [30] -1.794 0.4 -9.224 4.7 -1.512 280 -1.464 570 -2.963 1140 -1.82613 GEF [40] -1.793 0.7 -9.223 9.0 -1.511 699 -1.458 582 -2.949 1762 -1.743 14 BEC [28] -1.787 0.5 -9.199 5.6 -1.507 309-1.402 1688 -2.838 4150 -1.613 36 P -1.780 0.1 -9.173 0.6 -1.505 6 -1.430 9 -2.895 19 -1.711 0.4 PD -1.791 0.2 -9.217 1.0-1.509 13 -1.477 24 -2.981 32 -1.846 1 PD+ -1.791 0.3 -9.219 1.4 -1.509 20 -1.480 115 -2.995 224 -1.862 2.20双重解0ICP [38] -1.798 0.8 -9.246 11.3 -1.518 1235 -1.507 513 -3.053 1091 -1.930 41.1 D -1.797 0.2 -9.241 0.8 -1.517 13 -1.49934 ** -1.928 1.30表1.在所有数据集上的结果比较（C：成本，t(s)：时间（秒），†：超时，*：GPU内存不足）。我们报告每个类别内实例的平均原始和双重成本和运行时间。在原始解方面，我们的原始-双重求解器（PD，PD+）实现了接近或优于顺序求解器的目标，同时速度明显更快，特别是在较大的实例上。此外，我们的并行消息传递方法（D）在运行时间上给出了比ICP更好的下界，减少了两个数量级。0在表1中给出了所有数据集上的讨论结果。在Connectomics-SP数据集上，我们获得的原始目标与GAEC[30]非常接近，但在大型实例上速度快了一个数量级。对于Cityscapes和Connectomics-Raw数据集，我们不仅通过结合双重信息获得了比顺序算法更好的原始解，而且速度也更快。我们最好的求解器（PD+）超过了10^4。0比KLj[30]快10倍，并且产生更好的解决方案。Cityscapes的所有实例的运行时间和原始目标分布分别显示在图4和图5中。我们在图6中比较了我们的求解器随着实例规模增加的扩展行为，结果显示RAMA比GAEC更高效。附录中的图7给出了结果的一个视觉比较示例。最后，我们的双重算法（D）产生了高达两个数量级的加速和更好的下界，与串行ICP[38]相比，除了在Connectomics-Raw的完整实例上，我们的GPU内存不足。0运行时间分解我们的PD算法的运行时间分解如表2所示。大部分时间都花在寻找冲突循环上，我们发现在GPU上实现这一点既具有挑战性，又能保持运行时间和内存消耗较低。未来的改进有可能通过更高效地找到更长的循环来实现更好的结果和加速。05. 结论0我们已经证明了多切割是一种重要的组合优化问题，适用于机器学习和0找到S合同。循环消息传递0表2. PD算法在Cityscapes上的运行时间分解0计算机视觉可以在GPU上有效并行化。我们的方法在网格图上产生了比现有高效启发式算法更好的解决方案，在超像素图上产生了与之相当的解决方案，同时速度提高了一到两个数量级。我们认为超像素图上的性能差距是由于图结构包含更多（更长）的冲突循环。由于我们的实现只能找到长度最多为5的循环，能够高效处理更长循环的更好实现可能会带来进一步的改进。0与CPU算法相比，执行速度是限制因素，对于我们的GPU算法，相对较小的GPU内存量限制了应用程序的规模。我们希望我们的工作能够实现更多计算密集型的多切割应用，迄今为止，较慢的串行CPU代码路径一直阻碍了其采用。06. 致谢0我们要感谢Shweta Mahajan和Jan-HendrikLange的深入讨论，以及Constantin Pape，AdrianWolny和AnnaKreshuk对实验的建议。我们还要感谢所有匿名审稿人的宝贵反馈。[19] LLC Gurobi Optimization. Gurobi optimizer reference man-ual, 2019. 282010参考文献0[1]  CREMIMICCAI电子显微镜图像电路重建挑战。https://cremi.org。  6 ,  70[2]  Ahmed Abbas和PaulSwoboda。用于全景分割的组合优化：一种完全可微的方法。神经信息处理系统进展，34，2021年。  1 ,  70[3]  Amir Alush和JacobGoldberger。使用高效整数线性规划的集成分割。IEEE模式分析与机器智能交易，34（10）：1966-1977，2012年。  20[4]  Amir Alush和JacobGoldberger。打破和征服：用于图像分割的高效相关聚类。在基于相似性的模式识别国际研讨会上，第134-147页。Springer，2013年。  10[5]  Bjoern Andres, J ¨ org H. Kappes, Thorsten Beier, UllrichK ¨ othe, and Fred A. Hamprecht.具有封闭性约束的概率图像分割。在ICCV，2011年。  10[6]  Bjoern Andres，Thorben Kr ¨ oger，Kevin L. Briggman，Win- friedDenk，Natalya Korogod，Graham Knott，Ullrich K ¨ othe和Fred A.Hamprecht。用于连接组学的全局最优封闭表面分割。在ECCV，2012年。  10[7]  Bjoern Andres, Julian Yarkony, BS Manjunath, SteffenKirch- hoff, Engin Turetken, Charless C Fowlkes, andHanspeter Pfister.根据非平面超像素亲和图对平面超像素邻接图进行分割。在国际计算机视觉和模式识别能量最小化方法研讨会上，第266-279页。Springer，2013年。  10[8]  Bas Fagginger Auer and Rob H Bisseling. Bas Fagginger Auer和Rob HBisseling. Graph coarsening and clustering on the GPU.GPU上的图粗化和聚类.  Graph Partitioning and Graph Clustering , 588:223,0[9]  Alberto Bailoni, Constantin Pape, Steffen Wolf, Thorsten Beier, AnnaKreshuk, and Fred A Hamprecht. Alberto Bailoni, Constantin Pape, SteffenWolf, Thorsten Beier, Anna Kreshuk和Fred A Hamprecht. A gener- alizedframework for agglomerative clustering of signed graphs applied toinstance segmentation. 用于实例分割的带符号图的聚类的广义框架. arXivpreprint arXiv:1906.11713 , 2019.  20[10]  Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Nikhil Bansal, Avrim Blum和ShuchiChawla. Correlation clustering. 相关聚类.  Machine learning , 56(1-3):89–113, 2004.  1 ,  40[11]  Thorsten Beier, Bj ¨ orn Andres, Ullrich K ¨ othe, and Fred A Hamprecht.Thorsten Beier, Bj ¨ orn Andres, Ullrich K ¨ othe和Fred A Hamprecht. Anefficient fusion move algorithm for the mini- mum cost lifted multicutproblem. 用于最小成本提升多切问题的高效融合移动算法. In  Europe