本文主要记录Colmap中增量重建SFM的一些基本框架。整个增量重建的框架大致都可以分为
特征提取（Feature extraction）
特征匹配（Feature matching）
增量重建（Icremental mapping）
特征提取
Colmap中使用的主要是Sift特征及其变种DSP-Sift。输入的彩色图像在被读入时只保留灰度，之后先会进行一个resize的操作，colmap中有一个参数可控制最大能处理的像素数，默认是3200.这个resize操作可以使得针对不同的输入图像，内存（显存）以及运算时间可以大致控制在一定的范围内。特征提取部分的细节可以参见https://www.jianshu.com/p/94196a92cc18 。在完成特征提取之后，会有一个ScaleKeyPoints的操作，将resize后找到的特征点重新映射回原图的像素坐标。另外，对于有mask的情形，Colmap的做法是只保留在mask之内的特征点。
特征匹配
特征匹配模块干的事情是根据特征，去创造图与图之间的对应关系，这些对应关系将用来重建位姿及稀疏点云。本质上，特征匹配的结果是一个Scene graph，这个图的节点为单个图像，边代表这两张图能匹配上，而边的权重则可以是匹配的特征对数或者匹配的一致的特征对数。具体来说，需要解决几个问题
大量图的输入，采取何种匹配模式？
找到匹配图对后，如何构建匹配关系？
如何定义匹配是否成功？
匹配模式
这里主要介绍一下Colmap中两种常见的匹配模式：sequential和exhaustive。假设输入有张图，我们要确定图与图之间的关联，一种直接的想法就是两两去计算匹配关系，这就对应了exhaustive模式，而另一种情形是，拍摄时图像是有空间关联的，即相邻拍摄的图像有很大概率是有大重叠的，这时我们就可以只计算相邻的一些图像之间的匹配关系，这也就是sequential模式。二者的区别在于计算匹配的数量，对应了不同的计算时间。特别地，如果采集的数据满足可以分成多组，每组内拍摄图像有空间关联，则可以创造出一个新的匹配模式，我们称之为mixed的模式。
| 匹配模式 | 匹配次数 | 备注 |
|---|---|---|
| sequential | 一共 |
|
| exhaustive | 一共 |
|
| mixed | 一共 |
如下为一个绕物体拍摄两圈的示例，采用了mixed模式，左边为scene graph，右边为对应的位姿恢复结果。
如何匹配？
Matcher: sift特征对应的是一个128维的向量，匹配的过程就是对于任意一个特征点，在另一张图中找另一个特征点使得他们之间的特征向量的差距最小，这是通过flann来实现在高维空间寻找最近邻来实现的。
匹配成功？
TwoViewGeometryVerify: 将上一步匹配上的匹配对，通过RANSAC去估计基础矩阵F或Homography矩阵H，然后计算inlier的数目，当inlier的数目超过设定阈值（默认15）时，即可认为匹配成功。
如果guided_matching设成了true，那会增加一步检查特征点匹配对的重投影误差，具体是估计 和0的差距，差距过大的特征点匹配对会被剔除inlier。
增量重建
所谓增量重建是指位姿的估计，稀疏点云的重建都是逐步完成的，每次增加一个图像，获取其位姿，更新稀疏点云。具体而言，主要的步骤包括：
寻找初始匹配对，并三角化求解位姿及稀疏点云
寻找下一张用于重建的图像，并估计位姿，更新稀疏点云
不定时的局部或全局优化
初始匹配对的确定
初始匹配对的寻找是基于上面提到的scene graph进行的。我们将匹配数目最多的图像，即在graph中边最多的节点当做初始匹配对的第一张图，然后再在其所有边连接的节点中寻找第二张图。基本原则是按照节点连接的边数来排序，对于每一个candidate，检查其与第一张图三角化的结果，只要内点数目大于一定阈值（默认100），角度大于一定阈值（默认16度）且不是沿垂直于相机方向前后移动（z分量<0.95），即可被选作第二张图像。如果不符合，则顺延找下一张，直到找到满足条件的为止。如果第一张图对应的匹配对都不满足条件，则按照边的数目排序找下一张图当第一张图，再重复上述的操作。初始匹配对的选择一般要求条件较好，它选择的不好的话，会影响后续所有的重建，因此条件会比较严格。
下一张重建图的确定
在挑选下一张图进行重建时，主要是根据当前三维稀疏点云在该图上的可见点信息来确定的。一种容易想到的方式是根据可见点的个数或者占总特征点的比例来选择，而Colmap中默认是通过VisibilityUncertainty来做排序选择的。这个所谓的不确定性其实描述的是可见点的二维投影点（特征点）在图上的分布，越分布得开，越分布得广，对应认为结果更为鲁棒。具体而言，会在不同的图像分辨率上根据可见特征点所占有的像素个数打分，然后对不同分辨率加权，最终得到一个分布的分数。根据上述分数，对所有图进行排序，按顺序选择图来进行尝试。当然，被选中的图需要满足一些基本的特征，比如可见点的个数至少要达到10个。
确定好下一张图后，就需要对其进行增量式重建了，主要是恢复其位姿并补充稀疏点云。
位姿恢复的方法就是基于PnP（Perspective n points）。之前重建出的稀疏点云，每一个点都对应着一个track，这个track中记录了该三维点对应于哪张图像的哪个2D像素。根据2D的对应关系，可以知道当前图哪些点和稀疏点云的点有对应关系，因此问题转化为优化相机内参和外参，以保证这些3D点能正确投影到其对应的2D点。优化的过程大致可分为三步，第一步是确定内参。以pinhole模型为例，Colmap中需要优化的内参只有焦距，中心默认是在图像的中心。如果焦距信息能从图像EXIF中获取，则直接获取，如不能则需要额外优化。Colmap的优化其实是在可能的焦距取值空间均匀采样，对于每个采样点的焦距，再去优化外参（旋转及平移）。在所有的这些优化结果里边，挑一个最好的当做焦距，对应的优化外参也就确定了。第二步是外参的优化，外参的优化是采用RANSAC来完成的，在焦距固定的情况下，找出内点数最多的一组参数。第三步是一个重投影误差的优化，这一步以上两步得到的结果为初值，再进行一轮非线性的优化，以找到更好的参数组合。
有了位姿之后，就需要根据2D的对应关系，进行三角化，补充生成稀疏点云，以及更新对应点的track。
当所有的图像都尝试了，却仍然找不到满足条件的下一张图，则自动进入上一个流程，重新寻找初始匹配对，这样的结果会导致稀疏重建出现多个孤立的重建结果。
局部及全局的优化
SFM由于累积误差，在进行一段时间的增量重建以后，重建的位姿就将偏离真实的位置，需要通过局部和全局的优化（Bundle adjustment）来解决。不管局部还是全局的Bundle adjustment，优化的都是重投影误差，代价函数可以写成
其中，代表第
个相机的投影矩阵（内外参），
代表第
个三维点，
代表投影映射，即将3D点
投影到第
个相机平面，
为三维点
在第
个相机的对应点，
代表常用的二范数，
代表权重。局部与全局的区别在于代价函数中参与求和的相机个数和3D点的个数。
Colmap中每次加入一张新的图进行重建以后，都会进行一次局部的优化（IterativeLocalRefinement）。此时局部的定义是指，代价函数中只使用与新加的这张图共有3D点数最多的几张图，同时只使用track长度小于15（即能看到该3D点的2D图像数目<15）的3D点。后面这个限制的考虑在于，track长度够长的点，普遍认为它已经比较稳定，不需要再有过多的优化。另外，iterative是指说上述优化迭代进行多次，colmap中设置的是最多两次，迭代的退出条件是看数据的变化情况，即有多少点发生了改变。
全局的优化（IterativeGlobalRefinement）一般是隔一段时间进行一次，一般是以重建的图像数目，3D点的数目等为条件去设置间隔。Colmap中会保证重建的结束最后一次优化必须是全局的优化。全局的优化就会使用已有的所有图像和3D点。同时，在优化前会对所有的track进行一次清理，比如完善track的长度（CompleteTracks），合并一些很近的3D点（MergeTracks）等。优化后也会根据重投影误差删掉一些点(FilterPoints)，甚至删掉一些图像(FilterImage)。同上，这里也是iterative的，colmap中设置的最大迭代次数为5次。
