1利用Birkhoff多面体TolgaBirdal1，2UmutSims ekli31计算机科学系，斯坦福大学，CA 94305斯坦福，美国2Fakultaüt fürInformatik，TechnischeUni versitaütMünchen，85748München，German y3LTCI，Te′ le′ comParisTech，Univ ersite′Paris-Saclay，75013Paris，France摘要我们提出了一个全新的几何和概率的方法来同步多组对象或图像之间的对应关系。特别是，我们提出了两个算法：（1）Birkhoff-Riemannian L-BFGS用于以原则性的方式优化组合不可处理的循环一致性损失的松弛 版 本 ， （ 2 ） Birkhoff-Riemannian Langevin MonteCarlo用于在Birkhoff多面体上生成样本并估计所找到的解的置信度。为此，我们首先介绍了最近发展的黎曼几何的Birkhoff多面体。接下来，我们引入一个新的概率同步模型的马尔可夫随机场（MRF）的形式。最后，基于一阶收缩算子，我们将问题转化为随机微分方程的模拟我们在合成数据集和真实数据集上表明，我们实现了高质量的多图匹配结果，具有更快的收敛速度和可靠的置信度/不确定性估计。1. 介绍对应关系为各种计算机视觉应用提供了动力，例如运动恢 复结构（ SfM ）[62]、SLAM [53]、3D重建[20，8，6]、相机重新定位[60]、图像检索[44]和3D扫描拼接[38，22]。在典型场景中，给定两个场景，首先识别2D/3D关键点的初始集合。然后，每个关键点的邻域用局部描述符[47，23]进行总结，并通过关联相互最接近的描述符来匹配给定场景中的关键点。在大多数实际应用中，考虑多个图像或3D形状，并且确定这样的两视图或成对的对应性根本是不够的。这需要进一步完善，确保全球一致性。不幸的是，在这个阶段，即使是很好地定义的管道也默许了启发式/贪婪的改进[21]，或者将与将各个对应性估计链接到图1.我们的算法鲁棒地解决了多路图像匹配问题（a，b），并提供了置信图（c），这对进一步提高估计值（d）有很大帮助。右边的条用于为置信度分配颜色。对于其他人，不正确的匹配用红色标记，正确的用蓝色标记。全球一致的整体[30，62，73]。在本文中，通过使用的事实，对应关系是周期一致的1，我们提出了两种新的算法，用于细化分配在多路图中的多个图像/扫描（节点）和估计分配的置信度，分别。我们将图像对之间的对应关系建模为相对的总置换矩阵，并试图找到将检测到的关键点重新排列为单个规范的全局顺序的绝对置换。这个问题被称为映射或置换同步[56，70]。尽管在许多实际场景中，匹配仅部分可用，但当形状完整且匹配密度增加时，总置换就足够了[36]。类似于许多广受好评的作品[84，61]，我们将所寻求的置换重新放宽到双随机（DS）矩阵的集合。然后我们考虑DS的几何结构，Birkhoff多面体[9]。据我们所知，我们第一次引入并应用了最近发展的Birkhoff多面体的黎曼几何[26]来解决计算机视觉的挑战性问题。请注意，缺乏这种几何理解造成了大量的障碍，学者处理我们的问题[61，77]。由于一阶收缩，我们1任何循环路径的对应组合返回到起始节点。11105（a）（b）解决（c）信任/信心（d）多重假设解决方案1前N位前2名011106×可以使用最近的黎曼有限记忆BFGS（LR-BFGS）算法[82]来执行一致性损失的参数的最大后验（MAP）估计我们将我们的变体命名为Birkhoff-LRBFGS。在下一个阶段，我们采取的挑战，置信度/不确定性估计的问题，通过绘制样本的Birkhoff多面体和估计的经验后验分布。为了实现这一点，我们首先制定了一个新的测地随机微分方程（ESTA）。我们的方法基于黎曼朗之万蒙特卡罗（RLMC）[31，78，58]，该方法在从具有真指数映射的黎曼流形采样时是有效的。请注意，类似的随机梯度测地线MCMC（SG-MCMC）[46，11]工具已经用于空间刚性变换同步的背景下，其参数允许解析定义的测地线流[7]。不幸的是，对于我们的流形，收缩映射只到一阶，因此我们不能使用现成的方案。为了减轻这种麻烦，我们进一步贡献了一种新的数值积分器，通过用近似收缩映射代替DS矩阵的难处理指数映射来解决我们的问题。这导致了另一种新的算法：Birkhoff-RLMC。简而言之，我们的贡献是：1. 我们作为大使，引入Birkhoff多面体的黎曼几何[26]来解决计算机视觉中的问题。2. 我们提出了一个新的概率模型的置换同步问题。3. 我们通过黎曼LBFGS算法最大限度地减少了周期一致性损失，并在召回率和运行时间方面都超过了最先进的水平。4. 基于Langevin力学，我们引入了一个新的积分器和一个数值积分器，用于在高维复流形上绘制具有近似收缩的样本，如Birkhoff多面体. 这使我们能够估计置信度图，这可以帮助改进解决方案并发现一致性违规或离群值。请注意，本文开发的工具可以很容易地扩展到我们的应用程序之外，并有望促进有关计算机视觉中组合优化问题的有前途的研究方向。2. 相关工作置换同步是一个新兴的研究领域，由于其广泛的适用性，特别是在计算机视觉问题。我们现在尽可能按时间顺序回顾这一领域的发展注意，涉及空间几何的多路图匹配问题公式也得到了很好的研究[18，50，43，29，79，19]。作为转换同步[76，13，72，75，3，4，33]。为了简洁起见，我们省略了这些文献，并专注于显式操作对应矩阵的作品同步（Singer [67，66]创造的术语）在通信中的首次应用可以追溯到2010年代初[54]。Pachauri等人[56]给出了一个正式的定义，并设计了一种光谱技术。同样的作者很快将他们的工作扩展到置换扩散图[55]，寻找图像之间的对应关系。不幸的是，第一种方法在图像数量上是二次的，因此在计算上不友好。在MatchLift的续篇中，Huang、Chen和Guibas [36，15]首次将估计循环一致映射的问题转化为寻找与输入矩阵最接近的正半定矩阵。他们还讨论了部分排列的情况。由于涉及到半定规划（SDP）问题，该方法在实际应用中存在计算量大的问题.类似于Pachauri [56]，对于N个图像和M个边缘，该方法需要计算NM NM矩阵的特征分解。Zhou等[85]然后介绍了MatchALS，一种新的低秩公式与核范数松弛，全局解决一组图像的联合匹配，而不需要SDP。Yu等人[81]构造了一个类似于我们方法的同步能量，并提出了求解松弛问题的近似Gauss-Seidel方法然而，与我们不同的是，本文没有使用几何的约束或变量，从而诉诸复杂的优化程序，涉及弗兰克-沃尔夫子问题的全球约束满意度。阿尔-里戈尼等。[2]和Masetet al. [2]扩展Pachauri [56]，使用谱分解对部分排列进行操作。为此，他们考虑了部分匹配的对称逆半群，这通常很难处理。他们的封闭形式的方法不需要初始化步骤同步，但也没有建立一个明确的循环一致性。Tang等人[71]选择使用改进Pachauri的排序算法[56]。Cosmo等人[19]为估计多个3D形状之间的一致对应关系的问题带来了一个有趣的解决方案Schiavinato和Torsello [61]试图通过将任何图匹配问题转化为多图匹配问题来克服Birkhoff多面体缺乏群结构的问题。Bernard等人[5]使用基于NMF的方法来生成周期一致的同步。Park和Yoon [57]使用多层随机游走框架来解决多属性图的全局对应搜索问题从多层随机游动初始化出发，提出了一种迭代加权的鲁棒求 解 器 。 Hu 等 人 [35] 重 新 审 视 了 MatchLift ， 并 在ADMM的帮助下开发了一个可扩展的分布式解决方案，称为DMatch。他们将输入拆分成子集合的思想在温和的条件下仍然可以导致全局一致性，同时提高了效率。最后，Wanget al. [77]利用领域知识，加入图像坐标的几何一致性，11107n∈P∈O{}−J----∈ E <${}×{}E--DPDP我+11PJP ∈ DP低等级术语，以增加回忆。上述作品既没有考虑到概率单纯形Δθ���−1共同Birkhoff凸环的黎曼结构但是，他们也没有提供一个概率框架，这可以铺平道路的不确定性估计，同时解决优化问题。这就是我们在这项工作中提出的。3. 材料和技术背景定义1（置换矩阵）。置换矩阵被定义为稀疏的平方二进制矩阵，其中每列和每行仅包含单个真（1）值：正交超球面：伯克霍夫多面体置换矩阵������������=���TangentSpace切向空间������公共质心图2.我们考虑的几何学的简化（矩阵是矢量化的）说明：（i）DPN是凸的，（ii）DPN是严格包含在DPN中的. 在低维中，这种配置不存在，因为没有凸形只在角上接触到C-N。定理1（Birkhoff-von Neumann Theorem）。 这个骗局n×n所有置换矩阵的集合的凸凸壳是Pn：={P∈ {0，1}：P1n=1n，1nP=1}.（一）其中1n表示n维1向量。 每Pn并且存在一个潜在的非唯一θ使得任何DS矩阵都可以表示为k个置换矩阵的线性组合[9，39]：是全置换矩阵，Pij=1意味着元素i被映射到元素j。 置换矩阵是正交群nn=的唯一严格非负元素O：O<$O=I，m =n时Rn中m -标架Stiefel流形的一个特例.定义2（质心）。n个物体上所有排列的质心在Rn×n中定义为[59]：X=θ1P1+···+θkPk，θi>0 <$θ<$1k=1.（四）虽然找到最小值k被证明是NP-困难的[27]，但通过Marcus-Ree定理，我们知道存在一个可构造的分解，其中k（n−1）2+1。<定义6（Birkhoff多面体）。 多项模型-Cn=1P=n！Pi∈Pnn！（n−1）！1N1=n十一尺。nnn（二）DS矩阵的折叠与称为Birkhoff多胞形[9]是环境Rn × n 的一个（n 1）2维凸子流形，其中n！顶点：注意Cn∈/Pn，如Fi g所示。二、定义3（相对排列）。 我们定义一个置换矩阵是相对的，如果它是两个群元素（i→j）的比（或差）：Pij= PiPij。Bn.我们用DPn来表示Birkhoff多面体。有趣的是，这个凸多面体与n 在Cn，Cnn，并过参数化置换向量的凸包，置换面体[32]。Pn现在可以被认为是一个定义4（置换同步问题）。给定一组冗余的比率度量Pij：（i，j）1，. . .、N1、. . .，N，其中表示N个节点的有向图的边的集合，置换同步[56]可以用公式表示为恢复Pi的问题，i = 1，. - 是的- 是的，N，使得满足组一致性约束：Pij= PiP−1。如果输入数据被噪声破坏，则该一致性将不保持，并且为了恢复绝对排列Pi，某种形式的一致性误差被最小化。通常情况下，任何形式的最小化离散空间的置换是棘手的，这些矩阵是放松的双随机对应[10，84，61]（见图。2）。定义5（双随机（DS）矩阵）。DS矩阵是一个非负的正方形矩阵，其行和列之和为1。DS矩阵的集合被定义为：ΣnΣnDPn的正交子集：Pn={X∈ DPn：XX<$=I}，即置换矩阵的离散集是DS矩阵的凸集与On的交.3.1. Birkhoff多面体的黎曼几何最近，Douiket al. [26]赋予n以Fisher信息度量，从而得到n的黎曼流形。据我们所知，我们是第一个利用这个流形在计算机视觉领域，因此现在将回顾Douik等人的主要结果。[26]并总结了黎曼的主要结构DPn的优化 在[26]中可以找到证据。定义7（切空间和束）。切丛被称为所有切空间TDPn=<$X∈DPnTXDPn的并集，其中一个被定义为：TXDPn：={Z ∈ Rn×n：Z 1n= 0n，Z<$1n= 0n}.（五）定理2. 投影算子<$X（Y），Y ∈DPnDPn={X∈Rn×n：i=1xij =111108j=1xij=1}。（三）在X∈DPn的切空间上，TXDPn写为：<$X（Y）=Y−（α1<$+1β<$）<$X，其中（6）11109⊙i=1∈ DPDP∈ T DPPDPDP−DPP（n−1）n∈P∈EJ ∈ DPǁ· ǁ∈联系我们PP≥∈P.−2联系我们α= （ I−XX<$ ）+ （ Y−XY<$ ） 1 ，β=Y<$1−X<$α，+表示左伪逆和Hadamard乘积。请注意，存在一种数值上更稳定的方法来计算相同的简洁公式X（Y）[26]。定理3. 对于一个位于Xn的正切空间上的向量XXn，一阶收缩映射RX如下给出RX（<$X）=<$（X<$exp（<$X<$X）），（7）其中，算子表示到n上的投影，使用Sinkhorn算法有效地计算[68]，这是阿达玛师。Plis等人[59]证明了在n维Birkhoff多面体上，所有的排列都离质心Cn等距，因此DPn的极值点也是等距的，是置换矩阵，位于（n-1）-PPij（i，j）∈E和XXiN，分别是所有观测值和所有潜变量。建立概率模型的一种典型方法是首先为每个Xi选择n上的先验分布，然后在给定潜在变量的情况下为每个Xij选择n不幸的是，标准的参数分布既不存在于n上，也不存在于n上。变棒断裂[45]产生n上的隐式定义的PDF，并且不能提供对结果分布的直接控制。在置换矩 阵 上 定 义 基 于 Kantorovich 距 离 的 分 布 是 可 能 的[17]，但这些模型会产生很高的计算成本，因为它们需要在推理过程中解决最优运输问题由于这些原因，我们将直接对P和X的全联合分布建模，而不是构建分层概率模型。我们提出了一个概率模型，其中我们假设全联合分布具有以下因子分解形式：1Y维数h超球S（n−1）2的半径为<$n1，cen-在Cn。这个超球体是伯克霍夫号的附属物p（P，X）=Z（i，j）∈En（Pij，Xi，Xj），（8）顶点上的多面体其中Z表示归一化常数，1.提案 作为DPn和两者Σ∫Z：=Yn（Pij，Xi，Xj）dX，（9）2S和On随着n的增长而无穷大P∈P|E|DPNn（i，j）∈E证明在补充文件中给出。虽然存在多项式时间投影的n！- 元素置换空间上的连续超球面表示-而π被称为2）.（十）JF[59]《归去来兮》1、避免使用Hy-persphere松弛，在前面的作品[59，83]。4. 提出的概率模型我们假设我们被提供了一组成对的全排列Pij n（i，j），我们有兴趣找到潜在的绝对排列Xi这里F表示Frobenius范数，βR+是控制分布扩散的色散参数。请注意，该模型是马尔可夫随机场[40]。让我们更仔细地看一下所提出的模型。如果我们定义Xij：= XiXn，则由Thm. 1、我们有对于每个Xij，下面进行分解：对于i 1，. . .，N相对于共同原点（例如，X1=I，单位矩阵）。我们寻求绝对的排列，这将尊重基本的一致性Xij吉卜伊杰=θb=1ij，b摩洛哥b吉卜伊杰，θb=1ij，b=1，（11）图结构为了简洁起见，我们也限制我们的设置，丁全排列，并离开部分排列，生活在幺半群的扩展，作为未来的研究。因为直接在n上操作需要我们解决一个组合优化问题，其中，Bij是一个非线性整数，每个θij，b 0和Mij，bn. 下一个结果表明，我们有一个等价的对拟议模型的理论解释：第二个提案。Eq.中定义的概率模型。8包含以下层次分解：缺少歧管结构，n我们跟随流行方法[45，80，48]，并通过假设每个Xi∈ DPn来放松绝对置换的域。p（X）=1exp βCΣYXijZij（十二）211110我们用公式表示置换同步问题在概率的上下文中，我们处理成对关系，p（P（i，j）∈E1.一、|X，X）=exp（i，j）∈EΣ2β tr（PX）（十三）将有效排列作为观测随机变量，将绝对排列作为潜随机变量。特别是我们i j i jZijIJIJ概率构造使我们能够将同步其中C和Zij是归一化常数。此外，对于在模型中作为推论的nization问题。 以微弱所有i，j，ZijQBij≥b=1f（β，θij，b），其中f是正函数。在本文的其余部分中，我们将用符号a b来表示β和θij，b都增加的t。11111||F|IJǁǁ|DP|∝−nJF›→ DP∈Σ证明在补充中给出，并且基于简单分解p（P，X）=p（X）p（PX）。这种分层的观点让我们观察到一些有趣的性质：（1）li kp（PijXi，Xj）主要依赖于测量数据拟合度的项tr（PXi j）。 我们恰当地称这个项为P ij和X ij之间的“软汉明距离”，因为如果Xi，Xj是置换矩阵，则它将对应于两个置换之间的实际汉明距离[41]。 （2）另一方面，先验分布包含两个相互竞争的项：（i）项Zij为θij ， b ，它将把Xij推向Birkhoff多胞形的角，（ii）项Xi j2作为潜变量的正则化子，并将它们吸引到Birkhoff多胞形Cn的中心（参见图1）。Dfn. 2），这将在数值上有利于推理算法，将在下面的部分开发5. 推理算法我们现在可以将置换同步问题公式化为概率推理问题，其中我们将对以下量感兴趣：1. 最大后验概率（MAP）：X=arg max logp（X P）（14）X∈DPNnΣ黎曼有限内存BFGS（LR-BFGS）[37]，一种强大的优化技术，通过以有效的方式合并局部几何信息来实现更快的收敛速度这条额外的信息是通过逆Hessian的近似获得的，逆Hessian是在问题维度上以线性时间和空间复杂度对过去迭代的最新值进行计算的。我们在我们的supp中给出了更多关于LR-BFGS的细节材料算法的详细描述可以在[37，82]中找到。最后，我们通过匈牙利算法[52]将得到的近似解舍入为可行解，得到二元置换矩阵。5.2. 带收缩的黎曼Langevin Monte Carlo后验抽样在本节中，我们将通过借鉴[64，46，7]的思想，开发一种用于从后验分布p（X P）生成样本的一旦生成此类样本，我们将能够通过使用生成的样本来量化估计中的不确定性。Birkhoff流形的维数和复杂性使得在n或其乘积空间上生成样本非常具有挑战性，并且据我们所知，没有能够实现的黎曼MCMC算法其中log p（X|P）=+−βPij−XiX这一点。现有的黎曼MCMC算法并且=+表示直到加法常数的相等2. 完整的后验分布：p（X|P）n（P，X）.MAP估计通常更容易获得，并且在实践中很有用。另一方面，表征完整的poster-rior可以提供重要的附加信息，例如不确定性;然而，毫不奇怪，这是一项更困难的任务。除了与这些任务相关的通常困难之外，在我们的背景下，由于潜变量的非标准流形，我们还面临着额外的挑战。5.1.最大后验估计MAP估计问题可以被转换为DPn上的最小化问题，给出如下：[11，46]，能够在嵌入式的人身上提取样本Ifolds;然而，它们要求精确的指数图在分析上是可用的，在我们的情况下，最多只能通过收缩图来近似为此，我们开发了一个算法上更简单，但有效的算法。假设后验密度为 πH（X） ：=p（X P）exp（βU（X））关于Hausdorff测度。然后我们定义一个嵌入：RN（n−1）2N使得th a t <$（X<$）=X对于X<$RN（n−1）2。 根据面积公式（cf. Thm. [25]我们对于嵌入的后部，具有以下表达式密度πλ（相对于勒贝格测度）：.πH（x）=πλ（X）/|G（X）|，（15）X=arg min ，ΣU（X）：=、Pij−XiX其中G表示黎曼度量张量。X∈DPNn（i，j）∈EJF然后，我们考虑以下随机微分其中U被称为势能函数。我们观察到，色散参数的选择对MAP估计没有影响。虽然这个优化问题重新-方程（1），它是用于开发黎曼朗之万蒙特卡罗算法的1的略微修改[31，78，58]：集合常规的范数最小化，X存在于Birkhoff多面体的Carnival乘积中dX<$t=（−G−1<$X<$Uλ（X<$t）+Γt）dt+√2/βG−1dBt，这个问题非常复杂。由于在Birkhoff多面体上的收缩算子（cf.Thm. 3），我们可以使用几个黎曼运算-其中Bt表示标准布朗运动，称为校正项，其定义如下：[Γ（X<$）]=N（n−1）2<$[G−1（X<$）]/<$X<$。t ij=1tij j最优化算法[69]，而不采用基于投影的更新。在这项研究中，我们使用最近提出通过Thm。[49]的第1章，很容易证明解过程（X_t）t≥0等于嵌入后验分布（i，j）∈E11112×我我我F→ ∞ǁǁ图3.来自具有挑战性的Willow数据集的样本图像和手动注释的图像成对绘制（有多个），并以灰色显示，以便更好地查看。πλ不变非正式地说，这个结果意味着，如果我们可以模拟连续时间过程（Xt）t≥0，样本路径的分布将收敛到em。层后验分布πλ，因此，λ（Xλt）的分布应等于πH（X）. 然而，不可能精确地模拟这些路径，因此我们需要参考近似算法。一种可能的数值模拟方法是使用标准的离散化工具，如欧拉-丸山积分器[14]。然而，这将需要知道解析表达式，并在每次迭代中构造Gt和Γt另一方面，最近的研究结果表明，我们可以直接模拟随机微分方程通过使用测地线积分器[11，46，34]，完全绕过了这些问题。然而，这些方法要求流形的精确指数映射在分析上是可用的，限制了它们在我们的上下文中的应用。受最近流形优化算法[74]的启发，我们提出用Thm中给出的易处理的收缩算子代替测地线积分器中出现的精确的、难处理的指数映射3.我们发展了递归格式，我们将其称为收缩欧拉积分器：√6. 实验和评价6.1. 真实数据2D多图像匹配我们运行我们的方法在两个数据集CMU[12]和Willow Object Class [16]上执行多路图匹配。CMU是由房子和酒店对象下不断照明和平滑运动。初始成对对应关系以及地面实况（GT）绝对映射在数据集内提供。Willow数据集中的对象图像包括姿态，光照，实例和环境变化，如图所示。3、使朴素模板匹配不可行。对于我们的评估，我们遵循与Wang等人相同的设计。[77]见附件。首先，我们提取局部特征，一组227 227个补丁，以标注的地标为中心，使用在ImageNet [24]上预训练的繁荣的Alexnet [42]我们的描述符对应于锚定在手动注释关键点上的Conv4和Conv5层的特征映射响应然后，这些特征通过匈牙利算法[52]进行匹配，以获得初始成对置换矩阵P0。我们通过封闭形式MatchEIG [51]初始化我们的算法，并根据Spectral [56]，MatchALS [85]，MatchLift[36]，MatchEIG [51]和Wang等人的最新方法对其进行评估。[77]见附件。uni- verse的大小设置为每个图像的特征数我们假设这个数字是固定的，不存在部分匹配在使用Birkhoff结构的同时处理偏性是留给未来的工作。请注意，[77]使用与我们类似的成本函数，以初始化另外利用图像坐标几何作者也使用这个术语作为额外的信息位V（k+1）=1（h<$XU（X（k））+2h/βZ（k+1））（16）在其初始化期间。 标准评估指标，iX（k）ii i我在成对排列上定义为：X（k+1）=RX（k）我 （V（k+1）），n∈{1，. -是的-是的，N}（17）布吕 格恩1美元dˆ ˆ⊤其中h >0表示步长，k表示迭代，Z（k）表示Rn×n中的标准高斯随机变量，R（{Pi}|PGND）=的n|E|（i，j）∈EPij（18）ˆX（0）表示初始绝对排列。该方案的推导类似于[46]，我们在补充材料中提供了更详细的信息。据我们所知，用收缩算子近似的测地线积分器的收敛性质尚未得到分析。我们把这个分析作为将来的工作，这超出了本研究的范围。我们注意到，项Xij2在整个算法中起着重要的作用，因为它防止潜变量Xi去Birkhoff多面体的极值点，在那里收缩算子变得不准确。 我们还注意到，当β当分布πH集中在全局最优解X上时，所提出的收缩Euler积分器就变成了带收缩算子的黎曼梯度下降.其中Pij是GT相对变换，Pi是估计置换。在没有正确找到对应的情况下，R=0;对于完美解，R=1。选项卡. 1显示了不同算法以及我们的结果。请注意，我们的Birkhoff-LRBFGS方法只对成对排列进行操作，优于所有方法，即使是在初始化过程中使用几何的方法。此外，当我们的方法被用来初始化王等。[77]并进行几何优化，得到了最优结果。这些研究结果验证，行走的伯克霍夫多面体，甚至近似，并使用黎曼线搜索算法构成了一个有前途的方向，优化手头的问题。真实数据中的不确定性估计我们现在在 同 一 个Willow对象类上运行我们的置信度估计器[16]。我11113←←−∈∈|E||E|−表1.我们在WILLOW对象类图匹配数据集上的结果Wang−指的是没有几何一致性项的运行Wang [77]我们的方法的普通版本Ours已经缺少了这个项。我们的Geom然后指的是用我们的算法初始化Wang对于所有方法，我们使用作者的原始实现。[56][51][52][53][54][55][56][57][57][58][59][59][59][59]车0.480.550.650.690.660.720.711.001.00鸭0.430.590.560.590.560.630.670.9320.96脸0.860.920.940.930.930.950.951.001.00摩托车0.300.250.270.340.280.400.371.001.00酒瓶0.520.640.720.700.710.730.731.001.00CMU-House0.680.900.940.920.940.980.981.001.00CMU酒店0.640.810.870.860.920.940.961.001.00平均0.520.590.650.660.710.760.770.990.99要做到这一点，我们首先要找到同步的最佳点。 然后，我们设置h0。0001，β[0. 075，0。1]并自动开始围绕该模式对后验进行采样，迭代1000次。请注意，β是一个关键参数，也可以动态控制[7]。较大的β值不能为解决方案的良好多样性提供足够的变化。较小的值导致较大的随机扰动，导致样本远离最优值。这可能导致发散或样本无法解释局部模式。尽管如此，我们所有的测试在给定范围内的值都工作得很好所生成的样本在许多应用中是有用的，例如拟合分布或提供附加的解决方案提示。我们解决的情况下，多个假设生成的置换同步问题，并表明，生成一个额外的每边缘候选人具有高的确定性，有助于提高召回。选项卡.图2显示了我们通过简单地合并K个可能的样本而获得的前K个分数请注意，当随机抽取2个匹配并作为潜在的正确匹配时，召回率仅增加2%，而包含我们的样本反而将多路匹配提高了6%。表2.使用前K个误差按不确定性进行排名。基于置信度信息，我们可以保留多个假设。这是不可能的其他方法，如王等。[51，77]。Rand-K是指使用K−1个额外的随机假设来补充找到的解决方案。Ours-K通过我们的概率确定性对分配进行排名，并保留每个点的前K个候选项。数据集王我们 兰德-2我们的-2兰德-3我们的-3车0.720.710.730.760.760.81鸭0.630.670.670.690.670.72脸0.950.950.960.970.960.98摩托车0.400.370.450.490.520.60酒瓶0.730.740.770.820.790.85Avg.0.690.690.710.750.740.79我们进一步提出了说明性的结果，我们的信心预测图。4.在那里，通过分析不确定性，2[77]报告值为0。88，但对于他们的方法，我们达到0。93并因此报告该值。地图图中的列（e）描绘了置信图中保留的前2个最佳值，并且（e）绘制了与真实解重叠的赋值。请注意，我们可能无法在实际应用中访问这样的oracle，并且仅显示此以说明估计的置信度图的潜在用例。6.2. 合成数据的评价我们综合生成28个不同大小的问题：M[10，100]个节点，每个节点中有n[16，100]个点。对于图像匹配的场景，这将对应于每个图像中的M个相机和N个特征然后，我们引入15%-35%的随机交换GT绝对排列和计算观察到的相对的。该数据集的详细信息见附录。材料在所有28组合成数据中，我们获得了91%的总体重新调用，而MatchEIG [51]仍然约为83%。接下来，我们在上面解释的数据集上评估我们的算法与最先进方法的计算成本。我们所有的实验都在配备Intel i7 2.8GhZ CPU的MacBook计算机我们的实现使用修改后的Ceres求解器[1]。 所有其他算法都使用高度矢量化的MATLAB 2017 b代码，使我们的比较相当公平。图5表不同方法的运行时，不包括初始化。MatchLift轻松地花了20多对于中度问题，因此我们选择将其从该评估中排除。值得注意的是，由于使用更先进的求解器，如LBFGS的能力，我们的方法converges比王等快得多。与最快但最不精确的频谱同步[56]不相上下最坏情况下，算法的理论计算复杂度为OB-LRBFGS：=O（KKS（n2+（2n）3），其中K为LBFGS迭代次数，KS为Sinkhorn迭代次数.虽然KS可能是一个瓶颈，但实际上我们的矩阵已经限制在Birkhoff流形和Sinkhorn提前终止，让KS保持小。 其复杂度为：（1）与边缘数线性相关，最坏情况下与图像数成平方关系=N（N1），（2）与n成立方关系. 这是因为投影到11114(a) （b）解决方案图4.从我们的信心估计的结果。对于在（a）中初始化的问题，给定潜在错误的解决方案（b），我们的潜在样本发现了如中间三列（c-e）所示的不确定分配。当多个前2个解决方案被接受为潜在的积极因素时，我们的方法可以提出高质量的假设（f）。最后一列（f）中的边由其置信度值着色。请注意，尽管为了空间的缘故，我们显示了成对的图像，但数据集包含多组图像。切空间解2n×2n方程组7. 结论在这项工作中，我们提出了两个新的框架放松置换同步的双随机矩阵流形。我们的新模型和公式为使用复杂的优化器（如黎曼有限内存BFGS）铺平了道路我们进一步整合了300200100005 10 15 20 25问题复杂性流形-MCMC方案实现后验采样，从而进行置信度估计。我们已经表明，我们的置信图是关于周期不一致性的信息，并可以导致新的解决方案的假设。我们在top-K评估中使用了这些假设，并说明了它的好处。在未来，我们计划（i）解决部分排列，Birkhoff多面体的内部区域（ii）研究更复杂的MCMC方案，如[28，34，63，46，65]图5.随着问题大小的增加，不同方法的运行时间：N∈[10，100]，n∈[16，100]。(iii) 为我们的置信度估计寻求更好的用例，例如离群值移除。鸣谢：由ANR-16-CE 23 -0014（联邦调查局-矩阵）资助。作者感谢Haowen Deng 提供 的初步 3D 对应 ，感谢Benjamin Busam和JesusBriales提供的富有成效的讨论。（c）混乱（d）确定性地图（e）前2名混淆（f）不确定性的Top-2解决方案光谱MatchEIGMatchALSWang等人我们运行时间（秒）11115引用[1] Sameer Agarwal，Keir Mierle，and Others.谷神星解算器 http://ceres-solver.org。[2] Federica Arrigoni 、 Eleonora Maset 和 AndreaFusiello。对称逆半群中的同步。在图像分析和处理国际会议上，第70-81页。Springer，2017.[3] FedericaArrigoni 、 BeatriceRossi 和 AndreaFusiello 。 se 中 多 视 图 的 谱 同 步 （ 3 ） 。 SIAMJournal on Imaging Sciences，9（4）：1963[4] FlorianBernard ， JohanThunberg ， PeterGemmar ， Frank Hertel ， Andreas Husch ， andJorge Goncalves.一种通过变换同步的多对准解决方案在IEEE计算机视觉和模式识别会议论文集，第2161-2169页[5] FlorianBernard ， JohanThunberg ， JorgeGoncalves，and Christian Theobalt. 通过非负因式分 解 实 现 部 分 多 匹 配 的 同 步 。 CoRR ，abs/1803.06320，2018。[6] Tolga Birdal ， Emrah Bala ， Tolga Eren ， andSlobodan Ilic.通过局部重叠摄像机网络在线检测三维零件。在2016年IEEE计算机视觉应用冬季会议（WACV）上，第1-10页。IEEE，2016.[7] Tol g aBirdal ，UmutSim s ekli，M. OnurEk en和Slobodan Ilic 。 基 于 Bingham 分 布 和 TemperedGeodesic MCMC的贝叶斯姿态图优化。神经信息处理系统进展（NeurIPS），2018年。[8] Tolga Birdal和Slobodan Ilic。cad的准确性和灵活的实例重建先验。IEEE International Conferenceon Computer Vision，2017。[9] 加勒特·伯克霍夫关于代数线性的三个观察。 Univ. Nac 你要让我知道。 先生A，5：147[10] BenjaminBusam 、 MarcoEsposito 、 SimonChe'Rose、Nassir Navab和Benjamin Frisch。机器人 合 作 运 动 治 疗 的 立 体 视 觉 方 法 。IEEEInternational Conference on Computer VisionWorkshop（ICCVW），2015年12月。[11] 西蒙·伯恩和马克·吉罗拉米嵌入流形上的测地线蒙特卡洛。Scandinavian Journal of Statistics，40（4）：825[12] Tibe' rioSCaetano ， JulianJMcAuley ， LiCheng ，Quoc V Le，and Alex J Smola.学习图形匹配。IEEE模式分析和机器智能学报，31（6）：1048[13] Kunal N Chaudhury ， Yuejiang Khoo 和 AmitSinger。利用半定规划实现多点云的全局配准。SIAM Journal on Optimization，25（1）：468[14] Changyou Chen，Nan Ding，and Lawrence Carin.高阶积分随机梯度MCMC算法的收敛性。神经信息处理系统进展，第2278- 2286页，2015年[15] Yuxin Chen，Leonidas Guibas，and Qixing Huang.通过凸相关的近最佳联合目标匹配。在第31届机器学习国际会议的会议录-第32卷，ICML108. JMLR.org，2014年。[16] Minsu Cho，Karteek Alahari，and Jean Ponce.学习图形匹配。在IEEE国际计算机视觉会议论文集，第25- 32页[17] 圣潘·C·l·e·men·c·卡隆和J·r·e·mie·雅各布·奥·维奇。排序间的Kantorovich距离及其在排序聚合中的应用.在欧洲联合会议上机器学习和知识发现数据库。施普林格，2010年。[18] LucaCosmo，AndreaAlbarelli ， FilippoBergamasco ， AndreaTorsello ， EmanueleRodola` ，andDanielCremers.无序图像中多特征联合匹配的博弈论方法模式
