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

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

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

三维重建 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-

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

*延伸阅读

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

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

△长按添加极市小助手

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

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

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章