structure-from-motion revisited论文笔记

1. Introduction

提出一种新的SFM技术

SFM主要分为三类:增量式(most popular)\分层式\全局式;

但是目前在鲁棒性\精确度\完整性\扩展性方面还需要提高

2. Review of Structure-from-Motion

2.1 Correspondence Search---对应搜索

（1）特征提取：SIFT

（2）特征匹配：output：图片pair（a，b）、feature corrospondence（Mab = Fa × Fb）

（3）几何验证：由于特征匹配都是基于特征点的apparence的相似度，无法保证某个特征点可以准确的map到same scene point。所以利用投影几何来估计一个transformation，来map图像对儿之间的特征点。

· 具体方法如下：

a.平面场景：单应矩阵（H）

b.非平面场景：利用对极几何---本质矩阵（F：未标定）、基本矩阵（E：标定）

· 几何验证成功条件：如果transformation在图片对儿之间map的特征数量（内点，采用RANSAC方法）超过一定的阈值，就认为这两张图片通过了几何验证。

· 几何验证的output：通过几何验证的图像pair、内点对儿（Mab = Fa × Fb）、【可选】几何关系Gab

即 生成scene graph ，节点：图片；边：通过几何验证的图片对---verified pairs of images

tips：（单应矩阵、本质矩阵、基本矩阵讲解及约束关系推导：

http://www.cnblogs.com/youzx/p/6385513.html#wiz_toc_1）

2.2 增量式三维重建

input ：scene graph

output ：pose（Np个，注册成功的图片数）、points（Nx个，构成点云的三维点数）、

（1）初始化

在scene graph中选取两个dense location（with many overlapping cameras）---照片匹配数量多

（2）图片注册

通过PnP可以将新图片注册到当前的模型中（利用新加入图片与已注册图片之间的匹配点对儿&已生成的三维点---生成2D-3D对应，然后进行三角测量估计出出新加入图片的pose）

排除外点的影响：

a.标定的：用RANCAS & minimal pose slover

b.未标定的：minimal slovers 或者 sampling-based approaches

** 本文 ：提出一种next best image selection** 方法**，** 准确估计pose、 可靠的三角化

（3）三角化

新注册的图片需要满足的条件：1.看到已经生成的三维点； 2.通过与已注册的图片之间的新匹配生成新的三维点；

而三角化的作用，1.通过2D-3D对应实现新图片的注册；2.计算得到新的三维点

本文 ：提出一种robust&高效的三角化方法

（4）BA

原理 ：BA是一种联合非线性的，通过最小化重投影误差来对pose & 3D points进行refinement。

Levenberg-Marquard方法（结合高斯-牛顿算法&梯度下降法的优点）用来解决BA问题

BA问题中参数的特殊结构激发了Schur complement trick，该补全技巧首先解决了reduced camera system，然后通过back-substitution（回代）更新points，由于相机的数量通常小于points的数量，所以这种方式比较有效率

（精确步骤、非精确步骤、Schur complement trick、直接法、非直接法都是处理reduced camera system？？？他们之间的关系是什么？？？）

两种解决方式用来处理reduced camera system：

a. 精确步骤算法：

将system存储并分解成稠密或稀疏矩阵

b. 非精确步骤算法：

近似的求解system，通常是使用迭代的方法

直接：

直接法：只能处理几百个相机，对于大规模的情况代价太大

稀疏直接法：降低了稀疏问题的复杂度，但是这样会使得连接图的边更加密集，也不能用于大规模的无序数据集。（如i：iconic images方法）

非直接：

非直接方法：因此对于网络上的图片集来说，首选非直接法。

对于网上大量的near-duplicated images（重复图片太多对重建没有意义），会使BA耗费大量的时间。 本文提出 鉴别并参数化表示高度重叠的图片 ，从而提升大数量级的数据集的BA效率。

重建步骤总结:

(1)特征提取和匹配

(2)几何验证

(3)构造scene graph

(4)初始化:

选取initial image(根据scene graph)

2d-2d恢复相机位姿(计算 本质矩阵 ; 本质矩阵分解得到 相机位姿 ;)

三角测量(根据相机位姿和相机内参计算 投影矩阵, 生成 三维点)

BA

(5)下一张图片

选取下一张图片(根据scene graph)

3d-2d恢复相机位姿(根据与之前注册过的照片的匹配点,对应已经生成的三维点计算出相机位姿)

三角测量生成新的三维点(根据新匹配上的点,三角测量生成新的三维点)

(6)BA调整(通过最小化重投影误差,优化 相机位姿 &三维点)

3. challenges

尽管现存方法能够处理大规模的网络图片，但是在completeness 和robustness 上并不能完全使人满意 。

system会使得很多本该被注册的图片注册失败 或者由于mis-register和drift导致得到的是broken model 。 原因有：

a.correspondence search之后产生的scene graph不完整 （如没有得到completing model所必需的connectivity或者没有 充足的redundancy来实现可靠估计）；

b.在重建阶段由于缺少或者不准确的scene structure 导致的图片注册失败 （图片register和三角化二者是共生的关系，即 图片只能注册到当前已经存在的scene structure中，当前的scene structure也只能从注册的图片中进行三角测量）

增量式重建过程中每一步都将accuracy和completeness最大化 ，是SfM的一个挑战。** 本文** 完成了这个挑战，在提高效率 的同时，在完整性、健壮性和准确性方面显著改进了当前技术水平。

4. Contributions

（1）引入了一种几何验证 策略，用information增强scene graph ，提高了初始化和三角化的鲁棒性

（2）选择下一个最佳图片 （视角）---最大化增量式重建过程中的Robustness & accuracy

（3）更robust的三角化 方法---在降低计算消耗的同时比现存方法得到更加complete的scene structure

（4）迭代BA、re-triangulation、outlier flitering策略---通过减轻drift，显著提高了completeness & accuracy

（5）通过redundant view mining，对于dense图片集实现了一种更有效的BA参数化

这些使得整个系统在保证efficiency的同时，在robustness & completeness方面显著超越现存方法、

4.1. Scene Graph Augmentation

multi-model几何验证策略增强scene graph：

（1）估计基础矩阵：如果至少找到NF个内点，就认为该图像对满足几何验证

（2）通过测定该对图像的单应内点NH的数量，来对transformation进行分类 （即判断该图像对之间点的几何约束是满足本质矩阵还是单应矩阵---对应的是非平面/平面 ），以选择使用H矩阵还是F矩阵来估计相机pose。

具体方法：（使用类似于GRIC的方法来选择transformation---GRIC测度拟合单应矩阵模型和基本矩阵模型的误差方程，从而检测transformation是否合理）。

1.如果inliers的数量NH / NF < ...HF，就认为这是general scene；

2.对于已标定的相机，估计它的本质矩阵E和它的内点NE，如果满足NE / NF > ...EF，就认为标定是正确的；

3.如果满足条件1 & 2，就将E矩阵分解得到相机pose & 对内点对进行三角测量得到三维点 & 测量三角测量角度αm的中值（能够分辨出是纯相机旋转（label：panoramic）还是平面图像（label：planar）））

（3）对于WTFs问题 （watermarks, timestamps, and frames，会导致不同landmark之间产生错误连接），通过图像边界上的Ns个inliers，估计一个相似性变换，来检测这些WTFs图像对（如果Ns / NF > ...SF 或者 Ns / NE > ...SE，就说明这是一个WTFs图像，并且不把它加入到scene graph中）。

（4）scene graph中图像对的model标签： 分为general，panoramic，planar三种**（。。。后面没懂，passpasspass）。** label的目的：只用general标签的图像对儿进行重建。

意义：1.利用增强的scene graph能够高效的找到最佳initialization ，使重建过程更加robust。2.增加label，不用panoramic图片对儿进行三角测量可以防止degenerate points，可以增强三角测量的robustness & 有助于image registration。

4.2. Next Best View Selection

目的是为了最小化重建的误差。

本文提出一种高效的uncertainty-driven的选择下一张图片的策略，提高了重建的robustness

selection的重要性：一次错误的selection会导致一连串的camera mis-registrations & faulty triangulations，而且selection还影响了pose估计 & 三角测量的completeness和accuracy，不准确的pose也会导致三角测量failed。

对于网上的图片，通常都不知道场景的重叠情况、相机参数信息，一次决定selection要完全取决于appearance、two-view correspondance和已经重建出的scene（points）。

选择能看到最多三维点的图片作为下一张待注册图片是一种流行的方式， 采用PnP的方式（对于网上的图片还要进行相机内参估计），充足的2D-3D对应 （能看到尽可能多的三维点） & 点的uniform distribution 可以增加PnP的accuracy。

selection方法：

找到候选图片中至少看到Nt个三维点的图片（用一个feature tracks graph 可以有效的统计这个信息），但是网上的数据集中看到同一个场景的图片非常多，从而导致feature tracks graph会非常密集，本文提出用一个multi-resolution analysis的方法 高效的解决这个问题。具体方法如下：

1.对于每一张候选图片keep track可见三维点的数量和这些点在候选图像上的分布，points越多且在image上的分布越均匀,score S就越大,score的计算方法:

a.在x,y轴上分别划分出Kl个固定大小的网格,每个网格的可以有两个状态---empty || full.

b.在重建过程中,当一个网格中的点visible了,这个网格就从empty转变成full,并且Si的值根据权重wl增加.(通过上述方法来 quantifyvisible点的数量.meige格子只contribute S一次,所以避免了visible点集中在一起的情况.)
但是,当Nt << Kl的平方,每个格子就只包含一个点了,这种情况下就无法capture点的分布信息.为了解决这个问题,提出一种多分辨率金字塔方法（l = 1, 2, ..., L） ，其中Kl = ，计算score的时候根据每一种分辨率的 = 把每一种分辨率的结果累加得到score

4.3. Robust and Efficient Triangulation

transitive corrcorrespondence可以增加三角测量的completeness，也对后序图片的注册有帮助，基于appearance的近似匹配产生的图片对通常是baseline较小的（相机移动不大的），因此利用transitive可以使三角测量更加准确。

现存的一些multi-三角测量方法对于一定程度的外点robustness，但是还没有方法能对含有高ratio外点的feature tracks进行处理，本文提出一种高效的、sampling-base的方法，从含有外点的feature tracks中robust的估计所有points。

Bundler，在track中取样所有的点对儿，进行two-view三角测量，一旦找到一对儿点满足三角测量angle，就在这个track上进行multi-view triangulation，一旦track中的所有点都满足cheirality constrain，就接受这个track，这种方法有两个limitation：1. 对于外点不robust，因为它没法recover融合到track中的single point（因为是进行two-view）；2。对于所有pairwise点进行two-view 三角测量计算代价大。

本文 解决了Bundler的两个limitation：利用RANSAC方法和recursive三角测量

目标是用一个well-conditioned 三角测量最大化测量点的support

一个well-conditioned model 需要满足两个条件：

a.充分大的triangulation angle

b.将三维点从世界坐标系下投影到image pair所在的相机坐标系下，深度（z坐标）是正值。

如果1.深度是正值；2.重投影误差小于阈值；就认为track与model是一致的。

RANSAC采用循环的方法，随机的均匀取样至少两个view？（RANSAC maximizes K as an iterative approach and generally it uniformly samples the minimal set of size two at random.） 对于size较小的track，可能会有重复取样的问题，所以循环的过程中将通过一致性检验的点从剩余的点集中移除，直到track的size < 3的时候循环停止。

到底如何进行multi-view的三角测量？？？

4.4. Bundle Adjustment

在image registration和三角测量之后进行BA，增量式三维重建中，增加的点只会对局部产生影响，因此只对most-connected image 注册之后进行局部BA即可。同VisualSfM类似，只在模型增长达到某个比率时才进行全局BA。

Parameterization.

用Cauchy function作为局部BA的损失函数

对于几百张图片用sparse direct solver，对于大规模的问用PCG。

作者用Ceres Slover（We use Ceres Solver [2] and provide the option to share camera models of arbitrary complexity among any combination of images.）对于网上的无序图片，用一个简单的带有radial distortion的参数，as估计是基于self-calibration的

Filtering.

经过BA之后，一些observations不符合模型就要滤除。

首先滤除掉重投影误差大的点，然后滤除triangulation angle小于minimum的点；在局部BA之后检验degenerate cameras（e.g. those caused by panoramas or artificially enhanced images），所以将焦距和畸变参数freely optimize in BA。对于

Re-Triangulation.

extend the very effective pre-BA RT with an additional post-BA RT step，即通过continuing之前三角测量失败的点，来实现模型的completeness，另外也尝试merge tracks。

Iterative Refinement.

外点对于BA的影响是非常大的，由于drift 或者pre-BA RT，很多点会被当成外点从而被滤除。因此，提出循环运行BA、RT、fliting，直到the number of filtered observations and post-BA RT points diminishes.

4.5. Redundant View Mining

本文借鉴之前的方法，将问题分成几个submap（whose internal parameters are factored out）

作者的三个贡献点是：

a. 利用SfM固有属性提出一个高效的camera grouping scheme

b.不像之前方法将many cameras聚类到一个submap，作者将scene分割成许多小的，highly overlapping的camera groups，然后每个group由一个camera替代，这样较少了solving the reduced camera system的cost

c.由于much smaller、高度重叠的相机分组，省去了之前方法中分隔符变量的优化

SfM将images和points按照是否被latest重建影响分为两个set。由于网上图片的大量overlapping，将不被latest重建影响的scene part分成group（每个group中包含具有高度重叠的camera，并用一个camera代替group）。

将受到重建影响的images（新加入的用来重建的图片或者是在重建期间image中重投影误差超过阈值的点数大于r pixels）分到另外的分组进行优化。

衡量images重叠度的方法：

将每张image用一个Nx维的vector表示，其中Nx代表场景中包含Nx个points，每一维用0/1代表scene中的点在当前image中的可见性。

两张图片的重叠度根据bitewise operation进行计算。

grouping方式：

将images按照其vector进行排序，初始化一个Gr的方式是：

移出第一张图片Ia，并在sorted集合中找到使得Vab最大的图片Ib，如果Vab > V & IG

rI < S, image Ib就从sorted中移除并且将图片加到Gr中，否则就生成新的group。（为减少search Ib的cost，limiting the search to the Kr spatial nearest neighbors（按照视角））