Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 1/43
Chapter 6
Reconstruction from Multiple Views
Multiple View Geometry
Summer 2021
Prof. Daniel Cremers
Chair for Computer Vision and Artificial Intelligence
Departments of Informatics & Mathematics
Technical University of Munich
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 2/43
Overview
1 From Two Views to Multiple Views
2 Preimage & Coimage from Multiple Views
3 From Preimages to Rank Constraints
4 Geometric Interpretation
5 The Multiple-view Matrix
6 Relation to Epipolar Constraints
7 Multiple-View Reconstruction Algorithms
8 Multiple-View Reconstruction of Lines
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 3/43
Multiple-View Geometry
In this section, we deal with the problem of 3D reconstruction
given multiple views of a static scene, either obtained
simultaneously, or sequentially from a moving camera.
The key idea is that the three-view scenario allows to obtain
more measurements to infer the same number of 3D
coordinates. For example, given two views of a single 3D point,
we have four measurements (x- and y-coordinate in each
view), while the three-view case provides 6 measurements per
point correspondence. As a consequence, the estimation of
motion and structure will generally be more constrained when
reverting to additional views.
The three-view case has traditionally been addressed by the
so-called trifocal tensor [Hartley ’95, Vieville ’93] which
generalizes the fundamental matrix. This tensor – as the
fundamental matrix – does not depend on the scene structure
but rather on the inter-frame camera motion. It captures a
trilinear relationship between three views of the same 3D point
or line [Liu, Huang ’86, Spetsakis, Aloimonos ’87].
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 4/43
Trifocal Tensor versus Multiview Matrices
Traditionally the trilinear relations were captured by
generalizing the concept of the Fundamental Matrix to that of a
Trifocal Tensor. It was developed among others by [Liu and
Huang ’86], [Spetsakis, Aloimonos ’87]. The use of tensors
was promoted by [Vieville ’93] and [Hartley ’95]. Bilinear,
trilinear and quadrilinear constraints were formulated in [Triggs
’95]. This line of work is summarized in the books:
Faugeras and Luong, “The Geometry of Multiple Views”, 2001
and
Hartley and Zisserman, “Multiple View Geometry”, 2001, 2003.
In the following, however, we stick with a matrix notation for the
multiview scenario. This approach makes use of matrices and
rank constraints on these matrices to impose the constraints
from multiple views. Such rank constraints were used by many
authors, among others in [Triggs ’95] and in [Heyden, Åström
’97]. This line of work is summarized in the book
Ma, Soatto, Kosecka, Sastry, “An Invitation to 3D Vision”, 2004.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 5/43
Preimage from Multiple Views
A preimage of multiple images of a point or a line is the
(largest) set of 3D points that gives rise to the same set of
multiple images of the point or the line.
For example, given the two images `1 and `2 of a line L, the
preimage of these two images is the intersection of the planes
P1 and P2, i.e. exactly the 3D line L = P1 ∩ P2.
In general, the preimage of multiple images of points and lines
can be defined by the intersection:
preimage(x1, . . . ,xm) = preimage(x1) ∩ · · · ∩ preimage(xm),
preimage(`1, . . . , `m) = preimage(`1) ∩ · · · ∩ preimage(`m).
The above definition allows us to compute preimages for any
set of image points or lines. The preimage of multiple image
lines, for example, can be either an empty set, a point, a line or
a plane, depending on whether or not they come from the
same line in space.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 6/43
Preimage and Coimage of Points and Lines
Images of a point p on a line L:
• Preimages P1 and P2 of the image lines should intersect in
the line L.
• Preimages of the two image points x1 and x2 should
intersect in the point p.
• Normals `1 and `2 define the coimages of the line L.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 7/43
Preimage and Coimage of Points and Lines
For a moving camera at time t , let x(t) denote the image
coordinates of a 3D point X in homogeneous coordinates:
λ(t)x(t) = K (t)Π0g(t)X ,
where λ(t) denotes the depth of the point, K (t) denotes the
intrinsic parameters, Π0 the generic projection, and
g(t) =
(
R(t) T (t)
0 1
)
∈ SE(3),
denotes the rigid body motion at time t .
Let us consider a 3D line L in homogeneous coordinates:
L = {X | X = X 0 + µV , µ ∈ R} ⊂ R4,
where X 0 = [X0,Y0,Z0,1]> ∈ R4 are the coordinates of the
base point p0 and V = [V1,V2,V3,0]> ∈ R4 is a nonzero vector
indicating the line direction.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 8/43
Preimage and Coimage of Points and Lines
The preimage of L with respect to the image at time t is a plane
P with normal `(t), where P = span(ˆ̀). The vector `(t) is
orthogonal to all points x(t) of the line:
`(t)>x(t) = `(t)>K (t)Π0g(t)X = 0.
Assume we are given a set of m images at times t1, . . . , tm
where
λi = λ(ti ), x i = x(ti ), `i = `(ti ), Πi = K (ti )Π0g(ti ).
With this notation, we can relate the i-th image of a point p to
its world coordinates X :
λix i = ΠiX ,
and the i-th coimage of a line L to its world coordinates (X 0,V ):
`>i ΠiX 0 = `
>
i ΠiV = 0.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 9/43
From Preimages to Rank Constraints
The above equations contain the 3D parameters of points and
lines as unknowns. As in the two-view case, we wish to
eliminate these unknowns so as to obtain relationships
between the 2D projections and the camera parameters.
In the two-view case an elimination of the 3D coordinates lead
to the epipolar constraint for the essential matrix E or (in the
uncalibrated case) the fundamental matrix F . The 3D
coordinates (depth values λi associated with each point) could
subsequently obtained from another constraint.
There exist different ways to eliminate the 3D parameters
leading to different kinds of constraints which have been
studied in Computer Vision.
A systematic elimination of these constraints will lead to a
complete set of conditions.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 10/43
Point Features
Consider images of a 3D point X seen in multiple views:
I~λ ≡
x1 0 · · · 0
0 x2 0 0
…
…
. . .
…
0 0 · · · xm
λ1
λ2
…
λm
=
Π1
Π2
…
Πm
X ≡ ΠX ,
which is of the form
I~λ = ΠX ,
where ~λ ∈ Rm is the depth scale vector, and Π ∈ R3m×4 the
multiple-view projection matrix associated with the image
matrix I ∈ R3m×m.
Note that apart from the 2D coordinates I, everything else in
the above equations is unknown. As in the two-view case, the
goal is to decouple the above equation into constraints which
allow to separately recover the camera displacements Πi on
one hand and the scene structure λi and X on the other hand.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 11/43
Point Features
Every column of I lies in a four-dimensional space spanned by
columns of the matrix Π. In order to have a solution to the
above equation, the columns of I and Π must therefore be
linearly dependent. In other words, the matrix
Np ≡ (Π, I) =
Π1 x1 0 · · · 0
Π2 0 x2 0 0
…
…
…
. . .
…
Πm 0 0 · · · xm
∈ R3m×(m+4)
must have a nontrivial right null space. For m ≥ 2 (i.e.
3m ≥ m + 4), full rank would be m + 4. Linear dependence of
columns therefore implies the rank constraint:
rank(Np) ≤ m + 3.
In fact, the vector u ≡ (X>,−~λ>)> ∈ Rm+4 is in the right null
space, as Npu = 0.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 12/43
Point Features
For a more compact formulation of the above rank constraint,
we introduce the matrix
I⊥ ≡
x̂1 0 · · · 0
0 x̂2 · · · 0
…
…
. . .
…
0 0 · · · x̂m
∈ R3m×3m,
which has the property of “annihilating” I:
I⊥I = 0,
we can premultiply the above equation to obtain
I⊥ΠX = 0.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 13/43
Point Features
Thus the vector X is in the null space of the matrix
Wp ≡ I⊥Π =
x̂1Π1
x̂2Π2
…
x̂mΠm
∈ R3m×4.
To have a nontrivial solution, we must have
rank(Wp) ≤ 3.
If all images x i are from a single 3D point X , then the matrix
Wp should only have a one-dimensional null space.
Given m images x i ∈ R3 of a point p with respect to m camera
frames Πi , we must have the rank condition
rank(Wp) = rank(Np)−m ≤ 3.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 14/43
Line Features
We can derive a similar rank constraint for lines. As we saw
above, for the coimages `i , i = 1, . . . ,m of a line L spanned by
a base X 0 and a direction V we have:
`>i ΠiX 0 = `
>
i ΠiV = 0.
Therefore the matrix
Wl ≡
`>1 Π1
`>2 Π2
…
`>mΠm
∈ Rm×4
must satisfy the rank constraint
rank(Wl ) ≤ 2,
since the null space of Wl contains the two vectors X 0 and V .
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 15/43
Rank Constraints: Geometric Interpretation
In the case of a point X , we had the equation
WpX = 0, with Wp =
x̂1Π1
x̂2Π2
…
x̂mΠm
∈ R3m×4.
Since all matrices x̂ i have rank 2, the number of independent
rows in Wp is at most 2m. These rows define a set of 2m
planes. Since WpX = 0, the point X is in the intersection of all
these planes. In order for the 2m planes to have a unique
intersection, we need to have rank(Wp) = 3.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 16/43
Rank Constraints: Geometric Interpretation
Preimage of two image points.
The rows of the matrix Wp correspond to the normal vectors of
four planes. The (nontrivial) rank constraint states that these
four planes have to intersect in a single point.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 17/43
Rank Constraints: Geometric Interpretation
In the case of a line L in two views, we have the equation
rank(Wl ) ≤ 2, with Wl =
(
`>1 Π1
`>2 Π2
)
∈ R2×4.
Clearly, we already have rank(Wl ) ≤ 2, so there is no intrinsic
constraint on two images of a line: The preimage of two image
lines always contains a line. We shall see that this is no longer
true for three or more images of a line, then the above
constraint really becomes meaningful.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 18/43
Rank Constraints: Geometric Interpretation
Preimage of two image lines.
For the case of a line observed from two images, the rank
constraint is always fulfilled. Geometrically this states that the
two preimages of each line always intersect in some 3D line.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 19/43
The Multiple-view Matrix of a Point
In the following, the rank constraints will be rewritten in a more
compact and transparent manner. Let us assume we have m
images, the first of which is in world coordinates. Then we have
projection matrices of the form
Π1 = [I,0], Π2 = [R2,T2], . . . , Πm = [Rm,Tm] ∈ R3×4,
which model the projection of a point X into the individual
images.
In general for uncalibrated cameras (i.e. Ki 6= I), Ri will not be
an orthogonal rotation matrix but rather an arbitrary invertible
matrix.
Again, we define the matrix Wp as follows:
Wp ≡ I⊥Π =
x̂1Π1
x̂2Π2
…
x̂mΠm
∈ R3m×4.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 20/43
The Multiple-view Matrix of a Point
The rank of the matrix Wp is not affected if we multiply by a
full-rank matrix Dp ∈ R4×5 as follows:
WpDp =
x̂1Π1
x̂2Π2
…
x̂mΠm
(
x̂1 x1 0
0 0 1
)
=
x̂1x̂1 0 0
x̂2R2x̂1 x̂2R2x1 x̂2T2
x̂3R3x̂1 x̂3R3x1 x̂3T3
…
…
…
x̂mRmx̂1 x̂mRmx1 x̂mTm
.
This means that rank(Wp) ≤ 3 if and only if the submatrix
Mp ≡
x̂2R2x1 x̂2T2
x̂3R3x1 x̂3T3
…
…
x̂mRmx1 x̂mTm
∈ R3(m−1)×2
has rank(Mp) ≤ 1.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 21/43
The Multiple-view Matrix of a Point
The matrix
Mp ≡
x̂2R2x1 x̂2T2
x̂3R3x1 x̂3T3
…
…
x̂mRmx1 x̂mTm
∈ R3(m−1)×2
is called the multiple-view matrix associated with a point p. It
involves both the image x1 in the first view and the coimages
x̂ i in the remaining views.
In summary:
For multiple images of a point p the matrices Np,Wp and Mp
satisfy:
rank(Mp) = rank(Wp)− 2 = rank(Np)− (m + 2) ≤ 1.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 22/43
Multiview Matrix: Geometric Interpretation
Let us look into the geometric information contained in the
multiple-view matrix
Mp ≡
x̂2R2x1 x̂2T2
x̂3R3x1 x̂3T3
…
…
x̂mRmx1 x̂mTm
∈ R3(m−1)×2.
The constraint rank(Mp) ≤ 1 implies that the two columns are
linearly dependent. In fact we have
λ1x̂ iRix1 + x̂ iTi = 0, i = 2, . . . ,m which yields
Mp
(
λ1
1
)
= 0.
Therefore the coefficient capturing the linear dependence is
simply the depth λ1. In other words, the multiple-view matrix
captures exactly the information about a point p that is missing
from a single image, but encoded in multiple images.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 23/43
Relation to Epipolar Constraints
For the multiple-view matrix
Mp ≡
x̂2R2x1 x̂2T2
x̂3R3x1 x̂3T3
…
…
x̂mRmx1 x̂mTm
∈ R3(m−1)×2.
to have rank(Mp) = 1, it is necessary that the pair of vectors
x̂ iTi and x̂ iRix1 to be linearly dependent for all i = 2, . . . ,m.
This gives the epipolar constraints
x>i T̂iRix1 = 0
between the first and the i-th image. (Proof see next slide)
Yet, we shall see that the multiview constraint provides more
information than the pairwise epipolar constraints.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 24/43
Relation to Epipolar Constraints
In the previous slide, we claimed that the linear dependence of
x̂ iTi and x̂ iRix1 gives rise to the epipolar constraint
x>i T̂iRix1 = 0. In the following, we shall give a proof of this
statement which provides an intuitive geometric understanding
of this relationship.
Assume the two vectors x̂ iTi and x̂ iRix1 are dependent, i.e.
there is a scalar γ, such that
x̂ iTi = γx̂ iRix1.
Since x̂ iTi ≡ x i × Ti is proportional to the normal on the plane
spanned by x i and Ti , and x̂ iRix1 is proportional to the normal
spanned by x i and Rix1, the linear dependence is equivalent
to saying that the three vectors x i , Ti and Rix1 are coplanar.
This again is equivalent to saying that the vector x i is
orthogonal to the normal on the plane spanned by the vectors
Ti and Rix1, i.e.
x>i (Ti × Rix1) = x
>
i T̂iRix1 = 0.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 25/43
Analysis of the Multiple-view Constraint
For any nonzero vectors ai ,bi ∈ R3, i = 1,2, . . . ,n, the matrix
a1 b1
a2 b2
…
…
an bn
∈ R3n×2
is rank-deficient if and only if aib>j − bia
>
j = 0 for all
i , j = 1, . . . ,n. We will not prove this statement. Applied to the
rank constraint on Mp we get:
x̂ iRix1(x̂ jTj )> − x̂ iTi (x̂ jRjx1)> = 0,
which gives the trilinear constraint
x̂ i (Tix>1 R
>
j − Rix1T
>
j )x̂ j = 0.
This is a matrix equation giving 3× 3 = 9 scalar trilinear
equations, only four of which are linearly independent.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 26/43
Analysis of the Multiple-view Constraint
From the equations
x̂ iRix1(x̂ jTj )> − x̂ iTi (x̂ jRjx1)> = 0, ∀i , j ,
we see that as long as the entries in x̂ jTj and x̂ jRjx1 are
non-zero, it follows from the above, that the two vectors x̂ iRix1
and x̂ iTi are linearly dependent. If on the other hand
x̂ jTj = x̂ jRjx1 = 0 for some view j , then we have the rare
degenerate case that the point p lies on the line through the
optical centers o1 and oj .
In other words: Except for degeneracies, the bilinear (epipolar)
constraints relating two views are already contained in the
trilinear constraints obtained for the multiview scenario.
Note that the equivalence between the bilinear and trilinear
constraints on one hand and the condition that rank(Mp) ≤ 1 on
the other only holds if the vectors in Mp are nonzero. In certain
degenerate cases this is is not fulfilled.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 27/43
Uniqueness of the Preimage
We will now clarify how the bilinear and trilinear constraints
help to assure the uniqueness of the preimage of a point
observed in three images.
Let x1,x2,x3 ∈ R3 be the 2D point coordinates in three camera
frames with distinct optical centers. If the three images satisfy
the pairwise epipolar constraints
x>i T̂ijRijx j = 0, i , j = 1,2,3,
then a unique preimage is determined except if the three lines
associated to image points x1,x2,x3 are coplanar. Here Tij
and Rij refer to the transition between frames i and j .
Similarly, if these vectors satisfy all trilinear constraints
x̂ j (Tjix>i R
>
ki − Rjix iT
>
ki )x̂k = 0, i , j , k = 1,2,3,
then a unique preimage is determined unless the three lines
associated to image points x1,x2,x3 are colinear.
We will not prove these statements.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 28/43
Degeneracies for the Bilinear Constraints
In the above example, the point p lies in the plane spanned by
the three optical centers which is also called the trifocal plane.
In this case, all pairs of lines do intersect, yet it does not imply
a unique 3D point p (a unique preimage). In practice this
degenerate case arises rather seldom.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 29/43
Degeneracies for the Bilinear Constraints
In the above example, the optical centers lie on a straight line
(rectilinear motion). Again, all pairs of lines may intersect
without there being a unique preimage p.
This case is frequent in applications when the camera moves
in a straight line (e.g. a car on a highway). Then the epipolar
constraints will not allow a unique reconstruction.
Fortunately, the trilinear constraint assures a unique preimage
(unless p is also on the same line with the optical centers).
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 30/43
Uniqueness of the Preimage
Using the multiple-view matrix we obtain a more general and
simpler characterization regarding the uniqueness of the
preimage:
Given m vectors representing the m images of a point in m
views, they correspond to the same point in the 3D space if the
rank of the Mp matrix relative to any of the camera frames is
one. If the rank is zero, the point is determined up to the line on
which all the camera centers must lie.
In summary we get:
rank(Mp)=2 ⇒ no point correspondence & empty preimage
rank(Mp)=1 ⇒ point correspondence & unique preimage
rank(Mp)=0 ⇒ point correspondence & preimage not unique
With these constraints we could decide which features to match
for establishing point correspondence over multiple frames.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 31/43
Multiple-view Factorization of Point Features
The rank condition on the multiple-view matrix captures all the
constraints among multiple images of a point. In principle, one
could perform reconstruction by maximizing some global
objective function subject to the rank condition. This would
lead to a nonlinear optimization problem analogous to the
bundle adjustment in the two-view case.
Alternatively, one can aim for a similar separation of structure
and motion as done for the two-view case in the eight-point
algorithm. Such an algorithm shall be detailed in the following.
One should point out that this approach does not necessarily
lead to a practical algorithm as the spectral approaches do not
imply optimality in the context of noise and uncertainty.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 32/43
Multiple-view Factorization of Point Features
Suppose we have m images x j1, . . . ,x
j
m of n points pj and we
want to estimate the unknown projection matrix Π.
The condition rank(Mp) ≤ 1 states that the two columns of Mp
are linearly dependent. For the j-th point pj this implies
x̂ j2R2x
j
1
x̂ j3R3x
j
1
…
x̂ jmRmx
j
1
+ α
j
x̂ j2T2
x̂ j3T3
…
x̂ jmTm
= 0 ∈ R
3(m−1)×1,
for some parameters αj ∈ R, j = 1, . . . ,n. Each row in the
above equation can be obtained from λjix
j
i = λ
j
1Rix
j
1 + Ti ,
multiplying by x̂ ji :
x̂ jiRix
j
1 + x̂
j
iTi/λ
j
1 = 0.
Therefore, αj = 1/λj1 is nothing but the inverse of the depth of
point pj with respect to the first frame.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 33/43
Motion Estimation from Known Structure
Assume we have the depth of the points and thus their inverse
αj (i.e. known structure). Then the above equation is linear in
the camera motion parameters Ri and Ti . Using the stack
notation Rsi = [r11, r21, r31, r12, r22, r32, r13, r23, r33]
> ∈ R9 and
Ti ∈ R3, we have the linear equation system
Pi
(
Rsi
Ti
)
=
x11
> ⊗ x̂1i α
1x̂1i
x21
> ⊗ x̂2i α
2x̂2i
…
…
xn1
> ⊗ x̂ni α
nx̂ni
(
Rsi
Ti
)
= 0 ∈ R3n.
One can show that the matrix Pi ∈ R3n×12 is of rank 11 if more
than n = 6 points in general position are given. In that case the
null space of Pi is onedimensional and the projection matrix
Πi = (Ri ,Ti ) is given up to a scale factor. In practice one would
use more than 6 points, obtain a full-rank matrix and compute
the solution by a singular value decomposition (SVD).
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 34/43
Structure Estimation from Known Motion
In turn, if the camera motion Πi = (Ri ,Ti ), i = 1, . . . ,m is
known, we can estimate the structure (depth parameters
αj , j = 1, . . . ,n). The least squares solution for the above
equation is given by:
αj = −
∑m
i=2(x̂
j
iTi )
>x̂ jiRix
j
1∑m
i=2 ‖x̂
j
iTi‖2
, j = 1, . . . ,n.
In this way one can iteratively estimate structure and motion,
estimating one while keeping the other fixed.
For initialization one could apply the eight-point algorithm to
the first two images to obtain an estimate of the structure
parameters αj .
While the equation for Πi makes use of the two frames 1 and i
only, the structure parameter estimation takes into account all
frames. This can be done either in batch mode or recursively.
As for the two-view case, such spectral approaches do not
guarantee optimality in the presence of noise and uncertainty.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 35/43
Multiple-view Matrix for Lines
The matrix
Wl =
`>1 Π1
`>2 Π2
…
`>mΠm
∈ Rm×4
associated with m images of a line in space satisfies the rank
constraint rank(Wl ) ≤ 2, because WlX 0 = WlV = 0 for the
base point X 0 and the direction V of the line. To find a more
compact representation, let us assume that the first camera is
in world coordinates, i.e. Π1 = (I,0). The rank is not affected by
multiplying with a full-rank matrix Dl ∈ R4×5:
WlDl =
`>1 0
`>2 R2 `
>
2 T2
…
…
`>mRm `
>
mTm
(̀
1
̂̀
1 0
0 0 1
)
=
`>1 `1 0 0
`>2 R2`1 `
>
2 R2
̂̀
1 `
>
2 T2
…
…
…
`>mRm`1 `
>
mRm ̂̀1 `>mTm
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 36/43
Multiple-view Matrix for Lines
Since multiplication with a full rank matrix does not affect the
rank, we have
rank(WlDl ) = rank(Wl ) ≤ 2.
Since the first column of WlDl is linearly independent from the
remaining ones, the submatrix
Ml =
`
>
2 R2
̂̀
1 `
>
2 T2
…
…
`>mRm ̂̀1 `>mTm
∈ R(m−1)×4,
has the rank constraint:
rank(Ml ) ≤ 1.
For a line projected into m images, we have a much stronger
rank-constraint than for a projected point: For a sufficiently
large number of views m, the matrix Ml could in principle have
a rank of four. The above constraint states that a meaningful
preimage of m observed lines can only exist if rank(Ml ) ≤ 1.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 37/43
Trilinear Constraints for a Line
Again, we can take a closer look at the meaning of the above
rank constraint. Regarding the first three columns of Ml it
implies that respective row vectors must be pairwise linearly
dependent, i.e. for all i , j 6= 1:
`>i Ri ̂̀1 ∼ `>j Rj ̂̀1,
which is equivalent to the trilinear equation
`>i Ri ̂̀1R>j `j = 0.
Proof: The above proportionality states that the three vectors
R>i `i , R
>
j `j and `1 are coplanar. The lower equation is the
equivalent statement that the vector R>i `i is orthogonal to the
normal on the plane spanned by R>j `j and `1.
Interestingly, the above constraint only involves the camera
rotations, not the camera translations.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 38/43
Trilinear Constraints for a Line
Taking into account the fourth column of the multiple-view
matrix Ml , the rank constraint implies the linear dependency
between the i th and the j th row. This is equivalent to the
trilinear constraint:
`>j Tj`
>
i Ri ̂̀1 − `>i Ti`>j Rj ̂̀1 = 0.
The proof follows from the general lemma on page 25.
The above constraint relates the first, the i th and the j th
images. From previous discussion, we saw that all nontrivial
constraints in the case of lines involve at least three images.
The two trilinear constraints above are equivalent to the rank
constraint if the scalar `>i Ti 6= 0, i.e. in non-degenerate cases.
In general, rank(Ml ) ≤ 1 if and only if all its 2× 2-minors
(deutsch: Untermatrizen), have zero determinant. Since these
minors only include three images at a time, one can conclude
that any multiview constraint on lines can be reduced to
constraints which only involve three lines at a time.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 39/43
Uniqueness of the Preimage
The key idea of the rank constraint on the multiple-view matrix
Ml was to assure that m observations of a line correspond to a
consistent preimage L. The uniqueness of the preimage in the
case of the trilinear constraints can be characterized as follows.
Lemma: Given three camera frames with distinct optical cen-
ters and any three vectors `1, `2, `3 ∈ R3 that represent three
image lines. If the three image lines satisfy the trilinear con-
straints
`>j Tji`
>
k Rki ̂̀i − `>k Tki`>j Rji ̂̀i = 0, i , j , k ∈ {1,2,3},
then their preimage L is uniquely determined except for the
case in which the preimage of every `i is the same plane in
space. This is the only degenerate case, and in this case,
the matrix Ml becomes zero.
Note that the above constraint combines the two trilinear
constraints introduced on the previous slides.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 40/43
Uniqueness of the Preimage
No preimage: The lines L2 and L3 don’t coincide.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 41/43
Uniqueness of the Preimage
Uniqueness of the preimage: The lines L2 and L3 coincide.
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 42/43
Uniqueness of the Preimage
A similar statement can be made regarding the uniqueness of
the preimage of m lines in relation to the rank of the multiview
matrix Ml .
Theorem: Given m vectors `i ∈ R3 representing images of
lines with respect to m camera frames. They correspond to
the same line in space if the rank of the matrix Ml relative to
any of the camera frames is 1. If its rank is 0 (i.e. the matrix
Ml itself is zero), then the line is determined up to a plane on
which all the camera centers must lie.
Overall we have the following cases:
rank(Ml )=2 ⇒ no line correspondence
rank(Ml )=1 ⇒ line correspondence & unique preimage
rank(Ml )=0 ⇒ line correspondence & preimage not unique
Reconstruction from
Multiple Views
Prof. Daniel Cremers
From Two Views to
Multiple Views
Preimage & Coimage
from Multiple Views
From Preimages to
Rank Constraints
Geometric
Interpretation
The Multiple-view
Matrix
Relation to Epipolar
Constraints
Multiple-View
Reconstruction
Algorithms
Multiple-View
Reconstruction of
Lines
updated June 7, 2021 43/43
Summary
One can generalize the two-view scenario to that of
simultaneously considering m ≥ 2 images of a scene. The
intrinsic constraints among multiple images of a point or a line
can be expressed in terms of rank conditions on the matrix N,
W or M.
The relationship among these rank conditions is as follows:
(Pre)image coimage Jointly
Point rank(Np) ≤ m + 3 rank(Wp) ≤ 3 rank(Mp) ≤ 1
Line rank(Nl ) ≤ 2m + 2 rank(Wl ) ≤ 2 rank(Ml ) ≤ 1
These rank conditions capture the relationships among
corresponding geometric primitives in multiple images. They
impose the existence of unique preimages (up to degenerate
cases). Moreover, they give rise to natural factorization-based
algorithms for multiview recovery of 3D structure and motion
(i.e. generalizations of the eight-point algorithm).
From Two Views to Multiple Views
Preimage & Coimage from Multiple Views
From Preimages to Rank Constraints
Geometric Interpretation
The Multiple-view Matrix
Relation to Epipolar Constraints
Multiple-View Reconstruction Algorithms
Multiple-View Reconstruction of Lines