没有合适的资源?快使用搜索试试~ 我知道了~
6453∈群标号多重图Andrea Porfiri Dal Cin1、Luca Magri1、Federica Arrigoni2、Andrea Fusiello3和Giacomo Boracchi11DEIB -米兰理工大学(意大利)2DISI -特伦托大学(意大利)3DPIA -乌迪内大学(意大利)摘要同步指的是推断附在图的顶点上的未知值的问题本文讨论了多图的同步问题,即多个边连接同一对节点的图当多个度量可用于对两个顶点之间的关系进行建模时,问题自然出现当不同的传感器测量相同的量时,或者当原始图被划分为独立求解的子图时,会发生这种情况在这种情况下,子图之间的基线解决方案通过平均它们的多边将多图减少为简单图,但是这种方法不足,因为:i)平均值仅对某些组定义良好,以及ii)所得估计量不太精确和准确,如我们凭经验证明的。具体来说,我们提出了多个ULTISYNC,同步算法的多图,是基于一个原则性的约束特征值优化。多SYNC是一个一般的解决方案,可以应付任何线性组,我们证明是有益的合成和实际问题上使用。1. 介绍计算机视觉中的许多任务都可以用公式表示为组标记图的同步[50]:给定用组Σ的未知元素标记的节点的网络,需要从表示为附接到边缘的比率(或差异)的噪声相对测量的集合来估计它们。一个突出的例子是当图的节点是传感器时,目标是恢复公共参考系中每个传感器的未知姿态和位置。在这种情况下,标签在特殊欧几里德群Σ = SE(3)中,并且成对测量是相对取向。根据组,同步公式可以被利用来建模计算机视觉中的其他相关问题,例如运动结构、同时定位和映射图1:多图是允许其节点之间有多条边的图。节点对应于未知的群元素xIS0(3),并且边对应于已知的相对度量。基数为3的多边,例如由相对变换的不同估计产生,用橙色描绘。(SLAM)、多视图匹配和图像拼接。传统上,同步被定义在简单的图上,即图的顶点对最多由一条边连接。 在这项工作中,相反,我们处理多个测量可用于同一对节点(多边)并且同步在多图上而不是在简单图上执行的情况(参见图1)。这种一般的多图同步框架允许我们自然地考虑同一对节点之间的多个测量,这通常发生在许多应用中。在SLAM中,例如,多个传感器(相机、IMU、GPS、. . .)可以估计6车辆的d.o.f运动。多图自然出现的另一场景是在大规模问题中,其中原始图被划分成独立求解以节省计算时间的较小子图在这种情况下,连接来自不同子图的顶点的切割边产生多边并产生多图同步问题,如将在第2节中阐明的。五、这种分区方法不仅减少了内存和处理时间,而且还支持多线程和并行性。此外,它在隐私方面具有相关的含义,因为它允许数据被隔离,使得每个处理节点仅看到数据的一部分(参见例如,图1)。,[25])。多重图上的朴素同步解决方案6454此后称为边缘平均化-包括通过平均它们的测量值将多个边缘减少为简单边缘。这具有若干缺点。首先,平均值仅适用于某些组:虽然可以对旋转进行平均[32],但是对于单应性没有原则性的解决方案。其次,即使当它是可能的平均多边缘,所得到的估计具有次优的统计特性。作为示例,考虑估计将具有噪声条目的两个矩阵链接的比例因子s的问题:A=sB。 最佳估计是最小二乘解s= tr(BA)/tr(BB),其不同于例如,取入口方向除法A的平均值。/ B.我们的实验证实,这种直觉也适用于同步。捐款. 我们的解决方案-名为M ULTI S YNC -从一个新的角度探讨了组标记的多重图的同步:不是为了将多边折叠成简单边而对测量进行平均,而是扩展了多边中涉及的多图复制节点,并在复制节点之间强制实施身份约束。这导致了一个约束优化问题,我们推导出一个一般的封闭形式的频谱解决方案,可以应用于任何线性组标记的图形我们的实验,在合成和真实的数据集上进行,证明了多个SYNC优于边缘平均的准确性和精度。在partitioned问题的上下文中,我们的解决方案取得了很好的平衡之间的准确性和复杂性,而不是在整个图上执行同步。总而言之,我们的贡献有三个方面:首次给出了多图同步的形式化定义,它是简单图同步的一我们推导出一个实用的多图同步问题求解算法MULTISYNC,它是基于一个扩展算法加上一个约束的频谱解决方案来处理复制节点;我们演示了如何多图框架可以方便地用于划分经典的同步任务,实现了准确性和复杂性之间的良好权衡。纲要本文的结构如下。秒2回顾以前的作品。秒3提供了理论基础,并提出了我们的解决方案。秒4报告合成实验结果和Sec.5描述了多图同步的可能应用:分区同步结论绘制在Sec. 六、2. 相关工作同步问题的名称来源于时钟同步[26],并且已经在计算机视觉社区中得到了广泛的研究(参见[3]以了解最近的调查)。根据所选择的组,获得问题的具体实例,其涉及不同的应用。在特殊正交群(S 卩,,Σ = SO(3))被称为旋转同步、多旋转平均[32]或旋转优化[57]。 现有的技术包括最小二乘法[37],谱分解[50],Weiszfeld算法[31],Levenberg-Marquardt算法[19],李群优化[17],半定规划[ 58,22,21 ],离散规划[ 58,22,21]。贡献优化[56,52],低秩分解[6],黎曼优化[12],深度学习[42]和消息传递[49]。当特殊欧几里得群(即,Σ= SE(3)),它导致刚体运动同步、运动平均或姿态图优化。现有的技术包括谱分解[9,7]、李群优化[29]、对偶[54]第五十五章:我的天有限编程[44,43],分布式优化[53],组收缩[39],贝叶斯优化[14]和深度学习[33,27]。旋转和刚性运动同步都可以应用于运动结构[40]、3D点云的配准[30]和SLAM [16,23]。当考虑对称群(即,Σ = Sym(d)),得到了置换同步,并应用于多视点匹配。现有的方法包括谱分解[41,47,10],高斯-赛德尔松弛[60],分布式优化[35]和 黎 曼 优 化[13]。 其 他 同 步 问 题 涉 及 特 殊 线 性 群(即,Σ = SL(3)),其用于表示图像拼接中的单应性[46],以及一般仿射群(即,,Σ = GA(3)),其已用于求解全局颜色匹配[45]。所有上述方法,除了在注释1中讨论的少数例外,仅限于处理简单图。然而,在某些情况下,多图自然出现,最突出的一个是分区同步,这激发了我们的研究。对于大规模图,同步方法,特别是鲁棒的同步方法,可能会导致严重的计算问题,因为复杂性相对于图中的边的数量增加。一种有效的补救方法是将原始测量图划分成可以容易地同步的较小的子图(在该上下文中称为块),然后可以组合每个块的标记以获得原始图的一致这最后一个步骤可以被看作是在多重图上的同步,其解决了局部逐块解决方案的不确定性(参见图2)。(五)。将同步问题划分为较小的子问题(更容易解决)的想法存在于运动结构[11,24],同时定位和映射[36]和运动分割[4]的背景下的许多作品中。然而,这些技术确实6455∗||E → V∈VE E → V||≤V EVG∈∗V→V EV →不利用多重图公式-在文献中存在一些其他的分区流水线(例如,在3D重建[62,18,61]或传感器网络定位[20]的上下文中),然而,它们没有解决同步问题,因为它们利用相对测量值旁边的附加信息(例如3D点的3. 多图的同步在本节中,我们介绍了群标记多重图上同步的理论框架3.1),然后我们提出了我们的算法(命名为MULTI SYNC)的线性群。在高层次上,我们的方法包括以下主要步骤:图形扩展:通过创建顶点的副本,将多重图扩展为简单图(Sec. 3.2);约束优化:解决了受约束的特征值问题,以解决与共享相同标签的重复顶点的同步问题(参见图2)。3.3)。3.1. 制剂有向图中的多重边是具有相同尾顶点和相同头顶点的两个或更多个边的集合。允许多边的图被称为多重图(参见图1的示例),其扩展了图的定义如下:定义1(多重图[15])。 多重图=(,,s,t)是没有循环的有向图,其中是顶点的集合,是边的集合,s:是 将 边映射到其源顶点的函数,并且t:是将边映射到其目标顶点的函数。定义2(多边[15])。 给定一个多重图G =(V,E,s,t),多重边E(i,j)是如下集合:E(i,j)={e∈ E:s(e)=i ∧ t(e)=j}。(一)严格地说,每一个简单图也是一个多图,但此后我们把它们看作不同的对象:简单图指的是具有基数E(i,j)的图1,而重图必须至少有一对顶点(i,j),E(i,j)>1。群的元素(Σi)可以用于标记多重图的边,从而产生群标记的多重图:定义3(群标号多重图)。一个Σ-标记的多重图是一个元组Γ =(V,E,s,t,z),其中G=(V,E,s,t)是一个多重图,z:E →Σ是边标记函数。边集合E满足以下性质:如果e∈ E且s(e)=u∧t(e)=v,则e′∈ E且s(e′)=v∧t(e′)=u,且z满足:z(e)= z(e′)−1。(二)当量(2)意味着连接一对顶点(u,v)的每条边具有连接(v,u)的对应边,其用逆变换标记。定义4(标签一致)。设Γ =(,,s,t,z)是一个Σ-标号多重图,x:Σ是一个顶点标号图. 我们说x是一致标号当且仅当以下条件成立:z(e)=x(i)*x(j)−1(3)i,j ∈ V且当量公式(3)也被称为一致性约束,因为它意味着对于任何顶点对(i,j),连接i和j的边的标签必须等于顶点标签x(i)和x(j)的比率。在同步问题中存在固有的模糊性:如果x:Σ满足等式(1)(3),则y(i)=x(i)w也是一个解,对于任何(固定的)w Σ。在存在噪声的情况下,一致性约束将不被精确地满足,因此多图同步的任务是找到未知顶点标记,使得等式(1)为:(3)近似满足,例如,在最小二乘意义上。在这种情况下,多边缘表示冗余的相对测量以有效地补偿误差。注1. 由于谱解的一般性,本文着重讨论它,因为它可以应用于任何矩阵群(例如,旋转[50],刚性运动[9,7],同态[8])以及半群(例如,部分置换[38])和具有较差结构的集合(例如,二元矩阵[5])。观察到现有的基于谱解的同步技术不能直接应用于多图,因为多 个 边 不 能 在 邻 接 矩 阵 中 表 示 ( 参 见 第2 节 ) 。3.3)。因此,如稍后将阐明的,多重图必须被变换成存在基于以下约束的同步技术[37]:z(e)*x(j)=x(i)(4)这引起迹线最小化问题[57],其中多个边缘可能被考虑作为附加项。然而,这些方法限于群组,因为上述约束等效于等式(1)。(3)仅在群中;相比之下,我们的方法也有此外,基于非线性优化的一些技术(例如,[19,17,55])可以通过让边表示成本项的和来适应于多重图。然而,这些方法是精心设计的一个选定的组,而我们的方法提供了一个近似的封闭形式的解决方案,任何矩阵组。备注2. 边平均的朴素策略-6456X1X2X11X2X12--z1z2(a) 极小重图z11Σz2(b) 膨胀Xi(c) 具有两条多重边1x1x 2x31Σ 1Σ(d) 膨胀图2:多图扩展:通过复制特定顶点(阴影节点)并引入附加约束以保留图中节点之间的绝对(全局)和相对(成对)信息,将多图扩展为没有多边的简单图的过程。-此外,平均化并不总是很好地定义的:虽然[ 32 ]对SO(3)中的平均值进行了很好的研究,但对于同相图,类似的结果是未知的。出于这个原因,我们遵循不同的策略:不是通过折叠多个边来减少多重图,而是首先通过创建顶点的副本来扩展它,如第2节所示。3.2.然后,我们恢复一个一致的标签,ING由一个受约束的频谱解决方案,其中重复的顶点共享完全相同的标签,如第二节所述。三点三3.2. 多图展开我们提出了一个迭代的贪婪算法来扩展一个多图到一个简单的图保留所有的成对信息。基本原理是,每个多边可以通过适当地复制源或目标顶点而扩展成等于其基数的多个简单边。图2a表示两个顶点x1和x2由具有基数的单条多边连接2. 为了将其扩展为一个简单的图,这就足够了以仅复制两个顶点中的一个,从而将多边变成将副本连接到非复制顶点的2个边。标记为1 Σ的附加边缘(图中的蓝色边缘)2b)被添加以连接副本,因为它们共享相同的标签。在此步骤之后,连接到复制节点的所有顶点将少一个传入的多边形。这表明具有多个多边的顶点应该首先被扩展。更一般地,考虑顶点xi的展开通过多条边连接到多个顶点的边的特征在于不同的基数。参考图1B。在图2c中,我们有两个多边,其中边为2和3在x i中具有传入边的节点连接到所有副本(图1中的黑边)。第2d段)。另外,来自X1的所有外出边缘(即使当属于不同的多边缘时,例如,图中的橙色和绿色多边缘2d)保留它们的标签并且简单地将它们的源改变为副本之一 分布约束不会显著影响同步性能,并且证明在速度和存储器方面是有益的,因为需要向扩展图添加较少的约束。该算法的计算复杂度为O(n2m),其中m为多重边的平均重数,n为顶点数有关扩展算法的更详细说明,请参阅补充材料3.3. 约束特征值优化虽然多图同步的理论框架(Sec.3.1)和我们的扩展算法(Sec. 3.2)是一般的并且对任何群都成立,为了具体起见,我们将在下文中关注线性群,即,允许矩阵表示的组。一个简单的群标记图,其中群是线性的,可以使用谱方法[9,7]同步,我们在下面简要回顾,然后将其扩展到多重图。设n表示简单图的顶点数并且让我们收集大小为dn×d的分块矩阵X中的所有未知数和大小为dn×dn的另一个分块矩阵Z中的所有测度,其构造如下x(1)Idz(1,2).. . z(1,n)x(2)z(2,1)Id. . . z(2,n)....假设,为了说明的目的,每个多-好吧好吧...分别来自同一顶点X1。扩大X1包括以下步骤。i) 复制顶点:要引入的复制副本数对于xi等于从xi输出的多个边的最高基数k,即,图3中的3个灰色节点2d.ii) 添加标识约束:添加由1 Σ标记的k个1边以加强k个副本之间的同一性(图1中的蓝色边)。第2d段)。iii) 在复制副本之间分配以前的约束:每当量(5)显然指的是一个完整的图。 对于不完整图,Z填充有对应于缺失边缘,即,可用的测量值为ZA=Z◦(A1d),(6)其中A表示图的邻接矩阵,◦表示Hadamard(或条目式)积,表示Kronecker积,1d是由1填充的d×d矩阵x(n)z(n,1) z(n,2) . . .Id6457---.Σ--×个×个····∈.Σ−.ΣXFD例如,最终投影可以通过奇异值命题1([9,7])。一致的顶点标记X满足以下等式:ZA X−(DId)X= 0(7)其中D表示图的度矩阵这个命题是在一个简单的图形,其中,由于噪声,解决方程的同步频谱解决方案的基础上。(7)最小二乘法:2其中,∆和Γ是未知拉格朗日乘数的矩阵,具有∆对称性。设对X的导数为零,我们有L= 2M(十三)X回顾[28]中描述的方法,我们左乘C,然后使用CX= 0,我们得到2CMMX+CCΓ= 0,(14)minX X= IdMX由此我们得到Γ= 2C†MMX。将Γ的该封闭形式表达式插入(13)中得到:其中M=Z A(D)Id)由以下矩阵定义:不完整的相对测量。可以证明松弛同步允许一个封闭形式的解作为M[9,7]的零空间,而该零空间又可以从MM的最小特征向量导出。现在让我们考虑一个群标记的多重图的情况。通过求解等式(1)来同步扩展图。(8)对于未知标签,X达不到,因为它不保证复制的节点已经被分配了相同的标签。事实上,由标记有身份的边给出的约束被视为“软”约束,就像所有其他约束一样。为了获得与底层多重图一致的扩展图的标签,因此有必要强制复制的顶点共享完全相同的标签。因此,我们导致一个约束版本的方程。(八)、I−CC† MMX=−X∆,(15)其中C†=(CC)−1C。令P=I CCt且X=[X1,. . . ,xd],最后一个方程表明PMM的特征向量是(12)的平稳点,特征值是相应的平稳值。 即使P和MM是对称的,它们的乘积也不一定是对称的。然而,由于P2=P(因此它是投影矩阵),我们得到eig(PMM)= eig(P2MM)= eig(PMMP). 因此,(12)的平稳值是PMMP,它们是实数(以及特征向量)。第三条如果C具有秩k,则至少k个特征值将是最小值MX2服从XX=I,CX= 0,(9)零,因此当xi是d时,获得(9PMM的正交特征向量对应于特征-其中CX=0强制复制顶点之间的相等。具体地,C是由大小为nd_d的r个列块C_k组成的nd_rd矩阵,其适应副本之间的r个约束:假设第k个约束具有Xi-Xj=0的形式,因此值λk+1λk+d按r的升序排列。Golub[28]建议通过使用C的秩揭示QR分解来去除由于C的秩而导致的k个零特征值。补充材料中报告了这方面的详细情况。请注意,定理1解决了一个放松的问题,因为可行集由X∈Rdn×dn给出,其中XX=C=. C1···Ck···CrΣ,KDD(十)Id,而不是X Σn。 为了恢复块级式中X的结构(5)因此,必须对每个C =. 0· ··I···−I· · ·0 Σ。将X的d× d块映射到群Σ上。当Σ = SO(3)时,对于由于下面的新结果,约束问题(9定理1. 成本函数(9)的稳定点由I CCt的特征向量给出。 MM,其中C†是C的伪逆。证据 问题(9)等价于min trX(MM)Xs.t. XX=Id,CX = 0。(十一)X该问题的成本函数的拉格朗日量为腐烂。 这产生了我们的封闭形式的解决方案多图同步在存在离群值的情况下,可以通过迭代重新加权最小二乘法(IRLS)轻松获得鲁棒性,如[7]所示。总而言之,MULTISYNC输入组标记的多重图,并使用扩展算法(Sec. 3.2)将其扩展为具有复制节点的简单图。副本之间的硬约束然后被集成在约束问题(9)中,对于该约束问题(9),使用定理1导出封闭形式的解。最后,将解的每个块投影到Σ上。值得注意的是,我们的方法是通用的,它可以应用于任何线性群(和6458.Σ。ΣL−= trX(MM)X+ tr ∆(XXId)+tr. ΓCX)Σ,(十二)半组),如在SEC中提到的那些。2,其与各种视觉应用相关。6459边沿平均多同步1e 2(c)准确度w.r.t.边缘平均MultiSync旋转误差方差误差方差∈V∈(a) 准确度w.r.t. M105八、四六三四二10 20 30M(b) 精密度w.r.t. M10 2030M864200.0 0.2 0.4 0.60.82.01.51.00.50.0(d)精密度w.r.t.边沿平均多同步0.0 0.2 0.4 0.6 0.8图3:SO(3)中的实验:在m(多边缘的平均基数)和噪声水平σ的各种值下,合成多重图上的MULTISYNC和边缘平均的准确度和精度。曲线越低越好。1.00.80.63.02.52.01.51.02.081.561.0420.55 10 1520M0.55 10 1520M0十四十三十二十一0.0十四十三十二十一图4:SL(3)中的实验:在m(多边缘的平均基数)和噪声水平σ的各种值下的合成多重图上的MULTISYNC和边缘平均的准确度和精度。曲线越低越好。4. 合成实验我们比较了我们的解决方案(MULTISYNC)与合成数据的边缘平均的基线方法,因为这两种方法都是为多重图明确开发的一般技术。未来的工作将考虑替代的方法,可以很容易地适应从简单的图到多图(如在备注1中讨论的)。代码在[1]中可用。我们考虑了旋转群SO(3)和特殊线性群SL(3)中的同步问题。根据参数(n,p,m)生成随机多重图,其中n表示顶点的数目,p表示任意两个顶点由多重边连接的概率,并且m是多重边的平均基数我们考虑了不同级别的噪声,这是以不同的方式定义的两组。这些合成数据中不存在异常值,因此,我们集中于非鲁棒方法。SO(3)中的同步。我们通过旋转之间的角距离[34]将估计的标签x~与地面实况标签x进行比较,其被定义为i=并且我们报告所有节点i上的均值和方差。使用(非稳健)弦2-均值进行边缘平均[32]。在第一实验中,模拟的多重图具有n= 1。10个顶点,p= 0。75和多边缘的变化的平均基数m。对于每次运行,通过均匀采样欧拉角来实例化n个随机真实旋转矩阵x(i),因此生成相对旋转当z(i,j)=x(i)x(j)ω(i,j)时,ω(i,j)SO(3)是一个小的乘性噪声。 扰动ω(i,j)的欧拉角从具有零均值和标准差σ = π/8的高斯分布中采样。图图3(a)报告了在100次试验上平均的角距离,证明了我们的MULTISYNC相对于边缘平均在精度方面的益处,特别是对于较高的m值。图图3(b)报告了误差的方差,表明我们的方法对于m的所有值都提供了明显更精确的结果。在第二实验中,我们评估了当增加高斯噪声σ的水平时所分析的方法的响应,选择其中边缘平均和MULTISYNC在先前实验中显示出相当的性能的多图,即n= 10,p= 0。75且m= 5。图3(c)报告了作为σ的函数的平均角距离,示出了MULTISYNC比边缘平均更准确,特别是对于大量噪声。从图3(d)中,我们可以理解,与边缘平均相比,对于我们的MULTISYNC,方差增加得不那么快(相对于σSL(3)中的同步。我们在SL(3)中标记的合成多重图上重复了先前的验证过程。为了将估计的标签x~与地面实况标签x进行比较,误差被定义为与恒等式的偏差的Frobenius范数:i=并且我们报告所有节点i∈ V上的均值和方差。边缘平均通过计算边沿平均多同步(c)准确度w.r.t.边沿平均多同步1e 1(a)准确度w.r.t.M边缘平均MultiSync1e 3(b)精密度w.r.t.M边缘平均MultiSync1e 3(d)精密度w.r.t.边缘平均MultiSync平均旋转误差平均误差误差方差平均旋转误差平均误差旋转误差方差6460转∈∈∈vu∈. x u(i)w uΣ. x v(j)wΣ−=xu(i)w w−1xv(j)−1。在那里-∈∈逐元素平均,然后将得到的矩阵投影到SL(3)群上。地面实况变换x(i)被生成为具有在[0,1]中均匀采样的条目的随机矩阵,其最终被投影到组上。相对变换被具有零均值和标准差σ的加性高斯噪声破坏。分析方法的性能(100次随机运行的平均值)报告于图1中4,证实了SO(3)中的发现。相对于平均多边缘基数m,我们的方法是更准确和更精确的边缘平均。我们的解决方案的优点对于大噪声值σ甚至更明显,其中MULTISYNC具有较低的误差和较小的方差。这些实验的概要是边缘平均不提供最佳结果,因为在简化的测量图中引入了主要近似。MUL-TISYNC克服了这些限制,并且更好地组合由多个边缘标签提供的信息,特别是当它们的多重性趋于显著时。5. 适用范围:分区同步我们说明了我们的多图配方可以用来处理分区同步问题,展示了我们的方法对真实数据的优势。主要步骤可详细描述如下:A) 图分区:第一步在于将原始图Γ划分为多个片Φ1,…,Φ 2。. . Φk(见图的中间部分)(五)。为此,我们饲料其邻接矩阵谱聚类。我们选择[48]的归一化,因为它倾向于平衡聚类1中的边的数量,这是我们正在使用的稀疏矩阵方法的计算复杂度的相关参数。注意,在一些应用中,例如,在出于隐私原因信息不能在所有节点之间共享的情况下,给出图的分区并且回避该聚类阶段。简单图分割面片图图5:分区同步:简单图(在左侧)被划分为三个小片。每个补丁是单独同步的。为了解决局部模糊性,构建了一个补丁图(在右侧),其节点对应于补丁,并且多边包含切割边(以红色绘制)。补丁图同步与我们的多图的方法。1这个选择并不重要:其它算法给出类似的结果。B) 修补程序上的同步:每个补丁Φu(其是简单的图)使用标准同步技术独立地同步(参见第2节)。2),对每个面片Φu,得到一个标号xu:ΦuΣ。 每个局部标记都有自己的模糊性,因为它被定义为任意组元素的动作。因此,我们需要去除局部模糊性,并将该步骤中导出的多个标签提升为原始完整图上的单个一致标签。C) 补丁图构建:我们构建一个多重图,称为补丁 图 , 如 下 所 示 。 面 片 图 的 顶 点 对 应 于 面 片Φ1,. . . ,Φk,并且连接Φu和Φv的多边由所有切割边组成,即,一个端点在Φu中,另一个端点在Φv中的边(如果有的话)(见图的右边部分)(五)。补丁图中的每个节点用未知群元素标记,该未知群元素表示必须应用于补丁以修复其群歧义的变换,令w uΣ是节点Φ u的标签。补丁图的多边上的度量定义如下。让我们考虑连接节点Φu和Φv的多边缘,其包括两个贴片之间的多个切割边缘。让我们考虑连接节点iΦu和节点jΦv的一个切割边,并且让Xu(i)和Xv(j)是在先前对补丁的同步中找到的相应标签。这样的标签必须乘以表示局部歧义的相应矩阵,即w uΣ和w vΣ,因此一致性约束重写z(i,j)=1v前wuwv−1 =xu(i)−1z(i,j)xv(j)是Φu和Φv之间的多重边的标签。D) 补丁图上的同步:我们的MUL-TISYNC应用于补丁图,以计算未知的变换W1。. . w kΣ(参见第(3)第三章。对于每个补丁,通过应用相应的变换wu来相应地变换标签分配xu。这产生唯一且全局一致的标记,直到单个全局模糊度。为了实验验证,我们考虑了SO(3)中的parti-tied同步问题。我们使用取自[59,19]的大规模图像数据集,其提供输入图和相对旋转的估计。这些图表非常不完整,并受到缺失数据的影响。Bundler[51]的输出被视为地面实况,如文献中通常所做的那样。所有实验都在MATLAB中在Intel Core i9 9900k上以股票速度与16GB的3200MHz RAM耦合进行。在Sec。4、将该方法与边缘平均法进行了比较。MULTISYNC和边缘平均两者都对在从A到C的步骤之后构造的相同补丁图进行在步骤A中,其中输入图被划分的聚类的数量c由下式计算:6461×个表1:SO(3)中的分区同步在来自[59,19]的真实数据集上。报告了MULTISYNC和边缘平均的平均误差、中值误差和运行时间t全同步性能包括在内,但仅旨在作为理想的参考,因为它在不同的假设下工作,具有完整的图形,而不是将其分区。在补充材料表中,以全分辨率报告。边沿平均多进制YNC全同步执行分区方法,因为它利用了全图上可用的所有信息-一些较大的序列,如皮卡迪利,在这方面显示出13的如前所述,MULTI SYNC可以被视为一个通用框架,它对同步技术是不可知的。数据集nct联系我们联系我们在子图上使用nique(步骤B)。这方面在Tab中进行了研究。图2示出了与不同同步方法(即EIG-IRLS [7]、L1-IRLS [17]和R-GODEC[6])耦合的MUL-TISYNC最先进的MPLS [49]仅在表中报告。1.一、EIG-IRLS结果未在Cornell Arts Quad上报告,因为它未达到收敛。事实证明,各种方法在全图上的不同性能反映在分区情况下:例如,R-GoDec是最快的解决方案,而L1-IRLS是最准确的关于完全同步,我们再次看到多个当c = 0时,顶点数n。54√n,其中系数-0. 54已经在整个数据集上手动调谐在步骤B中,我们使用MPLS(消息传递最小二乘法)[2,49]来同步各个补丁,这代表了旋转同步的最新技术。然而,值得注意的是,我们的框架允许插入任何SYNC在准确性和计算负担之间取得了良好的平衡。表2:结合不同技术的 MULTISYNC在真实数据集上用于SO(3)中的同步的性能[59,19]。报告了中值误差和运行时间t。在补充材料表中,以全分辨率报告。方法,因为单个补丁的同步是这一点,我们以后会看到。为了效率起见,在步骤C中,我们通过对切割边缘进行随机子采样来考虑基数至多为50的多边缘。最后,由于这些数据集受到离群值的影响,因此步骤D中的多图同步通过鲁棒技术来执行:如[7]中所示,用IRLS增强MULTIYNC,以提供对离群值的鲁棒性;在边缘平均中,多边缘的标签是平均的。EIG-IRLSMULTISYNC全同步L1-IRLSMULTI SYNC全同步R-GoDecMULTI SYNC全同步使用Weiszfeld算法[31]进行计算,从而将多图折叠成简单图;然后,将所得图与MPLS同步[49]。作为参考,我们还包括整个图上的完全同步(使用MPLS),这在理想情况下代表了在准确性方面可实现的选项卡. 1报告了所有分析方法的平均/中值角度误差和请参阅补充材料,以获得该表的完整分辨率版本。对于每个数据集,进行50次独立运行,并计算平均结果。MULTISYNC在所有情况下的准确性方面始终优于边缘平均。Gendar-menmarkt数据集的最差准确性是由图相对稀疏且缺乏循环信息的事实引起的,如在[49]中已经关于以完全同步为代表的6. 结论和今后的工作研究了多重图的同步问题。在正式介绍的理论框架,我们推导出一个有效的算法,适用于任何线性组。我们的方法利用封装在多边缘的冗余,并具有更好的统计特性方面的基线方法的边缘平均,提高准确性和精度。多图同步的应用不计其数,包括分区同步.未来的工作将包括部分置换,同步和替代图扩展算法,包括最优性的分析。鸣谢。Federica Arrigoni得到了欧盟地平线2020研究和创新计划的支持,该计划是SPRING项目(赠款协议编号:871245)。埃利斯岛人民广场2473459113.565.620.731.861.021.273.495.220.681.411.071.3833.30.470.863.43.47纽约图书馆马德里大都市37639411114.917.843.353.190.931.134.247.142.322.521.011.183.166.61.271.124.81.18约克明斯特蒙特利尔北Dame45847412125.962.673.981.021.331.324.982.112.910.871.371.413.51.121.580.54.8310.1数据集nCϵˆ不ϵˆ不ϵˆ不ϵˆ不ϵˆ不ϵˆ不埃利斯岛24791.150.431.180.821.050.410.572.351.480.231.000.23Piazza del Popolo纽约图书馆34537611111.783.241.183.151.021.982.241.651.842.020.530.390.981.333.552.361.862.820.240.471.483.200.491.35马德里大都市约克明斯特39445811124.012.913.832.854.431.811.793.182.682.860.571.071.011.694.202.293.942.850.290.434.072.690.492.03蒙特利尔北Dame伦敦塔47448912132.122.986.923.740.592.794.092.431.012.833.671.200.582.637.101.941.022.890.520.460.853.281.052.116462引用[1] https://github.com/andreadalcin/multisync的网站。六个[2] https://github.com/yunpeng-shi/mpls的网站。八个[3] F. Arrigoni和A. Fusiello计算机视觉中的同步问题及其封闭解。国际计算机视觉杂志,128:26-52,2020。二个[4] Federica Arrigoni、Luca Magri和Tomas Pajdla。三焦点张量在运动分割中的应用。在2020年欧洲计算机视觉会议上。二个[5] Federica Arrigoni和Tomas Pajdla。通过同步进行运动分割。在IEEE国际计算机视觉研讨会(ICCVW),2019年。三个[6] Federica Arrigoni、Beatrice Rossi、Pasqualina Fragneto和Andrea Fusiello。通过低秩和稀疏矩阵分解实现SO(3)和SE(3)中的鲁棒同步计算机视觉和图像理解,174:95-113,2018。二、八[7] F. 阿里戈尼湾Rossi和A.Fusiello SE(3)中多视图的光谱SIAM Journal on Imaging Sciences,9(4):1963-1990,2016。二三四五八[8] A. Bartoli和P.斯特姆分段平面场景的多个未校准视图的约 束 结 构 和 运 动 。 International Journal of ComputerVision,52(1):45- 64,2003. 三个[9] F. Bernard , J.Thunberg , P.Gemmar , F.Hertel 、 A. 胡施,以及J. Goncalves通过变换同步进行多比对的解决方案。IEEE计算机视觉与模式识别会议论文集,2015年。二三四五[10] Florian Bernard,Johan Thunberg,Paul Swoboda,andChris-tian Theobalt.HiPPI:高阶投影功率迭代,用于可扩展的多匹配。在国际计算机视觉会议论文集,2019年。二个[11] BrojeshwarBhowmick 、 SuvamPatra 、 AvishekChatterjee 、 VenuMadhavGovindu 和 SubhashisBanerjee。 分而治:使用图分割从运动高效的大规模结构 。 2014 年 第 12 届 亚 洲 计 算 机 视 觉 会 议 ( ACCV2014)。二个[12] T. Birdal,M.Arbel,U.Simsekli和L.J. Guibas 通过最优传输同步旋转的概率测度。2020年IEEE/CVF计算机视觉和模式识别会议(CVPR),第1566二个[13] Tolga Birdal和Umut Simsekli。使用birkhoff多面体的黎曼结构的概率置换同步。在IEEE计算机视觉和模式识别集,第11105二个[14] Tolga Birdal,Umut Simsekli,Mustafa Onur Eken,andSlo-bodan Ilic.基于宾汉分布和缓和测地线mcmc的贝叶斯姿态图优化。神经信息处理系统进展,第31卷。Curran Associates,Inc. 2018. 二个[15] Be'laBollo ba's. 现代语法学,第184卷。SpringerScienceBusiness Media,2013. 三个[16] Luca Carlone、Roberto Tron、Kostas Daniilidis和FrankDellaert。用于3D SLAM的初始化技术:一项调查关于旋转估计及其在姿态图优化中的使用。IEEE机器人与自动化国际会议论文集,2015年。二个[17] A. Chatterjee和V.M. 戈文杜高效和鲁棒的大规模旋转平均。2013年国际计算机视觉会议论文集二、三、八[18] Yu Chen , Shuhan Shen , Yisong Chen , and GuopingWang. 基 于 图 的 运 动 并 行 大 规 模 结 构 。 Pat-ternRecognition,107,2020。三个[19] David Crandall , Andrew Owens , Noah Snavely , andDaniel P. Huttenlocher基于运动的大型结构离散-连续优化。在Proceedings of the IEEE Conference on ComputerVision and Pattern Recognition,pages 3001-3008,2011中。二三七八[20] M. Cucuringu,Y.Lipman和A.歌手. 基于欧几里德群特征向量同步 的传感器网络定位ACM Transactions onSensor Networks,8(3):19:1- 19:42,2012。三个[21] 放 大 图 片 作 者 : David M. Rosen , Jing Wu , RobertMahon
下载后可阅读完整内容,剩余1页未读,立即下载
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)