Colmap论文——《Structure-from-Motion Revisited》论文阅读笔记
最近又重新翻阅了Colmap的经典论文，并进行了深入的学习与总结。于是顺手在博客上记下一些笔记。其中，《Structure-from-Motion Revisited》被认为是目前最优解（SOTA）的增量式SfM方法之一，并由Colmap团队提出。该方法被视为增量式结构从运动领域的里程碑性贡献。
- 论文地址：https://openaccess.thecvf.com/content_cvpr_2016/papers/Schonberger_Structure-From-Motion_Revisited_CVPR_2016_paper.pdf
- 论文代码：http://colmap.github.io/
1 增量式SfM流程
如上图所示，作者将其分成两大部分：Correspondence Search和Incremental Reconstruction。
Correspondence流程是：首先对所有的输入图像进行特征提取，这通常是由稳健的SIFT算法实现的；然后使用提取的特征点描述子进行匹配，一种暴力方法是穷举所有可能的匹配对，但是这在大场景情形下是不可接受的；匹配完成后，还需要使用对极几何关系对每个匹配图像对里的匹配点对进行精化，因为通常会存在很多误匹配点对。
Incremental Reconstruction流程是：初始化部分是寻找一对初始的匹配图像对，这个图像对的选择对后面的重建过程非常重要，所以通常需要精心筛选。论文提到，初始图像对之间的匹配点数量越多，通常可以获得更为鲁棒和精确的结果；而如果匹配点数量较为稀疏，则重建速度会更快，因为BA（Bundle Adjustment）求解的问题较小。选定匹配对后，利用对极几何关系分解获得两张图像的位姿，然后三角化生成三维点。接下来，每次往系统中增加一张新的图像，通过PnP（Perspective-n-Point）估计它的位姿，然后三角化生成新的三维点，之后进行BA优化，BA过程中滤除外点。直至所有图像都被加入系统中。
2 本文贡献
本文指出，在现有SfM系统的重建效果上仍存在明显缺陷，并对其局限性进行了深入分析。针对上述问题进行优化改进的基础上提出了一种新的解决方案，并在此基础上实现了以下几项主要创新：1) 增强重建效果；2) 提高算法效率；3) 优化鲁棒性指标；4) 降低计算复杂度；5) 提升模型泛化能力等创新性成果。
- 一种增强几何验证方法在初始化阶段和三角化过程中的鲁棒性
- 一种最大限度地兼顾鲁棒性和准确性的候选图像最优配准方案
- 一种能够构建更加详尽场景结构的同时显著降低计算复杂度的方法
- 基于BA框架的迭代优化算法，在显著提高重建质量和稳定性的同时有效抑制累积误差传播
- 一种并行优化框架用于高效提取密集图像集中高价值特征
2.1 场景图增强
利用合适的几何关系去增强场景图，内容包括：
- 首先计算图像对的基础矩阵F（Fundamental Matrix），若内点数量超过NF，则该图像对通过几何验证。
- 接着计算单应矩阵H（Homography Matrix），统计有效点数量NH；若NH与NF之比小于εHF，则判断为一般场景。
- 对于已知相机参数K的图像，在此条件下估计本质矩阵E（Essential Matrix），并统计NE；若NE与NF之比大于εEF，则认为校准正确。
- 当满足步骤2和步骤3时，则判定为常规校准场景；此时分解本质矩阵E，并利用对应内点进行三角化计算。
- 计算三角化角度的中位数值αm；根据αm值判断场景类型：若αm接近180度则为全局旋转场景；否则属于平面场景。
- 为了识别网络图像中的水印信息以及其他元数据（统称为WTF），计算图像间的相似变换关系，并统计边缘有效点NS；若某对图像中NS与NF之比超过εNF或NS与NE之比超过εNE，则判定为异常WTF图像。
- 在场景图中所有成像对中选择具有最多特征的情形进行分类标记：即选择一般场景、全景场景或平面场景中的最大类。
- 初始选取成像对时，默认优先选择非全局旋转且具有已知内外参数的情况。
2.2 下一最佳视图选择
下一理想视角的选择对位姿估计的质量、三角化的完整性与精度受显著影响。研究指出,一个流行的方法是,寻找一张能观察到最多已三角化的点的图像。然而,有时该图像的观测条件数并不理想。研究发现,如果匹配点的分布越均匀化,则其重建结果也会更加优异。因此,研究者们提出了一种基于多尺度网格的新方法,用于量化匹配点的空间分布状况。
如图所示，在作者的研究中将图像划分为不同尺度的格网结构，并对每个尺度下的格网点进行分布情况进行打分。这种评价方法既能考虑点的数量也能考虑点的分布情况以全面评估图像的质量表现综合而言该评价体系能够较为客观地反映图像特征在具体实施中通过纵向对比分析了点分布的变化趋势及其对应的分数变化规律同时横向比较了不同密度下所得分数之间的差异具体而言分数计算采用加权求和的方式即每个维度的重要程度通过权重系数加以体现最终得到总评值S=∑_{i=1}^n w_i s_i
在不同匹配图像上进行打分后，在所有评分中选出评分为最高的那个作为下一个最佳匹配候选图片。实验证明这一策略能够提高重建过程中的稳定性和准确性。
2.3 鲁棒高效的三角化
该作者开发了一种高效且基于采样的三角化算法；该方法在存在异常值干扰的二维特征点集上仍能可靠地恢复三维空间点。其中τ代表任意一种三角化的策略；其中Colmap系统中通常采用直接线性变换（DLS）技术。
作者避免了对全景图像进行三角化操作，在实际应用中可能会因位姿估计出现偏差而导致产生的三角化点存在误差现象；为了实现有效的立体视觉效果，在实际应用中应具备以下三个必要条件：
- 相机位置与三角化点形成的夹角α应足够大：
- 三角化生成的三维点投影回图像上的深度值应该为正：
- 重投影误差小于阈值t：
作者采用RANSAC方法对三角化点进行选取样本点，并剔除outliers的影响。实验结果表明，所提出的方法能够在提高三角化完整性的同时降低计算复杂度。
2.4 BA
作者提出了一种BA优化策略：每当加入一张新图像时，在与该图像高度相关的部分执行局部BA操作；只有当模型规模达到一定程度时才会进行全局BA调整。这种设计有助于降低计算开销。
2.4.1 参数化求解方法
基于抗异常点影响的Cauchy核函数被选用作为鲁棒损失函数以应对outliers的影响。根据重建问题的不同规模,采用适应不同规模的问题的具体解决方案:当图像数量在几百张左右时,通过稀疏优化技术实现快速收敛;而当图像数量超过几百时,则采用预条件共轭梯度法以提升计算效率;针对不同的应用场景,基于相应的相机参数设置选择最优的方法进行建模与优化。
2.4.2 过滤
每次BA过程中
2.4.3 再三角化（RT）
为了增强重建场景的完整性，在筛选出先前被剔除但偏差相对较小的三维点后进行重新计算。维持当前设置的前提下，在误差低于原始筛选标准的情况下对相关观测进行重新计算。
2.4.4 迭代精化
由于位置漂移（shift）或者位姿推算误差的存在，在三维空间中通常会有大量本来属于物体的实际三维点被错误地剔除出去；然而通过分两步实施Bundle Adjustment（BA）处理，则能够明显提高结果精度。为此需要不断迭代处理BA（Bundle Adjustment）、重投影校正（RT）、去噪等步骤，并持续去除那些被剔除的数据以及重新三角化的数据；经过第二轮迭代后整体提升较为明显。
2.5 冗余视图处理
BA常被视为SfM性能的主要瓶颈。鉴于此，在面对大重叠度场景时，作者提出了高效的相机分组优化策略以替代那些昂贵的图割操作。与将多个相机归入同一子图相比，在这种新方法中作者将场景划分为许多高度重叠的小相机组，并用一个自由度更高的相机取代每组相机（从而减少BA优化中的自由参数数量）。
当物体在某一区域内的共视度超过预设阈值时，在满足每组内部包含的图像数量不超过设定上限的前提下，将对应的图像归入相应的分组。为确保各分组内部相机位置与姿态的一致性需求，在每一类分组中采用局部坐标系来进行相机参数的建模。针对所述图象群落中的BA损失函数如式（1）所示：
其中，
Gr代表了图像组共用的外参参数，
Pc代表了每张图像内部的姿态参数(即位姿)。
在优化过程中，
其姿态参数满足Pcr = Pc \times Gr的关系，
且由于Pc是一个固定的参数，
在整个优化过程中保持不变，
因此，
在Bundle Adjustment（BA）算法中，
自由变量的数量得到了显著的减少。
3 总结
Colmap针对现有SfM方法存在的问题进行了系统性改进，在增量式重建过程中建立了完善的优化策略，并显著提升了场景重建的完整性与效率的同时大幅增强了其鲁棒性和准确性。尽管该论文于2016年发表并提出时间已过去近十年之久但仍被广泛认为是增量式SfM领域的代表性算法具有极强的应用价值并持续发挥着重要的参考作用。