Skip to main content
Springer Nature Link
Log in

A generic interval branch and bound algorithm for parameter estimation

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

In engineering sciences, parameter estimation is a challenging problem consisting in computing the parameters of a parametric model that fit observed data. The system is defined by unknown parameters and sometimes internal constraints. The observed data provide constraints on the parameters. This problem is particularly difficult when some observation constraints correspond to outliers and/or the constraints are non convex. The ransac randomized algorithm can efficiently handle it, but is non deterministic and must be specialized for every problem. This paper presents the first generic interval branch and bound algorithm that produces a model maximizing the number of observation constraints satisfied within a given tolerance. This tool is inspired by the IbexOpt branch and bound algorithm for constrained global optimization (NLP) and is endowed with an improved version of a relaxed intersection operator applied to observations. Experiments have been carried out on two different computer vision problems. They highlight a significant speedup w.r.t. Jaulin et al.’s interval method in 2D and 3D shape recognition problems (having three parameters). We have also obtained promising results on a stereo vision problem where the essential matrix (five parameters) is estimated exactly at a good accuracy in hours for models having a thousand points, a typical size for such problems.

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

Similar content being viewed by others

Notes

  1. Note that this algorithm is heuristic in that it is possible that no such inner polytope is found.

  2. See https://sites.google.com/site/kevinlai726/datasets.

  3. Thanks to Leo Liberti for suggesting the MIP model.

  4. http://www.robots.ox.ac.uk/~vgg/data/data-mview.html.

  5. http://demo.ipol.im/demo/82/.

References

  1. Araya, I., Trombettoni, G., Neveu, B., Chabert, G.: Upper bounding in inner regions for global optimization under inequality constraints. J. Glob. Optim. (JOGO) 60(2), 145–164 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  2. Bazin, J.C., Seo, Y., Hartley, R., Pollefeys, M.: Globally optimal inlier set maximization with unknown rotation and focal length. In: Proceeding of European Conference of Computer Vision (ECCV), LNCS, vol. 8690, pp. 803–817 (2014)

  3. Benhamou, F., Goualard, F., Granvilliers, L., Puget, J.F.: Revising hull and box consistency. In: Proceeding of International Conference on Logic Programming (ICLP), pp. 230–244 (1999)

  4. Bethencourt, A., Jaulin, L.: 3D reconstruction using interval methods on the kinect device coupled with an IMU. Int. J. Adv. Robot. Syst. 10, 93 (2013)

    Article  Google Scholar 

  5. Campbell, D., Peterson, L., Kneip, L., Li, H.: Globally-optimal inlier set maximisation for simultaneous camera pose and feature correspondence. In: IEEE International Conference on Computer Vision (ICCV) (2017)

  6. Carbonnel, C., Trombettoni, G., Vismara, P., Chabert, G.: Q-intersection algorithms for constrained-based robust parameter estimation. In: Proceeding of Conference of the Association for the Advancement of Artificial Intelligence (AAAI), pp. 2630–2636 (2014)

  7. Chabert, G., Jaulin, L.: Contractor programming. Artif. Intell. 173, 1079–1100 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  8. Chew, P., Marzullo, K.: Masking failures of multidimensional sensors. In: Proceeding of Reliable Distributed Systems, pp. 32–41 (1991)

  9. Chin, T.J., Purkait, P., Eriksson, A., Suter, D.: Efficient globally optimal consensus maximisation with tree search. In: Proceeding of CVPR 15 (2015)

  10. Chin, T.J., Purkait, P., Eriksson, A., Suter, D.: Efficient globally optimal consensus maximisation with tree search. IEEE Trans. Pattern Anal. Mach. Intell. 39(4), 758–772 (2017)

    Article  Google Scholar 

  11. Collavizza, H., Delobel, F., Rueher, M.: Comparing partial consistencies. Reliab. Comput. 5(3), 213–228 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  12. Fischler, M.A., Bolles, R.C.: Random sampling consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 24(6), 381–395 (1981)

    Article  Google Scholar 

  13. Fusiello, A., Benedetti, A., Farenzena, M., Busti, A.: Globally convergent autocalibration using interval analysis. IEEE Trans. Pattern Anal. Mach. Intell. 26(12), 1633–1638 (2004)

    Article  Google Scholar 

  14. Hartley, R., Kahl, F.: Global optimization through searching rotation space and optimal estimation of the essential matrix. In: Proceedings of ICCV (2007)

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

    MATH  Google Scholar 

  16. Jaulin, L., Bazeille, S.: Image shape extraction using interval methods. In: Proceeding of the 16th IFAC Symposium on System, pp. 378–383 (2009)

  17. Jaulin, L., Walter, E.: Guaranteed robust nonlinear minimax estimation. IEEE Trans. Autom. Control 47, 1857–1864 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  18. Jaulin, L., Walter, E., Didrit, O.: Guaranteed robust nonlinear parameter bounding. In: CESA’96 IMACS Multiconference (Symposium on Modelling, Analysis and Simulation), pp. 1156–1161 (1996)

  19. Lai, K., Fox, D.: Object recognition in 3D point clouds using web data and domain adaptation. Int. J. Robot. Res. 29(8), 1019–1037 (2010)

    Article  Google Scholar 

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

    Article  Google Scholar 

  21. Messine, F.: Méthodes d’optimisation globale basées sur l’analyse d’intervalle pour la résolution des problèmes avec contraintes. Ph.D. Thesis, LIMA-IRIT-ENSEEIHT-INPT, Toulouse (1997)

  22. Misener, R., Floudas, C.: ANTIGONE: algorithms for coNTinuous/integer global optimization of nonlinear equations. J. Glob. Optim. (JOGO) 59(2), 503–526 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  23. Moisan, L., Moulon, P., Monasse, P.: Fundamental matrix of a stereo pair, with a contrario elimination of outliers. Image Process. Line 6, 89–113 (2016). https://doi.org/10.5201/ipol.2016.147

    Article  MathSciNet  Google Scholar 

  24. Neveu, B., de la Gorce, M., Trombettoni, G.: Improving a constraint programming approach for parameter estimation. In: 27th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), pp. 852–859 (2015)

  25. Neveu, B., Trombettoni, G., Araya, I.: Adaptive constructive interval disjunction: algorithms and experiments. Constr. J. 20(7), 452–467 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  26. Neveu, B., Trombettoni, G., Araya, I.: Node selection strategies in interval branch and bound algorithms. J. Glob. Optim. 64(2), 289–304 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  27. Ninin, J., Messine, F., Hansen, P.: A reliable affine relaxation method for global optimization. 4OR 13, 1–31 (2014)

    MathSciNet  MATH  Google Scholar 

  28. Nistér, D.: An efficient solution to the five-point relative pose problem. IEEE Trans. Pattern Anal. Mach. Intell. 26(6), 756–770 (2004)

    Article  Google Scholar 

  29. Raguram, R., Chum, O., Pollefeys, M., Matas, J., Frahm, J.M.: Usac: A universal framework for random sample consensus. IEEE Trans. Pattern Anal. Mach. Intell. 35(8), 2022–2238 (2013)

    Article  Google Scholar 

  30. Schnabel, R., Wahl, R., Klein, R.: Efficient RANSAC for point-cloud shape detection. Comput. Graph. Forum 26(2), 214–226 (2007)

    Article  Google Scholar 

  31. Tawarmalani, M., Sahinidis, N.V.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103(2), 225–249 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  32. Trombettoni, G., Araya, I., Neveu, B., Chabert, G.: Inner regions and interval linearizations for global optimization. In: Proceeding AAAI, pp. 99–104 (2011)

  33. Van Hentenryck, P., Michel, L., Deville, Y.: Numerica: A Modeling Language for Global Optimization. MIT Press, Cambridge (1997)

    Book  Google Scholar 

  34. Yang, J., Li, H., Jia, Y.: Optimal essential matrix optimization via inlier-set maximization. In: Proceeding of European Conference of Computer Vision (ECCV), pp. 111–126 (2014)

Download references

Author information

Authors and Affiliations

  1. LIGM, École des Ponts ParisTech, Université Paris–Est, Paris, France

    Bertrand Neveu, Martin de la Gorce & Pascal Monasse

  2. LIRMM, University of Montpellier, CNRS, Montpellier, France

    Gilles Trombettoni

Authors
  1. Bertrand Neveu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Martin de la Gorce
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Pascal Monasse
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Gilles Trombettoni
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Gilles Trombettoni.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Neveu, B., de la Gorce, M., Monasse, P. et al. A generic interval branch and bound algorithm for parameter estimation. J Glob Optim 73, 515–535 (2019). https://doi.org/10.1007/s10898-018-0721-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-018-0721-3

Keywords

Search

Navigation