OpenMVG论文——《Global Fusion of Relative Motions for ... Structure from Motion》论文阅读笔记
这篇博客是对经典的全局结构从运动（SfM）论文《Global Fusion of Relative Motions for Robust, Accurate and Scalable Structure from Motion》的翻译。于2013年发表在计算机视觉顶级会议ICCV上，并作为开放源代码库openMVG的基础内容发布。
- 论文地址：https://www.cv-foundation.org/openaccess/content_iccv_2013/papers/Moulon_Global_Fusion_of_2013_ICCV_paper.pdf
- 论文代码：https://github.com/openMVG/openMVG
Abstract
在同一个三维坐标系中进行多视图运动恢复结构（SfM）的估计工作。当以增量方式处理每一幅图像时，在全局方法中出现的残差均匀分布的情况将被外部校准漂移所取代这一现象值得关注。我们开发了一种基于图像对间的相对运动融合的新全局标定方法，并对其进行了改进以增强计算效率和鲁棒性。为了提高全局旋转计算的准确性我们引入了一种新的三焦点张量估计方法其能够有效提取出稳定的平移方向信息并在此基础上设计了一种精确可靠的平移配准算法这一算法能够恢复出相机在三维空间中的精确位置参数这些核心组件已经被成功整合到现有的SfM流程之中
1 Introduction
基于一组图片构建场景模型的过程中应用的摄影测量技术、同时定位与 mapping (SLAM) 和结构从运动恢复 (SfM) 方法均用于计算三维点云的几何结构以及相机姿态及其方向定位（内参数校正）。这些方法主要分为基于顺序增量式的逐步构建以及全局一次性完成的整体恢复两种类型
顺序SfM管道从基于两到三个图像的初始重建阶段开始，并在此基础上逐步整合新的图像进而在构建整体表示的过程中不断优化。其中最常见采用的是Bundler工具其通过反复实施BA优化程序来固定局部结构和运动从而实现稳定的结果但这一过程进展缓慢。然而部分问题仍可通过更高效的方式加以解决借助词汇树技术我们可以显著提升图像匹配算法的可扩展性同时还可以结合稀疏矩阵或GPU架构来加速计算速度进而提高处理效率最后一种优化策略则是通过去除束调整中的结构信息从而减少自由度数量以达到简化计算的目的
但是归因于误差积累以及难以处理相机轨迹的闭环问题，增量方法会受到漂移的影响。此外存在的另一个缺点是，在很大程度上重建的质量主要取决于所选初始图像对的数量以及后续图像添加的具体顺序。
大多数全局管道采用两步策略来解决SfM优化问题。第一步是计算每个视图的全局旋转；第二步则是计算相机平移以及结构（可选）。将这两步分开处理带来的好处是：即使对于较小的基线也能非常精确地估计相对两视图之间的旋转关系；这对于相对平移而言并不成立。这些全局方法利用了整个极线图的信息；其中每个节点代表一个视图；边则连接那些具有足够多一致匹配点的视图节点。所有环路都会产生多视图约束条件；在闭环中的连续节点之间应具有相对一致性关系。应用这些约束条件能够显著降低增量算法所面临的风险；同时误差可以在整体图像中得到均匀分布。然而这种全局性方法也面临着一个关键挑战：即使某些两视图几何关系拥有大量支持点也无法反映潜在的整体几何关系；这是因为误匹配现象的存在会导致这种状况发生。例如：重复出现的纹理图案会产生外点干扰；此外由于最小化过程基于结构信息和重投影误差评估标准；因此即便面对有限大小的数据集空间需求和时间复杂度也可能变得很高
该研究针对无序图像集合提出了一种新型的鲁棒全局单应矩阵估计方法。通过可高效融合的相对运动参数,该方法能够维持较低的问题复杂度。随后,我们在局部层次(涉及2至3个视图)构建结构模型,并随后将获得的所有局部分析结果整合到统一全局参考系中完成整体估计。为了全面验证该算法的有效性,我们分别在其校准准确的真实场景下以及在存在误置极线几何条件下的复杂数据集上进行了两次详细评估:首先是在具有精确校准信息的理想场景中进行评估;接着是在存在误置极线几何条件下的复杂数据集上测试重建性能。实验结果表明,相较于现有方法,我们的算法在精度上达到或超越现有水平;同时运行效率提升了显著程度,并且展现出良好的扩展性特征。具体而言,图1展示了经过该算法校准后的三维网格建模结果
1.1 Related work
本研究致力于估计全局旋转。基于从基础矩阵中获取的不同视图i与j之间的相对旋转量R_ij，在计算每个视图R_i的整体旋转变换时，默认假设其满足方程组 R_j = R_ij R_i 对所有i,j成立。此平均旋转变换问题可通过在全局基准框架下沿着闭链分布的方式实现误差分配。 Govindu提出了一种基于最小二乘法逼近的方法用于多视角配准。 Martinec等学者持续改进了这一近似解决方案，并结合半正定规划技术实现了更高的精度。 或者说采用在SO(3)李群上的优化方法来处理这个问题。 Crandall等人的工作则采用了基于闭环置信度传播的方法以达到一致估计的目的
Cycle consistency. 由于相对旋转Rij的估计值可能包含异常值，旋转平均值必须具有稳健性。给定相机极线图，实际任务是识别全局旋转和不一致/异常边（错误的基础几何关系）。有两类方法，基于生成树或循环。生成树方法基于经典的鲁棒估计方案RANSAC。对随机生成树进行采样，并通过遍历生成树时合成相对旋转来计算全局假定旋转。对于保留的构成闭环的边，基于旋转角度RjTRijRi进行评估，测量相对运动和全局运动之间的差异。保留基数最大的那一个。使用的角度阈值为0.25°或1°。
Enqvist等人基于单位阵偏差执行闭环移除。为此，使用内点对数量对图的边进行加权，并提取最大生成树（MST）。考虑由保留边形成的循环。如果一个闭环偏离单位阵足够小，则保留该闭环，偏离由因子1/√l进行归一化，其中l是闭环长度。该方法高度依赖于所选的MST，如果此树错误，则估计的旋转是错误的。
Zach等人基于贝叶斯推理，利用闭环误差检测不正确的相对旋转。对采样树和循环的数量设置限制，以保持问题的可处理性。最大闭环长度设置为6，以避免考虑不确定的闭环长度。
一旦确定了全局相机旋转参数R_i之后，则可以随后计算相应的全局平移值T_i。主要涉及两种不同的技术手段：一种是采用独立计算的方式进行平移求解；另一种则是将平移计算与结构分析同步完成
Estimating translations alone. Govindu提出了一种从估计的基础矩阵中提取的朝向向量tij中恢复未知平移Ti的方法。他构建并求解关于未知量Ti和相对未知标度因子λij的最小二乘问题：λijtij=Tj-Ti。通过随机采样，他试图找到最能代表全局运动的有效边集。
Sim等人提出了一种基于从三焦点张量中提取的朝向矢量的解决方案，该解决方案将朝向矢量和全局相机位置之间的角度误差降至最低。这种方法的优点是，他们使用紧凑的公式（3×相机变量数），但它们高度依赖于初始平移估计的质量。Arie Nachimson等人使用极线方程的最小二乘极小化来寻找未知的平移。他们的一个明显的缺点是，需要假设使用的所有对应点对中没有异常值对应。此外，Rodríguez等人表明，这种方法既不能处理共线视图序列，也不能处理共享光心的情况。
同时估计平移参数和三维空间中的点坐标。该方法基于基于l∞范数的二阶锥规划模型来进行表示，并且这种方法依赖于特征点残差的上限约束条件，在处理大量未知量时表现出较高的计算效率。然而由于其计算量大且内存消耗高这一缺点限制了其应用范围。为了克服这一缺陷团队采用了分阶段优化策略即通过将问题分解为多个子问题逐步逼近全局最优解从而实现了较好的计算效果。
而Dalalyan团队则采用l1范数约束替代了基于l2锥的优化方法以应对异常值这一挑战。这种选择使得他们的算法在识别异常值并进行内点优化时更加鲁棒并且避免了Olsson等人所采用的单步程序中对松弛变量数量迅速增加所带来的计算复杂度上升问题。
对于那些基于l∞范数的问题而言，在求解速度上具有显著优势。Seo等人提出的算法通过引入动态可行子集策略能够在不保证所有测量残差精度的前提下快速找到全局最优解这一特性使其在处理大规模数据时展现出良好的性能特征然而这种方法对异常值较为敏感缺乏鲁棒性。
Agarwal团队则通过引入多种二等分方案对比分析表明Gugat算法在收敛速度方面表现更为突出这为后续研究提供了新的思路。
Zach等人则提出了一种近似优化方法旨在加速类似凸规划模型下的最小化过程从而进一步提升了算法的实际应用效率。
Other approaches. Martinec团队反复利用全局管道以剔除具有最大残差的两视图几何对。为了优化运行效率，在几个关键点对上计算平移与结构；每个极线体仅由四个关键点定义。Courchay团队则采用极线图上的三阶张量树进行相机位置的一致性求解。这种方法受限于单一闭环的设计。
1.2 Our global method for global calibration
数据集是我们所处理的一组未排序图片{I1,…,In}。假设每个相机的内参数已知：我们旨在从图像对(Ii,Ij)中稳定且可靠地恢复所有相机的全局姿态。
我们的贡献如下：
- 我们的实验结果显示，在反复使用Zach等人的贝叶斯推断，并根据Enqvist等人的闭环长度权重进行优化后，能够有效地去除图中的大多数异常边。
- 我们开发出了一种基于l∞范数的三焦点张量估计方法，并构建了一个线性规划问题用于自适应RANSAC算法中的最小解算器。该方法计算速度快且结果可靠。
- 我们又开发出了一种新的平移配准方法，同样基于l∞范数构建了一个有效的线性规划。
- 将这些关键组件整合进一个SfM管道中去，在这一管道中首先通过清除极线图来消除异常值；接着利用相对值计算全局运动。经过实验证明该系统具有稳定可靠、精确且具扩展性的性能。
2 Robust estimation of global rotations
为了匹配分别位于图像Ii和Ij中的点X和X‘，两视图极线约束可以写为：
Nister's five-point algorithm has been introduced as a minimal solver into the RANSAC program, capable of robustly estimating the essential matrix E_ij = [t_ij] × R_ij under arbitrary scales, thereby obtaining the rotation matrix R_ij and direction vectors t_ij. To ensure accurate results, it is necessary to test four different motion configurations (comprising different R_ij and t_ij combinations) and select the configuration that yields the maximum number of corresponding points while satisfying cheirality constraints (3D point positive depths). Notably, the algorithm demonstrates insensitivity to baseline length variations when considering opposite translation directions. Additionally, while relative rotations between cameras can be constrained across multiple views using known relative orientation relationships, absolute translations remain unobservable since they are scaled by unknown parameters λ_ij in each camera pair.
在本研究中采用Zach等人提出的消除方法来判别图像中存在的相对旋转不一致性。基于初步实验结果显示，在应用Zach等人提出的测试方法时能够识别出大量离群旋转值。为此我们进行了两项系统性改进工作：首先基于Enqvist等人研究的结果对闭环误差概率进行了优化设置，在计算误差时采用了1/√l因子对误差值进行加权处理（其中l代表闭环路径长度）。其次我们采用了类似于Zach等人提出的方法迭代优化贝叶斯推理过程直至系统收敛稳定状态（即当贝叶斯推理不再剔除任何剩余边限时停止迭代）。最后我们在图中所有三元组关系中统计检验偏差超过单位阵2°的数据项并予以剔除。表1中的实验结果显示经过首次贝叶斯推断处理后约有一半的异常数据仍然存在这促使我们进一步开发了一种迭代消除算法以逐步去除这些异常值最终达到优化数据质量的目的
基于Martinec等人提出的方法进行全局旋转计算，并通过最小二乘法进行优化以寻求最接近的结果；旨在满足方程Rj=RijRi后，并进一步计算最接近的旋转矩阵以弥补上述过程中因缺乏正交性约束而导致的问题。
3 Relative translations from trifocal tensors
旨在提升相机间相对运动计算的稳健性和准确性，在本研究中我们采用三视图方法而非依照传统成对视图的方法进行处理。在第3.2节中展示的结果表明，在平移估计中的显著提升将由此方法实现。
3.1 Robust trifocal tensor with known rotations
基于第2节中计算得到的全局旋转参数Ri，在本研究中采用了一种自适应型RANSAC程序来估算简化的三焦点张量。这一方法相较于Sim等人所采用的方法，在于它并未采用闭式解法来最小化代数误差；相反地，则通过直接最小化了三维点Xj与其在三个图像中的观测点{(xij,yij)}（其中i属于{1,2,3}）在l∞范数下的重投影误差而实现对异常相关响应的有效抑制。
其中，ti代表视图i与其对应的Tim及其组成部分的平移操作。张量基于该线性规划问题的可行解而存在：
第二个约束保证每一个三维点都处于相机的前方区域；第三个约束则确定了三视图局部坐标系的具体位置。
通常，在应用线性规划时会遇到两个主要挑战。首先，在实际操作中可能会面临计算资源限制的问题。其次，在数据处理过程中如何保证算法稳定性和可靠性是一个需要深入研究的关键点
我们的方法采用小型线性规划作为核心组件用于张量计算，在三个不同的视角中设置了四个跟踪点，并结合了与AC-RANSAC框架。该框架具备抗噪声和异常数据的能力。RANSAC的一种变体依赖于一种逆向（即自反）机制用于确定内群与外群区分的标准：当某组配置在随机噪声环境中表现出异常时，则判断其为有效的内群。另一方面，全局l∞范数最小化算法则致力于寻找最优解...
式中
在这些公式中,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组对应样本，并确保每组包含300个随机样本，并计算这些模型的NFA指标。如Moisan等人所言，则立即停止，并在此基础上，在M内部点处进行额外重采样（每次重采样的数量为当前样本总数的十分之一）以进一步优化。如果所有重采样后的样本均不满足条件（6），则放弃该三元组。最后，在优化过程中采用捆绑调整策略以进一步精化平移参数以及k个关键三维内点的位置。
本研究通过表2对比实验表明，在计算时间和精度方面对比实验表明，在计算时间和精度方面对比实验表明，在计算时间和精度方面
3.2 Relative translation accuracy
在Enqvist等人的双视图旋转精度实验基础上
在Enqvist等人的双视图旋转精度实验基础上
4 Translation registration
假设有一组相对运动对(R_{ij}, t_{ij})包含着旋转和平移信息，则我们需要确定所有相机在全局坐标系中的位置参数(T_1, \dots, T_n)。如图3所示顶部部分所示，在该场景下我们关注的是确定n个整体平移参数以及与之对应的\lambda_{t_{ij}}比例因子。这些参数用于将各个局部平移关系整合到统一的全球坐标系统中：
因为观测噪声的影响，在实际应用中很难保证能够完全满足方程组（7）。然而，在最小二乘法框架下寻求线性方程组解的最佳逼近仍然是可行的策略。一个主要的问题是该方法试图通过固定公式计算λ_ij值时无法强制使其保持正值状态以满足chirality约束。
我们采用的方法基于l∞范数下的等式（7）求解。考虑到解在平移和缩放变换下的不变特性，在λij（表示缩放模糊度）上施加正约束，并将第一个摄像头固定于原点位置以消除平移模糊度参数的影响后展开计算。所建立的线性规划模型能够得到全局最优解
在我们的示例中，在给定的一对(i, j)涉及多个三元组的情况下，则会存在不同的位移向量t_ij（如图3所示）。因此，在这种情况下，则会考虑使用参数t_τ_ij来表示这些包含(i, j)的三元组。值得注意的是，在计算过程中，则会采用的是每个三元组对应的权重λ_τ而非每条边对应的权重λ_ij。我们实际解决的问题则是：
相比Govindu的方法而言，在这里我们不需要强制满足chirality这一条件，并且必然能够获得全局最优解。此外，在本节中我们将最小化一个线性规划问题,这一方法相较于Sim和Hartley所提出的SOCP方案具有显著的速度优势。其他研究者则采用角度误差作为度量标准,而我们的方法则基于欧几里德距离进行建模（如图3所示,位于下方）。这种方法引入了更为简便的约束条件。
5 The global reconstruction process
我们现在将演示如何在管道系统中利用这些元素实现稳健且精确的全局校准。该方法系统地包含以下几个关键步骤：首先，在管道模型中创建匹配图像对并构建其极线图的同时估算出两镜头间的本质矩阵；其次，在系统图形上验证各子相机组间的旋转一致性，并在此基础上执行贝叶斯推理以确定整体旋转角度；第三步，则利用三焦点张量计算各子相机间的相对平移关系；第四步，在整个物体空间坐标系下完成各局部坐标系与整体坐标系间的精确对齐；最后，在初始解的基础上应用约束优化技术进一步提升各参数的一致性和精确度。
Step 1: relative pairwise rotation.
步骤二：确保旋转一致性
Step 3: relative motion computation.
第4步：实现全局平移。 我们集成了相对平移方向，并采用本节所述的方法计算出全局平移量。
第五步：最终结构与运动
6 Results
为了评估该方法的效果, 我们采用了基于Strecha等人提出的基准, 该基准提供了相机位姿的真实值作为参考指标。在此基础上, 我们进行了包含多个复杂对极几何配置的数据集测试, 这些具有挑战性的数据集主要源于图像中的重复区域。通过对比分析了基于增量式的Bundler和VisualSfM两种算法, 并考察了基于全局优化的Olsson、Enqvist及Arie-Nachimson三种算法。值得注意的是, 在这项研究中仅针对Arie-Nachimson的方法提供了公开结果, 而其他算法的结果均为作者团队独立运行所获得。所有实验数据均在配备8核2.67 GHz处理器的服务器上由作者团队独立运行
为了探究我们提出的全局平移估计在存在噪声影响下的旋转敏感性,我们将喷泉数据集的真实旋转形式作为平移注册过程所需的输入参数,其中该旋转由一个较小幅度的随机扰动驱动,其旋转轴均匀分布在球体表面位置上,并且其角度范围从零开始直至给定的最大角度。实验结果表明,在不同噪声水平下,最终误差大致与噪声强度呈线性关系。Sim和Hartley等人的研究也得出了类似结论。
Accuracy. 表3左侧列出了Strecha等人的数据集上多种增量与全局方法的平均基准误差。通过3D相似变换实现了真实坐标系与计算坐标系的有效配准。尽管在前四个数据集中,我们略高于或与最佳方案相当;但在具有庭院循环特征的城堡型数据集中,则显著优于最佳方案。其主要原因在于有效地识别并排除了异常数据(如错误点对齐及错极线几何)。
Running time is a critical metric. Table 3 on the right presents the runtime metrics after calibrating the epipolar line computation, specifically focusing on camera pose estimation and 3D structure recovery. The proposed global approach achieves a speed improvement of 5 to 11 times compared to the implementations by Olsson and Enqvist (Matlab code). Notably, when parallelization is applied, the speed advantage increases further to between 16 and 26 times. This method even surpasses GPU-based and multi-core optimized incremental approaches in terms of performance.
Difficult datasets.
7 Conclusion
我们开发了一种全新的全局式运动恢复架构系统,该系统旨在从无序图像集合中实现大规模三维重建任务。经过深入研究发现,通过将局部相对估计量进行整体整合,该系统能够实现一种高效协同的方法,能够在保证良好的可扩展性基础之上同时实现了稳定的可靠性和精确度。进一步研究表明,基于已知旋转信息的相对平移参数可以被有效提取,并且这种提取过程能够在合理的时间框架内达到令人满意的自适应精度水平。其有效性不仅得到理论上的支持而且通过合成数据集与真实数据集的对比实验得到了充分验证
该管道具有多项优势。
该系统通过融合三焦点范围内的轨迹来构建稳定的结构模型。
几乎没有任何异常值（因为合并错误的对极几何的风险较低）。
由于系统的连贯性
因此无需预设初始配准。
即增量法中通常存在的较大初值问题。
高精度的相关平移估计结果
即使在随后进行精确优化前
全局平移精度也可以很好地概述相机位置；
虽然无需计算整体场景结构即可准确推导出相机位置。
这一现象进一步证实了上述观点。
实验结果表明，在提升全局旋转精度方面仍存在瓶颈。
Supplementary
本节探讨了我们所提出的全局式运动恢复结构的实验数据结果。针对每一个数据集，请提供：
- 初始图像
- 校准点云与相机位置（采用小三角形表示）
- 初始可见性图与贝叶斯旋转推理图分析结果
- 根据我们的SfM方法生成的三维重建模型
- 关于3D重建的关键统计数据（其中运行时间采用秒作为单位，并分为不同阶段记录重投影误差e_Xk (像素)）
