Globally Optimal Structure and Motion Estimation

branch and bound branch and bound

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 non-convex and these works rely on efficient construction of relaxations using developments in convex optimization and algebraic geometry.


Globally Optimal Stratified Autocalibration

branch and bound

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 non-convex 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 :

  1. M.K. Chandraker, S. Agarwal, D.J. Kriegman and S. Belongie. Globally Optimal Affine and Metric Upgrades in Stratified Autocalibration. ICCV 2007, Rio de Janeiro, Brazil. [PDF]
  2. M.K. Chandraker, S. Agarwal, D.J. Kriegman and S. Belongie. Globally Optimal Algorithms for Stratified Autocalibration. IJCV 90(2):236-254, 2010. [PDF]
[Top] [Home]

Optimal Bilinear Programming

branch and bound branch and bound

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 non-rigid structure-from-motion.

Publications :

  1. M.K. Chandraker and D.J. Kriegman. Globally Optimal Bilinear Programming for Computer Vision Applications. CVPR 2008, Anchorage, USA. [PDF]
[Top] [Home]

Direct Autocalibration

branch and bound branch and bound

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 non-linear 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 post-processing.

Publications :

  1. M.K. Chandraker, S. Agarwal, F. Kahl, D. Nistér and D.J. Kriegman. Autocalibration via Rank-Constrained Estimation of the Absolute Quadric. CVPR 2007, Minneapolis, USA. [PDF]
[Top] [Home]

Optimal Triangulation and Camera Resection

branch and bound branch and bound

We present globally optimal solutions to triangulation and camera resectioning, minimizing optimal reprojection error in the standard L2-norm as well as the robust L1-norm. 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 :

  1. S. Agarwal, M.K. Chandraker, F. Kahl, D.J. Kriegman and S. Belongie. Practical Global Optimization for Multiview Geometry. ECCV 2006, Graz, Austria, pp. 592-605, vol. 1. [PDF]
  2. F. Kahl, S. Agarwal, M.K. Chandraker, D.J. Kriegman and S. Belongie. Practical Global Optimization for Multiview Geometry. IJCV 79(3):271-284, September 2008. [PDF]
[Top] [Home]

Last updated May 31, 2014.