没有合适的资源?快使用搜索试试~ 我知道了~
通过循环一致性查看图的可解性
5540通过循环一致性查看图的可解性Federica Arrigoni1,Andrea Fusiello2,Elisa Ricci1,3和Tomas Pajdla41特伦托大学2乌迪内大学3布鲁诺·凯斯勒基金会4CIIRC布拉格CTUfederica. unitn.it,andrea. uniud.it,e. unitn.it,pajdla@cvut.cz摘要在运动恢复结构中,观察图是顶点对应于相机并且边缘表示基本矩阵的图。我们提供了一个新的配方和算法,用于建立是否观看图是可解的,即。它唯一地确定一组投影摄像机。已知的理论条件要么不完全表征所有观看图的可解性,要么非常难以计算,因为它们涉及求解具有大量未知数的多项式方程组。本文的主要结果是一种方法,用于减少未知数的数量,利用循环的一致性。我们推进的可解性的理解,(i)完成所有以前未决定的最小图的分类到9个节点,(ii)扩展到最小图的实际可解性测试,最多90个节点,和(iii)明确回答一个开放的研究问题,表明有限的可解性是不等价的可解性。最后,我们提出了一个实验的真实数据显示,不可解的图形出现在实际情况中。1. 介绍从运动求解结构是重要的,例如,用于从图像进行3D重建[33,34,29],图像匹配[26]以及视觉里程计和定位[22,1,28,35]。从运动恢复结构的基本问题是确定哪些图像集可以被重建。这可以例如进行,通过分析观看图表。一组图像的查看图[19](也称为对极图)是其中顶点对应于相机/图像并且边缘对应于基本矩阵的图。换句话说,当且仅当这样的图像对之间的基本矩阵可用时,在两个顶点之间存在边缘,这意味着存在足够的对应点。在大多数实际场景中,由于不同的相机可以查看场景的不同部分的事实,这样的图是不完整的。相关的问题是观看图是否是可解的,即,如果它唯一地确定一个投影构形图1:查看在[37]中未定义且我们确定可解的具有八个顶点的图。相机的作用,直到一个单一的投影变换。换句话说,对于不可解的观看图,存在可以应用于相机而不影响基本矩阵的多个在[19]中给出了可解性的一个等价定义,指出一个图是可解的当且仅当可用的基本矩阵唯一地确定其余的基本矩阵,即,可以将输入图变换为完整图。可解性与3D重建密切相关(参见表1)。1),因为观看图由一类从运动恢复投影结构的方法[30,16]使用,所述方法从多个基本矩阵开始重新覆盖投影相机。应当在解决重建之前评估观察图的可解性,因为如果问题是不可解的,则没有仅基于基本矩阵的方法将提供有用的重建。考虑到校准的相机,即使用本质矩阵而不是基本矩阵,可解图恰好是平行刚性图[24,38]。文献中已广泛研究了平行刚度(也称为轴承刚度)的主题(最近的调查见[3]在这里,我们关注的是未校准的场景,这已经少得多的理解。相关工作。在[19]中,刻画了至多六个顶点的图的可解性,并提供了一些关于如何分析更大图的见解。在[20]中讨论了实际完成这种视图图的构造性方法。Rudi等人。 [27]研究了可以使用线性方法求解查看图进一步的分析在[36]中可用,其中示出了一些可解图可以从三角形开始并且一次添加一个二度顶点来构造。在最近的一篇论文[37]中,给出了5541PGp q PEpqG PtupGPqEtu tu“|E|VPG1n校准的未校准的可解性[3][19,27,37]`我们的重建[25][30,16]表1:问题分类。我们处理未校准的情况。调查[3,25]解决了校准的情况。除了一个新的充分条件外,还报道了可解性由于这些结果,至多七个顶点的图可以被完全刻画,但也存在一些八个或九个顶点的图不能被完全刻画。可解或不可解(见图)。①的人。较大图建立有效的算法进行测试;对先前未决定的观看图进行分类;将可解性测试扩展到具有90个节点的图;证明有限可解性并不意味着可解性。本文的结构如下。我们定义的视图- ING图的可解性在SEC。2,目前的理论结果在Sec。3,并描述我们的算法在Sec. 4.第一章秒5给出了一些例子,并给出了对真实数据的实验。2. 背景让我们考虑n个未校准的相机Pi。. . PP没有被研究。[37]的作者还表明-然而,这种观察仅具有理论价值:求解这样的系统在计算上是昂贵的,因为它是非线性的,并且它涉及大量的未知数。因此,一个有效的测试解决方案仍然是失踪,这激励我们的工作。另一个开放的问题与有限可解性的概念有关,这与可解性的概念密切相关一个视图称为有限可解的,如果它最多确定有限数目的投影配置的相机。显然,如果图不是有限可解的(即,它确定了无限数量的摄像机配置),则它是不可解的。换句话说,可解性意味着有限的可解性。相反的含义– was left as an open贡献我们推导出一个新的公式,比[37]简单得多,这要归功于所涉及的未知数的数量大大减少。我们的配方是基于一个图的循环一致性属性,即(可逆)变换的组合物,沿任何循环应该是身份。这导致了一个新的算法,这是基于计算代数几何,实现了可解性的特征化。以前的技术只能测试一些充分或必要条件。使用这个算法,我们提供了一个完整的表征所有的最小图到9个节点,包括那些由[37]留下的未定。事实上,我们能够决定最多90个节点的最小图的可解性。在实践中,我们的ap-proach可以用来检测有趣的可解的子图的密集/大的观看图来自真实的数据集。最后,由于我们的算法,有可能展示有限可解但不可解的图的具体例子,从而回答了[37]中的开放性研究问题。总之,我们:提出了一种新的更简单的可解性公式;中心为c1,. . . ,cnR4. 让是顶点集为1,. . . ,n和边集1,. . .,n1、. . .,n.设m为边的个数。回想一下,对于每个边缘i,j,我们可以以封闭形式计算与相机i和j相关的基本矩阵Fij[15]。相反,基本矩阵i,j的唯一确定顶点i的相机[15 ][16][17][18][19][19][19]在下文中,我们将使用大写字母来表示矩阵,小写粗体字母来表示向量,并且小写字母来表示标量1。投影量被表示为非齐次变量,并引入合适的尺度来处理尺度歧义。定义 1. 让 被 一 观看 图 和P1,. . .、Pn是一组相机。如果产生相同基本矩阵的所有相机配置是投影等价的,即,该对被称为可解的。它们通过相同的射影变换相关联。命题1([37])。设G是一个视图,P″tP1,. . . .,P nu是具有中心c1,. . . ,cnPR4。 对pG,Pq的可解性仅取决于图G和相机中心c1,. . . ,cn.根据上面的结果,如果一个问题是不可解的,那么原因可能是图的拓扑结构或中心的实际坐标。例如,如果中心都对齐,则问题不可解(更多示例参见[19]下面的概念定义2. 一个图被称为可解的,如果它是可解的相机的一般配置。查看图可解性的必要条件[19,37]允许快速修剪可解性候选。例如,可解图必须满足:它至少有p11n´ 15q{7条边[37];1注意到这个符号与[37]中使用的符号不同。5542GHiGijGGPGPp q PEP pqP pqGGGPVp q PEp q PEGGS sLpGqLpGqG由以下公式[14]给出曲线图IJhij1sÿ它是双连接的[37];所有顶点的度至少为2,并且没有两个相邻顶点的度为2(如果n3)[19]。关于充分条件,已知任何弦(或三角化)图是可解的[36]。在[27,36,37]中提出了其他建设性方法,其中思想是检查输入图是否可以通过合适的操作转换为可解图。在[37]中导出了唯一的既必要又充分的条件,下面将对此进行回顾。2.1. 代数表征Trager等人 [37]将观察图可解性与可以应用于所有相机而不影响基本矩阵的投影变换集的特征化相关联。首先,它们确定使相机矩阵固定的变换族。对比2([37])。 设PPR3( 4 ) 为a,其中心为c PR4。对于G P GL p 4,R q和a P R ‰0,PG“aP的所有解都由下式描述:G其中I4表示44单位矩阵,GLp4,Rq表示实数44可逆矩阵的群。让我们考虑一个视图图,并让我们为每条边i,j分配一个投影变换G ijGL 4,R。应当理解,该变换将被应用于两个相邻相机PjPPj。显然,这不会改变基本矩阵Fij,因为它在射影变换下是不变PhPjPi图2:查看图形中的两个相邻边。如果我们处理单个边缘(即,一对相机),我们可以自由选择任何Gij。然而,当处理多个边(即,当考虑整个观看图时),这些矩阵必须满足全局兼容性约束。具体地,让我们考虑两个相邻的边h,i和i,j它们都入射到顶点i,并且两个变换G hi和G ij被分配给它们(见图1B)。2)的情况。此类变换必须使公共顶点处的相机保持固定,从而导致以下兼容性约束:定义3. 设是一个图,设c1,. . .,c,n,R4是n个通用相机中心。将变换Gi jGL4,R分配到图的边,使得等式(2)对所有相邻边成立,称为相容。命题3([37])。 设是一个图,设c1,. . . ,c,n,R4是n个通用相机中心。是可解的当且仅当任何相容的赋值都是以下形式Gij其中HPGLp4,Rq和sijPR‰0.在Prop。3意味着,对于可解图,作用于所有相机的唯一方式(不影响固定的基本矩阵)是应用单个投影变换。注意,中心可以随机采样,以便满足通用相机的假设。找到矩阵的相容分配,即,求解方程(2)对于所有相邻的边同时,是非常具有挑战性的,因为它定义了具有大量未知数的非线性代数系统。因此,Prop。3是在[ 37 ]中作为理论结果给出的,但没有得到检验视图可解性的实用算法。下一节将解释我们如何减轻这个缺点。3. 拟定制剂给定一个有n个顶点和m条边的图,我们的任务是确定这样的图是否是可解的。二、在整个讨论过程中,我们假设是连通的且n3 .第三章。建议的公式─的启发是代数表征中详细的Sec.2.1.具体来说,我们展示了如何减少方程中的未知数(2),从而提供了用于检查查看图可解性的更实用3.1. 线图的可解性我们的公式涉及与以下项相关联的线图G,其构造如以下定义中。定义4. 给定一个无向图,它的线图(也称为边到顶点对偶图)表示为LpGq的每个顶点表示的边缘;当且仅当两个顶点的相应边在中相邻,即它们与同一顶点重合时,它们才相邻。图3示出了一个示例。线图中的顶点的数量与原始图中的边的数量一致,即, n”m,而在GhiG´1其中hij和vhij PR ‰0(2)nMi2(四)PR4未知。我是554341PPP pq其中,n (四)、s ssSGτυτυτυPp qLpGqspqPEPp qSV'P“““我`我231个2个十二三十四四、三42观察线图中的每个节点有16个未知数,表示矩阵GτGL4,R。此外,线图中的每条边有五个未知数,表示向量vτυR4和a τυR‰0. 因此,未知数的总数由下式给出:5n图3:查看具有4个顶点(左)和相应线图(右)。请注意,原始图的一个顶点(例如,顶点2)可以多次作为线的边出现16ns`5ms21d2`11m(8)图,如通过颜色澄清的。其中di表示顶点i的度数。让我们重新写Eq。(2)根据线图LpGq 注意,边Ph,iq Pe是顶点τ P V,并且类似地,Ph,iqPe表示顶点XυPVs。这种证书回想一下,相机中心被认为是已知的在实践中随机抽样(见[37])。在线图上进行推理,我们能够证明以下结果,该结果仅根据变量vτυPR4给出可解性的表征。由边pτ,υq PEs通过构造(如PV第四个提案。 设G是一个图,且c1,. . .,cnP R4G它们共享输入图中的顶点i此后我们使用希腊字母表示线图中的顶点/边。使用该符号Eq. ⑵变成:GτG´υ1其中:并且相机的索引i被定义为是n个通用相机中心。图是可解的,如果和仅当任何一致的标签产生:在pτ,υqΡΕ.(九)证据 如果是,那就按一下[设定]。3时,所有的矩阵Gτ表示相同的射影变换,或者等价地,它们都是彼此的倍数因此,乘积GτG′υ1是恒等式的倍数(表示为由bτυI4和bτυPR‰0)。因此等式。(6)变成:定义5. 设G是一个图,且c1,. . . ,cnP R4是nbτυI4“a τ υ I 4 ` c i v T ô p b τ υ ´ a τ υq I 4“c i v T. (十)通用相机中心。 变换G τ的任意赋值GL4,R到线图的顶点,使得Eq.(5)所有边的保持称为一致标记。注1. 线图的一致标记对应于原始图上的兼容分配(参见Def.(3)第三章。我们在这里给出了这个等价的定义,以列出与同步问题的联系[32,10,5](最近的调查见[4]),其中的任务是从边缘上的测量比率开始找到一致的标签(顶点)。具体地,参考Eq.(5),则任务将是计算G τ,G υ,. . . 从已知的Z τυ开始。然而,在我们的例子中,变量ZτυGL4对于所有的τ,υ.然而,同步的框架对于导出可解性的新公式是有用的, 因为 它将在 下一 小节中 澄清 (参见 Thm 的证明)。①的人。备注2. 找到一致标记的问题涉及针对线图中的每条边的形式(5)的方程,当考虑条目时,该方程又产生16个方程。因此,使用Eq.在等式(4)中,等式的总数由下式给出:由于上述等式中的右项是秩-1矩阵,而I4是满秩的,因此使等式为真的唯一方法是设置bτυaτu0和vτu0,因此我们得到了结果。在相反的方向上,如果vτυ0,则等式(5)改写Gτ Gυ1aτυ I4,或换句话说,Gτ aτυ Gυ。这样的方程可以通过所有顶点τ传播只要线图是连通的(如果原始图是连通的,则为真[7])。这意味着所有矩阵Gτ都是彼此的倍数,因此该图是可解的,这要归功于Prop。3 .第三章。第三条 注意这个道具。3给出了关于矩阵Gτ的可解性的公式,而Prop.4仅考虑变量vτ u。在下一小节中,我们将证明,找到一致标记的问题可以通过不涉及矩阵Gτ(但仅涉及变量vτυ和aτυ)的方程组来表示在这方面,根据vτ u的可解性的公式(如Prop.(4)确实很重要。3.2. 循环一致性为了得到本文的主要结果,我们引入了“一致循环”的概念循环是一条非空路径,其中唯一重复的顶点是第一个和最后一个顶点。16ms1N2id2 m.(七)相容圈是满足代数约束的圈,如以下定义中给出的。5544LpGqCCGP`我SsLpGqt CCCuGPsPVnsG“IJp q PE嗨SLpGqLpGqSτυCspqPELpGqPp qPEPt CCCuGP“sSwd2米。(十二)5m_5S2无向图的线图在构造上是无向定义6. 设是一个图,设c1,. . .,c,n,R4是n个通用相机中心。 设τ1,τ2,τ3,. . . ,τι,τ1是线图中的圈。我们说是一致循环(或空循环),当且仅当循环一致性基的个数是边的个数减去顶点的个数加1(见[12]),我们得到方程的总数为沿循环的边标签返回标识,即Z τ1τ2 Z τ2τ3 ¨ ¨ ¨ ¨ Z ττ1“I 4.(十一)1N16pm´n`1qid2´ 2m `1。(十三)循环基是循环的最小集合,使得每个循环可以被写为基中的循环的和,其中两个循环的和是其中公共边缘消失的循环。存在几种类型的循环底座(参见[17]一项调查。我们在这里感兴趣的是线图的循环一致性基础,即循环基础,使得:如果基础中的循环是一致的,则一致性也保持在所有其他循环上(详见[12])。定理1. 让是一个图,设c1,. . .,cnR4是n个通用摄像机中心。设1,2,. . .,f是线图的循环一致性基础. 让我们在一个唯一的系统中收集基中所有循环的形式(11)的方程。G可解当且仅当回想一下,线图的顶点数满足由构造,边数m给定由等式(四)、请注意,方程式公式(11)仍然是非线性的,但它具有不涉及τ的未知数Gτ的优点,因此与公式(12)相比降低了问题的难度。(5),其中未知数的量在等式(5)中给出。(八)、备注5. 观察输入图是无向图。的确,给定一对摄像机,或者,等价地,一个边缘 i、j,固定该相机对的基本矩阵的投影变换与相机的顺序无关。换句话说,G ij G ji。当考虑线图时,我们关心的是具有定向边缘2。的确,Zτυ和Zυτ对于所有的pτ,υq∈E,该系统产生vτ u-0。证据已知存在一致标记当且仅当所有循环为空/一致(参见引理 [13]中的8和[4]中的推论1)。显然,如果所有的循环都是一致的,那么--特别地--基中的循环也是一致的。相反的情况一般不成立[12]。然而,如果我们考虑周期一致性基础,那么根据定义,在基础上的一致性意味着在所有周期上的一致性。因此,当且仅当在循环一致性基础中的所有循环都是一致的时,存在一致的标签。现在我们将这个一般结果应用于我们的问题:找到一致的标记,即,满足Eq.(5)中,等价于强制线图的循环一致性基中的所有循环是一致的。换句话说,通过对中的所有边叠加形式(5)的方程获得的系统等价于通过对中的所有循环叠加形式(11)的方程获得的系统,其中循环一致性基为. 根据prop。4,图是可解的当且仅当前者的解产生vτυ0为所有 τ,υ,从而得出本文的论题。备注4. Thm. 1包括五个非(我们在这里考虑τ h,i和υ i,j)。但是,从实际的角度来看,减少未知数的数量是方便的。 更准确地说,对于给定的定向边τ,我们考虑τ υR‰0和vτυR4为未知数,我们使用关系式Z'1来处理相对的边缘υ,τ,其中可以容易地计算逆3。3.3. 简化公式现在我们通过利用变量的变化导出一个更简单的等价公式。第五号提案。设是一个图,设c1,. . .,c,n,R4是n个通用相机中心。设1,2,. . .,f是线图的循环一致性基础. 对于每个周期kτ1、τ2、. . .,τ ι,τ1,让我们形成以下等式:Wτ1τ2Wτ2τ3¨ ¨ ¨Wττ1其中,bkPR‰0是未知标度,且Wτυ已知,表示向量vτυPR4和比例aτPR‰0。因此,在本发明中,哪里 uτυ PR4是未知的,并且十使用等式(4),未知数的总数由下式给出:G可解当且仅当上述系统`1n2我对于所有p τ,υ q P ε s,产生uτυ-0。还观察到,每个循环产生形式(11)的方程,当与(11)的方程一致时,其又产生16个方程然而,通过定向,它可以很容易地转化为有向图任意的边缘。3形式为I4`cvT的矩阵的逆由I4`cwT给出进入智慧之门考虑到基数其中11`cv v.注意w是v的标量倍数。i5545SSP4ms` 1pms´ns` 1qGCG“““p q PELpGqt CCCuGP“sssLpGq不PPLpGqG#方程式#变量#方程式#变量#方程式#变量#方程式#变量#方程式#变量#方程式#变量我们的配方643664401126311267192100208109Trager等人[37] 128120144141224198240219352286384312表2:方程式和变量的数量在我们的公式的一些最小示例上报告(参见方程式2)。(13),(17))和[37]中提出的一个(参见等式17)。(7)、(8))。回想一下,后者(在等式中描述)(2)和(5))由于其计算复杂性而在[37]中作为理论结果给出,而没有给出有效的算法。我们的公式更实际,因为它涉及较少的未知数。证据本文从线图中每条边的变量的如下变化推导出:uτυ”v τυ { a τυ(16),其被良好定义,因为aτυ ≤ 0。备注6. 谢谢prop。对于每个边τ,υ,我们有四个未知数在线图中,表示矢量uτυR4,加上每个周期的一个未知尺度。 因此,未知数的总数变为(十七)其低于与Thm相关的配方1,其中未知数的数量为5m(参见等式1)。(12))。方程的数量保持不变,由方程给出(13)。表2报告了我们的简化公式和方程中的公式之间的比较(5)举几个例子。推论1. 设是一个图,设c1,. . .,c,n,R4是n个通用相机中心。设1,2,. . .,f是线图的循环一致性基础.让我们在一个唯一的系统中收集基中所有循环的形式(14)的方程。是 可解的当且仅当这样的系统允许恰好一个解。证据 一个方向。 如果可解则uτυ0个(感谢prop。5),因此Eq.(14)对于基中的每个循环k给出bk1只有一个解决方案在相反的方向。很容易看出,如果我们把所有的标度设为b,k1和所有向量uτυ0,那么我们总是得到方程的解(14)。 如果我们假设存在唯一解,那么它一定等于b k1和uτυ0,即,该图是可解的,这要归功于Prop。五、如果图是不可解的,也会有其他的解。备注7. 推论1意味着在Eq.(14)允许固定所有的模糊性,使得解正好是一个(对于可解图)。这也意味着在实践中不需要显式地计算解,但是恢复解的数量就足够了注意,Eq.(11),相反,是受尺度模糊,因为它涉及以下中的每个边缘的未知尺度例如,当考虑单个周期时,这些标度的乘积是固定的,但它们都是自由的。关于全局投影模糊度(这是问题固有的),观察到坐标系中的全局变化仅影响矩阵Gτ,但不影响乘积GτG′υ1Zτυ因此,投影模糊性不存在于等式(1)中给出的公式中。(11)和(14)(不涉及矩阵Gτ)。4. 该算法我们的算法(总结在Alg. 1)是一个直接的结果,从第二节的理论结果。3;特别是,我们遵循的简化配方中得出的Sec。3.3,它基于Eq.(14)。一些步骤需要额外的解释,在下面的注释中给出。算法1查看图的可解性输入:无向图,输出:可解或不可解1. 随机抽取摄像机中心2. 计算线图LpGq3. 计算LpGq的环相容基4. 建立形式(14)和(20)5. 计算实数解的个数s六 、 如果s-1,则可解;否则不可解备注8. 关于步骤3,我们关注一种特定类型的循环一致性基[12],即,由于其简单性,我们考虑基本循环基。事实上,该基础可以从生成树开始构建,生成树可以通过深度优先搜索或广度优先搜索在线性时间内找到。 设是,的一个生成树,则添加从到的任意边生成一个圈;这些循环的集合构成基本循环基[17]。备注9. 至于第4步,回想一下我们的未知数包含一个标度b k每个循环的R和一个向量uτυR4的直线图中的每条边。这些变量必须满足5546‰“p` qěP节点3456789图111433627方法Alg. 1[37]Alg. 1[37]Alg. 1[37]Alg. 1[37]Alg. 1[37]Alg. 1[37]Alg. 1[37]可解1111114433三六三一十七五不可解00000000000个0个10个未知000000000005022表3:最小查看图的可候选图是有限可解且满足必要条件的连通图[37]未确定某些情况,而我们的方法提供了最多9个节点的所有最小图的完整表征以下限制:bk‰0(18)Wτυ I 4 ` c i u J τ υ P GL p 4,R q.(十九)而不是显式地强制它们,我们添加以下等式zτυdetpI4`ciuJτυq`1其中z τυR是辅助变量。Cl early,ifdeterI4ciuJτυ0,则上述等式不能在实数上满足。换句话说,该附加等式具有自动丢弃不可逆矩阵的效果。还观察到,如果所有矩阵W τ u是可逆的,则它们的子集的乘积也是可逆的。换句话说,Eq.(14)对于每个循环是可逆的,因此bk0。因此,等式(20)意味着(19)和(18)两者。备注10. 步骤5基于计算代数几何学。特别地,我们采用了Gr? bner基计算[8],这是求解域中系数多项式方程Gr¨ bner基可以看作是线性系统高斯消去法的非线性推广[18]。备注11. 虽然我们的问题是在R上陈述的,但是为了效率[2],我们在Zp上执行计算(即,整数模一个大素数p),如应用代数几何中的习惯这产生了与C[31]中相同的解的数目c,其大于或等于R中所寻求的解的数目s。 回想一下s1,因为总是存在至少一个平凡的实解(由uτυ“0,b k“1和z τυ”1给出)。几起案件给出:i)如果cs注意如果c是偶数s2,因为解必须是共轭的。5. 实验在本节中,我们证明了我们的方法可以适当地用于检查几个示例上的视图图可解性。另见补充材料。我们的算法在Macaulay2 [11]中实现,并且代码是公开可用的4。4https://github.com/federica-arrigoni/solvability我们遵循[37]中使用的协议,其中具有最小边数的图(即,Mr11n157s)进行了分析。如前所述,在[37]中存在有八个和九个节点未确定的情况(见表1)。2在[37]),因为它们满足必要但不充分的条件5。相反,我们的方法是对可解决性的有效测试,基于问题的表征(即,一个条件,既必要又充分);因此,它能够对所有那些未决定的情况进行分类,如表1中所总结的。3 .第三章。特别地,具有八个节点的五种情况(如图1所示)。1)都是可解的。图4:一些具有9个节点的可解最小查看图。图5:一些不可解的最小查看图,有9个节点。对于具有9个节点的极小图,在[37]中有22个未定图,特别地,它们是有限可解的(即,它们识别有限数量的照相机配置)。有限可解性是可解性的必要条件,但不知道它是否也是足够的,因为迄今为止研究的所有不可解图我们的算法能够证明这些未决定的情况的子集是可解图(见图1)。4为例)。令人惊讶的是,在这些候选者中也存在一些不可解的图(一些示例参见图5),其中我们的算法找到两个实数解。因此,图可能是有限可解的而不是可解的(即,具有严格大于一的有限个实数解这回答了Trager等人指出的一个开放的研究问题。[37 ]第37段。在[37]中没有研究查看具有超过9个节点的图形相反,我们的方法是能够处理最小的图形与多达90个节点。例如,我们可以证明图中报告的曲线图。6是可以解决的。5事实上,Trager et. al [37]手动计算出其中一个图是可解的。5547可解不可解数据集由suff.的Alg。1Tot.关于NEC的Alg。1Tot.佛牙178 20 198 2 0 217斯堪森克朗179 8 187 13 0 13图6:具有20个节点(左)和90个节点(右)的可解最小查看图的示例。更大/更密集的图将需要太多的计算工作来表征我们实 验 中 使 用 的 计 算 机 ( 具 有 1.4 GHz 处 理 器 的2020MacBook Pro, 8 GB RAM)。尽管如此,我们可以使用我们的方法作为探针来研究它们的局部结构。表4报告了Alg. 1的最小图上的最优解。计算复杂度主要由Gro¨ bner基计算决定,其最坏情况复杂度是变量数的双指数[8]。在我们的实验中,我们随机抽样小的子图的大视图图来自真实的数据集。更确切地说,我们进行如下:i)我们随机选择图的一个节点; ii)确定采样节点的第一个邻域(如果第一个邻域不够,我们还考虑邻居的邻域等等); iii)我们在邻域内随机选择8个节点。除了原始节点之外,这产生了九节点子图。按照这个过程,我们从每个实数图中抽取200个子图,不进行替换。结果报告于表1中。5,告诉我们大多数局部子图是可解的。这给出了关于哪些子图可以在实践中用作用于基于图像的3D重建的增量流水线节点数10 20 30 40 50 60 70 80 90时间1.6秒9 s93年代3分钟15分钟35分钟1小时<2小时4h表4:Alg. 1在一些极小图上。6. 结论和今后的工作我们研究了可解性的观察图,即。他们是否唯一地确定投影相机,并取得了一些重要的进展,在理论和实际使用的观察图。在[37]的基础上,我们提出了一种新的表征,通过利用循环一致性涉及更少的未知数。由此产生的算法是可解性的有效测试(必要和充分条件),由于它,我们对[37]中未决定的所有情况进行了分类,并证明了有限可解性并不意味着可解性,从而回答了一个开放的研究问题。此外,我们能够处理最多90个顶点的最小图,这在阿拉莫136 16 152 48 0 48宪兵广场128 11 139 61 0 61蒙特利尔圣母大学140 12 152 48 0 48纽约图书馆110 19 129 71 0 71皮卡迪利大街109 23 132 68 0 68伦敦塔123 18 141 59 0 59联合广场74 19 93 107 0 107约克明斯特116 14 130 70 0 70康奈尔大学艺术四楼76 23 99 101 0 101表5:具有从一些真实观看图中采样的九个节点的子图的表征[23,6,39]。可解的充分性意味着图满足一个充分条件,即弦[36]。不可解的必要性意味着图不满足某些必要条件[37]。所有其他情况都通过我们的方法解决(Alg. ①的人。未校准的情况下。虽然这还远远没有达到校准案例的成熟程度,但仔细分析小图是很重要的,因为它们是大图的构建块我们可以管理的最大规模是一个设计聪明的求解器和利用计算能力的问题例如,我们计划研究数值代数几何(例如,[9]),这为期望使计算易于处理大规模场景提供了很好的理由本文考虑了Def.图2中所示的方法,其仅基于查看图的拓扑。使用附加信息(例如,点)将产生不同的可解性概念[21],这将是有趣的探索在未来。绘制与校准情况的连接(平行刚性[3])也将是前瞻性研究的一个有趣主题。除了理论上的兴趣之外,可解性问题具有实际影响,因为[30,16]等重建方法将受益于提前知道手头的图是否可解:如果问题是不适定的,那么任何方法都不能返回有用的解。在这种情况下,找到一个可解的极大子图将是非常有趣的。鸣谢。这项工作得到了欧洲区域发展基金IMPACT项目(编号CZ)的支持。02. 1 .一、01{0. 0{0. 0{15 003{0000468}和EUH2020SPRING项目下的方案(第10号)871245)。维也纳主教座堂122 8 130 70 0 70罗马广场114 28 142 58 0 58特拉法加86 16 102 98 0 98巴黎圣母院165 18 183 17 0 17人民广场105 22 127 73 0 73马德里大都会88 28 116 84 0 84埃利斯岛136 30 166 34 0 34南瓜169 22 191 8 1 9沙皇尼古拉一世196 0 196 4 0 4Alcatraz Courtyard 200 0 200 0 05548引用[1] H. S.阿利斯梅尔湾Browning和M. B. Dias 评估机器人立体视觉里程计的位姿估计方法。第11届智能自治系统国际会议(IAS-11),2011年1月。一个[2] E. A. 阿诺德用于计算Gro¨bner基的模块化算法Journal ofSymbolic Computation,35(4):403- 419,2003. 七个[3] F. Arrigoni和A. Fusiello基于方位的网络可定位性:统一的 观 点 。 IEEE Transactions on Pattern Analysis andMachine Intelligence,41(9):2049- 2069,2019。一、二、八[4] F. Arrigoni和A. Fusiello计算机视觉中的同步问题及其封闭解。国际计算机视觉杂志,128:26-52,2020。四、五[5] F. Bernard , J.Thunberg , P.Gemmar , F.Hertel 、 A. 胡施,以及J. Goncalves通过变换同步进行多比对的解决方案。IEEE计算机视觉与模式识别会议论文集,2015年。四个[6] D. Crandall,A. Owens,N. Snavely和D.我是P·赫顿-罗彻 。 基 于 运 动 的 大 型 结 构 离 散 - 连 续 优 化 。 在Proceedings of the IEEE Conference on Computer Visionand Pattern Recognition,第3001-3008页八个[7] D. Cvetkovic,P.Rowlinson和S.西米奇线图的谱一般化:关于具有最小特征值的图-2. 伦敦数学学会讲义系列。剑桥大学出版社,2004。四个[8] T. W. 你好 。多项式理想和Gro¨ bner基的结构SIAMJournal on Computing,19(4):750- 773,1990. 七、八[9] T.达夫角Hill,A.詹森,K。Lee,A. Leykin和J.索姆-马斯。通过同伦连续和monodromy求解多项式系统。IMA数值分析杂志,39(3):1421-1446,2018。八个[10] V. M.戈文杜用于全局一致运动估计的李代数平均。在Proceedings of the IEEE Conference on Computer Visionand Pattern Recognition,pages 684四个[11] D. R. Grayson和M. E.斯蒂尔曼Macaulay2,一个代数几何研究软件系统。可在https://math.uiuc.edu/Macaulay2/ 上 获 得 。七个[12] L. J. Guibas,Q. Huang和Z.梁周期一致网络联合优化的条件数。在神经信息处理系统,第32卷,第1007-1017页,2019年。五、六[13] S.海鸠路径遍历和循环遍历问题的FPT算法。DiscreteOptimization,8(1):61- 71,2011. 五个[14] F.哈拉里图论艾迪生-韦斯利1972年三个[15] R. I. Hartley和A.齐瑟曼。 计算机视觉中的多视图几何。剑桥大学出版社,第二版,2004年。二个[16] Y. Kasten,A. Geifman,M. Galun和R.巴斯里GPSfM:在多视图基本矩阵上使用代数约束的全局投影SFM。在IEEE会议的会议记录中计算机视觉和模式识别,第3259-3267页,2019年。一、二、八[17] T.卡维塔角Liebchen,K. Mehlhorn,D.米海尔河瑞兹T. Ueckerdt 和 K. 茨 威 格 图 表 中 的 循 环 基 数 :Characterization , 算 法 , 复 杂 性 和 应 用 。ComputerScienze Review,3(4):199-243,2009. 五、六[18] D. 拉扎德Gr¨ bner基,高斯消去法和代数方程组的解在J.A. van Hulzen,editor,Computer Algebra,pages 146-156,Berlin,Heidelberg,1983.施普林格柏林海德堡。七个[19] N. Levi和M.沃曼查看图表。在Proceedings of the IEEEConference on Computer Vision and Pattern Recognition,第518 - 522页,2003中。一、二、三[20] A. Nardi,D. Comanducci和C.科伦坡增强视觉:从多个视点通过未校准的视觉传递看到视野和遮挡之外。在Proceedings of the 2011 Irish Machine Vision and ImageProcessing Conference,第38-44页一个[21] B.纳西哈特孔河Hartley和J.川普广义射影重构定理与射影分解的深度约束。International Journal of ComputerVision,115:87- 115,2015。八个[22] D. 你好啊O. Narodits ky和J. 做个将军。 视觉里程计在Proceedings of the IEEE Conference on Computer Visionand Pattern Recognition,pages 652一个[23] C. Olsson和O.恩奎斯特 无序图像集合的运动稳定结构 。 第 17 届 斯 堪 的 纳 维 亚 图 像 分 析 会 议 论 文 集(SCIASpringer-Verlag,2011. 八个[24] O. Ozyesil和A.歌手. 利用凸规划进行鲁棒摄像机位置在Proceedings of the IEEE Conference on Computer Visionand Pattern Recognition,pages 2674一
下载后可阅读完整内容,剩余1页未读,立即下载
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)
![](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)