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.
Similar content being viewed by others
Notes
Note that this algorithm is heuristic in that it is possible that no such inner polytope is found.
Thanks to Leo Liberti for suggesting the MIP model.
References
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)
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)
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)
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)
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)
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)
Chabert, G., Jaulin, L.: Contractor programming. Artif. Intell. 173, 1079–1100 (2009)
Chew, P., Marzullo, K.: Masking failures of multidimensional sensors. In: Proceeding of Reliable Distributed Systems, pp. 32–41 (1991)
Chin, T.J., Purkait, P., Eriksson, A., Suter, D.: Efficient globally optimal consensus maximisation with tree search. In: Proceeding of CVPR 15 (2015)
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)
Collavizza, H., Delobel, F., Rueher, M.: Comparing partial consistencies. Reliab. Comput. 5(3), 213–228 (1999)
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)
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)
Hartley, R., Kahl, F.: Global optimization through searching rotation space and optimal estimation of the essential matrix. In: Proceedings of ICCV (2007)
Hartley, R., Zisserman, A.: Multiple View Geometry in Computer Vision. Cambridge University Press, Cambridge (2003)
Jaulin, L., Bazeille, S.: Image shape extraction using interval methods. In: Proceeding of the 16th IFAC Symposium on System, pp. 378–383 (2009)
Jaulin, L., Walter, E.: Guaranteed robust nonlinear minimax estimation. IEEE Trans. Autom. Control 47, 1857–1864 (2002)
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)
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)
Longuet-Higgins, H.C.: A computer algorithm for reconstructing a scene from two projections. Nature 293(5828), 133–135 (1981)
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)
Misener, R., Floudas, C.: ANTIGONE: algorithms for coNTinuous/integer global optimization of nonlinear equations. J. Glob. Optim. (JOGO) 59(2), 503–526 (2014)
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
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)
Neveu, B., Trombettoni, G., Araya, I.: Adaptive constructive interval disjunction: algorithms and experiments. Constr. J. 20(7), 452–467 (2015)
Neveu, B., Trombettoni, G., Araya, I.: Node selection strategies in interval branch and bound algorithms. J. Glob. Optim. 64(2), 289–304 (2016)
Ninin, J., Messine, F., Hansen, P.: A reliable affine relaxation method for global optimization. 4OR 13, 1–31 (2014)
Nistér, D.: An efficient solution to the five-point relative pose problem. IEEE Trans. Pattern Anal. Mach. Intell. 26(6), 756–770 (2004)
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)
Schnabel, R., Wahl, R., Klein, R.: Efficient RANSAC for point-cloud shape detection. Comput. Graph. Forum 26(2), 214–226 (2007)
Tawarmalani, M., Sahinidis, N.V.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103(2), 225–249 (2005)
Trombettoni, G., Araya, I., Neveu, B., Chabert, G.: Inner regions and interval linearizations for global optimization. In: Proceeding AAAI, pp. 99–104 (2011)
Van Hentenryck, P., Michel, L., Deville, Y.: Numerica: A Modeling Language for Global Optimization. MIT Press, Cambridge (1997)
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)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
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
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-018-0721-3