点击上方“3D视觉工坊”，选择“星标”
干货第一时间送达
本文由知乎作者fishmarch授权转载，不得擅自二次转载。原文链接：https://zhuanlan.zhihu.com/p/54197361
引言
SfM 主要分为了增量式、层次式、全局式。目前，增量式是最为流行的。
SfM综述
1.关联搜索
由于图像是无序的，所以需要将有重叠关系的图像关联起来，该部分输出为经过几何验证的关联图像集，及地图点对应的图像投影点。主要包含了一下几步：
特征提取
特征点以及其描述子。例如sift、surf、orb等特征。
匹配
输出可能具有重叠关系的图像对集合，及其相对应的特征
几何验证
验证图像对的重叠关系。
根据不同的空间构型计算不同的几何关系：单应矩阵H（纯旋转或平面特征）、本质矩阵E和基础矩阵F（未标定）。
足够的内点时通过几何验证。因为外点的干扰，使用RANSAC算法。
输出为经过验证的图像对，及其对应的内点，也可包含图像间几何关系。该阶段输出也被称为scene graph，图像为顶点，关联关系为边。
2.增量式重建
输入为scene graph，输出为注册的图像位姿和地图点
初始化
选择合适的初始图像对至关重要。在有较多重叠图像的位置初始化使重建结果更鲁邦准确。而在较少重叠图像初初始化，将使运行速度较快。
图像注册
求解PnP将新的图像添加进来。由于外点的影响，使用RANSAC等方法。
三角化
新注册的图像通过三角化可提供更多地图点
Bundle Adjustment
图像注册和三角化是两个分离过程，都会产生误差，通过BA来减少该误差。
挑战目前的SfM算法在建图完整性，鲁棒性等方面经常出现问题。
漏注册、错误注册、累计误差等。
原因：
1：关联搜索中由于近似匹配产生了不完整的scene graph，因此没有足够的连通性，且影响精度。
2：重构阶段的失败。由于场景结构的丢失或错误。图像注册与三角化又是一个相互捆绑的问题。
本文贡献1.Scene Graph 改进
本文采用多模型几何验证策略。
首先，计算基础矩阵F，如果内点较多（ ），通过验证。
对同一对图像，计算单应矩阵H下的内点数（ ）。如果
,认为相机发生了移动（以纯旋转假设估计效果不好），为一般场景。
对于标定过的计算本质矩阵E，及内点数（ ）。如果
，认为标定正确。
如果标定正确，且相机发生了位移，分解本质矩阵E，三角化相应内点，并且计算夹角 ，该夹角可以区分纯旋转和平面特征。
由于网上的照片经常含有水印，时间戳，边框等，处理办法为：计算相似变换下图像四周上的内点，如果内点较多泽舍弃。
对于可靠的图像对，在场景图中标记了类型（一般、纯旋转、平面特征）以及最好模型对应的内点。
在初始化时选择标定好的，非纯旋转的图像对。对于纯旋转，建图过程中并不进行三角化。
2.下一最好图像对（next best）的选择
下一图像对选择至关重要，影响位姿的估计与三角化的精度。
一般的方法是选取看到最多地图点的图像。
实验证明PnP的精度依赖于地图点的数量以及其分布情况。
候选图像：同时可以看到至少 个地图点的所有未被注册的图像。在候选图像中记录地图点数目及其分布。数目较多且分布均匀的将优先选择。
将每张图像划分网格，每个格子用空和满来表示。当某一格子中当点变为可见时，该格子标记为满，且该图像点评分按权重增大。
点越多越均匀，评分越高。在每层中，每个格子内的点只计算一次，权重即为当前层格子的尺寸，具体来说上述四个评分的计算：
3.鲁邦且高效的三角化
为了应对外点，使用了RANSAC。
计算夹角，需要足够大：
两图像中对应的深度值为正:
重投影误差足够小：
4.Bundle Adjustment
每帧之后做一个局部BA，增长一定规模后做全局BA。
参数化
使用Cauchy核函数应对外点，小规模中使用直接求解器，大规模求解使用PCG
滤除
BA后对于不满足模型的观测滤除掉（重投影误差较大）
对每个地图点要满足最小的三角化夹角
全局BA后还要检查退化的图像（相机参数不正确，仅看到外点等）
优化中并没有对相机参数做限制
再三角化
pre-BA RT
post-BA RT
迭代优化
BA、RT、filtering迭代执行，直到滤除对观测和RT点较少
5.分组优化
BA是SfM对一个主要瓶颈。
将图像分组，分成很多小的，较多重叠的组。每组内认为是同一个相机。
在优化过程中，优化较多的是那些新加入的，其它的则仅仅是减小漂移。因此将图像分组优化会更搞笑。
判断两图像的共视程度：
其中向量 每个位描述了该图像中是否看到了对应的地图点。
将图像按照看到的地图点数量排序 ，构建图像组时，从中选择第一个（地图点最多的），接下来找到
最大的。如果
则将该图像加入这一组。否则创建新组。
组内图像BA：
参考文献：
[1] Schönberger, J. L., & Frahm, J. M. (2016). Structure-from-Motion Revisited. In IEEE Conference on Computer Vision & Pattern Recognition.
上述内容，如有侵犯版权，请联系作者，会自行删文。
推荐阅读：
吐血整理|3D视觉系统化学习路线
那些精贵的3D视觉系统学习资源总结（附书籍、网址与视频教程）
超全的3D视觉数据集汇总
大盘点|6D姿态估计算法汇总(上)
大盘点|6D姿态估计算法汇总（下）
机器人抓取汇总|涉及目标检测、分割、姿态识别、抓取点检测、路径规划
汇总|3D点云目标检测算法
汇总|3D人脸重建算法
那些年，我们一起刷过的计算机视觉比赛
总结|深度学习实现缺陷检测
深度学习在3-D环境重建中的应用
汇总|医学图像分析领域论文
大盘点|OCR算法汇总
重磅！3DCVer-知识星球和学术交流群已成立
3D视觉从入门到精通知识星球：针对3D视觉领域的知识点汇总、入门进阶学习路线、最新paper分享、疑问解答四个方面进行深耕，更有各类大厂的算法工程人员进行技术指导，830+的星球成员为创造更好的AI世界共同进步，知识星球入口：
学习3D视觉核心技术，扫描查看介绍，3天内无条件退款
圈里有高质量教程资料、可答疑解惑、助你高效解决问题
欢迎加入我们公众号读者群一起和同行交流，目前有3D视觉、CV&深度学习、SLAM、三维重建、点云后处理、自动驾驶、CV入门、三维测量、VR/AR、3D人脸识别、医疗影像、缺陷检测、行人重识别、目标跟踪、视觉产品落地、视觉竞赛、车牌识别、硬件选型、学术交流、求职交流等微信群，请扫描下面微信号加群，备注：”研究方向+学校/公司+昵称“，例如：”3D视觉 + 上海交大 + 静静“。请按照格式备注，否则不予通过。添加成功后会根据研究方向邀请进去相关微信群。原创投稿也请联系。
▲长按加群或投稿
