Skip to main content
Springer Nature Link
Log in

Rank-Constrained Fundamental Matrix Estimation by Polynomial Global Optimization Versus the Eight-Point Algorithm

  • Published:
Journal of Mathematical Imaging and Vision Aims and scope Submit manuscript

Abstract

The fundamental matrix can be estimated from point matches. The current gold standard is to bootstrap the eight-point algorithm and two-view projective bundle adjustment. The eight-point algorithm first computes a simple linear least squares solution by minimizing an algebraic cost and then projects the result to the closest rank-deficient matrix. We propose a single-step method that solves both steps of the eight-point algorithm. Using recent results from polynomial global optimization, our method finds the rank-deficient matrix that exactly minimizes the algebraic cost. In this special case, the optimization method is reduced to the resolution of very short sequences of convex linear problems which are computationally efficient and numerically stable. The current gold standard is known to be extremely effective but is nonetheless outperformed by our rank-constrained method for bootstrapping bundle adjustment. This is here demonstrated on simulated and standard real datasets. With our initialization, bundle adjustment consistently finds a better local minimum (achieves a lower reprojection error) and takes less iterations to converge.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20

Similar content being viewed by others

References

  1. Longuet-Higgins, H.C.: A computer algorithm for reconstructing a scene from two projections. Nature 293, 133–135 (1981)

    Article  Google Scholar 

  2. Armangué, X., Salvi, J.: Overall view regarding fundamental matrix estimation. Image Vis. Comput. 21, 205–220 (2003)

    Article  Google Scholar 

  3. Tsai, R.Y., Huang, T.S.: Uniqueness and estimation of three-dimensional motion parameters of rigid objects with curved surfaces. IEEE Trans. Pattern Anal. Mach. Intell. 6, 13–26 (1984)

    Article  Google Scholar 

  4. Hartley, R.: In defence of the 8-point algorithm. In: 5th International Conference on Computer Vision (ICCV’95), Boston, pp. 1064–1070 (1995)

  5. Torr, P.H.S., Fitzgibbon, A.W.: Invariant fitting of two view geometry or in defiance of the 8 point algorithm. In: British Machine Vision Conference (2002)

  6. Chojnacki, W., Brooks, M.J., Van Den Hengel, A.: Revisiting Hartley’s normalized eight-point algorithm. IEEE Trans. Pattern Anal. Mach. Intell. 25, 1172–1177 (2003)

    Article  Google Scholar 

  7. Bartoli, A., Sturm, P.: Nonlinear estimation of the fundamental matrix with minimal parameters. IEEE Trans. Pattern Anal. Mach. Intell. 26(3), 426–432 (2004)

    Article  Google Scholar 

  8. Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 796–817 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  9. Henrion, D., Lasserre, J.B.: Gloptipoly: global optimization over polynomials with Matlab and SeDuMi. In: Proceedings of IEEE Conference on Decision and Control (2002)

  10. Xuelian, X.: New fundamental matrix estimation method using global optimization. In: Proceedings of International Conference on Computer Application and System Modeling (ICCASM), Taiyuan, 22–24 October (2010)

  11. Chesi, G., Garulli, A., Vicino, A., Cipolla, R.: Estimating the fundamental matrix via constrained least-squares: A convex approach. IEEE Trans. Pattern Anal. Mach. Intell. 24, 397–401 (2002)

    Article  Google Scholar 

  12. Kahl, F., Henrion, D.: Globally optimal estimates for geometric reconstruction problems. Int. J. Comput. Vis. 74, 3–15 (2007)

    Article  Google Scholar 

  13. Salvi, J.: An approach to coded structured light to obtain three dimensional information. Ph.D. thesis, University of Girona (1999)

  14. Chen, P.: Why not use the lm method for fundamental matrix estimation? IET Comput. Vis. 4(4), 286–294 (2010)

    Article  MathSciNet  Google Scholar 

  15. Luong, Q.-T., Faugeras, O.: The fundamental matrix: theory, algorithms, and stability analysis. Int. J. Comput. Vis. 17(1), 43–76 (1996)

    Article  Google Scholar 

  16. Zhang, Z.: Determining the epipolar geometry and its uncertainty: a review. Int. J. Comput. Vis. 27, 161–195 (1998)

    Article  Google Scholar 

  17. Van Den Hengel, A., Chojnacki, W., Brooks, M.J., Gawley, D.: A new constrained parameter estimator: experiments in fundamental matrix computation. In: Proceedings of the 13th British Machine Vision Conference (2002)

  18. Chojnacki, W., Brooks, M.J., Van Den Hengel, A., Gawley, D.: A new approach to constrained parameter estimation applicable to some computer vision problems. In: Statistical Methods in Video Processing Workshop Held in Conjunction with ECCV’02, Copenhagen (2002)

  19. Hartley, R., Zisserman, A.: Multiple View Geometry in Computer Vision. Cambridge University Press, Cambridge (2003)

    Google Scholar 

  20. Torr, P.H.S., Murray, D.W.: The development and comparison of robust methods for estimating the fundamental matrix. Int. J. Comput. Vis. 24, 271–300 (1997)

    Article  Google Scholar 

  21. Glover, F.: Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13(5), 533–549 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  22. Hansen, P., Jaumard, B.: Algorithms for the maximum satisfiability problem. Computing 44(4), 279–303 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  23. Land, A.H., Doig, A.G.: An automatic method of solving discrete programming problems. Econometrica 28, 497–520 (1960)

    Article  MATH  MathSciNet  Google Scholar 

  24. Hansen, E.R., Walster, G.W.: Global Optimization Using Interval Analysis, 2nd edn. Marcel Dekker, New York (2003)

    Google Scholar 

  25. Moore, R.E., Kearfott, R.B., Cloud, M.J.: Introduction to Interval Analysis. SIAM, Philadelphia (2009)

    Book  MATH  Google Scholar 

  26. Weise, T.: Global Optimization Algorithms: Theory and Application, 2007-05-01 edn. Thomas Weise (2007)

  27. Zheng, Y., Sugimoto, S., Okutomi, M.: A practical rank-constrained eight-point algorithm for fundamental matrix estimation. In: CVPR 2013, IEEE Conference on Computer Vision and Pattern Recognitio (2013)

  28. Lasserre, J.B.: Optimisation globale et théorie des moments. C. R. Acad. Sci. 331, 929–934 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  29. Lasserre, J.B.: Moments, Positive Polynomials and Their Applications, Volume 1 of Imperial College Press Optimization Series. Imperial College Press, London (2010)

    Google Scholar 

  30. Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Emerging Applications of Algebraic Geometry. IMA Volumes in Mathematics and its Applications, vol. 149, pp. 157–270 (2009)

  31. Borchers, B.: Csdp, a c library for semidefinite programming. Optim. Methods Softw. 11, 613–623 (1999)

    Article  MathSciNet  Google Scholar 

  32. Benson, S.J., Ye, Y.: DSDP5 user guide: software for semidefinite programming. Technical Report ANL/MCS-TM-277, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne. http://www.mcs.anl.gov/hs/software/DSDP/. (2005). Accessed 03 Nov 2014

  33. Fujisawa, K., Fukuda, M., Kojima, M., Nakata, K., Nakata, M., Yamashita, M., Fujisawa, K., Fukuda, M., Kobayashi, K.: Sdpa (semidefinite programming algorithm): user’s manual. Technical Report, Department of Mathematics and Computer Sciences, Tokyo Institute of Technology (2003)

  34. Toh, K.C., Todd, M.J., Tutuncu, R.H.: Solving semidefinite–quadratic–linear programs using SDPT3. Math. Program. 95, 189–217 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  35. Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11–12, 625–653 (1999). Version 1.05. http://sedumi.ie.lehigh.edu/. Accessed 29 Oct 2014

  36. Nie, J.: Optimality conditions and finite convergence of Lasserre’s hierarchy. Technical Report, Department of Mathematics, University of California at San Diego (2012)

  37. Henrion, D., Lasserre, J.B., Löfberg, J.: Gloptipoly 3: moments, optimization and semidefinite programming. Optim. Methods Softw. 24, 761–779 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  38. Löfberg, J.: Yalmip: a toolbox for modeling and optimization in MATLAB. In: Proceedings of the CACSD Conference, Taipei (2004)

  39. Kahl, F., Henrion, D.: Globally optimal estimates for geometric reconstruction problems. In: Proceedings of the IEEE International Conference on Computer Vision (ECCV) (2005)

  40. Henrion, D., Lasserre, J.B.: Convergent relaxations of polynomial matrix inequalities and static output feedback. IEEE Trans. Autom. Control 51(2), 192–202 (2006)

    Article  MathSciNet  Google Scholar 

  41. Toh, K.C., Todd, M.J., Tutuncu, R.H.: SDPT3: a matlab software package for semidefinite programming. Optim. Methods Softw. 11, 545–581 (1999)

    Article  MathSciNet  Google Scholar 

  42. Luong, Q.-T., Viéville, T.: Canonical representations for the geometries of multiple projective views. Comput. Vis. Image Underst. 64, 193–229 (1996)

    Article  Google Scholar 

  43. Hartley, R., Sturm, P.: Triangulation. Comput. Vis. Image Underst. 68(2), 146–157 (1997)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Université de Toulouse; UPS, INSA, Mines Albi, ISAE, ICA (Institut Clément Ader), Bt 3R1, 118 Route de Narbonne, 31062, Toulouse, France

    Florian Bugarin

  2. ISIT, UMR 6284 CNRS/Université d’Auvergne, Clermont-Ferrand, France

    Adrien Bartoli

  3. LAAS-CNRS, Université de Toulouse, Toulouse, France

    Didier Henrion, Jean-Bernard Lasserre & Thierry Sentenac

  4. Faculty of Electrical Engineering, Czech Technical University in Prague, Praha 6, Czech Republic

    Didier Henrion

  5. Institut de Mathématiques de Toulouse, Université de Toulouse, Toulouse, France

    Jean-Bernard Lasserre

  6. Université de Toulouse; INSA, UPS, Mines Albi, ISAE; ICA (Institut Clément Ader), Campus Jarlard, 81013, Albi, France

    Jean-José Orteu & Thierry Sentenac

Authors
  1. Florian Bugarin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Adrien Bartoli
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Didier Henrion
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jean-Bernard Lasserre
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Jean-José Orteu
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Thierry Sentenac
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Florian Bugarin.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bugarin, F., Bartoli, A., Henrion, D. et al. Rank-Constrained Fundamental Matrix Estimation by Polynomial Global Optimization Versus the Eight-Point Algorithm. J Math Imaging Vis 53, 42–60 (2015). https://doi.org/10.1007/s10851-014-0545-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-014-0545-9

Keywords

Search

Navigation