A generic interval branch and bound algorithm for parameter estimation. (English) Zbl 1420.90050
Summary: 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.
MSC:
| 90C26 | Nonconvex programming, global optimization |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
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) · Zbl 1312.90057 · doi:10.1007/s10898-014-0145-7 |
| [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) · doi:10.5772/54656 |
| [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) · Zbl 1191.68628 · doi:10.1016/j.artint.2009.03.002 |
| [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) · doi:10.1109/TPAMI.2016.2631531 |
| [11] | Collavizza, H., Delobel, F., Rueher, M.: Comparing partial consistencies. Reliab. Comput. 5(3), 213-228 (1999) · Zbl 1130.65310 · doi:10.1023/A:1009922003700 |
| [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) · doi:10.1145/358669.358692 |
| [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) · doi:10.1109/TPAMI.2004.125 |
| [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) · Zbl 0956.68149 |
| [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) · Zbl 1364.93161 · doi:10.1109/TAC.2002.804479 |
| [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) · doi:10.1177/0278364910369190 |
| [20] | Longuet-Higgins, H.C.: A computer algorithm for reconstructing a scene from two projections. Nature 293(5828), 133-135 (1981) · doi:10.1038/293133a0 |
| [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) · Zbl 1301.90063 · doi:10.1007/s10898-014-0166-2 |
| [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 · doi:10.5201/ipol.2016.147 |
| [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) · Zbl 1329.90152 · doi:10.1007/s10601-015-9180-3 |
| [26] | Neveu, B., Trombettoni, G., Araya, I.: Node selection strategies in interval branch and bound algorithms. J. Glob. Optim. 64(2), 289-304 (2016) · Zbl 1339.90268 · doi:10.1007/s10898-015-0375-3 |
| [27] | Ninin, J., Messine, F., Hansen, P.: A reliable affine relaxation method for global optimization. 4OR 13, 1-31 (2014) · Zbl 1320.90065 |
| [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) · doi:10.1109/TPAMI.2004.17 |
| [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) · doi:10.1109/TPAMI.2012.257 |
| [30] | Schnabel, R., Wahl, R., Klein, R.: Efficient RANSAC for point-cloud shape detection. Comput. Graph. Forum 26(2), 214-226 (2007) · doi:10.1111/j.1467-8659.2007.01016.x |
| [31] | Tawarmalani, M., Sahinidis, N.V.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103(2), 225-249 (2005) · Zbl 1099.90047 · doi:10.1007/s10107-005-0581-8 |
| [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) |
| [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) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
