今天要介绍的是J. L. Sconberger等人于2016年发表在CVPR的文章。本文针对增量式SFM中三角化/BA等步骤进行了改进，能够比较明显地提升SFM的精确率/鲁棒性以及重建完整性。
首先给出代码 教程：
Code: https://github.com/colmap/colmap
官方教程：https://colmap.github.io
在公众号「3D视觉工坊」后台回复colmap获取，下面是COLMAP软件的使用教程，感兴趣的同学可以看看。
SFM 基本套路回顾
SFM通常首先进行特征提取/匹配以及后续的几何校验滤出外点，经过上述步骤可以得到所谓的场景图「scene graph」，该场景图是后续的增量式的基础（提供数据关联等信息）。增量式重建中需要非常仔细地挑选两帧进行重建，在图像进行注册（即定位当前帧在地图中的位姿）之前，需要进行三角化场景点/滤出外点以及BA优化当前的模型。
检索匹配
输入：一系列输入图片；输出：经过几何校验后的图像匹配关系。
为了得到尽可能准确的匹配关系，该步骤中涉及特征提取，匹配以及几何校验。
- 特征匹配：可以是任何一种特异性较强的特征，如SIFT（COLMAP默认），主要为后续的特征匹配服务；
- 匹配阶段，将输入的图像两两之间进行匹配（可以发现，这一步的时间复杂度非常大），得到潜在的场景重合部分；
- 几何校验：初始匹配的外点势必很多，此时需要滤出外点。通常情况下会用到基础矩阵（未标定）/本质矩阵（已标定）以及单应矩阵（纯旋转/共面）。图像经过上述三个步骤之后的输出为「scene graph」，即图像是节点，几何校验后的匹配对是边。
增量重建
输入：「scene graph」；输出：相机位姿以及3D路标点；
为了完成增量重建，需要完成初始化，图像注册，三角化以及BA优化这些步骤。
- 初始化：SfM在初始化时需要非常仔细的选择两帧进行重建；此时需要尽量选择「scene graph」中相机间可视区域多的两视角进行初始化，文中称这种选择增加了“redundancy”进而增加了重建的鲁棒性与精确性。
- 图像注册：即根据已有的SfM模型估计图片的位姿（更准确的是估计拍摄该图像相机的位姿）；根据未知的图像与地图中图像的2D-2D匹配，进而得到二者之间的2D-3D匹配，然后利用RANSAC-PNP解算出该相机位姿，完成图像注册。为了提高位姿结算精度以及可靠的三角化，本文设计了新颖的鲁棒后续帧选择策略，后续章节进行介绍。
- 三角化：新注册的图像需要对已有的场景点有足够多的观测，同时也可以通过三角化扩展场景点。现有的三角化方法鲁棒性不足且耗时严重。本文设计了一种全新的三角化策略，后续章节进行介绍。
- BA优化：由于图像注册与三角化是分开进行的，但二者是强相关的两个过程：错误的位姿会导致错误的三角化点点产生，反之亦然。所以此时，我们做SLAM的都知道是时候让BA上马了！BA能够同时优化相机位姿以及地图点，使模型的redundancy更强。这里顺便提一下BA，优化目标是通过调整相机位姿与地图点位置使重投影误差最小：
BA问题通常可以通过LM算法进行求解。作者提到，当SfM面对网络图像时，特别对于那些几乎一样的图像时，上述优化过程会占用极长的时间。本文尝试对该问题进行解决，后续章节进行介绍。
本算法的创新点
本文的贡献主要有以下5个方面：
- 提出了一种多模型几何校验策略：提高了初始化与三角化的鲁棒性；
- 后续最优帧选择策略：提升位姿结算鲁棒性与精度；
- 提出鲁棒三角化方法：使得重建的场景结构更加完整；
- 提出迭代BA，重三角化以及外点滤除策略对重建的完整性与精度都有贡献；
- 高效BA参数化方法对稠密图像的重建具有帮助；
场景图增强
采用了一种多模型几何校验策略增强场景图。对于输入的图像对，具体过程如下：
- 首先估计基础矩阵
，若此时的内点数大于
，则认为图像对满足几何校验通过；
- 然后估计单应矩阵
，记内点数为
；若
，则认为该场景为常规场景(general scene);
- 对于已经标定的相机，估计本质矩阵
，记内点数为
；
- 若
，则认为此时相机标定参数是符合要求的；
- 若此时场景符合标定且为常规场景，通过分解本质矩阵得到相机位姿，然后对点三角化，计算三角化点点平均角度
；随后利用该角度判断场景是纯旋转(pure rotation, panoramic)还是平面(planar scenes, planar）。
- 最后一步是为了应对网络图片存在的问题而设计的，网络图像可能存在的问题有水印(watermarks)/时间戳(timestamps)/镶边(frames), WTFs。此时计算图像对的相似矩阵
，记录图像对在图像边缘的内点数
；若此时，则认为该场景为WTFs，此时该图像不加入场景图。
综上，通过统计几种几何校验的内点数，根据设计的条件，判断出了该模型的类型：常规，全景，平面(general, panoramic, planar)。模型类型用于仅从非全景和已标定图像才参与重建。
注意：不对全景图像进行三角化，以避免退化点，可以提高三角化和后续图像注册的鲁棒性。
后续最优帧选择
参与重建的图像的选择对重建的效果的影响是非常大，若选择了不好的图像，可能会导致相机无法注册或者三角化失败。
通常的做法是选择能看到三角化点最多的图像进行注册。但仅数量多并不意味着好，文献[1]已经通过实验验证「PNP位姿解算多精度不仅与观测点数量相关而且与观测点在图像上的分布有关」：若点分布越均匀，位姿结算精度越高。
作者认为：可见点的数量越多且分布越均匀得分
越高，得分越高点的图像越会被先注册。于是作者设计了一种多尺度统计点分布点算法，具体见上图。将图像划分成
层，每层划分为
个格子，其中
（
），同时给每一层设计一个权重
（原文有误），然后统计可见点在每层上的得分并累加。上图所示的得分计算如下(左滑查看全部)：
可见在同样点数量下，点分布越均匀得分越高。
鲁棒高效三角化
作者提到，如果地图点能够被持续观测，这样可以使大基线情况下的图像也能够关联得不错，这对重建是有利的。但与此同时，特征追踪过程中可能由于外观相似的特征导致错误匹配，这样帧间三角化就会出现错误，这种现象在实际过程中是比较常见的！
本文使用了RANSAC对多帧观测进行三角化。记特征追踪
，它是由一系列的外点率
未知的观测构成的集合。观测Tn包括归一化坐标
以及它对应的投影矩阵
。最终目标是最大化三角化模型对观测的复合程度，于是三角化的点
为：
其中是任何一种三角化方法(本文使用了DLT[2]方法)。一个比较好的三角化点需要满足两个条件：
- 足够大的三角化角度；
- 三角化点深度为正，且该点的重投影误差小于阈值
；
值得注意的是，三角化的过程中使用了RANSAC，即从上述特征追踪中随机选择2个点(一对点)进行三角化，统计内点数(即，重投影误差小于阈值记为内点)，选择内点数最多的那个作为三角化点。这个过程中存在一个问题：假如该点被追踪到了比较少的次数
，此时随机采样会重复选择相同的一对点进行三角化，这样会造成不必要的资源消耗。本文设计了一种可以产生不重复随机组的random sampler；另外，为了能够保证以置信度为的概率至少选择一对无外点的最小解集，该过程至少重复进行
次。
BA优化
为了消除累计误差，在图像注册以及三角化之后需要进行BA优化。由于增量式重建仅会影响邻近帧，所以没有必要每次都做GBA。因此，当图像被注册之后仅对相关性最好的图像集合进行LBA即可。只有当模型增长到了一定程度才会对进行GBA，这可以分摊时间消耗。
- 参数化：LBA中使用柯西核函数应对外点；当优化中有数百个相机时，使用PCG求解器；
- 滤外点：BA之后，由于相机位姿/地图点发生了变化，此时会有很多不符合要求的观测，删除掉那些重投影误差较大的观测；然后检查几何校验条件是否满足；对于GBA，还要检查相机是否退化；
- 重三角化(post Re-Triangulation, post RT)：由于BA对位姿进行了优化，这使得之前由于不准确/错误位姿导致无法三角化的点有了能够被重新三角化的可能性，所以在BA之后执行一步重三角化(类比于BA之前的三角化)；
- 迭代优化：受到外点的影响，一次BA通常会导致很大一部分点被滤除，然后经过post RT对地图点进行了扩充；作者提到，上述过程需要多做几遍，一般是做完第二遍之后模型的完整性就会得到非常不错的提升。
冗余视角删除
BA是SfM的瓶颈，本文针对“稠密数据采集”带来的问题设计了一种高场景覆盖度的图像聚类的BA参数化策略。
本文主要改进了文献[3]提出的方法，具体操作如下：
图像与地图点根据重建过程中是否受到最新帧点影响分为两类。对于比较大的重建问题，最新的重建帧仅会影响其邻近的图像以及地图点，很大一部分图像/点并不会发生改变。本文将不受影响的那部分定义很多组的集合
，其中
表示一组「高重合度」的相机，它被参数化为「一个相机」。那么问题来了，什么才叫做高重合度呢？作者提到，一个组内相机的共视区域必须高度重合。令场景中共有
个点，那么每一张图像都可表示成一个二值向量
，其中当某个地图点被观测到时为1，否则为0；有了以上定义之后，我们可以定义图像
与图像
之间的重合度
为：
之后呢，对待处理帧的
个空间最近邻的那些图像计算重合度得分并排序，这样可以构造一组「高重合度」的相机集合。对于这一个相机组的BA (Group BA)损失被构造为如下形式：
上式中
表示该组的外参变换，
表示组的固定位姿。全局的损失函数是所有组/非组的BA损失之和。经过上面一顿操作之后，BA优化的效率得到了大幅度提升。
实验
模块测试
可以看到三角化采样的数量有了大幅度减少。
增加Group BA之后，GBA的次数大幅度减少。
三角化以及GBA耗时下降。
系统测试
总结
本文提出了一套集精度/鲁棒性以及完整性为一体的通用SfM框架，实验表明该方法能够获得非常好重建效果。该框架进行了模块化实现，且开源，到目前为止很多视觉三维重建的任务(如视觉定位[4])基于此项目完成(框架不变，提升模块性能)，可谓“功德无量”。
参考
[1]: V. Lepetit, F. Moreno-Noguer, and P. Fua. EPnP: An accurate O(n) solution to the PnP problem. IJCV, 2009. 2, 4.
[2]: R. Hartley and A. Zisserman. Multiple view geometry in computer vision. 2003.
[3]: K. Ni, D. Steedly, and F. Dellaert. Out-of-core bundle adjustment for large-scale 3d reconstruction. ICCV, 2007.
[4]: Long-Term Visual Localization, https://www.visuallocalization.net/
本文仅做学术分享，如有侵权，请联系删文。
