Project : coprin
Section: New Results
Keywords : rigidity , geometric decomposition , systems decomposition , computer vision .
Resolution of geometrical constraints systems by rigidity, consistency and interval analysis
Solving geometric constraints with recursive rigidification and interval analysis
Participants : Christophe Jermann, Bertrand Neveu, Gilles Trombettoni.
Geometric constraint satisfaction problems (GCSPs) are ubiquitous in applications like CAD, robotics or molecular biology [5] [3] [11]. They consist in searching positions, orientations and dimensions of geometric objects bound by geometric constraints. The goal of the thesis [12] was to find an efficient and complete solving method for GCSPs.
We have compared solving methods and decomposition techniques, and we have focused on Hoffmann's decomposition and interval solving methods. We define a general framework for the study of rigidity in GCSPs, a concept used in all the geometric decomposition methods [3].
Hoffmann's method has limits inherent to all the structural geometric approaches. We propose the degree of rigidity concept to overcome some of these limits together with a new decomposition and its combination with interval solving techniques [22] [24] [23].
Scene Modeling Based on Constraint System Decomposition Techniques
Participants : Gilles Trombettoni, Christophe Jermann.
This work is performed in collaboration with Marta Wilczkowiak from the MOVI project at INRIA Rhônes-Alpes. Marta Wilczkowiak's PhD thesis is supervised by Edmond Boyer and Peter Sturm.
We present a new approach to 3D scene modeling based on geometric constraints [37] [38]. Contrary to the existing methods, we can quickly obtain 3D scene models that respect the given constraints exactly. Our system can handle a large variety of linear and non-linear constraints in a flexible way.
To deal with the constraints, we decided to exploit the properties of the GPDOF algorithm developed by Trombettoni [11]. The approach is based on a dictionary of so-called r-methods, relying on geometry theorems, which can solve a subset of geometric constraints in a very efficient way. GPDOF is used to find, in polynomial-time, a reduced parameterization of a scene, and to decompose the equation system induced by constraints into a sequence of r-methods. We have validated our approach in reconstructing 3D models of building from images, using linear and quadratic geometric constraints.
Solving decomposable systems by Inter Block Backtracking
Participants : Christophe Jermann, Bertrand Neveu, Gilles Trombettoni.
We have studied a technique, called inter-block backtracking (IBB), which improves the solving by interval techniques of decomposed systems of non-linear equations over the reals [23].
This approach, introduced in 1998 by Bliek, Neveu and Trombettoni [1], handles a system of equations previously decomposed into a set of (small) sub-systems, called blocks. A solution is obtained by combining the solutions computed in the different blocks. The approach seems particularly suitable for improving interval solving techniques.
In this paper, we analyze into the details the different variants of IBB which differ in their backtracking and filtering strategies. We also introduce IBB-GBJ, a new variant based on Dechter's graph-based back-jumping.
An extensive comparison on a sample of 8 CSPs has allowed us to better understand the behavior of IBB. In particular, we clearly show that limiting the scope of the filtering to the current block is very fruitful. For all the tested instances, IBB efficiency is larger by several orders of magnitude as compared to global solving.
