基于三视图相对摄像机位姿估计的求解方法

12073TRPLP里卡多·法布里里约热内卢州立大学戴维·达科斯塔·德皮尼奥UENFPeter J. 吉布林利物浦大学蒂莫西·达夫佐治亚理工学院埃利亚斯·齐加里达斯INRIA巴黎本杰明·基米亚布朗大学范鸿毅布朗大学Charles W.万普勒圣母大学安东·莱金佐治亚理工学院玛格丽特·H Regan圣母大学Jonathan D. 豪恩施泰因圣母大学托马斯·帕伊德拉CIIRC CTU in Prague†摘要本文提出了一种基于三点一线和两点二线通过两点一线的三视图对应关系的三视图相对摄像机位姿估计的两个最小问题的求解方法。的积分。这些问题都是很难有效解决的最先进的Gr o¨ bner基方法。我们的方法是基于一个新的高效同伦连续（HC）求解器，大大加快了以前的HC解决专门HC方法，我们的问题的一般情况下。我们描述了他们的解决方案的数量，并与模拟实验表明，我们的求解器在图像噪声下是数值鲁棒性和稳定的。我们在实际实验中表明，（i）SIFT特征位置和方向为三视图重建提供了足够好的点和线对应关系，（ii）我们可以解决困难的情况下，太少或太嘈杂的试探性匹配，其中来自运动初始化的最先进的结构失败。1. 介绍3D重建主要依赖于运动恢复结构（SfM）[1，67，23，49]中的点，因此产生了影响[4]。尽管如此，即使是生产质量的SfM技术也失败了[4]联系方式：rfabbri@gmail.com，捷克信息、机器人和控制论研究所，布拉格捷克技术大学。RF由 UERJProcie Benncia 和 FAPERJJover emCientistadoNossoEstado E-26/201.557/2014支持TD和AL由NSF DMS- 1151297支持。JDH和MHR得到NSF CCF-1812746的支持，JDH得到ONR N 00014 -16-1-2722的额外支持，MHR得到施密特科学和工程领导奖学金的额外支持。BK和HF由NSF资助IIS-1910530支持。 TP得到了欧盟区域发展基金IMPACT CZ.02.1.01/0.0/0.0/15 003/0000468和欧盟H2020项目ARtwin 856994的支持。这项工作是在大多数作者在2018年秋季和2019年春季学期期间居住在布朗大学数学计算和实验研究所（ICERM）时发起的图1.用于引导SfM的传统双视图方法的缺陷：没有检测到足够的特征（小红点），因此SOTA SfM流水线COLMAP [67]无法重建相对相机姿态。相比之下，所提出的trinocular方法仅需要三个匹配特征：两个三元组的点切线（具有SIFT方向的点以绿色和青色显示）和一个三元组的没有方向的点（紫色）以重建姿势。红色相机是通过我们的方法计算的，绿色显示地面实况。当图像包含（i）具有很少或没有特征的大的均匀区域时;（ii）重复的纹理，如砖墙，产生大量模糊相关的特征;（iii）模糊区域，由移动的摄像机或物体产生;（iv）大规模的变动，而重叠并不十分显著;或者（v）多个独立移动的对象，每个对象都缺少足够数量的特征。在假设的对应关系上使用RANSAC的双焦姿态估计的失败，例如，使用5个点[48]，在马克杯图像的数据集中突出显示，图1（与[51]中的数据集类似，但没有校准板），其中使用标准SfM流水线COLMAP [63]的故障率为75%。直接应用的失败12074在该示例中使用5点算法甚至更高。 对于包含重复图案的图像存在类似的情况，其中存在大量特征，但是确定对应性是具有挑战性的。大多数传统的多视图管道估计两个最佳视图的相对姿态，然后使用P3P算法[68]配准剩余视图本文的重点是解决传统的双焦点算法在这种情况下失败的问题。双焦点算法的失败促使使用（i）更复杂的特征，即，具有额外的属性和（ii）更多样化的特征。我们提出，方向（在倾斜的意义上）是一个关键属性，以消除歧义的对应关系，我们表明，SIFT方向，特别是跨视图的三焦点姿态估计是一个稳定的功能。方向也可以来自曲线tan-1 [18，17，6]，并且多个视图中直线的方向也会约束姿势。然而，观察到方向不能仅在两个视图中被约束：两个视图中的SIFT方向或线方向是不相关的，但是一起可以识别它们的3D对应物，从而可以约束第三视图中的方向这激发了基于被赋予方向或包括直线特征的点特征的三目姿态估计长期以来，人们认为来自三焦点张量的相机估计增强了双视图姿态估计[21]，尽管最近的研究表明，与双焦点成对估计相比没有显著改进[31]。来自四个点的校准的三目相对姿态估计3v 4p明显难以解决[50，59，60，17]，并且不是最小问题-第一个工作的三焦点求解器[50]有效地将两个相机之间的相对姿态参数化为表示可能的核线的十度曲线然后使用第三视图来选择使重投影误差最小化的核线。从这个意义上说，三目姿态估计还没有真正作为一个最小的问题来解决。三焦点姿态估计需要确定11个自由度：对于每对旋转R和平移t，六个未知数，对于度量模糊性，少一个未知数。三种类型的约束出现在匹配的点特征赋予方向的三元组首先，epipo- lar约束为两个视图中的每对对应提供了一个方程第二，在对应的三元组中，每对对应都需要匹配规模，这提供了另一个约束;每个三元组总共有三个方程很容易看出，非正式地，三个点不足以确定三焦点姿势，而四个点太多了第三，定向特征点的每个三元组提供一个定向约束。因此，对于三个点，仅需要赋予两个点定向，从而针对11个未知量给出总共11个约束我们将三个对应点的三元组的问题称为，其中两个点具有定向特征，“在第二种情况下，即。，使用直线作为特征，对于三个点，仅需要一个自由（未附着到点）直线特征我们把三个三重对应点和一个三重对应自由线的问题称为本文讨论了上述两种场景下的三焦点位姿估计问题，证明了这两个问题都是最小问题，并为所得多项式系统开发了有效的求解器。具体地说，每个问题包括11个三焦点约束，原则上给出11个未知数中的11个多项式的系统。这些系统是不平凡的解决，并需要技术从数值代数几何[9，14，41]（i）探测系统是否超过或低于约束或以其他方式最小;（ii）了解实解个数的范围，并估计一个紧上界;以及（iii）开发有效的和实用的相关方法，用于找到真实的和代表摄像机配置的解决方案。本文表明，芝加哥问题是最小的，有多达312个解决方案（芝加哥的区号是312），其中通常3-4最终成为相关的相机配置。同样，我们证明了克利夫兰问题是最小的，有多达216个解决方案。一般情况下点和线的组合的最小化[15]是与这里提出的更具体的处理方法平行的具有几百个解的多项式方程组的数值求解具有挑战性。我们设计了一个自定义优化的同伦连续（HC）程序，该程序迭代跟踪解决方案，并保证全局收敛[14]。我们的框架专门的一般HC的方法，以最小的问题，典型的多视图几何，从而大大加快了实现。具体来说，我们的芝加哥和克利夫兰求解器不仅是第一个解决这种高程度问题的求解器，而且比解决这种规模问题的求解器快几个数量级：在英特尔酷睿i7- 7920HQ处理器上，四个线程的平均时间为660毫秒。它们共享相同的通用核心程序，并有足够的空间针对特定应用程序进行进一步优化。最重要的是，由于找到每个解是与其他解完全独立的积分路径，因此求解器适合于在GPU上实现，作为RANSAC的批处理，这将通过轨道的数量减少运行时间，即，两个或多个数量级。我们希望我们的开发可以成为解决其他计算机视觉问题的模板，这些问题涉及具有大量解决方案的多项式系统，事实上，所提供的C++框架完全模板化，可以无缝地包括新的最小问题。应当强调的是，作为更昂贵的操作的三焦点姿态估计不旨在作为双焦点估计算法的竞争者相反，在双焦点姿态估计失败的情况下，三焦点方法可以被认为是一种回退选项。12075Y= X+η DηYηXXDDα2αx 2β2αy2αX1D1y1X2D2γy2D2D3y3X2y2X3r2，t2r3，t3实验最初报告复杂的合成数据，以证明该系统是强大的和稳定的空间和方向噪声下，并在显着水平的离群值。真实数据上的实验首先表明，SIFT方向是一个非常稳定的线索，在很大的变化。然后，我们表明，我们的方法是在所有情况下，传统的SfM流水线的成功，但当然在更高的计算成本。至关重要的是，所提出的方法在SfM流水线失败的许多其他情况下取得了成功，例如，在EPFL [70]和Amsterdam Teahouse数据集[71]上，如图9和图10所示。双焦点方案失败-1.1. 文献综述三焦点几何形状校准的三焦点几何形状估计是一个难题[50，59，60，62]。我们知道没有公开可用的求解器。基于四个对应点（3v4p）的最新求解器[50]尚未找到许多实际应用[37]。对于未校准的情况，需要6个点[26]，Larsson等人。最近使用9条线解决了长期存在的三焦点最小化问题[38]。混合点和线的情况不太常见[53]，但在相关问题[63，58，72]中的兴趣越来越大。超过3v4p的校准Kileel [33]研究了许多极小问题在这种情况下，如克利夫兰问题解决了本文，并报告了研究使用同伦连续。Kileel还指出，理想生成器的完整集合，即，一组给定的多项式方程可证明是必要的，并且足以描述校准的三焦点几何形状，目前是未知的。在三个视图中使用曲线和边缘的种子作品传递微分几何用于匹配[5，61]，以及用于姿态和三焦点张量估计[13，66]，超出未校准[24，7]和校准[64，63] SfM的直线。点切线-不要与点射线[11]混淆-可以被框定为箭点（1-箭点），或具有属性方向的特征点（例如，角），最初在未校准的三焦点几何结构的背景下提出，但不强调与一般曲线的切线的连接[30，74]。我们注意到，点切场也可以被框定为向量场，因此相关技术可以应用于表面诱导的对应数据[17]。在校准设置中，Fabbri等人首先将点切线用于绝对姿态估计。[18，19]，只使用两个点，后来放宽未知的焦距[36]。具有三个点切线的三焦点问题作为全局曲线的三焦点姿态的局部版本首先由Fab-bri [17]，在这里作为一个最小的版本代号为芝加哥。同伦延拓多项式同伦延拓（HC）[9，46，69]的基本理论是在1976年发展起来的，它保证了算法从给定的起始解以概率1全局收敛。在过去十年中，许多通用HC软件都得到了长足的发展[8、12、41、73]。计算机视觉社区在90年代将HC最显著地用于曲线和曲面的3D视觉，用于诸如从表面相交计算3D线绘制、在投影下找到3D线绘制的稳定奇异点、计算遮挡轮廓、稳定姿态、通过从奇异点延拓来去除隐藏线、方面图、自校准和姿态估计等任务。10、22、27、28、29、34、35、42、45、54、55、57]，以及对于MRF [10，47]，以及最近的工作[16，25，65]。Pollefeys的Krieg-man和Ponce [34]的早期延拓求解器的实现仍然广泛适用于低阶系统[56]。作为一个早期的例子[27]，HC被用来找到600个解决方案的早期边界，以6条线的三焦点姿态。在视觉社区中，HC主要用作离线工具，用于在制作符号求解器之前对问题进行研究。Kasten等人[32]最近比较了一般目的HC求解器[73]与其符号求解器。然而，他们的问题比这里提出的问题低一个数量级，并且为我们的求解器[14]选择的HC技术比他们使用的多面体同伦更具体，在这个意义上，跟踪的路径更少（c.f.在[69]中的启动系统层次结构）。2. 两个三焦点极小问题2.1. 基本方程我们的符号遵循[24]明确的投影尺度。一个更精细的符号[13，18]可以用来表示方程的切线曲线。图2.三焦点姿势问题的符号。12076设X和Y表示三维点的非齐次坐标，xpv，ypv∈P2表示图像点的齐次下标p为点编号，v为视图编号。如果只使用一个下标，它将为视图编制索引。符号Rv、tv表示从相机1到相机v的旋转和平移变换坐标;d是齐次坐标中的图像线方向或曲线切线;并且D是非齐次世界坐标中的3D线方向或空间曲线切线符号α、β分别表示X、Y的深度，η是距离。对于芝加哥，我们有三倍的点方程（1）和两倍的切线方程（5）。有12个未知数R2，t2，R3，t3和24个未知数αpv，αpv，μpv.对于克利夫兰，我们需要在空间我们将L的一般点记为P+λV，其中点P在L上，L的方向V和实λ。 考虑由它们的齐次坐标π v表示的对应线的三元组，得到背投影平面的齐次坐标为π v=[Rv|[tv]Tv.所有πv都必须包含P和V，对应于位移γ的沿D的沿D。接下来我们用公式表示点的两个最小问题，秩ΣΣ[一|0] T1|[R2|t 2] T2|[R3|t 3] T3<3.第三章。（ 六）线在三个视图中，并推导出它们的一般方程，然后转向具体的公式。我们首先陈述新的最小问题，芝加哥，其次是一个重要的类似问题，克利夫兰。定义1（芝加哥三焦点问题）。在视图v = 1，2，3中，给定三个点x1v，x2v，x3v和两条直线1v，2v，使得pv满足xpv（p = 1，2，v = 1，2，3），计算R2，R3，t2，t3。定义2（克利夫兰三焦点问题）。在视图v=1、2、3中给定三个点x1v、x2v、x3v，并在每个图像中给定一条线x1v，计算R2、R3、t2、t3。为 了 建 立 方 程 ， 我 们 从 点 α1x1=X ，α2x2=R2X+t2，α3x3=R3X+t3的图像投影开始，消除X，得到αvxv=Rvα1x1+ tv ，v= 2 ， 3.（1）通过X的空间直线由它们的点Y =X+ηD，从X向D方向。点Y被投影到图像为βy =X+ηD，βy =R（X+ηD）+ t，方程1和6是克利夫兰的基本方程。有许多方法可以使用这些基本方程的消元法在3.1节中描述了一个基于芝加哥和克利夫兰的消失子式的特殊公式，它产生了我们第一个适用于芝加哥的解算器。2.2. 问题分析一般的相机姿态问题由每个图像中的标记特征的列表定义，这些标记特征是对应的。每个特征的图像坐标被给出，并且我们的目标是确定相机的相对姿态。来自所有摄像机的所有特征坐标的连接列表是图像空间Y中的点，而世界帧或摄像机1中的特征位置的连接列表除非给出某些特征的标度，否则相对平移的标度是不确定的，因此相对平移被视为在射影空间中。 对于N个相机，相机2、. - 是的- 是的 ，N是SE（3）N-1中的点。假设姿态空间为X，投影化的ver-1 1 2 2 2SE（3）N−1的2阶，所以dim X = 6N − 7。鉴于3Dβ3y3=R3（X +ηD）+t3.消除X给出β1y1= α1x1+ ηDβ2y2= α2x2+ ηR2Dβ3y3= α3x3+ηR3D。（二）特征和相机姿态，我们可以通过考虑查看地图V：W×X→Y来计算特征的图像坐标。相机姿势问题是：给定y∈Y，求（w，x）∈W×X使得V（w，x）=y。投影π：（w，x）<$→ x是我们寻找的相对姿态的集合。图像中的线的方向dv，其作为Y的投影减去X的投影而获得，即，β v γ vdv=yv−xv=α vxv+ηD − xv，（3）代入（2）。 去掉D后，我们得到（βv−αv）xv +βv γv dv =Rv（（β1−α1）x1+β1γ1 d1），（四）对于v=2，3.为了进一步简化符号，我们将变量改为μv=βv−αv，μv=βv γv，并得到vxv+ µ vdv= Rv（（五）12077定义3.如果V：W ×，则相机姿态问题最小X→Y是可逆的，并且在一般的y∈Y处是非奇异的。一个映射可逆且非奇异的一个必要条件是它的定义域和值域的维数必须相等。让我们考虑三种特征：点、直线上的点（相当于具有切线方向的点）和自由线（其上没有可区分点的线）。对于每个特征，比如F，让C F是看到它的摄像机的数量。每种特征对暗W和暗Y的贡献如下表所示，其中具有切线的点计为一个点和一个切线。因此，如果多条直线相交于一个点要素，则该点要素具有多条切线。12078`4JJ122j233j3特征尺寸W尺寸Y`3`3点，P32 ·CP切线，T21·CT`5`4自由线，L42 ·CL`2`2因此，将对dimY−dimW的贡献对于所有的特征，我们有以下结果。`1`1.定理2.1 设x= max（0，x）。一个必要条件对于一个N-出现的概率最小的问题是6N−7=P+T+L。对于所有相机都能看到所有特征的三焦点问题，即，C P=C T=C L=3，具有3个特征点和2条切线的姿势问题满足条件。具有3个特征点和1条自由线的姿势问题也满足该条件。向这些问题添加任何新的特征都会使它们受到过度约束，使dimY >dimW×X。为了证明充分性，找到（w，x）∈ W × X就足够了，其中V（w，x）的雅可比矩阵是满秩的随机点（w，x）的这种秩检验用于建立概率为1的非奇异性使用浮点数组-这是高度指示性的，但不严格，除非限制浮点误差，这可以使用区间或精确算法来完成。利用浮点数对雅可比矩阵进行奇异值分解，得到雅可比矩阵有一个远离零的最小奇异值，这可以作为问题是最小的数值证明。类似地，使用数值代数几何技术的仔细计算可以为随机选择的示例计算C中的完整解列表，从而产生问题的代数程度的数值演示。使用这样的技术，我们提出了以下要求，但要注意的是，它们已经被数值证明了。定理2.2（数值）。芝加哥三焦点问题的代数次数为312，克利夫兰问题的代数次数为216。证据前面的段落解释了数值计算，但计算机的确定性证明涉及到对Q上的Gro¨ bner基的符号计算，并有特殊的规定，如补充材料中所讨论的。虽然这个结果与克利夫兰的度计数在[33]中是一致的，但芝加哥的分析是新颖的，因为本文首次提出了这个问题。3. 同伦连续求解器在本节中，我们描述我们的同伦连续求解器。在3.1小节中，我们使用3.1小节中描述的基于微元的方程，将三焦点位姿估计问题重新表述为未知数R2、R3、t2、t3的参数多项式系统，而其他公式将在补充材料中讨论。我们相对地图3.芝加哥和克利夫兰的可见线图良好的运行时间有两个因素。首先，我们使用系数参数同伦，在3.2中概述，这自然地解释了问题的代数次数。已经使用通用软件[8，41]，观察到参数同伦以相对有效的方式解决问题其次，我们优化了同伦延拓程序的各个方面，如多项式求值和数值线性代数。在3.3小节中，我们描述了我们在C++中的优化实现，该实现用于第4节中描述的实验。3.1. 基于子式的建立参数同伦连续求解器的一种方法是将问题公式化如下。芝加哥的一个实例可以由每个视图中的5条可见线来描述我们用齐次坐标中的定义方程来表示每条线，即， 如图1所示，. .，对每个v∈ {1，2，3}，n ∈ 5 v∈ C 3 × 1. 按照惯例，前三条线穿过每个视图中的三对点，最后两条线穿过相关的点切线对，令L=[I |0]T[R |t]Tℓ[R |t ]TℓΣ,(7)对于每个j ∈ {1，. - 是的- 是的 ，5}。 我们通过设置每个Lj的所有3 × 3子式等于零来强制线对应。还必须满足某些公共点约束，即，证明了矩阵[L1]的4×4子式|L2|L4]、[L2|L3|L5]和[L1|全部消失。我们可以用类似的方程来描述克利夫兰问题。 对于这个问题，我们给出了线V，。- 是的- 是的 ，其中v∈{1，2，3}. 我们对矩阵L1，. . .，L4定义为（7）和公共点约束，要求[L1]的4×4子式|L2]、[L1|L3]和[L2|全部消失。两个问题的3.2. 算法从上一节中，我们可以定义一个特定的多项式系统F（R;A），其中未知数R=（R2，R3，t2，t3）由A =（R11，. - 是的- 是的）的情况。我们探索了许多旋转的表示，但我们的主要实现采用了四元数。一个基本的技术解决这样的系统，充分描述在[69]，是系数参数同伦。算法1总结了同伦连续从一组已知的解决方案，12079给定的参数值来计算所需参数值的一组解。它假设一些起始参数A0的解已经通过一些离线从头算阶段计算出来。对于我们感兴趣的问题，起始解的数量正好是问题的代数次数。有几种技术存在的从头算解决。例如，可以使用标准同伦延拓来求解系统F（R;A0）=0，其中A0是随机生成的起始参数[9，69]。该方法可以通过利用方程中的附加结构或使用再生。[14]中描述的另一种基于单值的技术用于获得第3.3节中描述的求解器的一组起始算法1：同伦连续解跟踪器输入：多项式系统F（R;A），其中R=（R2，R 3，t 2，t 3），A参数化数据;开始参数A 0;开始解决方案R 0，其中F（R0;A 0）= 0;目标参数A输出：目标解集R，其中F（R;A）= 0建立同伦H（R;s）=F（R;（1−s）A0+sA0）。对于每个起始溶液，s←−而s1则<选择步长s∈（0，1−s]。预测：从s到s+s的龙格库塔步骤，使得dH/ds= 0。正确：牛顿步圣。H（R;s+S）= 0。s←−s+sreturn计算的解R，其中H（R，1）= 0。3.3. 执行我们提供了一个优化的开源C++软件包，名为MINUS-MINIncidentalproblem这是一个同伦延续代码专门为最小的问题，模板在C++，使不同的问题和不同的配方有效的专业化是可能的。根据我们的实验，最可靠和高质量的求解器使用基于14×14minors的公式。尽管其他公式已经证明了进一步的潜力，加速的数量级，可能有可靠性权衡（c.f.补充材料）。4. 实验首先对合成数据进行了详细的控制研究，然后对真实数据进行了控制实验由于篇幅的限制，我们提出了更具挑战性的芝加哥问题的结果，离开克利夫兰补充材料。1代码可在http://github.com/rfabbri/minus获得合成数据实验：来自[20，18]的合成数据由投影到100台摄像机的4×4×4cm3体积中的3D曲线组成（图4），并进行采样以获得5117个点，这些点被定向（曲线的切线）包围，这些点是相同3D分析点和3D曲线切线的投影[20]，然后用噪声和离群值进行降级。摄像机中心是随机采样的平均球体周围的场景沿正态分布的半径平均1米和σ=10毫米。旋转是通过正态分布的注视方向构造的，其中平均值沿着朝向对象的球体半径，并且σ = 0。01rad，使得场景不离开视口，接着是均匀分布的滚动。 该采样被过滤，使得没有两个相机在彼此的15度范围内。我们的第一个实验研究的数值稳定性的求解器。数据集提供了真正的点对应关系，它继承了从切线到分析曲线的方向对于每个样本集，随机选择三个点对应的三元组，其中两个赋予曲线切线的方向。从输出中选择实数解，并且仅保留生成正深度的实数解。第三个三元组的未使用的切线用于验证解决方案，因为它是一个过约束问题。对于剩余的解决方案中的每一个，确定姿势。将姿态估计中的误差与地面实况进行比较，作为归一化平移向量之间的角度误差和四元数之间的角度误差。生成姿势计算的输入的过程重复1000次并取平均值。该实验证明：（i）姿态估计误差是可忽略的，图5（a）;（2）实数解的个数很少：平均35个实数解，通过强制正深度修剪到平均7个，甚至进一步修剪到平均约3-4个物理可实现的解，使用第三点的未使用的切线作为验证，图5（b）;（iii）求解器在大约1%的情况下失败，这是可检测的，并且虽然对于RANSAC不是问题，但是可以通过以更高的计算成本以更高的精度或更多的参数运行该求解路径的求解器来消除。第二个实验表明，我们可以可靠和准确地确定相机姿态与正确的，但嘈杂的对应关系。使用相同的数据集和子集点和切线的三个三元组的选择-总共200-将零均值高斯噪声添加到具有σ ∈ { 0. 25，0。5，0。75，1。0}个像素，并与切线的方向相关，其中σ∈{0。05，0。1，0。15，0。2}弧度，反映了预期的特征定位和取向定位误差。RANSAC方案确定生成最高特征的特征集。inliers的数量实验结果表明，平移和旋转误差是合理的。图6（顶部）显示了定位误差的程度如何影响姿态（以12080图7.特征位置的重投影误差分布与定位和定向误差的关系。图4.我们的合成数据集的示例视图在我们的实验中也使用了真实的数据集(3D[18]（20）。图5. (a)计算的姿态误差很小，表明求解器是数值稳定的。(b)不同阶段的实解数量的直方图。图6.相机1和2（蓝色）以及1和3（绿色）之间的平移和旋转误差分布，用于不同级别的特征定位（顶部）和方向噪声（底部）。的平移和旋转误差）。图6（底部）示出了在0.5像素的固定局部化误差下定向误差的程度如何影响姿态。更有意义的拒绝误差，即，点到位置的距离图8.不同离群值比例下真实内点的平均重投影误差。由一个三联体中的其他两个点确定，如图7所示，在100个三联体上取平均。第三个实验探讨了当正确的噪声对应与异常值混合时，系统是否能够可靠和准确地确定三焦点位姿。固定特征定位误差为0. 25像素和特征定向误差为0。1弧度，生成200个特征三元组，其中一部分特征三元组被具有随机位置和方向的样本替换。异常值的比例分别为10%、25%和40%，每次重复实验100次。由此产生的重投影误差很小，并且在离群值比率范围内保持稳定，见图8。计算效率：使用我们的软件MINUS的每次求解平均耗时660ms（最差情况下为1.9 s），而使用通用软件[8，41]的最佳pro-totype平均耗时超过1分钟，都是在英特尔酷睿i7- 7920 HQ处理器和四个线程上。如补充材料中所报告的，对微秒进行更真实数据实验：与标准管道非常相似，SIFT特征首先从所有图像中提取。成对的特征是通过对测量的相似性进行排序来找到的，并确保每个特征在另一个图像中的匹配不是模糊的，并且高于可接受的相似性。然后，来自第一和第二视图的特征对与来自第二和第三视图的特征对一起被分组为三元组。循环一致性检查强制三元组也必须支持来自第一和第三视图的一对。然后使用RANSAC选择三个特征三元组，并且三个相机的相对姿态由具有其分配的SIFT方向的两个切线和没有方向的第三点确定。12081图9显示了使用从EPFL密集多视图立体测试图像数据集[70]拍摄的三组图像可靠且准确地找到相机姿态。我们对来自该数据集的150个随机三元组的定量估计给出了 1 的 姿态误差。平移时为5×10−3弧度，3 .第三章。旋转24×10−4平均再现误差为0.31个像素。这些方法与[31]中报道的三焦相对姿态估计方法相当或更好。 我们对这个数据集的结论，其目的是简单地验证求解器，我们的方法至少和传统方法一样好，而且往往比传统方法更好。更多的例子和这一说法的证据见补充数据。请注意，我们并不主张为这个数据集替换trans-task方法。我们只是说，我们的方法同样有效，当然成本更高。EPFL数据集特征丰富，通常每个图像三元组产生1000个三元组特征。因此，它没有描绘在具有挑战性的情况下面临的一些典型问题，当有几个功能可用。阿姆斯特丹茶馆数据集[71]也有地面实况相对姿态数据，描绘了具有较少特征的场景。图10（顶部）显示了来自该数据集的三组图像，其中有足够的特征集（汤罐）来支持双焦点相对姿态估计，然后是第三视图的P3P配准（使用COLMAP [67]）。然而，当特征的数量减少时，如图10（底部）中汤罐被遮挡，COLMAP无法找到这些图像对之间的相对姿态相比之下，我们的方法依赖于三个而不是五个特征，能够恢复这个场景的相机姿势。进一步的结果在补充材料中。我们还创建了另一个类似于[51]中的无特征数据集，但手动移动了校准板。这种场景缺乏点特征，这对传统的运动结构是极具挑战性的。我们在这个数据集中构建了20个三元组的图像。在这20个三元组中，只有5个三元组的相机姿态可以用COLMAP生成，但是用我们的方法，可以估计出20个相机姿态中的10个。我们在图像三元组上的标准管道上实现了100%的改进。图1和图11显示了成功案例的示例。5. 结论本文提出了一个新的标定三焦点极小问题，分析了它的解的个数，并从数值代数几何学的一般计算技巧出发，给出了一个实用的求解器。我们的方法是能够描述和解决类似的困难的混合点和线的最小问题。解决三焦点问题的能力的提高是未来将点和线的多视图几何连接到观察3D曲线时出现的点和切线的多视图几何的更广泛问题的关键，例如，在没有点要素的场景中，使用图9. EPFL数据集的三焦点相对姿态估计。在每一行中，图像样本显示在右侧，结果显示在右侧：绿色为地面实况，红色为估计姿态。图10.美国茶室数据集的三焦点相对姿态估计样本顶行是COLMAP 能 够 处 理 的 图 像 样 本 三 元 组 ; 第 二 行 是 来 自COLMAP失败的图像的三元组。COLMAP的结果是蓝色的，我们的结果是红色的，地面实况是绿色的。图11.针对包括三个杯子的数据集的三焦点相对姿态结果，这对于传统的SfM是具有挑战性的对于每一行，显示图像三元组样本，结果在右侧。地面真实姿态为纯绿色，估计姿态为红色。微分几何[17，20]。我们的“100行定制的解决方案跟踪代码”也将用于尝试改进许多其他最小问题的求解器，这些问题尚未有效地用Gr？bner基解决[39]。12082引用[1] 放大图片创作者：Michael M.Seitz和Richard Szeliski。罗马在一天之内建成IEEE计算机视觉国际会议论文集。IEEE计算机学会，2009年。[2] C. Aholt和L.奥丁理想的三焦点品种。数学比较，83，2014。[3] 阿尔贝托·阿尔扎蒂和阿方索·托尔托拉。三焦点张量的几 何 方 法 。 Journal of Mathematical Imaging andVision，38（3）：159[4] ARKit团队。了解ARKit跟踪和检测。Apple，WWDC，2018.[5] N. Ayache和L.卢斯特曼快速可靠的被动三眼立体视觉。1987年6月，第一届计算机视觉国际会议[6] 丹尼尔·巴拉斯和祖扎娜·库克洛娃。来自两个方向和尺度协 变特 征的单 应性 在IEEE国际 计算 机视觉 会议（ICCV）上，2019年10月。[7] 阿德里安·巴托利和彼得·斯特姆。使用线的运动恢复结构：表示法、三角测量法和光束调整法. 计算机视觉和图像理解，100（3）：416[8] 放大图片作者：Daniel J.豪恩施泰因<美>来华传教士。Sommese，查尔斯W。 万普勒 数字代数几何软件.可在bertini.nd.edu上获得。[9] 放大图片作者：Daniel J.豪恩施泰因<美>来华传教士。Sommese，查尔斯W。万普勒数值求解多项式系统与贝尔蒂尼，第25卷的软件，设备和工具。工业与应用数学学会（SIAM），宾夕法尼亚州费城，2013年。[10] 阿 尔 弗 雷 德 ·M 作 者 声 明 ： Robert J.Holt ， and ArunN.Netravali如何抓住骗子J. Visual Communication andImage Representation，5（3）：273[11] Federico Camposeco，Torsten Sattler和Marc Pollefeys。从两条射线和一个点进行广义姿态和尺度估计的最小解算器。欧洲计算机视觉会议，第202-218页。施普林格，2016年。[12] Tianran Chen，Tsung-Lin Lee，Tien-Yien Li. Hom 4PS-3：基于多面体同伦延拓方法的多项式方程组并行数值求 解 器 。 在 Hoon Hong 和 Chee Yap ， 编 辑 ，Mathematical Software施普林格柏林海德堡。[13] 罗伯托·西波拉和彼得·吉布林。曲线和曲面的视觉运动。剑桥大学出版社，1999年。[14] Timothy Duff ， Cvetelina Hill ， Anders Jensen ， KisunLee，Anton Leykin，and Jeff Sommars.用同伦延拓和单值法求解多项式系统IMA数值分析杂志，39（3）：1421[15] TimothyDuff ， Kathle'nKohn ， AntonLeykin ，andTomasPa-jdla.完全多视图可见性下的点线极小问题。arXiv预印本arXiv：1903.10008，2019。[16] A. Ecker和A. D.杰普森从阴影中得到的多项式形状。2010年IEEE计算机协会计算机视觉和模式识别会议，第145[17] 里卡多·法布里多视图微分几何在计算机视觉中的应用。博士博士论文，工程部，布朗大学，普罗维登斯，RI，02912，2010年7月。[18] 作者：Peter J. Giblin，and Benjamin B.基米亚使用一阶曲线微分几何的摄影机位姿估计。在IEEE欧洲计算机视觉会议论文集，计算机科学讲义。Springer，2012.[19] 作者：Peter J. Giblin，and Benjamin B.基米亚使用一阶曲线微分几何的摄影机位姿估计。IEEE Transactions onPattern Analysis and Machine Intelligence，2019。接纳的话[20] 里卡多·法布里和本杰明·B·基米亚。曲线的多视图几何学。国际计算机视觉杂志，117：1[21] 奥利维耶·福杰拉斯和梁光端多重图像的几何学。麻省理工学院出版社，美国马萨诸塞州剑桥，2001年。[22] O. D. Faugeras，Q. T. Luong和S. J·梅班克摄像机自校准：理论与实验。In G. Sandini编辑，计算机视觉-ECCV施普林格柏林海德堡。[23] 古川康孝和让·庞塞。准确、密集、坚固的多视图立体视觉。IEEE传输模式分析马赫内特尔，32（8）：1362-1376，Aug. 2010年。[24] R. Hartley和A.齐瑟曼。计算机视觉中的多视图几何。剑桥大学出版社，第2版，2004年。[25] Jonathan D. Hauenstein和Margaret H.里根用同伦延拓求解参数化系统的自适应策略应用数学计算，332：19[26] A.海登通过相对深度从图像序列重建。第五届计算机视觉国际会议论文集，ICCV'95，第1058页-，华盛顿特区，美国，1995年。IEEE计算机协会。[27] Robert J. Holt和Arun N. Netravali来自线对应的运动和结构 ： 一 些 进 一 步 的 结 果 。 International Journal ofImaging Systems and Technology，5（1）：52[28] Robert J. Holt和Arun N. Netravali多帧对应的运动和结构解决方案的数量。国际计算机Vision，23（1）：5 -15，May1997.[29] Robert J. Holt，Arun N. Netravali和Thomas S.煌有运用同伦方法解决运动估计问题的经验。第1251卷，1990年。[30] B. Johansson，M Oskarsson，and K.阿斯特罗姆从三个视图中的复杂特征进行结构和运动估计。印度计算机视觉、图形和图像处理会议论文集，2002年。[31] 劳拉·朱莉娅和帕斯卡·莫纳斯。三焦点张量估计的评论。在第八届环太平洋图像和视频技术研讨会斯普林格。[32] Yoni Kasten、Meirav Galun和Ronen Basri。从成对匹配的 相 机 姿 态 的 基 于 结 果 的 增 量 恢 复 。 CoRR ，abs/1901.09364，2019。12083[33] J·基尔校准的三焦点变化问题最小。SIAM Journal onApplied Algebra and Geometry，1（1）：575[34] David J. Kriegman和Jean Ponce。曲线和曲面。章节ANew Curve Tracing Algorithm and Some Appli- cations，第 267-270 页 。 Academic Press Professional ， Inc. SanDiego，CA，USA，1991.[35] David J. Kriegman和Jean Ponce。计算机视觉的几何建模第1610卷，1992年。[36] 尤宾·