Improving a Constraint Programming Approach for Parameter Estimation

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. Calibration or geolocation can be viewed as specific parameter estimation problems. In this paper we address the problem of finding all the instances of a parametric model that can explain at least q observations within a given tolerance. 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. proposes a complete and combinatorial algorithm that exhaustively traverses the whole space of parameter vectors to extract the valid model instances. This algorithm is based on interval constraint programming methods and on a so called q-intersection operator, a relaxed intersection operator that assumes that at least q observed data are inliers. This paper proposes several improvements to Jaulin et al.'s algorithm. Most of them are generic and some others are dedicated to the shape detection problem used to validate our approach. Compared to Jaulin et al.'s algorithm, our algorithm can guarantee a number of fitted observations in the produced model instances. Also, first experiments in plane and circle recognition highlight speedups of two orders of magnitude.