Filetype PDF | Posted on 25 Jan 2023 | 2 years ago
Authentication
digital resources
154x 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.
