稠密CRF中线性规划能量的快速优化

3298稠密CRF1，Alban Desmaison2，Rudy Bunel2，Mathieu Salzmann3，Philip H.S. Torr2和M. PawanKumar2，41澳大利亚国立大学数据61，CSIRO2牛津大学工程科学系3计算机视觉实验室，洛桑联邦理工学院摘要条件随机场（CRF）高斯成对势已被证明是流行和有效的多类语义分割。虽然可以使用线性规划（LP）松弛精确地最小化密集CRF的能量，但是现有技术的算法太慢而不能在实践中使用。为了缓解这一不足，我们引入了一个有效的LP最小化算法密集CRF。为此，我们开发了一个proxi-mal最小化框架，其中每个proxi- mal问题的对偶我们表明，每个块的变量可以有效地优化。具体来说，对于一个块，问题分解成显着更小的子问题，其中每个是定义在一个单一的像素。对于另一个块，通过条件梯度下降来优化问题。这有两个优点：1）条件梯度可以在像素和标签的数量中线性的时间内计算;以及2）可以解析地计算最佳步长。我们在标准数据集上的实验提供了令人信服的证据，证明我们的方法优于所有现有的基线，包括以前的基于LP的密集CRF方法1. 介绍近 年 来 ， 基 于 高 斯 两 两 势 的 稠 密 条 件 随 机 场（CRF）已成为多类图像语义分割的主流。这种流行的起源在于使用有效的过滤方法[1]，该方法被证明导致线性时间平均场推理策略[12]。最近，这种过滤方法被用来使用其他通常更有效的连续松弛方法来最小化密集CRF能量[6]。在[6]中考虑的松弛中，线性规划（LP）松弛对解的质量提供了强有力的理论保证[9，15]。在[6]中，LP通过投影次梯度下降来最小化。而依赖于滤波方法，计算次梯度被证明是线性的像素数，但不是线性的。此外，即使使用线搜索策略，该算法也需要大量的迭代来收敛，这使得它效率低下。我们介绍了一个迭代LP最小化算法，一个密集的CRF与高斯成对的潜力，具有线性时间复杂度每次迭代。为此，我们建议使用邻近方法，而不是依赖于标准次梯度技术[20]。由此产生的proxi- mal问题有一个光滑的对偶，它可以有效地优化使用块坐标下降。我们表明，每个块的变量可以有效地优化具体来说，对于一个块，问题分解成显着更小的子问题，其中每个都是在一个单一的像素定义对于另一个块，可以通过Frank-Wolfe算法优化问题[8，16]。我们表明，该算法所需的特别地，我们修改了[1]的滤波方法，使得条件梯度可以在像素和标签数量的时间线性内计算。除了这种线性复杂性，我们的方法有两个额外的好处。首先，它可以用更快、更不精确的算法的解来初始化，例如平均场[12]或[6]的凸（DC）松弛的差，从而加速收敛。其次，我们的迭代过程的最佳步长可以得到分析，从而防止需要依赖于昂贵的线搜索过程。我们证明了我们的算法在MSRC和Pascal VOC 2010[7]分割数据集上的有效性实验证明，我们的算法明显快于[6]的最新LP最小化此外，它产生的分配，其能量远低于那些获得的基线[6，12]。总之，我们的框架构成了第一个高效和有效的最小化算法的密集CRF高斯成对电位。我们的代码可以在https://github.com/oval-group/DenseCRF上 找 到 ， 论 文 的 更 详 细 版 本 可 以 在https://arxiv.org/abs/1611.09718上找到。2. 预赛在介绍我们的方法之前，让我们首先提供一些关于密集CRF模型及其LP松弛的背景。致密CRF能量函数。 稠密CRF定义在n个随机变量X={X1，. . .，Xn}，其中每个随机变量Xa取标签Xa∈L，其中|L|为M. 对于给定的标记x，与a相关的能量3299一1¨¨成对密集CRF可以表示为IP目标E（y）。上述放宽措施与ΣnE（x）=Σnφa（ xa）+Σn（xa，xb），（1）标准LP松弛[4]的Potts模型和它亲，显示完整性差距为2。 [17]中的结果意味着，a=1a=1b=1，b/=a不太可能（除非唯一博弈猜想是假的）其中φa和φab表示一元势，潜力，分别。一元势定义数据成本，成对势定义平滑成本。高斯成对势类似于[6，12]，我们考虑高斯成对势，其具有以下性质：我们可以设计一个更好的放松来解决这个问题。使用标准求解器来最小化这个LP需要引入O（n2）变量（见附录A.1），这使得它变得棘手。因此，Eq.的非平滑（4）必须直接优化这件事下表：ab（xa，xb）=µ（ xa，xb）Σw（c）k.Σf（c），f（c）、 （二）使用[6]中的投影次梯度下降，这也将在实践中效率低下。 本文介绍k（fa，fb）= expaB.cΣ−fa−fb<$2.2一个有效的算法来解决这个问题，同时保持在空间和时间复杂度的线性这里，µ（xa，xb）被称为标签兼容性函数，高斯核的混合被称为像素兼容性函数。 权重w（c）≥0定义混合系数，f（c）∈ IRd（c）编码与随机变量Xa 相 关 的 特征，其中d（c）是特征维数. 对于语义分割，图像对应于随机变量。在实践中，如在[6，12]中，我们然后使用像素的位置和RGB值作为特征，并假设标签兼容性函数。3. LP松弛的邻近最小化我们的目标是为（4）中的LP松弛设计一个有效的最小化策略。为此，我们建议使用近似最小化算法[20]。这保证了目标值的单调下降，使我们能够利用更快，更准确的方法进行初始化。此外，额外的二次正则化项使对偶问题变得平滑，从而能够使用更复杂的优化方法。其余部分中这是Potts模型，即μ（xa，xb）=μ[xaxb]。在本文的第一部分，我们详细介绍了这种方法，并表明，这些潜力已被证明可用于获得细粒度的在分割任务中的标记[12]。可持续发展方案拟订。 另一种表示标签的方法是定义指示变量迭代具有线性时间复杂度。在实践中，我们的算法收敛在一个小的迭代次数，从而使整个方法的计算效率。近似最小化算法[20]是一种迭代算法，ya：i∈ {0，1}，其中ya：我=1当且仅当xa=i. 我们-方法，给定解yk的当前估计，使用这种符号，能量最小化问题可以被写为下面的可编程程序（IP）：解决问题minE（y）+<$y −yk<$2，（5）Σ Σ Σ Σ y2λminyE（y）=Σaφa：iya：i+我甲乙丙ai，jab：ijya：iyb：j，S.T. y∈M，其中λ设置近端项的强度。S.T.ya：i= 1<$a ∈ {1. . . n}，iya：i ∈ {0，1} {1. . . n}，n ∈ L.（三）注意，（5）由分段线性项和二次正则化项组成。具体来说，这里，我们使用简写φa ：i=φa（i）和φab：ij=φab（i，j）。第一组约束确保每个随机变量都被分配了一个标签。注意到目标函数的值等于由y编码的标记的能量。线性规划松弛。通过放松（3）中指示变量的二元约束，并使用标签相容性函数是Potts模型的事实，（3）的线性规划松弛[9]被定义为：线性项来自成对项|ya：i− yb：i|在（4）中，可以重新表示为max{ya：i− yb：i，yb：i− ya：i}。近似项y−yk2提供了二次正则化。在本节中，我们将介绍一种新的算法专门针对这个问题的。特别地，我们以块方式最优地求解（5）的拉格朗日对偶。3.1. 对偶公式对偶问题有三个变量，即α=Σ Σ Σ Σ|y− y |{α1，α2|1.|a ∈ {1. . . n}}3300a：ib：i阿布：我阿布：我minyE（y）=一.φa：iya：i+我Σa、b/=aKAB我、 且γ={γa：i，a ∈ {1. . . n}，i∈ L}. 在这里，我们介绍2两个矩阵，将是有用的写对偶问题10nm×pS.T.y ∈M=yiya：i= 1，a ∈ {1. . .n}（四）压缩具体地，矩阵A ∈IR（此处ya：i ≥0，a ∈ {1.. . n}，i ∈L，p=2n（n−1）m）和B ∈IRnm×n的定义使得Σ。ΣΣ1 2 2 1其中K=w（c）kf（c），f（c）.对于整数la-（Aα）a：i=−αab：i− αab：i+αba：i−αba：i、（6）ABCBb/=abellings，LP对象iveE（y）与（Bβ）a：i= βa..Σ3301a：我tΣ算法1LP的近端最小化（PROX-LP）要求：初始解y0∈M和对偶目标gk ← 0 . . K doAα0<$0，β0<$0，γ0<$0<$可行初始化for.t←0. Σ。 . 没做βt，γt←argming（αt，β，γ）Sec. 3.2.1yt←λ.β、γAαt+ Bβ+γt −φ+yk当前原始解决方案，可能不可行一个g的条件梯度，使用ytSec计算3.2.2δ←最优步长giv en（st，αt，y<$t）<$ Sec.3.2.2Aαt+1<$（1−δ）Aαt+δAt <$A t <$Frank-Wolfe update onαyk+1<$PM（y<$t）<$将原始解投影到可行集M这使得我们可以将（5）的拉格朗日对偶写为ming（α，β，γ）=λ<$Aα+Bβ+γ−φ<$2（7）注意，现在β是γ的函数。因此，我们在（7）中替换β，并在γ上最小化。有趣的是，结果-α、β、 γ. 2Σ+ Aα+Bβ+γ−φ， yk- β1，β2，可以针对每个像素独立地优化搜索问题其中每个子问题是m维二次方程S.T. γa：i≥ 0 <$a ∈ {1. . . n} i ∈ L，.Σα1+ α2=Kab，a，b/=a，i∈ L具有非负约束的程序（QP），其中m是标签的数量。对于像素a，该QP具有以下形式：α∈C=α阿布：我ab：i2.1T..不ΣkΣ1阿布：我2阿布：我≥0，a，ba，i ∈Lminγa2γaQγa+γa，Q（Aα）a−φa+ya、（10）给定对偶变量，可以使用KKT条件[3]获得相应的原始变量，如下：y= λ（Aα + Bβ + γ − φ）+yk。（八）我们建议读者参考补充材料中的附录A.1，以了解这种推导的细节。3.2. 算法对偶问题（7），在其标准形式中，只能使用投影梯度下降来解决然而，通过分离变量的可行域的类型的基础上，我们提出了一个有效的块坐标下降方法。这 些 块中的每一个都可以进行更复杂的优化，从而产生计算效率高的算法。由于对偶问题是严格凸的和光滑的，所以仍然保证最优解对于β和γ，问题分解到像素上，如3.2.1所示，因此使其有效。关于α的最小化是在一个紧域上，可以使用Frank-Wolfe算法有效地解决[8，16]。我们的完整算法总结在算法1中。在S.T.γa≥0.这里，γa表示向量{γa：i|i∈L}和Q=λ（I−1/m）∈IRm×m，其中I是单位矩阵，1是所有1的矩阵。我们使用[27]的算法来有效地优化每个这样的QP。在我们的例子中，由于矩阵Q的结构，迭代的时间复杂度与标签的数量成线性关系。因此，优化γ的总时间复杂度为O（nm）。一旦针对给定的αt计算出最优γ，则相应的最优β由等式（1）给出。（九）、更多详情见附录A.2。3.2.2优化α现在我们转向给定βt和γt的α优化问题。为此，我们使用Frank-Wolfe算法[8]，该算法具有无投影的优点此外，对于我们的具体问题，我们表明，所需的条件梯度可以有效地计算和最佳的步长可以得到解析。条件梯度计算。关于α的条件梯度通过求解线性方程组获得。在以下各节中，我们将更详细地讨论每个步骤。3.2.1优化β和γ耳化问题s =argminn∈C.ttt tαs，αg（α，β，γ）.（十一）我们首先转向当αt固定时优化β和γ由于对偶变量β是不受约束的，因此对偶目标g的最小值为-这里，αg（αt，βt，γt）表示对偶目标函数在（αt，βt，γt）处关于α的梯度。重要的是，我们证明了条件梯度具有解析形式，由下式给出：α，α3302a：我当βg（αt，β，γ）=0时得到。对β求导并将导数设为零，（阿秒）a：我Σ。=−Kab[yt不b：我]−Kab[yt不Σb：i]，β = BT。AαtΣ+γ−φ/m。（9）b（十二）≥y≤y3303其中，y=t是使用方程计算的当前（不可行）原始解（八）、关于详细的推导过程，我们请读者参阅附录A.3请注意，方程式（12）具有与LP子梯度相同的形式（等式12）。（20）in [6]）.这并不是一个令人惊讶的结果。事实上，对于某些问题，子梯度和条件梯度之间存在对偶关系[2]。为了计算该次梯度，在[6]中提出的现有技术的算法具有与像素数量成线性关系的时间复杂度。不幸的是，由于这构成了我们算法和[6]算法的关键步骤，4. 快速条件梯度计算在前一节中描述的算法假设条件梯度（等式10）是（12）可以有效地计算。请注意，方程式（12）包含两个项，这两个项在指示符函数中的标签约束的符号和顺序上是相似的。为了简化讨论，让我们关注第一项和一个特定的标签i，我们将在本节的剩余部分中不显式地写出来。在Eq中的第二项（12）和其他标签可以以相同的方式处理。通过这些简化，我们需要有效地计算形式为这种线性成本极大地影响了它们的效率。 在Σ{1. . . n}，v ′=k（f，f）[y ≥ y]，（14）然而，在第4节中，我们证明了这种复杂性可以降低到线性，从而有效地导致在实践中的一个数量级的加速。最佳步长。使用的主要困难之一 无论是次梯度还是条件梯度下降，迭代算法的性能关键取决于步长的选择。在这里，我们可以解析地计算最佳步长，该步长导致给定下降方向的目标如附录A.4所示，所得步长为：.Aαt−Ast，yaababb其中ya，yb∈ [0，1]，且fa，fb∈ IRd，对于所有a，b ∈{1}。. . n}。加快计算速度的常用方法，这种高斯核是通过使用有效的滤波方法[1]。这种近似方法已被证明是足够准确的类似应用[6，12]。在我们的例子中，由于序约束<$[ya≥yb]，对称性被破坏，直接应用过滤方法是不可能的。在[6]中，作者使用分治策略解决了这个问题，这导致了O（d2nlog（n））的时间复杂度。在实践中，这仍然是一个令人望而却步的高运行时间，特别是因为梯度组合，δ=P[0，1]λ A αt −Ast2.（十三）在算法的过程中多次执行推定。在这里，我们介绍一种更有效的方法。这里，P[0，1]表示到区间[0，1]的投影，是将值裁剪到[0，1]中。内存效率。 对于一个密集的CRF，对偶变量α需要O（n2m）的存储，这是不可行的，因为n是图像中的像素数。然而，请注意，在算法1中，α总是出现在乘积α=Aα中。因此，我们只存储变量α ，这将存储复杂度降低到O（nm）。3.2.3总结总之，我们的方法具有以下有效迭代算法的理想品质。首先，它可以受益于通过更快但不太准确的算法（例如平均场或DC松弛）获得的初始解其次，我们选择了一个二次近似项，对偶的近端问题可以有效地优化在一个块明智的方式。具体地，通过独立地最小化每个像素的一个小QP（维度为标签的数量）来有效地计算对偶变量β和γ利用Frank-Wolfe算法对剩余的对偶变量α进行优化，在线性时间内计算条件梯度，并解析地得到最优步长。总的来说，我们的算法的一个迭代的时间复杂度是O（nm）。据我们所知，这构成了第一个LP最小化算法的密集CRF，具有线性时间迭代。我们把这个算法称为PROX-LP。具体来说，我们表明，在方程中的术语。（14）可以在O（Hdn）时间内计算（其中H是4.2节中定义的小常数），以额外的存储为代价。 在实践中，这导致一个量级的加速。下面，我们先简单回顾一下原始过滤算法，然后解释我们的修改算法，有效地处理排序约束。4.1. 原始滤波方法在本节中，我们假设读者熟悉基于置换面体格点的滤波方法[1]。由于篇幅所限，本文仅作简要概述。我们请感兴趣的读者参阅原文[1]。在[1]中，每个像素a ∈ {1。. . n}与元组（fa，va）相关联，我们称之为特征点。这个元组的元素是特征fa∈IRd和值va∈IR。注意，在我们的例子中，对于所有像素，va=1在算法的开始，特征点被嵌入到一个d-维超平面镶嵌的permutohedral晶格（六边形形状所示的图。①的人。这种置换面体晶格的顶点称为晶格点。一旦构造了置换体晶格，该算法执行三个主要步骤：飞溅模糊和切割在溅射期间，对于每个格点，使用重心插值来累积相邻特征点的值。接下来，在模糊过程中，格点的值与沿每个特征维度的一维截断高斯核卷积。3304Splat模糊切片赋予属于相同级别或更高级别的特征点的值换句话说，特征点b仅在ya≥yb时影响特征点a的值。最后，在切片步骤期间，从qth置换晶格中接收属于l个水平q我们的算法在图的底行中以图形方式描绘。1.一、其伪代码在附录B.2中提供。注意，虽然针对形式为[ya≥yb]的约束进行了讨论，但该算法可以很容易地适应于处理[ya≤yb]约束，这是等式2中的第二项所需的。（十二）、总的来说，我们的改进的过滤方法具有O（Hdn）的时间复杂度和O（Hdn）的空间复杂度。请注意，晶格创建的复杂性仍然图1：由三角形组成的六边形代表每个d = 2的多面体晶格，其中特征点用正方形表示，晶格点用圆形表示。顶行：原始过滤方法。重心插值由箭头表示，并且k在这里是截断的高斯核。见第3节第3段。4.1. 下一行：我们修改的过滤方法。这里，H=3，并且该图因此示出了3个晶格。我们将每个特征点的bin编号写在它旁边。见第2节第2段。四点二。单独的。最后，在切片期间，使用相同的重心权重将格点的结果值传播回特征这些步骤在图的顶行中以图形方式1.一、算法的伪代码在附录B.1中给出。该算法的时间复杂度为O（dn）[1，12]，而全多面体格生成的复杂度为O（d2n）.由于[6]中的方法在每次迭代时创建多个格，因此这种方法的总体复杂度为O（d2nlog（n））。注意，在该原始算法中，不存在与每个像素相关联的分数ya的特别地，在溅射期间，值Va被累积到相邻格点而不考虑它们的分数。因此，该算法不能直接用于处理我们的排序约束条件<$[ya≥yb].4.2. 修正滤波法我们现在介绍一个基于过滤的算法，它可以处理排序约束。为此，我们将连续区间[0，1]均匀地离散为H个不同的离散仓或水平。请注意，每个像素或特征点根据其对应的分数属于这些箱中的确切一个。然后，我们提出实例化H置换-面体格，每个水平h ∈ {0}一个。. . H −1}。为了处理排序约束，我们以下面的方式修改splatting步骤。将一个位于面元q上的特征点映射到对应于能级q≤ h H 的 < 全 多 面 体 格 上 . 然 后 在 每 个 单 独 的permutohedral lattice中独立地这保证了特征点只会影响-O（d2n），并且可以对每个H实例重用。此外，与[6]中的方法相反，该操作仅在初始化步骤期间执行一次。在实践中，我们能够选择H小到10，从而与[6]的分治策略相比实现了显著的加速。通过对区间[0，1]进行离散化，我们为整个算法增加了另一个近似级别。但是，可以通过使用动态数据结构来消除这种近似（参见附录B.2.1）。5. 相关工作我们回顾过去在我们工作的三个不同方面的工作，以突出我们的贡献。致密CRF。完全连接的CRF在语义分割方面越来越受欢迎。它在防止过度平滑方面特别有效，从而在对象边界处提供更好的精度。事实上，在一个互补的方向上，许多方法现在已经提出将密集CRF与卷积神经网络[5，22，28]相结合，以实现最先进的分割基准性能。以前阻止使用密集CRF的主要挑战是它们在推理时的计算成本，天真地说，每次迭代的计算成本是O（n2）在高斯成对势的情况下，文[1]的有效滤波方法被证明是稠密CRF中推理易处理的关键虽然是一种近似方法，但计算的准确性证明足以满足实际目的。这是在[12]中首次观察到的平均场推断的特定情况最近，几种连续弛豫，如QP、DC和LP，也被证明适用于通过以各种方式利用该过滤过程来最小化密集CRF能量[6]。不幸的是，虽然易于处理，最小化LP松弛，这是已知的原始标记问题的最佳近似，在实践中仍然太慢[6]。我们的算法在理论上和经验上都更快此外，正如我们的实验所证明的那样，它产生的能量值低于任何现有的密集CRF推理策略。3305LP松弛 有两种方法可以让你放松心情--根据标签兼容性函数，将ger程序（3）转换为线性程序：1）标准LP松弛[4]和2）专用于Potts模型的LP松弛[9]。有许多值得注意的工作最小化的标准LP松弛稀疏CRF。这包括直接使用该LP的对偶的算法[10，11，25]和基于近端最小化框架的算法[18，21]。不幸的是，所有上述算法都利用了问题的稀疏性，并且在全连接的情况下，它们每次迭代的代价为O（n2）本文主要研究了基于Potts模型的稠密CRF的 LP松弛算法，并给出了一个时间复杂度为O（n）的迭代算法。尽管我们关注Potts模型，如[6]中所指出的，这种LP松弛可以使用分层Potts模型[14]扩展到一般标签压缩函数弗兰克·沃尔夫结构支持向量机（SVM）的优化问题具有类似于我们的近似问题的形式。Frank-Wolfe算法[8]通过块坐标优化[16]为此类问题提供了有效且高效的解决方案最近有几项工作集中在提高该算法的性能[19，23]并扩展其应用范围[13]。我们的工作从这种结构SVM文献中得到启发，并利用Frank-Wolfe算法来解决我们的整体LP最小化方法的子任务。然而，效率，只能实现感谢我们的修改的有效过滤过程来处理排序约束。据我们所知，我们的方法构成了第一个LP最小化算法密集CRF具有线性时间迭代。我们的实验证明了这一结果对速度和贴标质量的重要性。由于速度快，我们的算法可以集成到任何端到端学习框架中，例如[28]。因此，我们相信它将对未来的语义分割结果产生重大影响，并可能在其他应用中。6. 实验在本节中，我们首先讨论进一步加速我们的算法的两个变体和一些实现细节。然后，我们转向实证结果。6.1. 加速变体根据经验，我们观察到，我们的算法可以通过限制优化过程来加速，仅影响标签和像素的相关子集这些子集可以从PROX-LP的中间溶液中识别特别地，如果ya：i 0，我们从优化中移除标签i<。01对于所有像素A.换句话说，标签i的分数对于所有像素都是无关紧要的。我们将此版本表示为PROX-LP。类似地，我们仅在选择标签时不确定时才对像素进行优化这里，像素a被称为不确定是否maxiya：i<0. 九十五换句话说，没有标签的得分高于0。九十五这种策略背后的直觉是，经过几次PROX-LP迭代，大多数像素都被正确标记，我们只需要微调剩下的几个。在实践中，我们将此限制集限制为像素总数的10%我们表示这种加速算法为PROX-LP的accc。正如我们的实验所示，PROX-LP访问产生了显着的加速，几乎没有损失的结果的质量。6.2. 实现细节在实践中，我们用解初始化我们的算法，的最佳连续松弛算法，这是所谓的DC负 [6]。我们的算法的参数，如最近正则化常数λ和停止准则，是手动选择的。小的λ值导致更容易的最小化的邻近问题，但也产生较小的步骤，在每个邻近迭代。我们发现λ=0。1.在我们所有的实验中都能很好地工作我们将邻近步骤的最大数量（算法1中的K）固定为10，并且每个邻近步骤最多优化5次Frank-Wolfe迭代（算法1中的T）。在我们所有的实验中，水平H的数量固定为10。6.3. 分割结果我们在MSRC和Pas上评估了我们的算法。cal VOC 2010 [7]分割数据集，并将其与平均场推断（MF）[12]、[6]的最佳连续松弛方法（DCneg）和[6注意，在[6]中，LP用DC阴性溶液初始化并优化5次迭代。此外，以与第6.1节中讨论的方式相似的方式对DC阴性溶液鉴别的标记子集进行LP优化。我们将该算法称为SG-LP算法。对于所有基线，我们采用了从网络或通过个人交流获得的相应作者的此外，对于所有的算法，积分标记计算从分数的解决方案，使用argmax舍入方案。对于这两个数据集，我们使用了与[12]中相同的分裂和一元势使用两个内核定义成对势：一个空间核和一个双边核[12]。对于每种方法，使用Spearmint [24]对验证数据进行核心参数交叉验证（萌芽时间为2天）。为了能够比较能量值，我们使用相同的参数评估了所有方法。换句话说，对于每个数据集，每个方法都使用不同的参数值运行多次。请注意，在MSRC上，交叉验证是在原始数据集提供的不太准确的基础事实上进行的尽管如此，我们还是根据[12]提供的准确地面实况注释对所有方法进行了评估。MSRC和Pascal数据集上针对DC阴性调整的参数结果见表1。这里MF53306×106109876543210 5 10 15 20 25 30 3540时间（s）2.42.221.81.61.41.2×1061 2376.86.66.46.265.85.65.45.25×105MFDCnegSG-LPSG-LP PROX-LPPROX-LP接口PROX-LP接口0 50 100 150200时间（s）5.25.185.165.145.125.15.085.065.04×1055 10 15 20图2：MSRC（左）和MSRC（右）中图像的分配能量与时间的函数关系，其中参数针对DC阴性进行了调整。（右）帕斯卡。放大后的版本显示在每个图的旁边。除MF外，所有其他算法均使用DC阴性进行初始化。请注意，PROX-LP通过在更少的迭代中获得更低的能量，明显优于SG-LP。此外，我们算法的加速版本获得与PROX-LP大致相同的能量，但速度明显更快。算法MF5 MFDC阴性SG-LP100近端LP近端LP100近端LP接入Avg. E（×103）Avg. 不（s）Acc.IOUMSRCMF5-0000008078.00.279.3352.30MF96-000008062.40.579.3552.32DC阴性9696-00003539.61.383.0157.92公司简介969690-3113335.613.683.1558.09PROX-LP96969492-13451274.423.583.9959.66PROX-LP系列9696959481-611189.86.383.9459.50PROX-LP接入969695944931-1340.03.784.1659.65PascalMF5-13000001220.80.879.1327.53MF2-000001220.80.779.1327.53DC阴性9999--000629.53.780.4328.60公司简介999995-51212617.184.480.4928.68PROX-LP99999584-3250507.7106.780.6328.53PROX-LP系列9999868664-43502.122.180.6528.29PROX-LP接入999986864639-507.714.780.5828.45表1：MSRC和Pascal数据集上的结果，参数针对DC阴性进行了调整。我们显示：行方法严格优于列的最终积分能量，平均积分能量超过测试集，平均运行时间，分割精度和交叉工会得分的图像的百分比请注意，我们算法的所有版本都获得比基线低得多的能量有趣的是，虽然我们的完全加速版本在能量方面稍差，但它在MSRC中的分割准确性方面是最好的。表示运行5次迭代的平均场算法。图 2，我们显示了分配能量作为MSRC中图像的时间函数（图中的树图像）。3）和一个图像在帕斯卡（羊的形象，在图。（3）第三章。此外，我们在图中提供了一些分割结果。3 .第三章。总之，PROX-LP插值在两个数据集中获得最低的积分能量。此外，我们的完全加速版本是最快的LP最小化算法，并且在能量方面始终优于基线。从图3，我们可以看到PROX-LPacc标记了大多数关键像素（例如，对象边界）是不确定的，并有效地对其进行优化。请注意，除了速度快之外，PROX-LPacc在MSRC中获得了针对DCneg调整的参数的最高精度。确保不同能源之间的一致行为参数，我们对MF调整的参数进行了相同的实验在这种情况下，我们的算法的所有版本再次产生比基线明显更低的能量。由于空间限制，表2总结了选定算法的MSRC结果，附录C.2给出了该参数设置的完整结果。我们观察到较低的能量不一定会导致分割的改善，这是一个重要的观察结果（在[6，26]中观察到类似的行为）。实际上，密集CRF能量和分割准确性之间缺乏相关性突出了对密集CRF模型进行更彻底分析的重要性。6.4. 修正滤波法然后，我们将第4节中描述的修改后的过滤方法与分而治之策略进行MFDCnegSG-LPSG-LPPROX-LPPROX-LP接口PROX-LP接口积分能量积分能量3307图像MF DC阴性 SG-LP旁路PROX-LP旁路 不确定PROX-LP接入地面实况图3：在MSRC（上图）和Pascal（下图）中针对DC阴性图像调整参数的定性结果。由PROX-LPacc识别的不确定像素用白色标记。请注意，在这两幅图像中，我们算法的所有版本都获得了视觉上良好的分割。此外，PROX-LPacc将关键像素（对象边界）识别为不确定的，并对其进行有效优化此外，在MSRC图像中，PROX-LPacc相对于基线的改进是清晰可见的，并且最终分割几乎与准确的地面实况相同（彩色效果算法Avg. E（×103）Avg. 不（s）Acc.IOUMF1053.613.083.8659.75DC阴性812.72.883.5059.67PROX-LP接入295.97.983.0358.97表2：针对MF调整参数的MSRC结果。我们的方法获得了最低的能量，然而，正如预期的那样，由于参数是针对MF调整的，因此这种推断策略产生了最佳的准确性。标记物数目0 5 10 15 2060 6050 5040 4030 3020 2010 100.5 1 1.5 2像素数×105空间核（d= 2）标记物数目0 5 10 15 2050 5040 4030 3020 2010 100.5 1 1.5 2像素数×105双侧内核（d= 5）的[6]。为此，我们在Pascal VOC测试图像之一（图1中的绵羊图像）上评估了这两种算法。3），但改变图像大小，标签的数量和高斯核标准差。请注意，为了生成一个变量的图，其他变量固定为各自的标准值。像素数的标准值为187500，标签数为21，标准偏差为1。对于这个实验，条件梯度是从随机原始解计 算 的。 图4，我们展示了我们的修改后的滤波方法相对于[6]中的方法的加速如附录C.4所示，相对于内核标准差的加速比大致恒定。时间是10次运行的平均值，我们观察到不同运行之间的时间变化可以忽略不计。总之，我们修改后的滤波方法比[6]的最先进算法快10-65倍。此外，请注意，我们算法的所有版本都在加速比约为45 -65的区域中运行。7. 讨论我们已经介绍了第一个LP最小化算法的密集CRF与高斯成对的潜力，其迭代是线性的像素和标签的数量。由于我们的算法的效率和LP松弛的紧密性，我们的方法产生低得多的图4：在Pascal图像上，我们修改的过滤算法在[ 6 ]的分治策略上的加速。请注意，我们的加速比随着像素数的增加而增加，并且相对于标签数近似恒定。(Best颜色显示）能量值比最先进的密集CRF推理方法。此外，我们的实验表明，与正确的能量参数集，高精度的分割结果，可以得到与我们的算法。我们算法的速度和有效能量最小化使其成为端到端学习框架的完美候选者，如[28]。我们相信，这将是进一步提高深度语义分割架构准确性的关键。8. 确认这项工作得到了EPSRC、ERC赠款ERC- 2012-AdG321162-HELIOS、EPSRC/MURI的基金参考EP/N 019474/1、EPSRC基金EP/M013774/1、EPSRC项目基金Seebibyte EP/M013774/1、微软研究院博士奖学金、ANU博士奖学金和Data 61奖学金。Data61（前身为NICTA）由澳大利亚政府资助，由宽带，通信和数字经济部以及澳大利亚研究委员会通过ICT卓越中心计划代表加速比加速比3308引用[1] A. Adams，J. Baek，and M.戴维斯使用置换面体晶格的快速高维滤波计算机图形学论坛，2010年。一、四、五[2] F. 巴赫. 次梯度法与条件梯度法的对偶性SIAM Journalon Optimization，2015。4[3] S. Boyd和L.范登伯格凸优化剑桥大学出版社，2009年。3[4] C. Chekuri，S. Khanna，J. Naor，and L.佐辛度量标号问题的线性规划公式和近似算法SIAM Journal on DiscreteMathematics，2004. 二、六[5] L. Chen，G. 帕潘德里欧岛 科基诺斯角 墨菲和A.尤尔。使用深度卷积网络和全连接CRF进行语义图像分割。ICLR，2014年。5[6] A.德迈松河Bunel，P. Kohli，P. Torr和P.库玛密集型CRF的有效连续松弛ECCV，2016。一、二、四、五、六、七、八[7] M.埃弗灵厄姆湖，澳-地凡古尔角，澳-地威廉斯，J.Winn和A.齐瑟曼。Pascal视觉对象类（VOC）的挑战. IJCV，2010年。1、6[8] M. Frank和P.沃尔夫二次规划的一个算法.1956年海军研究后勤季刊。一、三、六[9] Kleinberg和E. Tardos具有成对关系的分类问题的近似算法：度量标号和马尔可夫随机场ACM杂志，2002年。一、二、六[10] 科尔莫哥洛夫能量最小化的收敛树重加权消息传递。PAMI，2006年。6[11] N. Komodakis，N. Paragios和G.齐里塔斯通过对偶分解实现MRF能量最小化和超越。PAMI，2011年。6[12] P. K raühenbuühl和V. 科尔顿具有高斯边缘势的全连接CRF中的有效推理NIPS，2011年。一二四五六[13] R. Krishnan，S. Lacoste-Julien和D.桑塔格Barrier Frank-Wolfe用于边际推理。NIPS，2015年。6[14] P.Kumar和D.科勒通过分层图割的半度量MRF的MAP估计。UAI，2009年。6[15] P. 库马尔河Kolmogorov和P.乇离散MRF的MAP估计的JMLR，2009年。1[16] S. Lacoste-Julien，M. Jaggi，M. Schmidt和P.普莱彻结构支持向量机的块坐标Frank-Wolfe优化。ICML，2012年。一、三、六[17] R. Manokaran，J. Naor，P. Raghavendra，and R.史瓦兹多向切割的SDP间隙和UGC硬度，0-扩展和度量标签。 STOC，2008年。2[18] O. Meshi，M.Mahdavi和A.施温光滑而结实：线性收敛的MAP推理。NIPS，2015年。6[19] A. 奥索金， J. Alayrac， I. 卢卡斯维茨， P.Dokania，以及S.拉科斯特-朱利安注意结构化支持向量机的块Frank-Wolfe优化的间隙。ICML，2016。6[20] N. Parikh和S.博伊德近端算法优化的基础和趋势，2014年。一、二[21] P. Ravikumar，A. Agarwal和M.温赖特图结构线性程序的消息传递：近似投影、收敛和舍入方案。ICML，2008年。6[22] A. Schwing和R.乌塔松完全连接的深度结构化网络。CoRR，2015年。5[23] N. Shah，V. Kolmogorov，and C.蓝伯特一种多平面块坐标Frank-Wolfe算法，用于训练具有代价极大预言机的结构支持向量机。CVPR，2015年。6[24] J. Snoek，H. Larochelle和R.亚当斯机器学习算法的实用贝叶斯优化。NIPS，2012年。6[25] M. Wainwright，T. Jaakkola和A.威尔斯基MAP estima-tion via agreement on trees ： message-passing and linearprogramming.信息理论，2005年。6[26] P. Wang，C. Shen和A.范登亨格尔。基于低秩