An Interval Branch and Bound Algorithm for Parameter Estimation

Bertrand Neveu 1, 2, 3 Martin De La Gorce 2, 1, 3 Gilles Trombettoni 4
1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 ENPC - École des Ponts ParisTech
3 IMAGINE [Marne-la-Vallée]
CSTB - Centre Scientifique et Technique du Bâtiment, LIGM - Laboratoire d'Informatique Gaspard-Monge, ENPC - École des Ponts ParisTech
4 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The parameter estimation problem is a widespread and challenging problem in engineering sciences consisting in computing the parameters of a parametric model that fit observed data. The computer vision community has proposed the RANSAC algorithm to deal with outliers in the observed data. This randomized algorithm is efficient but non-deterministic and therefore incomplete. Jaulin et al. propose a branch-and-contract algorithm that returns all the model instances fitting at least q observations. Assuming that at least q observed data are inliers, this algorithm achieves on the observations a relaxed intersection operator called q-intersection. First, this paper presents several improvements to Jaulin et al.'s algorithm. Second, an interval branch and bound algorithm is designed to produce a model that can explain the maximum number of observations within a given tolerance. Experiments are carried out on computer vision and image processing problems. They highlight a significant speedup w.r.t. Jaulin et al.'s interval method in 2D and 3D shape recognition problems. We have also investigated how the approach scales up in dimensions up to 7 for stereovision (estimation of essential and fundamental matrices).
Keywords : Interval branch and bound Shape detection Parameter estimation
Type de document :
Communication dans un congrès
GOW: Globla Optimization Workshop, Sep 2016, Braga, Portugal. 13th Globla Optimization Workshop, 2016, 〈http://apolo.dps.uminho.pt/gow16/〉
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger
https://hal-enpc.archives-ouvertes.fr/hal-01376601
Contributeur : Bertrand Neveu <>
Soumis le : mercredi 5 octobre 2016 - 12:22:58
Dernière modification le : lundi 15 octobre 2018 - 14:00:37
Document(s) archivé(s) le : vendredi 6 janvier 2017 - 13:22:43

Fichier

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

Identifiants

  • HAL Id : hal-01376601, version 1

Collections

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

Citation

Bertrand Neveu, Martin De La Gorce, Gilles Trombettoni. An Interval Branch and Bound Algorithm for Parameter Estimation. GOW: Globla Optimization Workshop, Sep 2016, Braga, Portugal. 13th Globla Optimization Workshop, 2016, 〈http://apolo.dps.uminho.pt/gow16/〉. 〈hal-01376601〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

373

Téléchargements de fichiers

165

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD