Fundamentals of Computer Vision
Lecture
• Epipolar geometry.
• Essential matrix.
• Fundamental matrix.
• 8-point algorithm.
Overview of today’s lecture
Slide credits
Most of these slides were adapted from:
• Kris Kitani (15-463, Fall 2016, Fall 2017), Ioannis Gkioulekas (16-385, Spring 2019), Robert Colin (454, Fall 2019s).
Some slides were inspired or taken from: • Fredo Durand (MIT).
Cross product
Can also be written as a matrix multiplication
Skew symmetric
Camera-camera transform just like world-camera transform
If these three vectors are coplanar then
Given a point in one image,
multiplying by the essential matrix will tell us the epipolar line in the second view.
Epipolar constraint
Potential matches for lie on the epipolar line
Assumption:
points aligned to camera coordinate axis (calibrated camera)
putting it together
rigid motion coplanarity
Essential Matrix
[Longuet-Higgins 1981]
Properties of the E matrix
Longuet-Higgins equation
Epipolar lines
Epipoles
(points in normalized coordinates)
How do you generalize to uncalibrated cameras?
The Fundamental matrix
The
Fundamental matrix
is a
generalization
of the
Essential matrix,
where the assumption of
calibrated cameras
is no longer valid
Given a point in one image,
multiplying by the essential matrix will tell us the epipolar line in the second view.
Assumption:
Epipolar constraint
points aligned to camera coordinate axis (calibrated camera)
The Essential matrix operates on image points expressed in
normalized coordinates
(points have been aligned (normalized) to camera coordinates)
Camera coordinate
camera Pixel coordinate point
image point
(row, col)
To use image (pixel) coordinates we must consider the
INTRINSIC camera
image plane
Recall?
K =
parameters
𝛼$ 𝑠 𝑝$ 0 𝛼( 𝑝(
001
camera coordinate system image coordinate system
The Essential matrix operates on image points expressed in
normalized coordinates
(points have been aligned (normalized) to camera coordinates)
K* + ,
To use image (pixel) coordinates we must consider the
INTRINSIC camera
camera point
image point
Camera coordinate
Pixel coordinate (row, col)
parameters
𝛼$ 𝑠 𝑝$ 0 𝛼( 𝑝(
001
image plane
Recall?
K =
camera coordinate system image coordinate system
The Essential matrix operates on image points expressed in
normalized coordinates
(points have been aligned (normalized) to camera coordinates)
K* + ,
camera image point point
Writing out the epipolar constraint in terms of image coordinates
Same equation works in image/pixel coordinates!
it maps pixels to epipolar lines
Properties of the E matrix
Longuet-Higgins equation
Epipolar lines
Epipoles
(points in image coordinates)
Breaking down the fundamental matrix
Depends on both intrinsic and extrinsic parameters
Writing out the epipolar constraint in terms of image coordinates
Breaking down the fundamental matrix
Depends on both intrinsic and extrinsic parameters
How would you solve for F?
The 8-point algorithm
Assume you have M matched image points
Each correspondence should satisfy
How would you solve for the 3 x 3 F matrix?
Assume you have M matched image points
Each correspondence should satisfy
How would you solve for the 3 x 3 F matrix? SVD
Assume you have M matched image points
Each correspondence should satisfy
How would you solve for the 3 x 3 F matrix?
Set up a homogeneous linear system with 9 unknowns
How many equation do you get from one correspondence?
ONE correspondence gives you ONE equation
Set up a homogeneous linear system with 9 unknowns
How many equations do you need?
Each point pair (according to epipolar constraint) contributes only one scalar equation
Note: This is different from the Homography estimation where each point pair contributes 2 equations.
We need at least 8 points
Hence, the 8 point algorithm!
How do you solve a homogeneous linear system?
How do you solve a homogeneous linear system?
Total Least Squares
minimize subject to
How do you solve a homogeneous linear system?
Total Least Squares
minimize subject to
SVD!
Eight-Point Algorithm
0. (Normalize points)
1. Construct the M x 9 matrix A
2. FindtheSVDofA
3. Entries of F are the elements of column of V
corresponding to the least singular value
4. (Enforce rank 2 constraint on F)
5. (Un-normalize F)
See Hartley-Zisserman for why we do this
Eight-Point Algorithm
0. (Normalize points)
1. Construct the M x 9 matrix A
2. FindtheSVDofA
3. Entries of F are the elements of column of V
corresponding to the least singular value
4. (Enforce rank 2 constraint on F)
5. (Un-normalize F)
How do we do this?
Eight-Point Algorithm
0. (Normalize points)
1. Construct the M x 9 matrix A
2. FindtheSVDofA
3. Entries of F are the elements of column of V
corresponding to the least singular value
4. (Enforce rank 2 constraint on F)
5. (Un-normalize F)
How do we do this? SVD!
Enforcing rank constraints Problem: Given a matrix F, find the matrix F’ of rank k that is closest to F,
min 𝐹−𝐹:; 01
2345 01 67
Solution: Compute the singular value decomposition of F, 𝐹 = 𝑈Σ𝑉?
Form a matrix Σ’ by replacing all but the k largest singular values in Σ with 0. Then the problem solution is the matrix F’ formed as,
𝐹: = 𝑈Σ:𝑉?
Essential/Fundamental Matrices
The essential and fundamental matrices are 3×3 matrices that “encode” the epipolar geometry of two views.
Given a point in one image, multiplying by the essential/fundamental matrix will tell us which epipolar line to search along in the second view.
Finding the left and right nullspaces of E/F tells us where the epipoles are.
Essential Matrix works in film plane
–
coordinates (calibrated
Fundamental Matrix
works in pixel
cameras) cameras)
– coordinates
(uncalibrated
Example
Epipolar lines
Where is the epipole?
How would you compute it?
The epipole is in the right null space of F
How would you solve for the epipole?
(hint: this is a homogeneous linear system)
The epipole is in the right null space of F
How would you solve for the epipole?
(hint: this is a homogeneous linear system) SVD!
>> [u,d] = eigs(F’ * F)
eigenvectors
u=
-0.0013 0.2586 -0.9660
0.0029 -0.9660 -0.2586
1.0000 0.0032 -0.0005
eigenvalue
d = 1.0e8*
-1.0000 0 0
0 -0.0000 0
0 0 -0.0000
>> [u,d] = eigs(F’ * F)
eigenvectors
u=
-0.0013 0.2586 -0.9660
0.0029 -0.9660 -0.2586
1.0000 0.0032 -0.0005
eigenvalue
d = 1.0e8*
-1.0000 0 0
0 -0.0000 0
0 0 -0.0000
Eigenvector associated with smallest eigenvalue
>> [u,d] = eigs(F’ * F)
eigenvectors
u=
-0.0013 0.2586 -0.9660
0.0029 -0.9660 -0.2586
1.0000 0.0032 -0.0005
eigenvalue
d = 1.0e8*
-1.0000 0 0
0 -0.0000 0
0 0 -0.0000
>> uu = u(:,3)
( -0.9660 -0.2586 -0.0005)
Eigenvector associated with smallest eigenvalue
Epipole projected to image coordinates
>> [u,d] = eigs(F’ * F)
eigenvectors
u=
-0.0013 0.2586 -0.9660
0.0029 -0.9660 -0.2586
1.0000 0.0032 -0.0005
eigenvalue
d = 1.0e8*
-1.0000 0 0
0 -0.0000 0
0 0 -0.0000
>> uu = u(:,3)
( -0.9660 -0.2586 -0.0005)
>> uu / uu(3)
(1861.02 498.21 1.0)
Epipole projected to image >> uu / uu(3)
coordinates
(1861.02 498.21 1.0)
epipole
Basic reading:
• Szeliski textbook, Sections 7.1, 7.2, 11.1.
• Hartley and Zisserman, Chapters 9, 11, 12.
References
Stereo
What’s different between these two images?
Objects that are close move more or less?
The amount of horizontal movement is inversely proportional to …
The amount of horizontal movement is inversely proportional to …
… the distance from the camera.
More formally…