TY - JOUR

T1 - Practical global optimization for multiview geometry

AU - Kahl, Fredrik

AU - Agarwal, Sameer

AU - Chandraker, Manmohan Krishna

AU - Kriegman, David

AU - Belongie, Serge

N1 - Funding Information: Acknowledgements S. Agarwal and S. Belongie are supported by NSF-CAREER #0448615, DOE/LLNL contract no. W-7405-ENG-48 (subcontracts B542001 and B547328), and the Alfred P. Sloan Fellowship. M. Chandraker and D. Kriegman are supported by NSF EIA 0303622 & NSF IIS-0308185. F. Kahl is supported by Swedish Research Council (VR 2004-4579) & European Commission (Grant 011838, SMERobot).

PY - 2008/9

Y1 - 2008/9

N2 - This paper presents a practical method for finding the provably globally optimal solution to numerous problems in projective geometry including multiview triangulation, camera resectioning and homography estimation. Unlike traditional methods which may get trapped in local minima due to the non-convex nature of these problems, this approach provides a theoretical guarantee of global optimality. The formulation relies on recent developments in fractional programming and the theory of convex underestimators and allows a unified framework for minimizing the standard L 2-norm of reprojection errors which is optimal under Gaussian noise as well as the more robust L 1-norm which is less sensitive to outliers. Even though the worst case complexity of our algorithm is exponential, the practical efficacy is empirically demonstrated by good performance on experiments for both synthetic and real data. An open source MATLAB toolbox that implements the algorithm is also made available to facilitate further research.

AB - This paper presents a practical method for finding the provably globally optimal solution to numerous problems in projective geometry including multiview triangulation, camera resectioning and homography estimation. Unlike traditional methods which may get trapped in local minima due to the non-convex nature of these problems, this approach provides a theoretical guarantee of global optimality. The formulation relies on recent developments in fractional programming and the theory of convex underestimators and allows a unified framework for minimizing the standard L 2-norm of reprojection errors which is optimal under Gaussian noise as well as the more robust L 1-norm which is less sensitive to outliers. Even though the worst case complexity of our algorithm is exponential, the practical efficacy is empirically demonstrated by good performance on experiments for both synthetic and real data. An open source MATLAB toolbox that implements the algorithm is also made available to facilitate further research.

KW - Branch and bound

KW - Camera pose

KW - Cameras

KW - Geometry

KW - Global optimization

KW - Multiple view geometry

KW - Reconstruction

KW - Triangulation

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

U2 - 10.1007/s11263-007-0117-1

DO - 10.1007/s11263-007-0117-1

M3 - Journal article

AN - SCOPUS:45049084485

VL - 79

SP - 271

EP - 284

JO - International Journal of Computer Vision

JF - International Journal of Computer Vision

SN - 0920-5691

IS - 3

ER -