Colmap 论文之一：Structure-from-Motion Revisited
下载链接：论文下载
作者：Johannes L. Schonberger等
题目：重新审视 SFM
一、摘要
增量式SFM可从无序的图像集中进行三维重建。但其鲁棒性、准确性、完整性和可伸缩性仍然是构建真正通用管道的关键问题。该论文提出了一种新的SFM技术。该技术开源。
二、引言
多年来，SFM发生了巨大的变化。
受到早期的自校准度量重建系统的启发，提出了多种SfM策略，包括渐进式、分层式和全局方法。其中，增量式SfM是重建无序图片集最流行的策略。
但目前为止，没有一个真正通用的SfM系统。虽然现有的系统已经极大地提高了技术水平，但是健壮性、准确性、完整性和可伸缩性仍然是增量SfM中的关键问题。
在本文中，作者（及团队）提出了一种新的SfM算法来实现这一最终目标。
代码名为：Colmap - https://github.com/colmap/colmap
三、SfM的技术回顾
SfM是将三维结构的投影重建为从不同视点拍摄的一系列图像的过程。
增量式SfM是一种具有迭代重建组建的顺序处理流水线（下图）。
通常从特征提取和匹配开始，然后进行几何验证。生成的场景作为重建阶段的基础，在增量注册新图像、三角化场景点、过滤异常值和使用束调整（BA）改进重建之前，该阶段使用精心选择的两视图重建为模型播种。（下面详细阐述这一过程）
3.1 Correspondence Search（特征搜索与匹配）
第一阶段是特征搜索，在输入图像集中找到重叠的场景，识别重叠场景中相同的投影。输出一组经过几何验证的图像对和每个点的图像投影图。
3.1.1 Feature Extration 特征提取
对于每张图像，SfM检测由外观描述符表示的位置的局部特征集。这些特征在辐射和几何变化下都应保持不变，这样SfM才能在多幅图像中唯一地识别它们。
代表算法：SIFT （及其衍生品），鲁棒性方面的黄金标准。
而 二值特征 以降低鲁棒性为代价提供了更好的效率。
3.1.2 Matching 特征匹配
SFM利用提取到的特征作为图像的外观描述来发现具有相同场景的图像。
naive方法不使用于大型图像集合。各种各样的方法解决了可扩展和有效匹配的问题，输出是一组可能重叠的图像（这里标记为C）对及其相关的特征对应（这里的特征对应要区别于特征匹配的关系）。
3.1.3 Geometric Verification 几何验证
这一阶段验证潜在重叠的图像对- C 。
由于匹配仅基于外观，因此不能保证对应的特征实际上映射到相同的场景点。
因此，SFM通过尝试使用射影几何，估计在图像之间的特征点的转换来验证匹配。
根据图像对的空间结构，不同的映射描述了它们的几何关系。
单应性 H 描述了 ：纯旋转或移动摄像机捕捉平面场景的变换。
对极几何：描述了移动摄像机的关系，并且可以使用三焦张量扩展到三个视图。
如果一个有效的变换在图像之间映射了足够数量的特征，它们就被认为是几何验证的。
由于匹配的对应关系经常受到离群值的污染，因此需要稳健的估计技术，如：RANSAC 。
这个阶段的输出是一组经过几何验证的图像对C、图像对的早期对应、以及几何关系的可选描述。
为了确定合适的关系，可以使用：GRIC等（Decision criterions)或 QDEGSAC等方法。
这一阶段的输出是一个所谓的场景图，以图像作为节点，验证的图像对作为边缘。
3.2 Incremental Reconstruction - 增量重建
重建阶段：
- 输入：场景图
- 输出：配准图像的姿态估计P + 作为点集合X的重构场景结构。
3.2.1 Initialization - 初始化
SFM通过精心选择的双视图来重构初始化模型。
选择合适的初始至关重要，因为重构可能永远无法从错误的初始化中恢复。此外，重建的鲁棒性、准确性和性能取决于增量过程的种子位置。
由于冗余度的增加，从图像中具有许多重叠相机的密集位置初始化通常会使重建结果更加健壮和准确。相反，从更稀疏的位置初始化会导致更短的时间，因为在BA处理重构过程中积累的整体稀疏问题所致。
3.2.2 Image Registration 图像注册（配准）
（这里我把 Registration翻译为了注册，感觉注册比较符合这一阶段所作的任务内容 ）
通过使用已注册图像中三角点的特征对应来解决 Perspective-n-Point（PnP）问题，可以将新图像配准到当前模型。PnP问题包括估计姿态、估计为标定相机的参数。因此，集合 P （3.2中的输出）被新注册图像的位姿扩展。
由于2D-3D对应关系经常受到离群值的污染，标定相机的姿态通常使用RANSAC和最小姿态求解器进行估计。
对于未标定的相机，存在各种最小解算器。
这里，作者提出了一种新的鲁棒性次优图像选择方法，用于精确的姿态估计和可靠的三角测量。
3.2.3 Triangulation 三角测量
新注册的必须观察到已有的场景。此外，它还可以通过三角测量扩展点集 - X 来 增加场景覆盖（ increase scene coverage）。
一个新的场景点可以三角化并添加到 X ，只要至少有一张图像，也可以覆盖新的场景部分，但要求是不同的注册视角（这里可以理解为不同的视角拍摄，要有视差，即图像与图像之间的区别）。
三角测量是SFM的关键步骤，因为它通过冗余增加了现有模型的稳定性，并且通过提供额外的2D-3D对应来实现新图像注册。目前存在大量的多视图三角测量方法。但这些方法在SFM中使用时，鲁棒性有限或计算成本高，作者由此提出了一种鲁棒且高效的三角测量方法来解决这个问题。
3.2.4 Bundle Adjustment - 束调整
束调整是一种优化算法，用于同时优化3D结构点和相机参数（包括位置、方向和内参等），以最小化投影误差。简而言之，它通过优化所有相机视图和3D点的位置，使得预测的2D投影点尽可能接近实际观测到的2D点。
图像注册和三角测量是独立的过程，尽管它们的输出是高度相关的 —— 相机位姿的不确定性传播到三角测量点，额外的三角测量可以通过增加冗余来改善初始相机位姿。
如果没有进一步的细化，SFM通常会迅速漂移到不可恢复的状态。BA是摄像机参数和点参数的联合非线性细化，它使用一个将场景点投影到图像空间的函数和一个可能降权的离群值的损失函数来最小化重投影误差E。
Levenberg-Marquardt是解决BA问题的首选方法。BAN问题中的参数的特殊结构激发了Schur Complement trick （补技巧），首先求解简化后的相机系统，然后通过反替换更新点。这种方案通常更有效，因为相机的数量通常小于点的数量。求解该系统有两种选择：精确步进算法和非精确步进算法。
精确步进算法的复杂度相对较高。
非精确方法近似求解系统，通常使用迭代求解器，复杂度相对于精确法要低很多。
直接算法（Direct algorithms）是几百台相机的首选方法，但在大规模设置中过于昂贵，虽然稀疏的直接方法在很大程度上降低了稀疏问题的复杂性，但由于通常需要十分密集的连接图，因此不适用于大型非结构化照片集。
在这种情况下，间接算法成为了选择。
特别是对于互联网照片，BA花费大量时间优化许多几乎重复的图像。因此，作者又提出了一种方法来识别和参数化高度重叠的图像，以实现密集集合的高效BA。
四、挑战
本节提出了一种新的算法，该算法改进了SfM中存在的主要问题。
- 引入了一种几何验证策略，通过信息增强场景图，从而提高初始化和三角化组件的鲁棒性。
- 一个次优视图选择最大化鲁棒性和准确性的增量重建过程。
- 一种鲁棒的三角剖分方法，以更低的计算成本产生比目前更完整的场景结构。
- 迭代BA、再测量和离群值滤波策略，通过减轻漂移效应显著提高完整性和准确性。
- 通过冗余视图挖掘对密集照片集进行更有效的BA参数化。
这使得系统在保持其效率的同时，在鲁棒性和完整性方面明显优于当前的技术。
4.1 Scene Graph Augmentation - 场景图形增强
提出了一种多模型几何验证策略，利用适当的几何关系对场景图进行扩充。