Lecture 7

Nguyễn Xuân Hạ

1
Structure from Motion (SFM)

• Problem formulation: Given a set of 𝑛 point correspondences

between two images, {𝑝1𝑖 = 𝑢1𝑖 , 𝑣1𝑖 , 𝑝2𝑖 = (𝑢2𝑖 , 𝑣2𝑖 )}, where i= 1…n, the
goals is to simultaneously
• Estimate the 3D points 𝑷𝒊 ,
• the camera relative-motion parameters(R,T),
• and the camera intrinsics 𝑲𝟏 , 𝑲𝟐 that satisfy:
𝑖
𝑋𝑊
𝑢1𝑖 𝑖
𝜆1𝑖 𝑣1𝑖 = 𝐾1 𝐼 0 . 𝑌𝑊
𝑖
1 𝑍𝑊
1
𝑖
𝑖 𝑋𝑊
𝑢2 𝑖
𝜆𝑖2 𝑌 𝑊
𝑣2𝑖 = 𝐾2 𝑅 𝑇 . 𝑖
𝑍𝑊
1
1

2
Structure from Motion (SFM)

• Let’s study the case in which the cameras are calibrated

• For convenience, let’s use normalized image coordinates
• Thus, we want to find 𝑹, 𝑻, 𝑷𝑖 that satisfy:
𝑢ത 𝑢
→ 𝑣ҧ = 𝐾 −1 𝑣
1 1

𝑖
𝑋𝑊
𝑢ത1𝑖 𝑖
𝜆1𝑖 𝑖 = 𝐼 0 . 𝑌𝑊
𝑣ҧ1 𝑖
1 𝑍𝑊
1
𝑖
𝑋 𝑊
𝑢ത 2𝑖 𝑖
𝜆𝑖2 𝑖 = 𝑅 𝑇 . 𝑌𝑊
𝑣ҧ 2 𝑖
1 𝑍 𝑊
1

3
Scale Ambiguity

• If we rescale the entire scene and camera views by a constant

factor (i.e., similarity transformation), the projections (in pixels) of
the scene points in both images remain exactly the same:

4
Scale Ambiguity

• In Structure from Motion, it is therefore not possible to recover

the absolute scale of the scene!
• What about stereo vision? Is it possible? Why?
• Thus, only 5 degrees of freedom are measurable:
• 3 parameters to describe the rotation
• 2 parameters for the translation up to a scale (we can only
compute the direction of translation but not its length)

5
Structure From Motion (SFM)

• How many knowns and unknowns?

• 𝟒𝒏 knowns:
• 𝑛 correspondences; each one 𝑢1𝑖 , 𝑣1𝑖 and 𝑢2𝑖 , 𝑣2𝑖 , , 𝑖 = 1 … 𝑛
• 𝟓 + 𝟑𝒏 unknowns
• 5 for the motion up to a scale (3 for rotation, 2 for translation)
• 3𝑛 = number of coordinates of the 𝑛 3D points

• Does a solution exist?

• If and only if the number of independent equations ≥ number of unknown
⇒ 4𝑛 ≥ 5 + 3𝑛 ⇒ 𝒏 ≥ 𝟓
• First attempt to identify the solutions by Kruppa in 1913 (see historical note on
slide 16).

E. Kruppa, Zur Ermittlung eines Objektes aus zwei Perspektiven mit Innerer Orientierung, Sitz.-Ber. Akad. Wiss.,
Wien, Math. Naturw. Kl., Abt. IIa., 1913. – English Translation plus original paper by Guillermo Gallego, Arxiv, 2017
(”To determine a 3D object from two perspective views with known inner orientation”)

6
Structure From Motion (SFM)

• Can we solve the estimation of relative motion (𝑅, 𝑇) independently of the

estimation of the 3D points? Yes! The next couple of slides prove that this
is possible.
• Once (𝑅, 𝑇) are known, the 3D points can be triangulated using the
triangulation algorithm from Lecture 7 (i.e., least square approximation
plus reprojection error minimization)

7
The Epipolar Constraint: Recap from Lecture 07

• The camera centers 𝐶1 , 𝐶2 and one image point 𝑝1 (or 𝑝2 ) determine the
so called epipolar plane
• The intersections of the epipolar plane with the two image planes are
called epipolar lines
• Corresponding points must therefore lie along the epipolar lines: this
constraint is called epipolar constraint
• An alternative way to formulate the epipolar constraint is to notice that
two corresponding image vectors plus the baseline must be
coplanar

8
Epipolar Constraint

𝑢1 𝑢2
𝑝1ҧ = 𝑣1 𝑝ҧ2 = 𝑣2
1 1

𝑝1ҧ , 𝑝ҧ2 , 𝑇 are coplanar:

𝑝ҧ2𝑇 . 𝑛 = 0 ⇒ 𝑝ҧ2𝑇 . 𝑇 × 𝑝1ҧ ′ = 0 ⇒ 𝑝ҧ2𝑇 𝑇 × (𝑅𝑝1ҧ ) = 0 ⇒ 𝑝ҧ2𝑇 𝑇𝑋 𝑅𝑝1ҧ = 0

⇒ 𝑝ҧ2𝑇 𝐸 𝑝1ҧ = 0 epipolar constraint

E = TX R 𝑒𝑠𝑠𝑒𝑛𝑡𝑖𝑎𝑙 𝑚𝑎𝑡𝑟𝑖𝑥

9
Epipolar Constraint

𝑢ത1 𝑢ത 2
𝑝1ҧ = 𝑣ҧ1 𝑝ҧ2 = 𝑣ҧ2 Normalized image coordinates
1 1

𝑝ҧ2𝑇 𝐸𝑝1ҧ = 0 Epipolar constraint or Longuet-Higgins equation (1981)

E = TX R 𝐸𝑠𝑠𝑒𝑛𝑡𝑖𝑎𝑙 𝑚𝑎𝑡𝑟𝑖𝑥

R and T can be computed from E recalling that: E = TX R(see slide 21)

NB: Because the skew-symmetric matrix has rank 2 and the rotation is orthonormal,
the Essential matrix has also rank 2

Hugh Christopher Longuet-Higgins, A computer algorithm for reconstructing a scene from two
PDF

projections, Nature, 1981, PDF.

10
Example: Essential Matrix of a Camera Translating along 𝑥

E = TX R
0 −𝑡𝑧 𝑡𝑦 0 0 0
𝑇𝑋 = 𝑡𝑧 0 −𝑡𝑥 = 0 0 𝑏
−𝑡𝑦 𝑡𝑥 0 0 −𝑏 0
R = I3×3
0 0 0
Essential matrix: E = TX R = 0 0 𝑏
0 −𝑏 0
0 0 0 𝑢ത1
𝑇
Epipolar constraint: 𝑝ҧ2 𝐸 𝑝1ҧ = 0 → 𝑢ത 2 𝑣ҧ2 1 0 0 𝑏 𝑣ҧ1 = 0
0 −𝑏 0 1
→ −𝑏𝑣ҧ1 + 𝑏𝑣ҧ2 = 0 → 𝑣ҧ1 = 𝑣ҧ2

11
How to compute the Essential Matrix?

• If we don’t know (𝑅, 𝑇) can we estimate 𝐸 from two images?

• Yes, given at least 5 correspondences

Image 1 Image 2

12
Historical Note

• Kruppa showed in 1913 that 5 image correspondences is the minimal case

and that there can be at up to 11 solutions
• However, in 1988, Demazure showed that there are actually at most 10 distinct
solutions.
• In 1996, Philipp proposed an iterative algorithm to find these solutions.
• In 2004, Nister proposed the first efficient and non iterative solution. It uses
Groebner basis decomposition.
• The first popular solution uses 8 points and is called the 8-point algorithm or
Longuet-Higgins algorithm (1981). Because of its ease of implementation, it is
still used today (e.g., NASA rovers)

[1] E. Kruppa, Zur Ermittlung eines Objektes aus zwei Perspektiven mit Innerer Orientierung,
Sitz.-Ber. Akad. Wiss., Wien, Math. Naturw. Kl., Abt. IIa., 1913. – English Translation plus original
paper by Guillermo Gallego, Arxiv, 2017
[2] H. Christopher Longuet-Higgins, A computer algorithm for reconstructing a scene from two
projections, Nature, 1981, PDF.
[3] D. Nister, An Efficient Solution to the Five-Point Relative Pose Problem, PAMI, 2004, PDF

13
The 8-point algorithm

• Each pair of point correspondences 𝑝1ҧ = (ത𝑢1 , 𝑣ҧ1 , 1)𝑇 , 𝑝ҧ2 = (𝑢ത 2 , 𝑣ҧ 2 , 1)𝑇
provides a linear equation:
𝑝ҧ2𝑇 𝐸 𝑝1ҧ = 0
𝑒11 𝑒12 𝑒13
𝐸 = 𝑒21 𝑒22 𝑒23
𝑒31 𝑒32 𝑒33

𝑢ത 2 𝑢ത1 𝑒11 + 𝑢ത 2 𝑣ҧ1 𝑒12 + 𝑢ത 2 𝑒13 + 𝑣ҧ 2 𝑢ത1 𝑒21 + 𝑣ҧ 2 𝑣ҧ1 𝑒22 + 𝑣ҧ 2 𝑒23 + 𝑢ത1 𝑒31 + 𝑣ҧ1 𝑒32 + 𝑒33 = 0

NB: The 8-point algorithm assumes that the entries of E are all independent(which is
not true since, for the calibrated case, they depend on 5 parameters (R and T))
By contrast, the 5-point algorithm uses the epipolar constraint considering the
dependencies among all entries.
H. Christopher Longuet-Higgins, A computer algorithm for reconstructing a scene from two projections,
Nature, 1981, PDF.

14
The 8-point algorithm

• For 𝑛 points, we can write

15
The 8-point algorithm

ഥ=0
Q. E
Minimal solution
ഥ
• 𝑄(𝑛×9) should have rank 8 to have a unique (up to a scale) non-trivial solution E

• Each point correspondence provides 1 independent equation

• Thus, 8 point correspondences are needed
Over-determined solution
• n > 8 points
• A solution is to minimize Q. 𝐸ത 2 subject to the constraint 𝐸ത 2 = 1. The solution is the
eigenvector corresponding to the smallest eigenvector of the matrix
𝑄 𝑇 𝑄 (𝑏𝑒𝑐𝑎𝑢𝑠𝑒 𝑖𝑡 𝑖𝑠 𝑡ℎ𝑒 𝑢𝑛𝑖𝑡 𝑣𝑒𝑐𝑡𝑜𝑟 𝑥 𝑡ℎ𝑎𝑡 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒𝑠 𝑄𝑥 2 = 𝑥 𝑇 𝑄 𝑇 𝑄𝑥).
• It can be solved through Singular Value Decomposition (SVD). Matlab instructions:
Degenerate Configurations
• The solution of the 8-point algorithm is degenerate when the 3D points are coplanar.
• Conversely, the 5-point algorithm works also for coplanar points

16
8-point algorithm: Matlab code

• A few lines of code. In today’s exercise you will learn

how to implement it

17
Extract R and T from E

• Singular Value Decomposition: 𝐸 = 𝑈𝑆𝑉 𝑇

• Because of noise, E may not have rank 2, so we must enforce this as a
constraint
• Enforcing rank-2 constraint: set the smallest singular value of 𝑆 to 0:
𝜎1 0 0
𝑆 = 0 𝜎2 0
0 0 0

0 ∓1 0 0 −𝑡𝑧 𝑡𝑦 𝑡𝑥
𝑇෠ = 𝑈 ±1 0 0 𝑆𝑈 𝑇 𝑇෠ = 𝑡𝑧 0 −𝑡𝑥 ⇒ 𝑡Ƹ = 𝑡𝑦
0 0 0 −𝑡𝑦 𝑡𝑥 0 𝑡𝑧

0 ∓1 0
𝑅 = 𝑈 ±1 0 0 𝑉𝑇
0 0 1

18
4 possible solutions of R and T

• There exists only one solution where points are in front of both
cameras (cheirality constraint)

19
Structure from Motion (SFM)

Two variants exist:

• Calibrated camera(s) ⇒ 𝑲𝟏 , 𝑲𝟐 are known
• Uses the Essential matrix
• Uncalibrated camera(s) ⇒ 𝑲𝟏 , 𝑲𝟐 are unknown
• Uses the Fundamental matrix

20
The Fundamental Matrix

• So far, we have assumed to know the camera intrinsic parameters

and we have used normalized image coordinates to get the epipolar
constraint for calibrated cameras:

𝑢ത1𝑖 𝑢1𝑖 𝑢ത 2𝑖 𝑢2𝑖

𝑖 = 𝐾1−1 𝑖 = 𝐾2−1
𝑣1ҧ 𝑣1𝑖 𝑣ҧ2 𝑣2𝑖
1 1 1 1

𝑝ҧ2𝑇 𝐸 𝑝1ҧ = 0

𝑖 𝑇
𝑢ത 2 𝑢ത1𝑖
𝑣ҧ2𝑖 𝐸 𝑣1ҧ 𝑖 = 0
1 1

21
The Fundamental Matrix

• So far, we have assumed to know the camera intrinsic parameters

and we have used normalized image coordinates to get the
epipolar constraint for calibrated cameras:

𝑢ത1𝑖 𝑢1𝑖 𝑢ത 2𝑖 𝑢2𝑖

𝑖 = 𝐾1−1 𝑖 = 𝐾2−1
𝑣ҧ1 𝑣1𝑖 𝑣ҧ2 𝑣2𝑖
1 1 1 1

𝑝ҧ2𝑇 𝐸 𝑝1ҧ = 0

𝑖 𝑇
𝑢2 𝑢1𝑖
𝑣2𝑖 𝐾2−𝑇 𝐸𝐾1−1 𝑣1𝑖 = 0
1 1

22
The Fundamental Matrix

• So far, we have assumed to know the camera intrinsic parameters

and we have used normalized image coordinates to get the
epipolar constraint for calibrated cameras:

𝑢ത1𝑖 𝑢1𝑖 𝑢ത 2𝑖 𝑢2𝑖

𝑖 = 𝐾1−1 𝑖 = 𝐾2−1
𝑣ҧ1 𝑣1𝑖 𝑣ҧ2 𝑣2𝑖
1 1 1 1

𝑝ҧ2𝑇 𝐸 𝑝1ҧ = 0
Fun thing: check out the
𝑖 𝑇 Fundamental Matrix song,
𝑢2 𝑢1𝑖 [Link]
𝑣2𝑖 𝐹 𝑣1𝑖 = 0
1 1
Fundamental Matrix 𝐹 = 𝐾2−𝑇 𝐸𝐾1−1

23
The 8-point Algorithm for the Fundamental Matrix

• The same 8-point algorithm to compute the essential matrix from a

set of normalized image coordinates can also be used to
determine the Fundamental matrix:
𝑖 𝑇
𝑢2 𝑢1𝑖
𝑣2𝑖 𝐹 𝑣1𝑖 = 0
1 1
• However, now the key advantage is that we work directly in pixel
coordinates

24
Problem with 8-point algorithm

25
Problem with 8-point algorithm

• Poor numerical conditioning, which makes results very sensitive to

noise
• Can be fixed by rescaling the data: Normalized 8-point algorithm

26
Normalized 8-point algorithm (1/3)

• This can be fixed using a normalized 8-point algorithm [Hartley, 1997],

which estimates the Fundamental matrix on a set of Normalized
correspondences (with better numerical properties) and then
unnormalizes the result to obtain the fundamental matrix for the given
(unnormalized) correspondences
• Idea: Transform image coordinates so that they are in the range ~[-1,1] ×
[-1,1]
• One way is to apply the following rescaling and shift

Hartley, In defense of the eight-point algorithm, IEEE Transactions of Pattern Analysis and Machine Intelligence,
PDF

27
Normalized 8-point algorithm (3/3)

• The Normalized 8-point algorithm can be summarized in three steps:

1. Normalize the point correspondences: 𝑝 ෞ1 = 𝐵1 𝑝1 , 𝑝
ෞ2 = 𝐵2 𝑝2
2. Estimate normalized 𝑭 ෡ with 8-point algorithm using normalized
coordinates 𝑝
ෞ2 , , 𝑝
ෞ1
3. Compute unnormalized F from 𝐹: ෠

28
Normalized 8-point algorithm (2/3)

• In the original 1997 paper, Hartley proposed to rescale the two point sets
such that the centroid of each set is 0 and the mean standard deviation
2 (equivalent to having the points distributed around a circle passing
through the four corners of the [−1,1] × [−1,1] square).
2
• This can be done for every point as follows: 𝑝෡𝑖 = (𝑝𝑖 − 𝜇)
𝜎

1 1 𝑛
Where 𝜇 = 𝜇𝑥 , 𝜇𝑦 = 𝑁 σ𝑛𝑖=1 𝑝𝑖 is the centroid and 𝜎 = σ 𝑝𝑖 − 𝜇 2 is
𝑁 𝑖=1
the standard deviation of the point set
• This transformation can be expressed in matrix form using homogeneous
coordinates:
2 2
0 − 𝜇
𝜎 𝜎 𝑥
𝑝෡𝑖 = 2 2 𝑝𝑖
0 − 𝜇
𝜎 𝜎 𝑦
0 0 1
Hartley, In defense of the eight-point algorithm, IEEE Transactions of Pattern Analysis and Machine Intelligence,
1997. PDF

29
Can 𝑅, 𝑇, 𝑲𝟏 , 𝑲𝟐 be extracted from F?

• In general no: infinite solutions exist

• However, if the coordinates of the principal points of each camera
are known and the two cameras have the same focal length 𝑓 in
pixels, then 𝑅, 𝑇, 𝑓 can determined uniquely

30
Comparison between Normalized and non-normalized algorithm

31
Error Measures

• The quality of the estimated Essential or Fundamental matrix can be

measured using different error metrics:
• Algebraic error
• Directional Error
• Epipolar Line Distance
• Reprojection Error

• When is the error exactly 0?

• These errors will be exactly 0 only if 𝑬 (or 𝑭) is computed from just 8
points (because in this case a non-overdetermined solution exists).
• For more than 8 points, the 8-point algorithm is overdetermined and the
error will only be 0 if there is no noise or outliers in the data

32
Algebraic Error

• It follows directly from the 8-point algorithm, which seeks to minimize the algebraic
error (see slide 19):
𝑛
𝑇
𝑒𝑟𝑟 = 𝑄𝐸 2
= ෍(𝑝ഥ𝑖 2 𝑬𝑝ഥ𝑖 1 )2
𝑖=1

• From the proof of the epipolar constraint and using the definition of dot product, it
can be observed that:
𝑝ҧ2𝑇 𝐸 𝑝1ҧ = 𝑝ҧ2𝑇 . (𝐸 𝑝1ҧ ) = 𝑝ҧ2 𝐸 𝑝1ҧ cos 𝜃 = 𝑝ҧ2 𝑇𝑋 𝑅 𝑝1ҧ cos 𝜃
• We can see that this product depends on the angle 𝜃 between 𝒑 ഥ𝟐 and the vector
𝑬𝒑𝟏 which is parallel to the normal 𝒏 of the epipolar plane. It is nonzero when 𝒑 ഥ𝟏 ,
ഥ𝟐 and 𝑻 are not coplanar
𝒑
• What is the drawback of this error measure?

33
Directional Error

• Sum of squared cosines of the angle from the epipolar plane:

𝑛

𝑒𝑟𝑟 = ෍(cos(𝜃𝑖 ))2

𝑖=1
• It is obtained by normalizing the algebraic error:
𝑝ҧ2𝑇 𝐸 𝑝1ҧ
cos 𝜃 =
𝑝2ҧ 𝐸 𝑝1ҧ

34
Epipolar Line Distance

• Sum of Squared Epipolar-Line-to-point

𝑛
Distances:
𝑒𝑟𝑟 = ෍(𝑑 𝑝1𝑖 , 𝑙1𝑖 )2 +(𝑑(𝑝2𝑖 , 𝑙2𝑖 ))2
𝑖=1

35
Reprojection Error

• Sum of the Squared Reprojection Errors:

𝑛
2 2
𝑒𝑟𝑟 = ෍ 𝑝1𝑖 − 𝜋(𝑃𝑖 , 𝐾1 , 𝐼, 0) + 𝑝2𝑖 − 𝜋(𝑃𝑖 , 𝐾2 , 𝑅, 𝑇)
𝑖=1
• More expensive than the previous three errors because it requires to
first triangulate the 3D points!
• However, it is the most popular because more accurate. The reason
is that the error is computed directly with the respect the raw input data,
which is ideal for robotics and AR/VR applications, where the goal is to
achieve visually accurate alignment in the image space.

36
Things to remember

• SFM from 2 view

• Calibrated and uncalibrated case
• Proof of Epipolar Constraint
• 8-point algorithm and algebraic error
• Normalized 8-point algorithm
• Algebraic, directional, Epipolar line distance, Reprojection error

37
Readings

• CH. 11.3 of Szeliski book, 2nd edition

• Ch. 14.2 of Corke book

38
Understanding Check

• Are you able to answer the following questions?

• What's the minimum number of correspondences required for calibrated SFM and
why?
• Are you able to derive the epipolar constraint?
• Are you able to define the essential matrix?
• Are you able to derive the 8-point algorithm?
• How many rotation-translation combinations can the essential matrix be
decomposed into?
• Are you able to provide a geometrical interpretation of the epipolar constraint?
• Are you able to describe the relation between the essential and the fundamental
matrix?
• Why is it important to normalize the point coordinates in the 8-point algorithm?
• Describe one or more possible ways to achieve this normalization.
• Are you able to describe the normalized 8-point algorithm?
• Are you able to provide quality metrics and their interpretation for the essential and
fundamental matrix estimation?

39