jagomart
digital resources
picture1_Geometry Pdf 166984 | Ponce Trinocular Geometry Revisited 2014 Cvpr Paper


 147x       Filetype PDF       File size 0.58 MB       Source: openaccess.thecvf.com


File: Geometry Pdf 166984 | Ponce Trinocular Geometry Revisited 2014 Cvpr Paper
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 ...

icon picture PDF Filetype PDF | Posted on 25 Jan 2023 | 2 years ago
Partial capture of text on file.
                                                          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
The words contained in this file might help you see if this file matches what you are looking for:

...Trinocular geometry revisited jean ponce martial hebert ecole normale superieure carnegie mellon university abstract x y cc c whendothevisual rays associated with triplets of point yy correspondences converge that is intersect in a common classical models based on the fundamental matrices and trifocal tensor corresponding cameras only provide partial an swers to this question large part because figure left visual three correct corre underlying but seldom explicit general conguration as spondences right degenerate epipolar constraints sumptions paper uses elementary tools from projec coplanar non intersecting lying trifo tive line necessary sufcient geo cal plane rest presentation image planes are metric analytical conditions for convergence terms omitted clarity gure see text details transversals without any such assumptions turn yields novel simple min each other since satisfy do imal parameterization not always they true under some collinear or pinholes rarely made it thus worth clar...

no reviews yet
Please Login to review.