Structure from Motion 综述

Structure from Motion（SfM）是一个估计相机参数及三维点位置的问题。SfM方法可以分为增量式（incremental/sequential）,全局式（global），混合式（hybrid）,层次式（hierarchical），基于语义的SfM(Semantic SfM)。

1. 增量式（incremental）

Incremental方式的SfM方法[1,2,3,4,5,6,7]是目前最广为使用的方法,大多数方法都以[1]中的pipeline为基础并进行了改进。

1.1 basic pipeline

以[1]中的SfM方法为主，一个基本的SfM pipeline可以描述为：对每张图片检测特征点（feature point），对每对图片中的特征点进行匹配，只保留满足几何约束的匹配，最后执行一个迭代式的、鲁棒的SfM方法来恢复摄像机的内参（intrinsic parameter）和外参(extrinsic parameter)。

如图1.1所示，该方法可以作更为具体的描述。首先使用SIFT特征检测器[8]提取特征点并计算特征点对应的描述子(descriptor)，然后使用ANN（approximate nearest neighbor）方法进行匹配，低于某个匹配数阈值（[1]中的阈值为20）的匹配对将会被移除。对于保留下来的匹配对，使用RANSAC(RANdom Sample Consensus)[9]和八点法[10]来估计基本矩阵(fundamental matrix)，在估计基本矩阵时被判定为外点（outlier）的匹配被看作是错误的匹配而被移除。对于满足以上几何约束的匹配对，将被合并为tracks。然后通过incremental方式的SfM方法来恢复场景结构。首先需要选择一对好的初始匹配对，一对好的初始匹配对应该满足[11]：（1）足够多的匹配点；（2）宽基线。之后增量式地增加摄像机，估计摄像机的内外参并由三角化得到三维点坐标，然后使用Bundle Adjustment[12]进行优化。

算法1和算法2对该方法做了精简的描述[6]。

Algorithm 1 Computation of geometry-consistent pairwise correspondences

Require: image set

Ensure: pairwise point correspondences that are geometrically consistent

Compute putative matches:

Detect features in each image and build their descriptor

Match descriptors (brute force or approximate nearest neighbor)

Filter geometric-consistent matches:

Estimate fundamental matrix F

Estimate homography matrix H

Algorithm 2 Incremental Structure from Motion

Require: internal camera calibration (matrix K, possibly from EXIF data)

Require: pairwise geometry consistent point correspondences

Ensure: 3D point cloud

Ensure: camera poses

Compute correspondence tracks t

Compute connectivity graph G (1 node per view, 1 edge when enough matches)

Pick an edge e in G with sufficient baseline (compare F and H)

Robustly estimate essential matrix from images of e

Triangulate te, which provides an initial reconstruction

Contract edge e

While G contains an edge do

Pick edge e in G that maximizes track (e){3D points}

Robustly estimate pose(external orientation/resection)

Triangulate new tracks

Contract edge e

Perform bundle adjustment

End while

1.2 后续的改进

[1]中的方法已经能够较为完整地重建出三维场景，但仍存在不足：当添加的摄像机越来越多时，该SfM方法会明显变慢。除此之外，重复出现的场景结构会产生很多错误的匹配，这会对场景重建的精度造成明显影响。由此，后续方法在降低重建的时间和提高重建精度上均做出过很多改进。

Photo Tourism[1]中SfM算法的时间复杂度为O(n4)，其中n为摄像机数量。VisualSFM[5]中将SfM算法的时间改进到O(n2)的同时又保留了较高的精度。[5]中提出一种抢占式特征匹配（preemptive feature matching）策略来提高匹配速度。该论文发现，在top-scale中，大小为h的匹配子集中一个匹配被保留的概率为h/k，其中k是两幅匹配的图像中最大的特征点数。

抢占式特征匹配策略如下：

1. 对每幅图片中的特征点按下降尺度（decreasing scale）进行排序
2. 使用全匹配或者选择一个子集生成匹配对列表
3. 对于每对图片：
4. 对两幅图片中的前h个特征点进行匹配
5. 如果子集中匹配点的数目小于某个阈值，则跳过（c）
6. 进行常规的特征匹配和几何估计

由于大规模场景中的很多图片具有很多冗余的视图和特征点，抢占式特征匹配策略可以将最有可能进行匹配的图片进行匹配。对于Bundle Adjustment，VisualSFM使用GPU版本的multicore bundle adjustment[13]来最小化重投影误差，使得bundle adjustment的时间复杂度减少到O(n)。由于摄像机和3D点在重建过程中会很快趋于稳定，因此在每次迭代过程中对所有摄像机和3D点进行优化是不必要的。为了减少累积误差，每当摄像机数目增加了某个常数时（该论文中为20），便使用partial BAs对摄像机和3D点进行局部优化；当模型的大小增加当某个比例时，便使用full BAs进行全局优化。由于摄像机位姿（pose）的累积误差，incremental SfM经常会出现drift。Drift的一个主要原因是：初始的位姿估计和BA优化后的位姿都不够准确，这就导致了一些正确的特征匹配在三角化时失败，这些正确的匹配丢失造成了误差的累积。VisualSFM中首次提到了使用re-triangulate(RT)来三角化失败的特征匹配——当模型大小增加25%时，便re-triangulate这些失败的特征匹配。

OpenMVG中的sequential SfM方法为adaptive structure from motion(ASfM) [6]。以往的SfM pipeline在模型估计（model estimation）中都使用固定的阈值，而ASfM则提出使用a contrario（AC） methodology使阈值来适应（adapt）输入数据及不同的模型估计问题。自动计算阈值有两个好处：参数不用人为设置；可以达到全局固定阈值达不到的优化程度。阈值选择是一个两难的问题，比如使用RANSAC过滤outlier时，阈值太小，则会导致内点数太少而不够用来拟合模型；阈值太大又会造成outliers较多而影响结果的精确度。对于基本矩阵(fundamental matrix)和单应矩阵(homography matrix)，ASfM使用AC-RANSAC[14]取代RANSAC；对于摄像机姿态估计，也使用AC-RANSAC[14]取代RANSAC。ASfM在精度方面有所提高，然而，自适应阈值的计算会额外增加O(n log n)时间复杂度。

尽管之前的incremental SfM方法做出了很多努力，在完整性(completeness)和鲁棒性(robustness)上仍然难以取得令人满意的效果——有的只重建出场景的部分，或是出现drift。Colmap[7]则在最大化重建精度和完整性上更进一步。Colmap主要在五个方面进行了改进：

1. 引入了geometric verification增强scene graph。首先估计基本矩阵，如果有至少NF 个内点被保留，则用于估计基本矩阵的这对图片则视为geometrically verified。接着对同一对图片估计单应矩阵，假设保留的内点数为NH，如果，则假定一个移动的摄像机位于一个通常的场景中。然后估计本质矩阵，假设保留的内点数为NE，如果，则假设图片已被正确标定。对于正确的标定以及满足的匹配，对本质矩阵进行分解并进行三角化，得到三角化后角度的中位数，使用来区分纯旋转和平面场景。
2. Next Best View Selection方面的改进。对于Next Best View的选择，一个常见的策略是选择看见重建出的最多的3D点的那张照片。使用feature tracks的一个graph可以非常有效地对这种方法进行实现，但是，对于网络上的图片，这样的一个graph会变得非常稠密，因为很多图片看见的是一个相同的场景结构。Colmap的策略则是同时对每张候选图片中的visible points的数量和点的分布情况进行跟踪，更多的visible points和visible points的更均匀的分布会得到一个更高的分数，得分最高的图片将作为next best view。
3. Sampling-based triangulation。由于错误的二视图验证和特征匹配，feature tracks中的outlier ratio仍然比较高，而之前的一些triangulation方法对于这样一种情况仍然不够鲁棒。Colmap中提出了一种高效的，sampling-based triangulation方法。Bundler[3]中对track中的所有匹配对进行triangulation，然后检查是否至少有一个匹配对具有足够大的triangulation angle。只要找到了这样一对匹配，则对该track中的所有匹配进行triangulation。但是这种方法不够鲁棒，而且计算时间也很长。Colmap则在triangulation的基础上加上了RANSAC来解决解决任意的outlier ratio的问题。此外，使用RANSAC拟合的模型需要满足两个约束：triangulation angle 需满足；以及对应点的深度为正数并且重投影误差小于某个阈值。
4. Bundle Adjustment。Colmap在BA方面部分采用了和VisualSFM[5]相同的策略——仅当模型增加到一定比例的时候才执行global BA；在global BA之前进行re-triangulation(pre-BA RT)。但是，由于BA对摄像机和点的参数进行了优化，因此Colmap中提出post-BA RT，即在global BA之后再次进行triangulation。除此之外，和Bundler[3]以及VisualSFM[5]在每一次优化时仅仅执行一次BA和filter outlier不同的是，Colmap会进行一个iterative refinement，即迭代使用，RT和filtering，直到没有可以被filter的观测值和post-BA RT的点存在。

图1.1 basic SfM pipeline

2. 全局式（global）

由于并没有对全局式SfM有过深入研究，因此仅仅大致提及。

1.1中提及的增量式重建方法，一个显著的缺陷就是随着误差的累积，存在闭环的场景在最后的重建结果中会漂移(其实简单来说可以看成是重建恢复的相机位置无法形成一个闭环)。全局式重建由于考虑了相邻相机之间的空间关系，因此不会出现漂移的情况。但是，由于全局式重建需要依赖正确的匹配结果，因此，全局式重建的精度较低，重建场景的完整性也不如增量式重建。目前也有很多算法对全局式重建算法进行了很多改进，从计算机视觉的三大会议论文数来看，目前全局式重建研究正在成为一种趋势。

3. 混合式（hybrid）

尽管incremental SfM在鲁棒性和重建精度上有着优势，但是效率却不够高，而且对于大规模的场景重建，随着误差的累积，场景结构很有可能会出现drift；而global SfM虽然效率比incremental方式快，但是却对外点较为敏感。

混合式SfM[15, 16]在一定程度上综合了incremental SfM和global SfM各自的优点。

HSfM[15]的整个pipeline可以概括为全局估计摄像机旋转矩阵，增量式计算摄像机中心，具体如图3.1所示。

图3.1 HSfM的pipeline

算法的输入为Epipolar Geometry Graph(EG)，EG被定义为：顶点为图片，相连的边为匹配的图片对，对应的图片之间的几何关系通过分解本质矩阵来进行估计。边(i, j)的相关旋转和相关的平移方向需满足以下约束：

其中和分别表示图片i的摄像机中心和旋转。全局摄像机旋转和相关旋转可以转换到李代数空间，然后使用L1优化求解。但是，全局的rotation averaging对EG的结构和对极几何匹配对的精确度很敏感，因此，HSfM方法使用community-based rotation averaging的方法来解决这两个问题。增量式计算摄像机中心时，每增加一个摄像机并进行三角化之后，就做一次BA。由于HSfM中的BA只对场景结构和摄像机中心进行优化，因此HSfM比传统的incremental方式速度更快。

与HSfM[15]相比，PSfM[16]则在大规模场景和高精度重建方面取得了更为令人诧异的效果。[16]能够在10台均为6核128GB内存的计算机上进行城市级规模（百万量级的高精度图片）的重建。由于城市级规模重建所需内存远超过一台计算机的内存，基于“分而治之”的思想，[16]把摄像机分成许多个cluster，每个cluster需要满足size constraint和completeness constraint。Size constraint是由于每个camera cluster应该足够小从而能够在单台计算机上进行local incremental SfM，论文中通过实验给出的结果是每个cluster中摄像机的数量不超过100；completeness constraint的引入是为了保留摄像机之间的connectivity，这些connectivity能够提供relative pose来进行global motion averaging，[16]中使用第i个camera cluster与第j个camera cluster中相交的摄像机在第i个camera cluster中所占的比率作为completeness constraint的评价标准，[16]中使用的比率为0.7 。camera clustering算法分为graph division和graph expansion两部分，graph division可以保证size constraint，graph expansion则保证了completeness constraint。具体算法如算法3所示。

Algorithm 3 Graph-based camera clustering algorithm

了解决在track generation过程中，一台计算机的无法同时将所有特征点和匹配加载到内存中的问题，[16]使用hierarchical camera cluster tree。其中，hierarchical camera cluster tree定义为这样的一个树结构：叶子结点对应独立不相交的camera cluster，非叶节点对应相交的camera cluster。令表示为树的第k层的第i个节点，和分别表示为的左右孩子节点，若和为叶子结点，则将它们的特征点及匹配载入内存，生成的tracks，再重新分配特征点和匹配的内存，并将tracks存入磁盘；若和为非叶子结点，则只将匹配和tracks载入内存，并将对应的tracks存入磁盘。当每个cluster中的local incremental SfM执行完毕之后，便用local incremental SfM中得到的relative motion参数用来进行global averaging，三角化之后再使用分布式BA进行全局优化。

4. 层次式（hierarchical）

1中的incremental SfM存在三个主要问题：易受initialization的影响，容易出现drift问题，时间效率不高。Hierarchical SfM[17,18,19]的方法较好地解决了前两个问题，并且将时间复杂度从incremental SfM的提高到。

标准的hierarchical SfM pipeline[17]使用一种agglomerative clustering策略，生成一棵binary cluster tree(dendrogram)。Agglomerative clustering算法自底向上开始处理：算法的每次迭代合并具有最小距离的两个clusters，每个cluster可以是一张图片，也可以是一个合并之后的cluster。组成cluster的两个视图需要满足两个要求：足够多的匹配点和足够宽的基线。由于合并的两个clusters的坐标系不同，因此合并的时候需要做相似变换。在incremental SfM中，增加view i需要做i次BA，因此总的时间复杂度为；而在[17]中，使用BA进行优化时仅选择每个cluster中k个视图，因此对于m个点和n个视图的BA算法，时间复杂度为。但是，在最坏的情况下，如果一个cluster每一次并不是和另一个cluster合并，而是和单个视图合并，那么就将得到一个不平衡的二叉树，在这种情况下的时间复杂度就将和incremental SfM一样。

在[17]的基础上，[18]提出了一种聚簇策略来使得dendrogram更加平衡。修改后的聚簇策略为：对于算法的每一次迭代，在l个最近匹配对的clusters中选择具有最小cardinality的一对cluster，一对cluster的cardinality为两个clusters的cardinality之和。

References

[1] Seitz S M, Szeliski R, Snavely N. Photo Tourism: Exploring Photo Collections in 3D[J]. Acm Transactions on Graphics, 2006, 25(3):835-846.

[2] Agarwal S, Snavely N, Simon I, et al. Building Rome in a day[J]. Communications of the Acm, 2011, 54(10):105-112.

[3] Snavely K N. Scene reconstruction and visualization from internet photo collections[M]. University of Washington, 2008.

[4] Frahm J M, Fite-Georgel P, Gallup D, et al. Building Rome on a cloudless day[C]// European Conference on Computer Vision. Springer-Verlag, 2010:368-381.

[5] Wu C. Towards Linear-Time Incremental Structure from Motion[C]// International Conference on 3dtv-Conference. IEEE, 2013:127-134.

[6] Moulon P, Monasse P, Marlet R. Adaptive structure from motion with a contrario, model estimation[C]// Asian Conference on Computer Vision. Springer Berlin Heidelberg, 2012:257-270.

[7] Schönberger J L, Frahm J M. Structure-from-Motion Revisited[C]// Computer Vision and Pattern Recognition. IEEE, 2016.

[8] Lowe D G, Lowe D G. Distinctive Image Features from Scale-Invariant Keypoints[J]. International Journal of Computer Vision, 2004, 60(2):91-110.

[9] Fischler M A, Bolles R C. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[J]. Readings in Computer Vision, 1987:726-740.

[10] Hartley R, Zisserman A. Multiple view geometry in computer vision[J]. Kybernetes, 2003, 30(9/10):1865 - 1872.

[11] Beder C, Steffen R. Determining an Initial Image Pair for Fixing the Scale of a 3D Reconstruction from an Image Sequence[J]. 2006, 4174:657-666.

[12] Triggs B, Mclauchlan P F, Hartley R I, et al. Bundle Adjustment — A Modern Synthesis[C]// International Workshop on Vision Algorithms: Theory and Practice. Springer-Verlag, 1999:298-372.

[13] Wu C, Agarwal S, Curless B, et al. Multicore bundle adjustment[C]// Computer Vision and Pattern Recognition. IEEE, 2011:3057-3064.

[14] Moisan L, Moulon P, Monasse P. Automatic Homographic Registration of a Pair of Images, with A Contrario Elimination of Outliers[J]. Image Processing on Line, 2012, 2:329-352.

[15] H Cui , X Gao,S Shen, Z Hu. HSfM: Hybrid Structure-from-Motion[C]// Computer Vision and Pattern Recognition. IEEE, 2017.

[16] Zhu S, Shen T, Zhou L, et al. Parallel Structure from Motion from Local Increment to Global Averaging[J]. 2017.

[17] Farenzena M, Fusiello A, Gherardi R. Structure-and-motion pipeline on a hierarchical cluster tree[C]// IEEE, International Conference on Computer Vision Workshops. IEEE, 2009:1489-1496.

[18] Gherardi R, Farenzena M, Fusiello A. Improving the efficiency of hierarchical structure-and-motion[C]// Computer Vision and Pattern Recognition. IEEE, 2010:1594-1600.

[19] Chen Y, Chan A B, Lin Z, et al. Efficient tree-structured SfM by RANSAC generalized Procrustes analysis[J]. Computer Vision & Image Understanding, 2017, 157(C):179-189.

原文链接：https://zhuanlan.zhihu.com/p/34256509