UC San Diego

Reconstructing the three-dimensional structure of a scene using images is a fundamental problem in computer vision. The geometric aspects of 3D reconstruction have been well- understood for a decade, but the involved optimization problems are known to be highly non-convex and difficult to solve. Traditionally, these problems are tackled using heuristic initializations followed by local, gradient- based optimization algorithms, which are prone to being enmeshed in local minima. In contrast, this dissertation proposes powerful, global optimization methods to derive provably optimal, yet practical, algorithms for estimating 3D scene structure and camera motion. This dissertation develops a branch and bound framework to solve several well-established problems in multiview geometry to their global optima, with a certificate of optimality. The framework relies on the construction of efficient and tight relaxations to the involved non-convex problems, using modern convex optimization methods. The underlying geometry of the task is exploited to restrict the search space to a small, fixed number of dimensions, which alleviates the worst case exponential complexity of branch and bound in practice. The dissertation begins by deriving optimal solutions to triangulation and camera pose estimation for an arbitrary number of views and points, using extensions to the theory of fractional programming. Next, the framework is amplified to solve the conceptually important affine and metric reconstruction stages of stratified autocalibration to their global optima. Additionally, an algorithm for directly upgrading a projective reconstruction to a metric one is proposed, based on elegant real algebraic geometry methods for global optimization of polynomial systems. Further, large- scale bilinear programs that arise in diverse applications such as shape from exemplar models and non-rigid structure from motion, are globally optimized using a novel branching strategy that exploits problem structure typical to 3D reconstruction. The final part of the dissertation develops a complete pipeline for real-time 3D reconstruction using stereo images and straight line features. The core structure from motion problem constitutes efficient optimization of an overdetermined system of polynomials that is fast enough to be used in a robust hypothesize-and-test framework. The algorithm has already found application in the autonomous navigation system for the well-known humanoid robot, ASIMO