二元配对能量的自适应和移动辅助割线

149220二元配对能量的自适应和移动辅助割线0Lena Gorelick Yuri Boykov OlgaVeksler计算机科学系西安大略大学0摘要0许多计算机视觉问题需要优化二元非子模块能量。在这个背景下，基于信任区域（LSA-TR）和辅助函数（LSA-AUX）的局部迭代子模块化技术最近被提出[9]。它们在许多计算机视觉应用中取得了最先进的结果。在本文中，我们在LSA-AUX框架中进行了两个方向的扩展。首先，与LSA-AUX不同，LSA-AUX仅基于当前解选择辅助函数，我们提出将几个附加标准纳入考虑。这样可以为更可能或更接近当前解的配置提供更紧密的上界。其次，我们提出了LSA-AUX的移动扩展，通过限制搜索空间实现更紧密的上界。最后，我们在几个应用中评估了我们的方法。我们表明，对于每个应用，我们的扩展中至少有一种明显优于原始的LSA-AUX。此外，在六个应用中，LSA-AUX的最佳扩展与LSA-TR相媲美或更好。01. 引言0二元配对非子模块能量的最小化是组合优化中的一个经典问题，例如参见[15, 8,2]。在过去的十年中，基于LP松弛的优化方法，例如QPBO[21]和TRWS[13]，在视觉领域变得流行，并得到了全面的评估[12]。另一组方法是基于局部线性化，例如并行ICM、IPFP[16]和类似的方法[4]。这些方法通过在当前解附近线性化能量，并在整数域内全局优化逼近。这种方法往往会因为步长过大而陷入较差的局部最小值，而不考虑逼近的质量。IPFP尝试通过在新最小值附近的某条连续线上探索松弛解来控制步长。不幸的是，由于全局最小化器保证降低原始能量，因此无需控制步长。0通过全局LP松弛，这些松弛解对于原始整数问题没有任何保证。最近，提出了两种局部子模块化方法，LSA-TR和LSA-AUX[9]。它们不使用线性逼近，而是使用一类更一般的子模块函数，这样可以获得更好的逼近效果，同时允许高效的优化。LSA-TR基于信任区域框架[23]。在每次迭代中，它使用子模块函数来逼近当前解附近的原始能量。这个逼近只在当前解附近的一个小区域内被信任，称为信任区域。下一个候选解是通过在这个信任区域内全局优化逼近得到的。根据逼近的质量，信任区域的大小会增加或减小，从而更好地控制步长问题。LSA-AUX基于辅助函数框架[14, 18,1]，也称为界限优化。在每次迭代中，它找到当前解附近的原始能量的一个子模块上界，并对其进行全局最小化。由于全局最小化器保证降低原始能量，因此无需控制步长。局部子模块化方法在涉及二次[9,11]和高阶[22]能量的几个应用中取得了最先进的结果，其中LSA-TR更准确，LSA-AUX更快。在本文中，我们在LSA-AUX框架中进行了两个方向的扩展。首先，我们引入了一种为每个超模块势选择上界的新方法。LSA-AUX使用一个预定的上界，仅基于其在当前解中的配置。相反，我们建议使用一种自适应上界，该上界基于几个附加标准进行选择，例如一元项偏好、能量偏好、与当前解的接近程度以及上述标准的组合。直观地说，这为更可能或更接近当前解的配置提供了更紧密的上界。其次，受多标签能量[3,17]和二元能量[10]上的移动算法的启发，我们提出了LSA-AUX的两种类型的二元移动扩展。通过限制搜索空间，它们实现了更准确的上界。最后，我们在几个应用上评估了我们的方法。我们表明，对于每个应用，我们的扩展中至少有一种明显优于原始的LSA-AUX。此外，LSA-AUX的最佳扩展在六个应用中有四个与LSA-TR相媲美或更好。E(S) = ST U + ST MS,S ∈ {0, 1}Ω(1)minS∈{0,1}Ω E(S).(2)Esub(S)=ST U + ST M −S(3)Esup(S)=ST M +S(4)E(S) ≤ At(S)(5a)E(St) = At(St)(5b)St+1 = arg minSAt(S) ,t = 1, 2, . . .(6)E(St+1) ≤ At(St+1) ≤ At(St) = E(St).49230搜索空间的划分。第一种类型基于 α-扩展，其中当前解可以增长或缩小。这样的移动会导致某些配置无效。因此，在选择上界时可以忽略它们，从而为剩余的配置提供更紧的上界。第二种类型的移动基于线段边界的几何性质。每个移动准确地模拟了某个方向上的边界变化，并且我们在各个方向上进行迭代。请注意，所提出的扩展可以与最近发表的伪上界优化 [22]结合使用，该方法使用伪上界的族。我们在修复、具有排斥力的分割和二值反卷积 [9]、平方曲率 [19]、紧凑形状 [5]和多部分对象 [6]先验上评估所提出的自适应和移动制作辅助割。我们表明，对于每个应用程序，我们的扩展中至少有一个明显优于原始的 LSA-AUX。此外，LSA-AUX的最佳扩展在六个应用程序中有四个优于或与 LSA-TR相当。本文结构如下。第 2 节概述能量并回顾LSA-AUX。第 3 节和第 4节分别描述了所提出的自适应和移动制作辅助割。第 5节报告了实验结果。02. LSA-AUX 概述0我们研究了一类常见于计算机视觉中的二元非次模能量。不失一般性，这样的能量可以写成如下形式：0其中 S = ( s p  |  p  ∈  Ω) 是定义在像素 p  ∈  Ω上的二元指示变量向量，U = ( u p  ∈ R |  p  ∈  Ω)表示一元势函数，对称矩阵 M = ( m pq  ∈ R |  p, q  ∈Ω) 表示二元势函数。在许多应用中，矩阵 M是稀疏的，对于所有非相互作用的像素对，m pq  =0。我们寻找以下整数二次优化问题的解：0当 m pq  ≤  0  � ( p, q ) 时，能量 (1)是次模的，可以在多项式时间内找到 (2) 的全局最优解[2]。一般的非次模情况下，(2) 是 NP 难的。LSA-AUX基于辅助函数框架。它是一类迭代算法，每次迭代都构造和优化原始能量 E在当前解周围的一个上界。假设这些上界比原始能量 E更容易优化。0请注意，变换是一个常数。0我们将能量 E 在 (1) 中分解为次模和超模部分 E ( S ) =  Esub ( S ) +  E sup ( S ) ，满足如下条件：0其中 M − 的元素 m − pq ≤  0 和 M + 的元素 m + pq ≥0 分别表示次模和超模势函数。给定当前解 S t ，如果函数A t ( S ) 满足以下条件，则 A t ( S ) 是能量 E 的辅助函数：0我们迭代地最小化一系列辅助函数：0使用 (5a)、(5b) 和 (6)，很容易证明 (6)中的解产生一系列递减的能量值。0边界优化的主要挑战是设计一个适当的上界 A t ( . ) ，满足(5a) 和 (5b)。然而，在整数二次优化问题 (2)的情况下，这一步是简单的[9]，并且可以总结如下。考虑任意超模势函数 2 β  ∙  s p sq  在 (4) 中。它可以被线性函数 v pq ( s p , s q ) :=  v p  ∙s p  +  v q  ∙  s q  ≥  β  ∙  s p s q  上界。其中 v p  和 v q是一些正标量。设 ( s t p , s t q ) 是当前解 S t 中像素 p 和q 的配置。下表指定了 ( s t p , s t q )的四种可能配置的上界，如 [9] 所示：0（stp，stq）上界vtpq（sp，sq）0（0,0）β2sp + β02sq0（0,1）βsp0（1,0）βsq0（1,1）β2sp + β02sq0表1. [9]中使用的上界。0对（4）中的所有超模势的上界求和得到一个整体线性上界0E sup（S）≤ ST Vt（7）0其中向量Vt =（vtp | p∈Ω）由元素组成0vtp = �0q0m + pq 2（1 +stq - stp）0而St是当前解。0为了简洁起见，这里使用β而不是m + pq。49240让At（S）是St处的辅助函数，定义为0At（S）：= ST Vt + E sub（S）。 （8）0使用不等式（7）满足条件（5a）0E（S）= E sup（S）+ E sub（S）≤ At（S）。0由于STtVt = Esup（St），我们的辅助函数（8）也满足条件（5b）。函数At（S）是次模函数。因此，我们可以在每次迭代中全局优化它，保证能量的减少。03. 自适应辅助函数0表1的第2-3行提供的边界βsp和βsq0对于配置（stp，stq）=（0，1）和（stp，stq）=（1，0），它们是可能的最紧密的，因为它们与原始势能fpq = βspsq在四个可能的离散配置中的三个上重合。但对于边界β2sp + β，情况并非如此。02sq用于另外两个配置（stp，stq）=（0，0）和（stp，stq）=（1，1）。它只在四个离散配置中的两个上与原始势能fpq重合。可以在表1的第1行和第4行找到更紧密的边界，例如，这些情况下也可以使用βsp或βsq。请注意，边界βsq与配置（0，0），（1，1）和（1，0）上的势能fpq重合，而边界βsp与配置（0，0），（1，1）和（0，1）上的fpq重合。选择其中一个边界实际上选择了哪个配置（0，1）或（1，0）由边界精确建模，除了（0，0）和（1，1）。因此，在本文中，我们使用“我们选择边界βsp”和“我们精确建模配置（0，1）”这两个陈述是可以互换的。类似地，“我们选择边界βsq”和“我们精确建模配置（1，0）”这两个陈述也是可以互换的。在没有其他信息的情况下，不清楚在表1的第1行和第4行的配置中，两个同样紧密的边界βsp和βsq哪个更好。一种方法是在这两种情况下随机选择βsp或βsq之一。这正是在将高阶超模势降低为成对势能时提出的基于排列的方法[18]。我们将此方法称为LSA-AUX-P。然而，在[9]中，LSA-AUX-P在除一个应用外都不如表1中的边界。另一种方法是决定哪个配置（0，1）或（1，0）在某种意义上更“可能”。如果配置（0，1）更可能，则选择边界βsp，否则选择βsq。这样，所选边界与更可能的配置上的原始成对势能重合。下面我们提供几个选择标准，产生不同的辅助割算法。所有这些方法在选择当前配置（stp，stq）=（0，0）和（stp，stq）=（1，1）的边界时有所不同，而将配置（stp，stq）=（0，1）和（stp，stq）=（1，0）的边界保持不变，如表1所示。03.1. 一元偏好0根据一元项来决定哪个配置（0，1）或（1，0）更有可能的最简单方法。设U为一元系数向量，如（1）所示。如果像素p对背景的偏好比像素q更强，即up >uq，我们说配置（sp，sq）=（0，1）比（1，0）更有可能，并选择边界βsp。我们将这种LSA-AUX版本称为AUX-U。下表指定了所有选择准则的情况以及配置（0，0）和（1，1）的结果边界：0一元偏好上界vtpq(sp, sq)0(up < uq)βsq0(up > uq)βsp0(up = uq)β2sp + β02sq03.2. ICM偏好0一个更复杂的选择βspβsq边界的方法受到了并行ICM原则的启发[16]。在ICM中，给定当前解St，我们固定除一个变量外的所有标签，并在剩余变量上进行优化。在并行ICM中，这对所有变量同时进行，得到一个线性近似函数，可以高效地优化。这样的近似函数在LSA-TR方法中被用于选择自适应上界[9]。我们使用变量对来选择自适应上界。给定超模块势函数β∙spsq，我们固定除sp和sq以外的所有变量到当前解St。然后我们评估解St的能量E，首先将（sp，sq）=（0，1）代入，然后将（sp，sq）=（1，0）代入，分别表示为S01t和S10t。选择能量较低的配置进行精确建模。这对所有超模块势函数同时进行。我们将这个LSA-AUX版本称为AUX-ICM，并在下表中指定了每种情况下的选择边界：0ICM偏好上界vtpq(sp, sq)0E(S01t) < E(S10t)βsp0E(S01t) > E(S10t)βsq0E(S01t) = E(S10t)β2sp + β02sq03.3. 距离从当前解St计算0另一种决定哪个配置（0，1）或（1，0）应该被精确建模的方法是基于与当前解的距离。考虑超模块势函数β∙spsq，令Dt = (dtp | p ∈Ω)为每个像素到当前解St边界的最短距离的向量。我们认为距离边界更近的变化比距离较远的变化更可取。假设当前配置（stp，stq）=（0，0）。如果像素p比像素q更接近边界，即dtp  dtq)βsp0(dtp = dtq)β2sp + β02sq0(1, 1) ∧ (dtp > dtq)βsq0(1，1) ∧ (dtp < dtq)βsp0基于距离的选择边界的方法具有一个有趣的特性。隐含地，它定义了一个大的段的族Ct = {S � Ω | STVt =Esup(S)}，其中上界STVt与原始的超模块能量项Esup(S)相一致。这意味着我们在Ct中对原始能量进行了精确优化。族Ct非常大。例如，它包含了所有与当前解St计算的距离变换Dt的水平集对应的段，参见图1的(a-左)。但这只是Ct中段的一个小子集。实际上，任何一个在距离变换的梯度方向上从标签1到0的转变发生的段也在Ct中，参见图1的(a-右)。值得注意的是，许多不在Ct中的段仍然可以由上界STVt精确地建模其轮廓的大部分部分。图1的(b)展示了一些具有精确建模部分的段的示例，绿色表示精确建模的部分，红色表示不精确建模的部分。在轮廓的红色部分中，从1到0的转变要么与梯度方向相反（b-左），要么与梯度平行（b-右）。这种转变的上界不是紧密的。由于距离变换的正则化特性，族Ct由具有平滑边界的连贯段组成。这样的段更有可能成为视觉应用的候选解。相比之下，像[18]中随机选择边界会得到一个不太可能包含（即精确建模）具有平滑边界的段的族Ct，因为随机配置集不太可能与平滑轮廓重合。我们将基于距离的LSA-AUX版本称为AUX-DIST。虽然基于距离的解决方案是非常好的候选解，但将距离准则与一元偏好相结合可以得到一个额外的候选解子集。在这个子集中，候选解根据一元偏好与距离变换的水平集有所偏离。我们将这种LSA-AUX版本称为AUX-DIST-U。下表指定了选择准则和配置（0，0）和（1，1）的结果边界：0(a)0(b)0图1.距离偏好。a）左：当前解St（蓝色）及其距离变换的等级集（灰色）属于Ct。右：Ct中的一个段（绿色），其中从1到0的转变与梯度方向对齐（黑色箭头）。b）不属于Ct的段，但具有精确建模的大边界部分（绿色）。不准确边界的部分显示为红色。0(stp,stq)∧组合偏好上界vtpq(sp,sq)0(0,0)∧(dp+updq+uq)βsp0(0,0)∧(dp+up=dq+uq)β2sp+β02sq0(1,1)∧(dp−updq−uq)βsp0(1,1)∧(dp−up=dq−uq)β2sp+β02sq03.4. 超模邻域大小0选择上界的另一种方法是基于超模邻域的大小。给定当前解St，我们可以测量每个像素p的超模势(p,r)与前景中的r的数量ntp：0ntp=0(r∈Np)∧(mpr>0)str。(9)0考虑超模势(p,q)。如果两个像素都在前景中且(ntp>ntq)，这在大多数情况下意味着q离边界更近。因此，我们精确地建模了保持不变的配置(1,0)。如果两个像素都在背景中且(ntp>ntq)，这意味着p离边界更近。因此，我们精确地建模了保持不变的配置(1,0)，其中q保持不变。远离边界的像素具有平坦值ntp，该值为零（在背景中）或超模邻域的大小（在对象内部）。下表指定了选择准则和配置(0,0)和(1,1)的结果上界：49260上界vtpq(sp,sq)的超邻域大小0(ntpntq)βsp0(ntp=ntq)β2sp+β02sq0(r∈Np)∧(mpr>0)mpr∙str，因为在实践中它的表现稍微好一些但一致。我们将这个版本的LSA-AUX称为AUX-SNS。04. 移动辅助剪切0受多标签[3,17]和二进制[10]能量上的移动算法的启发，下面我们提出了两种二进制移动扩展类型。与自适应上界方法相反，移动扩展通过显式或隐式地限制搜索空间来实现更好的性能。04.1. α-扩展辅助剪切0第一种类型基于α-扩展，其中当前解可以增长或缩小，如[10]所示。这些移动会导致某些配置无效，允许剩余的有效配置通过近似精确地建模。在每个α-扩展移动中，我们对当前具有标签α的所有变量进行硬约束，并运行辅助剪切方法直到收敛。我们重复交替α的过程直到收敛。注意，α-扩展可以与LSA-AUX [9]和Sec.3中的任何自适应辅助剪切方法结合使用。图2展示了限制辅助剪切搜索空间的优势。列对应于当前解中两两势函数（stp，stq）的四种可能配置。行对应于候选解中势函数（sp，sq）的四种配置。根据当前配置，在每种方法中选择适当的上界（每个部分中的绿线）。如果有两个选择，括号中指定了另一种选择。然后，我们指定每个候选解中（sp，sq）的每种可能配置是否是精确近似。可以看出，LSA-AUX[9]（黄色）在16种情况中有10种是精确的。自适应辅助剪切（灰色）在16种情况中有12种是精确的。最后，自适应方法的α-扩展（蓝色和粉色）在9种情况中有8种是精确的，因为其中一些配置是无效的。每当我们使用Sec.3中提出的任何方法的扩展移动时，我们在其名称后面添加-EXP后缀。例如，当AUX-U与扩展移动一起使用时，我们称之为AUX-U-EXP。04.2. 指南针移动0第二种移动方式基于段边界的几何形状。它受到顺序的启发。0� - 精确近似           �  - 不准确近似 �  - 无效移动0当前配置 新配置（0,0）（0,1）（1,0）（1,1）0LSA-AUX [11]（0,0）����（0,1）����（1,0）����（1,1）����0当前配置的近似0.5β �� + �� β� β� 0.5β �� + ��自适应AUX（0,0）����（0,1）�（�）���（�）（1,0）�（�）���（�）（1,1）����0当前配置的近似β� �βy ) β� β� β� �βy )0自适应AUX-EXP00扩展0（0,0）����（0,1）����（�）（1,0）����（�）（1,1）����0当前配置的近似N/A β� β� β� �βy)0自适应AUX-EXP01扩展0（0,0）����（0,1）�（�）���（1,0）�（�）���（1,1）����0当前配置的近似β� �βy ) β� β� /0图2.由于受限的搜索空间，具有扩展移动的自适应辅助割具有更高比例的精确边界。0在多标签能量的背景下提出了保持移动。在保持移动中，根据移动的方向，每个像素在选择的标签集上进行扩展。相比之下，在每个指南针移动中，选择一个方向（上，下，左，右），对于该方向中的所有超模块对势，我们选择配置（1，0）来精确建模上界。这允许对顶部、底部、左侧或右侧边界的变化进行精确的上界。我们保持交替移动，并对每个移动运行辅助割直到收敛。我们称这种方法为指南针移动。图3（顶部）示例说明了一个小例子上的指南针移动。考虑方向“右”。对于任何超模块势（p，q），其中q在p的右侧，我们精确建模配置（sp，sq）=（1，0）。条纹区域指定了像素q相对于像素p的可能位置。请注意，我们任意决定将p上方的像素视为其右侧。其他方向的处理方式类似。与基于距离的偏好一样，给定当前解St，指南针移动也定义了一个连贯的段族Ct，其中上界是精确的。图3（底部）显示了特定解St和方向“右”下的段的示例。绿色边界部分由于与所选方向对齐而被精确建模。蓝色边界部分由于需求5b而被精确建模。49270St0右 上0Ct0左 下0q0p0q0p0q0p0q0p0图3. 指南针移动：（顶部）-给定像素p和条纹区域中的任意像素q，配置（1，0）对于“右”，“上”，“左”，“下”方向进行精确建模。（底部）-给定St和方向“右”，Ct族中的段的示例。0请注意，与明确限制搜索空间的扩展移动不同，指南针移动的限制是隐含的。错误方向的变化是可能的，但不太可能，因为它们具有较松的上界。这个版本的辅助割被表示为AUX-COMPASS。05. 应用0下面我们将我们的方法应用于平方曲率正则化[19]、来自[9]的几个基准能量，如修复、具有排斥力的分割和二值反卷积，以及具有紧凑[5]和多区域[6]形状先验的分割。对于每个应用，我们将提出的自适应和移动扩展与原始LSA-AUX（这里简称AUX）、其随机排列版本LSA-AUXP（AUXP）和LSA-TR进行比较。为了完整起见，我们还将其与其他标准优化方法进行比较，如QPBO [21]、LBP [20]、IPFP[16]、TRWS和SRMP[13]。除非另有说明，所有局部近似方法都以整个域分配给前景进行初始化。所有全局优化方法最多运行5000次迭代。05.1. 平方曲率0下面我们重点讨论[ 19]中的平方曲率模型。结合外观项，该模型产生具有次模和非次模成对项的离散二进制能量。曲率项的权重相对于外观项由参数λ curv控制。对于这个应用，我们使用毕加索的唐吉诃德绘画。我们改变超模曲率项的权重λcurv，并评估所提出扩展的性能。最好的三个与LSA-TR、AUX和AUXP进行比较，参见图4。所有方法都从基于外观项的最大似然解开始。当超模曲率项的权重增加时，所提出的方法始终优于LSA-TR（蓝线）、AUX（红线）和AUXP（绿线）。所有其他标准优化方法，如QPBO、LBP、TRWS、SRMP和IPFP，甚至比所提出的扩展中最差的方法差得多，AUX-DIST-0输入图像0图4. 平方曲率模型。我们使用前景和背景外观的高斯分布（µ =0，σ = 0.2）和（µ = 1，σ = 0.2），以及7×7的角度分辨率。0算法名称0平均运行时间0平均能量 #最佳排名0MCBC 2053.89 秒 -49550.1 59 10BPS (LBP) � 72.85 秒 -49537.08 6 60ILP 3580.93 秒 -49536.59 5 70SA NaN 秒 -49533.08 11 40TRWS-LF 2106.94 秒 -49519.44 4 80LSA 0.08 秒 -49547.61 16 30AUX-DIST 0.07 秒 -49538.72 7 50AUX-DIST-U 0.07 秒 -49548.78 33 20AUX-ICM 0.07 秒 -49533.09 4 80表2. 汉字修复数据库 [ 12 ]。0U-EXP，详细信息请参见补充材料。05.2. 汉字修复0下面我们考虑汉字修复的任务，dtf-chinesechar [ 12]。我们使用作者提供的一组预训练的一元和成对势函数与数据集一起。表2报告了所提出扩展的最好三个和先前发表的结果[ 12 , 9]。我们省略了排名低于八的方法行。AUX-DIST-U排名第二，但运行速度比排名第一的MCBC快五个数量级。05.3. 排斥分割0下面我们考虑基于像素外观和相对位置的吸引和排斥成对势函数的分割[ 9]。我们使用16邻域系统，并定义势函数如下：ω ( p, q ) = − ∆( p,q )+ c0dist(p,q) . 这里dist(p,q)表示图像像素p和q之间的距离，∆(p, q)是它们各自强度的差异。常数c使相似的邻居相互吸引，产生次模势，并且排斥其他情况，产生超模势。λ reg是成对项的权重。E(S) =�p∈Ω(Ip − 19�q∈Npsq)2,(10)σ = 0.249280输入图像0图5. 排斥和吸引力分割。我们使用µ fg =0.4,  µ bg =0.6,  σ=0.4来表示外观，λ reg =100和c=0.06。0图5报告了结果。所提出扩展的最好三个优于AUX、AUXP和所有标准优化方法，除了LSA-TR。这是唯一一个许多所提出扩展都不如原始AUX的应用，这表明每个应用都需要专门设计的自适应边界。05.4. 二进制反卷积0考虑一个与均匀3×3滤波器卷积并与高斯噪声� N (0 , σnoise)相结合的二进制图像。二进制反卷积的目标是恢复原始的二进制图像。能量定义为0其中Np表示像素p周围的3×3邻域窗口，所有成对的相互作用都是超模的。图6报告了结果。在所提出的扩展中，最好的是AUX-ICM和AUX-U，它们明显优于原始的AUX和AUXP，但不及LSA-TR。对于这个应用，LSA-TR与IPFP共享第一名。这与[9]中的结果一致。05.5. 多区域对象的分割0在本节中，我们专注于MRI肝脏分割。输入图像包含一个带有四个肿瘤的肝脏。该问题被定义为非次模能量的最小化[10]。它采用了多区域模型[6]，能够编码区域之间的几何相互作用，如包含和排除。0图6.二值去卷积。我们报告了噪声水平σ的能量，平均值为十个随机实例。0肝脏由一个具有五层二值变量的图模型建模，对应于肝脏（Fg）和四个肿瘤（A，B，C，D）。见图7，(a-b)的示意图。使用次模和超模的层间成对势函数实现了肿瘤在肝脏内和肿瘤之间的排除约束。此外，我们在每一层上使用了Potts正则化。有关技术细节，请参见补充材料。图7，(c-d)显示了结果。我们使用涂鸦作为外观和硬约束。顶部图表比较了能量和运行时间方面的方法。底部图表对最有趣的部分进行了放大。大多数方法得到的解决方案都存在包含和排除约束的违规。LSA-TR，AUX-DIST，AUX-DIST-U实现了相同的最低能量，其中AUX-DIST的速度快了一个数量级。05.6. 广义紧凑形状先验0下面我们将我们的方法应用于具有广义紧凑形状先验的分割，该先验在[10]中提出。[5]中的原始紧凑形状先验将对象分为围绕用户给定中心的四个象限，每个象限必须遵循该象限的允许方向，见图8，(a)。广义先验[10]不是将对象分为四个象限，而是将背景分为四个区域，如图8，(b)所示，对应于标签：左上（TL），右上（TR），左下（BL），右下（BR）。前景对象（fg）也有一个标签。与多区域模型类似，该模型使用具有四个二值层的图：TL，TR，BL，BR。每一层只允许在某些方向上出现不连续性，使用Potts。二值层的相应节点之间还存在成对的超模排除约束，以强制实现一致的前景对象。见图8，(c-d)以及LSA-TR, E = 409738AUXP, E = 410701AUX, E = 410751IPFP, E= 1126304LBP, E = 485367SRMP, E = 411011QPBO-I, E = 410166TRWS, E = 499497AUX-DIST, E = 409738 AUX-DIST-U, E = 409738ABCDABDC(a)(b)(c)(d)SΩFgFgTLBLTRBRFg49290QPBO, 74% 标记0涂鸦0背景 前景 A B C D0未标记0排除0背景0前景0背景0前景0图7. 多区域肝脏分割。 (a) 肝脏和肿瘤的示意图，(b) 不同图层的相应节点之间的包含和排除交互作用，(c) 输入涂鸦 -肝脏（蓝色）和肿瘤（绿色，黄色，青色，洋红色）以及分割结果，(d) 能量与时间的关系图（顶部）和放大图（底部）。我们设置权重λsub= λsup = 100和λPotts = 25。0LSA-AUXE=0T=3.38s0LSA-AUXPE=0T=2.86s0IPFP E=-167540T= 105s0LBP E=-309556T= 262s0QPBO-I E=-77752T=55.3s0SRMP E=-316122T=1118s0TRWS E=-184754T=253s0LSA-TR E=-336486T= 31s0输入图像 用户涂鸦 外观项0AUX_DIST_U_EXPE= -336649T=4.69s0AUX_DIST_UE= -312618T=0.77s0（a）（c）0（d）（e）0S Ω0Ω0S0BL BR0TR TL0BL BR0TR TL0排除0（f）（g）03.8％标记0图8. 广义紧凑形状先验：（a）[5]中的模型，（b）[10]中的广义模型，（c）[10]中广义模型的示意图，（d）无法使用[5]建模的片段，（e）可以使用[10]进行分割，（f-e）结果和比较。0技术细节的补充材料。0[5]中的模型是广义模型[10]的特例，当背景标签之间的转换水平和垂直对齐时，如（b）所示。广义模型不需要这样的对齐。例如，它可以使用（e）中显示的四个区域来建模（d）中的对象。由于对轮廓方向的限制，无法使用[5]对该对象进行分割。0下面我们报告结果。图8，（f）显示了输入图像，用户涂鸦和得到的外观项，然后是每种方法的最终分割。图8，（g）比较了能量和时间方面的方法。大多数方法得到了违反方向和连贯性约束的差解。LSA-TR和AUX-DIST-U-EXP是唯一能够优化这种能量的方法，其中AUX-DIST-U-EXP得到了最低的能量。0在更短的时间内优化能量。06. 结论和未来工作0我们对LSA-AUX框架提出了两个扩展。首先，我们结合了能量和基于距离的选择准则来选择上界。这导致对于更可能或更接近当前解的配置，得到更紧的上界。其次，我们提出了LSA-AUX的两个移动扩展，通过限制搜索空间来实现更准确的上界。我们得出结论，不同的扩展对于不同的应用效果更好，为设计应用特定的自适应上界和移动留下了空间。我们还计划将我们的方法扩展到高阶和多标签能量。此外，基于子模函数理论设计上界也是一个有趣的方向。49300参考文献0[1] I. Ben Ayed，L. Gorelick和Y.Boykov。适用于一般高阶函数的辅助割。在IEEE计算机视觉和模式识别（CVPR）会议上，页码1304-1311，俄勒冈州波特兰，2013年6月。10[2] E. Boros和P. L.Hammer。伪布尔优化。离散应用数学，123:2002，2001年。1，20[3] Y. Boykov，O. Veksler和R.Zabih。通过图割进行快速近似能量最小化。IEEE模式分析与机器智能交易，23:1222-1239，2001年11月。1，50[4] W. Brendel和S.Todorovic。分割作为最大权重独立集。在神经信息处理系统（NIPS）中，页码307-315，2010年。10[5] P. Das，O. Veksler，V. Zavadsky和Y.Boykov。带有紧凑形状先验的半自动分割。图像视觉计算，27（1-2）：206-219，2009年。2，6，7，80[6] A. Delong和Y. Boykov. 多区域对象的全局最优分割.在IEEE第12届国际计算机视觉会议(ICCV 2009)上, 2009年,页码285-292.  2 ,  6 ,  70[7] S. Fujishige. 子模函数与优化. Elsevier, 2005年.  80[8] M. Goemans和D. Wiliamson.使用半定问题改进最大割和可满足性问题的近似算法. ACM,42(6):1115-1145, 1995年.  10[9] L. Gorelick, Y. Boykov, O. Veksler, I. B. Ayed,和A. De- long.用于二进制成对能量的次模块化.在计算机视觉和模式识别(CVPR)上, 2014年.  1 , 2 ,  3 ,  5 ,  6 ,  70[10] L. Gorelick, Y. Boykov, O. Veksler, I. B. Ayed,和A. De- long.用于二进制成对能量的局部次模块化. 在PAMI上, 已接受, 2017年.1 ,  5 ,  7 ,  80[11] J. H. Kappes, B. Andres, F. A. Hamprecht, C. Schnorr, S.Nowozin, D. Batra, S. Kim, B. X. Kausler, T. Kr¨oger, J.Lellmann, N. Komodakis, B. Savchynskyy,和C. Rother.结构化离散能量最小化问题的现代推理技术的比较研究.计算机视觉国际杂志, 页码1-30, 2015年. 1.  10[12] J. H. Kappes, B. Andres, F. A. Hamprecht, C. Schnorr, S.Nowozin, D. Batra, S. Kim, B. X. Kausler, J. Lellmann, N.Komodakis,和C. Rother.一种离散能量最小化问题的现代推理技术的比较研究.在计算机视觉和模式识别(CVPR)上, 2013年, 页码1328-1335.  1 ,60[13] V. Kolmogorov和T. Schoenemann.广义序列树重新加权传递. arXiv:1205.6352, 2012年.  1 ,  60[14] K. Lange, D. R. Hunter,和I. Yang.使用替代目标函数进行优化转移. 计算和图形统计杂志, 9(1):1-20,2000年.  10[15] R. Lazimy. 混合整数二次规划. 数学规划, 22:332-349,1982年.  10[16] M. Leordeanu, M. Hebert,和R. Sukthankar.一种用于图匹配和地图推理的整数投影固定点方法.在神经信息处理系统(NIPS)上, 2009年, 页码1114-1122.  1 ,  3 ,  60[17] X. Liu, O. Veksler,和J. Samarabandu.用于基于图割的优化的保序移动. IEEE模式分析与机器智能杂志,32(7):1182-1196, 2010年7月.  1 ,  50[18] M. Narasimhan和J. A. Bilmes.一种具有应用于判别式结构学习的次模-超模过程. 在UAI上,2005年, 页码404-412.  1 ,  3 ,  40[19] C. Nieuwenhuis, E. Toeppe, L. Gorelick, O. Veksler,和Y.Boykov. 高效的二次曲率. 在IEEE计算机视觉和模式识别(CVPR)上,2014年.  2 ,  60[20] J. Pearl. Reverend Bayes对推理引擎的分布式分层方法.在人工智能国际会议上, 1982年, 页码133-136.  60[21] C. Rother, V. Kolmogorov, V. Lempitsky,和M. Szum- mer.通过扩展的屋顶对偶性优化二进制MRFs.在计算机视觉和模式识别(CVPR)上, 2007年, 页码1-8.  1 ,  60[22] M. Tang, I. B. Ayed, and Y. Boykov.二进制能量的伪边界优化. 在计算机视觉欧洲会议(ECCV)上, 苏黎世,瑞士, 2014年9月.  1 ,  20[23] Y. Yuan. 用于优化的信任域算法综述.在第四届国际工业与应用数学大会(ICIAM)上, 1999年.  1