论文阅读《Structure-from-Motion Revisited》

摘要

增量式地运动结构恢复是从无序图像集合中进行三维重建的一个普遍策略。虽然增量式地重建系统在各个方面上都取得了巨大的进步，但鲁棒性、准确性、完整度和尺度仍然是构建真正通用管道的关键问题。我们提出了一种新的运动结构恢复技术，它改进了目前的技术水平，朝着这个最终目标又迈进了一步。完整的重建管道作为开源实现向公众发布。

1 介绍

近年来，无序图像的运动结构恢复(SfM)已经发生了巨大的变化。早期的自标定度量重建系统为新型重建系统奠定了基础，这些新型系统通过城区的互联网图片来进行三维重建。受这些作品的启发，越来越大规模的重建系统被开发出来，从数十万张、数百万张到最近的1亿张互联网图像。已经提出了多种SfM策略，包括增量式、分层式和全局式方法。可以说，增量式SfM是重建无序图片集最流行的策略。尽管增量式策略被广泛使用，但我们仍然没有设计出一个真正通用的SfM系统。虽然现有的系统已经极大地提高了技术水平，但是鲁棒性、准确性、完整度和尺度仍然是增量SfM中的关键问题，这阻碍了它成为通用方法。在本文中，我们提出了一种新的SfM算法来实现这一最终目标。新方法在各种具有挑战性的数据集上进行了评估，代码作为名为COLMAP的开源实现贡献给研究社区，可在https://github.com/colmap/colmap上获得。

在这里插入图片描述

图1 在75千张图片中配准了21千张，重建罗马的结果

2 运动结构恢复综述

SfM是指从一系列不同视觉拍摄的图像中恢复出三维结构。增量式SfM(本文中表示为SfM)是一个具有迭代重建组件的顺序处理管道(图2)。它通常从特征提取和匹配开始，然后进行几何验证。生成的场景图是重建阶段的基础，该阶段使用精心挑选的双视图重建为模型提供种子，然后逐步注册新图像、三角测量场景点、过滤异常值，并使用光束调整(BA)细化重建。接下来的章节将详细说明这一过程，定义整篇论文中使用的符号，并介绍相关工作。

2.1 对应关系搜索

第一阶段是对应关系搜索，它在输入图像 $\mathcal{I}=\{I_i|i=1\cdots N_I\}$ 中查找场景重叠并识别重叠图像中相同点的投影。输出是一组经过几何验证的图像对 $\bar{C}$ 和每个点的图像投影图。

特征提取。 对于每幅图像 $I_i$ ，SfM检测位置 $x_j \in \mathbb{R}^2$ 处的局部特征集 $\mathcal{F}_i=\{(x_j,f_j) | j= 1\cdots N_{F_i}\}$ ，由外观描述符 $f_j$ 表示。这些特征应该在辐射测量和几何变化下保持不变，以便SfM可以在多幅图像中唯一地识别它们。SIFT及其变体以及最近基于学习的特征是鲁棒性方面的黄金标准。另外，二进制特征提供了更好的效率，但鲁棒性降低了。

在这里插入图片描述

图2 增量式运动结构恢复管道

特征匹配。 接下来，SfM利用特征 $\mathcal{F}_i$ 作为图像的外观描述来发现看到相同场景部分的图像。这种简单的方法可以测试每一对图像是否存在场景重叠。通过比较特征的外观 $f_i$ ，可以找到图像 $I_a$ 中与图像 $I_b$ 中每个特征最相似的特征，最终得到特征对应关系。这种方法的计算复杂度为 $N_I^2N_{F_i}^2$ ，这对于大图像集而言是不可行的。有多种方法可以解决尺度和高效匹配问题。输出是一组可能重叠的图像对 $\mathcal{C}=\{ \{ I_a,I_b \} | I_a,I_b \in \mathcal{I}, a < b \}$ 及其相关的特征对应关系 $\mathcal{M}_{ab}\in \mathcal{F}_a \times \mathcal{F}_b$ 。

几何验证。 第三阶段验证可能重叠的图像对 $\mathcal{C}$ 。由于匹配仅基于外观，因此不能保证相应的特征实际上对应到相同的场景点。因此，SfM通过特征点的变换来验证匹配，而这个变换使用射影几何估计。根据图像对的空间配置，不同的映射描述它们的几何关系。单应矩阵 $H$ 描述了纯旋转或纯平移相机拍摄平面场景时的变换。对极几何通过本质矩阵 $E$ （已标定）或基础矩阵 $F$ （未标定）描述运动相机的关系，并且可以使用三焦点张量扩展到三个视图。如果有效的变换在图像之间映射了足够数量的特征，则认为它们通过了几何验证。由于匹配得到的对应关系经常受到异常值污染，因此需要使用诸如RANSAC之类的稳健估计技术。该阶段的输出是一组经过几何验证的图像对 $\bar{\mathcal{C}}$ 、它们相关的内点对应关系 $\bar{\mathcal{M}}_{ab}$ ，以及可选的它们之间的几何关系描述 $G_{ab}$ 。为了确定适当的关系，可以使用GRIC之类的决策标准或QDEGSAC之类的方法。此阶段的输出是所谓的场景图，其中图像为节点，经过验证的图像对为边。

2.2 增量式重建

重建阶段的输入是场景图。输出是已配准图像的估计位姿 $\mathcal{P}=\{ P_c \in SE(3) | c = 1\cdots N_P \}$ ，和重建的场景结构，以点集的形式 $\mathcal{X}=\{ X_k \in \mathbb{R}^3 | k = 1\cdots N_X \}$ 表示。

初始化。 SfM使用精心选择的双视图重建来初始化模型。选择合适的初始图像对是至关重要的，因为无法从错误的初始图像对中恢复出三维结构。此外，重建的鲁棒性、准确性和性能取决于增量过程的种子位置。使用许多重叠的相机从场景图中的密集位置进行初始化通常会由于冗余度增加而产生更加鲁棒和准确的重建。相比之下，从较稀疏的位置进行初始化会缩短运行时间，因为BA处理的问题会变得较稀疏。

图像配准。 从度量重建开始，可以通过求解PnP问题，将新图像注册到当前模型中。PnP问题涉及估计未标定相机的位姿 $P_c$ 及其内参。因此集合 $\mathcal{P}$ 由新注册图像的位姿 $P_c$ 扩展。由于2D-3D对应关系通常受到异常值污染，因此一般使用RANSAC和最小位姿求解器来估计已标定相机的位姿。对于未标定的相机，存在各种最小化求解器，或基于采样的方法。我们在第4.2节中提出了一种新颖的鲁棒的次优图像选择方法，用于准确的位姿估计和可靠的三角测量。

三角化。 新注册的图像必须观测现有的场景点。此外，还可以通过三角测量扩展点集 $\mathcal{X}$ 来增加场景覆盖率。只要至少再注册一张同样覆盖新场景部分但不同视点的图像，就可以对新的场景点 $X_k$ 进行三角测量并将其添加到 $\mathcal{X}$ 中。三角测量是SfM中的一个关键步骤，因为它通过冗余增加了现有模型的稳定性，并且通过提供额外的2D-3D对应关系实现了新图像的配准。存在大量多视图三角测量的方法。这些方法在SfM中使用时存在鲁棒性有限或计算成本高的问题，我们通过在第 4.3节中提出一种鲁棒且有效的三角测量方法来解决。

光束调整。 图像配准和三角测量是独立的过程，即使它们的产物高度相关——相机位姿的不确定性会传递到三角测量点，反之亦然，而额外的三角测量点可以通过增加冗余度来改善初始相机位姿。如果不进一步改进，SfM通常会很快偏离到不可恢复的状态。BA是相机参数 $P_c$ 和点参数 $X_k$ 的联合非线性优化，可最小化重投影误差
$\sum_j \rho_j (||\pi (P_c,X_k) - x_j||_2^2) \tag{1}$
使用函数 $\pi$ 将场景点投影至图像空间，使用损失函数 $\rho_j$ 来降低异常值的权重。LM方法可以用来求解BA问题。BA 问题中参数的特殊结构启发了Schur补技巧，其中首先求解简化的相机系统，然后通过回代来更新点。这种方案通常更有效，因为相机的数量通常小于点的数量。解决该系统有两种选择：精确和非精确步骤算法。精确方法通过存储和分解系统为稠密或稀疏矩阵来解决系统，空间复杂度为 $O(N_P^2)$ ，时间复杂度为 $O(N_P^3)$ 。非精确方法近似地求解系统，通常使用迭代求解器，例如预条件共轭梯度(PCG)，其时间和空间复杂度均为 $O(N_P)$ 。直接算法是多达几百台相机的首选方法，但在大规模设置中成本太高。虽然稀疏直接方法大大降低了稀疏问题的复杂性，但由于连接图通常更加密集，因此对于大型非结构化照片集而言，它们是禁止的。在这种情况下，间接算法是首选方法。特别是对于网络照片，BA花费大量时间来优化许多近似重复的图像。在第4.5节中，我们提出了一种识别和参数化高度重叠图像的方法，以实现密集照片集的有效BA。

3 挑战

虽然目前最先进的SfM算法可以处理大规模互联网照片集中图像的多样化和复杂分布，但它们在完整度和鲁棒性方面往往无法产生完全令人满意的结果。很多时候，系统无法配准大量根据经验应该可配准的图像，或者由于配准错误或漂移导致系统产生破裂的模型。首先，这可能是由于对应关系搜索产生不完整的场景图（例如由于匹配近似）造成的，因此既没有提供完整模型所需的连接性，也没有提供可靠估计所需的足够冗余度。其次，这可能是由于重建阶段由于场景结构缺失或不准确而无法配准图像造成的——图像配准和三角测量具有共生关系，因为图像只能配准到现有的场景结构中，而场景结构只能从配准的图像中进行三角测量。在增量式重建的每个步骤中最大化准确性和完整度是SfM中的一个关键挑战。在本文中，我们解决了这一挑战，并在完整度、鲁棒性和准确性方面显著提高了当前最先进的结果（第5节），同时提高了效率。

4 贡献

本节介绍了一种改进SfM中主要挑战的新算法。首先，我们引入一种几何验证策略，该策略通过信息扩充场景图，从而提高初始化和三角测量组件的鲁棒性。其次，下一个最佳视图选择可最大限度地提高增量重建过程的鲁棒性和准确性。第三，一种鲁棒的三角测量方法，可以以更低的计算成本产生比现有技术更完整的场景结构。第四，迭代BA、重新三角测量和异常值过滤策略可通过减轻漂移效应显著提高完整度和准确性。最后，通过冗余视图挖掘对稠密照片集进行更有效的BA参数化。这使得系统在保持效率的同时，在鲁棒性和完整度方面明显优于当前最先进的技术。我们将我们的贡献与当前最先进的系统Bundler(开源)和VisualSFM进行了对比。所提出的系统作为开源实现发布。

4.1 场景图增强

我们提出了一种多模型几何验证策略，以适当的几何关系增强场景图。首先，我们估计了基础矩阵。如果至少发现 $N_F$ 个内点，我们就认为该图像对已通过几何验证。接下来，我们通过确定同一图像对的单应性内点的数量 $N_H$ 来对变换进行分类。为了近似GRIC等模型选择方法，如果 $N_H/N_F < \epsilon_{HF}$ ，我们假设相机在一般场景中运动。对于标定后的图像，我们还估计了一个本质矩阵及其内点 $N_E$ 的数量。如果 $N_E/N_F> \epsilon_{EF}$ ，我们认为标定正确。在标定正确和 $N_H/N_F<\epsilon_{HF}$ 的情况下，我们对本质矩阵进行分解，从内点对应关系中对点进行三角化，并确定三角化角度中值 $\alpha_{m}$ 。利用 $\alpha_m$ ，我们区分了纯旋转场景（全景）和平面场景（平面）。此外，互联网照片中一个常见的问题是水印、时间戳和帧（WTFs）错误地链接了不同地标的图像。我们通过在图像边界估计带有 $N_S$ 内点的相似变换来检测这样的图像对。如果图像对满足 $N_S/N_F>\epsilon_{SF}$ 或 $N_S/N_E>\epsilon_{SE}$ ，则认为它是WTF，并不把它插入到场景图中。对于有效的图像对，我们用模型类别（一般、全景、平面）来标记场景图，同时记录支持该类别的最大内点数 $N_H$ 或 $N_E$ 或 $N_F$ 。模型类别仅用于重建初始图像对的选择，我们优先使用非全景和已标定的图像对。已经增强的场景图能够有效地为鲁棒重建过程找到最佳初始化。此外，我们没有对全景图像对进行三角化，以避免退化点，从而提高三角化和后续图像配准的鲁棒性。

在这里插入图片描述

图3 对于L=3，图像中具有不同分布（上和下）和不同点数（左和右）的分数。

4.2 下一个最佳视图选择

次优视图规划已经在计算机视觉、摄影测量和机器人领域得到了研究。在鲁棒SfM中选择次优视图的目的是最小化重建误差。在这里，我们提出了一种有效的次优视图策略，该策略遵循不确定性驱动的方法，最大限度地提高了重建鲁棒性。

选择下一个最佳视图是至关重要的，因为每个决定都会影响剩余的重建。一个错误的决定可能会导致一连串的相机错误配准和错误的三角化。此外，选择次优视图会极大地影响位姿估计的质量以及三角测量的完整度和准确性。准确的位姿估计对于鲁棒的SfM至关重要，因为如果位姿不准确，点的三角测量可能会失败。关于选择下一个最佳视图的决定是具有挑战性的，因为对于互联网照片集来说，通常没有关于场景覆盖和相机参数的先验信息，因此决定完全基于来自外观的信息、双视图对应、以及增量重建场景。

一种流行的策略是选择看到最多三角点的图像，目的是最大限度地减少相机resection的不确定性。Haner等人提出了一种不确定性驱动的方法，使重建误差最小化。通常，除了观测配置条件不佳的情况外，选择看到最多三角点的相机。为此，Lepetit等人通过实验表明，使用PnP求解出来的相机位姿精度取决于观测值的数量及其在图像中的分布。对于网络照片，将标准PnP问题扩展到缺少或不准确的先验标定情况下的内参估计。大量的2D-3D对应为这种估计提供了冗余，而点的均匀分布避免了不良配置，并使内参的估计可靠。

下一个最佳视图的候选对象不是那些至少看到 $N_t > 0$ 个三角点的尚未配准的图像。使用特征轨迹图可以有效地实现对该统计数据的跟踪。对于互联网数据集，这个图可能非常密集，因为许多图像可能看到相同的结构。因此，在重建的每个步骤中都有许多候选视图可供选择。Haner等人提出的穷举协方差传播是不可行的，因为每一步都需要计算和分析每个候选的协方差。我们提出的方法使用高效的多分辨率分析近似于它们的不确定性驱动方法。

我们必须同时跟踪每个候选图像中可见点的数量及其分布。可见点越多，这些点的分布越均匀，分数 $S$ 就越高，这样，具有更好条件的可见点配置的图像就会被优先配准。为了实现这一目标，我们将图像离散到一个固定大小的网格中，在两个维度上都有 $K_l$ 个bins。每个单元格有两种不同的状态：空和满。在重建过程中，只要空单元格中的一个点变得可见，单元格的状态就会变为满的，并且图像的分数 $S_i$ 增加一个权重 $w_l$ 。通过这个方案，我们量化了可见点的数量。由于单元格对整体得分只有一次贡献，我们更倾向于均匀的分布，而不是当点聚集在图像的一部分时（即只有少数单元格包含所有可见点）。但是，如果可见点的数量为 $N_t \ll K^2_l$ ，则该方案可能无法很好地捕获点的分布，因为每个点都可能落在一个单独的单元格中。因此，通过在每个连续的级别上使用更高的分辨率 $K_l = 2^l$ 来划分图像，我们将前面描述的方法扩展到 $1\dots L$ 的多分辨率金字塔。分数是通过分辨率相关的权重 $w_l=K_l^2$ 在所有级别上累积的。该数据结构及其分数可以在线高效更新。图3显示了不同配置的分数，第5节展示了使用该策略改进的重建鲁棒性和准确性。

4.3 鲁棒和高效三角化

特别是对于稀疏匹配的图像集合，利用传递对应可以提高三角测量的完整度和准确性，从而改善后续图像配准。近似匹配技术通常倾向于外观相似的图像对，因此两视图对应通常源于具有小基线的图像对。利用传递性在具有较大基线的图像之间建立对应关系，从而实现更准确的三角测量。因此，我们通过连接两视图对应来形成特征轨迹。

针对噪声图像观测的三角测量，研究人员已经提出了多种方法。虽然提出的一些方法对一定程度的离群值污染具有鲁棒性，但据我们所知，没有一种方法可以处理特征轨道中经常出现的高离群值比率（图6）。我们参考Kang等人对现有多视图三角测量方法的详细概述。在本节中，我们提出了一种有效的、基于采样的三角化方法，该方法可以鲁棒地估计异常值污染特征轨道内的所有点。

由于错误的沿极线模糊匹配的双视图验证，特征轨道通常包含大量的异常值。单个不匹配会合并两个或多个独立点的轨迹。例如，错误地合并四个长度相等的特征轨迹会导致75%的异常值比率。此外，由于高重投影误差，不准确的相机位姿可能使轨迹元素无效。因此，对于鲁棒的三角测量，有必要在使用多个视图执行优化之前找到一致的轨迹元素集。此外，为了从错误合并中恢复特征轨迹的潜在多个点，需要一个递归三角化方案。

Bundler对轨迹元素的所有成对组合进行采样，执行双视图三角化，然后检查是否至少有一个解具有足够的三角化角度。如果找到条件良好的解，则对整个轨迹进行多视图三角化，如果所有观测值都通过了cheirality约束，则接受此多视图三角化。该方法对异常点不具有鲁棒性，因为不可能恢复合并到一个轨道中的独立点。同时，由于穷举的两两三角化，计算量大。我们的方法克服了这两个限制。

为了处理任意水平的异常污染，我们使用RANSAC制定了多视图三角测量问题。我们考虑特征轨迹 $\mathcal{T} = \{ T_n | n = 1…N_T\}$ 作为一组具有先验未知内点比例 $\epsilon$ 的测量值。测量 $T_n$ 由归一化图像观测值 $\bar{x}_n \in \mathbb{R}^2$ 和相应的相机位姿 $P_n \in SE(3)$ 组成，它表示从世界到相机帧的投影 $P=[R^T,-R^Tt]$ ，其中 $R\in SO(3)$ ， $t\in \mathbb{R}^3$ 。我们的目标是最大限度地支持符合条件良好的双视图三角测量，
$X_{ab} \sim \tau(\bar{x}_a,\bar{x}_b,P_a,P_b) \ with \ a \neq b \tag{2}$
其中 $\tau$ 表示选择的三角化方法（本文中使用的是DLT方法）， $X_{ab}$ 是三角化点。请注意，我们没有从全景图像对进行三角测量（第4.1节），以避免由于不准确的位姿估计而导致错误的三角测量角度。一个条件良好的模型满足两个约束。首先，有足够的三角测量角 $\alpha$ ，
$cos\alpha = \frac{t_a-X_{ab}}{||t_a-X_{ab}||_2}\cdot \frac{t_b-X_{ab}}{||t_b-X_{ab}||_2} \tag{3}$
其次，关于视图 $P_a$ 和视图 $P_b$ 的正深度 $d_a$ 和 $d_b$ ，也即cheirality约束，深度定义为，
$d=[p_{31} \ p_{32} \ p_{33} \ p_{34}] [X_{ab}^T\ 1]^T \tag{4}$
其中 $p_{mn}$ 定义为矩阵 $P$ 的第 $m$ 行第 $n$ 列元素。如果测量值 $T_n$ 的深度 $d_n$ 为正，且其重投影误差
$e_n=\begin{Vmatrix} \bar{x}_n - \begin{bmatrix} x'/z' \\ y'/z' \end{bmatrix} \end{Vmatrix} _2 \ with \ \begin{bmatrix} x' \\ y' \\ z' \end{bmatrix} = P_n \begin{bmatrix} X_{ab} \\ 1 \end{bmatrix} \tag{5}$
小于固定阈值 $t$ 时，则认为该测量值 $T_n$ 符合模型。RANSAC作为一种迭代方法最大化 $\mathcal{K}$ ，通常它均匀地随机采样大小为2的最小集合。然而，由于对于小 $N_T$ 可能对相同的最小集进行多次采样，因此我们定义随机采样器仅生成唯一的样本。为了确保至少有一个无离群值的最小集被采样，RANSAC必须运行至少 $K$ 次迭代。由于内点的先验初始比率 $a$ 是未知的，我们将其设置为一个小的初始值 $\epsilon_0$ ，并在找到更大的共识集（自适应停止准则）时调整 $K$ 。因为一个特征轨迹可能包含多个独立的点，我们通过从剩余的测量中删除共识集来递归地运行这个过程。如果最新共识集的大小小于3，则递归停止。第5节中的评估表明，所提出的方法在降低计算成本的同时提高了三角测量的完整度。

4.4 光束调整

为了减少累积误差，我们在图像配准和三角测量后执行BA。通常，不需要在每个步骤之后执行全局BA，因为增量SfM只在局部影响模型。因此，我们在每个图像配准后对连接最多的图像集执行局部BA。与VisualSFM类似，我们只在模型增长到一定百分比后才执行全局BA，从而使SfM的线性运行时间平摊。

参数化。 为了考虑潜在的异常值，我们采用柯西函数作为局部BA中的鲁棒损失函数 $\rho_j$ 。对于多达几百个相机的问题，我们使用稀疏直接求解器，对于更大的问题，我们依靠PCG。我们使用Ceres Solver，并提供在任意图像组合中共享任意复杂的相机模型的选项。对于无序的互联网照片，我们依赖于一个简单的相机模型，只有一个径向畸变参数，因为估计依赖于纯粹的自标定。

过滤。 BA后，一些观测值与模型不符。因此，我们对重投影误差较大的观测值进行过滤。此外，对于每个点，我们通过在所有观察射线对上执行最小化三角测量的角度来检查条件良好的几何形状。在全局BA之后，我们还检查退化相机，例如由全景或人工增强图像引起的相机。通常情况下，这些相机只能观察到异常值，或者它们的内参收敛到一个虚假的最小值。因此，我们没有将焦距和畸变参数限制在一个先验的固定范围内，而是让它们在BA中自由优化。由于主点标定是一个不适定问题，对于未标定的相机，我们将其固定在图像中心。在全局BA后，视场异常或畸变系数量级较大的相机被认为估计和滤波不正确。

重新三角化。 与VisualSfM类似，我们执行重新三角测量（RT）来解释全局BA（pre-BA RT）之前的漂移效应。然而，BA通常会显著改善相机和点参数。因此，我们建议用一个额外的后BA-RT步骤来扩展非常有效的前BA-RT。这一步的目的是通过延续之前无法三角化的点的轨迹（例如，由于不准确的位姿等）来提高重建的完整度（比较第4.3节）。而不是增加三角测量阈值，我们只继续跟踪那些误差低于滤波阈值的观测值。此外，我们尝试合并轨迹，从而为下一个BA步骤提供更多的冗余。

迭代优化。 Bundler和VisualSfM执行BA和过滤的单个实例。由于漂移或前BA-RT，通常BA中很大一部分观测值是异常值，随后被过滤。由于BA受离群值的影响比较严重，第二遍BA可以显著改善结果。因此，我们建议在迭代优化中执行BA、RT和过滤，直到过滤的观测值和后BA-RT点的数量减少。在大多数情况下，经过第二次迭代后，结果显著改善，优化收敛。第5节揭示了所提出的迭代优化显著提高了重建完整度。

4.5 冗余视图挖掘

BA是SfM中的主要性能瓶颈。在本节中，我们提出了一种方法，利用增量SfM和稠密照片集合的固有特征，通过将冗余相机聚类到高场景重叠组中，从而更有效地参数化BA。

由于兴趣点的受欢迎程度不同，互联网图片集通常具有高度不均匀的可见性模式。此外，无序的集合通常聚集成在许多图像中共视的点片段。许多先前的工作利用这一事实来提高BA的效率，包括Kushal等人，他们分析了可见模式，用来高效地预处理简化的相机系统。Ni等人将相机和点划分为子图，并通过分隔变量连接，将划分视为连接相机和点参数图上的图割问题。然后，BA在固定相机和点和优化分隔变量之间交替进行，反之亦然。Carlone等人的另一种方法，将多个低秩点分解为单个因子，对相机施加高秩约束，从而在相机共享多个点时提供计算优势。

我们提出的方法是受到这些前人工作的启发。与Ni等人类似，我们将问题划分为子图，这些子图的内部参数被分解。我们有三个主要的贡献。其一，一种利用SfM固有特性的高效相机分组方案，取代了Ni等人使用的昂贵的图切方法。其二，我们将场景划分为许多小的、高度重叠的相机组，而不是将许多相机聚类到一个子图中。每组中的相机被压缩成一个单独的相机，从而降低了求解简化相机系统的成本。其三，由于相机组更小，高度重叠，我们通过跳过分隔变量优化来消除Ni等人的交替方案。

SfM根据图像和点的参数是否受到最新增量模型扩展的影响，将其分为两组。对于大型问题，大部分场景不受影响，因为模型通常在局部扩展。BA自然会对新扩展的部分进行优化，而其他部分只有在漂移的情况下才会改进。此外，网络照片通常有一个不均匀的相机分布和许多冗余的视点。基于这些观察结果，我们将未受影响的场景部分划分为具有高度重叠图像的组 $\mathcal{G}=\{ G_r | r = 1...N_G \}$ ，并将每个组 $G_r$ 参数化为单个相机。受最新扩展影响的图像被独立分组，以允许对其参数进行最佳优化。注意，这会导致标准BA参数化（Eq. 1）。对于未受影响的图像，我们创建基数为 $N_{G_r}$ 的组。如果在最新的模型扩展期间添加了图像，或者如果其观测值的比例大于 $\epsilon_r$ ，则我们认为图像受影响（以改进重新三角化相机）。

一组内的图像应尽可能冗余，图像之间共视点的数量是描述它们相互作用程度的一种度量。对于一个有 $N_X个$ 点的场景，每张图像可以用一个二值可见向量 $v_i \in \{0,1\}^{N_X}$ 来描述，其中如果点 $X_n$ 在图像 $i$ 中可见，则 $v_i$ 中的第 $n$ 个条目为1，否则为0。图像 $a$ 和 $b$ 之间的交互程度是通过对它们的向量 $v_i$ 进行位运算来计算的，
$V_{ab}=||v_a \cap v_b|| / || v_a \cup v_b|| \tag{6}$
为了构建组，我们对图像进行排序 $\bar{\mathcal{I}}=\{ I_i \Big | ||v_i|| \geq ||v_{i+1}|| \}$ 。我们通过从 $\bar{\mathcal{I}}$ 中删除第一张图像 $I_a$ 并找到最大化 $V_{ab}$ 的图像 $I_b$ 来初始化组 $G_r$ 。如果 $V_{ab} > V$ 和 $G_r|<S$ ，图像 $I_b$ 从 $\bar{\mathcal{I}}$ 中删除并添加到组 $G_r$ 中。否则，初始化一个新的组。为了减少寻找 $I_b$ 的时间，我们采用了启发式算法，将搜索限制在空间上最近邻的 $K_r$ 上，这些图像在 $\pm \beta$ 度范围内具有共同的观察方向，这一事实的动机是这些图像具有很高的相似性，它们共享许多点。

在这里插入图片描述
图4 高斯分布点 $x_j \in [0,1]\times [0,1]$ 的次优视图分数，该高斯分布的平均值为 $\mu$ ，标准差为 $\sigma$ 。右图的 $\mu$ 为0.5。

然后，组内的每张图像在一个共同的组内局部坐标系上进行参数化。对于一组图像的BA代价函数（公式1）为，
$E_g=\sum_j \rho_j \Big( || \pi_g \big( G_r,P_c,X_k \big) -x_j ||_2^2 \Big) \tag{7}$
其中 $G_r\in SE(3)$ 为外部组参数， $P_c$ 为固定值。然后定义组 $r$ 中图像的投影矩阵为组与图像位姿的级联 $P_{cr} = P_cG_r$ 。总代价 $\bar{E}$ 是分组成本贡献和未分组成本贡献的总和。为了有效地串联 $G_r$ 和 $P_i$ 的旋转分量，我们依赖于四元数。相对于 $\pi$ ，由于计算 $\pi_g$ 的开销较小，较大的组可以带来更大的性能优势。请注意，即使对于组大小为2，我们也能观察到计算优势。此外，性能优势取决于问题的大小，因为相机数量的减少对直接法的 $O(N^3)$ 时间复杂度的影响大于间接法的 $O (N)$ 时间复杂度（第2节）。

5 实验

我们在大量不同的数据集上运行实验，与最先进的增量（Bundler, VisualSFM）和全局SfM系统（DISCO, Theia）进行比较，评估所提出的组件和整个系统。这17个数据集共包含144953张无序的互联网照片，分布在一个很大的区域，并且相机密度变化很大。此外，Quad有相机位置真值。在所有实验中，我们使用RootSIFT特征，并使用在不相关数据集上训练的词汇树将每个图像与其100个最近的邻居进行匹配。为了确保不同方法之间的可比性，在具有256GB RAM的2.7GHz机器上，不包括对应搜索步骤。

在这里插入图片描述

图5 Quad的下一个最佳视图结果：在增量SfM期间共享的配准图像数量和重建误差。

图6 对于Dubrovnik数据集的三角化统计。左图：特征轨迹的离群比分布。右图：三角测量N个视点所需的平均样本数。

在这里插入图片描述

图7 平均相对运行时间。标签1表示标准全局BA、穷举三角化。标签2表示分组BA、RANSAC三角化。初始化和下一个最佳视图选择（所有策略）的运行时间小于0.1%。

下一个最佳视图选择。 一个综合实验（图 4）评估了分数S对点的数量和分布的反映程度。我们使用 $L = 6$ 的金字塔层级，生成 $(\sigma,\mu)$ 的高斯分布图像点。更大的 $\sigma$ 和更中心的 $\mu$ 对应于更均匀的分布，正确地产生了更高的分数。类似地，当点数很少时，分数由点的数量决定，否则由它们在图像中的分布决定。另一个实验（图5）将我们的方法（金字塔）与现有策略在重建误差方面进行了比较。其他方法是Number，它最大化三角测量点的数量；以及Ratio，它最大化可见点与潜在可见点的比例。在每个图像配准后，我们测量策略之间共享的配准图像数量（交集/联合）和重建误差作为到相机位置真值的中位数距离。虽然所有策略都收敛到同一组配准图像，但我们的方法通过为图像选择更好的配准顺序来产生最准确的重建。

鲁棒和高效地三角测量。 在Dubrovnik数据集上的实验（图6和表2）对由47M个验证匹配组成的2.9M条特征轨迹进行了评估。我们与Bundler和穷尽策略进行比较，该策略对轨迹中的所有成对组合进行采样。我们设置 $\alpha=2°$ ， $t = 8$ px， $\epsilon_0=0.03$ 。为了避免组合爆炸，我们将穷举方法限制为10K次迭代，也即 $\epsilon_{min} \approx0.02$ ， $\eta=0.999$ 。多样化的内点比分布（通过递归、穷举方法确定）证明需要一种鲁棒的三角测量方法。我们提出的递归方法比非递归方法恢复更长的轨道和更多的轨道元素。注意，基于RANSAC的递归方法的点数越多，轨迹长度就越短。基于RANSAC的方法产生的轨迹略差，但速度更快（10-40 倍）。通过改变 $\eta$ ，很容易平衡速度和完整度。

在这里插入图片描述
表1 最先进的SfM系统在大规模无序互联网图片集上的重建结果。

在这里插入图片描述
表2 $\eta_1=0.99$ 和 $\eta_2=0.5$ 时的三角测量结果。

在这里插入图片描述
图8 不同的场景覆盖 $V$ ， $\epsilon_r=0.02$ ， $S = 10$ 时在标准分组BA中的相机数目。

冗余视图挖掘。 我们在稠密分布图像的无序集合上评估了冗余视图挖掘。图8显示了固定BA迭代次数下参数化相机数目在全局BA中的增长速率。根据强制的场景重叠 $V$ ，我们可以通过一个重要的因子来减少求解相机系统的时间。总运行时间的有效加速分别为5%（ $V = 0.6$ ），14%（ $V = 0.3$ ），32%（ $V = 0.1$ ），而平均重投影误差分别从0.26px（标准BA）降低到0.27px、0.28px和0.29px。当 $V > 0.3$ 时，这几种配置下的重建质量相差不大。 $V$ 越小，重建质量越差。使用 $V = 0.4$ ，对于Colosseum的整个管道的运行时间减少了36%，但重建的质量是基本相同的。

系统。 表1和图1展示了整个系统的性能，从而也评估了系统中各个组件的性能。对于每个数据集，我们报告最大的重建组件。Theia是最快的方法，而我们的方法获得的时间比VisualSFM略差，比Bundler快50倍以上。图7显示了各个模块的相对时序。对于所有数据集，我们在完整度方面明显优于任何其他方法，特别是对于较大的模型。重要的是，增加的轨迹长度导致BA中更高的冗余。此外，我们在Quad数据集上实现了最佳位姿精度：DISCO 1.16米，Bundler 1.01米，VisualSFM 0.89米，本文的方法 0.85米。图9对比了我们的方法和Bundler的重建结果。我们鼓励读者查看补充材料，对结果进行额外的视觉比较，展示我们方法的优越鲁棒性，完整度和准确性。

在这里插入图片描述
图9 我们的方法和Bundler在Gendarmenmarkt下的重建结果。