偏序标号上凸先验可分的MRF优化

V → LVLV → L偏序标号上凸先验可分的MRF优化作者：Cassaba Domokos1，2，Frank R.Schmidt1、 2和Daniel Cremers11Munich、Garchin gbeiMu¨nchen、Germany的Technicremers@tum.de2博世人工智能中心，Renningen，德国{csaba.domokos，frank.r.schmidt}@ de.bosch.com抽象。如果标签集是全序的，则求解带有凸罚的多标签问题可以在多项式时间内实现。在本文提出了一种对偏序集的推广。为此，我们假设标签集是笛卡尔积的全序集和凸先验是可分的。对于这种设置，我们介绍了一个通用的组合优化框架，提供了一个近似的解决方案。更具体地说，我们首先构造一个图，其最小割提供了我们的能量的下界。然后，使用这种松弛的结果通过经典的移动决策切割来获得可行的解决方案。为了加快优化，我们提出了一个有效的粗到精的方法在标签空间。我们证明了所提出的框架，通过广泛的实验光流估计。关键词：多标号问题，偏序集，次模松弛1介绍许多计算机视觉问题，如立体匹配[1-对于一组变量有限标签集，映射f：称为多重标记。多标签问题的目的是找到最小化能量E（f）的多标记f。一般来说，这个问题是NP-难的，而且，没有算法可以近似这个一般的能量最小化，其近似比输入大小中的一些指数函数更好[7]。然而，通过做一些假设多标记问题变得易于处理[8在本文中，我们解决的问题，解决多标签问题。为了找到最优的多标记f：我们希望最小化以下形式E（f）= Σi∈VEi（fi）+Σ（i，j）∈EEij（fi，fj），（1）这项工作是作者在慕尼黑2C. Domokos，F.R. Schmidt和D.Cremers000L × L →L∈ E−G V E −≥L L L × × L其 中 E V × V 表 示 不同变量的 成 对 依 赖 关 系 。 Ei ：L→R 和Eij ：L×L→R+d分别表示为有限光滑项和成对光滑项。对于所有i ∈ V，数据项Ei可以任意选择，平滑项Eij具有以下形式Eij（fi，fj）=wij·d（fi，fj）f或alll（i，j）∈E.（二）能 量 （ 1 ） 对 应 于 一 个 马 尔 可 夫 随 机 场 （ MRF ） 公 式 [8] 的vranundirectedgraph=（，），其中P（f）e×p（E（f））。Here，wij0在a和d处的输入上执行以下操作：R+是一个.在较弱的限制下，已知（1）可以在多项式时间内全局最小化，如果|L| [11]或者如果L是全序集{1，，}并且有一个even，co nvexfunctiong：R→R+suchthatd（fi，fj）=g（fi−fj）[8].在本文中，我们专注于一个更一般的设置偏序标签集。特别地，我们假设=1。. .k可以写成k个不同的全序标签集的笛卡尔乘积。此外，我们假设惩罚用于交互像素的不同标签的函数d（即，对于所有（i，j） ）具有形式d（fi，fj）= g（fi，fj），其中g是偶的可分凸函数，即，标签空间的每个维度的正则化子的总和本文的其余部分组织如下。我们在第1.1节中简要介绍了相关工作在第2节中，我们介绍了偏序集的理论背景，a.k.a.偏序集论文的两个主要贡献可归纳如下：– 我们提出了一个组合优化框架，它可以应用于最小化定义在偏序集标签上的能量也就是说，我们展示了一个一般的图结构（见2.2节），其最小割提供了我们能量的下界。利用经典的移动决策割[1]，利用这种松弛来获得可行解。所提出的图结构可以处理任意的数据成本和可分离的凸光滑成本。– 我们还提出了一个有效的粗到精的策略，在标签空间（见第3节），有效地减少了可能的搜索空间，并在一个相当大的速度的算法的结果。作为所提出的优化方案的说明，我们认为光流估计的问题。在第4节中的综合实验表明，该方法提供了竞争力的结果与其他组合优化算法在降低复杂度。第五节是论文的总结。1.1相关工作部分有序标记集在几种计算机视觉应用中非常常见，如光流估计、图像配准、立体曝光融合等，其中标签集L是全序集的笛卡尔积。偏序集上凸先验可分的MRF优化32L谢霍夫佐夫等[12]提出了一种用于图像配准的MRF模型，其中变形由像素的离散X和y位移的耦合场描述。该模型由两层变量组成。层间交互用于对数据项进行编码，并且层内交互对相邻像素的成对（平滑度）约束进行编码。该模型导致更简单的松弛，其中应用了顺序树重加权消息传递（TRW-S）算法[2]。Chen和Koltun [6]解决了光流估计的问题，其中通过利用TRW-S算法[2]在规则网格上最小化经典Horn-Schunck目标[13]。在[5]中提出了另一种用于光流估计的离散优化方法。作者将该问题表述为离散推理，并应用块坐标下降法，该方法通过动态规划迭代优化所有图像行和列。Kohli等人[14]考虑了优化多标记成对MRF的问题。首先将多标签MRF模型转换为等效的二进制MRF，然后将其放松，这可以使用最大流算法[11]有效地求解。该解决方案提供了一个部分最优的标签的二进制变量，这是转移到多标签问题。在[15]中可以找到对具有子模3和非子模项的最小化函数的详细回顾，称为QPBO方法（二次伪布尔优化）。然而，QPBO的输出是部分标记，这意味着存在被解释为“未知”的特殊标记Goldstein等人[16]提出了一种求解向量值极小化问题的广义变分泛函提升技术。 该技术允许找到光流的全局极小值。作者认为全变差作为正则化。与我们的方法相反，L2惩罚不能在[16]中考虑。当标号空间是连续乘积空间且正则化子是可分的时，[17]提出了多标号问题的连续凸松弛。 通过放松的问题，各种问题，如光流，立体匹配和分割，可以解决在可证明的范围内的全局最优。 这种方法允许在多维标签空间上的一个非常一般的连续正则化类。正则化子可以任意混合，在这个意义上，标签空间的每个维度都可以有自己的正则性类型我们注意到，在连续松弛相反，我们专注于组合优化方法在本文中。2偏序集上的能量极小化在下文中，我们解决最小化（1）的问题，如果是偏序集（或偏序集）。在2.1节中，我们简要介绍了偏序集[18]，并解释了它们在能量最小化框架中的困难在2.2节特别地，我们将在2.3节中展示如何有效地最小化这种提升。3一个集函数f：2V→R称为次模的，如果对于任意一对子集A，B V，f（A）+f（B）≥f（A∪B）+f（A∩B）4C. Domokos，F.R. Schmidt和D.CremersL ≤ L L ≤∈L≤/L−L {}设置通过在图中找到最小切割来获得能量，以及如何采用启发式投影方案以找到原始能量的可行解。2.1偏序集、下水平集与下理想偏序集是一个集合L加上一个关系，该关系存储了对于任意一对元素α，β∈ L，陈述α≤β是否为真定义1（偏序集）。给定一组和一个关系对.我们称（，）偏序集或偏序集，如果对所有α，β，γ∈L都满足下列条件α≤α（自反性）α≤β，β≤α⇒α=β（反对称）α≤β，β ≤γ ⇒α ≤γ（传递性）（L，≤）称为全序集，如果对任意对α，β∈ Lα ≤ β或β ≤ α为真。偏序集和全序集的主要区别在于，偏序集中可能有两个不同的元素α，β，我们不能确定其中一个元素是否大于另一个。从现在起我们使用符号α β当且仅当α β和α=β成立。创建偏序集最简单的方法是取两个或多个全序集的笛卡尔积。引理1（笛卡尔积）。设（L1，≤1）和（L2，≤2）是两个全序集. 笛卡尔积L：= L1× L2成为偏序集（L，≤）（α1，α2）≤（β1，β2）：（α1≤1β1）∧（α2≤2β2）。证据直接从偏序集的定义导出将偏序集的内部结构可视化的一种常用方法是考虑其Hasse图。定义2（Hasse图）。 设（L，≤）是有限偏序集. 那么，L的Hasse图是一个有向图H =（L，EL），其顶点集L和边EL：={（β，α）∈ L × L |α <β，αγ ∈ L：¬（α <γ<β）}。对于全序集=1、. . .，，Hasse图恰好有1条边。这些边的形式为（α+ 1，α）。因此，全序集的哈塞图总是一个链。另一方面，如果是偏序集，则Hasse图成为DAG（有向无环图）（见图1）。下一节特别感兴趣的是下理想的集合。定义3. 对于每个α∈L，我们引用集合[α]：={β∈ L|β≤ α}偏序集上凸先验可分的MRF优化5111L1111LLL1L≤{}≤1 151617 18 19（0， 1）（1， 1）1 30 101112 13 14（0， 0）（1， 0）0 2-15678 9（b）L*={0，1}×{0，1}={0，1，2，3}-201234L2（0， 1）（1，1）（0， 1），（1， 0）}1 3一个12L1- 2 - 10 1 2（0，0）（1， 0）0 2（a）L={− 2，. . . ，2}× {− 2，. . . ，1}（c）L*={0，1，2，A12，3}Fig. 1. Hasse图(a)偏序集L=L1×L2的Hasse图，其中L1 ={−2，. . . ，2}且L2={−2，. . . ，1}保留所有您的旧数据集。 H具有L1的分布图和L2在s中接收。 （b）对于L={0，1}× {0，1}λ=Lλ，我们给出了一个简单的平面图.（c）L*=L*∪{[（1，0）]∪[（0，1）]}∪={0，1，2，3，A12}的两个简单的作为其较低水平集。进一步地，如果以下成立，我们称子集I为下理想α∈ I ⇒ [α] I.我们把所有低理想的集合记为L* 2 L，把所有低水平集合的集合记为L* L*。事实上，L*的每个元素都可以表示为包含在L* 中的元素的并集。换句话说，一个下理想L∈ L*是一个累积的集合较低水平集，即[L=α∈L[α]。注意，通过构造，L和L*具有相同的基数。从来没有-否则，L*可以大于L*。我们还注意到L*的元素是1 1L的子集值得注意的是，对于全序集，我们总是有*=*，它具有与相同的基数。因此，下理想和下水平集之间的差异仅在偏序集上可见。例1）对于全序集（，）=（0， 1，），我们得到低水平集如下：[0]={0}，[1] ={0，1}，L*={[0]，[1]}=L*。2）对于偏序集（L，≤）=（{0， 1} × { 0， 1}，≤），我们得到[(0，0）] ={（0， 0）}，[（1， 0）]={（0， 0），（1，0）}，[(0，1）]={（0， 0），（0， 1）}，[（1， 1）]=L，6C. Domokos，F.R. Schmidt和D.Cremers111L|L|L L∪LLL∈E·{}× L−V ×LV×L如果L={[（0，0）]，[（1，0）]，[（0，1）]，[（1，1）]}，则L={0，1，2，3}，并且[1，2，3，A1 2}.（三）因此，对于偏序集，低水平集和低理想之间存在差异我们将参考这个差异A ** LL：=L−L12（四）作为增广标签集，或者等价地 *=*A。请注意，A的基数可能相对于呈指数增长。在2.2节中，我们将看到如果我们提升能量（1），这些增广标签是如何事实上，增强标签导致不可行的解决方案。为了获得一个可行的解决方案，没有增广标签，我们提出了一个启发式投影方案。2.2能量提升从现在开始我们假设偏序集（L，≤）=（L，），其中L = L1×. . . ×Lk是k个全序集的笛卡尔积，H=（L，EL）是它的Hasse图.设E具有形式（1）。此外，我们假设平滑项Eij具有形式（2），并且d（fi，fj）=g（fi-fj）可以通过偶可分凸函数g来表示。我们想构造一个图G，使得每个标号f：V → L对应于G的一个s-t割，E（f）是它的割值[11]。全序标签集在简单的情况下k=1，因此=1是一个全序集，我们可以按照Ishikawa [8]的构造来设计具有所需性质的图。所使用的顶点由源s、汇t和内部节点组成。边缘可以分为三个不同的类。 无限容量的（i，）和（i，1）之间的约束边保证了在最优割中集合i的二元标号具有形式（1，. . .、1、0、. . .，0），其中1指示顶点与源连接。数据边可以被设计为s（分别为t）和（i，t）之间的终端链路。此公式是由于[19]，与[ 8]的原始公式不同。存储容量的大小随jcδb∈n个vi（i，+δ）和d（j，），对所有（i，j），对凸函数g建模。 这是通过使用非负值c0=g1−g0和dcδ=gδ+1−2gδ+gδ−1（δ>0）。更多详情请参见[8]。对于一般情况k>1，我们希望设计具有所需属性的不同图。和前面一样，使用的顶点是源点s、汇点t和内部顶点。此外，我们还引入了约束边，数据边和光滑边。 虽然这些边缘将不同于图8的构造[ 8]，但是它们保留了所述图像的真实性。偏序集上凸先验可分的MRF优化7645622111∗−*A∗ 4ˆ78457867 834 5(b) L1惩罚;切割的值为3 = |2 − 0|+的|1 −2|01 2（一）(c) L2惩罚;切割的值为5 = |2 − 0 |2个以上|1 − 2 |2图二、平滑项的图形构造。（a）偏序集L的Hasse图={0，1，2}× {0，1，2}。 （b）、（c）Graphc ons t io n c tionrL1和L2penalties，resp.， 其中灰色和白色节点分别连接到源和宿（对应于1和0）。这个例子显示了fi=（2，1）∈ L，fj=（0，2）∈ L的情况。切口由蓝色虚线示出。请注意，只应切割1-0条边约束边还应将标签与其直接前代标签′连接起来。由于偏序关系，“”不是唯一的。因此，我们使用L的Hasse图H =（L，EL），并对每个（i，′）∈ EL，在（i，）和（i，′）之间引入无限容量的边。因此，我们得到一个标号f：V→ L而不是f：V→ L。注意，下理想的集合L*包含了下水平集L和增广标签L。由于L与L之间存在一一对应的关系，即它们是同构的，我们可以将f理解为f的松弛，我们将f表示为f：V →（L ∪ LA）。数据边应反映数据项Ei（fi）。因为标签fi∈L是现在由较低水平集[fi]∈ L表示，我们必须将Di，n的一元数据成本与顶点（i，n）相关联，使得以下成立Σ∈[fi]Di，n= Ei（fi） n ∈ V，fi∈ L.（五）由于Hasse图是DAG，因此该线性方程组的矩阵（在置换之后）是上三角形因此，问题（5）可以通过连续替换容易地解决。如果得到的Di，为正，则其导致从（i，）到汇点t的容量Di，的边缘。否则，其导致从源s到（i，n）的容量Di，n的边缘[9]。平滑边应反映成对平滑项，即Eij（fi，fj）=wij·g（fi−fj）。 他，我们的提案的特殊性开始发挥作用。 L = L1×。. . × Lk导致k维标签，因此，我们写fi=（fi，1，. . . ，fi，k）和dfi=（fi，1，. . . ，f，j，k）。既然如此，4当两个偏序集作为图的Hasse图彼此同构时，称它们同构12123378121234563456788C. Domokos，F.R. Schmidt和D.Cremers∈LL一V → LV →L ∪L可分凸函数，我们有k个偶数凸函数gκ，其中κ = 1，. . . ，k使得d（fi，fj）= Σkκ=1gκ（fi，κ−fj，κ）.（六）由于标签fi现在由其较低水平集[fi]表示，因此该较低水平集还包含（01，. . . ，0k-1，fi，k，0k+1，. . . ，0k），（7）其中0κ′表示全序集Lκ′的极小元素。因此，将gκ编码在Lκ：={01}×。 . . ×{0κ−1}×Lκ×{0κ+1}×。 . . ×{0k}。并不是所有的K都是直接确定的，并且对于所有的K = 1，，. .，k，以便设计平滑度边缘。注意，这是可能的，因为g是可分凸的。更多细节请参见图2。总的来说，我们已经证明了以下定理。定理1. 设L是一个偏序集，可以表示为k个全序集Lκ，κ = 1，. . . ，k. 进一步考虑最小化f：V → L的能量（1）的多标号问题Σ ΣE（f）= Ei（fi）+Ei，j（fi，fi），i∈V（i，j）∈E其中平滑度项给出为Eij（fi，fj）=wij·d（fi，fj）=wijΣkκ=1gκ（fi，κ−fj，κ）wij≥0对于偶数，凸函数gκ对所有κ = 1，. . . ，Σk. 然后我们可以定义一个提升的Σ子模图可表示泛函D：V →（L ∪ L）→R使得D（f）= E（f）如果f：V → L.（八）到目前为止，我们找到了一个最佳标记f：（A）的情况。如果这个标签实际上是一个不包括增广标签的标签f：如果考虑的数据项非常明显，则可能发生这种情况。尽管如此，我们应该假设在实践中会出现增广标签。虽然D（f）=E（f）对于较低水平集是满足的，但是我们想要强调的是，我们的能量（1）通常不是子模5。我们考虑一个能量具有次模成对项，然而，任意的一元项使能量非次模。所提出的松弛是图可表示的，因此它是子模6。因此，我们可以计算全局最优的松弛能量的成本具有增广的标签。在下一节中，我们提供了一个启发式算法来删除这些增强的标签。⑤证明载于补充材料6图的可表示性隐含子模块性[9]偏序集上凸先验可分的MRF优化9−--2.3解析扩充标签假设LAfiSMµ=1[αµ].解决歧义的一种方法是运用像α这样的走法[1]在标签[ α 1 ]上交换β [1]，. . .，[αm].尽管如此，我们还是想指出一种不同的启发式方法，它更好地考虑了偏序集的结构。我们的想法是还考虑那些可以通过连接操作构造的标签α ∨ β=min {γ|α≤γ且β≤γ}。例如，让我们考虑标签空间L={0，1} × {0，1}，并设fi=[（1，0）]∪ [（0，1）]。在这种情况下，我们考虑关于（1， 0），（0， 1），（1， 1）的所有α−β交换基本原理是关于f的能量累积了[（1，0）]和[（0，1）]的数据项。由于关于[（1， 1）]的能量也累积这些数据项（和（1， 1）的数据项），因此拓宽用于移动决策方法的标签空间是有意义的。讨论主要应用于将表集定义为表7，（即，表 7）。e. 规则网格）。Topkis [18]提出了子模能量最小化理论在格子上。虽然我们的标签集也形成了一个格，但我们的能量（1）不是子模的。在[20]中，引入了一个通用的层次模型，其中标签空间形成了一个任意的树，指定了标签上的偏序。作者提出了有效的多标记移动，称为路径移动[20]。路径移动算法可以被看作是众所周知的α-扩展[1]和Ishikawa的c on s t r u c t i on [ 8]的组合。然而，在本文中，我们假设它是一个格，而不是一棵树，因此路径移动算法不能直接应用。3由粗到精战略在实践中，随着标签数量的增长，提升能量（8）的最小化变得迅速棘手。因此，使可能的标签的数量尽可能小是有益的。此外，我们处理放松，我们的原始能量我们不能保证得到一个可行的解决方案。因此，对于一些像素，我们可以获得增强的标签（即，标签的组合），我们需要解决这些问题以获得可行的解决方案。注意，通过增加标签集的大小，增强标签的数量呈指数增长，这使得增强标签移除非常具有挑战性。为了克服这些问题，我们考虑以下从粗到细的方法。为了简化符号，我们假设k = 2且L = L1× L2。 在第一次迭代中，我们只考虑每个像素的m × n个标签，其中m和n分别是L1和L2大小的约数。每个粗略标注对应7如果偏序集的两个元素α和β有一个最小上界（最大下界），记为α∨β（α∧β），这是它们的并（交）。一个偏序集包含其每对元素的并和交，它就是一个格[18]=10C. Domokos，F.R. Schmidt和D.Cremers1JL110322JL110322 30 12 30 12 30 1L−迭代我迭代我迭代3I jL2L2L2L2L2L1L1L1L1图3.第三章。在标签空间L= L上的所提出的从粗到细策略的图示{0，. . . ，7}× {0，. . . ，7}，其中m=n=2。 在将用于像素的图像分割成mn = 4个相等区域的过程中，分别由，0，1，2和3，以及寻找最佳区域。在下一次迭代中将仅考虑标签空间的该最优区域。其余的标签（以红色显示）将被忽略到标签区域。在对最粗糙的级别做出决定之后，下一次迭代仅考虑在前一次迭代中选择的区域。这种常见的方法如图3所示。 经过几次迭代之后，L1或L2都不能再被除。这意味着优化的剩余部分归结为全序集上的最小化，其可以例如通过类似于[ 8]的约束来有效地解决。对于粗略级别上的数据项，我们在属于同一区域的标签上应用最小池化因此，我们对当前水平的优化有很强的指导作用对于平滑度项，我们使用所选面片中心之间的距离。值得注意的是，与以前的作品[21]相比，我们在标签空间而不是图像域中应用了一种从粗到细的方法此外，我们的方法的目标是计算在实践中提供有用的结果，即使不是所有的标签可以选择最佳的标签。与α展开一样，我们的方法试图尽快找到局部最优值。由于这个原因，我们只能提供一个弱持久性保证，即如果没有增广标签的推断，找到全局4数值实验在本节中，我们讨论所提出的最小化方案的实施细节，并通过光流估计来说明它。4.1实现细节我们运行我们的实验在一台机器上与英特尔至强E5-2697CPU@2.3GHz的Linux下在Matlab与C/C++ mex扩展。对于最大流计算和移动决策算法（即α β交换和α-扩展），我们使用公开可用的GCO库[1，9，11]。为了与其他方法进行公平的比较，我们使用了能量项的浮点表示。我们的实现可在https://github.com/csaba- domokos/MRFOptimizationOnPosets上公开获得。2 30 1偏序集上凸先验可分的MRF优化11O| E||V|- -联系我们∪×-2最小化为了最小化我们的弛豫能量，我们应用BK算法[11]。在流图构造期间，对于每个像素，通过数据边和对应的约束边来寻找增强路径到给定的像素。该预处理具有线性时间复杂度，并且由于BK算法具有最坏情况的复杂度，因此最终使BK算法具有更好的运行时间（2C），其中C是流图[11]中的最小切割的值。为了解决增广标签，即。不可行的解决方案，我们应用了我们在2.3节探索的启发式。也就是说，我们认为，在所提出的粗到细的方法的每次迭代中的2 - 2标签空间。因此，我们只有一个增广标签，即α =[（0，1）][（1，0）]，我们通过标准的α β交换移动[1]在标签（0，1），（1，0），（1，1）中选择一个可行的标签。更确切地说，用对应于给定像素的最低数据成本的可行标签替换增强标签然后，在所有三个标签对上运行α β交换算法[1]。αβ交换算法要求成对项是半度量的，这在我们的情况下是满足的，因为我们假设能量中的函数是偶数。4.2光流估计为了证实我们的优化质量，我们专注于光流应用。 假设输入图像对I1和I2，经典光流估计旨在找到I1中的像素与I2中的对应像素之间的位移[13]。 在离散设置中，可以考虑全有序（有限）标签集L1和L2来对水平和垂直位移进行建模。每个像素的标签取自偏序集L1×L2。目标是在I1（pi）=I2（pi+fi）处找到f：V → L1 × L2的最优解.最近，Chen和Koltun [6]提出了一种有效的光流估计解决方案。在这里，我们定义了我们的能量，从[6]中采用，为E（f）= Σi∈VEi（fi）+λΣ（i，j）∈Ewij|fi−fj|、（9）其中λ=0。021，并将保留该关键字符串，然后将该关键字符串设置为特定因素。 数据成本的形式为Ei（fi）=1−max（0，NCC（i，fi）），其中NCC（i，fi）是分别以像素i和i+ fi为中心的大小为3 × 3的块之间的归一化互相关。为了防止负相关补丁的惩罚，负值被钳位到零。两两光滑项被定义为对比度敏感的Potts模型[24]，即，基于边缘的加权因子被计算为wij=exp.2ΣI1（i）−I2（j）2σ1，其中σ=√6。12C. Domokos，F.R. Schmidt和D.Cremers×建议输入（0. 70，E：5640。8）插值后的误差图GroundtruthFullFlow（0. 55，E：5476。7）插值后的误差图建议输入（0. 53，E：3596。3）插值后的误差图GroundtruthFullFlow（0. 40，E：5476。7）插值后的误差图建议输入（0. 33，E：2627。5）插值后的误差图GroundtruthFullFlow（0. 20，E：2456。1）插值后的误差图见图4。Sintel数据集上的定性结果[22]。输入图像与地面实况一起在第一列中。分别用我们的方法和FullFlow [6]方法得到的结果，显示在第二列中。平均端点误差和能量值E在括号中。相应的错误映射在第三列中。最后一列中的结果是在EpicFlow [23]插值后获得的后处理在几种方法中，估计的光流被进一步插值以获得子像素精度[25，6]。最近，应用EpicFlow插值[23]作为后处理已经成为一种常见技术。EpicFlow需要点匹配作为输入，并通过变分优化实现最终结果。我们采用了文献[6]中的插值法。因此，我们还使用了EpicFlow插值[23]（参见图4）。4.3评价为了进行评估，我们使用了MPI Sintel数据集[22]，这是一个来自3D动画电影Sintel的自然光流数据集。每个图像具有438 1024像素的分辨率。该数据集包括各种具有挑战性的功能，如长序列，大运动，镜面反射，运动模糊，散焦模糊和大气效果。我们在训练集上运行了最终序列的实验，包括运动模糊。通过遵循[6]中的设置，我们首先重新缩放偏序集上凸先验可分的MRF优化13× × ××−|L|基线α−β交换α展开FullFlow [6]提出[12个]序列|L|EPERT.EPE室温EPE室温EPE室温EPE室温 EPE睡眠18× 81.12 二点二三0.563.060.55 3.160的情况。520.860.600的情况。351.77睡觉28× 80.71 一点五0.532.820.53 2.520的情况。470.860.530.24 1.46萨满316 ×16 1.106.44 0.7627.480.73十四点十九分0的情况。622.740.850的情况。441.451支弄32× 32 1.45 20.79 0.85三百七十七点三四0.77六十一点八五0的情况。5810.930.920的情况。561.44胡同232× 32 3.69 29.45 1.24 四百四十五点三九1.16 七十四点九三0的情况。7411.231.320的情况。703.48绷带232× 32 0.93 19.44 0.54三百一十四点四五0.53五十九点四九0的情况。4010.940.570。45 0.93萨满232× 32 一点二九十六点零三0.65377.79 0.58 六十七点二一0的情况。3610.970.950.62 0.92埋伏764× 6457.801.58 9278.76 1.36 286.73 0的情况。6547.331.400的情况。893.30市场264× 64 1.67七十九点零七分1.025851.91306.620的情况。5847.961.610的情况。841.27表1.与其他组合优化方法的定量比较Sintel数据集[22]。EPE和rt.，相应地，代表平均端点误差和运行时间（秒）的平均值。所有实验都在单个CPU核心上运行将输入图像放大1/ 3倍我们考虑具有50个图像的序列，其具有10、22、46和94的各种最大位移，其对应于到大小为8的标签集八、十六十六、三十二32和6464、分别后重新缩放。使用平均终点误差作为评价指标。一些定性结果可以在图4中看到我们的实验旨在提供与现有技术组合优化方法的全面比较。作为基线，我们运行交替优化，从零流量初始化，其中全局优化方法[8]用于每个方向。我们考虑了经典的移动决策算法，即α β交换和α-展开[1]。在TRW-S方法的情况下，我们使用了FullFlow方法的实现[6]。与[6]相反，我们在单个CPU核心上运行代码，以便进行公平的运行时比较。仅计算TRW-S方法的三次迭代。为了完整起见，我们还运行了Shekhovtsov等人的方法。[12]第10段。我们使用了作者的实现，其设置与其他方法类似。我们注意到[12]的实现应用TRW-S方法作为推断，然而，所考虑的能量与能量（9）不同，因此，这种比较不完全公平。定量结果示于表1中。我们可以观察到，随着标签集的大小的增长，经典的移动决策算法很快变得令人望而却步我们提出的方法提供了可比的准确性，这些方法。FullFlow方法始终提供最小的平均端点误差，但其运行时相对于线性增长。与FullFlow方法相比，我们的方法提供了中等程度的较差结果，但是，我们的方法的运行时间增加非14C. Domokos，F.R. Schmidt和D.Cremers常缓慢，并且始终保持在一秒以下。方法[12]提供了比其他方法更大的误差。偏序集上凸先验可分的MRF优化151JL110322JL110322 3012 3012 301×−×−LL迭代我迭代我迭代3I jL2L2L2L2L2L2L1L1L1L1图五. 标签细化的三次迭代的图示。在粗到细方法的给定级别，我们具有（粗）标签fi=l和fi= 0，并且考虑（粗）标签空间{0，. . . ，7}× {0，. . . ，7}，由绿色显示，用于细化。在下一次迭代中，考虑精化标签的3 × 3邻域从表1中可以看出，通过我们的方法获得的误差随着标签集的大小而增长。事实上，我们从粗到精的策略存在固有的局限性。当它在当前级别处对像素做出决定尽管最小池化操作提供了强有力的指导，但当前级别的标记不一定是最佳的。为了克服这个限制，我们研究了标签细化技术。在每次迭代中，我们得到一个可行的解决方案，然后通过应用- ING本地移动决策削减来细化。更确切地说，对于当前的标签，我们只考虑在由粗到细的方法的给定级别的标签，并探索3标签空间中的3个邻域（参见图5）。经典的α β交换算法用于33个区域，以细化当前标签。我们再次重新考虑产生的标签，并使用相同的过程，直到没有更多的改进是可能的。由于α β交换总是降低能量，因此保证了收敛。然而，我们观察到结果略有改善，但代价是更高的运行时间（参见补充材料）。5结论在这项工作中，我们提出了一种新的方法来计算（局部）最优标签的特定类别的偏序标签集。我们假设标签集L可以表示为k个不同的完全有序标签集κ的笛卡尔积。在凸先验关于k个全序标签集是可分的假设下，我们能够设计一个图可表示的子模能量。当这种能量导致一个放松的解决方案时，我们可以证明放松有助于我们指导局部移动决策方法。结合变分后处理，我们能够提供光流的结果，与国家的最先进的方法，基于组合的方法，在降低的时间复杂度。致谢这项工作得到了亚历山大·冯·洪堡基金会的部分支持。2 30116C. Domokos，F.R. Schmidt和D.Cremers引用1. Boykov，Y.，Veksler，O.，Zabih，R.：通过图切割的快速近似能量最小化。IEEETransactions on Pattern Analysis and Machine Intelligence23（11）（November2001）12222. Kolmogorov，V.：能量最小化的收敛树重加权消息传递第 IEEE Transactions on Pattern Analysis and Machine Intelligence 28 （ 10 ）（2006年10月）1568-15833. Komodakis ， N. ， Tziritas ， G. ： 基 于 线 性 规 划 的 图 割 近 似 标 注 。 IEEETransactions on Pattern Analysis and Machine Intelligence28 （ 8 ） （ August2007）14364. Ladic k y'，L.， Russell，C.， Kohli，P.， Torrr，P. H. S. ：一个支持的区域领域的IEEE Transactions on Pattern Analysis and Machine Intelligence 36（6）（June 2013）1056-10775. Menze，M.，Heipke，C. Geiger，A.：光流离散优化。 在Gall，J. Gehler，P.莱贝湾编辑：德国模式识别会议论文集。LNCS第9358亚琛，德国，施普林格（2015）166. 陈昆，Koltun，V.： 全流：通过规则网格上的全局优化进行光流估计。In：Proceedings of IEEE Conference on Computer Vision and Pattern Recognition，Las Vegas，NV，USA，IEEE（2015年6月）7. Li，M.，Shekhovtsov，A. Huber，D.：离散能量最小化问题的复杂性。在Leibe，B. Matas，J.，塞贝，N.，Welling，M.，编辑：欧洲计算机视觉会议论文集。计算机科学讲义第9906卷阿姆斯特丹，荷兰，施普林格（2016年10月）8348. Ishikawa，H.：具有凸先验的马尔可夫随机场的精确优化。IEEE Transactions onPattern Analysis and Machine Intelligence25（10）（2003年10月）13339. Kolmogorov，V. Zabin，R.：什么样的能量函数可以通过图割最小化？IEEETransactions on Pattern Analysis and Machine Intelligence26（2）（2004年2月）14710. Ramalingam，S.，Kohli，P.，Alahari，K.，Torr，P.H.S.：具有高阶团的多标签CRF中的精确推断。In：Proceedings of IEEE Conference on Computer Vision andPattern Recognition，Anchorage，AK，USA，IEEE（June 2008）11. Boykov，Y.，Kolmogorov，V.：最小割/最大流算法在视觉中能量最小化的实验比较 。 IEEE Transactions on Pattern Analysis and Machine Intelligence26 （ 9 ）（2004年9月）112412. She k hovtsov，A.， 哥夫敦岛， Hlav'a c，V. ：有效的MRFde形成模型，非刚性图像匹配计算机视觉与图像理解112（1）（2008年10月）91-9913. Horn，B.K.，Schunck，B.G.：确定光流。人工智能17（114. Kohli，P.，Shekhovtsov，A. Rother，C.，Kolmogorov，V. Torr，P.H.S.：多标签MRF中的部分最优性。In：Proceedings of International Conference on MachineLearning，Helsinki，Finland，ACM（July 2008）48015. Kolmogorov，V. Rother，C.：用图割最小化非次模函数。IEEE Transactions onPattern Analysis and Machine Intelligence29（7）（2007年7月）127416. Goldstein，T.，Bresson，X.，Osher，S.：马尔可夫随机场并应用于光流。逆问题&成像6（4）（2012年11月）623-644偏序集上凸先验可分的MRF优化1717. Goldluecke，B.，Strekalovskiy，E.，Cremers，D.：向量值标号的紧凸松弛。SIAM Journal on Imaging Sciences6（3）（2013年3月）162618. T