Epipolar Geometry

We consider two perspective images of a scene as taken from a stereo

pair of cameras (or equivalently, assume the scene is rigid and imaged
with a single camera from two different locations).
p
X

Left Image Right Image

q
X
L
R
e(p )
p Epipolar
L Lines
p L
e(q )
L R
q q

Left NP Right Epipole Right NP

~ p which is imaged in the “left” camera at p~ L,

Given a scene point X
where could the image of the same point be in the right camera? We
denote this point as p~ R . The relationship between such corresponding
image points turns out to be both simple and useful.

Readings: See Sections 10.1 and 15.6 of Forsyth and Ponce.

2503: Epipolar Geometry c A.D. Jepson and D.J. Fleet, 2006 Page: 1
 Epipolar Line
Two Perspective Cameras: Let d~ L and d~ R be the 3D positions of the
nodal points of the left and right cameras. As discussed earlier in this
course, we model perspective projection by placing the image plane in
~ p is then imaged in the left
front of the nodal point. A scene point X
camera at p~ L , which is the point of intersection of the the image plane
with the line containing the scene point X ~ p and the nodal point d~ L (see
previous figure).

Epipolar Line: If we know the left image point p~ L , then the corre-
sponding scene point X ~ p is constrained to be on a ray through this
image point. The position of X~ p on this ray is unknown. However, the
image of this whole ray is a line in the right image, namely the epipolar
line e(~p L ).

Epipolar Plane: An alternative geometric view is to consider the 3D

plane containing the image point p~ L along with left and right nodal
points d~ L and d~ R . Then the scene point X
~ p and the corresponding right
image point p~ R must also be on this epipolar plane. The intersection
of this epipolar plane with the right image plane provides the epipolar
line e(~p L ).

2503: Epipolar Geometry Page: 2

 Epipolar Constraint

Epipolar Constraint: Suppose p~ L is the left image position for some

~ p. Then the corresponding point p~ R in the right image
scene point X
must lie on the epipolar line e(~p L).

R
Epipolar p e(pL)
Lines
L
e(q )
R
Right Epipole q

Right Image Plane

Notice the epipolar line e(~p L ) depends on the position of the point in
the left image. For example, another image point ~q L generally gives
rise to a different epipolar line e(~q L ).

Epipole: All the epipolar lines in the right image pass through a single
point (possibly at infinity) called the right epipole. This point is given
by the intersection of the line containing the two nodal points d~ L and
d~ R with the right image plane (see figures above and on p.1). (Notice
that the line containing the two nodal points must be in all the epipolar
planes, and hence its image must be on all the epipolar lines.)

2503: Epipolar Geometry Page: 3

 Constraints on Correspondence

Clearly we can swap the labels “left” and “right” in the above analysis,
it does not matter which image we start with.

The previous analysis showed there is a mapping between points in one

image and epipolar lines in the other. Such a mapping would be compu-
tationally useful since it provides strong constraints on corresponding
points in two images of the same scene.

• For example, for each point in one image we could limit the search
for a corresponding point in the second image to just the epipolar
line (instead of naively searching the whole second image).

• Alternatively, given a set of hypothesized correspondences, we can

use the epipolar constraints to identify (some) outliers.

To achieve these applications we need to be able to estimate the map-

ping from points to epipolar lines, which is what we consider next. We
begin with the case of two calibrated cameras, and then consider the
uncalibrated case.

2503: Epipolar Geometry Page: 4

 Camera Coordinates and Image Formation

Here we apply the image formation model introduced earlier to the

stereo imaging setup. We introduce three coordinate frames:
~ w,
• A world coordinate frame X

• The left and right camera coordinate frames, X

~ cL and X
~ cR .

The origins of the left and right camera coordinate frames are at their
nodal points, and their z-axes are aligned with the two optical axes.
Therefore, as discussed in the image formation notes, given a 3D point
~ L in the left camera’s coordinates, the left image of this point is at
X c
 
pL1,c
L
f ~L  
p~c = L Xc =  p2,c 
L  L
. (1)
X3,c
fL

Here, f L is the distance between the image plane and the nodal point
for the left camera.

A similar expression holds for the location of the right image point.
However, before applying this expression, the 3D point X ~ L must be
c
transformed from the left to the right camera’s coordinates. We do this
via the world coordinate frame X ~ w.

2503: Epipolar Geometry Page: 5

 External Calibration

The external calibration parameters for the left camera provide the 3D
rigid coordinate transformation from world coordinates to the left cam-
era’s coordinates (see the image formation notes)

~ L = M L [X
X ~ T , 1]T , (2)
c ex w

L
with Mex a 3 × 4 matrix of the form
 
L
Mex = RL −RLd~Lw . (3)

Here RL is a 3 × 3 rotation matrix and d~Lw is the location of the nodal

point for the left camera in world coordinates.

Similarly, the 3 × 4 matrix Mex

R
provides the external calibration of the
right camera.

2503: Epipolar Geometry Page: 6

 The Essential Matrix

Let p~wL and p~wR be the left and right image points (written in world
coordinates) for some given 3D point X ~ w . Then the epipolar constraint
states that these two image points and the two nodal points d~wL , d~wR are
all coplanar. This constraint can be written as
h i
~ L T ~ L ~ R R ~
(~pw − dw ) (dw − dw ) × (~pw − dw ) = 0,
L R
(4)

where ’×’ denotes the cross-product.

We rewrite this by replacing the cross-product by an equivalent matrix-

vector product,
 
0 −T3 T2
 
T~ × p~ = [T~ ]×p~, where [T~ ]× 
=  T3 0 −T1 
.
−T2 T1 0

Also, we use (2) and (3) to write p~wL − d~wL in terms of the left camera’s
coordinates as p~ L − d~ L = (RL )T p~ L . Using the analogous expression
w w c
for the right image point, we find that (4) can be rewritten as

(~pcL)T E~pcR = 0, (epipolar constraint) (5)

where E is the 3 × 3 essential matrix (or E-matrix)

E = RL[d~wL − d~wR ]× (RR )T . (6)

2503: Epipolar Geometry Page: 7
 Properties of the Essential Matrix

Clearly, any nonzero scalar multiple of the E-matrix provides an equiv-

alent epipolar constraint (5).

From (6) it follows that the E-matrix has rank 2, with two equal non-
zero singular values and one singular value at 0.

Given a point p~cL in the left image, the epipolar constraint (5) states that
the corresponding point ~pcR in the right image must be on the line

~aT p~cR = a1pR R

1,c + a2 p2,c + a3 f
R
= 0,

where ~a = E T p~cL.

The right epipole ~ecR is a null vector for E. It can be written as

R ~L T
~ecR = αMex [(dw ) , 1]T = αRR (d~wL − d~wR ),

where α is a nonzero constant. Notice, using (6),

~aT ~ecR = (~pcL)T E~ecR = α(~pcL)T RL [d~wL −d~wR]× (RR )T RR (d~wL −d~wR) = 0,

so the epipole is on every epipolar line.

Given a point p~cR in the right image, analogous expressions give the
epipolar line in the left image and the left epipole.

2503: Epipolar Geometry Page: 8

 Internal Calibration

We wish to rewrite the epipolar constraint (5) in terms of homogeneous

pixel coordinates ~x L = (xL, y L , 1)T , where (xL, y L ) are the coordi-
nates of an image point in terms of pixels.

L
The internal calibration matrix Min provides the transformation from
camera coordinates to homogeneous pixel coordinates (see the image
formation notes),
~x L = Min
L L
p~c . (7)
For example, a camera with rectangular pixels of size 1/sx by 1/sy ,
with nodal distance f , and piercing point (ox, oy ) (i.e., the intersection
of the optical axis with the image plane provided in pixel coordinates)
has the internal calibration matrix
 
sx 0 ox/f
 
Min =   0 sy oy /f
.
 (8)
0 0 1/f
We can use (7) to rewrite the epipolar constraint in terms of pixel coor-
dinates.

2503: Epipolar Geometry Page: 9

 The Fundamental Matrix

By using (7) we can rewrite the epipolar constraint (5) in terms of ho-
mogeneous pixel coordinates in the left and right images as

(~x L)T F ~x R = 0. (9)

Here the fundamental matrix (or F-matrix) is given by

L −T R −1
F = (Min ) E(Min ) , (10)

where the notation M −T denotes the transpose of the inverse M .

Similar to the E-matrix, the F-matrix has rank 2, but the two nonzero
singular values need not be equal. The over-all scale of the F-matrix
does not effect the epipolar constraint (9). So there are 7 remaining
degrees of freedom in F .

The right (left) null vector of F gives the homogeneous pixel coordi-
nates for the right (left, resp.) epipole.

More explicitly, for example, the epipolar constraint (9) states that,
given a point ~x L in the left image, the corresponding point ~x R in the
right image must be on the epipolar line

~aT ~x R = a1xR + a2y R + a3 = 0,

where ~a = F T ~x L .
2503: Epipolar Geometry Page: 10
 Estimating the Fundamental Matrix
Given corresponding image points {(~xkL, ~xkR )}K
k=1 we wish to estimate
the F-matrix.

Gold Standard Approach: Suppose the noise in the point positions

~xkµ , for µ = L, R is independent and normally distributed with mean
zero and covariance Σµk. (Note that there is no noise in the third com-
ponent of ~xkµ .) That is,

~xkµ = m
~ kµ + ~nkµ , (11)

~ kµ is the true position of the point and ~nkµ is the mean zero
where m
noise. Then the (maximum likelihood) problem is to find F ∈ <3×3
~ kµ for k = 1, . . . , K and µ = L, R, such that the following
along with m
objective function is minimized:
X X
K
O ≡ ~ kµ )T (Σµk)† (~xkµ − m
(~xkµ − m ~ kµ ) (12)
µ∈{L,R} k=1

where (Σµk )† denotes the pseudo-inverse. We minimize this objective

function O subject to the epipolar constraints:

~ Lk)T F m
(m ~Rk = 0, k = 1, . . . , K, (13)
rank(F) = 2 (14)

~ µk’s, with nonlinear

Thus O is a quadratic objective function for the m
constraints (13) and (14).
2503: Epipolar Geometry Page: 11
 Alternative Estimation Approaches
We would like to be able to avoid a nonlinear optimization problem.
The cost of this will be to obtain a noiser estimate of the F -matrix than
the one provided by the previous gold standard approach.

An initial simplification is to ignore the noise in ~xkL for the purpose of

~ Lk). That is, we say the corresponding
estimating the epipolar line e(m
right image point ~xkR should be close to e(~xLk ) instead of e(m
~ Lk). This
epipolar line e(~xLk) can be written as

(~n T , c)~x R = 0, (15)

where !
~n 1 T L
= F ~xk . (16)
c ||(I2 ~0)F T ~xkL||2
The normalization in (16) simply ensures ~n is the unit normal to the
epipolar line e(~xkL). Therefore

d(~xkR , e(~xkL )) ≡ (~n T , c)~x R , (17)

is the perpendicular distance between ~xkR and the epipolar line e(~xkL).

We could try to minimize the sum of squares of these epipolar distances

d(~xkR , e(~xkL )) for k = 1, . . . , K. However, due to the normalization
factor in (16), the objective function is not quadratic in the unknown F .

2503: Epipolar Geometry Page: 12

 Algebraic Error
Consider the reweighted epipolar distance objective function
X
K
O(F ) ≡ w(~xkL)d2(~xkR , e(~xkL ))
k=1
XK
 
L T R 2
= (~xk ) F ~xk . (18)
k=1

Here the weights w(~xkL ) are chosen to provide a quadratic objective

function O(F ). That is,

w(~xkL) = ||(I2 ~0)F T ~xkL ||22. (19)

This objective function corresponds to the algebraic error in the noise-

less epipolar constraint (9).

In terms of maximum likelihood estimation, Equation (18) is appro-

priate when the variances of the error in algebraic constraints (9) are
roughly constant (and the means are zero). If the variances deviate
significantly from this, then we will get poor estimates for F .

Indeed, without any rescaling (which we discuss next), this approach

provides excessively noisy estimates of F .

2503: Epipolar Geometry Page: 13

 Renormalized 8-Point Algorithm
Hartley (PAMI, 1997) introduced the following algorithm. Given cor-
responding points {(~xkL, ~xkR )}K
k=1 with K ≥ 8,

1. Recenter and rescale the image points using M µ, µ = L, R, such

that  
s µ
0 bµ1
 
M µ
= 
0 sµ bµ2 ,
 (20)
0 0 1
with
1 X µ µ
K
M ~xk = (0, 0, 1)T , (21)
K
k=1

1 XK
[M µ~xkµ − (0, 0, 1)T ]2∗ = (σ12, σ22, 0)T , (22)
K
k=1

where σ12 + σ22 = 2. Here [...]2∗ denotes the square of each element.
Rescale the image points using ~rkµ = M µ~xkµ for k = 1, . . . , K and
µ = L, R.

2. Minimize the objective function O(F̂ )

K h
X i2
O(F̂ ) ≡ (~rkL)T F̂ ~rkR . (23)
k=1

Note this is a linear least squares problem for the elements of F̂ .

(Continued on next page.)
2503: Epipolar Geometry Page: 14
 Renormalized 8-Point Algorithm (Cont.)

3. Project F̂ to the nearest rank 2 matrix (with the error measured in

the Frobenius norm):

(a) Form the SVD of F̂ = U ΣV T . In general Σ = diag[σ12, σ22, σ32]

with σi2 ≥ σi+1
2
for i = 1, 2.
(b) Reset σ3 = 0.
(c) Assign F̂ to be U ΣV T .

4. Undo the normalization of the image points,

F = (M L )T F̂ M R (24)

This algorithm has been found to provide reasonable estimates for the
F -matrix given correspondence data with small amounts of noise (see
Hartley and Zisserman, Multiple View Geometry in Computer Vision,
Camb. Univ. Press., 2000).

It is not robust to outliers.

In order to deal with outliers, we apply the Random Sample Consensus

(RANSAC) algorithm to the estimation of the F -matrix.

2503: Epipolar Geometry Page: 15

 RANSAC Algorithm for the F-Matrix
Suppose we are given corresponding points {(~xkL, ~xkR )}K
k=1 , which may
include outliers. Let  > 0 be an error tolerance, and T be the number
of trials to do.

Loop T times:

1. Randomly select 8 pairs (~xkL , ~xkR ).

2. Use the renormalized algorithm to solve for F using only the eight
selected pairs of points.

3. Compute perpendicular errors d(~xkR , e(~xkL )) and d(~xkL, e(~xkR )), see
(16) and (17) for 1 ≤ k ≤ K.

4. Identify inliers

In = {k : d(~xkL, e(~xkR )) <  and d(~xkR , e(~xkL)) < , 1 ≤ k ≤ K}.

5. If the number of inliers |In| is the largest seen so far, remember the
current estimate of F and the inlier set In.

End loop.
6. Solve for F using all pairs with k ∈ In (i.e., all inliers). Re-solve for
the inlier set In as done in steps 3 and 4 above.

Can iterate step 6 until the set of inliers In does not change.
2503: Epipolar Geometry Page: 16
 RANSAC: How Many Trials?
Suppose our data set consists of a fraction p inliers, and 1 − p outliers.

How many trials T should be done so that we can be reasonably confi-

dent that at least one sampled data set of size d = 8 was all inliers?

The probability of choosing d = 8 inliers from such a population is

roughly pd when K >> d (it is exactly pd if we sample with replace-
ment). So the probability that a given trial of RANSAC fails to select
d inliers is 1 − pd. Therefore, the probability that RANSAC failed to
have any trial with d inliers is (1 − pd)T . In other words, the probability
P0 that at least one of the RANSAC trials will be a success is

P0 = 1 − (1 − pd)T

Given an estimate for the fraction of inliers p in the data set, we could
then choose T such that P0 > 0.95, say. That is,

T > log(1 − P0)/ log(1 − pd).

For example, for 70% inliers and d = 8, we require T > 50. Alter-
natively, if we only have 50% inliers, the same formula states that T
should be chosen to be at least 766.

2503: Epipolar Geometry Page: 17

 Example
Given local image features, RANSAC was used to fit the F -matrix.

Here have choosen random colours to circle image features. The same
colour is then used for the corresponding point in the other image, and
also for the epipolar lines generated from these two points.

Note:
1. By construction, each point lies close to the epipolar line generated
by its corresponding point in the other image.
2. A visual sanity check can be obtained by sampling other points on
one epipolar line, and checking that they also appear somewhere
along the corresponding epipolar line. This must be the case since,
when the F-matrix is correct, both epipolar lines correspond to the
intersection of the scene with the epipolar plane. (Compare the
current fit with the result of a poor fit shown on p.19.)
3. The intersection of the epipolar lines corresponds to the epipole in
each image. The nodal point of the second camera is on the line (in
world coordinates) containing the nodal point of the first camera
and the epipole in the first image.
2503: Epipolar Geometry Page: 18
 Poorly Fitted F-Matrix
The same local image features were used as in the previous example,
and RANSAC was used to fit the F -matrix (but with only 10 trials).
The solution it found is displayed below:

Note:
1. The feature points are still near the corresponding epipolar lines.
Here 82% of the data points are within 4 pixels of the correspond-
ing epipolar line. In contrast, the solution on the previous page
achieved 94%.
2. However, the visual sanity check fails. This is most apparent for
(proposed) epipolar planes which intersect the scene over a large
range of depths. For example, consider the (proposed) epipolar
planes which cut across the tower at the top of the image and at
least one of the buildings in front.

2503: Epipolar Geometry Page: 19