没有合适的资源?快使用搜索试试~ 我知道了~
Paul Swoboda∗,1,2, Dagmar Kainm¨uller3,4, Ashkan Mokarian3,4, Christian Theobalt1,2, Florian Bernard1,2312221133111560多图匹配的凸松弛01 MPI信息学 2 Saarland信息学校园 3 柏林健康研究所 4 MDC柏林0摘要0我们提出了一种用于多图匹配问题的凸松弛方法。我们的公式允许部分成对匹配,保证循环一致性,我们的目标函数包括线性和二次成本。此外,我们还提出了高阶成本的扩展。为了解决凸松弛问题,我们采用了一种优化对偶问题的消息传递算法。我们在计算机视觉的已建立基准问题上进行了实验比较,以及在生物图像分析中规模超过以前研究的多图匹配实例的大问题上进行了实验。01. 引言0在计算机视觉和计算机图形学研究中,寻找图像或形状之间的对应关系是一个长期存在的问题。这些问题对于各种应用非常重要,包括跟踪、分割或形状建模。然而,许多对应问题的表述,如众所周知的二次分配问题(QAP),已知是NP难的。大多数对应问题可以解释为图匹配问题的一个实例,其中的目标是建立两个给定图的节点之间的对应关系,使得两个图的边能够一致匹配。多图匹配(MGM)问题将图匹配推广到同时建立多个图之间的对应关系。对于多个匹配,循环一致性的概念出现:假设Xpq是图p和q之间的分配矩阵。条件Xpr Xrq = Xpq � p, q,r被称为循环一致性,参见图1的示例。多匹配问题在多视图重建、视频中的对象跟踪或形状集合对齐等方面是相关的。通常,通过多图匹配计算对应关系会得到比仅通过一系列图匹配问题计算的匹配结果更好的质量解决方案。原因是数据中的噪声引入的虚假匹配可以得到纠正,因为每个图之间的对应关系都通过循环一致性依赖于其他匹配。0� 对应作者的电子邮件:pswoboda@mpi-inf.mpg.de0图A0图B 图C0图1.多图匹配中的循环一致性示例(最佳观看效果为彩色)。每个图A、B、C包含三个节点(绿色、蓝色、紫色)和三条边(白线)。真实对应关系由节点颜色和节点标签1、2、3表示。图对之间的匹配由彩色线条表示(A � B为黄色,A � C为灰色,B �C为蓝色)。虚线表示错误的匹配。多匹配A1 � B2 � C2 �A2不具有循环一致性。0与仅通过一系列图匹配问题计算的匹配相比,通过多图匹配计算的匹配结果质量更高。原因是数据中的噪声引入的虚假匹配可以得到纠正,因为每个图之间的对应关系都通过循环一致性依赖于其他匹配。0尽管两个图之间的匹配问题已经研究了五十多年并且受到了关注[6, 18, 28, 20, 9, 36, 35, 48, 30, 26, 12, 1, 16, 11, 4,46, 49, 14, 21, 2,19],但多图匹配问题的研究较少,因此在理论和实践方面都有很大的改进潜力。在这项工作中,我们提出了一种新颖的多图匹配方法,具有以下主要贡献:3. Lagrangian MGM relaxation111570贡献。与大多数先前的工作相比,我们的方法基于一个有原则和理论上良好的凸优化方法,它(i)在考虑循环一致性约束的同时,联合优化了一个通用的二次多图匹配目标,(ii)相对于强松弛提供了原始/对偶间隙,(iii)不依赖于初始化,(iv)由于使用了最先进的消息传递技术,可以扩展到大规模问题,(v)可以轻松扩展到多超图匹配问题。据我们所知,文献中没有结合这些理想特性的求解器。02. 相关工作0我们将在下面回顾与图匹配和多图匹配问题相关的算法先前工作。图匹配。图匹配的最简单版本是线性分配问题(LAP),可以使用匈牙利[24]或拍卖[6]算法在多项式时间内解决。对于二次成本,图匹配问题也被称为二次分配问题(QAP)[18]。它被认为是实际上最困难的NP难问题之一[28]。因此,已经提出了许多启发式和近似算法,其中包括基于Lagrangian松弛[36, 47, 35],半定规划[30, 16]和凸优化[12, 1,11, 4]的算法。除此之外,还提出了基于谱技术[20,9]、路径跟踪[46, 49,14]、循环置信传播[2]和ADMM[19]的原始启发式算法。关于在组合优化社区中使用的技术的综述论文,我们参考[28,21]。图匹配的高阶变体,即超图匹配,也已经被考虑过,例如在[25,10]中。我们的算法可以被看作是从图匹配问题到更困难的多图匹配问题的消息传递技术的扩展,这些技术在[47,35]中提出。多图匹配。已经应用了各种技术来解决多图匹配问题。方法[32]保存了表示所有成对匹配的张量。这样,循环一致性得到满足,但他们的方法不可扩展。在[37]中提出了一种基于聚类的快速MGM算法,但只考虑了线性成本。在[44]中,作者交替优化单个图匹配问题,并重复强制执行循环一致性,以逐步获得更好的MGM解决方案。[38]的工作提出了一个平滑的非凸秩约束形式的多匹配问题,并利用块坐标下降来解决所得问题。其他方法包括基于随机游走的扩展0方法[29],分解图匹配[49]或矩阵分解[45]。[43]的作者建议交替使用现有的图匹配求解器,以实现循环一致性。[42,41]的工作也使用现有的图匹配求解器,并逐渐通过添加循环一致性约束来扩展问题,直到获得可行的多图匹配。然而,[43, 42, 41]的工作没有使用整体优化公式。在[16,4]中,作者考虑了基于半定规划的MGM的凸松弛。虽然[16]的方法依赖于使问题计算昂贵的变量提升,但[4]的方法是无提升的,但仅讨论了完全匹配的情况。另一种方法将MGM问题的解决分为两个步骤:首先解决单个成对图匹配问题,然后通过后处理强制执行循环一致性。[27, 7, 50, 31, 22,5]的工作假设它们给出了单个匹配,然后通过矩阵分解对它们进行后处理,以获得循环一致的匹配,他们称之为置换同步。类似地,在[3]中,作者改进了给定的匹配,但他们没有获得循环一致的匹配。组织。第3节包含我们的整体多图匹配方法。在第3.1节中,我们正式陈述了MGM问题,在第3.2节中,我们描述了线性规划(LP)松弛的一般Lagrange分解框架,在第3.3节中,我们在这个框架内提出了MGM问题的分解。为了获得一个可扩展的LP求解器,我们建议使用消息传递,在第3.4节中描述了消息,第3.5节中描述了求解器本身。由于循环一致性是通过立方数量的约束来强制执行的,在第3.6节中,我们提出了一个双重割平面算法,只包括工作集中所需的约束。我们在第3.7节中讨论了对多超图匹配问题的扩展。最后,在第4节中,我们在计算机视觉和生物医学图像分析问题上对我们的求解器进行了实验评估。我们在附录A中提供了额外的细节。代码和数据集可从https://github.com/LPMP/LPMP获得。0在本节中,我们首先介绍具有二次成本的多图匹配问题。接下来,我们回顾Lagrange分解框架[34],并展示如何将其应用于将MGM分解为可高效求解的子问题。我们还回顾了[34]中的消息传递算法,用于一般分解,并详细说明了如何通过该方法优化我们的MGM分解。最后,我们描述了一个用于循环一致性约束的对偶割平面算法。由于问题分解很复杂,因此描述它所需的符号也是如此。为了帮助读者,我们一致地使用指代相同类型对象的符号。使用的索引变量总结在表1中。min{X[pq]∈Pmpmq }�p,q∈[d](x[pq])⊤W [pq]x[pq](1)s.t.X[pq]X[qr] ≤ X[pr] ,(2)Pmn = {X ∈ {0,1}m×n : X1n≤1m, X⊤1m≤1n} . (3)∀x ∈ Y k :Ak,jx ∈ {0, 1}me .(5)minµ∈Λj∈V⟨θj, µj⟩(6)111580描述它所需的符号也是如此。为了帮助读者,我们一致地使用指代相同类型对象的符号。使用的索引变量总结在表1中。0表1. 符号约定0符号含义0j, k 子问题 s, t 向量和矩阵索引 p, q, r成对GM问题的索引 i, ℓ用于求和的临时索引 {∙} [ pq ]从p到q的匹配,p < q0{∙} [ pq ] 从q到p的匹配,p < q d图的数量 m p 图p中的节点数03.1. 问题表述0我们将多图匹配问题的问题表述为在所有图对之间联合求解成对图匹配问题,并附加循环一致性约束。尽管我们的方法适用于考虑子集的成对图匹配,但为了符号方便,我们将MGM问题表述为所有可能的图对的匹配。我们假设匹配第p个图和第q个图的成本,其中p, q ∈ [ d ] := { 1 , . . . , d },由 ( x [ pq ] ) � W [ pq ] x [ pq ]给出,因此MGM问题可以表示为:0其中我们定义了x [ pq ] := vec( X [ pq ]),而m×n(部分)置换矩阵P mn的集合定义如下:0请注意,我们在MGM问题中写出了所有引用图对(或三元组)的索引,例如W [ pq ]。0命题1. 设 ( X [ pq ] ) p,q ∈ [ d ]是一组部分匹配。那么约束 (2)将剔除所有非循环一致的元素。0我们在附录中的示例1中给出了约束2何时处于活动状态的最小示例。03.2. Lagrange分解0我们将在Lagrange分解框架中解决问题(1)。为此,我们回顾了[34]中的框架,在那里定义了整数松弛成对可分离线性规划(IRPS-LP)类。IRPS-LP是对偶分解[13]的特例。0定义1 (IRPS-LP [34]) . 设 N ∈ N ,并且 G = ( V , E )是一个图,其中 V = { 1 , . . . , N } 。对于每个 j ∈ V,设 d j ∈ N ,Y j � { 0 , 1 } d j ,以及 θ j ∈ R d j 。设Λ := conv ( Y 1 ) × ∙ ∙ ∙ × conv ( Y N ) 。对于每个 { j, k } = e ∈ E ,设 m e ∈ N ,A j,k ∈ { 0 , 1 } m e × d j,以及 A k,j ∈ { 0 , 1 } m e × d k ,满足0� x ∈ Y j : A j,k x ∈ { 0 , 1 } m e , 并且 (4)0然后,下面的LP称为整数松弛的成对可分离的,相对于图G。0对于 �{ j, k } ∈ E : A j,k µ j = A k,j µ k . (7)0这里,G = ( V , E )定义了一个与IRPS-LP相关的一般问题分解图,不应与我们希望匹配的图混淆。每个 j ∈V 定义一个子问题,每个边 jk ∈ E定义了子问题的依赖关系。定义1比一般的Lagrange分解更具体,因为首先,假设子问题是二进制的,其次,线性约束(7)描述了子问题的依赖关系,这些约束由将01向量映射到01向量的01矩阵定义。IRPS-LP可以通过[34]的消息传递框架进行高效优化。在接下来的内容中,我们将通过我们给自由变量x j ∈ Y j 的独特名称来引用子问题 j ∈ V。0它们优化的变量。从上下文中将清楚地知道我们何时使用子问题变量xj来引用子问题j。03.3. 多图匹配分解0我们将提出将问题(1)分解为IRPS-LP。在图2中,我们说明了子问题的分解。我们的分解包括三种类型的子问题:(i)匹配子问题,用于将一个图的节点与另一个图的节点匹配,(ii)二次成本子问题,用于将一个图的边与另一个图的边匹配,以及(iii)循环一致性子问题,用于约束来自三个不同图的匹配为有效的多匹配。在接下来的内容中,我们将使用以下符号规则:给定图p和q之间的成对图匹配问题,其中不失一般性地p
�∈ [� #]0�'3∈0,1 6 7 �∈ [� $]0��&'3∈0,1 6 > ×6 >3 � ∈ � # 3 � ∈ [� #]0�&'3∈0,1 6 7 ×6 73 � ∈ � $ 3 � ∈ [� $]0成对GM问题333(�#$)<�#$�[#$]0��&3∈0,1 6 > �∈ [� " ]0�'3∈0,1 6 8 �∈ [� $]0��&'3∈0,1 6 > ×6 >3 � ∈ � " 3 � ∈ [� " ]0�&'3∈0,1 6 8 ×6 83 � ∈ � $ 3 � ∈ [� $]0成对GM问题333(�"$)<�"$�["$]0循环一致性约束333�["#]�#$≤�["$]0�&'3∈{0,1}0匹配子问题s0二次成本子问题循环一致性子问题0图2.三个成对GM问题[pq],[pr],[qr]的子问题分解及其耦合的概览,以及[pqr]的循环一致性约束(最佳以彩色查看)。圆角矩形对应于Def.1中的(一些)节点V,彩色线对应于(一些)边E。0并为了更容易解释(例如,我们使用X而不是X[pq]),我们省略上标p,q。我们将(mp×mq)维部分匹配矩阵X写成矩阵行和列的形式0�0�0X1,�...Xmp,�0�0�� = � X�,1...X�,mq �. (8)0对于X的每一行索引为s∈[mp],我们定义一个可行集的子问0Ys ={x∈{0,1}mq:�x,1�≤1},对于每一列索引为t∈[mq],我们定义一个可行集为Yt ={x∈{0,1}mp:�x,1�≤1}。则X∈Pmpmq等价于(9)和(10):0(对于s∈[mp],(Xs,�)�∈Ys,以及(9))0X�,t∈Yt for t∈[mq]. (10)The pairwise costs are θst = 0.5·(W (st) + (W (ts))⊤),sothatwecanwritethequadraticcostfunction0.5·((xs)⊤W (st)xt + (xt)⊤W (ts)xs) in terms of each pair-wise st-factor (s, t ∈ [mq], s < t) as the linear term⟨xst, θst⟩. Analoguously, we define the costs for the vari-ables xs, xt, xst, s, t ∈ [mp]. Note that this constructioncorresponds to the local polytope [39].Cycle consistency subproblems. Since the cycle con-sistency subproblems couple the individual pairwise graphmatching problems, in this paragraph we cannot drop thesuperscripts p, q, r, so that we e.g. write X[pq] instead ofX, and x[pq],s ∈ Y [pq],s instead of xs ∈ Y s.Let now the triplet of matchings X[pq], X[qr] and X[pr]be given. The element-wise matrix inequality X[pq]X[qr] ≤X[pr] comprises mpmr scalar inequalities. Let us considerthe scalar inequality at position (s, t) ∈ [mp] × [mr], whichreadsX[pq]s,∗ X[qr]∗,t =�i∈[mq]X[pq]s,i X[qr]i,t≤ X[pr]st.(16)Accordingly, we define the feasible setY [pqr],st = {x[pqr],st = (a, b, c) ∈ {0, 1}mq×mq×1 :⟨a, b⟩ ≤ c} .(17)For any p, q, r, s, t, the matching constraints Aj,kµj=Ak,jµk from (7) translate into111600(i) x[pq],s = a for x[pq],s ∈ Y[pq],s from (9)0(ii) x[qr],t = b for x[qr],t ∈ Y[qr],t from (10)0(iii) x[pr],st = c for x[pr],st ∈ Y[pr],s from (9), and0(iv) x[pr],ts = c for x[pr],ts ∈ Y[pr],t from (10),0其中x[pqr],st = (a, b, c) ∈Y[pqr],st。请注意,这里我们明确指示了成对图匹配问题的可行集(9)和(10)中的索引,例如,我们写Y[pq],s来表示给定p, q的(9)中的Ys。0注2:约束(iii)和(iv)只需要其中一个。我们在我们的公式中包含两者,因为约束将转化为Lagrange变量,并且对于我们的算法来说,拥有这种过完备表示是有利的,因为它会导致更频繁的更新。03.4. 消息0正如上面已经指出的,我们不直接求解原始问题(6),而是求解其对偶问题。具体来说,我们考虑与θ等价的重新参数化成本函数θ的空间,其中我们要求对于每个对原始问题(6)可行的µ,满足�µ, θ� = �µ, θ�。0可以通过以下方式获得这样的重新参数化成本函数:对于任意两个依赖的子问题{j, k} = e ∈E,其中关联的约束矩阵Aj,k ∈ {0, 1}me × dj,Ak,j ∈ {0,1}me ×dk(参见定义1),我们可以根据更新规则将θj和θk更改为任意向量∆ ∈ Rme0ˆθj := θj + (Aj,k)�∆ (18) ˆθk := θk −(Ak,j)�∆. (19)0我们将根据规则(18)–(19)对θ进行任何更新称为消息传递。消息传递不会改变任何原始可行解的成本,因为0�ˆθj, µj� + �ˆθk, µk�0= �θj + (Aj,k)�∆, µj� + �θk − (Ak,j)�∆, µk� (20)0= �θj, µj� + �θk, µk� + �∆, Aj,kµj − Ak,jµk� (21)0(7) = �θj, µj� + �θk, µk�. (22)0然而,消息传递确实会改变由(6)给出的对偶下界L(θ),其定义如下:0L(θ) := 0j ∈ V min x ∈ Yj �θj, x�. (23)0通过消息传递获得的所有成本中L(θ)的最大值等于(6)的最小值,通过线性规划对偶性可得。我们通过消息传递来改变成本θ,以最大化下界L(θ)。基本消息更新。如果消息更新作用于一对因子{j, k} ∈E,并通过消息∆对因子j和k进行重新参数化,我们将其称为基本消息更新。基本消息更新要求单调地减小下界L(θ),并且在偏序关系下是最大的,如[34]所述。由于在我们的情况下,所有基本消息都可以通过按照[34]的方法机械地推导得到,我们在表2中给出了匹配/二次/循环一致性子问题因子之间的相应更新。我们用∆ = msg(j,k)表示消息计算,用repam(∆, j,k)表示重新参数化。我们的整体算法将通过传递一系列重新加权的基本消息进行。03.5. 消息传递算法0算法1展示了IRPS-LP通用消息传递算法的前向传递过程。它按照给定顺序依次访问子问题的子集。对于每个访问的因子j,它首先从一组相邻的子问题R→j接收基本消息更新。其次,它通过带有权重ω→j的缩放基本消息传递更新向另一组相邻的子问题S→j发送消息。在反向传递中,我们将其反转。̸̸̸̸5repam(∆, k, j);111610j ∈ V k ∈ V ∆ = msg(j, k)0x s ∈ Y s x t ∈ Y t θ s (x s t) − min x ∈ Y s \{x s t} θ s (x)0x t ∈ Y t x s ∈ Y s θ t (x t s) − min x ∈ Y t \{x t s} θ t (x)0匹配/二次 x s ∈ Y s x st ∈ Y st θ s − min x ∈ Y s θ s (x)0x st ∈ Y st x s ∈ Y s min → θ st0x st ∈ Y st x t ∈ Y t min ↓ θ st0x s ∈ Y s x st ∈ Y st θ s − min x ∈ Y s θ s (x)0x st ∈ Y st x s ∈ Y s min → θ st0x st ∈ Y st x t ∈ Y t min ↓ θ st0x [pq],s ∈ Y [pq],s (a, b, c) ∈ Y [pqr],st θ [pq],s − min x ∈ Y [pq],s θ0x [qr],t ∈ Y [qr],t (a, b, c) ∈ Y [pqr],st θ [qr],t − min x ∈ Y [qr],t θ [qr],t0x [pr],s ∈ Y [pr],s (a, b, c) ∈ Y [pqr],st θ [pr],s (x [pr],s t) − min x ∈ Y [pr],s \{x [pr],s t}0θ [pr],s (x)0x [pr],t ∈ Y [pr],t (a, b, c) ∈ Y [pqr],st θ [pr],t (x [pr],t s) − min x ∈ Y [pr],t \{x [pr],t s} θ[pr],t (x)0(a, b, c) ∈ Y [pqr],st x [pq],s ∈ Y [pq],s (min (a i, a i + b i + c, min j ≠ i {a i + b j}) − min (0, c, min j {b j})) i = 1,...,m q (a, b,c) ∈ Y [pqr],st x [qr],t ∈ Y [qr],t (min (b i, a i + b i + c, min j ≠ i {a i + b j}) − min (0, c, min i {a i})) j = 1,...,m p (a, b, c) ∈ Y[pqr],st x [pr],s ∈ Y [pr],s min (z, z + min i {a i + b i}) − min (0, min i {a i}, min j {b j}, min i ≠ j {a i + b j}) (a, b, c) ∈ Y[pqr],st x [pr],t ∈ Y [pr],t min (z, z + min i {a i + b i}) − min (0, min i {a i}, min j {b j}, min i ≠ j {a i + b j})0表2. 基本消息更新。符号 min → A 表示矩阵 A 按行取最小值,而 min ↓ (A) 表示矩阵 A 按列取最小值。0为了使得在算法1中,我们按照访问因子的顺序进行替换 (R→, S →, ω →) 为 (R ←, S ←, ω←)。为了方便起见,我们定义 N j := {k : {j, k} ∈ E}作为子问题图 (V, E) 中第 j个子问题的邻居。为了使用算法1解决上述的MGM问题,我们指定以下自由参数:• V update对应于所有匹配子问题。• V update的顺序:我们按照索引 p, q ∈ [d]对图匹配子问题进行字典序排序。对于给定的 p 和 q之间的图匹配问题,我们首先考虑列匹配子问题 x [pq], 1, .. . , x [pq], m q,然后是行匹配子问题 x [pq], 1, . . . , x[pq], m p。此外,我们定义0• R → j :=0� N j \{x [pq],st : s < t}, j = x [pq],t, N j\{x [pq],st : s < t}, j = x [pq],t, and0� N j \{x [pq],st : s > t}, j = x [pq],t, N j \{x [pq],st : s > t}, j = x [pq],t, and •ω → j := 10# { S → j }。我们定义 R ← j := S → j 和 S ← j := R →j,即我们将 R → j 和 S → j 中的“<”和“>”互换。0算法1:IRPS-LP消息传递的前向传递01 对于 j ∈ V 按升序更新 � V02 接收消息:03 对于 k ∈ R → j � { k ∈ V : { j, k } ∈ E } 进行循环04 ∆ = msg(k, j) ;06 结束07 发送消息:08 对于 k ∈ S → j � { k ∈ V : { j, k } ∈ E } 进行循环09 ∆ k = msg( j, k ) ;011 对于 k ∈ S → j � { k ∈ V : { j, k } ∈ E } do012 repam( ω → j,k ∙ ∆ k , k, j ) ;013 结束014 结束03.6. 循环一致性的割平面0有 O ( m 2 d 3 ) 个循环一致性子问题,其中 m = max p∈ [ d ] { m p } ,即每个图匹配三元组一个̸111620p, q, r ∈ [ d ] 且每对节点 s ∈ [ m p ] , t ∈ [ m r ]。因此,一次性添加所有这些节点是不切实际的。由于其中许多节点不是实现LP最优解所必需的,我们采用割平面方法,只添加那些保证增加对偶下界 L ( θ )的循环一致性子问题。具体来说,我们开始优化时没有任何循环一致性子问题。当没有进展或经过一定数量的迭代后,我们开始添加循环一致性子问题。为此,我们首先枚举所有图匹配三元组 { p, q, r } ,其中 p, q, r ∈ [ d ]。对于每个三元组,我们枚举所有相关的循环一致性子问题 x [ pqr ] ,st0并测试如果添加 x [ pqr ] ,st,对偶下界将增加多少。我们记录增加量,并添加 K个最佳循环一致性子问题,其中 K是要添加的子问题的固定数量。从添加子问题 x [ pqr ] ,st可以使用算法2计算对偶下界的保证增加量,见附录A。03.7. 多超图匹配0我们的框架可以轻松扩展到超图匹配情况。对于三阶情况,我们有3阶张量 W ′ [ pq ] ,而不是矩阵 W [ pq ],如(1)所示。换句话说,我们有一个多线性对称形式的三阶张量 W ′ [ pq ] ∈ R m p m q × m p m q × m p m q,而不是矩阵 W [ pq ] ∈ R m p m q × m p m q,如(1)所示。为了解决这个更高阶的成本形式,我们引入了三阶成本子问题,并将它们与二次子问题连接起来,就像对MRFs所做的那样,参见[40,17]。虽然超图匹配公式可以用于优化更复杂的成本形式,但我们将其用于加强我们的LP松弛,就像对MRFs所做的那样[40]。这相当于在拉格朗日分解中具有零成本的三阶成本子问题。由于添加所有可能的三阶成本子问题将导致计算上的限制,我们采用了[33]中提出的割平面方法,该方法使用最大割问题的约简来找到违反的循环不等式。然后将找到的循环三角化以产生我们的公式中的三阶子问题。03.8. 运行时间0基本松弛的每次迭代运行时间与非零条目的数量 # { ij : Wij � = 0 }和三元组约束的数量成线性关系,因为表2中的相应操作可以在相应的时间内计算出来。当我们进一步加强问题时,相应的消息传递操作可以在每个三阶成本子问题 p ∈ [ d ]的时间 O ( m 3 p )中进行简单地执行。对于零成本的三阶子问题,[23]中描述了更高效的消息传递操作,给出了预期的运行时间 O ( m 2p log( m p ))。04. 实验0在本节中,我们对我们的算法进行了实验评估,我们考虑了两个变体:MP:我们的消息传递算法1与第3.6节中的循环一致性割平面例程。我们使用排列同步[27]在解决LAP后基于舍入后的对偶成本获得原始解。MP-T:与上述MP算法相同,但还有第3.7节中描述的额外加强。04.1. 合成的MGM问题0根据[41]的作者的实验协议,我们生成了四种不同配置的合成MGM问题(complete,density,deform,outlier),其中每个问题的图数量d从4变化到16。有关问题生成的详细信息,请参见[41]。我们将我们的MP/MP-T算法与RRWM[8],基于组合的亲和力优化(CAO)[41],MatchOpt(mOpt)[44],排列同步(mSync)[27]以及最新的DS*方法[4]进行比较。结果如图3所示。我们的MP-T方法在complete和density实例上的表现与DS*相似,并且与其他方法相比要好得多。请注意,与DS*相反,我们的方法明确考虑了异常值,因此我们的方法在具有大量异常值的设置中特别适用(请参见异常值案例)。除了complete,MP已经很紧密,收紧(第3.7节)显着改善了结果,可以通过将MP与MP-T进行比较来看出。我们认为我们的方法的优势在于它可以扩展到优化更紧密的LP松弛,而在其他更为特定的方法中这将是困难的[8, 42, 44, 4, 27]。04.2. CMU房屋和酒店0在这个实验中,我们考虑CMU房屋和酒店的序列,这是带有注释的图像序列。为了获得具有挑战性的MGM问题,我们考虑了40%的点是异常值(每个图像的总点数为10)。为此,我们遵循了[41]的协议,其中进一步描述了详细信息。我们考虑与第4.1节中相同的一组MGM算法。这个实验的结果如图4所示。在这两个数据集中,我们的方法(MP-T)相比于其他所有方法都实现了更高的精确度,同时也实现了更好的召回率。这再次证实了我们方法的鲁棒性。04.3. 秀丽隐杆线虫00.20.40.60.810.20.40.60.810.20.40.60.80.20.40.60.810.20.40.60.810.20.40.60.810.20.40.60.80.20.40.60.810.30.40.50.60.700.20.40.60.80.40.60.8100.51̸111630rrwm cao-c* cao-c mOpt mSync DS* 我们的(MP) 我们的(MP-T)04 8 12 16 d0精确率0合成/complete04 8 12 16 d0精确率0合成/密度04 8 12 16 d0精确率0合成/变形04 8 12 16 d0精确率0合成/异常值04 8 12 16 d0合成/complete04 8 12 16 d0合成/密度04 8 12 16 d0合成/变形04 8 12 16 d0合成/异常值0图3. 合成数据的结果(最好以彩色查看)。请注意,在第一列(complete)中,DS*,MP和MP-T方法在所有情况下都实现了完美匹配。04 8 12 16 d0精确率0房
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功