Perception and Mapping (PM)

3D perception: (passive) multiple view

geometry

Andry Maykol Pinto

amgp@[Link]
 Outline

1 Estimate depth from stereo

Stereopsys
Stereo vision
Disparity equation
Depth accuracy
Correspondence problem

2 Geometry of Multiple Views

Epipolar geometry
The uncalibrated case: fundamental matrix
The calibrated case: essential matrix
Stereo rectification

3 References

2022-10-17 amgp@[Link] 2
 Estimate depth from stereo Geometry of Multiple Views References

Estimate depth from stereo

Estimate depth from stereo

2022-10-17 amgp@[Link] 3
 Estimate depth from stereo Geometry of Multiple Views References

Stereopsys

Humans have two eyes facing forward, resulting in a stereoscopic

vision.

Stereoscopic depth perception: how it works?

Eyes are separated horizontally so that they

look at the world from two different points.

Each eye receives a slightly different picture

of the three-dimensional scene.

2022-10-17 amgp@[Link] 4
Estimate depth from stereo Geometry of Multiple Views References

Stereopsys

The brain fuses retinal images by

converting their disparities into
relative/absolute depth perception.

The phenomenon of retinal

disparity into depth perception is
not entirely understood.

2022-10-17 amgp@[Link] 5
 Estimate depth from stereo Geometry of Multiple Views References

Stereo vision

The depth of a scene point along

the corresponding projection ray
is not directly accessible in a
single image.

Stereo vision is a technique that

estimates the 3D information of
the world from images with
different viewpoints.

2022-10-17 amgp@[Link] 6
 Estimate depth from stereo Geometry of Multiple Views References

Stereo vision

Considering the frontal parallel stereo assumption: undistorted and

coplanar image planes with parallel optical axes that are
row-aligned.

2022-10-17 amgp@[Link] 7
 Estimate depth from stereo Geometry of Multiple Views References

Stereo vision

In this example: principle points (cR and cL) are aligned with the
center of imaging plane.

2022-10-17 amgp@[Link] 8
 Estimate depth from stereo Geometry of Multiple Views References

Stereo vision

The depth (Z) can be found by the triangulation of corresponding

points in two images.
The line of sight starts at center of projection (O);
Each ray/line extends through the principle point of image plane;
The translation/baseline between two centers of projection is T.

Depth can be derived by using similar triangles:

Z X
= L (1)
f x
Z X −T
= (2)
f xR

2022-10-17 amgp@[Link] 9
 Estimate depth from stereo Geometry of Multiple Views References

Disparity equation

f .T
=⇒ Z = L (3)
x − xR
where f is the focal distance and x R and x L are the horizontal
position of points in the left and right image, respectively.

The disparity between views is defined by d = x L − x R .

2022-10-17 amgp@[Link] 10
Estimate depth from stereo Geometry of Multiple Views References

Disparity equation

source: 10.13140/RG.2.2.25020.28809

2022-10-17 amgp@[Link] 11
 Estimate depth from stereo Geometry of Multiple Views References

Disparity equation

For parallel cameras, the point P (XYZ) can be reconstructed from

points in the xLyL-frame:
f .T
Z= L (4)
x − xR
L Z
X =x . (5)
f
L Z
Y =y . (6)
f

2022-10-17 amgp@[Link] 12
Estimate depth from stereo Geometry of Multiple Views References

Depth accuracy

Depth is inversely proportional to disparity;

A non-linear relation between depth and disparity;
High depth resolution only for objects relatively near the
stereo rig.

2022-10-17 amgp@[Link] 13
 Estimate depth from stereo Geometry of Multiple Views References

Depth accuracy
Properties of Depth Accuracy:
Disparity (d) ∝ 1/ Depth;
Depth error (∂Z ) ∝ Depth (Z);
Depth error ∝ 1/baseline.

Z2
∂Z = − ∂d (7)
f .T

Selecting a baseline:
Large baseline: small depth error but less correspondences due
to smaller stereo FOV;
Small baseline: large depth error but large stereo FOV.
2022-10-17 amgp@[Link] 14
 Estimate depth from stereo Geometry of Multiple Views References

Correspondence problem

The 3D information can be extrapolated from two problems:

1) Prior knowledge about the focal distance and the baseline

(camera calibration);

2) Given a pixel pL on left image, the correspondent point pR in

the right image must be determined.

2022-10-17 amgp@[Link] 15
 Estimate depth from stereo Geometry of Multiple Views References

Correspondence problem

The last one is known as the correspondence problem.

2022-10-17 amgp@[Link] 16
 Estimate depth from stereo Geometry of Multiple Views References

Correspondence problem

A variety of search techniques can be used to mach pixels based on

their local appearance and motion properties.

Dense: Similarity metrics (e.g., cross correlation, SSD, SAD, etc);

Sparse: Feature-based techniques.

2022-10-17 amgp@[Link] 17
 Estimate depth from stereo Geometry of Multiple Views References

Correspondence problem

Sparse stereo uses feature matching to recover the coordinate (X,

Y, Z) for each corresponding point pair.

2022-10-17 amgp@[Link] 18
 Estimate depth from stereo Geometry of Multiple Views References

Correspondence problem

Dense stereo recovers the coordinate (X,Y,Z) for (almost) all pixels
in the image.

This problem is more difficult than sparse correspondence since

inferring depth in textureless regions is challenging.

2022-10-17 amgp@[Link] 19
 Estimate depth from stereo Geometry of Multiple Views References

Correspondence problem

Finding stereo correspondences is a computationally expensive

procedure.

How many comparisons needs to be done?

2022-10-17 amgp@[Link] 20
 Estimate depth from stereo Geometry of Multiple Views References

Correspondence problem

Converting this 2D to a 1D searching problem can be done!

The solution is the Epipolar Constraint for Correspondence.

It also generalizes the camera configuration (we do not need to have

parallel optical axes).

2022-10-17 amgp@[Link] 21
 Estimate depth from stereo Geometry of Multiple Views References

Geometry of Multiple Views

Geometry of Multiple Views

2022-10-17 amgp@[Link] 22
 Estimate depth from stereo Geometry of Multiple Views References

Geometry of Multiple Views

There is a geometric constraint that holds among two (or more)

views of the same scene.

is captured by a 3 ×3 matrix known as essential matrix for

calibrated cameras and as fundamental matrix for uncalibrated
cameras.
reduces the search space of correspondences from two dimensions
to one dimension.

2022-10-17 amgp@[Link] 23
 Estimate depth from stereo Geometry of Multiple Views References

Geometry of Multiple Views

All the possible locations of a point seen in one image is a line that
goes through the corresponding point and the epipolar point on the
other image.

This is known as epipolar constraint.

2022-10-17 amgp@[Link] 24
 Estimate depth from stereo Geometry of Multiple Views References

Geometry of Multiple Views

The geometric entities involved in the epipolar geometry:

Conjugate points (1p and 2p) represent at pixel coordinates the

projection of the world point P onto the images planes I1 and
I2, respectively.

Epipoles (1e and 2e) are the intersection points of the line joining
the center of projection (or optical center) {2} and {1}, in
the respective image plane.

Equivalently, 1e is the center of projection of {2} represented in the

image plane I1, in terms of pixel measurements.

2022-10-17 amgp@[Link] 25
 Estimate depth from stereo Geometry of Multiple Views References

Geometry of Multiple Views

Epipolar Plane is the plane defined by both optical centers and the
world point P.

Epipolar Line (1l or 2l ) is obtained by the intersection of the

epipolar plane with the respective image plane.

All the epipolar lines in the image plane intersect the epipole.

2022-10-17 amgp@[Link] 26
 Estimate depth from stereo Geometry of Multiple Views References

Geometry of Multiple Views

The projected 3D point P into the first image plane is 1p.

The projection of the 1p in a second image plane is restricted to the

corresponding epipolar line 2l .

2022-10-17 amgp@[Link] 27
 Estimate depth from stereo Geometry of Multiple Views References

Geometry of Multiple Views

There are 2 methods for extracting 3D information from a pair of

images:

Structure from Motion (SfM) or the uncalibrated case.

the fundamental matrix is obtained from stereo correspondences.
the projective 3D scene is derived from the fundamental matrix.

3D Reconstruction or calibrated case.

the intrinsic parameters of each camera are known.
the essential matrix of the system is extrated from the epipolar
geometry.
the essential matrix provides 3D Euclidean scene.
2022-10-17 amgp@[Link] 28
 Estimate depth from stereo Geometry of Multiple Views References

The Uncalibrated Case

1) The uncalibrated case:

F is a 3 × 3 matrix called as fundamental matrix that contains the:
the instrinsic information of both cameras;
translation and rotation the relate the two viewpoints in space.

The epipolar relationship can be defined by:

2p
eT F 1pe = 0 (8)
where 1pe and 2pe are the image points 1p and 2p, expressed in pixels
(homogeneous coordinates).

2022-10-17 amgp@[Link] 29
 Estimate depth from stereo Geometry of Multiple Views References

The Uncalibrated Case

The last terms (F 1pe) represent the epipolar line in the second
image:

l∼
2e
= F 1pe (9)

The epipolar line in the first image plane of the point viewed by the
second view:

l∼
1e
= FT 2pe (10)

2022-10-17 amgp@[Link] 30
 Estimate depth from stereo Geometry of Multiple Views References

The Uncalibrated Case

Note:

Every pixel point p = (u, v ) on a plane can be represented by their

homogeneous coordinates pe = (u, v , 1).

Homogeneous coordinates means that (e p∼= αep ) the scale is

unimportant. In this context, the operator ∼
= is equal up to a
non-zero scale factor α.

2022-10-17 amgp@[Link] 31
 Estimate depth from stereo Geometry of Multiple Views References

The Uncalibrated Case

The fundamental matrix can be constructed from both camera

Projection Matrix (M) matrices.

pe = (u, v , 1)T ∼ M P (11)

Both cameras are separated by R and t:

M1 = K1 [I |0] (12)
M2 = K2 [R|t] (13)

2022-10-17 amgp@[Link] 32
 Estimate depth from stereo Geometry of Multiple Views References

The Uncalibrated Case

The fundamental matrix is given by the epipolar constraint:

F = K−T
2 [t]× R K −1
1 (14)

The proof is available on Zhengyou Zhang (2016)

[Link]

2022-10-17 amgp@[Link] 33
 Estimate depth from stereo Geometry of Multiple Views References

Geometry of Multiple Views

t = [tx , ty , tz ] is the translation vector.

[t]× is a skew-symmetrical matrix;

A skew-symmetrical matrix holds the property: [t]T

× = − [t]×.

 
0 −tz ty
[t]× =  tz 0 −tx  (15)
−ty tx 0

2022-10-17 amgp@[Link] 34
 Estimate depth from stereo Geometry of Multiple Views References

Geometry of Multiple Views

The F encodes the epipoles (F1e = 0 and FT 2e = 0):

singular vectors with zero singular values are epipoles (1e and 2e);
  T 
h i σ1 v1
F = UΣVT = u1, u2,2 e  σ2   vT (16)
 
2 
0 1 eT

2e is the projection of t into image 2. It is defined as the left

singular vector of E (with 0 singular value).
1e is the zero right singular vector.

2022-10-17 amgp@[Link] 35
 Estimate depth from stereo Geometry of Multiple Views References

The Uncalibrated Case

Properties of the fundamental matrix:

is unique up to scale.
is rank 2 ([t]× is rank 2).
has nine elements that are not independent det(F) = 0.
has seven degrees of freedom.
2 for each epipole
3 for the homography that relates two image planes.
the scale parameter is missing from the homograpy (4
parameters).

At least seven correspondences to solve a homogeneous system

equation.
2022-10-17 amgp@[Link] 36
 Estimate depth from stereo Geometry of Multiple Views References

Geometry of Multiple Views

There are several methods to compute the F:

7-points
8-points
Levenberg-Marquardt
Least-Median-Squares
Random Sampling

2022-10-17 amgp@[Link] 37
 Estimate depth from stereo Geometry of Multiple Views References

The Uncalibrated Case

This is the uncalibrated case of the epipolar geometry because the

intrinsic calibration matrices K1 and K2 are unknown for both
cameras, see equation 14.

The fundamental matrix depends on:

the intrinsic parameters of both cameras (if the images were
captured by different cameras);
the location of the second image plane (the translation vector t);
the rotation matrix R of the second image relative to the first
plane.

2022-10-17 amgp@[Link] 38
 Estimate depth from stereo Geometry of Multiple Views References

Geometry of Multiple Views

Finally, this matrix is very useful to finding features correspondences

because they must lie on the corresponding epipolar lines, for
instance, to satisfy the relation defined by Equation 8 the feature
1pe must have its conjugate point on the epipolar line 2e li .
i

2022-10-17 amgp@[Link] 39
 Estimate depth from stereo Geometry of Multiple Views References

Calibrated Case

2) The calibrated case:

Analogous to the uncalibrated case, the epipolar constraint can be

defined by:
2pe T E 1pe = 0 (17)
c c

where E is a 3 × 3 matrix called essential matrix.

1pe = (x , y , 1)T and 2pe = (x , y , 1)T are the two normalized

c 1 1 c 2 2
camera points of 1p and 2p, expressed in homogeneous coordinates.

x1 = X1/Z1 (18)

2022-10-17 amgp@[Link] 40
 Estimate depth from stereo Geometry of Multiple Views References

Calibrated Case

The intrinsic calibration matrices K1 and K2 are known.

E∼
= KT
2 F K1 (19)

E = [t]× R (20)

2022-10-17 amgp@[Link] 41
 Estimate depth from stereo Geometry of Multiple Views References

Calibrated Case

The E maps a point 1pec (in image 1) into a line 2e

l in image 2.

1pe T . 1e
l =0 (21)
c

2pe T . 2e
l =0 (22)
c

2022-10-17 amgp@[Link] 42
 Estimate depth from stereo Geometry of Multiple Views References

Calibrated Case

The E is purely geometric which relates physical coordinates (e.g.,

seen by left camera to a point in the coordinate of the right
camera):

the translation t;
the rotation R of the second view relative to the first in global
coordinates system.

2022-10-17 amgp@[Link] 43
 Estimate depth from stereo Geometry of Multiple Views References

Stereo rectification

A stereo rig will almost never be

exactly configured as frontal
parallel.

Physical alignment facilitates

the mathematical treatment.
Lens distortions are removed.
Images are aligned (horizontal
epipolar lines) and
synchronized.

2022-10-17 amgp@[Link] 44
 Estimate depth from stereo Geometry of Multiple Views References

References

Zhengyou Zhang, Epipolar Geometry, Springer, DOI:

[Link]

Chapter 14 of Robotics, Vision and Control, Peter Corke, Springer, DOI

10.1007/978-3-642-20144-8

Chapter 7 of Computer Vision: Algorithms and Applications, Richard Szeliski, 2010 Springer.

2022-10-17 amgp@[Link] 45
 Thank you!

Andry Maykol Pinto

amgp@[Link]