A Generic Interval Branch and Bound Algorithm for Parameter Estimation

Bertrand Neveu 1, 2, 3 Martin de la Gorce 1, 2 Pascal Monasse 1, 2 Gilles Trombettoni 4
1 ENPC - École des Ponts ParisTech
2 LIGM - Laboratoire d'Informatique Gaspard-Monge
3 IMAGINE [Marne-la-Vallée]
LIGM - Laboratoire d'Informatique Gaspard-Monge, CSTB - Centre Scientifique et Technique du Bâtiment, ENPC - École des Ponts ParisTech
4 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Type de document :
Article dans une revue
Liste complète des métadonnées

Littérature citée [35 références]  Voir  Masquer  Télécharger
https://hal-enpc.archives-ouvertes.fr/hal-01942306
Contributeur : Bertrand Neveu <>
Soumis le : lundi 3 décembre 2018 - 10:15:31
Dernière modification le : mercredi 31 juillet 2019 - 15:02:33
Archivage à long terme le : lundi 4 mars 2019 - 12:56:29

Fichier

bbestim_jogo_2018.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

ENPC | COCONUT | UNIV-MONTPELLIER | CNRS | LIRMM | UPEC-UPEM | PARISTECH | MIPS | IMAGINE | LIGM_A3SI | LIGM

Citation

Bertrand Neveu, Martin de la Gorce, Pascal Monasse, Gilles Trombettoni. A Generic Interval Branch and Bound Algorithm for Parameter Estimation. Journal of Global Optimization, Springer Verlag, 2019, 73 (3), pp.515-535. ⟨10.1007/s10898-018-0721-3⟩. ⟨hal-01942306⟩

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

176

Téléchargements de fichiers

393

Contact

Informations

CCSD