Abstract
We introduce a framework for computing statistically optimal estimates of geometric reconstruction problems. While traditional algorithms often suffer from either local minima or non-optimality—or a combination of both—we pursue the goal of achieving global solutions of the statistically optimal cost-function.
Our approach is based on a hierarchy of convex relaxations to solve non-convex optimization problems with polynomials. These convex relaxations generate a monotone sequence of lower bounds and we show how one can detect whether the global optimum is attained at a given relaxation. The technique is applied to a number of classical vision problems: triangulation, camera pose, homography estimation and last, but not least, epipolar geometry estimation. Experimental validation on both synthetic and real data is provided. In practice, only a few relaxations are needed for attaining the global optimum.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Agarwal, S., Chandraker, M.K., Kahl, F., Belongie, S., and Kriegman, D.J. 2006. Practical global optimization for multiview geometry. In European Conf. Computer Vision, Graz, Austria, pp. 592–605.
Boyd, S. and Vandenberghe, L. 2004. Convex Optimization, Cambridge University Press.
Chesi, G., Garullli, A., Vicino, A., and Cipolla, R. 2002. Estimating the fundamental matrix via constrained least-squares: A convex approach. IEEE Trans. Pattern Analysis and Machine Intelligence, 24(3):397–401.
Fazel, M., Hindi, H., and Boyd, S. 2004. Rank minimization and applications in system theory. In American Control Conference, Vol. 4, pp. 3273–3278.
Fusiello, A., Benedetti, A., Farenzena, M., and Busti, A. 2004. Globally convergent autocalibration using interval analysis. IEEE Trans. Pattern Analysis and Machine Intelligence, 26(12):1633–1638.
Hartley, R. and Schaffalitzky, F. 2004. L_∞ minimization in geometric reconstruction problems. In Conf. Computer Vision and Pattern Recognition, Washington DC, USA, Vol. I, pp. 504–509.
Hartley, R. and Sturm, P. 1997. Triangulation. Computer Vision and Image Understanding, 68(2):146–157.
Hartley, R.I. and Zisserman, A. 2004. Multiple View Geometry in Computer Vision, 2nd Edn., Cambridge University Press.
Henrion, D. and Garulli, A. (Eds.) 2005. Positive Polynomials in Control. Lecture Notes in Control and Information Sciences. Springer-Verlag.
Henrion, D. and Lasserre, J.B. 2003. GloptiPoly: Global optimization over polynomials with Matlab and SeDuMi. ACM Trans. Math. Soft., 29(2):165–194.
Henrion, D. and Lasserre, J.B. 2004. Solving nonconvex optimization problems—how GloptiPoly is applied to problems in robust and nonlinear control. IEEE Control Systems Magazine, 24(3):72–83.
Henrion, D. and Lasserre, J.B. 2005. Detecting global optimality and extracting solutions in GloptiPoly. In Positive Polynomials in Control, Springer-Verlag.
Henrion, D. and Lasserre, J.B. 2006. Convergent relaxations of polynomial matrix inequalities and static output feedback. IEEE Trans. Automatic Control, 51(2):192–202.
Jibetean, D. and de Klerk, E. 2006. Global optimization of rational functions: A semidefinite programming approach. Mathematical Programming, 106(1):93–109.
Kahl, F. 2005. Multiple view geometry and the L_∞-norm. In Int. Conf. Computer Vision, Beijing, China, pp. 1002–1009.
Kahl, F. and Henrion, D. 2005. Globally optimal estimates for geometric reconstruction problems. In Int. Conf. Computer Vision, Beijing, China, pp. 978–985.
Kahl, F., Heyden, A., and Quan, L. 2001. Minimal projective reconstruction including missing data. IEEE Trans. Pattern Analysis and Machine Intelligence, 23(4):418–424.
Kim, Y. and Mesbahi, M. 2004. On the rank minimization problem. In American Control Conference, Vol. 3, pp. 2015–2020.
Kolmogorov, V. and Zabih, R. 2002. Multi-camera scene reconstruction via graph cuts. In European Conf. Computer Vision, Copenhagen, Denmark, Vol. III, pp. 82–96.
Lasserre, J.B. 2001. Global optimization with polynomials and the problem of moments. SIAM J. Optimization, 11:796–817.
Ma, Y., Soatto, S., Kosecka, J., and Sastry, S. 2003. An Invitation to 3-D Vision: From Images to Geometric Models, Springer Verlag.
Nistér, D. 2001. Automatic dense reconstruction from uncalibrated video sequences. PhD thesis, Royal Institute of Technology KTH, Sweden.
Oliensis, J. 2002. Exact two-image structure from motion. IEEE Trans. Pattern Analysis and Machine Intelligence, 24(12):1618–1633.
Shor, N.Z. 1998. Nondifferentiable Optimization and Polynomial Problems, Kluwer Academic Publishers.
Soatto, S. and Brockett, R. 1998. Optimal structure from motion: Local ambiguities and global estimates. In Conf. Computer Vision and Pattern Recognition, Santa Barbara, USA.
Stewénius, H., Schaffalitzky, F., and Nistér, D. 2005. How hard is three-view triangulation really? In Int. Conf. Computer Vision, Beijing, China, pp. 686–693.
Sturm, J.F. 1999. Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones. Optimization Methods and Software, 11–12:625–653.
Szeliski, R. and Kang, S.B. 1997. Shape ambiguities in structure from motion. IEEE Trans. Pattern Analysis and Machine Intelligence, 19(5).
Tomasi, C. and Kanade, T. 1992. Shape and motion from image streams under orthography: A factorization method. Int. Journal Computer Vision, 9(2):137–154.
Triggs, B., McLauchlan, P.F., Hartley, R.I., and Fitzgibbon, A.W. 1999. Bundle adjustment—a modern synthesis. In Vision Algorithms’99, pp. 298–372, in conjunction with ICCV’99, Kerkyra, Greece.
Waki, H., Kim, S., Kojima, M., and Muramatsu, M. 2006. Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity. SIAM J. Optimization, 17(1):218–242.
Zhang, Z. 1998. On the optimization criteria used in two-view motion analysis. IEEE Trans. Pattern Analysis and Machine Intelligence, 20(7):717–729.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kahl, F., Henrion, D. Globally Optimal Estimates for Geometric Reconstruction Problems. Int J Comput Vision 74, 3–15 (2007). https://doi.org/10.1007/s11263-006-0015-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11263-006-0015-y