The Critical Sets of Lines for Camera Displacement Estimation : A Mixed Euclidean-Projective and Constructive Approach

Nassir Navab 1 Olivier Faugeras
1 ROBOTVIS - Computer Vision and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : The problem of the recovery of the motion, and the structure from motion is relevant to many computer vision applications. Many algorithms have been proposed to solve this problem. Some of these use line correspondences. For obvious practical reasons, it is important to study the limitation of such algorithms. In this paper, we are concerned with the problem of recovering the relative displacements of a camera by using line matches in three views. In particular we want to know whether there exist sets of 3D lines such that no matter how many lines we observe there will always be several solutions to the relative displacement estimation problem. Such sets of lines may be called critical in the sense that they defeat the corresponding algorithm. This question has been studied in detail in the case of point matches by early-century Austrian photogrammeters and, independently, in the mid-seventies and early-eighties by computer vision scientists. The answer lies in the idea of a critical surface. The case of lines has been much less studied. Recently, Thomas Buchanan \citeBuc92,Buc92a provided a first analysis of the problem in which he gave a positive answer: there exist critical sets of lines and they are pretty big ($\infty^2$ lines). In general these sets are algorithm dependent, for example the critical set of lines for the Liu-Huang algorithm introduced in \citeBuc92, but Buchanan has shown that there is a critical set that defeats any algorithm. This paper is an attempt to build on his work and extend it in several directions. First, we cast his purely projective analysis in a more euclidean framework better suited to applications and, currently, more familiar to most of the computer vision community. Second, we clearly relate his critical set to those of previously published algorithms, in particular \citeLH88a,LH88b. Third, we provide an effective, i.e. computational, approach for describing these critical sets in terms of simple geometric properties. This has allowed us to scrutinize the structure of the critical sets which we found to be both intricate and beautiful.
Type de document :
RR-2305, INRIA. 1994
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 15:09:46
Dernière modification le : jeudi 11 janvier 2018 - 16:41:43
Document(s) archivé(s) le : mardi 12 avril 2011 - 16:44:44



  • HAL Id : inria-00074368, version 1



Nassir Navab, Olivier Faugeras. The Critical Sets of Lines for Camera Displacement Estimation : A Mixed Euclidean-Projective and Constructive Approach. RR-2305, INRIA. 1994. 〈inria-00074368〉



Consultations de la notice


Téléchargements de fichiers