The 8-point algorithm
16-385 Computer Vision (Kris Kitani)
Carnegie Mellon University
Fundamental Matrix Estimation
Given a set of matched image points
0
{xi , xi }
Estimate the Fundamental Matrix
0>
xm Fxm =0
What’s the relationship between F and x?
Assume you have M point correspondences
0
{xm , xm } m = 1, . . . , M
Each correspondence should satisfy
0>
xm Fxm =0
How would you solve for the 3 x 3 F matrix?
Assume you have M point correspondences
0
{xm , xm } m = 1, . . . , M
Each correspondence should satisfy
0>
xm Fxm =0
How would you solve for the 3 x 3 F matrix?
S V D
Assume you have M point correspondences
0
{xm , xm } m = 1, . . . , M
Each correspondence should satisfy
0>
xm Fxm =0
How would you solve for the 3 x 3 F matrix?
S V D
Assume you have M point correspondences
0
{xm , xm } m = 1, . . . , M
Each correspondence should satisfy
0>
xm Fxm =0
How would you solve for the 3 x 3 F matrix?
S V D
Assume you have M point correspondences
0
{xm , xm } m = 1, . . . , M
Each correspondence should satisfy
0>
xm Fxm =0
How would you solve for the 3 x 3 F matrix?
Set up a homogeneous linear system with 9 unknowns
0>
xm Fxm =0
2 32 3
⇥ ⇤ f 1 f2 f3 xm
0
xm 0
ym 1 4 f4 f5 f 6 5 4 ym 5 = 0
f7 f8 f9 1
How many equation do you get from one correspondence?
2 32 3
⇥ ⇤ f 1 f2 f3 xm
0
xm 0
ym 1 4 f4 f5 f 6 5 4 ym 5 = 0
f7 f8 f9 1
ONE correspondence gives you ONE equation
0 0
x m x m f 1 + x m ym f 2 + x m f 3 +
0 0
y m x m f 4 + ym y m f 5 + ym f 6 +
0 0
x m f 7 + ym f 8 + f 9 = 0
2 32 3
⇥ ⇤ f 1 f2 f3 xm
0
xm 0
ym 1 4 f4 f5 f 6 5 4 ym 5 = 0
f7 f8 f9 1
Set up a homogeneous linear system with 9 unknowns
2 3
f1
6 f2 7
6 7
2 36
6 f3 7
7
x1 x01 x1 y10 x1 y1 x01 y1 y10 y1 x01 y10 1 6 f4 7
6 .. .. .. .. .. .. .. .. .. 76 7
4 . . . . . . . . . 56
6 f5 7=0
7
6 f6 7
xM x0M 0
x M yM xM yM x0M 0
y M yM yM x0M 0
yM 1 6 7
6 f7 7
6 7
4 f8 5
f9
How many equations do you need?
Each point pair (according to epipolar constraint)
contributes only one scalar equation
0>
xm Fxm =0
Note: This is different from the Homography estimation
where each point pair contributes 2 equations.
Each point pair (according to epipolar constraint)
contributes only one scalar equation
0>
xm Fxm =0
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?
AX = 0
How do you solve a homogeneous linear system?
AX = 0
Total Least Squares
2
minimize kAxk
2
subject to kxk = 1
How do you solve a homogeneous linear system?
AX = 0
Total Least Squares
2
minimize kAxk
2
subject to kxk = 1
SVD!
How do you solve a homogeneous linear system?
AX = 0
Total Least Squares
2
minimize kAxk
2
subject to kxk = 1
SVD!
How do you solve a homogeneous linear system?
AX = 0
Total Least Squares
2
minimize kAxk
2
subject to kxk = 1
SVD!
Eight-Point Algorithm
0. (Normalize points)
1. Construct the M x 9 matrix A
2. Find the SVD of ATA
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)
Example
epipolar lines
2 3
0.00310695 0.0025646 2.96584
F=4 0.028094 0.00771621 56.3813 5
13.1905 29.2007 9999.79
2 3
343.53
x = 4 221.70 5
1.0
0
l = Fx
2 3
0.0295
=4 0.9996 5
265.1531
0
l = Fx
2 3
0.0295
=4 0.9996 5
265.1531
Where is the epipole?
How would you compute it?
Fe = 0
The epipole is in the right null space of F
How would you solve for the epipole?
(hint: this is a homogeneous linear system)
Fe = 0
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!
Fe = 0
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!
Fe = 0
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
>> [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 >> uu = u(:,3)
smallest eigenvalue ( -0.9660 -0.2586 -0.0005)
>> [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 >> uu = u(:,3)
smallest eigenvalue ( -0.9660 -0.2586 -0.0005)
Epipole projected to image >> uu / uu(3)
coordinates (1861.02 498.21 1.0)
this is where the
other picture is
being taken
Epipole projected to image >> uu / uu(3)
coordinates (1861.02 498.21 1.0)
