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.
Similar content being viewed by others
References
Longuet-Higgins, H.C.: A computer algorithm for reconstructing a scene from two projections. Nature 293, 133–135 (1981)
Armangué, X., Salvi, J.: Overall view regarding fundamental matrix estimation. Image Vis. Comput. 21, 205–220 (2003)
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)
Hartley, R.: In defence of the 8-point algorithm. In: 5th International Conference on Computer Vision (ICCV’95), Boston, pp. 1064–1070 (1995)
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)
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)
Bartoli, A., Sturm, P.: Nonlinear estimation of the fundamental matrix with minimal parameters. IEEE Trans. Pattern Anal. Mach. Intell. 26(3), 426–432 (2004)
Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 796–817 (2001)
Henrion, D., Lasserre, J.B.: Gloptipoly: global optimization over polynomials with Matlab and SeDuMi. In: Proceedings of IEEE Conference on Decision and Control (2002)
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)
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)
Kahl, F., Henrion, D.: Globally optimal estimates for geometric reconstruction problems. Int. J. Comput. Vis. 74, 3–15 (2007)
Salvi, J.: An approach to coded structured light to obtain three dimensional information. Ph.D. thesis, University of Girona (1999)
Chen, P.: Why not use the lm method for fundamental matrix estimation? IET Comput. Vis. 4(4), 286–294 (2010)
Luong, Q.-T., Faugeras, O.: The fundamental matrix: theory, algorithms, and stability analysis. Int. J. Comput. Vis. 17(1), 43–76 (1996)
Zhang, Z.: Determining the epipolar geometry and its uncertainty: a review. Int. J. Comput. Vis. 27, 161–195 (1998)
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)
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)
Hartley, R., Zisserman, A.: Multiple View Geometry in Computer Vision. Cambridge University Press, Cambridge (2003)
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)
Glover, F.: Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13(5), 533–549 (1986)
Hansen, P., Jaumard, B.: Algorithms for the maximum satisfiability problem. Computing 44(4), 279–303 (1990)
Land, A.H., Doig, A.G.: An automatic method of solving discrete programming problems. Econometrica 28, 497–520 (1960)
Hansen, E.R., Walster, G.W.: Global Optimization Using Interval Analysis, 2nd edn. Marcel Dekker, New York (2003)
Moore, R.E., Kearfott, R.B., Cloud, M.J.: Introduction to Interval Analysis. SIAM, Philadelphia (2009)
Weise, T.: Global Optimization Algorithms: Theory and Application, 2007-05-01 edn. Thomas Weise (2007)
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)
Lasserre, J.B.: Optimisation globale et théorie des moments. C. R. Acad. Sci. 331, 929–934 (2000)
Lasserre, J.B.: Moments, Positive Polynomials and Their Applications, Volume 1 of Imperial College Press Optimization Series. Imperial College Press, London (2010)
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)
Borchers, B.: Csdp, a c library for semidefinite programming. Optim. Methods Softw. 11, 613–623 (1999)
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
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)
Toh, K.C., Todd, M.J., Tutuncu, R.H.: Solving semidefinite–quadratic–linear programs using SDPT3. Math. Program. 95, 189–217 (2003)
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
Nie, J.: Optimality conditions and finite convergence of Lasserre’s hierarchy. Technical Report, Department of Mathematics, University of California at San Diego (2012)
Henrion, D., Lasserre, J.B., Löfberg, J.: Gloptipoly 3: moments, optimization and semidefinite programming. Optim. Methods Softw. 24, 761–779 (2009)
Löfberg, J.: Yalmip: a toolbox for modeling and optimization in MATLAB. In: Proceedings of the CACSD Conference, Taipei (2004)
Kahl, F., Henrion, D.: Globally optimal estimates for geometric reconstruction problems. In: Proceedings of the IEEE International Conference on Computer Vision (ECCV) (2005)
Henrion, D., Lasserre, J.B.: Convergent relaxations of polynomial matrix inequalities and static output feedback. IEEE Trans. Autom. Control 51(2), 192–202 (2006)
Toh, K.C., Todd, M.J., Tutuncu, R.H.: SDPT3: a matlab software package for semidefinite programming. Optim. Methods Softw. 11, 545–581 (1999)
Luong, Q.-T., Viéville, T.: Canonical representations for the geometries of multiple projective views. Comput. Vis. Image Underst. 64, 193–229 (1996)
Hartley, R., Sturm, P.: Triangulation. Comput. Vis. Image Underst. 68(2), 146–157 (1997)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
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
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10851-014-0545-9