TY - JOUR

T1 - Globally optimal algorithms for stratified autocalibration

AU - Chandraker, Manmohan

AU - Agarwal, Sameer

AU - Kriegman, David

AU - Belongie, Serge

N1 - Funding Information: Acknowledgements The authors would like to thank Fredrik Kahl for several helpful discussions and providing data for the experiments with real images. Manmohan Chandraker and David Kriegman were supported by NSF EIA-0303622. Sameer Agarwal was supported by NSF EIA-0321235, UW Animation Research Labs, Washington Research Foundation, Adobe and Microsoft. Serge Belongie was supported by NSF Career #0448615 and the Sloan Research Fellowship.

PY - 2010/11

Y1 - 2010/11

N2 - We present practical algorithms for stratified autocalibration with theoretical guarantees of global optimality. Given a projective reconstruction, we first upgrade it to affine by estimating the position of the plane at infinity. The plane at infinity is computed by globally minimizing a least squares formulation of the modulus constraints. In the second stage, this affine reconstruction is upgraded to a metric one by globally minimizing the infinite homography relation to compute the dual image of the absolute conic (DIAC). The positive semidefiniteness of the DIAC is explicitly enforced as part of the optimization process, rather than as a post-processing step. 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 inherent problem structure to restrict the search space for the DIAC and the plane at infinity to a small, fixed number of branching dimensions, independent of the number of views. Chirality constraints are incorporated into our convex relaxations to automatically select an initial region which is guaranteed to contain the global minimum. Experimental evidence of the accuracy, speed and scalability of our algorithm is presented on synthetic and real data.

AB - We present practical algorithms for stratified autocalibration with theoretical guarantees of global optimality. Given a projective reconstruction, we first upgrade it to affine by estimating the position of the plane at infinity. The plane at infinity is computed by globally minimizing a least squares formulation of the modulus constraints. In the second stage, this affine reconstruction is upgraded to a metric one by globally minimizing the infinite homography relation to compute the dual image of the absolute conic (DIAC). The positive semidefiniteness of the DIAC is explicitly enforced as part of the optimization process, rather than as a post-processing step. 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 inherent problem structure to restrict the search space for the DIAC and the plane at infinity to a small, fixed number of branching dimensions, independent of the number of views. Chirality constraints are incorporated into our convex relaxations to automatically select an initial region which is guaranteed to contain the global minimum. Experimental evidence of the accuracy, speed and scalability of our algorithm is presented on synthetic and real data.

KW - Autocalibration

KW - Convex relaxations

KW - Global optimization

KW - Multiple view geometry

UR - http://www.scopus.com/inward/record.url?scp=79960327284&partnerID=8YFLogxK

U2 - 10.1007/s11263-009-0305-2

DO - 10.1007/s11263-009-0305-2

M3 - Journal article

AN - SCOPUS:79960327284

VL - 90

SP - 236

EP - 254

JO - International Journal of Computer Vision

JF - International Journal of Computer Vision

SN - 0920-5691

IS - 2

ER -