SfM是指从一系列不同视觉拍摄的图像中恢复出三维结构。增量式SfM(本文中表示为SfM)是一个具有迭代重建组件的顺序处理管道(图2)。它通常从特征提取和匹配开始，然后进行几何验证。生成的场景图是重建阶段的基础，该阶段使用精心挑选的双视图重建为模型提供种子，然后逐步注册新图像、三角测量场景点、过滤异常值，并使用光束调整(BA)细化重建。接下来的章节将详细说明这一过程，定义整篇论文中使用的符号，并介绍相关工作。
2.1 对应关系搜索
第一阶段是对应关系搜索，它在输入图像 I = { I i ∣ i = 1 ⋯ N I } \mathcal{I}=\{I_i|i=1\cdots N_I\} I={Ii∣i=1⋯NI}中查找场景重叠并识别重叠图像中相同点的投影。输出是一组经过几何验证的图像对 C ˉ \bar{C} Cˉ和每个点的图像投影图。
特征提取。 对于每幅图像 I i I_i Ii，SfM检测位置 x j ∈ R 2 x_j \in \mathbb{R}^2 xj∈R2处的局部特征集 F i = { ( x j , f j ) ∣ j = 1 ⋯ N F i } \mathcal{F}_i=\{(x_j,f_j) | j= 1\cdots N_{F_i}\} Fi={(xj,fj)∣j=1⋯NFi}，由外观描述符 f j f_j fj表示。这些特征应该在辐射测量和几何变化下保持不变，以便SfM可以在多幅图像中唯一地识别它们。SIFT及其变体以及最近基于学习的特征是鲁棒性方面的黄金标准。另外，二进制特征提供了更好的效率，但鲁棒性降低了。
特征匹配。 接下来，SfM利用特征 F i \mathcal{F}_i Fi作为图像的外观描述来发现看到相同场景部分的图像。这种简单的方法可以测试每一对图像是否存在场景重叠。通过比较特征的外观 f i f_i fi，可以找到图像 I a I_a Ia中与图像 I b I_b Ib中每个特征最相似的特征，最终得到特征对应关系。这种方法的计算复杂度为 N I 2 N F i 2 N_I^2N_{F_i}^2 NI2NFi2，这对于大图像集而言是不可行的。有多种方法可以解决尺度和高效匹配问题。输出是一组可能重叠的图像对 C = { { I a , I b } ∣ I a , I b ∈ I , a < b } \mathcal{C}=\{ \{ I_a,I_b \} | I_a,I_b \in \mathcal{I}, a < b \} C={{Ia,Ib}∣Ia,Ib∈I,a<b}及其相关的特征对应关系 M a b ∈ F a × F b \mathcal{M}_{ab}\in \mathcal{F}_a \times \mathcal{F}_b Mab∈Fa×Fb。
几何验证。 第三阶段验证可能重叠的图像对 C \mathcal{C} C。由于匹配仅基于外观，因此不能保证相应的特征实际上对应到相同的场景点。因此，SfM通过特征点的变换来验证匹配，而这个变换使用射影几何估计。根据图像对的空间配置，不同的映射描述它们的几何关系。单应矩阵 H H H描述了纯旋转或纯平移相机拍摄平面场景时的变换。对极几何通过本质矩阵 E E E（已标定）或基础矩阵 F F F（未标定）描述运动相机的关系，并且可以使用三焦点张量扩展到三个视图。如果有效的变换在图像之间映射了足够数量的特征，则认为它们通过了几何验证。由于匹配得到的对应关系经常受到异常值污染，因此需要使用诸如RANSAC之类的稳健估计技术。该阶段的输出是一组经过几何验证的图像对 C ˉ \bar{\mathcal{C}} Cˉ、它们相关的内点对应关系 M ˉ a b \bar{\mathcal{M}}_{ab} Mˉab，以及可选的它们之间的几何关系描述 G a b G_{ab} Gab。为了确定适当的关系，可以使用GRIC之类的决策标准或QDEGSAC之类的方法。此阶段的输出是所谓的场景图，其中图像为节点，经过验证的图像对为边。
2.2 增量式重建
重建阶段的输入是场景图。输出是已配准图像的估计位姿 P = { P c ∈ S E ( 3 ) ∣ c = 1 ⋯ N P } \mathcal{P}=\{ P_c \in SE(3) | c = 1\cdots N_P \} P={Pc∈SE(3)∣c=1⋯NP}，和重建的场景结构，以点集的形式 X = { X k ∈ R 3 ∣ k = 1 ⋯ N X } \mathcal{X}=\{ X_k \in \mathbb{R}^3 | k = 1\cdots N_X \} X={Xk∈R3∣k=1⋯NX}表示。
初始化。 SfM使用精心选择的双视图重建来初始化模型。选择合适的初始图像对是至关重要的，因为无法从错误的初始图像对中恢复出三维结构。此外，重建的鲁棒性、准确性和性能取决于增量过程的种子位置。使用许多重叠的相机从场景图中的密集位置进行初始化通常会由于冗余度增加而产生更加鲁棒和准确的重建。相比之下，从较稀疏的位置进行初始化会缩短运行时间，因为BA处理的问题会变得较稀疏。
图像配准。 从度量重建开始，可以通过求解PnP问题，将新图像注册到当前模型中。PnP问题涉及估计未标定相机的位姿 P c P_c Pc及其内参。因此集合 P \mathcal{P} P由新注册图像的位姿 P c P_c Pc扩展。由于2D-3D对应关系通常受到异常值污染，因此一般使用RANSAC和最小位姿求解器来估计已标定相机的位姿。对于未标定的相机，存在各种最小化求解器，或基于采样的方法。我们在第4.2节中提出了一种新颖的鲁棒的次优图像选择方法，用于准确的位姿估计和可靠的三角测量。
三角化。 新注册的图像必须观测现有的场景点。此外，还可以通过三角测量扩展点集 X \mathcal{X} X来增加场景覆盖率。只要至少再注册一张同样覆盖新场景部分但不同视点的图像，就可以对新的场景点 X k X_k Xk进行三角测量并将其添加到 X \mathcal{X} X中。三角测量是SfM中的一个关键步骤，因为它通过冗余增加了现有模型的稳定性，并且通过提供额外的2D-3D对应关系实现了新图像的配准。存在大量多视图三角测量的方法。这些方法在SfM中使用时存在鲁棒性有限或计算成本高的问题，我们通过在第 4.3节中提出一种鲁棒且有效的三角测量方法来解决。
光束调整。 图像配准和三角测量是独立的过程，即使它们的产物高度相关——相机位姿的不确定性会传递到三角测量点，反之亦然，而额外的三角测量点可以通过增加冗余度来改善初始相机位姿。如果不进一步改进，SfM通常会很快偏离到不可恢复的状态。BA是相机参数
P
c
P_c
Pc和点参数
X
k
X_k
Xk的联合非线性优化，可最小化重投影误差
E
=
∑
j
ρ
j
(
∣
∣
π
(
P
c
,
X
k
)
−
x
j
∣
∣
2
2
)
(1)
E = \sum_j \rho_j (||\pi (P_c,X_k) - x_j||_2^2) \tag{1}
E=j∑ρj(∣∣π(Pc,Xk)−xj∣∣22)(1)
使用函数
π
\pi
π将场景点投影至图像空间，使用损失函数
ρ
j
\rho_j
ρj来降低异常值的权重。LM方法可以用来求解BA问题。BA 问题中参数的特殊结构启发了Schur补技巧，其中首先求解简化的相机系统，然后通过回代来更新点。这种方案通常更有效，因为相机的数量通常小于点的数量。解决该系统有两种选择：精确和非精确步骤算法。精确方法通过存储和分解系统为稠密或稀疏矩阵来解决系统，空间复杂度为
O
(
N
P
2
)
O(N_P^2)
O(NP2)，时间复杂度为
O
(
N
P
3
)
O(N_P^3)
O(NP3)。非精确方法近似地求解系统，通常使用迭代求解器，例如预条件共轭梯度(PCG)，其时间和空间复杂度均为
O
(
N
P
)
O(N_P)
O(NP)。直接算法是多达几百台相机的首选方法，但在大规模设置中成本太高。虽然稀疏直接方法大大降低了稀疏问题的复杂性，但由于连接图通常更加密集，因此对于大型非结构化照片集而言，它们是禁止的。在这种情况下，间接算法是首选方法。特别是对于网络照片，BA花费大量时间来优化许多近似重复的图像。在第4.5节中，我们提出了一种识别和参数化高度重叠图像的方法，以实现密集照片集的有效BA。