A Survey of Three-Dimensional Reconstruction Methods

I. What Is Three-Dimensional Reconstruction

Three-dimensional reconstruction uses a camera to photograph real-world objects and scenes, then processes them with computer vision techniques to obtain a three-dimensional model of the object.

The main techniques involved include multi-view stereo, depth map estimation, point cloud processing, mesh reconstruction and optimization, texture mapping, Markov random fields, image segmentation, and more.

Main application areas include augmented reality, mixed reality, robot navigation, autonomous driving, industrial workpiece dimensional inspection, flatness inspection, and more.

II. Traditional Three-Dimensional Reconstruction Methods

2.1 RGBD

Basics

Depth camera: a camera that can directly obtain three-dimensional information about the measured object.

Depth cameras are mainly divided into structured-light cameras and ToF cameras. A structured-light camera projects a fringe pattern or laser speckle forward with an infrared projector, then uses a camera to capture the shape and size of that fringe pattern and speckle, thereby obtaining the object’s three-dimensional information. ToF measures the time between emitting a pulse and receiving it to compute the target distance.

KinectFusion - 2011

Paper: https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6162880
Code: https://github.com/chrdiller/KinectFusionApp

KinectFusion was the first three-dimensional reconstruction system to use an RGBD camera. It uses a TSDF map, and many later real-time three-dimensional reconstruction systems are extensions of KinectFusion.

Implementation pipeline: first acquire an RGBD image and compute the point cloud and the normalized normals; then use the ICP algorithm to compute the camera pose of the current frame; then fuse the current point cloud into the TSDF map; finally, from the TSDF map and the current frame’s pose, predict the current frame’s depth image.

A TSDF map is a grid-style map. First choose the three-dimensional space to be modeled, then divide that space into many small cells at a given resolution and store the information inside each cell. Each TSDF voxel stores the distance from that cell to the nearest object surface. If the cell is in front of the nearest object surface, it has a positive value; conversely, if the cell is behind the surface, the value is negative. Because an object surface is usually a very thin layer, values that are too large or too small are clamped to 1 and -1, which yields the truncated distance—that is, the so-called TSDF.

BundleFunsion - 2016

Paper: https://arxiv.org/abs/1604.01093 Code: https://github.com/niessner/BundleFusion

Rough pipeline: the input color+depth data stream first needs frame-to-frame correspondence matching, then global pose optimization to correct overall drift (shown in the lower part of the figure above). Throughout reconstruction, the model is continuously updated dynamically.

For matching, a sparse-then-dense parallel global optimization method is used. That is, sparse SIFT feature points are first used for coarser registration, because sparse feature points themselves can also be used for loop closure detection and relocalization. Dense geometric and photometric continuity is then used for finer registration.

For pose optimization, a hierarchical local-to-global optimization method is used, as shown in the figure below. There are two layers in total. At the lowest first layer, every 10 consecutive frames form a chunk, with the first frame as the keyframe, and a local pose optimization is performed on all frames in that chunk. At the second layer, only the keyframes of all chunks are associated with one another and then globally optimized. Why go to the trouble of layering? Or rather, what is the benefit of layering this way? Because keyframes can be separated out, reducing the data that must be stored and processed. This hierarchical optimization also reduces the number of unknowns in each optimization, ensuring the method can scale to large scenes with little drift.

For dense scene reconstruction, the algorithm sets three filtering strategies for feature matching. The first directly tests the consistency and stability of the distribution of the keypoints themselves. The second tests the surface area spanned by feature match pairs and removes especially small ones, because pairs that span a small area easily become ambiguous. The third performs dense bilateral geometric and photometric verification and removes match pairs with large reprojection error.

Features: real-time robust tracking on GPU, can address drift, and removes dependence on real-time operation.

2.2 MVS Multi-Frame Image Reconstruction

Basics

MVS reconstructs a 3D model from a series of images.

Pipeline: image capture - pose estimation - model reconstruction - texture mapping. Image capture can be sequential images such as video, or non-contiguous images. In pose estimation, different methods are used depending on whether the images are sequential.

Applications: audiovisual entertainment, AR cultural heritage, autonomous driving, large-scene three-dimensional reconstruction, and more.

Survey: Multi-View Stero: A Tutorial

COLMAP - 2016

Paper: https://ieeexplore.ieee.org/document/7780814 Code: https://github.com/colmap/colmap

SFM usually first performs feature extraction/matching and subsequent geometric verification to filter outliers. After those steps, a so-called scene graph is obtained, which is the basis for subsequent incremental reconstruction (providing data association and other information). In incremental reconstruction, two frames must be selected very carefully for reconstruction. Before an image is registered (that is, before the current frame’s pose in the map is localized), scene points must be triangulated / outliers filtered, and BA must optimize the current model.

The innovations of the COLMAP algorithm are

• It proposes a multi-model geometric verification strategy: improving the robustness of initialization and triangulation;
• A subsequent optimal-frame selection strategy: improving the robustness and accuracy of pose solving;
• It proposes a robust triangulation method: making the reconstructed scene structure more complete;
• It proposes iterative BA, re-triangulation, and outlier filtering strategies that contribute to both reconstruction completeness and accuracy;
• An efficient BA parameterization that helps with reconstruction from dense images;

OpenMVS

Code: https://github.com/cdcseacave/openMVS

The input to OpenMVS is images and poses, where poses can be computed in many ways such as COLMAP or SLAM. It then performs dense reconstruction - point cloud fusion - initial mesh reconstruction - mesh optimization - texture mapping.

Among current three-dimensional reconstruction frameworks, OpenMVS produces relatively good recovery results; it also provides automated scripts and is not very hard to use. You can download, compile, and install it from GitHub.

III. Deep Learning–Based Three-Dimensional Reconstruction

3.1 mesh Reconstruction

Reconstruction Based on 3DMM

3DMM (3D Morphable Model) deformable model: any face image can be reconstructed according to the following formula

$S_{model} = S^2+\sum^{m-1}_{i=1}\alpha_i S_i, T_{model} = T^2+\sum^{m-1}_{i=1}\beta_i T_i$

Extended network: Nonlinear 3D Face Morphable Model

• Learns a nonlinear model with greater representational capacity than traditional linear models;
• Weakly supervised learning: uses large numbers of two-dimensional images without three-dimensional scans to jointly learn the model and the model-fitting algorithm

Extended network: 2DASL

• A self-supervised model that overcomes the shortage of 3D annotated data

Extended network: PRNet

• Solves face alignment and three-dimensional face problems in an end-to-end manner so they are completed together, and is not limited by a low-dimensional solution space
• A lightweight framework that runs at over 100FPS

IF-Nets

IF-NETS is an object and human reconstruction network. The network can reconstruct sparse and dense point clouds into mesh models. Due to dataset limitations (most data are rendered from CAD models), recovery of real-scene models is only average.

PifuHD

PIFu is a human reconstruction network.

Algorithm advantages

• Supports both single-view and multi-view;
• Highly complex shapes such as hairstyles and clothing, as well as their variations and deformations, can all be digitized in a unified way
• Reconstruction accuracy and detail representation are better than existing methods;
• Unlike voxel representations, it is more memory-efficient, can handle arbitrary topology, and the generated surface is spatially aligned with the input image

3.1 Depth Map Reconstruction MVSNet

Network structure: the input is multiple images with arbitrary poses, and the relationships among the images must be considered jointly.

MVSNet essentially borrows depth estimation methods based on a two-image cost volume for binocular stereo matching and extends them to depth estimation from multiple images. Because cost-volume-based binocular stereo matching is already fairly mature, MVSNet is also essentially borrowing from a relatively mature field, then proposing a cost volume based on differentiable homography for multi-view depth estimation.

Process:

(1) Input one reference image (primary) and several source images (auxiliary);

(2) Separately use a network to extract feature maps downsampled to one quarter, with 32 channels;

(3) Adopt the cost volume concept from stereo matching (i.e., binocular depth estimation), and use homography warping to transform the features of several source images onto the reference image. During the transformation, similar to epipolar search, depth information is introduced. Building the cost volume can be said to be the key of MVSNet.

Specifically, a point on the cost volume is the variance of features from all images at that point and depth value; the smaller the variance, the higher the confidence at that depth.

(4) Use 3D convolution to operate on the cost volume, first output the probability of each depth, then take a weighted average of depths to obtain the predicted depth information, and regress the depth with L1 or smoothL1; it is a regression model.

(5) Use reconstruction constraints among multiple images (photometric and geometric consistencies) to select correctly predicted depth information and reconstruct it into a three-dimensional point cloud.

Extended network: MVS-JDACS-MS Introduces co-segmentation and data-augmentation strategies into an unsupervised network framework to overcome interference from illumination differences that naturally exist across views.

Extended network: MVS-PatchMatchNet An efficient multi-view stereo framework based on the traditional PatchMatch algorithm.

IV. Algorithm Benchmark Websites

Binocular stereo matching: https://vision.middlebury.edu/stereo/eval3/

Onboard binocular stereo related algorithms: http://www.cvlibs.net/datasets/kitti/eval_scene_flow.php?benchmark=stereo

Outdoor scenes: https://www.eth3d.net/low_res_two_view

A collection of computer-vision related papers, models, datasets, and code: https://paperswithcode.com/sota