# Two-view geometry - Computer graphics Two-view geometry http://graphics.cs.cmu.edu/courses/15-463 15-463, 15-663, 15-862 Computational Photography Fall 2019, Lecture 17

Course announcements Homework 4 was due on Friday. - Any questions? Homework 5 will be posted tonight. - Will be due on Monday November 11th. - Start early: Capturing the photometric stereo data is challenging. Equipment needs for final project: https://docs.google.com/spreadsheets/d/1Mfm35okoWpzHMknBe7wfeGclb

g_sRbk9G0v6mqCBEVM/edit#gid=2055341146 Guest lecture on November 6th: Aswin Sankaranarayanan, Compressive Sensing. Overview of todays lecture Triangulation. Epipolar geometry.

Essential matrix. Fundamental matrix. 8-point algorithm. Slide credits Many of these slides were adapted from: Kris Kitani (16-385, Spring 2017).

Srinivasa Narasimhan (16-720, Fall 2017). Triangulation Triangulation image 1

image 2 Given camera 1 with matrix camera 2 with

matrix Triangulation Which 3D points map to x? image 1

camera 1 with matrix image 2 camera 2 with matrix

Triangulation How can you compute this ray? image 1 camera 1 with matrix

image 2 camera 2 with matrix Triangulation

Create two points on the ray: 1) find the camera center; and 2) apply the pseudo-inverse of P on x. Then connect the two points. + Why does this

point map to x? image 1 camera 1 with matrix image 2

camera 2 with matrix Triangulation How do we find the exact point on the ray?

+ image 1 camera 1 with matrix

image 2 camera 2 with matrix Triangulation Find 3D object point Will the lines intersect?

image 1 camera 1 with matrix image 2

camera 2 with matrix Triangulation Find 3D object point (no single solution due to noise) image 1

camera 1 with matrix image 2 camera 2 with matrix

Triangulation Given a set of (noisy) matched points and camera matrices Estimate the 3D point

known known Can we compute X from a single correspondence x? known

known Can we compute X from two correspondences x and x? known

known Can we compute X from two correspondences x and x? yes if perfect measurements known

known Can we compute X from two correspondences x and x? yes if perfect measurements There will not be a point that satisfies both constraints because the measurements are usually noisy

Need to find the best fit (homogeneous coordinate) Also, this is a similarity relation because it involves homogeneous coordinates (homorogeneo

us coordinate) Same ray direction but differs by a scale factor How do we solve for unknowns in a similarity relation? (homogeneous coordinate)

Also, this is a similarity relation because it involves homogeneous coordinates (inhomogeneo us coordinate) Same ray direction but differs by a scale factor

How do we solve for unknowns in a similarity relation? Remove scale factor, convert to linear system and solve with SVD. (homogeneous coordinate) Also, this is a similarity relation because it involves homogeneous coordinates

(inhomogeneo us coordinate) Same ray direction but differs by a scale factor How do we solve for unknowns in a similarity relation?

Remove scale factor, convert to linear system and solve with SVD! Recall: Cross Product Vector (cross) product takes two vectors and returns a vector perpendicular to both cross product of two vectors

in the same direction is zero remember this!!! Same direction but differs by a scale factor Cross product of two vectors of same direction is zero (this equality removes the scale factor)

Using the fact that the cross product should be zero Third line is a linear combination of the first and second lines. (x times the first line plus y times the second line) One 2D to 3D point correspondence give you 2 equations

Using the fact that the cross product should be zero Third line is a linear combination of the first and second lines. (x times the first line plus y times the second line) One 2D to 3D point correspondence give you 2 equations Now we can make a system of linear equations

(two lines for each 2D point correspondence) Concatenate the 2D points from both images sanity check! dimensions? How do we solve homogeneous linear system?

Concatenate the 2D points from both images How do we solve homogeneous linear system? S V D ! Recall: Total least squares (Warning: change of notation. x is a vector of parameters!)

(matrix form) constraint minimize subject to

minimize (Rayleigh quotient) Solution is the eigenvector corresponding to smallest eigenvalue of Epipolar geometry

Epipolar geometry Image plane Epipolar geometry Baseline

Image plane Epipolar geometry Baseline Image plane

Epipole (projection of o on the image plane) Epipolar geometry Epipolar plane

Baseline Image plane Epipole (projection of o on the image plane)

Epipolar geometry Epipolar line (intersection of Epipolar plane and image plane) Epipolar plane Baseline

Image plane Epipole (projection of o on the image plane) Quiz

What is this? Quiz Epipolar plane Quiz What is this?

Epipolar plane Quiz Epipolar line (intersection of Epipolar plane and image plane) Epipolar plane

Quiz Epipolar line (intersection of Epipolar plane and image plane) Epipolar plane

What is this? Quiz Epipolar line (intersection of Epipolar plane and image plane) Epipolar plane

Epipole (projection of o on the image plane) Quiz Epipolar line (intersection of Epipolar

plane and image plane) Epipolar plane What is this? Epipole (projection of o on the image plane)

Quiz Epipolar line (intersection of Epipolar plane and image plane) Epipolar plane

Baseline Epipole (projection of o on the image plane) Epipolar constraint Potential matches for lie on the epipolar line

Epipolar constraint Potential matches for lie on the epipolar line The point x (left image) maps to a ___________ in the right image The baseline connects the ___________ and ____________ An epipolar line (left image) maps to a __________ in the right image

An epipole e is a projection of the ______________ on the image plane All epipolar lines in an image intersect at the ______________ Converging cameras Where is the epipole in this image? Converging cameras

here! Where is the epipole in this image? Its not always in the image Parallel cameras

Where is the epipole? Parallel cameras epipole at infinity The epipolar constraint is an important concept for stereo

vision Task: Match point in left image to point in right image Left image Right image

How would you do it? Recall:Epipolar constraint Potential matches for lie on the epipolar line The epipolar constraint is an important concept for stereo

vision Task: Match point in left image to point in right image Left image Right image

Want to avoid search over entire image Epipolar constraint reduces search to a single line The epipolar constraint is an important concept for stereo vision Task: Match point in left image to point in right

image Left image Right image Want to avoid search over entire image Epipolar constraint reduces search to a single line

How do you compute the epipolar line? The essential matrix Recall:Epipolar constraint Potential matches for lie on the epipolar line

Given a point in one image, multiplying by the essential matrix will tell us the epipolar line in the second view. Motivation The Essential Matrix is a 3 x 3 matrix that encodes epipolar geometry

Given a point in one image, multiplying by the essential matrix will tell us the epipolar line in the second view. Representing the Epipolar Line

in vector form If the point is on the epipolar line then

Epipolar Line in vector form If the point is on the epipolar line then

Recall: Dot Product dot product of two orthogonal vectors is zero vector representing the line is normal (orthogonal) to the plane

vector representing the point x is inside the plane Therefore: So if

and then So if and

then Essential Matrix vs Homography Whats the difference between the essential matrix and a homography? Essential Matrix vs

Homography Whats the difference between the essential matrix and a homography? They are both 3 x 3 matrices but Essential matrix maps a point to a line

Homography maps a point to a point Where does the Essential matrix come from? Does this look familiar?

Camera-camera transform just like world-camera transform These three vectors are coplanar If these three vectors are coplanar then If these three vectors are coplanar

then Recall: Cross Product Vector (cross) product takes two vectors and returns a vector perpendicular to both If these three vectors are coplanar

then If these three vectors are coplanar then putting it together rigid motion

coplanarity Cross product Can also be written as a matrix multiplication Skew symmetric

putting it together rigid motion coplanarity putting it together rigid motion

coplanarity putting it together rigid motion coplanarity putting it together

rigid motion coplanarity Essential Matrix [Longuet-Higgins 1981] properties of the E matrix

Longuet-Higgins equation (points in normalized coordinates) properties of the E matrix Longuet-Higgins equation Epipolar lines

(points in normalized coordinates) properties of the E matrix Longuet-Higgins equation Epipolar lines

Epipoles (points in normalized camera coordinates) Recall:Epipolar constraint Potential matches for lie on the epipolar line Given a point in one image,

multiplying by the essential matrix will tell us the epipolar line in the second view. Assumption: points aligned to camera coordinate axis (calibrated camera) 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 removed The Essential matrix operates on image points expressed in normalized coordinates

(points have been aligned (normalized) to camera coordinates) camera point imag e point

The Essential matrix operates on image points expressed in normalized coordinates (points have been aligned (normalized) to camera coordinates) camera point

imag e point Writing out the epipolar constraint in terms of image coordinates Same equation works in image coordinates!

it maps pixels to epipolar lines F properties of the E matrix Longuet-Higgins equation Epipolar lines

Epipoles F F F

F F (points in image coordinates) Breaking down the fundamental matrix Depends on both intrinsic and extrinsic parameters

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? S V D

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. Find the SVD of A 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) Eight-Point Algorithm 0. (Normalize points) 1. Construct the M x 9 matrix A

2. Find the SVD of A 3. Entries of F are the elements of column of V corresponding to the least singular value 4. (Enforce rank 2 constraint on See F) HartleyZisserman for why 5. (Un-normalize F) we do this

Eight-Point Algorithm 0. (Normalize points) 1. Construct the M x 9 matrix A 2. Find the SVD of A 3. Entries of F are the elements of column of V corresponding to the least singular value

4. (Enforce rank 2 constraint on F) How do we do this? 5. (Un-normalize F) Eight-Point Algorithm 0. (Normalize points) 1. Construct the M x 9 matrix A 2. Find the SVD of A

3. Entries of F are the elements of column of V corresponding to the least singular value 4. (Enforce rank 2 constraint on F) How do we do this? 5. (Un-normalize F) SVD!

Enforcing rank constraints Problem: Given a matrix F, find the matrix F of rank k that is closest to F, min

2 rank ( ) =

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,

= Eight-Point Algorithm 0. (Normalize points) 1. Construct the M x 9 matrix A 2. Find the SVD of A 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

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?

The epipole is in the right null space of F How would you solve for the epipole? SVD! References Basic reading:

Szeliski textbook, Section 8.1 (not 8.1.1-8.1.3), Chapter 11, Section 12.2. Hartley and Zisserman, Section 11.12.