Colmap论文之一：Structure-from-Motion Revisited

《Structure-from-Motion Revisited》

作者：Johannes L. Schönberger 和 Jan-Michael Frahm，分别来自北卡罗来纳大学教堂山分校和苏黎世联邦理工学院。

摘要：

• 论文探讨了增量式结构从运动 (Incremental Structure-from-Motion, SFM) 这一在无序图像集合中进行3D重建的策略。
• 现有的增量式SFM系统在健壮性、准确性、完整性和可扩展性等方面都取得了显著的进步。
• 作者提出了一种新的SFM技术，旨在建立一个真正的通用流程。
• 全面重建流程将向公众开放，具有开源实现。

引言

• 论文探讨了无序图像中的结构从运动 (SFM) 的发展趋势，这种技术已经经历了显著的革命。
• 提及了自校准的度量重建系统、自互联网照片集合、大城市和大规模的重建系统。
• 提到了多种SFM技术，包括传统的、基于层次的、全局的和递增的。
• 现有的增量式SFM尚未成功地解决无序照片集合的重建问题。
• 作者提出了一个新的通用方法，并介绍了一个名为COLMAP 的开源实现。
  

2. Review of Structure-from-Motion

• SFM是从不同视点的图像序列中重建3D结构的过程。
• 该方法是一个迭代的处理流程，从特征提取和匹配开始，然后通过几何验证。
• 描述了重建流程的不同阶段，包括场景图的构建和模型的逐步重建。
• 介绍了与增量式SFM相关的技术细节，如特征点匹配和场景图构建。

2.1 Correspondence Search ：

• 寻找重叠的图像输入，即那些在重叠图像中的同一点的投影。
• 输出是一组相机视图和特征点对的图。
• 具体地，每个特征点集 表示在特定位置 的局部特征描述符。
• 这些特征在不同的辐射和几何条件下应该是不变的，如SIFT和其他多种技术。

Feature Extractor

• SFM开始于从输入图像中提取特征点。
• 提取的特征点的质量和数量直接影响后续的匹配和3D重建。
• 使用不同的特征提取器，如SIFT，可以获取高质量的特征点。
  

Matching

• SFM试图匹配相同场景的图像。
• 该过程涉及寻找每个图像中的最相似特征，从而确定可能的图像重叠。
• 对于大型图像集合，直接进行逐对比较具有高计算复杂性。
• 论文引用了多种匹配策略来解决这一问题。

Geometric Verification

• SFM验证通过外观确定的匹配是否确实对应于同一场景点。
• 通过估计一个能够将两个图像之间的特征点映射到同一场景点的投影几何进行验证。
  • 解释：为了验证两个图像中的特征点是否真的代表同一个真实世界中的点，我们可以使用投影几何的原理来估计一个模型或变换。如果这个估计的模型/变换可以准确地将一个图像中的特征点对应到另一个图像中的相应点（代表同一场景点），那么我们就可以说这两个特征点确实匹配，并且代表同一个3D空间中的点。

2.2 Incremental Reconstruction

• 下一步是场景图重建，输出为姿态估计 和已重建的点集 。
• SFM初始化模型，确保始于一个可靠的初始估计。

Image Registration

• 进行度量重建（Metric Reconstruction）后，新图像可以通过求解透视-对-点 (PnP) 问题进行注册。
• 已经注册的图像和其特征点被纳入到已有的3D重建中。
• 新观测的3D点或者在其他摄像机视图中观测到的现有3D点可以被加入到重建中。
• 选择合适的初始对至关重要，因为重建可能永远无法从不良的初始化中恢复。
• 论文还讨论了使用增量式方法的其他细节和技术。

Triangulation

三角测量是计算机视觉和摄影测量中的一个关键技术，主要用于确定3D空间中点的位置。当从不同的角度或位置观察一个点时，通过跟踪这个点在两个或多个图像中的位置，可以使用三角法确定其在三维空间中的确切位置。

在Structure-from-Motion (SfM) 和其他3D重建方法中，三角测量是基本的步骤之一。具体来说，在SfM中，首先识别出图像中的特征点，并在多个图像之间找到这些特征点的匹配。然后，利用摄像机的姿态和内部参数，通过三角测量来估计这些匹配特征点在3D空间中的位置 。

在论文的上下文中，三角测量被用来观察现有的场景点。当一个新的场景点被观察到，它可以通过三角测量和现有的场景点被定位。此外，为了更准确地恢复三维结构，作者也讨论了一个强大和高效的三角测量方法。

三角测量的准确性对于3D重建的质量至关重要，因为小的误差会在后续的处理中放大，可能导致重建的不准确。因此，选择或设计一个稳健的三角测量方法对于高质量的3D重建是非常重要的。

Bundle Adjustment (BA)

• Bundle Adjustment 是3D重建中的核心优化技术，旨在改进相机参数和场景点的估计 。
• 这一过程的目的是通过最小化重投影误差来优化相机参数和3D点的估计，这通常是通过非线性最小二乘方法完成的。
• BA通常需要考虑很多因素，例如稀疏性、计算效率和稳健性。
• Levenberg-Marquardt被选择作为解决BA问题的方法。
• Schur补技巧是用于BA问题的一种优化方法，它首先固定结构参数，然后求解动态参数，并通过反向替代来更新点。
• 两种主要的求解技术是：精确方法和近似方法。精确方法通过存储和分解一个稠密矩阵来求解系统，而近似方法使用诸如共轭梯度的迭代方法来求解。
• BA的主要挑战之一是对于特定的数据集，可能需要优化数百甚至数千的相机。为了提高效率，很多策略已经被提出。
• 对于Internet图片，BA在优化大量非重复图像上花费了很多时间。

3. 挑战

• 当前的SFM算法在处理大规模、多样性图像集合时面临许多挑战。
• 有时系统可能无法注册一个稳定的图像，或者由于测量偏差或系统偏移，产生的模型可能是错误的。
• 如果不能建立一个完整的场景图，那么搜索就可能产生一个不完整的图。
• 重建过程中的两个关键阶段是：图像注册和三角测量。这两者有着紧密的关系，因为场景结构只能通过已注册的图像进行三角测量。
• 本文的目标是通过挑战提高SFM的完整性、稳健性和准确性。

4. 贡献

• 一个新算法，其在多个方面对现有SFM技术进行了改进。
• 新算法增加了场景图验证策略，提高了初始化和三角测量组件的稳健性。
• 为了提高鲁棒性，算法中增加了一种新的视图选择方法。
• 提出了一个鲁棒的三角测量方法，可以显著减少计算成本。
• 通过迭代BA技术，进一步提高了完整性和准确性。
• 与其他两种SFM方法相比，新方法在鲁棒性和完整性方面都表现出优越性，同时保持了计算效率。

4.1. Scene Graph Augmentation

• 这部分提出了一个多模型的几何验证策略来增强场景图。
• 首先，算法估计了一个基本矩阵。
• 若至少有 内连点，则认为图像对在几何上得到了验证。
• 接下来，通过转换分类的方式，将这些图像对分类为同一图像组、一般场景、全景或双平面之间的关系。
• 为了更准确地建模场景，算法考虑了内连点数与图像点数的比率。
• 该方法可以有效地处理复杂的多摄像机场景和各种其他情况。
  

4.2. Next Best View Selection

• 选择下一个最佳视图是一个关键步骤 ，因为每一个决策都会直接影响到余下的重建过程。
• 文章提到了一个基于不确定性的新策略，用于选择最佳的下一个视图 ，以优化三角化点数。
• 此方法强调了视图选择中的挑战性，特别是对于互联网照片，因为其选择不仅仅基于场景覆盖和相机参数，还基于完全依赖于信息驱动的决策。
• 这种方法旨在选择那些大部分已经被三角测量的图像 ，从而最小化由于观测的不确定性而导致的重建误差。

4.3. Robust and Efficient Triangulation

• 文章强调了对大型图像集合进行三角测量的重要性，这样可以提高三角测量的完整性和精度，并进一步改善随后的图像重建。
• 算法倾向于选择外观相似、基线小的图像对进行三角测量 。
• 为了提高效率和准确性，算法使用跨图像的传递性对应关系来进行三角测量。
• 许多不同的方法已经被提出来处理噪声较多的观测值。

这一节介绍了如何在存在大量异常值的特征轨迹中进行三角测量。为了做到这一点，提出了一个新方法，这个方法能够准确估计一个轨迹集合中所有点的真实位置。

• 当两个视图之间有许多不匹配的特征点时，这些不匹配的点可能会导致错误的三角测量结果。因此，需要一个有效的方法来排除这些异常值并提供准确的三角测量 。
• 该方法首先对两个视图进行三角测量，然后检查每个轨迹元素的合适性。如果找到了一个良好的解决方案，它将继续进行多视图三角测量。
• 这个新方法不只是对异常值进行过滤，它还尝试合并多个轨迹，这是必要的，因为同一场景中的不同点可能会投影到相同的位置。

这一节还介绍了RANSAC ，一种处理异常值的方法，用于增强三角测量的稳健性。RANSAC 常被用来鉴别匹配点之间的内点和外点。在两幅图像之间进行特征匹配时，可能会有许多错误匹配（外点），但也有正确匹配的点（内点） 。

4.4. Bundle Adjustment

为了减少在整个过程中累积的误差 ，这篇文章中提议了使用bundle adjustment（BA）。BA是一种常用的优化方法，可以同时调整相机的参数和场景结构以最小化投影误差。

• 作者建议在每个重要步骤后进行BA，尤其是在增加新的观测值之后。
• 文中提到，增长模型的速度是受限的，每次只增加一定百分比，这样可以保证每次BA的时间是线性的。
• 为了识别和处理异常值，使用了Cauchy函数作为鲁棒的损失函数。
• BA结束后，对观测进行进一步的过滤，以确保它们与模型是一致的。
• BA 的一个重要步骤是在全局 BA 之后检查像“全景摄像机或人为增强图像”这样的退化相机情况。
• 如果有摄像机的内部参数没有指定，那么它们会在 BA 中自由优化。尽管在某些情况下，这些参数（例如图像中心）可能会被固定。
• 为了解决全局 BA 之前由于漂移效应而产生的问题，提出了重投影（Re-triangulation, RT）技术。
• BA 的目的是改进相机和特征点的参数 。因此，文中提出了一个迭代方法，首先执行 BA，然后进行后 BA 重投影步骤 。
• 如果某些观测值在 BA 中被视为异常值，则它们会被随后过滤掉。由于 BA 的执行可以显著提高结果，因此提议在 BA 之后多次执行 BA，并过滤异常值 。大多数情况下，经过两次迭代后会发现模型稳定性得到改善。

这两部分强调了在进行场景重建时如何确保结果的准确性和稳健性。三角测量和BA都是3D重建中非常重要的步骤，而这篇文章提出了一些新方法和优化，使得这些步骤更加有效和鲁棒。

4.5. Redundant View Mining

• 在结构从运动（SfM）中，BA 是一个主要的性能瓶颈 。为了更有效地完成 SfM，文中引入了冗余视图挖掘 。
• 很多的互联网照片集合都有高度非均匀的视频内容，并且经常有大量的无序集合。因此，利用已有的研究，特别是那些可以利用冗余相机的研究，是很有用的。
• 为了有效地对相机和点进行分组，提出了一个方法，该方法通过分离变量将相机和点分组到子图中。

在提出的方法中，考虑了相机和点参数的图割问题，并在固定相机参数和点参数之间交替进行 BA。此外，还考虑了如何更高效地构建 SfM（当说到“构建 SfM”时，指的是从多个二维图像构建出一个三维场景模型的整个过程。这不仅包括空间中的物体结构，还包括摄像机的移动路径和方向。），尤其是考虑到对相机内部参数的控制，以及如何用更少的成本来构建大型的照片集合。

总之，文中介绍了一个更高效、更准确的方法来执行结构从运动，并特别强调了在实践中如何处理大量的照片集合。这种方法考虑了许多实际问题，如摄像机参数的退化、冗余视图的挖掘、以及如何在大型照片集合中有效地执行 BA。

文章还描述了如何使用“下一最佳视图”得分（如图所示）为高斯分布的点选择图像，这些点具有平均值和标准差，并考虑了与统一性的得分和点数。此外，还介绍了一种启发式方法，通过限制在视角方向上±β度范围内的空间最近邻来加速查找Ib的时间。这种方法的背后思想是，具有相似视角的图像更有可能共享许多点。

每个图像在与通用组局部坐标框架相关的参数化下都进行了处理。接下来定义了组图像的BA（束调整）成本函数（方程式 (7)）。这个函数考虑了每个图像的投影误差，其中包括组的外部参数Gr以及固定的摄像机内部参数Pc。图像在组内的投影矩阵是通过组和图像姿势的连结来定义的。

总的成本函数Es是分组和非分组贡献的总和。为了有效地计算Gr和Pi的旋转分量，文章中提到，组的大小在一定程度上会导致更好的性能。这是因为，与处理单独的摄像机相比，处理包含两个或两个以上摄像机的组在计算上有利。另外，由于计算的直接方法，增加摄像机的数量会导致计算复杂性呈立方增长。

这些内容提供了冗余视图挖掘的更深入的细节和实现，突出了其在结构从运动（SfM）过程中的重要性。

参考文献：