融合移动技术的多标签离散马尔可夫随机场在图匹配中的应用

6270能量（×1000）图匹配Lisa Hutschenreiter*，Stefan Haller*，Lorenz Feineis*，CarstenRother*，Dagmar Kainmüller†，Bogdan Savchynskyy**海德堡大学，†Max Delbrück分子医学中心，柏林摘要我们有助于近似算法的二次分配问题，也被称为图匹配- ING。灵感的成功的融合移动技术开发的多标签离散马尔可夫随机场，我们研究其适用于图匹配。特别是，我们展示了融合移动如何有效地与最近在计算机视觉和生物成像应用中显示出优异结果的专用最先进的双重方法相结合。正如我们对各种各样的图匹配数据集的经验评估所表明的那样，融合移动在所获得的解决方案的速度和质量方面显着提高了这些方法的性能我们的方法设置了一个新的国家的最先进的一个显着的利润率相对于其竞争对手。1. 介绍二次分配问题，也称为图匹配问题，是一个最突出的组合问题，有着广泛的应用。 计算机视觉中它主要用于特征匹配[47]。这种应用的现代方法是深度图匹配，参见例如。[40，42，55]，在社会上享有不断增长的关注。从名称可以看出，深度图匹配将神经网络与组合匹配技术相结合，用于推理和联合学习。尽管大多数早期的深度图匹配方法[17，24，51，52，53]采用线性分配问题（LAP）求解器1来获得其流水线中的匹配，但最有前途的现有技术方法[40]使用全特征的图匹配求解器。上的循环调用鸣谢。这项工作得到了欧洲研究委员会（ERC欧盟地平线2020研究和创新计划，资助647769），德国研究基金会（图形模型中基于Ex-act松弛的推理，DFG SA 2640/1- 1）和亥姆霍兹健康信息数据科学学院（HIDSS 4 Health）的支持。计算是在德累斯顿工业大学信息服务和高性能计算中心（ZIH）的HPC集群上进行的。1无二次代价的图匹配的多项式子类。-50−600 100 200 300时间图1.可扩展的图匹配对于生物成像尤其重要，其中不同图像上的数百甚至数千个细胞必须彼此匹配pairs数据集的实例（参见第二6），仅示出了每个第五匹配。（底部）最先进方法dd-ls 0[47]的收敛性（参见第6）不融合和融合移动。注意，融合移动在明显更短的时间内获得在每次训练迭代中，该求解器必须在非常有限的时间预算（通常小于一秒）内提供高质量的解决方案现代最先进的方法[46，47，56]只有在应用于相对较小的问题时才能满足这一要求，最多只有几十个特征点。因此，深度图匹配的可扩展性关键取决于高效图匹配求解器的存在。在这项工作中，我们解决这个问题，通过引入一个新的图形匹配技术，显着提高了国家的最先进的速度和达到的准确性。特别是，它在不到一秒的时间内为超过500个特征的问题提供了高精度的解决方案相关的工作。图匹配问题在1957年首次提出由于其重要性，几乎所有可能的优化技术都对其进行了测试，参见调查[10，12，38]和其中的参考文献。通常对于NP难问题，没有一种方法可以有效地解决所有的图匹配实例。不同的应用需要不同的方法，我们集中dd-ls0+融合6271. Σuu∈LLu∈Vuuv∈E L × L→LL L∪{}L L L→∈V{}∈ ELE这里是关于计算机视觉的问题实例传统上，在这个社区原始启发式2[1，14，19，19]。25，35，36，50，54，57，58]主要使用，因为对低计算时间的需求通常支配对最优性保证的需求。这些方法还包括建立在光谱弛豫[35，36，50，57]或凸到凹路径跟踪程序[7，15，58]。然而，最近的工作[46，47，56]表明，基于La- grange对偶的方法获得了更好的准确性，特别是随着问题规模和复杂性的增长。重要的是要注意，在运筹学中，至少自90年代以来，这种用于图匹配的La- grange对偶方法是已知的[2，22，30]，并且广泛用于分支定界求解器。虽然它们解决了与[46，56]类似的松弛，但它们的迭代复杂度比[46，56]高一个数量级。这使得它们在典型的计算机视觉应用中的使用非常昂贵。虽然分支定界仍然是获得精确解的主要工具，但它具有指数最坏情况的复杂性，并且通常过于昂贵。因此，像[46，47]这样的对偶方法改进这样的启发式算法以获得高质量的原始解决方案，已经经过几次双重迭代将允许超越纯原始方法，不仅在准确性，而且在运行时间。融合移动，如[34]所介绍的，是针对马尔可夫随机场中的最大后验推理提出的原始启发式，也称为离散标记或能量最小化问题，参见例如。[43]。为了简洁起见，我们将其称为MRF问题。在其最常见的设置中，融合移动方法试图通过将其与另一分配建议合并来改进当前近似原始分配合并构成了相对小的两标签MRF问题，由该方法产生的溶液总体。贡献我们展示了如何使用融合移动来有效地解决图匹配问题，并提供了一个理论基础，有效的融合移动的建议必须是可行的，即。满足图匹配问题的唯一性约束。我们确保我们的proposals质量的基础上产生的双重优化过程中改进的reparametrized成本，并通过利用振荡的双重更新，如在对偶次梯度法，或我们提出的高效的随机贪婪算法，强制多样性总而言之，我们的方法结合了双解算器的准确性我们demonstrate我们的技术在多个数据集上的优越性能我们使用的代码和数据集可在https://vislearn.github.io/libmpopt/iccv2021上获得。补充部分（称为§A1-§A7）包含详细的2. 预赛图匹配问题。设G=（V，E）是一个无向图，其中V是有限节点集，V2边的集合。对于互补性，我们表示边u，v简单地通过UV。设是一个有限集标签我们将每个节点u与标签u 的子集和一元成本函数θ u：# R相关联，其中#：= u #。这里，#表示与所有标签不同的虚拟标签，以编码没有标签被选择。类似地，对于每个边uv，令θ uv：##R为成对代价函数然后，找到标签到节点的最优分配的问题，称为图匹配或二次分配问题，可以表述为minΣE（x）：=Σθu（xu）+Σθuv（xu，xv）Σ（1）为此存在有效的精确和近似技术。如[34]中所述，该方法的成功显著取决于x∈Xu∈Vuv∈E提案的质量和多样性。 一些S. t.u，v∈ V，u为管理成果框架问题生成通用建议的方法以及对应辅助的（近似）求解器其中X代表笛卡尔积×L#。的目的问题已被[29]评估他们还审议图匹配问题的几个实例被视为MRF。然而，他们发现融合移动与他们的，通常是不可行的，建议是不如其他方法。[47]使用简单但低质量的基于本地搜索的提案生成器报告了类似的负面结果。在运筹学中，融合移动自1997年以来被称为优化交叉或重组，当时它被提出来解决独立集问题[3]。然而，对于二次分配问题，据报道，当用作贪婪遗传算法的构建块时，它是低效的[4]。这是因为缺乏多样性。2缺少最优性保证的算法的通用名称。被称为唯一性约束。它们允许每个非伪标签最多被选择一次。所选虚拟标签的数量不受限制。 元素xx称为赋值。如果一个赋值满足所有的唯一性约束，那么它是可行的因此，本质上，（1）对应于具有标签的唯一性约束的MRF问题请注意，这个公式推广了经典的二次分配问题，见例[10]，通过允许不完整的赋值，即不是每个标签IN都必须被分配给节点，并且不是每个节点都必须被分配标签IN。相反，可以为节点分配虚拟标签。为每个节点中的虚拟标签选择一个大的常量作为一元成本会强制执行完整的分配。6272ΣΣ∈∈·¢#）¢）∈ E ∈L ×L如果没有成对成本θuv，二次分配问题（1）可简化为著名的线性分配问题（LAP）。当二次分配问题在坐标x u=s和x v=t的解决方案标记x。这些变量一起形成向量μ ∈ {0，1}N，其中N=2| V|+4个|E|.然后是ILP一般的NP-难问题，可以在多项式时间内求解通过例如。匈牙利方法。[34]第34话：（一）min{0，1}Nμv∈Vu，sθu（s）+uv∈Eμuv，stθuv（s，t）（5）应变，MRF问题.最简单的，但是s∈Lu（s，t）∈Lu×Lvminx∈XE（x）最广泛使用的场景，在算法的每次迭代S. t. u∈ V：μ u，x′u+μu，x′u′=1通过求解辅助最小化问题将当前最佳分配x′X与另一候选分配x′′X融合uv∈E，（s，t）∈Lμuv，st≤μ u，s，μ uv，st≤μ v，t，μ uv，st≥μ u，s+μ v，t−1，minx∈Xaux E（x），（2）u，v∈V，uv，s∈（L其中X：={x∈X|X∈{x′，x′′}，u ∈ V}. 由于μu，s+μv，s≤1auxuu u等于（4）。特别地，（6）中的不等式限制标签空间X的相当小的尺寸辅助问题（2）通常可以被有效地近似地或甚至精确地求解。求解器只需确保最佳分配的单调改进E（x*）≤min（E（x′），E（x′′））（3）对于其输出x*，然后进一步认为是最佳分配，即在下一次迭代中x′：=x*。注意，单调性条件（3）对任何x*都自动成立，它是（2）的精确解 对于近似方法，不等式（3）可以通过将x*分配给具有较低能量的建议来强制执行。 每个融合操作也被称为融合移动。我们通过扩展辅助问题（2）将该方法应用于图匹配问题（1最小E（x）（4）强制唯一性约束。显然，没有唯一性约束（6）的问题（5）构成MRF辅助问题（2）的ILP表示。ILP问题（5）-（6）可以通过现成的ILP求解器如Gurobi [21]来解决。然而，随着问题规模的增长，这样的求解器变得非常慢，因为它们具有指数最坏情况的复杂性。因此，人们不得不求助于其他精确或近似的优化技术，我们现在审查。消除唯一性约束。节点u和v之间的唯一性约束（6）可以通过将非常大的成本C∞分配给相应边上的成对成本函数来消除，即θuv（s，s）：=C∞，s∈（Lu∩Lv）\{#}.（7）若uv∈/E，则边uv与E成对相加x∈XauxS. t.u，v∈V，ucostsθuv（s，t）：=C∞s=t如果A成立，则为1，否则为0。，其中A等于即，与（2）相比，在融合期间考虑唯一性约束，这保证了当前最佳分配的可行性。有两个主要的问题，必须回答应用融合移动：㈠如何提出建议？（ii）如何解决辅助问题（4）？从第二个开始，我们在下面解决这些问题。3. 解决辅助问题ILP制剂。辅助问题（4）可以被公式化为整数线性规划（ILP），如下所示。为所有u∈V令Lu：={x′u，x′u′}是限制标签集3我们为每个节点u∈V引入二元变量μ u，s∈ {0，1}，并为每个边uv引入标签s∈L（u ）和μu v ，st∈{0，1}并且每个标签对（s，t）uv. 设置μ u，s=μ v，t=μ uv，st=1对应于分配3不失一般性，我们假设非平凡情况x′u=x′u′对于所有的u∈ V。6273这样，图匹配辅助问题（4）在可能不同的图上被简化为MRF辅助问题（2）。这允许考虑解决MRF辅助问题的专用方法（2）。这些方法的效率非常依赖于成对成本θuv的子模块性。我们在下面回顾这个属性和相应的优化方法。次模块化病例。一般来说，像（2）这样的双标签MRF问题是NP难的[8]。然而，如果对所有的u∈ V存在一个双射映射，则它们成为有效可解的δu：{0，1}→Lu称为或deringg，使得所有成对的问题（2）中的费用θuv，uv∈ E是次模的，即θuv（0，0）+θuv（1，1）≤θuv（0，1）+θuv（1，0），（8）其中我们将θuv（δu（0），δv（1））缩写为θuv（0，1）。已知在这种情况下，（5）的自然线性规划（LP）松弛是紧的，并且此外，可简化为有效可解的最小割/最大流问题[31]。44排序δu也可以显式地找到[44]，允许更有效的最小切割/最大流减少[32]。6274∈Vn|V|.Σ非次模块化病例。对于给定的映射δu，不满足子模性条件（8）的成对代价称为超模。不等式（8）意味着交换然而，由于一个节点中的交换改变了所有事件成对成本的子/超模块性，因此我们不能总是将所有超模块成对成本转变为子模块成对成本。这已经是不可能的，如果图包含一个三角形子图，所有成对成本是超模。在这些情况下，所提到的LP松弛通常不是紧密的。然而，它具有重要的持久性，I.E.松弛解的所有整数坐标属于最优整数解[31]。这允许为（2）建立有效的近似方法，也适用于非子模的情况[41]。这些方法在文献中被称为二次伪布尔优化（QPBO）或屋顶对偶。作为替代方案，[20]已经提出了用于（2）的基于信任他们是基于子模块化问题的迭代逼近的问题。为此，我们用一元代价来近似超模成对代价.与QPBO技术类似，信赖域方法的性能随着超模成对成本的数量增加而下降与QPBO技术相反，它们需要标签集的显式排序。4. 提案的可行性在我们解决方案的生成之前，我们理论上证实了用于图匹配问题的融合移动方案的主要性质：可行性换句话说，建议应该满足唯一性约束，以允许该方法良好地执行。搜索空间的大小。简单地说，融合移动是一种局部搜索方法，搜索空间由建议定义。这种方法的性能关键取决于搜索空间的大小。 假设一个更好的， 或者甚至可以有效地找到该空间内的最佳解，则该搜索空间应当尽可能大以允许更好的近似。下面的命题设定了搜索空间大小的界限：1.提案对于图匹配问题（1），设x′是可行的，x′′是可能不可行的.设m是伪标签的数量，n是x′′中不同非伪标签的数量。 则辅助问题（4）具有至多2m|V|+1n个可行解。换句话说，对于固定数量的伪标签，搜索空间的大小随着x”中不同标签的数量呈指数增长。可行的赋值使这个数最大化，见§A1关于Prop的证明1.一、可行分配的需要将图匹配与MRF问题区分开来，其中可能分配的空间可行的解决方案总是以2n的形式增长，其中n是方案不同的节点的总数因此，一种流行且非常有效的生成MRF建议的方法称为α-扩展[9]，其中x′u′=α对于所有u，对于图匹配完全无效：根据命题1，搜索空间减少到+1个解。另一种流行的方法[29，34]建议从本地最佳标签中构建建议，例如，循环信念传播如由[29]经验地观察到的，对于图匹配问题，这样的提议通常不满足唯一性约束，并且因此导致融合移动的非竞争性性能。近似求解器的效率。如第3节所述，辅助问题（2）的近似求解器的性能随着超模成对成本比例的增加而下降由于辅助问题（4）的唯一性约束被转化为大的成对成本，所以找到其中这些大成本不会导致违反子模块性约束（8）的排序是重要的。设建议x′′不可行，即 存在u，v ∈ V，u=v，其中x′u′=x′′#. 现在考虑排序，其中标签x′u′映射到0，对于所 有 u ∈ V ， 并 且 所 有 x′u 映 射 到 1 。 然 后 ， 根 据（7），θ uv（0，0）= C∞，这将导致超模成对成本θuv 。如 果 有 多 个 节 点 具 有 相 同 的 标 签 ， 即x′u′=x′v′=x′w′，这将导致具有超模的全连通子图成本 如第3节所述，这些成本不能全部通过交换标签0和1，将其转换为子模。结果，这导致图匹配辅助问题（4）的近似方法这种情况可以通过要求x′′是可行的来避免相反，考虑实际上不可避免的情况下，相同的标签在不同的建议，即x′u=x′v′，对某个u，v∈ V，u=v. 根据（7），具有相同的初始排序如上，θuv（1，0）：=C∞。然而，这使得对应的成对代价子模，c.f.（8）其中简化了优化。总而言之，建议的可行性增加了每个融合的搜索空间，同时允许辅助问题的有效近似求解器5. 提案生成如第1节所述，如果提议的质量高且多样化，融合移动效果最好。本质上，高质量意味着低对应能量E，并且可以通过对两个提议不同的节点的数量进行计数来量化分集如何获得高质量的提案？获得高质量建议的自然想法是采用一些迭代优化过程，该过程在每次迭代时输出解决方案如第4节所讨论的，在图匹配的情况下，这些建议应该是可行的。配备双方法6275uvs∈L#∈ V ∈L∈联系我们s∈Lu\L′∪{#}v∈N（u）∩V′问题（1）可以写成：uuvs∈L#u（s，t）∈L#×L#uvΣuu2u2--算法一：随机贪婪启发式。输入：图G=（V，E），标签L和成本θ初始化V′：=和L′：=当V′ =Vdo5.2.对偶求解器双重问题。 图匹配问题（1）可以用与辅助问题（2）类似的ILP形式表示。我们定义二进制变量μu，s和μuv，st模拟-随机选择u∈N（V′）或u∈V\V′，如果N（V′）=gously。这样的变量的数量是M：= Σuv∈Euvu∈V |+|+u设置ΣΣ| L编号||L编号|. 通过表示包含xu：= arg minθu（s）+Σθuv（s，xv）特定非伪标签s作为V（s）：={u ∈ V |s ∈ Lu}，更新V′：=V′∪{u}和L′：=L′∪{xu}输出：可行分配x=（x）μminMΣμu，sθu（s）+Σμu v，s tθu v（s，t）（9）u u∈V{0，1}u∈V#s∈Luv∈#E数量（s，t）∈L ×L由于可有效计算的原始试探法因此是提议生成器的自然候选在5.2节中，我们简要介绍了两种类型的这种方法，块坐标S. t. uv∈ E，t∈L#：Σμuv，st=μv，t（10）u∈ V：Σs∈L#μu，s=1（11）u以上升和下降为基础的。如何获得不同的建议？ 提案的多样性s∈L：Σu∈V（s）μu，s≤1（12）基于双重优化的方法可以由噪声引起双重更新，或者必须是原始启发式的固有属性。我们使用这两种策略。次梯度法是第一类的代表。由于非最佳步长和更新方向，它通常展示了通过引入ξλ（s）：=θu（s）+λu，s和ξ（λ（s）：=θu（s）λu，s对于u，s#和任意λu，sR，我们可以等价地将（9）中的目标重写为分别表示为EMRF和ELAP的MRF和LAP子问题的目标之和Σμu，sξλ（s）+Σμu v，stθu v（s，t）+Σμu，sξλ（s）。通过原始启发式获得。u∈V#s∈Luuuv∈#E数量（s，t）∈L×Luvuu∈V#s∈Lu相比之下，块坐标上升方法基于并保证单调改进的双重价值。因此，相应的=：EMRF（μ，λ）X`=：ELAP（μ，λ）x由确定性原始试探法计算的分配通常缺乏多样性。为了解决这个问题，我们建议使用5.1节中描述的随机贪婪启发式作为通用方法令Λ是所有二进制向量μ〇的集合，满足约束（10）-（11），并且B是那些约束的集合满足-实施例（11）-（12）。然后求和minEMRF（μ，λ）+minELAP（μ，λ）（13）提出不同的建议。 它结合了多样性，由于μ∈Λ∈B由于采用局部最优标签，因此具有高质量的节点选择顺序的随机化该方法的另一个重要优点是，它可以从对偶优化中获益，并且随着对偶优化的进展，提供定性更好的建议。特别地，如果全局最优分配是唯一的并且MRF和LAP子问题的独立最小化构成了（9）-（12）的下限。而第二项可以被有效地最小化，例如根据匈牙利方法 ， 第 一 项 本 身 是 NP 难 问 题 。 通 过 对 偶 化 约 束（10），得到其拉格朗日对偶下界，c.f. [43，第6章]，双重约束是紧的。我们描述了它的使用与一个双BCA求解器。D（，λ）：=Σminξ，λ（s）+Σminθ（s，t），`6276，λ∈BUV5.1.随机贪婪启发式哪里u∈Vuuv∈Eu v设N（u）：={v ∈ V |uv ∈ E}是的邻域ξ，λ（s）：=ξλ（s）−Σu，v（s），（14）u，且N（V′）：=. Su∈V′N（u）Σ\V′的邻域V V Nu uv∈N（u）’。注：（）=。随机贪婪启发式由算法1定义。在每个步骤中，从已分配节点的邻域中随机选择未分配节点，并且向其分配标签，使得满足唯一性约束，并且计算其一元成本和连接其与已分配节点的边上的所有成对成本的总和。θ（s，t）：=θuv（s，t）+u，v（s）+v，u（t），通常被称为重新参数化成本。总而言之，（9）-（12）的对偶问题在于下限最大化maxΣD（，λ）+minELA P（µ，λ）Σ。（十五）最小化6277uG∈ E∈L∈VUV|V|不超过|V|不超过|V|不超过|V|u∈ V|V|vuv∈EuvΣ#∈ L×L双块坐标上升，§A2。基于[45，56]的思想以及MRF[48，49]的对偶求解器开发的最新进展，我们实现了块坐标上升（BCA）求解器，该求解器还允许输出分配建议。我们的求解器通过交错最大化w.r.t.和λ。在上的每一步都包括最大化边界w.r.t.变量块（u，v（s），v，u（t）），（s，t）##与一个边缘uv相关联。寻址所有边缘的这些步骤的序列等效于[48]的MPLP++算法的一次迭代，其显著优于[56]使用的MPLP算法[18]。λ上的每一步都包括最大化对偶目标w.r.t. blocks（λ u，s），u[15]每一个人，都有自己的故事。对于原始估计，我们要么使用（15）中的LAP 项minμ∈BELA P（μμ，λ）的精确解作为λ的当前值，要么在具有一元和成对成本ξ，λ和θ的图匹配问题上运行我们的随机贪婪算法1，用于当前值。对于LAP启发式算法，我们使用Gurobi [21]作为求解器。在使用例如匈牙利的方法解决LAP将是更快的，我们发现，贪婪的启发式与融合移动相结合，始终优于它的LAP对应在我们所有的实验在运行时间和质量方面。次梯度法我们使用[47]的代码作为对偶次梯度方法的代表。在其表示为dd-ls 0的基本版本中，其代表没有局部子问题的对偶分解，其优化了与（15）相同的界限，不同之处在于，代替对偶MRF项D（λ，λ），其使用了对应于MRF项D（λ，λ）的等价树分解。问题minμ∈ΛEMRF（μ，λ），参见例如[43，Ch.9]详细信息。作为原始界限，它使用LAP问题minμ∈BELAP（μμ，λ）对于λ的当前值。我们在实验中使用的两个其他版本的求解器表示为DD-LS 3和DD-LS 4的部分另外考虑分别由原始图的3个或4个相邻节点组成的子图上的局部子问题这些修改每次迭代需要更多的时间，但优化比（15）更严格的边界。此外，这些变体估计原始解决方案的基础上的解决方案的局部子问题。我们参考[47]以了解更多细节。双BCA算法复杂性每迭代O（|L编号||L编号|），例如在Prob的大小中线性L L∪ {}AMD EPYC 7702 2.0 GHz处理器和512 GB主内存。为了公平的比较，我们使用了所有讨论的算法，rithms的有效实现，并报告5个独立的预定试验的最小运行时间。数据集，§A3。我们的实验评估是在8个数据集上进行的，其中总共316个问题实例来自下面详细描述的计算机视觉和生物成像。为了证明我们的方法的可扩展性，以及 计算机视觉酒店，房屋 ，汽车， 汽车和opengm的标准小规模数据集52，我们考虑中等规模的流量，126，以及大规模的蠕虫和配对数据集565。据我们所知，后者是计算机视觉。宽基线匹配（酒店、房屋）基于来自不同视角的同一对象的一系列图像。基于[11]的工作，我们使用与[47关键点匹配（汽车，摩托车）包含PASCAL VOC2007 Chal- lenge [16]中的汽车和摩托车实例，具有[37]中的功能和成本我们preprocessed的模型，通过删除零成本的边缘，从而大大降低了图形密度。文献[5]引入了大位移流（flow），用于大位移流场景的关键点匹配我们使用[46]中的关键点和成本。OpenGM匹配（opengm）是[33]的一组非刚性点匹配问题，现在是OpenGMBench-mark [28]的一部分蠕虫图谱匹配（worm atlas matching，worms）的目标是对C. elegans，一种用于发育生物学的著名模式生物，通过从生物体的预计算图谱中分配细胞核名称。我们使用[26，27]中的模型与蠕虫数据集相反，蠕虫对蠕虫匹配（对），参见图1的说明，直接匹配个体C的细胞核。优雅的蠕虫彼此。这减轻了基于手动注释预先计算图谱的需要。通过对图谱在所有核上捕获的核（对）特异性协方差矩阵求平均来导出相应图匹配问题这将模型粗化到无需手动注释即可实现的级别。对于我们的实验我们从30·29= 870中随机选择了16个实例莱姆 对于u=#的全连通图，u ，则为O（4）.这比运筹学中已知的双上升算法[2，22，30]的迭代复杂度O（5）6. 实验和分析实验装置。我们通过测量它们的总运行时间和获得的解决方案的质量来评估所有测试算法的性能。我们的实验是在基于与蠕虫相同的数据的非平凡蠕虫对。算法。 作为提案生成器，我们评估这三个基于对偶次梯度的算法dd-ls 0、dd-ls 3、dd-ls 4和我们的BCA求解器bca在第5.2节中描述。后者与基于LAP解决方案或贪婪算法1的原始启发式一起使用，分别表示为bca-lap和bca-greedy我们还使用贪婪算法1作为独立的基线。作为建议融合方法，我们将Gurobi[21]评估为6278能量（×1000）能量（×1000）|V||E|-20-40−60车5流20−1个−2−3−4-50-55−60对5生成（下限和上限）dd-ls0bca-lapbca-贪婪+ILP融合电话：+86-050 -88888888传真：+86-050 -迭代0 200 400 600迭代0 200 400 600迭代(a)(b)（c）第（1）款图2. （a-b）融合的影响。图中显示了dd-ls 0（蓝色）、bca-lap（橙色）和greedy（绿色）算法生成的分配能量以及适用的对偶边界匹配颜色中的粗线示出了当使用ILP解算器在顶部进行融合时对于每个算法实现的能量值得注意的是，融合以少得多的迭代实现了非常好的质量对于一些数据集，即使是贪婪地生成的建议也足以在融合时获得（几乎）最佳解决方案。（c）LAP与贪婪启发式。该图示出了由bca-lap（橙色）和bca-greedy（红色）针对示例性配对实例生成的提议的质量。这些发生器顶部的熔融溶液以相同颜色显示为粗线。应用于bca-greedy的融合移动比应用于bca-lap时产生显著更好的结果，即使bca-greedy的提议明显比bca-lap的提议差。表示为ilp的辅助问题（5）的精确ILP求解器，表示为lsatr的[20]的基于信赖域的方法，以及表示为qpbo的不同QPBOXX.对于这些变体的描述，请参见[41]和相应的源代码。此外，在第6.2节中，我们将我们的方法与许多最先进的算法进行了比较。6.1. 不同组分熔融对溶液质量的影响， 图2（a-b），§A4、A6. 在我们的第一个实验中，我们用了三种方法生成建议：bca-lap、dd-ls0和greedy。算法bca-lap和dd-ls 0表示具有基于LAP的原始启发式的标准对偶技术，并且贪婪构成基线。我们用ilp方法融合生成的建议图图2（a-b）示出了针对来自所考虑的数据集的两个示例性实例的融合之前和之后的这三个建议生成器的结果虽然dd-ls 0方案的能量远远不是最优的，但它们的融合立即带来了更好的结果。虽然bca-lap方案的能量通常比dd-ls 0方案的能量低得多，但融合方案的能量不一定更低。我们的解释是，bca-lap提案缺乏多样性这种解释证实了融合贪婪的建议的性能。尽管贪婪的建议质量非常依赖于数据集，但与融合相结合，它通常会产生良好的结果。虽然它们仍然比图2中的双重方法获得的那些差。2（a），他们可以是非常有竞争力的，如图所示第2段（b）分段。该实验清楚地表明，通过融合生成的建议可以大大提高整体解决方案的质量。由于融合以相对较少的提议提供了已经非常好的结果，因此与无融合方法相比，它承诺显著的加速，因为这可以显著减少必要的迭代次数以实现特定的性能。溶液质量精确融合与近似融合，§A4、A6。为了估计通过融合获得的运行时加速，我们将精确ilp求解器与近似qpbo-i、qpbo-p、qpbo-pi和lsatr求解器进行了比较。其中，我们发现qpbo-i在一致的质量和速度方面表现最好尽管最坏情况的计算复杂度为O（），但qpbo-1比双重更新快10LAP与BCA的贪婪启发式，图。第2段（c）分段。如上所述，融合移动仅略微改善bca-lap的性能，因为由该方法生成的提议的低多样性。如果我们将其与bca-greedy进行比较，这很容易看出，其中LAP启发式算法被贪婪算法1取代。实际上，对于所有数据集，我们观察到bca-greedy提议的融合产生至少与bca-lap提议的融合一样好的结果，即使当bca-greedy提议本身具有比bca-lap的能量更高的能量时。松弛收紧的影响，§A4、A6。一般来说，从长远来看，更紧密的松弛提供更好的界限。然而，这需要为每次迭代付出更高的运行时间。有趣的是，由于融合，所有三种次梯度方法dd-ls 0、dd-ls 3和dd-ls4在大多数数据集中接近甚至达到因此，由于较低的迭代时间，对应于最弱松弛的方法dd-lso首先收敛，并且因此是优选的。由于融合显着提高了所发现的解决方案的能量，我们声称，没有融合，将不得不使用更严格的松弛，以达到相同的结果质量。摘要 表1总结了我们的性能研究。我们包括dd-ls 0和bca-greedy作为他们的算法类的最佳代表。我们观察到基于qpbo-i的融合以实现具有与底层提议生成器相同或更低能量的解决方案，同时还平均比没有融合的提议生成器更快地换句话说，使用融合招式的。能源6279†表1. 融合动作性能总结。每个数据集的最佳建议的平均能量（最佳生成）。），以及生成它所需的平均时间（tgen）。此外，其示出了qpbo-i融合算法在融合时平均花费多长时间来击败dd-ls 0或bca贪婪提议（tbeat）、由融合生成的最佳提议的平均能量（best fused）、以及获得该最佳提议之后的平均时间（tfuse）。所有时间都以秒为单位。能量前面的小数字表示通过相应方法求解到最优性的实例的数量。具有融合的方法获得更好的能量值并且平均更快。数据集dd-ls 0+qpbo-i bca-贪婪+qpbo-i表2. 对比表。 我们表示所提出的BCA贪婪+QPB 0 - 1方法。对于每种方法，我们声明opt/t，表示最优解决实例的数量以及达到最优解决方案的平均时间（以秒为单位）（如果没有实例被解决为最优，则为“E或acc列中的符号意味着至少对于一个问题实例，相应的对于由指示的数据集，没有已知的真实情况，因此没有报告准确性。最佳准确度没有用粗体突出显示，因为算法无法访问地面实况，因此不会显式地最大化准确度。蠕虫达到86%的相对较低的准确性解释模型误指定。原始工作[27]报告了dd-ls 4在没有时间限制的情况下实现的83%的准确率。由于我们的方法是随机的，我们在适当的情况下报告范围。数据集（实例数）时间预算[47]HBP[56]AMP[46]AMP-tight[46]我们的opt/tEacc opt/tEacc opt/tEacc opt/tEacc opt/tEacc opt/t E acc opt / tEacc酒店（105）1 s 105/0.01-4293 100 105/0.04-4293100 102/0.11--98/0.11-428099 104/0.13 -4292 100 100-住宅（105） 1 s 105/0.03-3778 100 105/0.13-3778100 104/0.20-- 102/0.30-3773 100 105/0.19-3778 100105/0.01-3778100汽车（30）1 s28/0.13-69九十二14/0.55 -57七十四23/0.12 -- -一种24/0.11-69九十二26/0.12-699127- 28 / 0.01 -6991 ±1马达（20）1秒20/0.07 -63九十七13/0.25 -57八十七19/0.14 -- -一种18/0.04-63九十六个17/0.08-639719- 20 /0.01 -63 98 ±1Opengm†（4）1 s1/0.81-1510/--1180/--0/--570/--1504/0.004-17110 s3/1.08电话：+86-10-88888888传真：+86-10 - 88888888-150 4/0.004-171流量†（6）1 s2/0.79-20891/0.90-19620/--1/0.13-26283/0.16-4-5 / 0.06 -2837±110 s3/1.66-28195/2.81-28210/--1/0.13电话：+86-21 - 88888888传真：+86-21 -88888888蠕虫（30）1 s0/-60597260/-64158230/---0/---0/---10-22 / 0.23 -48461 ±38610 s0/-50578240/-49610240/---1/6.45-48389860/---16-25 / 0.39 -48464 ±186双†（16）10 s0/- 电话：021 - 8888888传真：021 - 88888888 -65259±13330 s0/- 电话：+86-0516 - 8888888传真：+86-0516 - 8888888 -65594±120虽然bca-greedy+ qpbo-1优于dd-ls 0 + qpbo-1，但后者非常有竞争力，并且明显优于其基本变体dd-ls0。6.2. 比较和结论表2将我们的bca-greedy+qpbo-i方法与几种最先进的技术进行了比较，另请参见§A5。我们省略了与[11，13，19，35，36，58]的详细比较，因为它们达到的精度明显低于后面的论文中所示的对偶方法[47，56]。这一结论也得到了我们自己实验的支持。不幸的是，最近的作品[25，54因此，我们将我们的比较限制在基于对偶的技术上，因为它们已被证明在计算机视觉数据集上表现最好。请注意，AMP方法[46]最近提升了最先进的在深度图匹配方法中[40]。我们区分了简单的问题实例（酒店，房子，汽车，汽车），中等难度的问题（opengm，流量，蠕虫）和困难的问题（对）。对于简单的数据集，我们在1秒内提供结果，对于中等难度的数据集，我们分别在1秒和10秒内提供结果，对于困难的数据集，我们分别在10秒和30秒内提供结果，其他运行时设置和内存消耗的比较请参见§A5结论. 如表2所示，我们的方法在速度和准确性方面明显优于其竞争对手。由于它实际上在显著小于一秒的时间内解决了所有容易和中等困难的问题实例，因此它可以有效地用于深度图匹配流水线中。简单的数据集酒店，房子，汽车，汽车在很大程度上是由所有最先进的方法解决的，不能再用来显示求解器的进展。（实例数）最佳遗传tgen.打不过最佳熔融测试保险丝最佳遗传tgen.打不过最佳熔融测试保险丝宾馆（105）105 -4293.000.070.04105 -4293.000.04103—4291.210.810.03105 -4293.000.03住宅（105）105 -3778.130.020.02105 -3778.130.02105 -3778.130.940.09105 -3778.130.09汽车（30）29-69.340.170.1729-69.370.1727-69.191.280.1229-69.370.17马达（20）20-62.950.060.0320-62.950.0319-62.930.800.0220-62.950.02流量（6）3—2818.832.791.125—2835.841.914—2837.829.650.655 -2840.000.66Opengm（4）331.420.940.77326.180.87421.221.290.04421.220.046280引用[1] Kamil Adamczewski和Yumin Suh Kyoung Mu Lee。图匹配的具体禁忌搜索算法。IEEE International Conferenceon Computer Vision，2015。二个[2] 沃伦山口Adams和Terri A.约翰逊改进的线性二次分配问题的基于编程的下界。离散数学与理论计算机科学，1994. 二、六[3] 查鲁角作者：James B.Orlin和Ray P.泰