147x Filetype PDF File size 0.58 MB Source: openaccess.thecvf.com
Trinocular Geometry Revisited Jean Ponce∗ Martial Hebert ´ Ecole normale superieure Carnegie-Mellon University Abstract x δδ x y3 τ ξ3 ξ3 cc c c 3 3 3 Whendothevisual rays associated with triplets of point ξ ξξ11 ξξ2 yy33 ξξ11 ξξ2 yy33 3 correspondences converge, that is, intersect in a common π δ 3 3 ξ point? Classical models of trinocular geometry based on 1 c1 c2 c1 c2 ξ c the fundamental matrices and trifocal tensor associated δ cc 2 2 π y y 1 y1 11 1 1 π 2 δ y2 2 2 y2 with the corresponding cameras only provide partial an- y1 swers to this fundamental question, in large part because of Figure 1. Left: Visual rays associated with three (correct) corre- underlying, but seldom explicit, general configuration as- spondences. Right: Degenerate epipolar constraints associated sumptions. This paper uses elementary tools from projec- with three coplanar, but non-intersecting rays lying in the trifo- tive line geometry to provide necessary and sufficient geo- cal plane τ (as in the rest of this presentation, the image planes are metric and analytical conditions for convergence in terms omitted for clarity in this part of the figure). See text for details. of transversals to triplets of visual rays, without any such assumptions. In turn, this yields a novel and simple min- each other, since rays that satisfy epipolar constraints do imal parameterization of trinocular geometry for cameras not always converge, but they are true under some general with non-collinear or collinear pinholes. configuration assumptions, rarely made explicit. It is thus worth clarifying these assumptions, and understanding ex- 1. Introduction actly how much the trifocal constraints add to the epipolar ones for point correspondences. This is the problem ad- Theimagesofpoints recorded by multiple cameras may dressed in this paper, using elementary projective line ge- only match when the corresponding visual rays converge— ometry. In particular, our analysis shows that exploiting that is, intersect in a common point (Figure 1, left). For two both the epipolar constraints and one or two of the trinoc- views, this condition is captured by the bilinear epipolar ular ones, depending on whether the camera pinholes are constraint and the corresponding fundamental matrix [8, 9]. collinear or not, always guarantees the convergence of the Three images can be characterized by both the pairwise corresponding visual rays. Our analysis also provides, in epipolar constraints associated with any two of the pic- both cases, a novel and simple minimal parameterization of tures, and a set of trilinearities associated with all three trinocular geometry. views and parameterized by the associated trifocal ten- 1.1. Related Work sor [5, 15, 16, 22]. For cameras with non-collinear pin- holes, at least, the rays associated with three image points Geometric constraints involving multiple perspective that satisfy the corresponding epipolar constraints almost views of the same point (Figure 1, left) have been stud- always converge: The only exception is when the points ied in computer vision since the seminal work of Longuet- have been matched incorrectly, and all lie in the trifocal Higgins, who proposed in 1981 the essential matrix as a bi- plane spanned by the three pinholes (Figure 1, right). Inter- linear model of epipolar constraints between two calibrated estingly, Hartley and Zisserman state that the fundamental cameras [8]. Its uncalibrated counterpart, the fundamental matrices associated with three cameras with non-collinear matrix, was introduced by Luong and Faugeras [9]. The tri- pinholes determine the corresponding trifocal tensor [6, Re- linear constraints associated with three views of a straight sult 14.5], while Faugeras and Mourrain [3] and Ponce et line were discovered by Spetsakis and Aloimonos [16] and al. [12], for example, note that the rays associated with three byWeng,HuangandAhuja[22]. Theuncalibratedcasewas points only satisfying certain (and different) subsets of the tackled by Shashua [15] and by Hartley [5], who coined the trilinearities alone must intersect. These claims contradict term trifocal tensor. The quadrifocal tensor was introduced ∗Willow project team. DI/ENS, ENS/CNRS/INRIA UMR 8548. by Triggs [20], and Faugeras and Mourrain gave a sim- 1 1.2. Problem Statement and Proposed Approach As noted earlier, the goal of this paper is to understand exactly how much the trifocal constraints add to the epipo- lar ones for point correspondences. Since both types of constraints model incidence relationships among the light rays joining the cameras’ pinholes to observed points, we address this problem using the tools of projective geome- try [21] in general, and line geometry [13] in particular. As (3) (4) (5) (6) (1) (2) noted earlier, the trifocal tensor was originally invented to characterize the fact that three image lines δ1, δ2, and δ3 are the projections of the same scene line δ [15, 16, 22] (Figure 1, left). The trilinearities associated with three im- age points y1, y2, and y3 were then obtained by construct- ing lines δ1, δ2, and δ3 passing through these points, and whosepreimageisalineδ passing through the correspond- ing scene point x. By construction, this line is a transversal to the three rays ξ1, ξ2, and ξ3, that is, it intersects them. It Figure 2. Top: The possible configurations of three pairwise- is therefore not surprising that much of the presentation will coplanar distinct lines, classified according to the way they inter- bededicatedtothecharacterizationofthesetoftransversals sect. The three given lines are shown in black; the planes where to a triplet of lines. two of them intersect are shown in green; and the points where In particular, we have already seen that the fact that three two of the lines intersect are shown in red. Bottom: Transversals lines intersect pairwise is necessary, but not sufficient for to the three lines, shown in blue, and forming (1) a line bundle; (2) these lines to intersect. We will show in the rest of this pre- a degenerate congruence; and (3) a line field. sentation that a necessary and sufficient condition for three ple characterization of all multilinear constraints associated lines to converge is in fact that they be pairwise coplanar with multiple perspective images of a point [3]. The usual and admit a well defined family of transversals. We will formulation of the trilinear constraints associated with three also give a simple geometric and analytical characterization imagesofthesamepointareasymmetric,oneoftheimages of these transversals under various assumptions. When ap- playing a priviledged role. A simple and symmetric formu- plied to camera systems, it will provide in turn a new and lation based on line geometry was introduced in [12]. A few simple minimal parameterization of trinocular geometry. minimal parameterizations of trinocular geometry are also Contributions available[1,11,14,19]. Fromahistoricalpointofview,itis • We give a new geometric characterization of triplets of worth noting that epipolar constraints were already known converging lines in terms of transversals to these lines by photogrammeters long before they were (re)discovered (Proposition 1). by Longuet-Higgins [8], as witnessed by the 1966 Manual •Weprovideanovelandsimpleanalyticalcharacterization of Photogrammetry [17], but that this book does not men- of triplets of converging lines (Lemma 3 and Proposition 2), tion trilinear constraints, although it discusses higher-order that does not rely on the assumptions of general configura- trinocular (scale-restraint condition equations). tion implicit in [12]. • We show by applying these results to camera geometry Thedirect derivation of trifocal constraints for point cor- that the three epipolar constraints and one of the trifocal respondences typically amounts to writing that all 4×4 mi- ones (two if the pinholes are collinear) are necessary and nors of some k × 4 matrix are zero, thus guaranteeing that sufficient for the corresponding optical rays to converge the three lines intersect [3, 12]. These determinants are then (Propositions 3 and 4). rewritten as linear combinations of reduced minors that are • Weintroduce a new analytical parameterization of epipo- bilinearortrilinearfunctionsoftheimagepointcoordinates. lar and trifocal constraints, leading to a minimal parameter- The whole difficulty lies in selecting an appropriate subset ization of trinocular geometry (Propositions 5 and 6). of reduced minors that will always guarantee that the rays 2. Converging Triplets of Lines intersect. We have already observed that the bilinear epipo- lar constraints, alone, are not sufficient. We are not aware 2.1. Geometric Point of View of any fixed set of four trilinearities that, alone, guarantee convergence in all cases. This suggests seeking instead ap- All lines considered from now on are assumed to be dif- propriate combinations of bilinear and trilinear constraints, ferent from each other. A transversal to some family of which is the approach taken in this presentation. lines is a line intersecting every element of this family. We independenceoflinesmatchestheusualalgebraicdefinition of linear independence, in which, given a coordinate sys- tem, a necessary and sufficient for k lines to be linearly de- pendent is that some nontrivial linear combination of their ¨ Pluckercoordinatevectors(Section2.2.1)bethezerovector of R6. Geometrically, the lines linearly dependent on three skew lines form a regulus [21]. A regulus is either a line (3) (4) (5) (6) field, formed by all lines in a plane; a line bundle, formed (1) (2) by all lines passing through some point; the union of all lines belonging to two flat pencils lying in different planes but sharing one line; or a non-degenerate regulus formed by oneofthetwosetsoflinesrulingahyperboloidofonesheet or a hyperbolic paraboloid. Linear (in)dependence of four or more lines can be defined recursively. Armed with these definitions, we obtain an important corollary of Lemma 1. Figure 3. Top: The possible configurations of three distinct, non- Lemma2. Three distinct lines always admit an infinity of pairwise-coplanar lines, classified according to the way they in- transversals, that can be found in exactly six configurations tersect. Bottom: Transversals to the three lines, forming (4) two (Figures 2 and 3, bottom): (1) the transversals form a bun- pencils of lines having one of the input lines (in black) in common dle of lines; (2) they form a degenerate congruence consist- (5) two pencils of lines having one line (in red) in common; and ing of a line field and of a bundle of lines; (3) they form a (6) a non-degenerate regulus. See text for details. line field; (4) they form two pencils of lines having one of prove in this section the following main result. the input lines in common; (5) they form two pencils of lines having a line passing through the intersection of two of the Proposition 1. A necessary and sufficient condition for input lines in common; or (6) they form a non-degenerate three lines to converge is that they be pairwise coplanar, regulus, with the three input lines in the same ruling, and andthattheyadmitatransversalnotcontainedintheplanes the transversals in the other one. defined by any two of them. To prove Proposition 1, we need two intermediate re- Lemma 2 should not come as a surprise since the sults. In projective geometry, two straight lines are either transversals to three given lines satisfy three linear con- skew to each other or coplanar, in which case they inter- straints and thus form in general a rank-3 family (the de- sect in exactly one point. Our first lemma enumerates the generate congruence is a rank-4 exception [21]). Without possible incidence relationships among three lines. additional assumptions, not much more can be said in gen- eral, since Lemma 2 tells us that any three distinct lines Lemma1. Three distinct lines can be found in exactly six admit an infinity of transversals. When the lines are, in ad- configurations (Figures 2 and 3, top): (1) the three lines are dition, pairwise coplanar, cases 4 to 6 in Lemmma 2 are not all coplanar and intersect in exactly one point; (2) they eliminated, and we obtain Proposition 1 as an immediate are coplanar and intersect in exactly one point; (3) they are corollary of this lemma. coplanarandintersectpairwiseinthreedifferentpoints; (4) 2.2. The Analytical Point of View exactly two pairs of them are coplanar (or, equivalently, in- tersect); (5) exactly two of them are coplanar; or (6) they 2.2.1 Preliminaries are pairwise skew. To translate the geometric results of the previous section The proof is by enumeration. Lemma 1 has an immedi- into analytical ones, it is necessary to recall a few basic ate, important corrolary—that is, when three lines are pair- facts about projective geometry in general, and line geome- ¨ wise coplanar, either they are not coplanar and intersect in try in particular. Readers familiar with Plucker coordinates, one point (case 1); they are coplanar and intersect in one the join operator, etc., may safely proceed to Section 2.2.2. point (case 2); or they are coplanar, and intersect pairwise Given some choice of coordinate system for some two- 2 2 in three different points (case 3). In particular, epipolar dimensional projective space P , points and lines in P can constraints are satisfied for triplets of (incorrect) correspon- be identified with their homogeneous coordinate vectors in dencesassociatedwithimagesofpointsinthetrifocalplane R3. In addition, if x and y are two distinct points on a line containing the pinholes of three non-collinear cameras. ξ in P2, we have ξ = x × y. A necessary and sufficient To go further, it is useful to introduce a notion of linear condition for a point x to lie on a line ξ is ξ · x = 0, and (in)dependence among lines. The geometric definition of two lines intersect in exactly one point or coincide. A nec- essary and sufficient conditions for three lines to intersect is lines ξ = (ξ1j,...,ξ6j)T (j = 1,2,3) and define j that they be linearly dependent, or Det(ξ1,ξ2,ξ3) = 0. ξ ξ ξ In three dimensions, given any choice of coordinate sys- i1 i2 i3 3 D = ξ ξ ξ (3) tem for a three-dimensional projective space P , we can ijk j1 j2 j3 3 ξ ξ ξ ¨ k1 k2 k3 identify any line in P with its Plucker coordinate vector ξ = (u;v) in R6, where u and v are vectors of R3, and we use a semicolon to indicate that the coordinates of u and v to be the 3 × 3 minor of the 6 × 3 matrix [ξ1,ξ2,ξ3] cor- have been stacked onto each other to form a vector in R6. responding to its rows i, j, and k. A necessary and suffi- In addition, if x and y are two distinct points on some line cient condition for this matrix to have rank 2, and thus for ξ = (u;v) in P3, we have the three lines to form a flat pencil (Section 2.1), is that all the minors T = D , T = D , T = D , and 0 456 1 234 2 315 " # " # T =D beequaltozero. x y −x y x y −x y 3 126 4 1 1 4 2 3 3 2 u= x y −x y , and v= x y −x y . (1) 4 2 2 4 3 1 1 3 Lemma 3. Given some integer j in {0,1,2,3}, a neces- x y −x y x y −x y 4 3 3 4 1 2 2 1 sary and sufficient condition for ξ , ξ , and ξ to admit a 1 2 3 transversal passing through x is that T = 0. ¨ j j A Plucker coordinate vector is only defined up to scale, and its u and v components are by construction orthoganal Proof. Let us prove the result in the case j = 0. The to each other—this is sometimes known as the Klein con- proofs for the other cases are similarA necessary and suf- straint u · v = 0. Let us consider the symmetric bilinear ficient condition for a line δ = (u;v) to pass through x is form R6 × R6 → R associating with two elements λ = 0 that v = 0 (this follows from the form of the join matrix). (a;b)andµ = (c;d)ofR6 thescalar(λ|µ) = a·d+b·c. Thus a necessary and sufficient condition for the existence Anecessary and sufficient for a nonzero vector ξ in R6 to of a line δ passing through x and intersecting the lines represent a line is that (ξ|ξ) = 0, and a necessary and suf- 0 ficient condition for two lines λ and µ to be coplanar (or, ξj = (uj;vj) is that there exists a vector u 6= 0 such that equivalently, to intersect) is that (λ|µ) = 0. (ξj|δ) = vj · u = 0 for j = 1,2,3, or, equivalently, that the determinant T = D =|v ,v ,v |bezero. 0 456 1 2 3 Let us denote the basis points of some arbitrary pro- jective coordinate system by x to x , with coordinates Combining Proposition 2 and Lemma 3 now yields the 0 4 T T T following important result. x0 = (0,0,0,1) , x1 = (1,0,0,0) , x2 = (0,1,0,0) , T T x = (0,0,1,0) , and x = (1,1,1,1) . Points x to 3 4 0 Proposition 2. A necessary and sufficient condition for x3 are called the fundamental points. The point x4 is the three lines ξ , ξ , and ξ to converge is that (ξ |ξ ) = 0 for unit point. Let us also define four fundamental planes pj 1 2 3 i j all i 6= j in {1,2,3}, and that T = 0forallj in{0,1,2,3}. (j = 0,1,2,3) whose coordinate vectors are the same as j those of the fundamental points. The unique line joining Proof. Theconditionisclearlynecessary. Toshowthatisis two distinct points is called the join of these points and it is sufficient, note that since the three lines are pairwise copla- denoted by x ∨ y. Likewise, the unique plane defined by a nar, they either intersect in exactly one point (cases 1 and line ξ = (u;v) and some point x not lying on this line is 2 of Lemma 2), or are all coplanar, intersecting pairwise in called the join of ξ and x, and it is denoted by ξ ∨ x. Al- three distinct points, with all their transversals in the same gebraically, we have ξ ∨ x = [ξ∨]x, where [ξ∨] is the join plane (case 3). But the latter case is ruled out by Lemma 3 matrix defined by and the condition T = 0 for j = 0,1,2,3 since the funda- j [u ] v mentalpointsxj arebyconstructionnotallcoplanar, andat [ξ ] = × . (2) least one of them (and thus the corresponding transversal) ∨ −vT 0 does not lie in the plane containing the three lines. Anecessary and sufficient condition for a point x to lie on 3. Converging Triplets of Visual Rays a line ξ is that ξ ∨ x = 0. 3.1. Bilinearities or Trilinearities? 2.2.2 BacktoTransversals Let us now turn our attention from general systems of lines to the visual rays associated with three cameras. As Letustranslate some of the geometric incidence constraints noted earlier, it follows from Lemma 1 that the epipolar derived in the previous section into algebraic ones. We constraints alone do not ensure that the corresponding view- assume that some projective coordinate system is given, ing rays intersect (Figure 1, right). On the other hand, the and identify points, planes, and lines with their homoge- only case where they do not is when the corresponding rays neous coordinate vectors. Let us consider three distinct lie in the trifocal plane when the camera pinholes are not
no reviews yet
Please Login to review.