UC Davis

3D multiple-view reconstruction is an important topic with applications in robotics, surveillance, augmented reality, and other fields. The ubiquity of reconstruction makes it a vital component in many systems, which need hardware and algorithms capable of processing the vast data found in reconstruction. In this dissertation, we first propose a method for performing a stage of reconstruction, triangulation, on the GPU that does not require second-order optimization and yields an order-of-magnitude speedup over a multi-core CPU processor. Next, we accelerate triangulation further on the GPU by discussing a method that leverages the path of a moving camera as a constraint and thus avoids doing non-linear optimization altogether. Subsequently, we shift to the problem of dense stereo, where we use GPU processing power to create more complete dense reconstructions while again leveraging scene constraints to keep runtime tractable. Finally, we devote a large portion of this dissertation to studying the use of multiple GPUs to accelerate the most expensive stage in reconstruction, bundle adjustment. The strategy is to partition the scene and optimize the subproblems in parallel. This approach minimizes communication across GPUs and removes the need for multi-GPU synchronization, which can be costly when there are many GPUs. We analyze multiple parallel, partitioned bundle adjustment strategies and their advantages and disadvantages. We develop an alternate method that parallelizes more efficiently and is scalable on large datasets with more GPUs. We compare the performance of the partitioned, parallel implementation against that of the original, full-problem implementation. We confirm our hypothesis that our approach can obtain large speedups with competitive accuracy for certain scenes but is less robust to ill-conditioned problems and the presence of local minima.