Efficient 3D Scene Reconstruction From Multi-view Images

Multi-view reconstruction is a basic problem in computer vision, which has a wide area of applications. This thesis aims at how to implement large scale multi-view reconstruc-tion problem efficiently. Here large scale means the quantity of input views is much more than before, followed by high computation complexity. Along with the increasing amount of input images, the computational consumption of the reconstruction grows rapidly. The theoretical analysis and experiments indicate that the performance bottleneck lies in the fol-lowing two steps of the reconstruction pipeline:(1) feature detection and matching; (2) multi-view geometry computation. As the beginning of multi-view reconstruction, features need to be detected in each input view and be matched between each pair of views. The computation complexity of this procedure is square order of the quantity of input views. Since multi-view geometry constraints are calculated between each pair of views too, the computation complexity grows substantially as the quantity of input views increases. In addition to efficiency, the robustness of the algorithm also should be considered.For feature detection, a new GPU (Graphic Processor Unit) accelerated parallel SIFT (scale invariant feature transform) algorithm is proposed. The computational complexity on each step of SIFT was finely analyzed, and the feasibility of parallelization was studied base on CUDA (Compute Unified Device Architecture). We show experimentally that the proposed method can achieve 28 frame per second on 640 x 480 image resolution, which is 30 x faster than the CPU algorithm and 1.5 x faster than the state-of-the-art GPU algorithm.For feature matching, a new method based on LSH (Locality Sensitive Hashing) is proposed. Different from current methods which are based on local matching between pairs of views, the proposed method collect the feature points from all the views, treat them as a database and try to solve the matching problem globally. We also proposed a new BSLSH (Balanced Sphere LSH), which take the data characteristics of SIFT descriptors into consideration. We show experimentally that our method achieved 2.9x to 7.8x speedup to the linear search with a precision drop in the range from 9%to 20%.For the computation of multi-view geometry, a new robust estimator LO-MLESAC is proposed by integrating local optimization and maximum likelihood estimation into the random sample framework. We also proposed a stategy for efficient computation of the multi-view geometry system, which can eliminate uncorrelated view pairs from the system and save the time on computation. The result of the experiment showed that our method achieved 2.4x to 3.1 x speedup with less than 5%decrease on the output inliers.