拉格朗日分解与对偶上升解的二次分配问题研究

1图匹配的拉格朗日分解与对偶上升解的研究Paul Sw oboda1、Carsten Rother2、Hassan Ab u Alhaija2、Dagmar Kain müller3和Bogdan Sa vchynsk yy21IST奥地利，2TU Dresden，3MPI-CBGpswoboda@ist.ac.at摘要我们研究二次分配问题，在计算机视觉中也称为图匹配。这个问题的两个主要解决方案优化拉格朗日分解duals与次梯度和对偶上升（也称为消息传递）更新。我们进一步探索这个方向，并提出了几个额外的拉格朗日松弛的图匹配问题以及相应的铝出租，这都是基于一个共同的对偶上升框架。我们广泛的实证评估给出了一些理论见解，并提出了一个新的国家的最先进的任何时间求解所考虑的问题。我们对最先进技术的改进在一个新的数据集上特别明显，该数据集具有大规模稀疏问题实例，每个实例包含超过500个图形节点1. 介绍在计算机视觉及其他领域，二次分配问题，也称为图匹配、特征对应和特征匹配，引起了人们极大的兴趣。这个问题类似于离散两图模型上的最大后验概率（ MAP ） 推 断 ， 在 文 献 中 也 称 为 条 件 随 机 场（CRF）。它的不同之处在于附加的唯一性约束：每个标签最多只能使用一次。这种唯一性约束使其非常适合攻击，例如。跟踪问题或形状匹配。在这两种情况下，特征点或对象部分必须在多个帧之间一一匹配。不幸的是，唯一性约束阻止了用于MAP推理的有效消息传递求解器对该问题的天真应用。出于这个原因，开发了许多专用的图形匹配求解器，请参阅下面的相关工作。另一方面，有效的双块坐标上升（也称为消息传递）算法，如TRW-S [33]，是条件随机场中MAP推理的最有效求解器之一。此外，图匹配问题，在可能引入许多额外的变量，在标准的成对CRF中可以被描述为MAP推理问题。这种方法已经超过了大多数最先进的图匹配求解器。因此，期望设计出不表现出上述缺点的专用收敛消息传递求解器，即，（i）直接操作图匹配问题的紧凑表示，以及（ii）使用来自MAP推理社区的技术来获得计算效率。为了实现这一目标，我们提出了（i）几个拉格朗日分解的图匹配问题和（ii）新的有效的消息传递解决这些放松。我们在广泛的实证评估中显示了它们的功效相关工作术语图匹配指的是模式识别中的一些不同的优化问题，请参阅[18]的评论。我们指的是明确称为二次分配问题（QAP）的特殊版本[36]。最近，图匹配被推广到超图匹配问题（参见[43]和其中的参考文献），其在两个以上的图之间进行匹配。二次分配问题在1957年的[13]中首次提出。由于旅行商、最大团、图同构和图划分等NP完全问题都可以直接归结为QAP问题，因此该问题本身也是NP难的。它对众多应用的重要性大大提高了它的分析：（已经老化的）概述[41]包含362篇参考文献，其中超过150篇文章提出了新的算法，超过100篇文章提出了与此问题相关的新理论结果。几乎所有可能的求解器范例都被用于QAP测试。这些包括但不限于基于拉格朗日分解的凸松弛[31，52]，线性[6，22]，凸二次[9]和半定[46，51，63]松弛，它们可以直接用于获得近似解或仅用于提供下界。为了收紧这些界限，提出了几种切割平面方法[11，12]。另一方面，各种原始算法，都是（i）确定性的，如局部搜索[5，44]，分级分配方法[25]，不动点迭代[39]，谱160716082技术及其衍生物[17，38，53，62]和（ii）随机，如随机游走[16]和蒙特卡洛抽样[37，49]，建议提供近似解决方案的问题。总之，这些方法作为构建块精确分支定界[10，23，26]算法和其他非凸优化方法[25，59，64]。优秀调查[15，41]包含进一步的参考资料。对于NP难问题，没有一种方法可以有效地解决所有QAP实例。不同的应用程序需要不同的方法，我们在这里集中在特定的计算机视觉的prob- lem实例。传统上，在这个社区主要使用原始算法，因为对低计算时间的需求通常支配着获得最优性保证的需求然而，最近提出的两种基于拉格朗日分解（也称为计算机视觉中的对偶分解）的求解器[52，61]已经显示出优越的结果，并超过了许多最先进的原始算法。对偶分解求解器[52]将问题表示为二进制CRF的MAP推断、线性分配问题和少量变量上的许多小规模QAP的组合;连接这些子问题的拉格朗日乘子使用次梯度方法更新虽然求解器在计算机视觉数据集上显示出更好的结果，但我们怀疑其效率可以通过切换到不同的更新方法来进一步提高，例如bundle [30，32]或块坐标上升[57]。这种怀疑是基于CRF [29]中MAP推断的此类求解器的比较以及与其他组合优化问题相关的类似观察（参见例如，[45]）。匈牙利信念传播（HBP）[61]认为多标签CRF和线性分配的组合是子问题;拉格朗日乘数更新的块坐标上升（消息传递）算法和得到的下限内采用分支定界求解器。然而，众所周知[34]，消息传递的效率很大程度上取决于发送消息的时间表。具体来说，双上升算法的效率取决于选择上升方向（优化变量块）和执行这些上升操作的顺序可以说，潜在的多标签CRF子问题是至关重要的，消息传递必须有效地处理它HBP [61]（双上升）算法基于最近的消息传递框架[50]。在局部多面体松弛的情况下，我们的算法与SRMP方法[34]一致，SRMP方法是著名的TRW-S算法[33]的高阶推广。我们的实验评估为图匹配问题提出了一种新的最先进的方法，该方法优于对偶分解[52]和HBP [61]求解器。我们提出了更严格的凸松弛我们所有的方法。此外，我们显着提高性能的HBP算法通过改变其消息传递时间表。附 录 中 给 出 了 证 明 。代 码 和 数 据 集 可 以 从https://github.com/pawelswoboda/LP_MP 获得。记法。无向图表示。通过=（V，E），其中V是有限节点集，E<$V是边集。v∈V的相邻节点集w.r.t.图G记为NG（v）：={u：uv∈E}。一个集合X<$Rn的凸包用conv（X）表示。2. CRF和图形匹配首先，我们引入条件随机场和状态的图匹配问题作为一个额外的唯一性约束。其次，我们考虑的图形匹配问题，这是一个逆配方，再加上原来的配方，往往会导致更快的算法。条件随机场（CRF）。设G=（V，E）是一个无向图。对于每个节点u∈V，我们关联一个变量xu，它的值取在一个有限的标签集合Xu中，{（1，0，. . . ，0），（0，1，0，. . . ，0），. . . ，（0，. . . ，0，1）}。因此，我们认为，每个标记对应于Q单位向量。记法XA表示笛卡尔积u∈A<$VXu。一个向量x∈XV，其坐标为（xu）u∈V，称为标号。同样，我们使用符号xA∈XA（特殊情况为xuv∈Xuv<$Xu×Xv ） 表 示 标 记 的 一 部 分 。 函 数 θu ：Xu→R，u∈V和θuv：Xuv→R，uv∈E是势函数，它们定义了标签和标签对的局部性质CRF的能量最小化或MAP推断问题是使用与MPLP算法[24]类似的消息传递调度，其被示出[29，34]明显慢于SRMP（TRW-S）[34]的调度。Σminθu（xu）+x∈XVu∈VΣθ uv（x uv）。（一）uv∈E本文研究了图匹配问题的几种拉格朗日分解。其中一些是已知的，例如。一个用于HBP算法[61]，一个对应于图匹配的成对CRF表示的局部多面体松弛。据我们所知，其他的还没有发表。对于所有这些分解，我们提供了有效的消息传递（1）中的目标被称为CRF的能量大量的应用问题可以有效地转换为格式（1），参见例如[29，54]。这决定了它对计算机视觉、机器学习和其他一些科学分支的重要性[54]。虽然问题（1）通常是NP难的，但提出了许多精确和近似的求解器[29]。1609LSt图形匹配。虽然问题（1）的格式允许我们有效地表达许多实际上重要的优化任务，但某些应用需要得到的标记x来满足附加约束。特别地，对于图匹配问题，没有标签可以被取两次。设给定一个公共的标签论域L ，使得Xu<$L<$u∈V。我们要求每个标签s∈ L最多被取一次，即 |{u ∈ V：x u= s}|≤ 1。换句话说，我们寻找一个内射映射（xu）u∈V：V→ L。这个问题可以表述为Σ Σminθ u（x u）+θ uv（x uv）S.T. x u/=xvuv.CRF的局部多面体。MAP推理问题（1）可以通过对每个节点和边对应的势进行分组，使用过完备表示[54]将其表示为整数线性规划（ILP）[35]分离成不同的载体也就是说，θw（xw），w∈V<$E代表一个坐标为（θw（xw））xw∈Xw的向量。实值向量μw与θw具有相同的维数，并且对于x w的相应的线性规划（LP）松弛如下：Σ最小值θw，µw（4）w∈V ∈Ex∈XVu∈Vuv∈E（二）Σμw（xw）=1，μw（s）≥0，w∈V∈E，s∈Xw，图匹配是NP难的，因为它等价于在平凡情况下的CRF（1）的MAP推断，当图的节点包含相互不相交的标签集时。逆图匹配如果要匹配的标签的论域L与图的节点集具有相同的大小，则会出现特殊情况|L|为|V|.则每个内射映射（xu）u∈V：V→ L也必是双射。因此，每个可行标号x∈XV对应于V的一个置换。在这种情况下，图匹配问题（2）也可以根据逆置换来处理到为此，设逆图G′=（V′，E′）由下式给出：V′=L;逆标号集X′={v∈V：s∈Xv}xw<$∈Xwμ uv（x uv）=μ u（x u），uv∈E，u∈uv，xu∈X u.xv∈X v（4）的约束定义了局部多面体LG。注意，添加完整性约束μ w∈ {0，1} |XW|使问题（4）等价于其组合公式（1）。松弛两两可分线性规划（IRPS-LP）下面我们来描述一个常见的问题：[50]中研究的一种新的局部多胞形松弛方法，推广了[4]中的局部多胞形松弛方法。重要的是，相同的格式也适合图匹配问题的拉格朗日分解，我们将在下面考虑这使得有可能考虑从一般的观点来看，所有这些放松都是一次性iQs与每个节点s∈V相关联;分别为XL=设因子图G=（F，E）由节点F=X′是逆标号的集合，X′表示s∈Lsst{1，. . . ，k}，称为因子和边E，称为因子边。Xs×Xt;定义了逆图的边集设Xi<${0，1}dim（Xi），i∈F，是二元向量集当E′={st∈V′×V′：nxst∈X′′ ′ ′S.T. xs xt∈E}。的和（ii）A（i，j）<${0，1}dim（Xi）×Kij，ij∈E，Kij∈N是对于s，s∈V，xs∈X′，逆成本θ为：.θ′（xs）=θx（s），θ′（xst）=θxstS（s，t），x st∈ E具有二进制项的矩阵，其将二进制向量从从{0，1}Kij转换为二进制向量，即，A（i，j）：Xi→Kssst0，否则。{0，1}i j. IRPS-LP是一类问题，它面临着-考虑由此产生的逆图匹配问题根据G.ΣΣ Σminθ′（x）+θ′（x）S.T. X/= x st.minθi，µix∈X′sLs∈Lstst s tst∈E′Gi∈F .Σ（三）.Λ：=µ. . .价格：μ i∈ conv（X i） i ∈ F.KG1标号x∈XV和逆标号y∈X′对应A（i，j）µi=A（j，i）µjij∈E当且仅当xu=s∈V惠ys=u∈V。注意，当边缘集合E是稀疏的时，逆边缘制约因素A（i，j）µi=A（j，i）µj相互关联“E”可能不是。在这种情况下，反问题的计算复杂度高于原始问题。3. 拉格朗日分解由于图匹配问题（2）是NP困难的，因此通常考虑凸松弛。下面，我们提出了三个拉格朗日分解为基础的松弛的问题。这些可以应用于原始图匹配问题（2）、逆图匹配问题（3）以及两者的组合。由于所有这些松弛都是基于CRF（1）的MAP推理的著名局部多面体松弛[47，55]，我们首先简要概述一下这种松弛1610因子边和称为耦合约束。 当代表-将局部多面体松弛（4）表示为（5），我们假设F=V∈E且E={{u，uv}，{v，uv}：uv∈E}。Xw的凸壳完全由（4）中的第一行约束定义，因为Xw构成一组单位二进制向量。（4）中的第二条约束线定义了耦合约束。束缚我们用变量名µ表示（一般来说）非二进制向量µi∈conv（Xi），用x表示二进制向量xi∈Xi，i∈F。3.1. 图匹配问题松弛。下面，我们描述图匹配（2）问题的三个放松，其适合IRPS-LP（5）格式。第一1611u第一种方法导致了一个特殊构造的CRF的标准局部多面体松弛（4），第二种方法利用了（4）之上的附加耦合约束，而第三种方法使用了网络流子问题。此外，我们使用逆公式（3）并构建两个额外的IRPS-LP。（R1）图形匹配作为CRF。为了构建与图匹配等价的CRF，我们从底层CRF开始IRPS-LP框架。对于有效实现至关重要的是，（6）可以通过最小成本流求解器[7]有效求解。下面我们将（6）作为一个单独的因子M处理，并将其与（4）联系起来，以获得IRPS-LP。它的因子图定义为F=V<$E <${M}和E={{u ，uv}，{v，uv}：uv∈E}{{u，M}：u∈V}. 所得IRPS-LP制剂如（2）中所示，并表示边中的唯一性约束为因素 为此，我们（i）用新的连接一个N Y T W O N O的边。具有至少一个共同点的组min Σw∈V ∈Eθw，µw Σu∈Vθ标签，即E：=E{uv∈V2 ：XuXv（ii）将μ∈LG，μ∈M，边势θuv<$0到所有n条边E<$\E;（iii）对于所有µm（s）=µm（s），u∈V，s∈X.uv∈E<$我们指定θuv（x，x）：=∞<$x∈Xuu u u第十条; 任何结果CRF（1）的求解是一个假设。<根据IRPS-LP的松弛是局部多面体（4）。这种方法通常会导致二次数量的额外的边缘电位，这可能会变得棘手的图形匹配问题的大小的增长。（R2）带标签因子的松弛。每个标签s∈ L，我们引入了一个额外的标签因子，它跟踪分配标签s的节点。这个因子Xs：={u∈V：s∈Xu}<${#}的标签集由以下内容组成：节点u∈V，可以被分配标签s和一个额外的虚拟节点#表示标签s的未分配。La- bel #是必要的，因为并不是每个标签都需要采取。因子集变为F=V<$E<$L，耦合约束集E={{u，uv}，{v，uv}：uv∈E}<${{u，l}：u∈V，l∈Xu}。得到的IRPS-LP公式如下：首先，我们设置θ=0。唯一性约束的表示（6）已经被已经使用的例如，在[20]中。然而，他们的优化技术缺乏收敛性保证和单调性的下限，我们的方法具有。文献[61]把（R3）的Lagrange对偶问题作为图匹配问题的一个相关问题来考虑。他们的松弛等价于（R3），但他们的算法与我们的不同我们参考第5节讨论差异，参考第6节进行实验比较。（R4-R5）耦合原始图匹配（2）及其逆（3）。在特殊情况下|L|为|V|我们可以解决逆图匹配问题（3），而不是原创1（2）另一种选择是同时解决这两个问题，并通过要求（2）的标记是min Σw∈V ∈Eθw，µw Σs∈Lθ标签（3）这种做法使问题加倍大小，但它可能导致获得收敛所这种方法既适用于µ∈LGμs∈conv（Xs），s∈ L松弛（R2）和（R3）。所得的（R2）读数μu（s）=μs（u），s∈Xu.minΣΣθ，µθ′，μ′这里我们引入了附加势θs为标签µ，µ′w ww∈V ∈ Ew ww∈V′ ∈ E′法克托河初始时，我们设置θ=θ0。（R3）具有网络流因子的松弛。如果忽略（2）中的边缘势θuv，则该问题可以等价地重新表述为二分匹配[7]：Σμ∈LG，μ′∈LG′u ∈ V，u′∈ X u：μ u（u′）= μ′′（u）。这里，（R2）中的标签因子的角色已经被逆图匹配（3）的节点因子所取代我们最初在θ和θ′minμ∈Mu∈Vθu，μu另一个耦合的IRPS-LP，对应于（R3）读取.µ（s）= 1，u∈VminΣΣθ，µΣθ′，µ′M=（μu）u∈V≥0：n∈Xuuµ，µ′，µwww wu uu∈V，s∈Xu μu（s）≤1，s∈ Lw∈V ∈ Ew∈V′∈E′u∈V1612在这里，我们用线代替了唯一性约束μ∈LG，μ′∈LG′，με∈M（R5）u∈V，u′∈X：μ（u′）=μ耳不等式u∈V，s∈Xuµu（s）≤1，相当于u u uu'u对于μ u∈ {0，1} |Xu|. 已知M是满足M[7]的条件的所有二元向量的凸包，即conv（M <${0，1}dim（M））=M。因此，M适合于这里，网络流因子M控制原始标记μ和反向标记μ′的一致性。最初，我们设定θ=0，并在θ和θ′中平均分配成本。1613我i=1我（i，j）（i，j）u通过弛豫（R1）-（R5）获得的最佳值1.提案（R2）=（R3）和（R4）=（R5）。弛豫（R1）弱于（R2）和（R3）。我们用AD（θi，x∈，J）表示容许向量的集合。引理1（[50]）. 可接受的消息不减少对偶值，即，<$∈AD（θ φ，x<$，J）蕴涵D（0）≤ D（0）.我我4. 通用算法在这一节中，我们定义了IRPS-LP问题（5）的一般算法，它适用于分解例1. 让我们将定义1应用于CRF的局部多面体松弛（4）。设ij对应于{u，uv}，其中u∈V是某个节点，uv∈E是它的任一条关联边所以J={j}。则x∈ {\displaystyle x ∈ {\displaystyle x}}对应于局部最优标签(R1)–(R5) of the graph matching problem第3.1节。我们的算法是一个简化版本的xu∈argmins∈Xuθ u（s）和ν（s）=<$s=xu）. 因此我们可以将θu，uv（s）赋给[0，θu（xθ）-算法[50]，其中我们将几个参数固定到弛豫（R1）我们不直接优化IRPS-LP（5），而是考虑它的拉格朗日对偶w.r.t.耦合约束A（i，j）µ i=A（j，i）µ j。IRPS-LP 问 题 （ 5 ） 可 以 简 单 地 写 为minµ{\displaystyle\mathbb{\mathbb}Aμ=0，μ∈P}，其中θu（s）]。这确保满足（8）并且xu保持a重新参数化后的局部最优标签，即使存在Xu中的多重最优解站内短信权限.过程1表示我们的优化算法的一个基本步骤。它包括发送µ代表（µi）k，Aµ=0表示所有耦合连接，消息从节点i发送到其邻居J的子集。straintsA（i，j）µi−A（j，i）µj=0，P表示封装其余约束的通过对偶Aµ= 0用拉格朗日乘子的向量，⊤步骤1：从i∈F发送消息到J<$NG（i）1优化因子：x<$∈argmin<$θ i，μ i<$拉格朗日函数θ，µ−，Aµ = θ − A，µ。Af-i在引入θ：=θ−A之后，双物镜读作：X.i∈Xid≥ 0，xx（s）= 1D（μ）=最小µ{\displaystyle {\frac {{\frac {0}} μ∈P}。 众所周知[14]。2 选择δ∈Ris.t. δ（s）我≤ 0，x（s）= 0对于任何可行的μ，D（θ）≤θ，μμ，对偶问题在于使D（θ）在μ上最大化。从θ到θ我3最大化到J的可接受消息：称为等价变换或重新参数化在CRF社区的文献或信息传递（i，J）：=（（i，j））j∈J∈ argmaxθφ∈D（θφ，xφ，J）δ，θ现在我们将上述考虑应用于一般的i iIRPS-LP问题（5）. 具体地说，设i，j∈F是两个i因子图G中的相邻因子。 对于任何一个i且μj满足边ij∈E的耦合约束4 更新θ和θj，j∈J，根据（7）θi，μi=θi，µi联系我们=0过程1首先在第1行中计算因子i的最优标记，然后在（9）中计算消息更新，最后在第4行中更新成本θ。第2行中的成本δ被选择为±1，除了当i=M是网络流时=θi+A（i，j），μi（i，j），μjF.（R3）和（R5）的作用。在这种情况下，我们选择δ（u，xu）=0，xu =x拉格朗日乘子的值和符号定义了多少成本从当我们考虑i的相邻因子的子集J∈ NG（i）时，得到的等价变换为：Σθ→θ+A.∆和θ →θ−A∆. （七）联合1−|X u|、x u/= x计算（9）提供了一个最大可能的admis-从i到{J}的消息。本质上，它使因子i的成本向量尽可能均匀因此，在示例1的设置中，uv（s）变为等于θu（x）-θu（s）ii（i，j）（i，j）jj（j，i）j∈J下面我们在设置（7）中定义一个改进对偶的消息子类（i，j）定义1. 消息<$（i，j），j ∈ J称为可接纳的，如果存在x<$∈argmin<$θ，μ<$argmin<$θ <$，μ <$因此θi （s）=θ u（xu）对所有s∈X u. 以来（9）的结果是可接受的消息，过程1从不减少对偶目标，如从引理1得出的。双上升算法。让符号{j1，. . . ，jn}表示有序集合，使得jkjk+1，我并且另外.我我xi∈X i1614我我xi∈X ik=1，. . .，n. 下面的算法2将遍历一些因子i∈F，并调用过程1向/从某些邻居发送或接收消息（s）≥0，v（s）= 1，其中ν：=Ax*。 （八）算法2的工作原理如下：我们选择一个有序（i，j）≤0，v（s）= 0（i，j）i因子的子集{i，. . .，i} .对于每个因子i∈F，我们1K<1615vu算法2：IRPS-LP的双上升1 输入：I={i1，. . .，ik}<<$F，（J r（i）<$NG（i））i∈I，（Js（i）<$NG（i））i∈I2，其中iter = 1，. . . 做3，其中i = i1，. . . ，i kdo4接收信息：5，对于j∈Jr（i）do6使用输入（j，{i}）调用算法1。7端8发送信息：9使用输入（i，Js（i））调用算法1。10端部11颠倒i 1的顺序。. . ，i k和交换参与者12端部选择从其接收消息的因子的邻域Jr（i）∈ NG（i）和通过过程1向其发送消息的邻域Js（i）。我们运行算法2，{i1，. . .，ik}<（正向）和{ik，. . .，i1}<（向后方向）交替地进行，直到满足某个停止条件。由于算法2仅通过过程1重新参数化问题，并且后者保证不会减少对偶，因此算法2也是如此。关于算法2的进一步理论性质，我们参考[50]。5. 图匹配算法。对于图匹配问题的松弛（R1）-（R5）中的每一个，我们详细描述了在我们的实验中使用的算法2的参数：我们定义集合I，J r（i），J s（i）。算法名称。我们使用以下快捷方式将算法2专门化到松弛（R1）-（R5）：GM对应于（R1），AMP对应于（R2），AMCF对应于（R3）。为了获得弛豫（R1-R3 ） ， 我 们 使 用 原 始 图 （ 如 （ 2 ） ） 或 逆 图 （ 如（3））。这些选项分别用后缀-O和-I表示另外，两个耦合弛豫（R4）和（R5）分别由算法AMP-C和AMCF-C来解决总之，我们有八个算法GM-O，GM-I，AMP-O，AMP-I，AMP-C，AMCF-O，AMCF-I和AMCF-C。在表5中定义了集合I、Jr⑴和Js⑴。对于后缀为-I的算法，其值与后缀为-O的算法相同，但对应于逆图。我们假设图节点V：={u1，. . . ，u n}<和标签L：={s1，. . .得双曲余切值.| L|要<先给出。我们定义匹配因子M为unAMP-OAMCF-O{u1，. . ，un，s1，. . 得双曲余切值.| L|}<{u 1，. . ，un，M}NG（i）>AMP-CAMCF-C{u1，. . ，un，s1，. . 得双曲余切值.| L|}<{u1，. . ，un，M，l1，. . ，l| L|}NG（i）>表1. 算法2的专门化的输入集。对于后缀为-I的算法，其集合与后缀为-O的算法相同，但对应于逆图。{j∈ NG（i）：j i}和NG（i）>：=NG（i）\Jr（i）作为前因子和后通过某个因素发送消息自动意味着通过另一个耦合因素接收该消息。因此，在算法2中不需要遍历所有因素。特别地，边缘因子仅耦合到节点因子，因此在算法2中自动处理所有节点因子意味着也更新所有边缘因子。在集合Jr（i）和Js（s）的处理顺序和选择中，我们遵循最有效的MAP求解器TRWS [33]和SRMP [34]（后者是TRW-S对高阶模型的推广，并且对于成对CRF（1）具有略微不同的实现）。在所有节点包含不相交标签子集的特殊情况下，图匹配问题（2）转化为CRF（1）中的MAP推理。然后我们所有的算法GM，AMP和AMCF都简化为SRMP [34]。值得一提的是，对于CRF，存在算法，例如MPLP[24]，其仅经过边缘因子，并且以这种方式隐式地处理节点因子。如SRMP [34]中所示，MPLP通常比SRMP慢在第6节中，我们证明了我们的方法与最近提出的HBP [61]相比也是有利的，HBP [61 ]类似于AMCF-O，但使用了类似于MPLS的处理时间表。过程1的优化子问题。对于过程1的每个调用，必须在第1行中找到最佳因子元素，并通过求解（9）来计算最佳消息。第一个子问题是通过明确地扫描节点，边缘和标签因素的因素的所有元素来解决对于M上的优化，我们使用最小成本流求解器。通过封闭形式的解或调用最小费用流求解器，可以求解（9）中的所有因子和邻域选择，并在附录中进行了描述。原始舍入。算法2仅提供原问题（2）的下界。为了获得原始解，可以忽略边缘势θuv，并使用最小成本流求解器来求解由此产生的重新参数化的二分匹配问题（6），如[61]中所做的那样。根据经验，我们发现最好是交错舍入和消息传递，类似于TRWS [33]和SRMP[34]。假设我们已经计算出了所有v u的原始整数解x，我们想计算x。为此，1616v⊆3uv对于i=u，我们将算法2的第4行和第5行分配给Σx∈argminxu：xu/=xvuθu（xu）+θ uv（x u，x）。（十）v u：uv∈E时间复杂度如果X u=L <$u∈V，则每次迭代的时间复杂度为O（|L||V|+的|L|2|E|）的GM。对于AMP，我们必须添加|L|对于AMCF，求解（6）的时间（可能在O（L3）中）。详细信息和加速在附录中高阶扩展。我们的方法是直接向前扩展到图匹配问题，海厄rorderfactors，一个特殊情况是三阶：设表2. 数据集说明。#I表示实例数，#V表示节点数|V|，#L是数字|Xu|节点的标签数u∈V可以匹配到，C是图的连通度。TV是节点的三元组的子集，UVW：Xuvw→数据集。我们比较了六个数据集：R是相应的三重态电势。相应的三阶图匹配问题如下：• [12][13][14][15][16][17][18][19][1任务是在图像之间找到匹配的特征点Σminθu（xu）+x∈XVu∈VΣθuv（xuv）+uv∈EΣθuvw（xuvw）uvw∈T从不同的视角捕捉物体。• car和motor都在[40]中使用，包含要匹配关键点的成对汽车和摩托车的图像S.T. xu/=xvuv.（十一）来自VOC PASCAL 2007挑战[21]。相关的IRPS-LP可以通过以类似于（4）中的方式包括所有三元组的附加因子来构建，参见例如[56]的相应松弛。对于松弛（R1）为此，我们在开始时设置θuvw<$0。通过这种构造，（11）等价于（2），然而对应的IRPS-LP不是：放松得更紧。6. 实验算法。我们比较了第1节中描述的两个基于拉格朗日分解的求解器[52，61]。• 双分解求解器DD[52]。我们使用包含4个节点的局部子问题。请注意，[61]中的比较是用大小为3的子问题进行的，因此DD• “Hungarian belief propagation”在[61]中，一个分支和边界求解器被用在对偶的顶部，美分求解器。为了进行公平的比较，我们的重新实现只使用了双上升部分。对于AMP和AMCF，我们在HBP后面加上后缀-O和-C来表示我们让HBP运行的弛豫。根据[52，61]，这两种算法优于竞争对手[16，19，20，25，27，38，39，42，46，51，58，64]在他们的出版时，因此我们不与后者进行比较。我们为每个算法设置了1000次迭代的硬阈值，当原始/对偶间隙消失或不再观察到对偶进展时，在我们的算法中，每5次迭代计算对于GM、AMP、AMCF和HBP，我们使用第5节中讨论的收紧扩展来改进对偶下界。我们没有双重进步的时候就收紧放松。成本是根据[40]中的特征计算的。• 图流数据集[1]来自具有大位移的跟踪问题[8]。通过Kinect摄像头获得的RGB-D图像帧中的关键点- [60]第60话相濡以沫在计算电位θ时考虑Kinect相机提供的深度信息。• 生 物 成 像 的 蠕 虫 数 据 集 [4][28] 。 目 的 是 注 释C.elegans，一个著名的模式生物用于发育生物学，通过找到相应的细胞核在一个预先计算的模型。据我们所知，蠕虫的实例是文献中有史以来最大的图数据集特征总结见表2。以前的计算研究集中在小规模的问题，有多达60个节点和标签。 我们已经包含了蠕虫数据集，最多有500个节点，|= 1500个标签。|= 1500 labels.结果图2示出了算法在所有6个考虑的数据集上的性能。在所有变量-O，-I，-C分别对应于原始，逆和耦合配方，我们只绘制了最好的一个。正如预期的那样，对于密集图（数据集房屋，酒店，汽车，汽车），具有耦合的变体-C提供了最稳健的收敛，类似于-O或-I中的最佳结果，因此在图上呈现。对于稀疏图，逆表示-由于逆边集E′可能是稠密的，即使E在（3）中是稀疏的，因此sentation变得太昂贵。因此，我们坚持原来的问题-O。• hotel和house是简单的数据集，许多实例需要5次迭代才能收敛。

下载后可阅读完整内容，剩余1页未读，立即下载