三維重建 3D reconstruction 有哪些實用算法?

https://www.zhihu.com/question/29885222/answer/918009389在這個問題下，竟然沒有人說大名鼎鼎的KinectFusion以及他後面的一系列工作？KinectFusion單篇論文引用都已經超過3000次了，不應該啊！如果只想看現階段效果最好的三維重建算法，請拉到文章最後（如有更好的算法，還請告知）。帝國理工的Newcombe等人在2011年提出的KinectFusion，可在不需要RGB圖而只用深度圖的情況下就能實時地建立三維模型。KinectFusion算法首次實現了基於廉價消費類相機的實時剛體重建，在當時是非常有影響力的工作，它極大的推動了實時稠密三維重建的商業化進程。KinectFusion重建效果

在他們的論文中沒有開原始碼，最初的代碼是由PCL團隊實現的：

KinectFusion的重建效果可以看這個視頻：KinectFusion之後，陸續出現了Kintinuous，ElasticFusion，ElasticReconstruction，DynamicFusion，InfiniTAM，BundleFusion等非常優秀的工作。其中2017年史丹福大學提出的BundleFusion算法，據說是目前基於RGB-D相機進行稠密三維重建效果最好的方法。
二、Kintinuous和ElasticFusion這兩個工作都是同一個人做出來的，這個人就是Thomas Whelan。這兩個工作應該算KinectFusion之後影響力比較大的。

Kintinuous GitHub代碼：

mp3guy/Kintinuous

mp3guy/ElasticFusion

Kintinuous2.0重建效果：

Kintinuous2.0重建效果ElasticFusion 重建效果項目官網：http://qianyi.info/scene.htmlGitHub代碼：qianyizh/ElasticReconstructionElasticReconstruction重建效果InfiniTAM提供Linux，iOS，Android平臺版本，CPU可以實時重建。GitHub代碼：victorprad/InfiniTAM官網：DynamicFusion Project Page

代碼：

https://github.com/mihaibujanca/dynamicfusionDynamicFusion重建效果論文：https://arxiv.org/pdf/1604.01093.pdf算法解讀：計算機視覺方向簡介 | 深度相機室內實時稠密三維重建

作者 | 劉銳@知乎

來源：

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

主要的深度學習系列算法有DBN， ConvNets, RNN等，基本上經典的深度學習算法都用過。詳細請看唐路路（研究方向 深度學習 3D重建）在專欄 機器學習&深度學習--學術水準的理解 總結的文章 深度學習在3D重建上的應用。近年來Deep Learning在計算機視覺上的應用主要在2D image 的detection，segmentation，classification等方面，感覺已經快無孔不入了。但是DL在3D scene上的研究相對還較少，比如3D reconstruction or 3D modeling。因此,今天我想淺談下image-based 3D reconstruction.具體來講，image-based的3D重構算法可以描述為當給定某個物體或場景的一組照片時， 在一些假設條件下，比如物體材料、觀測視角和光照環境等，通過估計一個最相似的3D shape來解釋這組照片。一個完整的3D重構流程通常包含以下幾個步驟：1. 收集場景圖片（Collect images）;2. 計算每張圖的相機參數（Camera parameters for each image）；3. 通過圖組來重構場景的 3D shape（幾何模型）以及其對應的相機參數;（Reconstruct the 3D geometry of the scene and corresponding camera parameters.）4. 有選擇的重構場景的材料等（Optionally texture the reconstructed scene.）。

(Image source：Multi-View Stereo: A Tutorial, by Yasutaka Furukawa from Washington University)其中最核心的工作是第三步：3D shape的重構算法。常規的3D shape representation有以下四種：深度圖（depth）、點雲（point cloud）、體素（voxel）、網格（mesh）。近年來，基於Deep learning 的3D reconstruction 也逐漸火熱起來, 例如David EigenNIPS2014上的文章 「Depth Map Prediction from a Single Image using a Multi-Scale Deep Network」，以及Fayao Liu 在CVPR2015上的文章「Deep Convolutional Neural Fields for Depth Estimation from a Single Image」。兩篇文章都是利用CNN網絡結構學習預測 a single image與其對應的depth map 之間的關係。然而我個人覺得depth image 還不足以解釋重構原始input的信息,它只能作為3D scene understanding的一個輔助信息。因此，一些學者開始研究利用一組二維圖來重構3D 點雲圖或voxel以及mesh圖，這裡就不詳細展開了。個人覺得基於deep learning 的3D 點雲和mesh重構是較難以實施的，因為DL學習一個物體完整的架構需要大量數據支撐。然而傳統3D模型是由 vertices 和 triangulation mesh 組成的，因此不一樣的data size造成了training的困難。所以後續大家都用 voxelization(Voxel）的方法把所有CAD model轉成binary voxel 模式（有值為1，空缺為0）這樣保證了每個模型都是相同的大小。早期的voxel-based 三維物體重建代表作有3DShapeNet (princeton.edu)，它採用Deep Belief Network （DBN）來學習 voxel 的 probabilistic embedding 然後在給帶有2.5D信息的圖片後，通過 Gibbs Sampling來不斷預測他的 shape class 和填補他的未知voxel以完成3D模型重建。

後續又有CMU的

paper 「Learning a Predictable and Generative Vector Representation for Objects」，利用auto-encoder 學習3D Model 的 embedding， 然後通過 ConvNets學習一個 deterministic function 讓其 rendered image infer 到學習到的 embedding 上。因為 auto -encoder是generative的，對於新的test image，模型就會infer 到相關的3D model embedding，再通過decoder生成其相應的 3D model。同類型的工作還有Choy 在ECCV2016的一篇文章「3D-R2N2: A Unified Approach for Single and Multi-view 3D Object Reconstruction」。採用深度學習從2D圖像到其對應的3D voxel模型的映射: 首先利用一個標準的CNN結構對原始input image 進行編碼；再利用一個標準 Deconvolution network 對其解碼。用Long Short-Term Memory（LSTM是RNN中的一種）進行過渡連接, LSTM 單元排列成3D網格結構, 每個單元接收一個feature vector from Encoder and Hidden states of neighbors by convolution，並將他們輸送到Decoder中. 這樣每個LSTM單元重構output voxel的一部分。總之，通過這樣的Encoder-3DLSTM-Decoder 的網絡結構就建立了2D images -to -3D voxel model 的映射。

但是，由於3D voxel是三維的，它的resolution成指數增長，所以它的計算相對複雜，目前的工作主要採用32*32*3以下的解析度以防止過多的佔用內存。但這使得最終重構的3D model解析度並不高， 也可能catch不到一些常規的結構（比如對稱性、直線、曲線等），離真實物體還有較大差距。在DL如此火熱的今天，如何將其更好的應用到3D reconstruction（3D重構） 或3D modeling（3D建模）上確實值得我們進一步深入研究。例如考慮如何提高voxel model 的解析度；如何選擇best view 和最少的 view來重構3D物體；如何利用mesh 或point cloud來直接重構3D物體等。但由於mesh 和point cloud是不規則的幾何數據形式，因此直接使用CNN是不可行的。但是可以考慮將3D mesh data 轉化為graphs形式，再對3D曲面上的2D參數進行卷積。具體方法有Spatial construction (Geodesic CNN)和Spectral construction (Spectral CNN)。基於point cloud的方法，可以參考大神Hao Su的CVPR2017文章「PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation」和「A Point Set Generation Network for 3D Object Reconstruction from a Single Image」。但是基於mesh和point cloud的方法總的來講數學東西多，而且細節恢復上效果欠佳。不過可以考慮結合voxel來提高重構精度。這裡就不囉嗦了，有興趣的留言交流。若有理解錯誤的也歡迎指正，謝謝！

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+

先用SIFT對每張照片提取特徵，再對每一對圖片做魯棒的特徵匹配，將所有2圖匹配合併，找出track，通過tracks估算相機參數場景的稀疏結構, 再用相機參數做dense reconstruction, 輸出dense point cloud (with surface nornal)如果需要,可以用poisson surface reconstruction將dense point cloud轉化為polygon1. 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: SIFT on GPU (siftgpu)我的JS實現: web-sfm/src/websift at master · ptx-pluto/web-sfm · GitHub2. 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: ANN - Approximate Nearest Neighbor Library
我的JS實現: web-sfm/src/webmatcher at master · ptx-pluto/web-sfm · GitHub用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實現: web-sfm/ransac.js at master · ptx-pluto/web-sfm · GitHub4. 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 Registrtionbundler是incremental的，並且依賴於sparse bundle adjustment。初始化第一對相機後，便不斷的用已知點估算新相機，並triangulate新的點，直到沒有candidate為止，中間不斷的做SBA來擬合新的參數, 並且每一輪做一次全局SBA。Bundler-Structure from Motion (SfM) for Unordered Image Collections我的JS實現: web-sfm/register.js at master · ptx-pluto/web-sfm · GitHub6. SBA (Sparse Bundle Adjustemt)SBA就是一個為view geometry優化之後的levenberg-marquardt非線性擬合算法. 在最小化projection error的時候，jacobian和hessian矩陣是稀疏的，而且存在特殊規律。利用了稀疏結構之後，就算有幾千個變量需要擬合，速度也非常快。下圖為sparse jacobian和sparse hessian.sba: Sparse Bundle Adjustment in C/C++
web-sfm/sparse-bundle-adjustment.js at master · ptx-pluto/web-sfm · GitHub

7. CMVS/PMVS 

使用surfel model的dense reconstruction, 比較複雜， 自己查看。

本文是對知乎高關注問題《三維重建 3D reconstruction 有哪些實用算法》中高贊回答的整理，如有侵權，請聯繫我們。