三维重建 3D reconstruction 有哪些实用算法？

加入极市专业CV交流群，与10000+来自腾讯，华为，百度，北大，清华，中科院等名企名校视觉开发者互动交流！

同时提供每月大咖直播分享、真实项目需求对接、干货资讯汇总，行业技术交流。关注 极市平台 公众号 ，回复 加群，立刻申请入群~

三维重建 3D reconstruction 有哪些实用算法？

https://www.zhihu.com/question/29885222

知乎高质量回答

一、作者：曹力科

https://www.zhihu.com/question/29885222/answer/918009389

本文来自知乎问答，仅供学习参考，著作权归作者所有。

在这个问题下，竟然没有人说大名鼎鼎的KinectFusion以及他后面的一系列工作？KinectFusion单篇论文引用都已经超过3000次了，不应该啊！

如果只想看现阶段效果最好的三维重建算法，请拉到文章最后（如有更好的算法，还请告知）。

一、KinectFusion

帝国理工的Newcombe等人在2011年提出的KinectFusion，可在不需要RGB图而只用深度图的情况下就能实时地建立三维模型。KinectFusion算法首次实现了基于廉价消费类相机的实时刚体重建，在当时是非常有影响力的工作，它极大的推动了实时稠密三维重建的商业化进程。

KinectFusion重建效果

在他们的论文中没有开源代码，最初的代码是由PCL团队实现的：https://link.zhihu.com/?target=http%3A//pointclouds.org/news/kinectfusion-open-source.html

KinectFusion的重建效果可以看这个视频：

KinectFusion之后，陆续出现了Kintinuous，ElasticFusion，ElasticReconstruction，DynamicFusion，InfiniTAM，BundleFusion等非常优秀的工作。其中2017年斯坦福大学提出的BundleFusion算法，据说是目前基于RGB-D相机进行稠密三维重建效果最好的方法。

二、Kintinuous和ElasticFusion

这两个工作都是同一个人做出来的，这个人就是Thomas Whelan。这两个工作应该算KinectFusion之后影响力比较大的。

Kintinuous GitHub代码：https://github.com/mp3guy/Kintinuous

ElasticFusion GitHub代码：https://github.com/mp3guy/ElasticFusion

Kintinuous2.0重建效果：

Kintinuous2.0重建效果

ElasticFusion 重建效果：

ElasticFusion 重建效果

三、ElasticReconstruction

项目官网：http://qianyi.info/scene.html

GitHub代码：https://github.com/qianyizh/ElasticReconstruction

重建效果：

ElasticReconstruction重建效果

四、InfiniTAM

InfiniTAM提供Linux，iOS，Android平台版本，CPU可以实时重建。

官网：http://www.robots.ox.ac.uk/~victor/infinitam/

GitHub代码：https://github.com/victorprad/InfiniTAM

重建效果：

五、DynamicFusion

官网：https://grail.cs.washington.edu/projects/dynamicfusion/

代码：https://github.com/mihaibujanca/dynamicfusion

重建效果：

DynamicFusion重建效果

六、BundleFusion

官网：http://graphics.stanford.edu/projects/bundlefusion/

论文：https://arxiv.org/pdf/1604.01093.pdf

代码：https://github.com/niessner/BundleFusion

重建效果：

二、作者： 徐普

https://www.zhihu.com/question/29885222/answer/48940748

本文来自知乎问答，仅供学习参考，著作权归作者所有。

我讲一下用一组图片来做3D reconstruction需要的算法吧(SFM), 使用这种方法的软件比较代表性的有 Pix4Dmapper, Autodesk 123D Catch, PhotoModeler, VisualSFM

我用JavaScript撸了个WebSFM, 完全用Javascript实现的3D reconstruction系统，可以在浏览器里跑.

http://websfm.org , 用Chrome,Firefox,IE10+打开即可.

pipeline大致是:

先用SIFT对每张照片提取特征，再对每一对图片做鲁棒的特征匹配，将所有2图匹配合并，找出track，通过tracks估算相机参数场景的稀疏结构, 再用相机参数做dense reconstruction, 输出dense point cloud (with surface nornal)

如果需要,可以用poisson surface reconstruction将dense point cloud转化为polygon

1 SIFT (Scale Invariant Feature Transform)

同样的特征点在不同的scale，方向，光照下都能被检测到，并且理论上会有相同的描述向量. (即invariant)

SIFT有很多变种，但实际上很类似，一般是添加几种可以保持invariant的变换， 比如仿射变换.

一个SIFT特征有四个部分(位置position, 大小scale, 方向direction, 描述向量descriptor).

比较两点可以直接比较其特征向量，不用考虑别的参数.

特征点的position和scale是在DoG Pyramid中找到的extrema.

方向是在特征scale下周边梯度histagram的主导方向.

描述向量是特征scale下以特征方向为准的坐标系下的梯度histagram

lowe's sift: http://www.cs.ubc.ca/~lowe/keypoints/

SiftGPU:http://cs.unc.edu/~ccwu/siftgpu/

我的JS实现: hhttps://github.com/ptx-pluto/web-sfm/tree/master/src/websift

2 ANN Feature Matching (近似最邻近特征匹配)：

找出两张图片之间特征向量的Nearest Neighbor，从而找出点与点之间的匹配关系。

这里输出的匹配是嘈杂的，存在错误, 且非常耗时

先对两组特征（vs1[], vs2[]）分别建立kd-tree

特征有128维，传统的kd-tree效果很差，需要对其进行平衡。在构建kd-tree选择hyperplane的时候，取方差最大的维度，在中位数处split.

为了加快速度，并不寻找严格NN, 而是在kd-tree上寻找ANN(Approximate NN).

匹配是否被采纳并不是使用传统的阀值，而是用一个优先序列来找ANN，最后通过第一与第二的距离比来确定是否采纳。同时v1,v2必须同时互为ANN，匹配(v1,v2)才被采纳.

ann: https://www.cs.umd.edu/~mount/ANN/
我的JS实现: https://github.com/ptx-pluto/web-sfm/tree/master/src/webmatcher

3 RANSAC:

用RANSAC和八点算法可以将嘈杂的匹配的结果稳定化.

适用情形: dataset存在少量错误，但服从一个constrain，并且constrain可以用dataset的一个很小的子集倒推回去。(在几何中这样的例子很多，比如给你某个平面上1000个点的坐标，但其中有错误数据，其constrain就是这个平面，而平面用3个点就可以确定)

原理: 随机抓一个subset并估算constrain，若subset中有错误数据，该constrain会很不准确，reject大部分数据；相反若subset中恰好都是正确数据，则会得到正确的constrain，accept大部分数据。因此不停的执行这个过程，直到找到正确的constrain，然后判定被其reject的数据为错误数据。（或因尝试次数过多退出）

在这里，dataset就是特征匹配输出的对应关系，而constrain就是核线几何(f-matrix), 用8个对应关系即可用八点算法估算出f-matrix. RANSAC可以筛除不符合核线几何的错误匹配.

RANSAC非常简单，代码只有十几行，而且效果非常明显，肉眼可辨

我的JS实现: https://github.com/ptx-pluto/web-sfm/blob/master/src/math/ransac.js

4 Eight Point Algorithm (八点算法)

用八个点点对应关系计算核线几何(f-matrix)

两个Projective Camera之间的点点对应关系是需要满足核线几何的，就像三点可以确定一个平面一样，8对匹配可以确定两个相机的核线几何.

核线几何简单的讲就是 x1*F*x2=0 , F是fundamental matrix (3x3, rank 2), x1,x2是相对应的两点的homogenous坐标。

将x1,x2代入后可以得到关于(f1,....f9)的一个线性方程，8对就是8个方程，再用SVD即可得最小二乘解.

5 Bundler Camera Registrtion

用tracks来估算相机参数.

bundler是incremental的，并且依赖于sparse bundle adjustment。初始化第一对相机后，便不断的用已知点估算新相机，并triangulate新的点，直到没有candidate为止，中间不断的做SBA来拟合新的参数, 并且每一轮做一次全局SBA。

bundler: http://www.cs.cornell.edu/~snavely/bundler/
我的JS实现:https://github.com/ptx-pluto/web-sfm/blob/master/src/webregister/register.js

6 SBA (Sparse Bundle Adjustemt)

SBA就是一个为view geometry优化之后的levenberg-marquardt非线性拟合算法. 在最小化projection error的时候，jacobian和hessian矩阵是稀疏的，而且存在特殊规律。利用了稀疏结构之后，就算有几千个变量需要拟合，速度也非常快。下图为sparse jacobian和sparse hessian.

sba: http://users.ics.forth.gr/~lourakis/sba/
我的JS实现:https://github.com/ptx-pluto/web-sfm/blob/master/src/webregister/sparse-bundle-adjustment.js

7 CMVS/PMVS (Dense Reconstruction)

使用surfel model的dense reconstruction, 比较复杂， 自己看吧

CMVS/PMVS: http://www.di.ens.fr/cmvs/

-END-

点击   阅读原文 ，可跳转浏览本文内所有网址链接

*延伸阅读

• 最强战队 | 三维视觉、SLAM方向全球顶尖实验室汇总

• SkeletonNet：完整的人体三维位姿重建方法
  

• ICCV 2019 Oral | 三维"ZAO"脸，单张图片估计人脸几何，效果堪比真实皮肤

极市平台视觉算法季度赛，提供真实应用场景数据和免费算力，特殊时期，一起在家打比赛吧！

添加极市小助手微信 （ID : cv-mart） ，备注： 研究方向-姓名-学校/公司-城市 （如：目标检测-小极-北大-深圳），即可申请加入 目标检测、目标跟踪、人脸、工业检测、医学影像、三维&SLAM、图像分割等极市技术交流群 ，更有 每月大咖直播分享、真实项目需求对接、求职内推、算法竞赛、 干货资讯汇总、行业技术交流 ， 一起来让思想之光照的更远吧~

△长按添加极市小助手

△长按关注极市平台，获取最新CV干货

觉得有用麻烦给个在看啦~