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

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, Buchanan (1992a, 1992b) 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 (² lines). In general these sets are algorithm dependent, for example the critical set of lines for the Liu-Huang algorithm introduced in (Buchanan, 1992a), 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 (Liu and Huang, 1988a, 1988b). 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.