In this line of work, we present a unified framework for globally optimal solutions to several important problems in multiview geometry. Structure from motion problems are inherently nonconvex and these works rely on efficient construction of relaxations using developments in convex optimization and algebraic geometry. 
Globally Optimal Stratified Autocalibration 
We present a practical, stratified autocalibration algorithm with theoretical guarantees of global optimality. Given a projective reconstruction, the first stage of the algorithm upgrades it to affine by estimating the globally optimal position of the plane at infinity. In the second stage, a metric upgrade is performed by computing the globally optimal dual image of the absolute conic (DIAC). For each stage, we construct and minimize tight convex relaxations of the highly nonconvex objective functions in a branch and bound optimization framework. We exploit the problem structure to restrict search spaces for the DIAC and plane at infinity to a small, fixed number of branching dimensions, independent of number of views. 
Publications :

Optimal Bilinear Programming 
A wide variety of problems in computer vision can be posed as bilinear programs, for which we provide a globally optimal solution, in both standard L2 and robust L1 norms. Efficient convex elaxations are constructed and minimized in a branch and bound paradigm. The main theoretical result proves that the structure of common bilinear programs in computer vision allows a drastic reduction in search space. Example applications include 3D face reconstruction from exemplars using a single input image and nonrigid structurefrommotion. 
Publications :

Direct Autocalibration 
Direct autocalibration recovers the metric reconstruction in a single step, by estimating the absolute dual quadric. The problem is formulated as a polynomial objective function, subject to polynomial constraints. Rather than use locally optimal nonlinear minimization, we construct convex linear matrix inequality relaxations of the polynomial program to globally minimize it. Unlike prior work, our framework enforces critical requirements like rank degeneracy and semidefiniteness of the quadric within the estimation, rather than as postprocessing. 
Publications :

Optimal Triangulation and Camera Resection 
We present globally optimal solutions to triangulation and camera resectioning, minimizing optimal reprojection error in the standard L2norm as well as the robust L1norm. We show these problems to be instances of a wider class of fractional programs, for which we construct efficient second order cone programming relaxations. Subsequently, global minimization is carried out in a branch and bound framework, exploiting the properties of multiview geometry to achieve rapid convergence in practice. 
Publications :

Last updated May 31, 2014.