最近又将Colmap论文翻出来仔细阅读总结了一下，于是顺便写个博客记录一下。Structure-from-Motion Revisited是当前SOTA的增量式SfM算法Colmap的论文，发表于2016年计算机视觉顶会CVPR。它是增量式SfM里程碑式的作品。
- 论文地址： 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系统在重建的完整性和鲁棒性（completeness and robustness）上还是存在缺陷。本文对此进行了改进，主要贡献包括：
- 一种提高初始化和三角测量鲁棒性的几何验证方法
- 最大化鲁棒性和准确性的次佳匹配图像选择策略
- 一种鲁棒的三角剖分方法，可以获得更完整的场景结构且计算成本更低
- 一种迭代BA、重三角化、外点滤除策略，显著提升重建完整性和精度，减轻漂移影响
- 一种用于挖掘密集图像集间的冗余视图的高效BA参数化方法
2.1 场景图增强
使用适当的几何关系增强场景图，包括：
- 首先估计图像对的F矩阵（fundamental matrix，基础矩阵），如果内点数大于N
F
，图像对通过几何验证。 - 然后估计H矩阵（homography matrix，单应矩阵），统计内点数N
H
，如果N
H
/N
F
<ε
HF
，它被认为是一般情况。 - 如果是校准过（知道相机内参K）的图像，估计E矩阵（essential matrix，本质矩阵）并计算内点数N
E
，如果N
E
/N
F
>ε
EF
，校准被认为是正确的。 - 如果同时满足2和3，则为一般的校准场景，分解E矩阵，并使用对应的内点匹配进行三角化。
- 计算三角测量角的中值 α
m
， 用一个
m
判断是纯旋转（全景）还是平面场景（平面）。 - 为了检测网络图像的水印、时间戳、边框等（统称WTF），通过估计图像间的相似变换并计算图像边缘的内点数N
S
，如果某对图像的N
S
/N
F
>ε
NF
或者N
S
/N
E
>ε
NE
，则认为这是一对WTF图像，不加入到场景图中。 - 对于场景图中的所有图像对，将场景图的类型标记为图像对最多的情况（正常、全景、平面）。
- 初始图像对倾向于选择非全景的校准图像对。
2.2 下一最佳视图选择
下一个最佳视图选择对姿态估计的质量、三角测量的完整性和准确性有很大影响。作者提到，一种流行的方法是找到一个图像，该图像观察到已被三角剖分最多的点。但是，有时图像的观察条件数并不好。研究表明，匹配点分布越均匀，重建效果越好。因此，作者提出了一种使用多尺度网格来衡量匹配点分布的方法。
如上图所示，作者将图像划分为不同尺度的网格，然后对不同尺度的网格点分布进行打分，这样可以同时考虑点数和分布的影响。一般来说，点数越多，分布越均匀，该图像的得分就越高。上图中垂直方向是点分布差异和分数差异的比较，水平方向是点数和分数的比较。分数计算如下：
在对不同的匹配图像进行评分后，选择得分最高的图像作为下一个最佳匹配图像。实验表明，使用该策略可以提高重建的鲁棒性和准确性。
2.3 鲁棒高效的三角化
作者提出了一种高效的、基于采样的三角化方法，它可以从受异常值污染的特征点中鲁棒地估计出三维点。三角化的公式如下所示。其中τ指代任意一种三角化的方式，Colmap里用的是DLT（Direct Linear Transform，直接线性变换）。
作者不对全景图像进行三角剖分，这可能会由于错误的姿态估计而产生错误的三角剖分点。适合三角剖分的图像对应满足以下三个条件：
- 相机位置和三角点形成的角度α应该足够大：
- 投影回图像的三角剖分生成的 3D 点的深度值应为正：
- 重投影误差小于阈值t：
作者使用RANSAC方法对三角化点进行采样，从而剔除outliers的影响。实验表明，所提出方法可以在提高三角化完整性的同时减少计算量。
2.4 BA
作者提出的BA优化策略是：在每次增加一张新图像后，只对与该图像有最大关联的一部分图像进行局部BA。当模型增加一定比例之后，才进行一次全局BA。这样做可以减少计算的代价。
2.4.1 参数化求解方法
使用Cauchy核函数作为鲁棒损失函数来应对outliers的影响。依据不同大小的重建问题，使用不同的求解策略。对于数百张图像的情况，使用sparse方法进行求解；对于更多张的图像，使用PCG进行求解。对不同问题，采用不同的相机模型进行求解。
2.4.2 过滤
每次BA过程中，将重投影误差较大的三维点过滤掉。在优化过程中，使相机焦距和畸变参数自由优化，然后在全局BA后，将视野不正常或者畸变参数大的相机视为错误估计，并进行剔除。
2.4.3 再三角化（RT）
为了提高重建场景的完整性，对之前过滤掉但偏差不大的 3D 点进行重新三角化。不要提高三角测量阈值，仅对误差低于过滤阈值的观测值重新进行三角测量。
2.4.4 迭代精化
由于漂移（drift）或者错误的位姿估计，通常会有很大一部分三维点被错误滤除，而使用两步BA可以显著提升结果精度。因此，迭代进行BA、RT、过滤，直到被滤除的观测点和再三角化点减少。大多数场景下，在第二轮迭代过后，结果就会有显著的提升了。
2.5 冗余视图处理
BA是SfM性能的瓶颈。因此，作者针对大重叠度场景提出一种高效的相机分组优化策略，代替了昂贵的图割操作。与将很多相机聚类到一个子图上相比，作者将场景分割成很多小的、高度重叠的相机组，然后将每组相机使用一个（自由）相机来代替（这样可以减少BA优化过程中自由参数的数量）。
通过图像之间的共视程度来决定哪幅图像归于同一组。具体的，对于一个具有n个三维点的场景，使用一个{0，1}向量来表示每张图像的观测，若观测到该三维点，则为1，否则为0。然后通过交集/并集来获得共视程度，如下式所示：
若共视程度大于阈值且组内图像数量小于阈值，则将该图像加入该组。在每组内使用局部坐标系来参数化组内的相机。针对图像组的BA损失函数如下式所示：
其中，Gr是图像组共用的外参，Pc是组内每张图像的位姿。在进行优化的时候，组内每张图像的位姿为Pcr=PcGr，其中Pc在优化过程中固定不变，Gr可变。如此，BA优化时候，自由变量的数量就大大减少了。
3 总结
Colmap针对当前SfM存在的问题进行了充分的改进，它针对增量式重建的每一个步骤都提出了新的优化方法，从而提高了重建场景的完整性、鲁棒性、精度、效率等。虽然该论文是2016年提出的，但时至今日，它仍被认为是SOTA的增量式SfM算法，仍有很强的借鉴意义。
文章出处登录后可见！
