交替方向图匹配的模块化和可扩展方法及其在视觉任务中的优势

1交替方向图匹配D. Khu eLe-Huu Nik osParagiosCentraleSupe lec，Uni versit eP-Saclay，法国{khue.le，nikos.paragios}@ centralesupelec.fr摘要在本文中，我们介绍了一种图匹配方法，可以考虑任意阶的约束，任意的潜在功能。与以往的分解方法，依赖于图结构，我们介绍了一个分解的匹配约束。图匹配，然后重新制定为一个非凸的不可分离的优化问题，可以分为更小的和更昂贵的解决子问题，通过交替方向的方法的乘数。所提出的框架是模块化的，可扩展的，并且可以实例化为不同的变体。两个实例进行了研究，探索成对和高阶约束。实验结果表明，广泛采用的基准测试，包括合成和真实的例子，所提出的解决方案优于现有的成对图匹配方法，并与最先进的高阶设置的竞争力。1. 介绍寻找两组视觉特征之间的对应关系在计算机视觉和模式识别中有着广泛的应用。这个问题可以使用图匹配[28]有效地解决，并且作为结果，这些方法已经成功地应用于各种视觉任务，例如立体匹配[14]，对象识别和分类[1，12]，形状匹配[1]，表面配准[31]等。通过图匹配解决特征对应的一般思想是将每个特征集关联到一个属性图，其中节点属性描述局部特征，而边（或超边）属性描述结构关系。匹配任务寻求最小化由一元、成对和潜在高阶项组成的能量（目标）函数。这些项称为能量函数的势。在成对设置中，图匹配可以被视为一般形式的二次分配问题（QAP），称为Lawler的QAP [19]。由于已知QAP是NP完全的[5，27]，因此图匹配也是NP完全的[13]，并且只能在多项式时间内找到近似解。在过去的几十年中，图匹配一直是计算机视觉领域的一个活跃的研究课题。在最近的文献中，[13]提出了一种分级分配算法来迭代求解匹配问题的一系列凸近似在[22]中，引入了基于亲和矩阵（由势组成）的秩-1近似的光谱匹配，随后在[9]中通过将仿射约束引入到更紧密的松弛来改进。在[23]中，提出了一种整数投影不动点算法，该算法使用匈牙利方法[18]求解一阶Taylor逼近序列，而在[28]中，考虑了匹配问题的对偶，通过对偶分解获得能量下界。在[6]中，使用随机游走变体来解决图匹配，而[32]将亲和矩阵分解为更小的矩阵，允许可以以路径跟踪方式解决的凹凸松弛他们的灵感来自路径跟踪方法[29]，该方法利用了一 种 更 受 限 制 的 图 匹 配 公 式 ， 称 为 Koopmans-Beckmann的QAP [17]。最近，[7]在图匹配框架中提出了一种最大池化策略，该策略对离群值非常鲁棒。最近，研究人员提出了高阶图匹配模型，以更好地结合结构相似性并获得更准确的结果[11，30]。为了求解这种高阶模型，[30]将匹配问题视为使用迭代连续投影算法求解的概率模型处理高阶势的成对方法的扩展也被考虑，例如在[11]中通过张量匹配（从[22]扩展），或在[31]中通过三阶对偶分解（源于[28]），或在[21]中通过高阶重新加权随机游走匹配（[6]的扩展）。最近，[26]开发了一种用于解决三阶图匹配的块坐标上升算法。他们将三阶问题提升为四阶问题，在凸化步骤之后，通过一系列线性或二次分配问题来解决尽管性能令人印象深刻，但这种方法有两个局限性：（a）它不能应用于除第三和第四阶之外的任意阶的图匹配，以及（b）它不能处理图匹配，62536254D=a我IJijkijkijk在两边都允许遮挡的情况下，也不允许有许多-按照惯例，FNb如果a > b，则xd= F。对多匹配本文提出了一类新的算法，用于解决具有任意阶和任意势的约束的图匹配问题。这些算法依赖于一个分解框架，使用交替方向的乘法器的方法。本文的其余部分组织如下。第2节提供了我们的方法的数学基础，而在第3节中，一般的分解策略，在这项工作中，我们感兴趣的张量具有相同的尺寸在每个模式，即 n1= n2=. . . = nD= n. 因此，所有的张量都应该具有这个性质。2.2.图与超图匹配两个图G1=（V1，E1）和G2=（V2，E2）之间的匹配构型可以用一个分配矩阵X∈{0，1}n1×n2 表示，其中n1=|V1|，n2=|V2|.X的一个元素x（i，i）等于1，如果节点i1∈V1是1 2egy与该框架的两个实例一起提出工作到一个成对和高阶的方法。第4节介绍了深入的实验验证和与竞争方法的比较。最后一部分是对全文的总结和展望.2. 数学背景和符号让我们首先提供我们的方法的基本符号以及基本的数学基础在第一小节中，我们将简要回顾张量，这将有助于我们完整地制定图匹配问题，这将在随后的小节中显示。2.1. 张量实值D阶张量F是一个属于Rn1 ×n2 ×··×nD（其中n1，n2，. . . ，nD是正整数）。我们将F的元素表示为：匹配到节点i2∈V2，否则等于0。标准的图匹配施加了一对（最多）一的约束，即。X的任意行或任意列的和必须≤1。如果X的元素是二进制的，那么X服从硬匹配约束。当X被放松为在[0，1]中取实值时，X服从软匹配约束。在本文中，我们使用以下符号：vec（V）表示矩阵V的列向量化副本; mat（v）是n维向量v的n1× n2整形矩阵，其中n=n1n2; X∈Rn1×n2是分配矩阵，x = vec（X）∈ Rn是分配向量; M（分别为M）是服从硬（分别地，软）匹配约束。能量函数。 设xi= x（i1，i2）是X的一个元素，表示两个节点i1和i2的匹配。 假设匹配这些节点需要一个势F1∈ R. 似-fi1i2. ID其中1 ≤id≤nd 对于d = 1，2，. . . 、D.每个larly，设F2 表示匹配两条边的可能性张量的维数称为模。（i1，j1），（i2，j2）和F3用于匹配两个（三阶）我们称与张量F相关联的多线性形式为函数F：Rn1×Rn2×···×RnD→R，定义如下：超边（i1，j1，k1），（i2，j2，k2）等等。图匹配可以表示为最小化F（x，. . .得双曲余切值.Σn1）=的···乌斯怀恩D Fx1x2···xDΣF1xi+ Σ ΣF2xixj+F3xixjxk+···（5）1个Di1=1iD=1i1i2. ID我1我2ID（一）伊伊季伊伊季ijkijk其中xd=（xd，xd，. . . ，xd）∈ Rnd，其中d = 1，2，. . . 、D.上面的函数可以重写得更复杂，使用1 2nd张量可以乘以特定模式下的向量张量 事实上，让我们考虑例如第三阶设v =（v1，v2，. . . ，vnd）bean nd维向量的潜力 自F3有三个指数，（F3）1≤i，j，k≤nF和v的模d乘积，用F <$dv表示，是a（D−1）t维n1× ···×nd−1×nd+1×的h阶张量G可以看作是Rn×n×n中的三阶张量和它的多线性形式（c.f.（1）是函数···×nD定义为Gd=Fv.（二）Σn Σn ΣnF3（x， y， z）=3ijk（6）第一次见面。i1... id−1 id+1.IDid=1i1...我... iDiDi=1j=1k=1有了这个定义，很容易看出多线性形式（1）可以重写为F（x 1，x 2，. . . ，xD）= F 1x 12x 2···DxD。（三）F6255D=a定义为x，y，z∈Rn。显然，（5）中的三阶项可以重写为F3（x，x，x）。更一般地，D阶势可以由D阶十阶势表示FD和它们在目标函数中的对应项为了方便起见，让我们考虑符号Nb注意从模式A到模式B的产品序列：Ob去-可以重写为FD（x，x，. . .，x），导致图匹配的以下重新表述。问题1（D阶图匹配）最小化FD=axd=Faxaa+1xa+1···bxb。（四）F1（x）+F2（x，x）+···+FD（x，x，. . . ，x）（7）6256¨¨¨¨在x ∈ M∈ M的条件下，其中Fd（d = 1，. . . ，D）是表示d阶势的张量Fd的多线性形式.在下一节中，我们提出了一种方法来解决这个问题的连续松弛，即。最小化（7）服从x∈M（软匹配）而不是x∈M（硬匹配）。返回的连续解使用通常的匈牙利方法离散化[18]。3. 交替方向图匹配3.1. ADMM概述我 们 简 要 描 述 了 （ 多 块 ） 交 替 方 向 乘 法 器（ADMM），用于解决以下优化问题：最小化φ（x1，x 2，. . . ，xp）3.2. 图匹配分解框架分解是一种解决问题的一般方法，通过将其分解为可以有效地单独解决的较小问题，然后将结果重新组合为原始未分解问题的全局一致解决方案[2，4，10]。显然，上述ADMM是这样一种方法，因为它将大问题（8）分解为较小的问题（10）。在计算机视觉中，诸如对偶分解（DD）和ADMM等分解方法已被应用于优化离散马尔可夫随机场（MRF）[15，16，20，25]和解决图匹配[28]。其主要思想是将原复杂图分解成简单的子图，然后使用不同的机制将解重新组装到这些子图上而在MRF推理中，这一概念已被证明是灵活和强大的，这与图匹配中的情况相去甚远设A1x1 +A2 x2 +· ··+Apxp=b，xi∈Xi<$Rni<$1≤i≤p，（八）这是由于匹配约束的严格性的确，为了处理这些约束，[28]例如，采用了一种策略，即创建子问题，这些子问题也是较小的图其中X是 是闭凸集，Ai∈Rm×ni∈i，b ∈ Rm.匹配问题，这在计算上是高度挑战性的。此外，次梯度法已被用于上述问题的增广拉格朗日量是Lρ（x 1，x 2，. . . ，x p，y）= φ（x 1，x2，. . . ，x p）强加共识，已知其收敛速度较慢[2]。可以得出结论，DD是一种非常缓慢的方法，并且通常适用于有限的能量模型集+y.Σpi=1AixiΣ-b+¨普普¨2¨i=1Aixi¨¨— 贝¨2、（9）与小尺寸和低到中等几何连通性相关[28]。在我们的框架中，我们不依赖于图的结构，而是依赖于变量的性质实际上其中y称为拉格朗日乘子向量，ρ>0 称为惩罚参数。设x[a，b]表示（xa，xa+1，... . . ，xb）（按照惯例，如果a >b则忽略x [a，b]）。标准ADMM通过迭代来解决问题（8）1. 对于i = 1，2，. . . ，p，更新xi：xk+1=argminLρ（xk+1，x，xk，yk）.（十）我们的想法是将分配向量x（通过拉格朗日松弛）分解为不同的变量，其中每个变量都服从较弱的约束（更容易处理）。例如，与处理赋值向量x∈M，我们可以用两个向量 x1和 x2来表示，其中mat（x1）的每一行的和≤ 1，mat（x2）的每一列的和≤ 1，并且我们约束这两个向量相等。更一般地说，我们可以分解x转换成任意多的向量，无论如何，我2. 更新y：x∈Xi[1，i−1]. Σp[i+1，p]Σ唯一的条件是施加在这些向量上的约束集合必须等价于x1=x2=· · ·=xp∈M，其中p是向量的个数。至于目标函数（7），也有无限多的方法来重新计算，yk+1 =yk+ρA xk+1−bk+1.（十一）把它写在新的变量x 1，x 2，.下。. . ，xp. 唯一的i=1ii条件是当x1= x2=···= xp= x时重写的目标函数必须等于原始目标函数。如果以下残差随着k→∞收敛到0，则算法收敛¨p¨2p例如，如果p=D，则可以将（7）重写为F1（x1）+F2（x1，x2）+···+FD（x1，x2，. . . ，xD）。（十三）（a）这种变量分解和¨Σ¨Σ¨ ¨2rk=+。（b）这种重写目标函数的方式将产生我i=1我2i=1ii2（十二）26257不同的拉格朗日松弛，从而产生不同的算法。由于实际上有无限的这样的com-我们将在3.4节讨论ADMM的收敛性。binations，可以设计的算法数量6258DD¨我它们也是无限的，更不用说重组机制的不同选择，例如次梯度方法，因此，假设cst是一个与x无关的常数，我们有：[2]，[4]，[5]，[6]，[7]，[8]，[9]，[10]，[11]，[12]，[13]，[14]， [15]，[16]，[17]，[18]，[19]，[1我们把基于ADMM Alter的算法类称为-k+1[1，d−1]K[d+1，D]，yk）=（pk）<$xkkk¨2生成方向图匹配（ADGM）算法。 一与其他机制相比，ADMM的主要优点是+（y）（Adx+sd）+2-Adx+sd-2+cst，（23）它的子问题只涉及一个变量块，与目标函数的形式无关。作为ADGM的一个例子，我们在下面介绍一个段落。子问题（19）被简化为最小化Md（d = 1，2，.）上的下列二次函数. . . ，D）：典型的例子。尽管如此，这个例子仍然足够普遍，可以包括无限多的特殊情况。xAAdx +.A=k+Σ⊤1（Ayk + pk） X. （ 二十四）问题2（分解图匹配）最小化F1（x1）+F2（x1，x2）+···+FD（x1，x2，. . .（14）受A1 x1 + A2 x2 +···+ ADxD=0，（15）xd∈Md<$1≤d≤D，（16）其中（Ad）1≤d≤D是m×n矩阵，定义为使得（15）等价于x1=x2=· ··=xD，（Md）1≤d≤D是Rn的闭凸子集，满足M1<$M2<$···<$MD= M。（十七）很容易看出，上述问题等价于问题1的连续松弛。显然，这个问题是标准形式（8）的一个特例。因此，ADMM可以直接应用于它。问题2的增广拉格朗日量是ΣDLρ（x 1，x 2，. . . ，xD，y）=Fd（x1，. . . ，x d）D d dρd d总之，ADGM算法有三个主要步骤：1）选择（Ad）1≤d≤D和（Md）1≤d≤D满足问题2中的条件，2）通过在Md上最小化（24）来更新xk+1，3）使用（11）更新yk+1（并重复2），3）直到收敛）.3.3. 两种简单的ADGM算法让我们用两个例子来遵循上述三个步骤第一步：选择（Ad）1≤d≤D和（Md）1≤d≤D。第一、（Md）1≤d≤D取以下两个集合之一的值Mr={x：mat（x）的 每 行 之 和 ≤ 1}，（ 二十五）Mc={x：mat（x）的每列之和≤1}，（26）使得Mr和Mc都至少取一次。如果在G1（相对于G2）中没有遮挡全部被覆盖，则对于Mr（相应地Mc），项如果允许多对多匹配，则这些不等式约束被移除。在任一情况下，Mr和Mc是.ΣD+yd=1ΣA x¨PüeD+¨2¨A x？ . （ 十八）闭凸的。显然，由于Mr= Mc= M，（17）满足。D dd=1¨¨d=1D迪¨2第二，为了使x1 = x2 =···=xD，我们可以举例说明-选择（Ad）1≤d≤D，使得y更新步骤（11）和残差的计算（12）是微不足道的。让我们关注x更新步骤（10）：x 1= x 2，x 1= x 3，. . . ，x1=xD（27）xk+1 =argminLρ（xk+1，x，xk，yk）。（十九）或替代地D表示x∈Mdd−1[1，d−1]ΣDLρ（x，x，x126259DJDLD[d+1，D]x1=x2，x 2= x 3，. . . ，xD−1=xD。（二十八）容易看出，上述两组约束可以sk=Aixk+1+i=1DOd−1Ajxk，（20）j=d+1O我两者均以一般形式表示（15）。 每一个选择都导致不同 的 算 法 。 设 ADGM 1 表 示 从 （ 27 ） 获 得 的 值 ，ADGM 2表示从（28）获得的值。pk=Fii=dj=1k+1Jl=d+1xk. （见第（4）段）（21）步骤2：更新xk+1。将（27）和（28）代入（15），子问题（24）被简化为（细节在可以看出，（补充资料中给出了详细信息）ΣD补充）.ΣFi（xk+1，x，xk）=（pk）x。 （二十二）xk+1= argmin1<$x <$2−c<$x、（二十九）i=d[1，d−1][d+1，i]dx∈Md22XD6260DD=.1D22我D−1我XKD−d d1d其中，对于ADGM 1，（cd）1≤d≤D定义如下.Σ变量的一致性，这将导致更快的收敛。使用该方案，我们观察到，我们的算法-1天1天1天Od法律在实践中总是趋同的。在实验中，我们c1=D−1D=2xk−ρD=2yk−Fdρd=1i，I=2集合T1=300，T2=50，β=2，ρ0n1000cd= xk+1+1yk−ρΣDρi=dOd−1Fii=1k+1iO我j=d+1（三十）克杰（三十一）4. 实验我们将3.4节中的自适应方案应用于3.3节中提出的两种ADGM算法，并分别将它们表示为ADGM 1和ADGM 2。然而，在成对设置中，由于这两个算法是相同的，对于2≤d≤D，对于ADGM 2：我们将其简单地表示为ADGM。我们将ADGM和ADGM 1/ADGM 2与以下最先进的方法进行比较：c1 = xk−1yk−ρ11天ρd=11OdFdI=2DO−1xk，（32）成对：具有仿射约束的谱匹配（SMAC）[9]，投影不动 点 （ IPFP ） [23] ， 重 新 加 权 的 随 机 游 走 匹 配（RRWM）[6]，具有分支和界限的对偶分解（DD）[28]以及cD= xk+1+ρkFDDρi=1xk+1，（33）最大池匹配（MPM）[7]。我们应该注意到，DD仅在使用相同能量c =1（xk+1 +xk）+1（yk−yk）模型在[28]。 对于其他实验，DDd2d−11天-Fi2ρd+12ρdOd−1Oik+1kIjd+1（三十四）由于禁止的执行时间而被排除。此外，如[23]中所建议的，我们使用光谱匹配（SM）[22]返回的解决方案作为IPFP的初始化。i=d对于2≤d≤D−1。i=1j=d+1高阶：概率图匹配（PGM）[30]，张量匹配（TM）[11]，重加权随机游走超图匹配（RRWHM）[21]和块坐标-步骤3：更新yk+1。 从（27）和（28）可以看出，该步骤被简化为yk+1=yk+ρ（xk+1-xk+1），对于ADGM 1，yk+1=yk+ρ（xk+1−xk+1）nateAscent Graph Matching （ BCAGM ） [26].对 于BCAGM，我们使用MPM [7]作为子程序，因为在[26]中（并且再次通过我们的实验）表明，d d d−1d备注。 当D = 2时，这两个算法是相同的。注意，（29 ）表示xk+1 是cd 在Md 上 的 投 影。由于（Md）1≤d≤D只服从行或列约束，因此投影变为行或列方式，并且可以基于在单纯形上的投影来求解[8]。我们展示了如何做到这一点，并在补充中给出了上述算法的草图。3.4.收敛ADGM注意，问题2中的目标函数一般既不是可分的，也不是凸的这类函数的ADMM收敛性是未知的。实际上，我们的ADGM算法并不总是收敛的，特别是对于惩罚参数ρ的小值。当ρ很大时，它们很可能收敛。然而 ，我们也注意到，较小的ρ通常（但不总是）会获得更好的目标值。在此基础上，我们提出了一种自适应算法，该算法从一个小的初始值ρ0开始，进行T1次迭代以达到稳定，然后，如果每T2次迭代都没有对残差rk进行改进，则将ρ增大一个因子β并继续。这个方案背后的直觉很简单：我们希望用一个小的ρ来达到一个好的目标值，但是如果这导致缓慢（或没有）收敛，那么我们增加ρ来对XXXyX16261由于MPM的有效性，BCAGM（在[26]中表示为由于没有歧义，在续集中，我们将此变体简称为我们应该注意到，虽然我们将图匹配公式化为最小化问题，但上面列出的大多数方法都是最大化求解器，并且在以前的工作中，许多模型/目标函数都被设计为最大化。为了便于比较，ADGM也被转换为最大化求解器（通过使其最小化目标函数的加性逆），本节中报告的结果是针对最大化设置（即，目标值越高越好）。在实验中，我们还使用了一些成对最小化模型（如[28]中的模型），我们将其转换为最大化问题。在从（最小化）势建立亲和矩阵M之后，通过max（M）-M计算新的（最大化）亲和矩阵，其中max（M）表示M的最大元素。注意，不能简单地取−M，因为有些方法只适用于非负电位。最后，由于空间限制，我们将每个算法的报告运行时间保留在补充中（除了第一个实验，可以完整地呈现）。简而言之，ADGM比SMAC更快[9]6262IJL一..（a）20例患者vs 30例患者（10个离群值）（b）MPM 15/20（352.4927）(c)RRWM 15/20（352.4927）（d）IPFP 5/20（316.9299）表1：使用第4.1节中描述的成对模型A和先前在[28]中提出的成对模型A对房屋和酒店序列的结果。（e）SMAC 12/20（315.0426）（f）ADGM18/20（353.3569）图1：使用第4.1节中描述的成对模型B进行房屋匹配。真实值为343。1515 (Best以颜色查看）。(in成对设置）和ADGM 1/ADGM 2比TM[11]（在高阶设置中）更快，但比其他方法更慢。4.1. 房子和酒店CMU House和Hotel序列1在以前的工作中被它由111个合成房屋的框架和101个合成酒店的框架组成。这些序列中的每个帧都手动标记有30个特征点。成对模型A. 在这个实验中，我们匹配每个序列中所有可能的图像对，所有30个点（即，无异常值）。对这30个点执行Delaunay三角剖分以获得图形边缘。一元项是形状上下文描述符之间的距离[1]。 当匹配（i1，j1）到（i2，j2）时的成对项是失配的总百分比和达到全局最优的频率。结果在表1中给出。可以观察到DD和ADGM总是达到全局最优，但ADGM的速度快了数百倍。即使是最近的方法RRWM和MPM表现不佳，在这个模型（只有MPM产生可接受的结果）。此外，我们注意到与[28]中报告的结果相比，SMAC和IPFP的性能急剧下降。我们应该注意到，上述势，包含正值和负值，是为最小化问题定义的。 不清楚这些最大化求解器是如何在[28]中使用的。为了让读者能够复制结果，我们将我们的软件公开提供。两两模型B. 在这个实验中，我们将所有可能的序列对与基线（即，帧之间的分离，例如，第5帧和F2=ηexp.Σδ2/σ2 +（1−η）exp.Σα2/σ2 -1（35）帧105是100），以10个。对于每一对，我们将第一幅图像中的10、20和30个点与第二幅图像中的30个点进行我们设置一元其中η、σl、σa是一些权重和缩放常数，项为0，并计算成对项为−−→−−→δ、α根据d1=i1j1和d2=i2j2计算为：二、. −−→−−→。2Σ.−−→−−→ΣFij= exp −。i1j1 /σ、（三十七）δ=|d1− d2|，α= arccosi1j1·i2j2.（三十六）d1+d2d1d2其中σ2= 2500。 应该注意的是，对于每对（i1，j1）和（i2，j2）计算上述成对项，这个实验是从[28]使用他们的能量模型文件2复制的。应该注意的是，在[28]中，上述一元势被减去一个大的数字以防止阻塞。我们建议读者参考[28]以了解更多细节。为了便于与[28]中报告的结果进行比较，这里我们还报告了每个算法的性能，1http://vasc.ri.cmu.edu/idb/html/motion/index.html2http://www.cs.dartmouth.edu/ lorenzo/Papers/tkr_pami13_data.zip。I.E. 图是完全连通的。本实验在以前的工作中，包括[6]和[26]中的房子序列上进行。在这里，我们考虑酒店序列以及。 我们在图2中报告了每个算法的平均目标比率（即获得的目标值与地面真实值的比率）和平均准确度。 由于空间限制，我们只显示了允许遮挡的较难情况下的结果，并将其他结果留在补充中。正如人们可以观察到的，方法误差（%）全球选购配件（%）时间（s）房子MPM42.3200.02RRWM90.5100.01IPFP87.3000.02SMAC81.1100.18DD010014.20ADGM01000.03酒店MPM21.4944.800.02RRWM85.0500.01IPFP85.3700.02SMAC71.3300.18DD0.1910013.57ADGM0.191000.0262632|d− d|1.110.90.80.7120 40 60 80100基线1.110.90.80.7120 40 60 80100基线1.21.110.90.80.7120 40 60 80100基线1.110.90.80.70.6120 40 60 80 100基线0.80.80.80.80.60.60.60.60.40.20.40.20.40.20.40.2020 40 60 80100基线020 40 60 80100基线020 40 60 80100基线020 40 60 80 100基线(a) 众议院：20分vs 30分(b) 众议院：10分vs 30分(c) 酒店：20分vs 30分(d) 酒店：10分vs 30分图2：使用第4.1节中描述的成对模型B的House和Hotel序列结果。ADGM在几乎所有的测试中产生了最高的客观值。三阶模型。该实验与前一个实验具有相同的设置，但使用了[11]中提出的三阶模型。 我们将一元项和成对项设置为0，并在匹配两个三元组的点（i1，j1，k1）和（i2，j2，k2）时计算势为10.90.80.70.60.5120 40 60 80 100基线1.41.210.80.60.40.2120 40 60 80 100基线3ijk =exp.--- i1j1k1— fi2j 2k2Σβ2/γ 、（三十八）0.80.60.80.6其中fijk 是一个特征向量，0.40.20.40.2三角形（i，j，k），γ是所有平方的平均值。tances 我们在图中报告了House序列的结果结果3，并在补充中提供其他结果。可以观察到ADGM1 和 ADGM 2 实 现 了 非 常 相 似 的 性 能 ， 两 者 都 与BCAGM竞争[26]020 40 60 80 100基线(a) 20例患者vs 30例患者020 40 60 80 100基线(b) 10例患者vs 30例患者而优于所有其他方法。4.2. 汽车和摩托车汽车和摩托车数据集在[24]中介绍，并已在以前的工作中用于评估图匹配算法。它由30对汽车图像和20对摩托车图像组成，具有不同的形状，视点和比例。每对包含两个内点（cho-图3：使用三阶的第4.1节中描述的模型。将成对项设为F2=ηδ+（1−η）1−cosα，（39）ij2其中η∈[0，1]是权重常数，计算δ，α手动检测）和离群值（随机选择）。−−→−−→两两模型C. 在这个实验中，我们保留了两张图像中的所有内点，并将离群点随机添加到第二张图像中。根据d1=i1j1和d2=i2j2，−−→−−→δ=12， cosα=i1j1·i2j2.（四十）MPMRRWMIPFPSMACADGMMPMRRWMIPFPSMACADGMMPMRRWMIPFPSMACADGMMPMRRWMIPFPSMACADGMMPMRRWMIPFPSMACADGMMPMRRWMIPFPSMACADGMMPMRRWMIPFPSMACADGMMPMRRWMIPFPSMACADGMPGMTMRRWHMBCAGMADGM 1ADGM 2PGMTMRRWHMBCAGMADGM 1ADGM 2PGMTMRRWHMBCAGMADGM 1ADGM 2PGMTMRRWHMBCAGMADGM 1ADGM 2精度目的精度目的精度目的精度精度目的目的精度目的F6264异常值的数量以5为间隔从0到40不等。我们尝试了4.1节中描述的成对模型B，d1+d2d1d2直觉，F2 计算几何一致性，获得不满意的匹配结果（显示在柔软，−−→IJ −−→材料）。 受[28]中模型的启发，我们支持下面是一个新的模型，非常简单，但非常适合现实世界的图像。我们将一元项设置为0和com-在i1j1和i2j2之间，就长度和方向而言，第 上述电位测量相异性是-补间的边缘，因此相应的图形匹配626510.80.60.40.210.80.60.40.200 10 20 3040异常值0 10 20 3040异常值(a) 汽车10.80.60.40.210.80.60.40.200 10 20 3040异常值0 10 20 3040异常值(b) 摩托车1.210.80.60.410.80.60.40.200 5 1015异常值0 5 1015异常值(a) 汽车10.80.60.410.80.60.40.200 5 1015异常值0 5 1015异常值(b) 摩托车图4：使用4.2节中描述的成对模型C对汽车和摩托车的结果。(a)46例患者vs 66例患者（20个离群值）（b）MPM 13/46（966.2296）(c)RRWM 6/46（988.0872）（d）IPFP 35/46（1038.3965）(e)（f）ADGM 46/46（1043.0687）图5：使用成对模型C进行摩托车匹配在第4.2节中描述。（最好是彩色的）。问题是最小化。 基于长度和角度的成对电位先前在[24，28]和[32]中提出。然而，我们的计算是最简单的。 在这个实验中，η= 0。五、我们匹配每个图像对，并报告平均值图4中的每种方法的目标值和匹配精度。可以观察到ADGM完全优于所有其他方法。三阶模型。该实验与前一个实验具有相同的设置，除了它使用三阶模型（与House and Hotel实验相同），并且离群值的数量从0到16不等（间隔为2）。图6中报告了结果，图7中给出了匹配示例。ADGM在这个数据集上做得很好。在汽车上，ADGM 1和ADGM 2都取得了更好的客观价值。图6：使用第4.2节中描述的三阶模型对汽车和摩托车的结果。(a)25例患者vs 36例患者（9个离群值）（b）PGM 4/25（337.8194）(c)RRWHM 3/25 （ 1409.832 ）(d)BCAGM 15/25（1713.487）(e)ADGM 125/25 （ 2161.5354 ） （ f ） ADGM 225/25（2161.5354）图7：使用第4.2节中描述的三阶模型进行车辆匹配。（最好是彩色的）。7/9例优于BCAGM。在摩托车上，ADGM 1在5/9例病例中击败BCAGM，在1/9例病例中具有等同性能;ADGM 2在8/9例病例中击败BCAGM。5. 结论和今后的工作我们提出了ADGM，一类新的算法解决图匹配。两个例子的ADGM的实施和评估。结果表明，他们优于现有的成对方法和竞争力的最先进的高阶方法。在未来的工作中，我们计划采用一个更有原则的自适应方案的惩罚参数，并研究不同的ADGM变体我们的算法的软件实现鸣谢。我们感谢匿名评论者的深刻评论和建议。MPMRRWMIPFPSMACADGMMPMRRWMIPFPSMACADGMMPMRRWMIPFPSMACADGMMPMRRWMIPFPSMACADGMPGM TMRRWHMBCAGMADGM 1ADGM 2PGM TMRRWHMBCAGMADGM 1ADGM 2PGM TMRRWHMBCAGMADGM 1ADGM 2PGM TMRRWHMBCAGMADGM 1ADGM 2目的精度目的精度目的精度目的精度6266引用[1] S.贝隆吉，J. Malik和J.普兹查使用形状上下文的形状匹配和物体识别。IEEE模式分析与机器智能学报，24（4）：509[2] D. P. Bertsekas. 非线性规划雅典娜科学贝尔蒙特，1999年。[3] S. 博 伊 德 ， N. Parikh ， E. 楚 湾 ， 澳 - 地 Peleato 和 J.Eckstein通过交替方向乘子法的分布优化和统计学习。基金会和《机器学习》，3（1）：1-122，2011.[4] S.博伊德湖Xiao、肖氏A. Mutapcic和J.麦亭利 Notes on分解方法EE 364 B注释，斯坦福大学，第1-36页[5] R. E. Burkard，E.塞拉，P. M. Pardalos和L. S.皮苏利二次分配问题。在组合优化手册中，第1713-1809页。Springer，1998年。[6] M. Cho、J. Lee和K. M.李你图匹配的加权随机游动。计算机施普林格，2010年。[7] M. Cho，J.孙岛，澳-地Duchenne和J.庞塞在干草堆中寻找匹 配： 存在 离群 值的 图匹配 的最 大池 化策 略在Proceedings of the IEEE Conference on Computer Visionand Pattern Recognition，第2083[8] L.康达 快速投影到单纯形和球上。Mathematical Programming，第1-11页[9] T. Cour，P. Srinivasan，and J.石平衡图匹配。神经信息处理系统的进展，19：313，2007。[10] G. B. Dantzig和P.沃尔夫线性规划的分解原理。运筹学，8（1）：101[11] O. Duchenne，F.巴赫岛- S. Kweon和J.庞塞基于张量的高阶图匹配算法IEEE transactions on pattern analysis andmachine intelligence，33（12）：2383[12] O. Duchenne，A. Joulin和J.庞塞一个用于对象分类的图匹配核。2011年国际计算机视觉会议，第1792IEEE，2011年。[13] S. Gold和A.兰加拉詹一种图匹配的分级赋值算法。模式分析与机器智能，IEEE学报，18（4）：377[14] Kolmogorov和R.扎比使用图割计算具有遮挡的 计算机视觉，2001年。ICCV 2001年。诉讼第八届IEEE国际会议，第2卷，第508-515页。IEEE，2001年。[15] N. Komodakis和N.帕拉吉奥斯超越能量：高阶磁流变液的有效优化。 在计算机视觉和模式识别，2009年。CVPR 2009。 IEEE会议，第2985-2992页。IEEE，2009年。[16] N. Komodakis，N. Paragios和G.齐里塔斯通过对偶分解实现磁流变能量最小化。IEEE transactions on patternanalysis and machine intelligence，33（3）：531[17] T. C. Koopmans和M.贝克曼分配问题与经济活动的选址计量经济学：计量经济学会杂志，第53-76页[18] H. W. 库恩指派问题的匈牙利方法海军研究后勤季刊，2（1-2）：83[19] E. L.劳勒二次分配问题。Management-ment science，9（4）：586[20] D. K. Le-Huu. 离散马尔可夫随机场优化的加速一阶格式对偶分解 技术报告，Ce ntraleSupe′ lec ， Uni versite′P-Saclay，2014年。[21] J.李，M. Cho和K. M.李你 基于加权随机游动的超图匹配 。 在 ComputerVisionandPatternRecognition（CVPR），2011 IEEE Conference on，第1633-1640页中。IEEE，2011年。[22] M. Leordeanu和M.赫伯特利用成对约束求解对应问题的谱方法计算机视觉，2005年。ICCV 2005年。第十届IEEE国际会议，第2卷，第1482-1489页。IEEE，2005年。[23] M. Leordeanu，M. Hebert和R.苏克坦卡图匹配和地图推理的整数投影不动点方法。神经信息处理系统的进展，第1114-1122页，2009年[24] M.莱奥尔代亚努河Sukthankar和M. 赫伯特图匹配的无监督学习。International Journal of Computer Vision，96（1）：28[25] A. F.马丁斯，M。A.菲格雷多山口M. Aguiar，N. A.Smith和E. P. Xing。广告3：交替方向的双重分解图推理模型。The Journal of Machine Learning Research