Abstract
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. The efficacy of our algorithm 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.
Chapter PDF
Similar content being viewed by others
References
Freund, R.W., Jarre, F.: Solving the sum-of-ratios problem by an interior-point method. J. Glob. Opt. 19, 83–102 (2001)
Longuet-Higgins, H.: A computer algorithm for reconstructing a scene from two projections. Nature 293, 133–135 (1981)
Hartley, R.I., Zisserman, A.: Multiple View Geometry in Computer Vision, 2nd edn. Cambridge University Press, Cambridge (2004)
Tawarmalani, M., Sahinidis, N.V.: Semidefinite relaxations of fractional programs via novel convexification techniques. J. Glob. Opt. 20, 137–158 (2001)
Benson, H.P.: Using concave envelopes to globally solve the nonlinear sum of ratios problem. J. Glob. Opt. 22, 343–364 (2002)
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)
Hartley, R., Sturm, P.: Triangulation. CVIU 68, 146–157 (1997)
Stewénius, H., Schaffalitzky, F., Nistér, D.: How hard is three-view triangulation really? In: Int. Conf. Computer Vision, pp. 686–693 (2005)
Kahl, F., Henrion, D.: Globally optimal estimates for geometric reconstruction problems. In: Int. Conf. Computer Vision, Beijing, China, pp. 978–985 (2005)
Ke, Q., Kanade, T.: Robust L 1 norm factorization in the presence of outliers and missing data by alternative convex programming. In: CVPR, pp. 739–746 (2005)
Kahl, F.: Multiple view geometry and the L ∞ -norm. In: Int. Conf. Computer Vision, Beijing, China, pp. 1002–1009 (2005)
Sturm, J.: Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones. Optimization Methods and Software 11-12, 625–653 (1999)
Schaible, S., Shi, J.: Fractional programming: the sum-of-ratios case. Opt. Meth. Soft. 18, 219–229 (2003)
Kotz, S., Kozubowski, T.J., Podgorski, K.: The Laplace distribution and generalizations. Birkhäuser, Basel (2001)
Wolf, L., Shashua, A.: On projection matrices P k ↦P 2, k = 3,...,6, and their applications in computer vision. Int. Journal Computer Vision 48, 53–67 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Agarwal, S., Chandraker, M.K., Kahl, F., Kriegman, D., Belongie, S. (2006). Practical Global Optimization for Multiview Geometry. In: Leonardis, A., Bischof, H., Pinz, A. (eds) Computer Vision – ECCV 2006. ECCV 2006. Lecture Notes in Computer Science, vol 3951. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11744023_46
Download citation
DOI: https://doi.org/10.1007/11744023_46
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33832-1
Online ISBN: 978-3-540-33833-8
eBook Packages: Computer ScienceComputer Science (R0)