并行二次伪布尔优化算法在图像分割中的应用

6260基于并行二次伪布尔优化的放大图片作者：Patrick M.Jensen，Anders N.作者：Christensen，Anders B.Dahl和VedranaA.应用数学与计算机科学丹麦技术大学，Kgs。Lyngby{niejep，patmjen，anym，abda，vand}@ dtu.dk摘要我 们 介 绍 了 一 个 并 行 版 本 的 二 次 伪 布 尔 优 化（QPBO）算法解决二进制优化任务，如图像分割。Kolmogorov和Rother的原始QPBO实现依赖于Boykov-Kolmogorov（BK）maxflow/mincut算法，并且对于许多图像分析任务表现良好。然而，其QPBO算法的串行性质导致现代硬件的利用率很差。通过重新设计的QPBO算法与并行最大流/最小割算法，我们显着减少大型优化任务的求解时间我们比较我们的并行QPBO实现其他国家的最先进的求解器和基准测试他们两个大的分割任务和大量的小segmenta-灰任务。结果表明，并行QPBO算法在大任务上比串行QPBO算法快20倍以上，在小任务上比串行QPBO算法快3倍以上虽然我们专注于图像分割，我们的算法是通用的，可以用于任何QPBO 问 题 。 我 们 的 实 现 和 实 验 结 果 可 在 DOI ：10.5281/zenodo.52016201. 介绍计算并行性对于许多图像分割算法的性能和实用性是必不可少的最好的例子也许是深度学习，它的成功很大程度上归功于在训练和推理过程中使用的矩阵运算然而，并非所有用于计算机视觉的算法都依赖于易于并行化的矩阵运算。图割算法由于其速度快和保证最优性而被广泛用于解决图像分析中的二进制优化问题。因此，它们为各种计算机视觉问题提供了有效的解决方案-单独[ 8，9，11，16，23，26，33，35 ]，或与其他方法[ 18，29，30 ]相而一些流行的图形切割算法已经被并行化[11，36，41，43]，其他算法仍然是串行的，这严重限制了它们利用现代硬件的能力。一个示例是二次伪布尔优化（QPBO）算法[7，19，33，39]，其允许非子模能量项，使得其对于实例分割特别有用。没有训练数据的实例分割在显微镜和材料科学中是常见的，其中手动标记大体积数据集可能是非常不切实际的。通常，使用QPBO进行分割所需的输入可以更容易地获得。本文介绍了第一种并行QPBO算法（P-QPBO）.我们的目标是提供一个有效的和可扩展的算法，可以利用现代多核处理器。与我们的P-QPBO算法，结果可以得到一个数量级的速度比以前的串行方法，任务的规模可以显着增加。它使我们能够在几分钟内基于有限的用户输入和没有训练数据分割具有数百个交互3D对象虽然我们只证明了P-QPBO的图像分割的优势，P-QPBO可以用于任何QPBO问题。这项工作的重点是我们的并行算法和它的时间和内存效率的图像分割任务。因此，为特定的计算机视觉任务制定合适的能量函数超出了本文的范围。1.1. 相关工作已经开发了几种算法来解决QPBO问题[19，32，33]。在计算机视觉中，由Kolmogorov和Rother [33，39]实现的QPBO算法[7，19]利用串行Boykov-Kolmogorovmaxflow/mincut（BK）算法[9]来解决优化问题，可以说是最流行的。一般来说，maxflow/mincut算法可以分为三组[42]：push-relabel算法[3，10，14，15]，增强路径算法[9，17]和pseudoflow算法[16，20，21]，它们是前两类算法的混合。BK是一种增广路径算法。是6261V ∈ {}∈ V ∈ V222222在计算机视觉中最流行的maxflow/mincut算法，由于其处理动态maxflow/mincut场景的性能和能力，通过在对图进行改变时重用来自先前解决方案的计算[31]。在过去的十年中，伪流算法，如Excesses In-maxflow/mincut算法可用于最小化以下形式的能量函数E（x）= Σθ p（x p）+ Σθ pq（x p，xq）.（一）p∈Vp，q∈Vcremental广度优先搜索（EIBFS）[16]在大多数静态情况下以及一些动态情况下形成BK。但是，与动态问题的图更改相关的开销对于EIBFS仍然高于BK。推送重标记算法传统上是大多数并行化努力的目标[2，5，11，13，22，43]，因为操作主要在本地进行，使它们非常适合并行执行。然而，同步开销意味着需要许多线程来实现良好的性能[6，40]。最近的工作[36，40，41，44，45]集中在并行增广路径算法。这里，图被划分成多个子图，并且串行算法被并行地应用于每个子图。然后，信息在子图之间传播，或者它们被合并。重复该过程，直到找到全局解。并行伪流算法尚未尝试。最后，由于基于网格的图在计算机视觉中相对常见，因此也开发了专门用于这种结构的算法，例如Grid-Cut [24，25]。网格结构图也是基于GPU的实现的目标[38，43]，因为它们依赖于网格图的高度规则结构来充分利用GPU。虽然基于网格的算法实现了显着的性能改进，provements，他们只适用于有限的（但肯定是重要的）子集的二进制优化问题。在本文中，我们关注的是一个通用并行这里，是一组节点，x p0，1是节点标签，θp是一元能量项，θpq是成对能量项。如果E是次模的，意味着所有成对能量满足θpq（0，0）+θpq（1，1）≤θpq（0，1）+θpq（1，0），（2）则保证基于最大流/最小切的算法（包括QPBO）找到最小化问题的全局最优解[9，33]。然而，如果能量函数包含非子模项，我们不能直接将其建模为最大流/最小割问题[12，34]。为了克服该限制，QPBO算法使用扩展的图形方法，其中每个节点由两个图形节点表示：节点p和翻转节点p。每个能量项然后由两个图边缘表示（参见表1）。这允许非子模项被表示为节点p和q以及翻转的节点p和q之间的图边。计算该扩展图的最大流/最小割对应于最小化能量函数（1）[33]，假定所有项都是非负的。可以使用[33]中描述的线性时间算法将QPBO函数转换为等效的表1.从能量项到图边的转换[33]，其中s是源节点，t是汇节点，p，q∈ V是节点p，q∈ V的翻转版本。QPBO算法，因此将不讨论网格-算法进一步。1.2. 贡献我们介绍了一个快速并行算法解决QPBO问题。它基于如[33]中所提出的QPBO算法的有效两阶段方法和来自[36]的自底向上合并方法。我们的算法是完全兼容的原始QPBO算法，我们证明，它是保证找到等价的解决方案。我们表明，我们的并行算法减少了解决时间显着的一个大型多对象的3D分割任务相比，目前最先进的方法。我们还基准我们的算法分割使用一个大的2D图像集，并显示显着的性能改善，即使是较小的分割任务。我们的实现，基准代码，结果，笔记本和证明可在10.5281/zenodo.5201620获得。2. QPBO我们在这里简要总结原始QPBO算法。QPBO算法和通用能量项对应边边容量θp（0）（p→t），（s→p）1θp（0）θp（1）（s→p），（p→t）1θp（1）θpq（0，1）（p→q），（q→p）1θpq（0，1）θpq（1，0）（q→p），（p→q）1θpq（1，0）θpq（0，0）（p→q），（q→p）1θpq（0，0）θpq（1，1）（q→p），（p→q）1θpq（1，1）然而，对非子模项的支持意味着找到全局最优解的保证被找到部分最优解的保证所取代[33]。这意味着我们可能会得到一个具有未标记节点的解决方案，这可能会导致不好的分割结果[23]。然而，当非次模项仅用于排除时，[26]已经表明，未标记的节点是罕见的，几乎不影响得到的分割。原始QPBO算法使用有效的两阶段方法[33]。在阶段1中，仅考虑子模项，并且将问题建模并作为常规问题求解。6262W WW{|∈ V}W WWV V VVV ∪ V EE{→∈ E |∈ W}G {W} EGG最大流问题，即，没有翻转的节点。在阶段2中，通过从阶段1复制残差图并反转边缘来创建翻转图最后，添加非子模项的边并更新解。这种两阶段的方法显著地减少了求解时间，但是依赖于可以有效地处理动态图的maxflow求解器，例如BK算法[31]。3. 并行QPBO我们现在描述我们的新并行QPBO（P-QPBO）算法，其将第2节中描述的两阶段QPBO方法与Liu和Sun[36]的自底向上合并并行化方法相从以前的工作[36，40，41，44，45]来看像刘和孙在阶段A中，QPBO问题被分成不相交的子问题，这些子问题被并行地独立求解在阶段B中，这些部分解被合并并重新求解，也是并行的，以得到完整的解。注意，阶段A/B严格地指的是子问题的拆分和合并。阶段1/2是指与子问题相关联的子图是否已经添加了翻转图。与 Liu 和 Sun 的 算 法 相 比 ， 该 算 法 严 格 用 作maxflow/mincut求解器，我们的算法还将每个子问题视为QPBO问题。具体来说，每个子问题都保留在阶段1中（在那里我们不需要翻转图），只要它只包含子模块项。因此，在非子模项很少的情况下，对于阶段A和阶段B中的大多数，大多数子问题将保留在阶段1中。这大大缩短了求解时间。我们现在将描述这两个阶段，包括特定条件，这将触发子问题转换到阶段2图1显示了一个可视化摘要。阶段A：QPBO问题的划分通过分裂底层图来完成。 我们将节点集分成N个不相交的集合1，2，…， N.这给出了图节点到块1、2、…其中i=p，ppi。然后，对于由一个或多个边缘连接的每对块i、 j，我们识别块间边缘并将这些存储在单独的列表中。从现在开始我们将这些边列表称为块接口。在构建块接口之后，我们从中移除块间边缘。我们现在有一系列子图i=i，s，t，i其中i=（p q）p，qi.因为这些子图是不连通的，除了通过源和宿节点，我们可以并行计算它们各自的maxflow解决方案（见图1a）。对于每个子图，我们采用串行QPBO算法的两阶段方法。首先，我们只考虑子模项，不添加翻转图。然后，当（且仅当）子图包含非子模项时，我们将子图转换为Stage2. 在此转换过程中，将构建翻转图通过从阶段1复制残差图，添加剩余的非子模边，并且更新最大流解（参见图1b）。当所有的子图都被解决后，我们进入阶段B。阶段B：在该阶段中，我们合并子图以重新创建原始扩展图。通过重新添加在阶段A中移除的块间边缘来完成合并两个子图。如果所有子图和块间边对应于子模项，则我们将两个子图保持在阶段1中（参见图1c）。如果一些块间边缘对应于非子模项，则在添加块间边缘（参见图1e）之前，将两个此外，如果两个子图处于不同阶段，则在重新添加块间边缘并且合并子图之前，将阶段1中的子图变换到阶段2（参见图If）。在合并之后，更新组合图的解。为了进一步减少求解时间，我们希望合并并行发生，为此我们使用[36]中的策略。更新maxflow解决方案是一个串行过程，因此一次只能有一个线程处理子图。对于同步，每个子图可以被锁定（意味着它正在被处理）或解锁（意味着它对于合并是自由的）。为了决定要合并哪些子图，每个线程扫描在阶段A中创建的块接口的列表，直到它找到连接两个未锁定的子图的块接口。线程然后锁定子图并合并它们。然后，它重新计算合并子图的最大流解注意，在子图已经被合并之后，可以存在连接先前合并的子图的若干块接口。因此，当线程找到要合并的一对子图时，它继续扫描块接口的列表以找到连接该对子图的所有块接口。然后从全局列表中删除块接口全局同步对象用于确保一次只有在阶段B结束时，剩余的合并数将少于运行线程的数量（除非只使用一个线程）。因此，如果线程扫描块接口的整个列表而没有遇到一对未锁定的子图，则其终止。 因此，并行度在接近阶段结束时逐渐减小B.但是，对于大多数问题，最后一次合并所需的时间与总求解时间相比很小。总的来说，执行的合并的数量将比块的数量少一个。算法1中总结了每个线程的过程。3.1. 正确性我们的P-QPBO算法将始终给出与串行QPBO算法的解等价的解能量：解的能量由唯一的6263∈ V∈ V图1.合并策略的图示。 蓝色点和线表示非翻转图中的节点和边，而红色点和线是翻转图中的节点和边。绿线表示节点p和翻转节点q之间的边，对应于非子模项。虚线表示块间边缘，其在子图被合并时被重新添加。两个蓝色节点之间的绿色虚线除外这些表示非子模能量项，一旦添加翻转的图，其将被转换为边。未示出源/宿节点和边缘。（a）将图分成子图，并且并行计算每个子图的阶段1解（b）子图A包含内部非子模项，因此将其变换到阶段2并且更新解（c）合并子图D和E重新添加块间边缘并且更新子图解决方案。由于所有块内和块间项都是子模块化的，因此子图保持在阶段1中。（d）B和C之间的项是非子模的，因此子图被变换到阶段2以准备合并。（e）合并子图B和C（f）子图D + E被转移到阶段2以允许与剩余子图合并所有子图现在都处于阶段2，并且合并可以像正常的自底向上合并那样进行。扩展图的最小切割的值。由于串行和并行算法的最终图是相同的，并且它们都计算最小割，因此解必须具有相同的能量。标记：可能存在具有相同成本/能量但标记不同数量的节点的若干最小切割[33]。然而，给定一个残差图，[4，33]中的算法将选择标记最大节点数的最小割。可以示出（补充材料中的证明），由于QPBO和P-QPBO都计算相同图的最小切割，因此它们必须在运行该额外算法之后标记相同的节点由于这个额外的步骤是整个运行时的一个无关紧要的部分，所以我们不将其包括在我们的运行时实验中。3.2. 高效的图划分和合并将图节点划分成块对于P-QPBO算法的性能是重要的。虽然我们的方法允许对节点进行任何划分，但理想情况下，我们希望在阶段A（计算部分解）中完成尽可能多的工作，而在阶段B（计算部分解）中完成尽可能少的工作。在阶段B中完成（合并子图和更新解）。实现这一点的一个好方法是将节点分成密集封装（许多块内项）和稀疏相关（很少块间项）的块这通过减少对图形所做的更改的数量来加速合并当然，理想的划分在很大程度上取决于能量函数。对于图像分割，我们可以在将节点/像素分割成块时使用它们的空间位置只要块不是很小，与块间项相比，将图像切割成均匀大小的矩形块，如[36，41当使用稀疏分层图（SLG）[26]解决实例分割任务当对象之间的交互与对象的大小相比很低时（通常是这种情况），并且我们至少有与系统上可用的并行线程数量一样多的对象时，这很有效。我们使用这种自然的方式来划分我们所有的实验节点，因为我们的大多数图像包含许多对象。6264∅GGGGGG{|{\fn方正粗倩简体\fs12\b1\bord1\shad1\3cH2F2F2F}G GGGGGG×× ×算法1：并行QPBO算法的阶段B每个线程的Rithm。而真正的锁定同步对象设S=foreach块接口的do设i和j是由s如果i和j都未锁定，则S=sisi连接i和j断开从块接口列表中删除S如果S为空，则解锁同步对象返回锁定由S连接的子图i和j解锁同步对象/* 如果需要，确保子图处于阶段2。*/如果S包含非子模项或阶段2中的Gi或阶段2中的Gj，然后将Gi变换到阶段2然后将Gj变换到阶段2将子图i和j合并为子图ij/* 重新插入边界边 */对于Sdo中的每个块间边缘e在图形中重新插入e如果ij在阶段2中，则在图形中重新插入e的翻转边如果a的节点具有不同的标签，则将重新插入的边的节点标记为活动更新子图ij的最大流/* 使ij可用于合并 */锁定同步对象解锁子图ij解锁同步对象为了确定合并顺序，P-QPBO使用与Liu和Sun [36]相同的方法。在阶段A之后，当合并包含块的子图时，我们在每个块接口上循环并且对潜在的新扩充路径的数量进行计数。这用作在合并子图时必须完成多少工作然后，块接口的列表根据潜在的新扩充路径的数量以降序排序，希望线程将首先执行最昂贵的目标是在阶段B的早期尽可能多地完成工作，同时并行度很高。4. 基准测试结果为了测试我们的P-QPBO算法的可扩展性，我们比较它与两个串行QPBO实现。第一个是Kolmogorov对原始QPBO算法的稍微优化的实现-我们使用稍微修改过的版本的实现对于大型图具有溢出问题。第二个串行实现是我们自己对K-QPBO的重新实现，它包含了许多数据结构的改进和代码的优化，从而提高了性能。我们将这种实现称为现代QPBO（M-QPBO）。包括M-QPBO以提供串行和并行实现之间的更公平的比较，因为M-QPBO包含与P-QPBO相同的性能当参考我们的并行实现的结果时，我们使用符号P-QPBO（t），其中t是P-QPBO使用的并行线程的数量。我们在[26]中使用的两个数据集上测试QPBO实现，并使用[27]中共享的确切能量函数。我们的笔记本（基于[27]）用于制定能量函数和基准QPBO算法，包含在我们的补充材料（DOI：5201620）。然而，由于我们在这篇文章中的重点是纯粹的计算性能，能量公式不包括在本文中。用于我们实验的第一个数据集是神经的高分辨率µCT 3D图像[28]，如图2a所示。这是具有许多非重叠对象的大型分割任务它允许我们测试跨许多CPU线程的并行QPBO实现的可扩展性。第二个数据集是来自BroadBioimageBenchmarkCollection[37]的BBBC038v1stage1 train（S1）图2b中示出了来自数据集的图像以及实例分割结果。使用这些图像，年龄，我们测试各种小型和中型的分割任务的QPBO实现的性能对于这两个数据集，能量函数创建由不规则互连的有序多列子图组成的非平凡图拓扑。与一般的最大流问题不同，其中存在许多常用的基准数据集[16]，没有专门用于QPBO的常用基准数据集。我们在所有基准测试中使用双插槽配置的两个IntelXeon Gold 6226 R（16核/16有了这个，我们测试我们的实现如何在一个现代的，ern架构上的规模高达32个线程并行执行。4.1. 大型细分任务该实验的目标是比较K-QPBO和M-QPBO与P-QPBO在大型分割任务上在各种并行线程计数下的求解虽然解决时间不同的系统架构，这个实验显示使用P-QPBO的好处，这取决于可用的CPU内核的数量在实验中，我们使用[26]的SLG方法，以两种不同的径向采样分辨率分割2048 2048 2048体积中的216个神经的髓鞘和轴突。第一分辨率（N1）是[26]所使用的分辨率，而第二分辨率（N2）更高，导致图形更如如6265（（图2.（a）N1神经分割任务的结果。节点被分割成块，使得与神经的内表面（红色）或外表面（蓝色）相关联的所有节点（b）来自S1的具有最多细胞核的图像上的细胞核分割的示例。节点被分割成块，使得与单元相关联的所有节点在同一块中（每个单元一个块）。是N1的两倍（见表2）。在这两种情况下，输出是具有总共432个交互对象（每个神经两个）的3D多标签分割。对于P-QPBO，我们每个对象使用一个块（参见图2a）。如表2所示，与K-QPBO实现相比，我们的M-QPBO实现将N1任务的求解时间减少了25%，而P-QPBO（1）对于该任务的性能略优于M-QPBO，与K-QPBO相比减少了33%，仅使用单个线程。使用两个线程，与K-QPBO相比，P-QPBO（2）提供求解时间减少62%使用40个线程实现最佳结果，在这种情况下，P-QPBO比K-QPBO快11倍以上。图3a示出了与K-QPBO相比使用P-QPBO时的相对加速。我们看到，性能提高到并超过了我们的测试系统中的CPU内核数量（32）对于更大的N2任务，我们观察到P-QPBO比N1更大的性能改进和更好的缩放（参见图3b）。从表2中的求解时间，我们看到，即使没有并行性，自下而上的合并策略与K-QPBO相比，P-QPBO（1）的求解时间减少了51%。同时，M-QPBO提供了相对于K-QPBO的26%的减少换句话说，P-QPBO随着任务的增长而明显地提高了其相对性能，而M-QPBO对于N1和N2表现类似当观察相对于K-QPBO的相对改进时图3a和图3b都示出了超过16个线程时加速增加显著更少这是意料之中的，因为我们正在双插槽系统上进行测试，这意味着当使用两个CPU时，我们可能会遇到一定程度的计算开销，尤其是对于高速缓存和内存密集型系统表2.神经分割任务的图形详细信息。节点和边是指完全扩展图的大小内存占用是图形和相关簿记的总内存占用。P-QPBO和M-QPBO对N1使用32位索引，但对N2使用64位边缘索引，因为它具有多于2个31个边缘。K-QPBO始终使用64位指针进行索引。示出了三种算法中的每一种的求解时间，其中P-QPBO具有许多不同的线程配置。每次求解时间最少为N1的十次运行和N2的三次运行。例如计算最大流量的任务。然而，尽管有开销，组合的32个CPU核允许P-QPBO针对Nl和N2两者扩展超过32个线程，其中P-QPBO（40）在两种情况下都显著优于P-QPBO（32）这可能是由于某些线程在等待释放同步锁时处于空闲状态。P-QPBO随线程数量缩放的方式的另一个原因是在阶段B结束时并行度的降低根据Amdahl对于神经分割任务，我们估计了0.88而N1和N2分别为0.92（包括开销），这意味着大部分工作是并行完成的。我们预期M-QPBO相对于K-QPBO的大部分性能改进是由于表2中所示的图的较小的存储器占用。我们通过使用更紧凑的数据结构的节点和边缘来实现这种减少。在可能的情况下，我们使用32位索引，而不是64位指针。此外，我们在内存中存储相邻的前向和后向边，以 避免在这些边 之间存储指 针. P-QPBO和M-QPBO对节点和边使用相同的基本数据结构。增加的N1N2节点363,748,800818,434,800边缘2,124,073,4544,864,255,488内存占用K-QPBO [33]134.2 GB306.8 GBM-QPBO60.1 GB182.7 GBP-QPBO70.0 GB224.9 GB最快解算时间K-QPBO [33]836s四千九百八十七秒M-QPBO628s3,704秒P-QPBO（1）558S2,429秒P-QPBO（16）94年代323 sP-QPBO（32）80后264秒P-QPBO（40）74s245秒P-QPBO（48）76秒239秒6266（a）K-QPBOM-QPBOP-QPBOAmdahl定律拟合K-QPBO（一）求解时间提速（次）求解时间提速（次）122010八一五六点十分452012 4 8 16 24 32 40 48 56 64的线程012 4 8 16 24 32 40 48 56 64的线程图3.图显示了与K-QPBO和M-QPBO相比，使用P-QPBO时求解时间的相对加速使用N1的十次运行和N2的三次运行中的最快求解时间计算加速。K-QPBO和M-QPBO表示为水平线，因为它们总是使用单个线程。我们还展示了Amdahl定律[ 1 ]和平行分数p的拟合请记住，使用了两个16核CPU，这意味着当使用超过32个并行线程时，我们预计加速会停滞甚至对于这些任务，在我们的测试系统上，停滞似乎从40个线程开始六、六五、五四四三三二、二第11章0个0个图4.箱形图显示了M-QPBO和P-QPBO与K-QPBO相比，S1数据集中每个图像的相对加速。根据Tukey离群值定义为距离最近的四分位数的四分位间距的1.5倍以上的值，并显示为环。在（a）中，示出了所有670个图像的结果，而（b）仅包括具有16个或更多个核的502个图像使用每种方法的最快求解时间计算相对加速，其中每种方法已运行十次。P-QPBO图的存储器占用是自底向上合并所需的额外簿记的结果。由于两个原因，减少图结构的存储器占用是重要的1)由于CPU缓存和内存效率的提高，它提高了性能。2)它允许我们在不耗尽内存的情况下解决更大的任务。重要的是要记住，缩放取决于优化问题和系统架构。通常，由于合并子图的开销，我们期望M-QPBO在较小的任务然而，对于大型任务，使用自底向上的合并，即使没有并行计算，实际上也会更快。这种行为之前由[16，36]指出，并且可能是由于较短的增强路径和更好的缓存效率的组合。对于N1任务，[26]报告了K-QPBO的求解时间为44分钟，远高于我们在实验中发现的14分钟我们怀疑主要原因因为最大的区别是他们的系统只有112 GB内存，而图中的内存占用至少为134 GB。这可能会导致内存交换，这可能会对性能产生负面影响。4.2. 较小的细分任务我们使用先前在[26]中使用的S1数据集来比较P-QPBO，M-QPBO和K-QPBO在不同大小的2D（非网格）分割问题上图5示出了图像的图节点和边的分布。中值为437，400个节点和1，598，060条边，我们认为这些分割任务中的大多数相对较小。有几个任务要大得多，最大的任务（如图2b所示）有600多万个节点和6000万条边。为了检查M-QPBO和P-QPBO对于这些小型到中型任务的整体性能，我们计算当使用我们的实现时与K-QPBO相比的相对（b）K-QPBOM-QPBOP-QPBOAmdahl定律拟合求解时间提速（次）K-QPBO（b）第（1）款求解时间提速（次）6267最小值= 16 K中位= 0.4 M最大值= 6 M±100200内存最佳加速N1 N1 S150100M-QPBO 60.1GB 1.33 1.72±0.2800 2 4 6节点1e600 2 4 6边缘1e7P-QPBO 70.0 GB10.47 2.96±0.89刘孙[36] 70.0GB 6.07 0.78±0.13图5.在S1中分割图像时使用的图的节点和边的分布直方图图4示出了针对数据集中的每个图像（图4a）和针对具有16个或更多个核的每个图像（图4b）的M-QPBO和P-QPBO的相对加速与K-QPBO相比，M-QPBO和P-QPBO均显示出显著的改善。当我们包含所有图像时，存在相对性能下降的情况在这些少数情况下，任务非常小（很少节点和项），使得P-QPBO的开销超过益处。如果我们仅查看具有16个或更多个核（259，200个节点或更多）的502个图像对于这些较小的任务，合并块的开销不会被较短的增强路径所超过。因此，当仅使用单个线程时，无需自底向上合并即可实现最佳对于具有16个或更多个核的图像（图4 b），M-QPBO给出 1.8x的中值 加速，最 大为2.5x。P-QPBO（4）实现了最佳的整体性能，中值加速为3.2倍，最大加速为5.3倍。虽然P-QPBO（6）和P-QPBO（8）在一些最大的任务中表现出最佳性能，但与使用四个线程相比，总体性能略有下降，这是由于大多数任务相对较小。4.3.与其他求解器的我 们 比 较 P-QPBO 与 其 他 国 家 的 最 先 进 的maxflow/mincut算法。为了测试两阶段QPBO策略的效果 ， 我 们 将 其 与 我 们 自 己 的 Liu 和 Sun [36] 的 并 行maxflow/mincut 算 法的 实现 进行 此外 ， 我们 与串 行EIBFS算法[16]进行了比较，因为它是目前最快的串行最大流/最小割求解器，并且我们与我们自己的基于自底向上合并的EIBFS（P-EIBFS）最后，我们包括一个最好的情况下估计的QPBO实现使用EIBFS作为其最大流/mincut求解器（EIBFS-QPBO）。我们比较了N1和S1任务的算法。的maxflow/mincut算法进行评估，首先转换，ING的QPBO问题的充分扩展的图，然后运行该算法在这个图。我们在基准测试中不包括此转换时间。结果如表3所示。我们看到，我们的算法显着优于其他方法。EIBFS [16] 175.1GB 1.08 0.33±0.08P-EIBFS 175.8GB 0.63 0.68±0.14EIBFS-QPBO* 175.1GB 2.17 0.66±0.08* 最佳情况估计（EIBFS求解时间的一半）。表3.烧蚀实验结果。 我们考虑N1最多32个线程，S1最多16个线程。我们报告记忆和最佳加速N1和最佳平均标 准 。 加 速 S1 数 据 。 加 速 是 根 据 w.r.t. K-QPBOmaxflow/mincut解算器在完全扩展图上运行。我们不包括用于将QPBO问题转换为图形的时间5. 结论我们的P-QPBO算法是第一个并行QPBO算法。它比现代多核硬件上的串行K-QPBO算法更好地扩展，通过将任务划分为子任务并并行解决它们。它使用自下而上的合并策略来合并解决方案，也是并行的。这使得P-QPBO能够比当前算法更快地解决图像分割等任务。我们的实验表明，P-QPBO解决大型多对象分割任务的速度比K-QPBO快20倍以上它这样做，同时保持与K-QPBO完全兼容，不对图形结构进行约束假设即使对于较小的任务，只有几十万个节点，P-QPBO也比K-QPBO快2-5倍，只使用四个线程。这表明P-QPBO将显著优于K-QPBO，即使在消费者硬件上也是如此。当与现代硬件结合时，P-QPBO的可扩展性此外，由于它是一个并行算法，我们预计P-QPBO的相对性能，以保持在未来增加。最后，P-QPBO是一种通用算法，适用于许多二进制优化任务，而不仅仅是图像分割。因此，我们相信P-QPBO不仅可以用于更快的图像分割，而且还可以用于计算机视觉和其他领域的各种确认这 项 工 作 得 到 了 FORCE Technology 和 MAX IV（QIM）成像数据量化中心的支持。最小值= 48 K中位= 2 M最大值= 60 M6268引用[1] 吉恩·M·阿姆达尔单处理器方法实现大规模计算能力的有效性在1967年4月18-20日春季联合计算机会议的会议录中，第483-485页六、七[2] Richard Anderson和Joao C.塞图巴尔最大流问题的推重标记算法的并行实现。Journal of Parallel and DistributedComputing（JPDC），29（1）：17-26，1995. 二个[3] Chetan Arora、Subhashis Banerjee、Prem Kalra和SN Ma-heshwari。计算机视觉问题的一种高效图割算法。欧洲计算机视觉会议论文集，第552-565页，2010年一个[4] Bengt Aspvall，Michael F Plass，and Robert Endre Tarjan.一种线性时间算法，用于检验某些量化布尔公式的真实性Information Processing Letters，8（3）：121四个[5] David A Bader和Vipin Sachdeva。一个缓存感知并行实现的推重标记网络流算法和实验评估的差距重标记启发式。技术报告，佐治亚理工学院，2006年。二个[6] Niklas Baumstark，Guy Blelloch，and Julian Shun.同步并行推重标记算法的高效实现。欧洲算法研讨会论文集（ESA），第106-117页，2015年。二个[7] Endre Boros，Peter L Hammer和Xiaorong Sun。网络流与二次伪布尔函数的极小化。技术报告，技术报告RRR17-1991，RUTCOR，1991年。一个[8] 尤里·博伊科夫和加雷斯·芬卡·李图割和有效的N-D图像分 割 。 International Journal of Computer Vision ， 70（2）：109-131，nov 2006. 一个[9] 尤里·博伊科夫和弗拉基米尔·科尔莫戈洛夫。最小割/最大流算法在视觉中IEEE Transactions on Pattern Analysisand Machine Intelligence（PAMI），26（9）：1124一、二[10] Boris V Cherkassky和Andrew V Goldberg。关于最大流问题的推-重标记方法的实现Algorithmica，19（4）：390-410，1997. 一个[11] 安德鲁·德隆和尤里·博伊科夫。ND网格的可扩展图割在IEEE计算机视觉和模式识别会议（CVPR）中，第1-8页一、二[12] 丹尼尔·弗里德曼和彼得罗斯·德里纳斯。通过图切割的能量最小化：解决什么是可能的。 在IEEE计算机视觉和模式识别会议（CVPR）的会议记录中，第939-946页，2005年。二个[13] 安德鲁·V·戈德堡最大流算法的处理器高效实现。Information Processing Letters ， 38 （ 4 ） ： 179-185 ，1991. 二个[14] 安德鲁·V·戈德堡最大流问题的部分增广-重标号算法。欧洲算法研讨会论文集（ESA），第466-477页，2008年1[15] 安德鲁·V·戈德堡最大流问题的两级推重标记算法在我店国际会议Algorithmic Applications in Management，第212-225页，2009年。一个[16] Andrew V Goldberg，Sagi Hed，Haim Kaplan，PushmeetKohli，Robert E Tarjan，and Renato F Werneck.更快和更动态的最大流增量广度优先搜索。欧洲算法研讨会论文集，第619-630页，2015年一、二、五、七、八[17] Andrew V Goldberg，Sagi Hed，Haim Kaplan，Robert ETarjan，and Renato F Werneck.增量广度优先搜索的最大流 在 Proceedings of the European Symphony Algorithms（ESA），第457-468页，2011中。一个[18] Zhihui Guo ， Ling Zhang ， Le Lu ， MohammadhadiBagheri，Ronald M Summers，Milan Sonka，and JianhuaYao.深度LOGISMOS：基于深度学习图的CT扫描胰腺肿瘤3D分割第1230-1233页，2018年。一个[19] Peter L Hammer，Pierre Hansen，and Bruno Simeone.二次0-1最优化问题的屋顶对偶性、互补性和持续性。Mathematical Programming，28（2）：121-155，1984.一个[20] Dorit S.霍克鲍姆伪流算法：一种求解最大流问题的新算法Operations Research，56（4）：992-1009，2008. 一个[21] Dorit S. Hochbaum和James B.奥林伪流算法的简化和加速。Networks，61（1）：40- 57，2013. 一个[22] 柏宏和何正宇。非阻塞全局重标记启发式最大网络流问题的异步多线程算法IEEE Transactions on Parallel andDistributed Systems（TPDS），22（6）：1025二个[23] Hossam Isack，Olga Veksler，Ipek Oguz，Milan Sonka，and Yuri Boykov.分层结构交互段（HINTS）的有效优化。在IEEE计算机视觉和模式识别会议（CVPR）的会议记录中，第1445-1453页，2017年。一、二[24] OndˇrejJamr isˇka和DanielS y`kora。GridCut。 版本1.3。https://gridcut.com，2015年。2020-06-12访问。二个[25] OndˇrejJamr isˇka，DanielSy`kora，andAl e xanderHornung.结构化网格上的高速缓存高效图割在Proceedings of theIEEEConferenceonComputerVisionandPatternRecognition（CVPR），第3673-3680页二个[26] Niels Jeppesen ， Anders N Christensen ， Vedrana ADahl，and Anders B Dahl.用于多对象分割的