专栏首页点云PCLStructure from Motion 综述

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

本文分享自微信公众号 - 点云PCL(dianyunPCL),作者:陈煜

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-03-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 基于激光雷达增强的三维重建

    尽管运动恢复结构(SfM)作为一种成熟的技术已经在许多应用中得到了广泛的应用,但现有的SfM算法在某些情况下仍然不够鲁棒。例如,比如图像通常在近距离拍摄以获得详...

    点云PCL博主
  • 点云存储文件格式简介

    在众多存储点云的文件格式中,有些格式是为点云数据“量身打造”的,也有一些文件格式(如计算机图形学和计算机和学领域的3D模型或通讯数据文件)具备表示...

    点云PCL博主
  • 深度相机Astra Pro测试教程

    最近在微信群内,很多群友在群友的推荐下,购买了Astra pro的深度相机,价格地道,物超所值!群友反馈积极,所以这里出一波简单的教程。以下内容抛砖引玉,主要讲...

    点云PCL博主
  • socket、tcp、udp、http 的认识及区别

    在网络层有IP协议、ICMP协议、ARP协议、RARP协议和BOOTP协议。 在传输层中有TCP协议与UDP协议。

    Java架构师历程
  • 热点 | 又一起“汉芯事件”?融资2.5亿的国产浏览器之光竟是谷歌Chrome换层皮

    今天,全网被一则新闻刷屏,即最近宣布完成2.5亿C轮系列融资的“红芯”公司,在网友将其软件exe文件解压再解压,再将IInstall文件解压一遍后竟然发现了,谷...

    镁客网
  • Chrome浏览器加固修复幽灵漏洞:内存占用将多出13%

    数据显示,Chrome(Chromium内核)浏览器的全球用户量已经超过了10亿,牢牢占据No.1。

    C4rpeDime
  • 第23天 常用模块四

    应用一:将字符串的alex make love的第一个字符串和第三个字符串进行替换====》love make alex

    py3study
  • OSI网络七层模型

    OSI七层模型:OSI(Open System Interconnection)开放系统互连参考模型是国际标准化组织(ISO)制定的一个用于计算机或通信系统间互...

    胡齐
  • Google、Facebook等均开始支持的HTTP3是什么? 为什么需要HTTP3?

    最近一段时间以来,关于HTTP/3的新闻有很多,越来越多的国际大公司已经开始使用HTTP/3了。

    睡魔的谎言
  • 强势增长的HubSpot是不是被高估了?

    HubSpot股价在今年大部分时间里一直处于波动中,尽管自今年以来股价上涨了近40%,但较历史高点下跌了近20%。尤其是自9月中旬以来,股价一直处于下行趋势,似...

    人称T客

扫码关注云+社区

领取腾讯云代金券