这篇博客翻译的是经典全局式SfM的代表性论文《Global Fusion of Relative Motions for Robust, Accurate and Scalable Structure from Motion》，2013年于计算机视觉顶会ICCV上提出，是著名全局式SfM开源库openMVG的原文。

  多视图运动恢复结构（SfM）在一个共同的3D坐标系中估计图片的位置和方向。当以增量方式处理视图时，此外部校准可能会发生漂移，这与残差均匀分布的全局方法相反。我们提出了一种新的基于图像对间相对运动融合的全局标定方法。我们改进了现有的鲁棒计算全局旋转的方法。我们提出了一种有效的对映（contrario）三焦点张量估计方法，可以从中提取稳定而精确的平移方向。我们还定义了一种有效的平移配准方法，可以恢复精确的相机位置。这些组件被合并到原始SfM管道中。我们的实验表明，在大多数数据集上，它的准确性优于其他现有的增量和全局管道。它还实现了惊人的良好的运行时间：它比我们可以比较的其他全局方法快20倍左右，与最好的增量方法一样快。更重要的是，它具有更好的可扩展属性。   

  摄影测量、SLAM（同步定位和映射）和SfM（运动恢复结构）在给定一组图片的情况下重建场景模型。他们计算3D点云（结构）和相机姿势，即位置和方向（校准）。方法可分为两类：顺序（增量式）和全局。

  顺序SfM管道从基于两个或三个视图的最小重建开始，然后逐步将新视图添加到合并的表示中。最广泛使用的增量管道是Bundler。它多次进行束调整（BA），使局部结构和运动固定下来。因此，这是一个相当缓慢的过程。然而，问题的某些部分可以得到更有效的解决。借助词汇树技术，图像匹配可以变得更具可伸缩性。束调整可以使用稀疏矩阵或GPU进行优化。通过消除捆绑调整中的结构（structure），也可以减少变量的数量。最后，一些方法在极线图上使用分而治之的方法来减少计算量。

  然而，由于误差累积和难以处理相机轨迹的闭环，增量方法会受到漂移的影响。另一个缺点是，重建的质量在很大程度上取决于初始图像对的选择和后续图像添加的顺序。

  大多数全局管道通过两个步骤解决SfM优化问题。第一步计算每个视图的全局旋转，第二步计算相机平移以及结构（可选）。分离这两个步骤的好处是，即使对于较小的基线，也可以非常精确地估计相对的两视图旋转，这对于相对平移来说是不正确的。这些方法考虑了整个极线图，极线图的节点表示视图，边连接具有足够多的一致匹配点的视图。图的所有环都会产生多视图约束，在闭环中的连续节点之间的相对运动应该具有一致性。实施这些约束可大大降低增量方法中存在的漂移风险。此外，与增量方法相反，误差可以均匀分布在整个图上。但是，这种全局方法面临这样一个事实，即某些两视图几何中，即使它们有大量的点对应支持，也可能无法反映潜在的全局几何关系，这主要是因为误匹配的存在。例如，重复的纹理结构会产生外点。此外，由于最小化是基于结构和重投影误差，因此即使对于大小有限的图像数据集，空间和时间要求也可能非常大。

  本文针对无序图像集提出了一种新的鲁棒全局SfM方法。使用可以快速合并的相对运动，可以保持较低的问题复杂性。我们首先在局部尺度（2和3个视图）上解决结构问题，然后将得到的相对运动合并到一个通用的全局坐标系中。我们评估了我们的重建管道在具有校准真值的场景和带有错误极线几何的挑战性数据集上的效率和精度。与其他方法相比，我们实现了更好或类似的精度，运行时间显著缩短，可扩展性更好。图1显示了使用我们的管道校准后的mesh结果。

  Estimating global rotations. 考虑到从基础矩阵中提取的视图i和j之间的相对旋转Rij，计算每个视图Ri的全局旋转包括求解所有i、j的系统Rj=RijRi。   这种旋转平均任务可以通过在一个基础闭环上沿所有闭环分散误差来执行。Govindu提出了使用最小二乘最小化进行多视图配准的近似解，Martinec等人重复使用了该近似解，并用半正定规划进行了扩展。或者，平均操作可以在SO(3)李群中进行。Crandall等人使用闭环置信度传播方法，但他们依赖于已知的朝向信息，这不适合一般情况。

  Cycle consistency. 由于相对旋转Rij的估计值可能包含异常值，旋转平均值必须具有稳健性。给定相机极线图，实际任务是识别全局旋转和不一致/异常边（错误的基础几何关系）。有两类方法，基于生成树或循环。生成树方法基于经典的鲁棒估计方案RANSAC。对随机生成树进行采样，并通过遍历生成树时合成相对旋转来计算全局假定旋转。对于保留的构成闭环的边，基于旋转角度RjTRijRi进行评估，测量相对运动和全局运动之间的差异。保留基数最大的那一个。使用的角度阈值为0.25°或1°。   Enqvist等人基于单位阵偏差执行闭环移除。为此，使用内点对数量对图的边进行加权，并提取最大生成树（MST）。考虑由保留边形成的循环。如果一个闭环偏离单位阵足够小，则保留该闭环，偏离由因子1/√l进行归一化，其中l是闭环长度。该方法高度依赖于所选的MST，如果此树错误，则估计的旋转是错误的。   Zach等人基于贝叶斯推理，利用闭环误差检测不正确的相对旋转。对采样树和循环的数量设置限制，以保持问题的可处理性。最大闭环长度设置为6，以避免考虑不确定的闭环长度。

  一旦估计了全局相机旋转Ri，就可以计算全局平移Ti。主要有两种方法，一种是单独计算平移，另一种是与结构一起计算平移。

  Estimating translations alone. Govindu提出了一种从估计的基础矩阵中提取的朝向向量tij中恢复未知平移Ti的方法。他构建并求解关于未知量Ti和相对未知标度因子λij的最小二乘问题：λijtij=Tj-Ti。通过随机采样，他试图找到最能代表全局运动的有效边集。   Sim等人提出了一种基于从三焦点张量中提取的朝向矢量的解决方案，该解决方案将朝向矢量和全局相机位置之间的角度误差降至最低。这种方法的优点是，他们使用紧凑的公式（3×相机变量数），但它们高度依赖于初始平移估计的质量。Arie Nachimson等人使用极线方程的最小二乘极小化来寻找未知的平移。他们的一个明显的缺点是，需要假设使用的所有对应点对中没有异常值对应。此外，Rodríguez等人表明，这种方法既不能处理共线视图序列，也不能处理共享光心的情况。

  Estimating both translations and 3D points. 平移和三维点的联合估计可以用基于l∞范数的二阶锥规划来表示。这种方法依赖于特征点残差的上限约束，并且快速地涉及大量的未知量。它们的计算量大，内存消耗昂贵。由于使用拟凸问题的二等分进行多重凸优化，该解决方案是全局最优的。   Dalalyan等人使用l1约束而不是l2锥来处理异常值。它依赖于两个线性程序，第一个用于识别异常值，第二个用于解决所选内点上的平移和三维结构。它避免了在Olsson等人使用的单步程序中使用非负松弛变量，因为每次测量添加一个松弛变量会随着图像数量的增加而迅速增加问题的大小。   那些l∞问题可以更快地求解。Seo等人通过保证在所有测量残差都在子集的精度之内的基础上，使用一个不断增长的可行子集来找到全局解决方案。这种方法速度更快，因为只有一个子部分的数据被提供给l∞最小化。然而，它对异常值不具有鲁棒性。Agarwal等人测试了不同的二等分方案，并表明Gugat算法收敛到全局解的速度更快。Zach等人使用一种近似方法来加速此类凸问题的最小化。

  Other approaches. Martinec等人多次使用他们的全局管道来迭代丢弃具有最大残差的两视图几何对。为了保持良好的运行时间，他们仅在几个点对上计算平移和结构：每个极线几何体仅由4个点表示。Courchay等人使用极线图上的三焦点张量树的线性参数化来求解相机位置。该方法仅限于一个闭环。   

  我们的输入是一组无序的图片{I1，…，In}。假设每个相机的内参Ki已知：我们的目标是从图像Ii和Ij之间的相对相机运动（旋转Rij和朝向平移向量tij）稳健地恢复每个相机的全局姿态（绝对运动旋转Ri和平移Ti）。

  我们的贡献如下：

  为了匹配分别位于图像Ii和Ij中的点X和X‘，两视图极线约束可以写为：

  Nistér的五点算法作为最小解算器插入RANSAC程序中，由于尺度是任意的，因此可以稳健地估计本质矩阵Eij=[tij]×Rij，从中可以提取Rij以及方向tij。实际上必须测试四种不同的运动（Rij、tij），保留产生最大点数的点，以满足cheirality约束（3D点的正深度）。需要注意的是，与平移方向相反，旋转精度几乎对基线长短不敏感。此外，虽然连接视图之间的相机旋转可以链接，但相对平移不能链接，因为它们在不同的未知比例因子λij下可用。

  我们使用Zach等人的边缘消歧法来识别图中不一致的相对旋转。由于初步实验表明，许多离群旋转可以通过Zach等人的测试，我们进行了两项改进。首先，我们利用Enqvist等人的结果调整了闭环误差概率，通过因子1/√l对误差进行加权，其中l是闭环的长度。其次，我们使用Zach等人的算法，直到没有更多的边缘被贝叶斯推理过程去除。最后，我们检查图的所有三元组，并拒绝闭环偏差大于单位阵2°的三元组。 表1中的实验表明，在第一次贝叶斯推断之后，一半的异常值可以保留下来，这激发了我们的迭代消除方法。

  按照Martinec等人的方法计算全局旋转，通过最小二乘法最小化，试图满足方程Rj=RijRi，然后计算最近的旋转，以覆盖最小化过程中缺少正交性约束的情况。   

  为了提高计算相机之间相对运动时的稳健性和准确性，我们考虑三视图，而不是像往常一样考虑成对视图。我们在第3.2节中显示，这会在估计的平移中产生一个数量级的精度跳跃。   

  根据第2节中计算的估计全局旋转Ri，我们使用自适应RANSAC程序估计“简化”三焦点张量，以对异常相关响应具有鲁棒性。我们没有像Sim等人那样用闭环形式的解来最小化代数错误，而是最小化3D点Xj与其在三幅图像中的观测点{(xij，yij)}i∈{1,2,3}的l∞重投影误差：

  其中，ti是视图i和tim及其组成部分的平移。张量由该线性规划的可行性得出：   第二个约束确保所有三维点位于相机前面，第三个约束定义了三视图局部坐标系的原点。

  通常，使用线性规划会导致两个问题。首先，随着变量数量的增加，求解时间呈多项式增长。其次，对异常值的鲁棒性通常是通过松弛变量实现的，这使得问题更庞大。

  我们的方法包括使用小型线性规划作为最小解算器计算张量，在三个视图中有四个跟踪点，并结合AC-RANSAC框架，以对噪声和异常值具有鲁棒性。RANSAC的这种变体依赖于一种逆向（AC）方法来计算内部/离群点判别的自适应阈值：如果一个配置在随机环境中的观察结果是意外的，则认为该配置是有意义的。而全局l∞最小化旨在找到具有最低γ值的解决方案，通过二分发现，AC-RANSAC确定错误警报（NFA）的数量满足如下关系：

  式中，M是最小求解器使用四个随机对应获得的测试三焦点张量，γ=0.5像素，n是三元组中对应点的数量，其中ek=εk/max(w,h)取决于第k个误差：   在这些公式中，w和h是图像的维数，ek是一个点具有某重投影误差的最大概率εk。 Xj由对应点{(xij，yij)}i∈{1,2,3}的最小二乘三角剖分得到。k表示假定的内点数。因此，在等式(4)中，ek(M)k−4是k−4个三幅图像（我们的背景模型）中均匀分布的独立对应点的最小重投影误差中的最大概率εk、 类似于等式(3)中对于内点的最佳γ的作用。(4)中的其他项定义了n−4个剩余点中的k个内点子集数量。因此，NFA(M,k)是具有最大误差γ=εk的随机对应期望。如果出现以下情况，则认为三焦点张量M有意义（不太可能因为偶然情况出现）：

  在实践中，我们最多抽取4个对应的N=300个随机样本，并评估相关模型的NFA。正如Moisan等人所述，一旦发现有意义的模型M，我们就停止并通过在M的内点中重新采样N/10次来精化它。如果没有样本满足(6)，我们丢弃这个三元组。最后，我们通过捆绑调整来精化平移和k个3D内点。

  表2评估了我们的鲁棒对消三焦点估计的计算时间和精度，与合成配置上具有松弛变量的等效全局估计相比。在每个完美对应中加入均匀的1像素噪声，并引入2%的异常值。我们评估了结果的准确性（真值和计算出的平移之间的角度误差）以及找到解决方案所需的时间。全局解决方案找到了一个适合数据噪音的解决方案，但AC-RANSAC能够更进一步，找到更精确的解决方案。   

  在Enqvist等人关于双视图旋转精度的实验之后，我们证明使用三焦点张量可以显著改善相对平移估计。为了评估小基线的影响，进行了一个简单的综合实验。在[−1,1]3的立方体和3个相机放置在距离为5，角度为0°、α和2α的圆上（见图2，左图）。我们将α从1°变到20°来模拟中小型基线。将均匀的1像素噪声添加到图像投影中。使用AC-RANSAC和5点解算器（本质矩阵）以及具有已知旋转的AC-RANSAC三焦张量估计相机的相对平移。我们比较了三个相对平移方向的角度误差w.r.t.地面真值（因为重建比例是任意的），并将结果平均50次（见图2，右图）。随着基线的增加，两种方法的精确度都会提高。然而，我们的三焦点估计性能要好得多，即使在较小的基线下也有很好的结果。   

  给定一组相对运动对(Rij, tij)（旋转和平移方向），我们希望找到所有相机的全局位置（T1，…，Tn），如图3顶部所示。因此，我们正在寻找n个全局平移和#tij个比例因子λij，它们将不同的平移方向协调到全局坐标系中：

  由于噪声影响，通常无法精确满足方程组（7），但可以在最小二乘意义下优化线性方程组的解。问题是，使用这个公式，λij不能被约束为正，以满足cheirality约束。

  我们的方法包括在l∞范数下优化等式（7）。由于解在平移和缩放下是不变的，通过在λij（缩放模糊度）上添加正约束并将第一个相机设置在原点（平移模糊度）来移除自由度。以下线性规划产生全局最优解：   在我们的例子中，如果一个给定的(i, j)属于几个三元组，我们可能会有不同的平移方向tij（见图3，顶部）。因此，我们考虑tτij对于包含(i, j)的三元组τ。此外，相对尺度是每个三元组（λτ）而不是每条边（λij）。我们实际上解决了以下问题：

  与Govindu的方法相比，该方法不强制要求符合cheirality条件，我们肯定会找到一个全局最优解。此外，我们在这里最小化了一个线性规划，它比Sim和Hartley的SOCP快得多。他们使用角度误差，而我们的方法使用欧几里德距离（见图3，底部）涉及更简单的约束。   

  现在，我们将展示如何在管道中使用这些元素来执行稳健和准确的全局校准。该方法包括以下步骤：（1）建立匹配图像对的极线图，并估计本质矩阵；（2）检查旋转一致性，在图上执行贝叶斯推断，并在生成的图上计算全局旋转；（3）计算三焦点张量的相对平移；（4）在全局坐标系中注册平移；（5）计算粗略的三角化结构，并通过捆绑调整优化旋转、平移和结构。

  Step 1: relative pairwise rotation. 我们使用SIFT匹配和稳健的反向本质矩阵估计。可能的反向精度上限设置为4像素。外极线图实际上分为两个边连接的组件，可以为其计算单独的全局校准。生成的姿态和结构稍后将基于标准姿态估计/后方交会进行合并（旋转、平移、缩放）。

  Step 2: rotation consistency. 我们使用我们的自适应贝叶斯推理来去除异常旋转（见第2节）。如步骤1所示，必要时检查并清理极线图。我们将图中长度为3的圈列为可能的三元组。具有链式旋转且与单位阵的角度偏差大于2°的被丢弃。最后，使用Martinec等人所做的稀疏特征值解算器计算全局旋转，该解算器的效率与最小化过程中约束正交性的效率相同。

  Step 3: relative motion computation. 我们在已知旋转后计算图的每条边的相对平移估计。为此，我们首先建立一个所有图边的列表。然后，对于每条边，我们尝试按照第3节中所述的方法求解边所属轨迹的最大支持度的三元组。使用快速联合查找方法计算轨迹。如果三元组已解，我们将确定属于张量的三条边，并将其从列表中删除。如果三焦点张量估计失败，我们将继续使用包含此边的其他三元组（如果有），按轨迹数的降序排列。当边列表为empy时，进程停止。这一步不仅可以找到相对平移，还可以确定每个三元组的连贯3D结构。这种方法的一个优点是可以并行计算三元组。这种方法需要一个由连续三元组覆盖的图，这可能并不总是适用的。然而，在实践中经常出现这种情况，部分原因是特征检测器的重复性不断提高。

  Step 4: translation registration. 我们集成了相对平移方向，并使用第4节的l∞方法计算全局平移。

  Step 5: final structure and motion. 前面的步骤很好地估计了运动以及每个三元组的结构。我们通过特征跟踪将这些结构中的点连接起来，并通过三角剖分计算每条轨迹的3D点位置。然后，使用Ceres解算器通过捆绑调整（BA）对该全局结构和平移进行优化。有趣的是，BA在几次迭代中收敛，这评估了我们初始估计的质量。最后一个BA用于优化结构和相机旋转和平移，以处理步骤2的噪声旋转估计。在这两个步骤中，首先是固定旋转的部分BA，然后是全局BA，其灵感来自Olsson和Enqvist的方法。这个想法是为了防止在第一步中通过旋转调整来补偿平移错误，因为旋转更可靠。根据我们的实验，两级BA提高了精度。   

  为了评估我们的方法，我们使用了Strecha等人的基准，它提供了相机位姿真值。我们还试验了具有多个错误对极几何的具有挑战性的数据集，主要是由于重复的部分。我们比较了Bundler和VisualSfM这两个增量式方法，以及Olsson、Enqvist和Arie-Nachimson这三个全局式方法。除Arie Nachimson方法只有已公布的结果可用外，所有报告的数据都是通过作者的软件在8核2.67 GHz机器上获得的。

  Sensitivity to rotation noise. 为了研究我们的全局平移估计关于带噪声的全局旋转的敏感性，我们将喷泉数据集的真值旋转作为平移注册过程的输入，该旋转由一个小的随机旋转所驱动，该旋转的轴在球体上均匀采样，其角度在0和给定的最大角度之间均匀绘制。图4显示，最终误差几乎与噪声水平呈线性关系。Sim和Hartley给出了类似的结果。

  Accuracy. 表3（左）显示了Strecha等人数据集上几种增量和全局方法的平均基线误差。3D相似变换将真值和计算的坐标系进行了配准。虽然在前四个数据集上，我们的精确度略好于或可与最佳结果媲美，但在以庭院中的环路为特征的城堡数据集上，我们的精确度明显优于最佳结果。原因之一是很好地拒绝了异常数据（错误的点对应和错误的极线几何）。

  Running time. 表3（右）报告了极线图计算后校准的运行时间（相机姿态和3D结构的估计）。我们的全局方法比Olsson和Enqvist（Matlab代码，对时间影响大的关键部分使用C++）的速度快5到11倍（并行化时为16到26倍）。它甚至可以与GPU和多核优化的最快增量方法竞争。

  Challenging datasets. 我们使用具有重复或类似场景部分（类似的立面，包括镜像）的数据集进行测试，这会导致极线图中出现错误的几何关系。我们展示了初始图、通过重复贝叶斯推理去除错误边的图以及相机位置。对于Orangerie数据集（61幅图像，见图5），Bundler无法实现闭环，并且错误放置了多个视图，这与我们的方法相反。对于Opera数据集（160幅图像，见图6），运行时间（在特征检测和匹配之后）有着显著的不同：Bundler在3小时内运行，而我们在7分钟内校准（并行版本为4分钟）。事实上，Bundler在重复捆绑调整（BA）中花费了大量时间；虽然第一张照片用时不到一分钟，但最后一张照片用时大约十分钟。我们的运行时间和剩余信息详见表4。   

  我们提出了一种全局式的运动恢复结构系统，用于从无序图像集进行大规模三维重建。我们已经证明，全局校准可以通过全局合并局部相对估计，在确保可扩展性的同时保持鲁棒性和准确性来执行。此外，我们还表明，已知旋转的相对平移三元组可以在可承受的计算时间内以良好的自适应精度进行计算。这些结果得到了理论论证以及合成数据集和真实数据集的实验比较的支持。

  我们的管道有许多优点。它通过在三焦点级别合并轨迹来计算稳定的结构，几乎没有异常值（合并错误的对极几何的风险较小）。由于链是全局的，因此不需要提供初始对，即增量方法中问题严重的初始种子。由于相关平移估计的良好质量，即使在通过捆绑调整进行细化之前，全局平移的精度也可以很好地概述相机位置；我们不需要为此计算场景的全局结构。捆绑调整执行的迭代次数非常少，这就证实了这一点。我们的实验表明，限制全局方法精度的问题是全局旋转的精度。我们相信，只要有足够的RAM用于最终的捆绑调整（可选），我们的方法甚至可以在标准计算机上在城市规模上工作。   

  下面介绍了我们的全局式运动恢复结构的实验结果。对于每个数据集，给出：