Epipolar geometry Binocular stereo Special case: cameras are parallel to each other and translated along X axis X axis Z axis

Stereo head Kinect / depth cameras Perspective projection in rectified cameras Without loss of generality, assume origin is at pinhole of 1st camera

X coordinate differs by tx/Z Y coordinate is the same! Perspective projection in rectified cameras X coordinate differs by tx/Z That is, difference in X coordinate is inversely proportional to depth Difference in X coordinate is called disparity

Translation between cameras (tx) is called baseline disparity = baseline / depth The NCC cost volume Consider M x N image Suppose there are D possible disparities. For every pixel, D possible scores Can be written as an M x N x D array To get disparity, take max along 3rd axis

Computing the NCC volume 1. For every pixel (x, y) 1. For every disparity d 1. 2. 3. Get normalized patch from image 1 at (x, y)

Get normalized patch from image 2 at (x + d, y) Compute NCC Computing the NCC volume 1. For every disparity d 1. For every pixel (x, y) 1. 2. 3.

Get normalized patch from image 1 at (x, y) Get normalized patch from image 2 at (x + d, y) Compute NCC Assume all pixels lie at same disparity d (i.e., lie on same plane) and compute cost for each Plane sweep stereo

Perspective projection in rectified cameras For rectified cameras, correspondence problem is easier Only requires searching along a particular row. Perspective projection in rectified

cameras What about nonrectified cameras? Is there an equivalent? For rectified cameras, correspondence problem is easier Only requires searching along a particular row.

Epipolar constraint Reduces 2D search problem to search along a particular line: epipolar line Epipolar constraint True in general! Given pixel (x,y) in one image, corresponding pixel in the

other image must lie on a line Line function of (x,y) and parameters of camera These lines are called epipolar line Epipolar geometry Epipolar geometry - why? For a single camera, pixel in image plane must correspond to point somewhere along a ray

Epipolar geometry When viewed in second image, this ray looks like a line: epipolar line The epipolar line must pass through image of the first camera in the second image - epipole Epipole Epipolar line

Epipolar geometry Given an image point in one view, where is the corresponding point in the other view? ? epipolar line C

/ C epipole baseline A point in one view generates an epipolar line in the other view The corresponding point lies on this line

Epipolar line Epipolar constraint Reduces correspondence problem to 1D search along an epipolar line Epipolar lines Epipolar lines

Epipolar lines Epipole Epipolar geometry continued Epipolar geometry is a consequence of the coplanarity of the camera centres and scene point

X x C x/ C/

The camera centres, corresponding points and scene point lie in a single plane, known as the epipolar plane Nomenclature X left epipolar line l/

x right epipolar line x/ e e/

C C/ The epipolar line l/ is the image of the ray through x The epipole e is the point of intersection of the line joining the camera centres with the image plane this line is the baseline for a stereo rig, and the translation vector for a moving camera

The epipole is the image of the centre of the other camera: e = PC/ , e/ = P/C The epipolar pencil X e e

/ baseline As the position of the 3D point X varies, the epipolar planes rotate about the baseline. This family of planes is known as an epipolar pencil (a pencil is a one parameter family). All epipolar lines intersect at the epipole.

The epipolar pencil X e e /

baseline As the position of the 3D point X varies, the epipolar planes rotate about the baseline. This family of planes is known as an epipolar pencil (a pencil is a one parameter family). All epipolar lines intersect at the epipole. Epipolar geometry - the math Assume intrinsic parameters K are identity

Assume world coordinate system is centered at 1st camera pinhole with Z along viewing direction Epipolar geometry - the math Assume intrinsic parameters K are identity Assume world coordinate system is centered at 1st camera pinhole with Z along viewing direction Epipolar geometry - the math

Assume intrinsic parameters K are identity Assume world coordinate system is centered at 1st camera pinhole with Z along viewing direction Epipolar geometry - the math Assume intrinsic parameters K are identity Assume world coordinate system is centered at 1st camera pinhole with Z along viewing direction

Epipolar geometry - the math Assume intrinsic parameters K are identity Assume world coordinate system is centered at 1st camera pinhole with Z along viewing direction Epipolar geometry - the math 0 0

Epipolar geometry - the math Can we write this as matrix vector operations? Cross product can be written as a matrix Epipolar geometry - the math Can we write this as matrix vector operations? Dot product can be written as a vector-vector times

Epipolar geometry - the math Can we write this as matrix vector operations? Dot product can be written as a vector-vector times Epipolar geometry - the math Epipolar geometry - the math Homogenous Homogenous

coordinates of coordinates of point in image 2 point in image 1 Essential matrix Epipolar constraint and epipolar lines Consider a known, fixed pixel in the first image

What constraint does this place on the corresponding pixel? where What kind of equation is this? Epipolar constraint and epipolar

lines Consider a known, fixed pixel in the first image where Line! Epipolar constraint: putting it all together

If p is a pixel in first image and q is the corresponding pixel in the second image, then: qTEp = 0 E = [t]XR For fixed p, q must satisfy: qTl = 0, where l = Ep For fixed q, p must satisfy: lTp = 0 where lT = qTE, or l = Etq These are epipolar lines!

Epipolar line in 2nd image Epipolar line in 1st image Essential matrix and epipoles E = [t]XR Ep is an epipolar line in 2nd image

All epipolar lines in second image pass through c2 c2 is epipole in 2nd image Essential matrix and epipoles E = [t]XR ETq is an epipolar line in 1st image All epipolar lines in first image pass through c1 c1 is the epipole in 1st image

Epipolar geometry - the math We assumed that intrinsic parameters K are identity What if they are not? Fundamental matrix Fundamental matrix

Fundamental matrix Fundamental matrix Fundamental matrix Fundamental matrix Fundamental matrix result

Properties of the Fundamental Matrix is the epipolar line associated with T is the epipolar

line associated with 0 48 Properties of the Fundamental Matrix

is the epipolar line associated with T is the epipolar line associated with and

All epipolar lines contain epipole 0 Properties of the Fundamental Matrix

is the epipolar line associated with T is the epipolar line associated with and is rank 2

0 50 Why is F rank 2? F is a 3 x 3 matrix But there is a vector c1 and c2 such that Fc1 = 0 and FTc2 = 0 Fundamental matrix song

Estimating F If we dont know K1, K2, R, or t, can we estimate F for two images? Yes, given enough correspondences Estimating F 8-point algorithm The fundamental matrix F is defined by

x' Fx 0 for any pair of matches x and x in two images. Let x=(u,v,1)T and x=(u,v,1)T, f11 F f 21

f 31 f12 f 22 f 32 f13 f 23 f 33

each match gives a linear equation uu ' f11 vu ' f12 u ' f13 uv' f 21 vv' f 22 v' f 23 uf 31 vf 32 f 33 0 8-point algorithm u1u1 v1u1 u1 u1v1 v1v1 v1 u1 u u v u u u v v v v u 2 2 2

2 2 2 2 2 2 2 2

u n u n vn u n u n u n v n v n v n v n u n

v1 1 v2 1 vn 1

In reality, instead of solvingAf 0, we seek f to A Af minimize , least eigenvector of A.

f11 f12 f13 f 21 f 22 0 f 23 f 31

f 32 f 33 8-point algorithm Problem? F should have rank 2 To enforce that F is of rank 2, F is replaced by F that minimizes F F ' subject to the rank constraint.

This is achieved by SVD. Let F UV where 0 1 0 1 0 0 0 2 0 ' 0 2 0 , let

0 0 0 3 0 0 then F ' U' V

is the solution. , Recovering camera parameters from F/E Can we recover R and t between the cameras from F? No: K1 and K2 are in principle arbitrary matrices

What if we knew K1 and K2 to be identity? Recovering camera parameters from E t is a solution to ETx = 0 Cant distinguish between t and ct for constant scalar c How do we recover R?

Recovering camera parameters from E We know E and t Consider taking SVD of E and [t]X Recovering camera parameters from E

t is a solution to ETx = 0 Cant distinguish between t and ct for constant scalar c 8-point algorithm Pros: it is linear, easy to implement and fast Cons: susceptible to noise Degenerate: if points are on same plane

Normalized 8-point algorithm: Hartley Position origin at centroid of image points Rescale coordinates so that center to farthest point is sqrt (2) Structure-from-motion Given 2 (or more) images from unknown cameras and with 3D world unknown Can we recover both the cameras and the 3D world structure?

Step 1: Get correspondences Step 2: Estimate Essential matrix, get R and t (assuming K known) Step 3: Use calibrated cameras + correspondence to get 3D locations of points