Globally Optimal Algorithms for Stratified Autocalibration

被引:21
作者
Chandraker, Manmohan [1 ]
Agarwal, Sameer [2 ]
Kriegman, David [1 ]
Belongie, Serge [1 ]
机构
[1] Univ Calif San Diego, Dept Comp Sci & Engn, San Diego, CA 92103 USA
[2] Univ Washington, Dept Comp Sci & Engn, Seattle, WA 98195 USA
基金
美国国家科学基金会;
关键词
Autocalibration; Multiple view geometry; Global optimization; Convex relaxations; OPTIMIZATION; POLYNOMIALS; PROGRAMS; MATLAB;
D O I
10.1007/s11263-009-0305-2
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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.
引用
收藏
页码:236 / 254
页数:19
相关论文
共 47 条
[1]  
Agarwal S., 2008, IEEE C COMP VIS PATT
[2]  
AGARWAL S, 2006, EUR C COMP VIS, P592
[3]  
AGRAWAL M, 2004, INT C IM PROC
[4]   JOINTLY CONSTRAINED BICONVEX PROGRAMMING [J].
ALKHAYYAL, FA ;
FALK, JE .
MATHEMATICS OF OPERATIONS RESEARCH, 1983, 8 (02) :273-286
[5]  
[Anonymous], IEEE C COMP VIS PATT
[6]  
[Anonymous], IEEE C COMP VIS PATT
[7]  
[Anonymous], 2001, Robotica, DOI DOI 10.1017/S0263574700223217
[8]  
[Anonymous], EUR C COMP VIS ECCV
[9]  
Boyd S., 2004, CONVEX OPTIMIZATION, VFirst, DOI DOI 10.1017/CBO9780511804441
[10]  
Breuel TM, 2002, LECT NOTES COMPUT SC, V2352, P837