基于多样性和随机性的图聚类多图增量匹配方法

基于多样性和随机性的图聚类多图增量匹配田树宇1、严俊池2、刘伟3、李宝新11亚利桑那州立大学，2上海交通大学，3腾讯AI实验室@asu.edu，yanjunchi@sjtu.edu.cn，wl2223@columbia.edu抽象。多图匹配是指找到跨图的对应关系，这在传统上通过在单批中匹配所有图来解决。 然而，在现实世界的应用程序中，图形通常是增量收集的，而不是一劳永逸。 本文提出了一种新的多图匹配方法，该方法在全局一致性约束下利用先前的匹配结果对到达图进行处理。当一个新的图到达，而不是重新优化所有的图，我们建议划分成具有一定的拓扑结构的子集图，并在每个子集内进行优化分区过程的多样性内的分区和随机性的迭代，我们提出了一个解释，为什么这两个因素是必不可少的。最后的匹配结果是通过一个交集图在所有子集上计算的大量的实验结果表明，我们的算法显着提高效率，而不牺牲准确性的合成和真实图像数据集。关键词：多图匹配;增量图匹配;定点过程;图聚类1介绍图匹配（Graph matching，GM）是指通过探索一元（顶点）和成对（边）亲和度来找到一组图上的公共顶点对应关系的问题，是计算机视觉中的基本问题，并且已知是NP难的[1]。与矢量数据相比，当需要考虑结构关系时，表达性图表示往往更受欢迎。由于其对噪声的鲁棒性，GM已被采用在各种视觉应用例如场景理解[2]、视觉跟踪[3]和对象识别[4]等。虽然在利用结构数据方面被证明是成功的，但两图匹配仍然遭受固有的局部模糊性，这一方面导致非平滑和困难的优化问题。另一方面，亲和度目标可以偏离地面实况对应。虽然学习亲和度函数[5]可以缓解这样的问题，但可以为联合分析带来更多的图形匹配可以是消除局部偏差的更自然和有效的方式[6，7]。然而，不是一次获得，而是在实践中经常随时间收集图，例如，街景车拍摄的照片、2Tianshu Yu，Junchi Yan，Wei Liu，Baoxin Li监控摄像头新发现的蛋白质现有蛋白质对于这种设置，通过将旧的批次和新的图视为新的批次来从头开始匹配的朴素策略是低效的。给定先前的匹配结果，出现了如何利用现有匹配来加速新匹配或甚至提高准确性的问题尽管有实际的重要性，很少的努力，以解决这个在线设置，这是本文的重点。与大量关于离线多图匹配的文献[7-14]相比– 据我们所知，这是解决多个图的增量匹配问题的第一批作品之一。– 与离线基线相比，该方法可以实现甚至提高匹配精度，同时显着降低计算成本。– 我们提出的结构和机制的解释，这可以被视为一个更一般的框架[6]和[7]。2相关作品由于其重要性和基础性，在最近的调查中已经进行了大量的图匹配工作并进行了彻底的审查[15]。我们从以下几个方面对代表作进行分类。2.1亲和函数模型图匹配结合了一元节点到节点，和二阶，甚至更高阶，（超）边到（超）边结构相似性。在其传统设置中，其中不考虑高阶亲和性[16-20]，两个图匹配问题可以被公式化为二次分配问题（QAP）[1]，是众所周知的NP完全[21]。最近关于超图匹配的工作进一步探索了亲和函数建模[22-26]中的高阶（并且主要是三阶）与上述方法相比，其中亲和度函数是预定义的，而不管它们的顺序或属性层，采用学习来使亲和度函数适应不同的设置[16，19，5]。已经探索了有监督[5]和无监督[16]学习范式以提高匹配精度。然而，无论是基于学习还是无学习的亲和函数建模都不能完全解决两图匹配中固有的模糊性和噪声。2.2求解器和技术在过去的几十年里，出现了各种GM求解器。大量的文献致力于不同的松弛技术的研究，以减轻在自然界中的困难的组合问题典型的松弛包括i）增量多图匹配3i，j=1i，j=1匹配矩阵上的双随机松弛[17，27，28]; ii）半定规划（SDP）[29，30];iii）谱松弛[27，31]。从优化的角度来看，不同的延拓方法[17，32，33]被广泛采用。与这些涉及后处理步骤以二进制化最终结果的连续松弛方法不同，若干方法倾向于直接在离散分配空间中计算解基于采样的方法[34，35]通过蒙特卡罗采样直接生成离散解最近[36]设计了一个定制的禁忌搜索图匹配。我们的方法涉及迭代求解成对匹配。我们从上述技术出发，遵循基于无二进制化合成的技术[7]以得到已被证明是高效和有效的成对匹配2.3多图匹配除了两个图匹配之外，一种新兴的工作倾向于联合解决多个图的匹配问题 这些作品[37 -39，9-11，40，13，41]的动机是：i）在实际情况下，更常见的是多个图可用并且需要用于匹配; ii）对一批图的可用性提供全局信息，以实现针对局部噪声的鲁棒模型。对每对图采用独立的两图匹配方法可能导致所谓的循环不一致问题。考虑一个玩具样本，用于在没有外部的情况下获得相等大小的Gi、Gj、Gk。独立于每对图获得的时间匹配解Xij、Xik、Xkj可能导致循环不一致性：如[9]中所示。为了解决这个问题，提出了各种多图匹配模型，以迭代或一次性方式结合所谓的一致性我们按照调查[15]将这些作品分为以下两类。迭代方法[10，9，6，11，7]试图找到亲和性和一致性得分之间的权衡。在一般情况下，作者写出了多重图的目标通过添加成对亲和度项{vec（X）Kvec（X）}N来匹配，以及成对匹配{X}N从而在每次迭代严格地或逐渐地满足循环一致性约束具体地说，[9，6]在整个迭代变量更新过程中强制执行严格的循环一致性约束Xij=Xib Xbj结果，由于对起始点和更新旋转顺序的固有敏感性，匹配精度可能下降。在[10]中也采用这种思想将两图匹配方法-相比之下，在[11，7]中设计了一种更灵活和鲁棒的机制，由此在迭代中逐渐增加一致性。单次方法[39，40]试图在假定的两图匹配的情况下强制执行整体一致性作为后步骤。然而，由于亲和度信息完全丢弃在一致性执行过程中，这些方法遭受的敏感性的质量推定的匹配作为初始化。在[42]中，一阶亲和度与一致性约束一起使用，以提高对真实图像的鲁棒性。然而，高阶信息被忽略。4Tianshu Yu，Junchi Yan，Wei Liu，Baoxin Li基于上述两种方法，作者在[12]中提出了一个公式，其中图之间的亲和度由图的向量化属性堆叠的矩阵编码，并且变量被减少到一组固有的在[13]中，提出了一种基于张量表示的多图匹配方法。然而，所有上述工作都忽略了一个重要的设置，即图形以顺序的方式到达，并且需要在线匹配。事实上，在线或增量匹配的图的问题是不平凡的，现有的方法可能不容易推广到处理这个新的问题。据我们所知，这是第一个明确地解决，ING在网上的方式，从而提出了一个增量匹配技术的图匹配问题的作品之一。实验结果表明，我们的求解器可以显着优于传统的多图匹配方法。3预赛我们考虑一对一双射匹配的情况该设置具有其技术考虑，因为循环一致性约束要求图的大小相同。虽然大多数现有的多图匹配方法采用这种设置[25，11，39，42，14]，但可以通过引入虚拟节点或松弛变量来处理不平衡的图大小，如[18]中所述在双射的情况下，图Gi和Gj之间的匹配可以在rixXij∈{0，1}n×n的i上进行，其中n是每个图中的顶点数。给定亲和矩阵Kij∈ Rn2×n2- 分别在对角线和非对角线上编码顶点和边相似性对于Kij（参见现有技术[6]中对Kij的更详细的定义），由Gij和Gij组成的匹配目标可以被定义为：maxEij = xT Kij xijxij第二章（一）S.T. Hxij = 1， xij∈{ 0， 1}n其中x ij= vec（X ij）是X ij的列向量化形式。 H是强制匹配为一对一的选择矩阵。由于组合性质，获得Eij的最优解通常是NP困难的，并且它是通常通过替换约束xij而放松到连续域{0， 1}n2xij∈[0，1] n2的有效和近似优化[27，31，18]。除了两图匹配之外，多图匹配最近获得了前tensiveat ten tion，其中有一部分可以通过Σmathing轻松找到在所有给定的图之间，以最大化总体亲和度得分E=i，jEi，j。一简单的方法是通过最大化每个Eij独立地。然而，这可能导致一个事实，即一个匹配解Xij与由替代路径导出的另一个解不一致：Xij= Xik Xkj。为了解决这个问题，提出了循环一致性[7]以将匹配结果约束为循环一致的，其强调了在Gi和Gj之间的任何两个匹配p都必须具有相似的分辨率。为了有效和简单，本文遵循了广泛使用的一阶相容性增量多图匹配5IJ在图Gk上，如在[6，7]中，其被定义为：Σ ΣCk=1−i j>i<$Xij−XikXkj<$F/2 （2）求实数（0，1）nN（N−1）/2其中N是图的个数，·F是指Frobenius范数。该等式测量直接匹配与经由中间图的另一匹配的一致程度。因此，所有图的总体一致性变为：1ΣC=NCk（3）K通过将C作为正则化器添加到亲和度得分，具有一致性正则化的多图匹配产生优化：Emgm=λE+（1−λ）C（ 4）其中λ是控制参数。由于该目标与使用解析或基于梯度的方法优化的目标显著不同，在[7]中引入了Emgm上的启发式多图匹配方法，其中前一次迭代中的匹配被两个置换的乘积代替。路径X ′上的矩阵 = X ik X kj，如果Emgm上升。其有效性和为了提高效率，我们在我们的方法中采用了这种策略。作为离线多图匹配的扩展，增量多图匹配尝试在已经计算N个图的先前匹配时匹配第N+1个到达的图当一个或几个新的图到达时，期望可以重用先前的匹配结果一种简单的方法是将N个图的前一个解作为迭代更新的起点，无论使用现有的多图匹配方法，期望从N个图获得的结果可以作为比随机猜测更好的初始化，并加速收敛。然而，每次新的图到达时，仍然必须计算所有N+1个匹配Xij4该方法4.1超图拓扑在深入讨论细节之前，值得在这里提及一些定义。超图G由多个图和它们之间的成对匹配组成在数学上，超图被定义为（也在图1中绘出）：G={{G1，… GN}，{Mij}}，i，j∈ {1，.，N} i = j（5）其中Mi j是Gii和Gj 之 间 的 最 小 值。对于通常的描述，其是覆盖相应结构的复合物。给定索引子集u{1，…，N}，我们将索引重新编号为u ={11，...，lk}。那么一个子超图Gu包含k个图的子集及其由指标集u诱导的匹配：Gu=. {G11，… Glk}，{Mlilj}Σ，li，lj∈ u，lii =lj（6）6Tianshu Yu，Junchi Yan，Wei Liu，Baoxin Li到达图复盖复合体集群相交图图1：具有花瓣形拓扑的超图及其覆盖复形。有10个现有图和一个到达图。 注意：i）在迭代中，图被重新聚类成由相交图重叠的k个分区;ii）在每次迭代时，从不一定是新图的所有图中重新选择相交图; iii）在给定的聚类数（这里k = 3）下，通过随机性和多样性的标准对分区进行聚类。根据超图G的拓扑结构，计算每对图之间的匹配。由于这样的匹配的量与图的数量是组合的，因此它可能是计算密集型的。然而，如果我们能够减少超图的大小这一事实激发了将超图划分为若干子超图，对每个子超图进行优化并合并所有匹配结果的思想。图1展示了我们的方法的一般视图我们将在下面的章节中详细介绍该算法并给出直观的4.2算法详情如算法1中所示，一种被称为经由基于随机性和多样性的图聚类的增量多图匹配（Incremental Multi-Graph Matching，缩写为Multi-Graph）的方法。IMGM）提出。通常，该方法包括i）相交图选择和排除; ii）在没有相交图的情况下基于随机性和多样性的图聚类;iii）沿着相交图的匹配传播这些步骤迭代地执行并且在图1中示出。1) 选择子超图共享的交集图。在每个子超图内应用多图匹配不能保证全局循环一致性，因为不同子超图之间没有链接，这也限制了跨所有图的全局信息的有效使用为了建立子超图之间的连接，我们采用[6，7]中的标准，通过根据等式（2）最大化一致性得分来选择交集图Gv（参见图1中的图示因此，通过将参考图视为属于每个子超图，参考图超图的结果拓扑是花瓣形的，如图1所示（注意，结果簇彼此重叠增量多图匹配7算法1通过基于随机性和多样性的图聚类（IMGM）的1：函数IMGM（S，G，N）S-相似度，G-超图，GN-新图2：对于每个新图GN：do3：G=G∪{GN}4：通过基于更新的X最大化等式（2）来找到相交图v5：基于更新的X6：使用基于S的k-DPP将G | v划分成d个簇，或者随机划分7：对于u = l，. . . ，d do8：生成由第u个簇诱导的子超图Gu9：Gu=Gu∪{Gv}10：使用Gu，u = l，…U11：应用CAOPC（或其他多图匹配求解器）以获得Xu12：结束13：对于i∈Iu1，j∈Iu2，i，ji=vdo14：Xij = Xiv Xvj构造通过新图的长度为2的路 15：X=∪Xu∪{Xij}16：结束17：结束18：返回X19：结束功能通过交叉图）。因此，为了获得用于多图匹配的圈一致超图G，仅需要考虑每个子超图内的圈一致性约束。2) 基于随机性和多样性的子超图聚类。 我们专注于两个理想的属性分区/聚类超图在我们的设置：多样性（迭代）和随机性（迭代）。我们首先将一般思想描述如下：对于第一个属性，传统的聚类方法将数据划分为几个集合，以聚合相似的对象并分离不相似的对象。然而，这种策略并不适合我们的情况，直观的想法是，很难通过交集图来匹配来自两个聚类的两个不相似图。因此，我们采取的政策，鼓励多样性在每个簇，并希望每个簇是代表整个超图。另一方面，第二个属性强调分区在迭代中的相对如果分区在每次迭代时是固定的，则优化可能落入局部最优并且具有较少的机会逃脱。从这个意义上说，匹配解决方案将在早期迭代中收敛，而不会随着图序列一起演化。为了引入随机性，我们期望分区在迭代之间可以在一定程度上改变，使得启发式过程可以探索更多的解空间。基于上述观察，我们介绍了两种在迭代时和迭代期间划分的具体方法：随机采样和行列式点过程（DPP）[43]。由于随机抽样是微不足道的，我们在下面解释更多关于民进党的parti- tioningDPP采样依赖于计算的相似性Sij，8Tianshu Yu，Junchi Yan，Wei Liu，Baoxin Li0.1 0.10.08 0.080.06 0.060.04 0.040.02 0.020 0-0.02-0.02-0.04-0.04-0.06-0.06-0.08-0.08-0.10.05 - 0.05 0.05 0.10.15(a) 谱聚类划分-0.10.05 - 0.05 0.05 0.1 0.15(b) k-DPP分割图2：在40个图上使用具有相似性的谱聚类（左）和具有多样性的所提出的DPP过程（右）的划分结果。通过多维标度[45]将图形正方形标记是每个簇的质心。任何一对图i和j。为此，我们首先引入最优能量Sij=Eij作为i=j时的测量。 对于i = j，我们令Sii= 1。1×maxi，j，ijEij有着巨大的潜力。 新函数Sij=Sij−mini，j，i=/jEij。F或Ngaphs对于d个分区，我们首先通过使用N/d并对其进行适当的舍入来计算每个分区的大小。然后，我们应用d次k-DPP [44]来获得分割。有关k-DPP的更多详细信息，请参阅[44]。我们在图2中可视化了这样的划分策略。该示例包含40个图形，并且通过多维缩放[45]获得2-D点正方形框对应于每个聚类质心。可以看到左侧面板中的质心比右侧面板中的质心更分散。左侧面板中的集群内的点彼此更接近，而右侧面板中的分区内的点尽可能地跨越整个空间。备注人们可能会争论采用基于相异度的光谱聚类，其也可以在每个聚类中生成散射点。然而，这种方法是确定性的，导致每次迭代中的分区冻结。另一种替代方案是使用随机采样来形成每个聚类，而缺点是不能有效地确保每个聚类中的多样性。事实上，DPP由于其固有的随机性质，可以确保每次迭代时每个聚类中的多样性以及迭代的随机性。3) 沿着交叉点传播匹配。具体地，对于具有图样本索引集Iu的每个聚类u，通过将参考图视为形成花瓣形拓扑的相交图，我们定义了用于增量匹配的新Einc= ΣUu=1Σi，j∈IuλEij+（1−λ）Cu（7）增量多图匹配9XIJ事实上，我们可以应用现有的多图匹配算法，例如。该方法被称为具有成对一致性的组合亲和力优化（CAOPC）。[7]在每个子超图上独立地优化该得分函数。然后我们可以得到一个全连通子超图，在这个意义上，每对图都是在子超图中的。在严格意义上，对于从不同的子超图中生成的G_i和G_j没有直接联系，我们用交图G_k作为中间结点，生成一个长度为2的匹配X_ij =X_ik X_kj，使G_i和G_j的长度为2。i∈Iu，j∈/Iu.对于等式（7）的最优选择，记录如下：ithtΣhege n-通过交叉图的有界匹配，用X=*表示，其中也可以用作匹配下一个新图形的起点图1展示了我们的算法生成的拓扑结构。每个实心圆对应于分区，而优化在每个虚线椭圆内进行。在每个虚线椭圆中，我们密集地计算每对图的匹配与一致性正则化。4.3进一步讨论复杂度CAOPC的复杂度为O（N3n3+N2τpair），其中N和n分别是图的个数和顶点数.τ对是指所选图匹配求解器的复杂度。在k-DPP采样中，涉及特征分解和投影过程，其复杂性分别为O（N3）和O（N2如果超图被聚类为d个分区，并且w.l.g. 在每个分区的大小相等的情况下，IMGM的CAO-PC步的复杂度为O （N3n3/d2+N2τ 对）.在这种情况下，k-DPP划分的复杂度是O（N3/d2）。 很容易看出，聚类和覆盖拓扑可以显著降低复杂度。 在一般情况下，所提出的算法的复杂度为O（N3n3/d2+N2τpair+N3/d2）.拓扑解释[14]中讨论了离线多图匹配的复杂概念，作者证明了在下列条件下超图G是圈一致的：1）每个子超图（不包括G本身）都是圈一致的; 2）每对子超图都是联合法线; 3）超图的复盖复形是拓扑单连通的。虽然这些陈述中的假设是理想的，但它仍然提供了显示我们的算法为什么有效的提示。由于所提出的拓扑结构保证，一旦达到了在每个分区的周期一致性，整体的周期一致性来自相交图将得到相应的满足。此外，我们提供了一个明确的策略，如何构建这样的拓扑结构，这是没有涵盖在[14]。首先，我们观察到所提出的方法的拓扑结构可以被视为[6]和[7]的广义版本如果分区的大小另一方面，如果只有一个分区，我们的方法退化为[7]。从这个意义上说，我们的拓扑利用了前两种结构，因此可以达到10Tianshu Yu，Junchi Yan，Wei Liu，Baoxin LiIJABABAB2在准确性和效率之间取得了很好的平衡。此外，也可以提出满足先前段落中陈述的三个条件的线或圆结构）。我们把这些变化留给未来的工作。5实验绩效评估标准我们采用三种常用的衡量标准[6，7]评估算法的性能：准确性，亲和力Σ得分和一致性（分别缩写为acc、scr和con）。acc =1−i、jXXGT2/nN2∈[0， 1]是指通过比较解X*的匹配精度ij FΣvec（X*）TKIJvec（X*）到X GT的地面实况匹配scr =1ijijij ij计算ijN2i，jvec（XGT）TKijvec（XGT）ij ij总体亲和力得分。con =C参考等式3。注意scr可以在上面1比较方法和设置由于几乎没有以增量方式的现有多图匹配算法，我们通过扩展[7]中的CAOPC算法和[6]中的一致性匹配算法来设计两个基线。为此，我们重新使用先前迭代中的匹配结果X作为起始点，并且将到达的图GN并入当前迭代中以用于另一轮基于批处理的多图匹配。我们将这两个基线称为增量CAO和增量ConMatch。我们还采用原始CAOPC从头开始计算匹配，而不使用以前的结果。每突变同步（mSync）[39]，其处理匹配以实现循环一致性，也用于比较。所提出的算法e-equiped与DPP和随机采样的图聚类迭代，被称为IMGM-D和IMGM-R，分别。所有初始成对匹配都是使用重新加权随机游走[18]获得的，这已被证明是一种有效且稳定的两图匹配求解器。5.1关于合成随机图我们遵循[7，9]来实现对合成数据的测试，其中成对的亲和力分数是用高斯变形扰动随机生成的。对于每个试验，通过分配一个节点计数nR = 10来创建具有节点计数n R重量qR对于从[0， 1]均匀采样的边缘（a，b）然后是高斯噪声µ N（0，）被添加为qD= qR+ µ以生成目标图。的根据密度参数ρ调整图的边密度。边缘亲和力因此通过Kac计算;bd=exp（-（qab−qcd）σ2）.我们测试不同的COM-基图NB和到达图NA 的数目的组合。对这类组合进行了三次设置：（NB，NA）∈ {（25， 15），（30， 20），（35， 25）}。在所有测试中，我们保持将超图划分为2个子超图（如果不是另有规定），每次试验50次，计算平均值增量多图匹配110.750.70.650.60.550.50.450.4精度1.151.11.0510.950.9亲和度分值10.90.80.70.60.50.4一致性时间（s）76543210.350.850.80.750.70.650.60.550.50.450.4123456789 10 1112131415到达图精度0.851.151.11.0510.950.9123456789 101112131415到达图亲和度分值0.310.90.80.70.60.50.41234567891011121314 15到达图一致性0123456789101112131415到达图时间（s）2520151050.350.80.750.70.650.60.550.50.450.40.351 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20到达图精度0.851.151.11.0510.950.91 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20到达图亲和度分值0.310.90.80.70.60.50.4123456789 10 11 12 13 14 15 16 17 18 19 20到达图一致性01 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20到达图时间（s）4035302520151050.30.850.80.750.70.650.60.550.50.450.40.351 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25到达图精度DPP ， 第2组DPP ， 第3组DPP ， 第4组Rnd， 第2组Rnd， 第3组Rnd， 第4组12345678 9 10 11 12 13 14 15 16 17 18 19 20到达图0.851.061.041.0210.980.960.940.920.91 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25到达图亲和度分值DPP ， 第2组DPP ， 第 3组Rnd， 第2组Rnd， 第3组Rnd， 第4组12345678 9 10 11 12 13 14 15 16 17 18 19 20到达图0.30.90.850.80.750.70.650.60.550.50.450.41 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25到达图一致性DPP ， 第2组DPP ， 第3组Rnd， 第 2组Rnd， 第 3组Rnd， 第 4组1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20到达图01 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25到达图时间（s）7654321012345678 910 11 12 13 14 15 16 17 18 19 20到达图图3：关于合成数据的性能w.r.t.累计到达图形计数。从上到下的基本图形编号：25 30 35 30性能我们设ρ = 0。9，θ = 0。15和σ2 = 0。05.测试结果显示在图3的前三行为了评估不同分区大小d的影响，我们利用（NB，NA）=（30，20）进行附加测试，其中d∈{2， 3， 4}。该试验由100次独立试验组成。该附加测试的结果显示在图3的最后一行中，其中DPP和Rnd分别对应于顶GM-D和顶GM-R。可以看出，当基图的大小为25时，我们的算法在精度上优于原始CAO，并且非常接近增量CAO。当大小增加到30时，当更多图到达时，IMGM优于增量CAO。在任一情况下，原始CAO、增量ConMatch和 mSync 具 有 低 得 多 的 准 确 性 。 当 有35 个 基 本 图 时 ， IMGM-D 和IMGM-R都显著优于所有其他算法，实现了最先进的性能。此外，IMGM-D具有更稳定的准确度增长以及到达图。我们还可以观察到，我们的算法达到更好的全局一致性比基于CAO的方法。这是由于跨子超图的匹配经由中间图生成的事实，因此具有较高的一致性得分。需要注意的是，增量匹配的匹配精度粗CAO增量CAOIMGM-DIMGM-R增量ConMatchmSync基本图= 25节点计数= 10基本图= 25节点计数= 10粗CAO增量CAOIMGM-DIMGM-R增量ConMatchmSync基本图= 25节点计数= 10粗CAO增量CAOIMGM-DIMGM-R增量ConMatchmSync基本图= 25节点计数= 10原始CAO增量CAO IMGM-DIMGM-R增量ConMatchmSync基本图形= 30节点计数= 10粗CAO增量CAOIMGM-DIMGM-R增量ConMatchmSync基本图= 30节点计数= 10粗CAO增量CAOIMGM-DIMGM-R增量ConMatchmSync基本图= 30节点计数= 10粗CAO增量CAOIMGM-DIMGM-R增量ConMatchmSync原始CAO增量CAO IMGM-DIMGM-R增量ConMatchmSync基本图= 30节点计数= 10基本图形= 35节点计数= 10粗CAO增 量CAO IMGM -DIM GM -R增 量ConM atch mSync基本图形= 35节点计数= 10粗CAO增 量CAO IM GM -DIM GM -R增 量ConM atch mSync基本图= 35粗 CAO增 量 CAO IM GM -DIM GM -R增 量ConM atch mSync节点计数= 10基本图形= 35节点计数= 10粗CAO增量CAOIMGM-DIMGM-R增量ConMatchmSync精度DPP，第2DPP，第3组Rnd，第2Rnd，第3Rnd，第4精度精度精度亲和度分值亲和度分值亲和度分值亲和度分值一致性一致性一致性一致性时间（s）时间（s）时间（s）时间（s）12Tianshu Yu，Junchi Yan，Wei Liu，Baoxin Li0.750.70.650.60.550.50.450.4精度原始CAO增量CAO IMGM-DIMGM-R增量ConMatchmSync1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20到达图1.21.151.11.0510.950.9亲和度分值原始CAO增量CAO IMGM-DIMGM-R增量ConMatchmSync1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20到达图10.90.80.70.60.50.4一致性原始CAO增量CAOIMGM-DIMGM-R增量ConMatchmSync123456789 10 11 12 13 14 15 16 17 18 19 20到达图时间（s）25201510501 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20到达图(a) 在CMU酒店0.690.680.670.660.650.640.630.620.610.6精度原始CAO增量CAO IMGM-DIMGM-R增量ConMatchmSync1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20到达图1.221.21.181.161.141.121.1亲和度分值原始CAO增量CAO IMGM-DIMGM-R增量ConMatchmSync1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20到达图10.950.90.850.80.750.70.650.60.55一致性原始CAO增量CAO IMGM-DIMGM-R增量ConMatchmSync1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20到达图时间（s）25201510501 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20到达图(b) 在CMU房屋图4：关于CMU序列的性能累计到达图形计数。ConMatch随着图形序列而减小这是因为该算法的拓扑结构不会随着到达图而演变（总是只有一个簇），因此迭代之间缺少随机性值得注意的是，我们还观察到约3至4倍的加速相比，CAO算法。从底行可以观察到，较大的集群大小d通常加速计算并增强一致性。然而，较大的d导致准确度下降因此，我们需要在精度和由d控制的效率之间找到一个折衷（参见第2节的复杂度分析）4.3）。最后但并非最不重要的是，我们还观察到IMGM-D通常可以比IMGM-R更快地收敛，这补偿了执行DPP的额外开销。5.2在真实图像上：CMU序列CMU姿态数据集1由两个图像序列组成。一个是CMU房子，有111个框架和30个地标，另一个是CMU酒店，有101个框架和30个地标。每个序列包含一个逐渐改变其位置的对象该数据集在[18，42，7]中进行了广泛测试我们使用该数据集来评估部分相似性和离群节点下的性能为此，我们遵循[7]中的设置，在每帧中选择10个内点，并从每帧中的剩余地标中随机选择4个点，使匹配更具挑战性。按照[7]中的方法，在内部值和外部值亲和力生成由Kac;bd =exp（−（qab−qcd）σ2），其中qab测量欧几里得距离通过除以最大边长度，将点a和点b之间的值归一化为[0， 1]的1http://vasc.ri.cmu.edu/idb/html/motion/精度亲和度分值精度一致性亲和度分值时间（s）一致性时间（s）2原始CAO增量CAOIMGM-DIMGM-R增量ConMatchmSync原始CAO增量CAOIMGM-DIMGM-R增量ConMatchmSync增量多图匹配13活性炭活性炭活性炭与节点相似性相对应的亲和度的对角元素被设置为0作为先前的测试。对于每个轨迹，我们随机采样NB= 30个帧作为基本图，然后从剩余帧中随机采样NA我们进行了20次单次试验，并计算了平均性能。令〇2 = 0。05.性能曲线如图4所示。在酒店序列上，IMGM-D方法取得了显着的精度优于其他比较算法。在房屋序列测试中，IMGM-D的表现与最先进的算法相比具有竞争力。虽然界标的相对位置的变化在图中并不严重，但是离群点阻碍了匹配算法，因为干扰边缘可能与离群点一起出现稳定的性能证明了所提出的算法，特别是IMGM-D，对离群值的鲁棒性。该算法显示出类似的行为，在合成测试的指标，而不是准确性。因此，我们只在下一个Willow-ObjectClass数据测试中提供准确性。5.3在真实图像上：Willow-ObjectClassWillow-ObjectClass数据集在[5]中收集并发布，其中包括从Caltech-256和PASCAL 07收集的5类图像：109张人脸，66张酒瓶，50张鸭子，40张汽车和40张摩托车图像。所有图像均取自自然场景。对于每个图像，手动标记对应对象上的10个界标点。我们选择Winebottle、Duck和Car进行实验，分裂（NB，NA）分别为（30，20）、（30，20）和（25，15）。对于Winebottle（或称Bottle），作为NB+NA66，我们遵循之前测试中的设置，每次试验随机抽取50张图像。<对于其余两个对象，我们随机排列所有图像。随机选择背景上的4个SIFT特征点作为离群值。我们仍然采用稀疏Delaunay三角剖分来构造邻接图。然后计算亲和力作为Kac;bd=βKlen+（1−β）Kang同时考虑边缘长度和角相似性，其中β∈[0，1]是控制参数。虽然定义透镜活性炭与CMU序列测试所用的相同措施不同-边缘（a，b）和（c，d）之间的绝对角度的存在对角元素的所有元素都像以前一样设置为0。β = 0。9在这次测试中我们进行了20次独立试验，平均准确度见图5。当Winebottle和Duck测试中有更多的基图时，IMGM-D在大多数到达图上优于所选择的对应物。另一方面，在具有较少基图的Car测试中，所提出的方法随着到达图而逐渐适应问题，并且达到竞争性能。5.4讨论我们观察到，所提出的方法优于所有的同行算法时，图的大小是足够大的。这可能是由于以下两个原因。一方面，子超图的多样性必须能充分地表示整个图空间，但当图的个数太少时，多样性很难得到满足。另一方面，分区过程能够的K14Tianshu Yu，Junchi Yan，Wei Liu，Baoxin Li精度10.75精度0.85精度0.950.90.850.80.750.70.650.60.70.650.60.550.50.450.40.350.80.750.70.650.60.550.50.450.40.551 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20到达图0.31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20到达图0.351234567891011121314 15到达图(a)瓶子（30个基本图）（b）鸭子（30个基本图）（c）汽车（25个基本图）图5：从Willow-ObjectClass数据集匹配对象的准确性通过“输出”组来恢复在子组优化中的不可靠性，如果采用整批优化，则该不可靠性可以传播到所有匹配结果。我们还观察到，由于[7]中的算法适用于置换矩阵，如果分区沿时间稳定，则每个子超图内的一段时间后的匹配解可能落入置换子组中，并且不会进一步演化。相反，通过在partitions中施加随机性，我们的算法可以摆脱糟糕的局部最优。最后但并非最不重要的是，我们观察到IMGM-D在我们的合成测试中表现接近IMGM-R，并且在所有真实世界图像测试中表现优于IMGM-R。我们推测这是由于对于合成数据，它们是基于共享的碱基结构（具有额外的轻微噪声）生成的。然而，自然图像数据在其图形结构中具有更复杂的分布，这可以通过基于多样性的聚类来更好地捕获。6结论本文提出了一种增量式多图匹配方法IMGM，该方法以先前的匹配和到达的图作为输入，在一个圈一致的拓扑结构上进行优化。据我们所知，这是第一次尝试解决图匹配增量。我们还分析了超图的功能拓扑结构，解释了增量设置中多样性和随机性的必要性该方法减少了计算开销，在图数足够的情况下提高了匹配精度。我们的范例是灵活的，允许采用其他多图匹配方法作为插件。确认这项工作得到了ONR的部分资助本材料中表达的任何观点均为作者的观点，不一定反映ONR的观点。严俊驰获得腾讯人工智能实验室犀牛鸟联合研究计划（编号：JR201804）和NSFC 61602176。#离群值= 4原始CAO增量CAOIMGM-DIMGM-R增量ConMatchmSync原始CAO增量CAOIMGM-DIMGM-R增量ConMatchmSync#离群值= 4原始CAO增量CAOIMGM-DIMGM-