An Interval Branch and Bound Algorithm for Parameter Estimation - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

An Interval Branch and Bound Algorithm for Parameter Estimation

(1, 2, 3) , (2, 1, 3) , (4)


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).
Fichier principal
Vignette du fichier
gow16.pdf (315.01 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01376601 , version 1 (05-10-2016)


  • HAL Id : hal-01376601 , version 1


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. ⟨hal-01376601⟩
300 Consultations
213 Téléchargements


Gmail Facebook Twitter LinkedIn More