Classification of the perspective-three-point problem, discriminant variety and real solving polynomial systems of inequalities

Jean-Charles Faugère 1 Guillaume Moroz 1 Fabrice Rouillier 1 Mohab Safey El Din 1
1 SALSA - Solvers for Algebraic Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : Classifying the Perspective-Three-Point problem (abbreviated by P3P in the sequel) consists in determining the number of possible positions of a camera with respect to the apparent position of three points. In the case where the three points form an isosceles triangle, we give a full classification of the P3P. This leads to consider a polynomial system of polynomial equations and inequalities with 4 parameters which is generically zero-dimensional. In the present situation, the parameters represent the apparent position of the three points so that solving the problem means determining all the possible numbers of real solutions with respect to the parameters' values and give a sample point for each of these possible numbers. One way for solving such systems consists first in computing a discriminant variety. Then, one has to compute at least one point in each connected component of its real complementary in the parameter's space. The last step consists in specializing the parameters appearing in the initial system by these sample points. Many computational tools may be used for implementing such a general method, starting with the well known Cylindrical Algebraic Decomposition (CAD in short), which provides more information than required. In a first stage, we propose a full algorithm based on the straightforward use of some sophisticated software such as FGb (Grobner bases computations) RS (real roots of zero-dimensional systems), DV (Discriminant varieties) and RAGlib (Critical point methods for semi-algebraic systems). We then improve the global algorithm by refining the required computable mathematical objects and related algorithms and finally provide the classification. Three full days of computation were necessary to get this classification which is obtained from more than 40000 points in the parameter's space.
Type de document :
Communication dans un congrès
ISSAC 2008 - 21st International Symposium on Symbolic and Algebraic Computation, Jul 2008, Hagenberg, Austria. ACM, pp.79-86, 2008, 〈10.1145/1390768.1390782〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01111711
Contributeur : Fabrice Rouillier <>
Soumis le : vendredi 30 janvier 2015 - 18:17:28
Dernière modification le : mardi 17 avril 2018 - 11:24:56

Lien texte intégral

Identifiants

Collections

Citation

Jean-Charles Faugère, Guillaume Moroz, Fabrice Rouillier, Mohab Safey El Din. Classification of the perspective-three-point problem, discriminant variety and real solving polynomial systems of inequalities. ISSAC 2008 - 21st International Symposium on Symbolic and Algebraic Computation, Jul 2008, Hagenberg, Austria. ACM, pp.79-86, 2008, 〈10.1145/1390768.1390782〉. 〈hal-01111711〉

Partager

Métriques

Consultations de la notice

371