对极几何和立体视觉

1 .Epipolar Geometry and Stereo Vision Computer Vision Jia-Bin Huang, Virginia Tech Many slides from S. Seitz and D. Hoiem

2 .Last class: Image Stitching Two images with rotation/zoom but no translation f f . x x X

3 .This class: Two-View Geometry Epipolar geometry Relates cameras from two positions Stereo depth estimation Recover depth from two images

4 .This class: Two-View Geometry Epipolar geometry Relates cameras from two positions Stereo depth estimation Recover depth from two images

5 .This class: Two-View Geometry Epipolar geometry Relates cameras from two positions Stereo depth estimation Recover depth from two images

6 .Correspondence Problem We have two images taken from cameras with different intrinsic and extrinsic parameters How do we match a point in the first image to a point in the second? How can we constrain our search? x ?

7 .Key idea: Epipolar constraint

8 .Potential matches for x have to lie on the corresponding line l’ . Potential matches for x’ have to lie on the corresponding line l . Key idea: Epipolar constraint x x’ X x’ X x’ X

9 . Epipolar Plane – plane containing baseline (1D family) Epipoles = intersections of baseline with image planes = projections of the other camera center Baseline – line connecting the two camera centers Epipolar geometry: notation X x x’

10 . Epipolar Lines - intersections of epipolar plane with image planes (always come in corresponding pairs) Epipolar geometry: notation X x x’ Epipolar Plane – plane containing baseline (1D family) Epipoles = intersections of baseline with image planes = projections of the other camera center Baseline – line connecting the two camera centers

11 .Example: Converging cameras

12 .Example: Motion parallel to image plane

13 .Example: Forward motion What would the epipolar lines look like if the camera moves directly forward?

14 .e e’ Example: Forward motion Epipole has same coordinates in both images. Points move along lines radiating from e: “Focus of expansion”

15 .X x x’ Epipolar constraint: Calibrated case Given the intrinsic parameters of the cameras : Convert to normalized coordinates by pre-multiplying all points with the inverse of the calibration matrix; set first camera’s coordinate system to world coordinates Homogeneous 2d point (3D ray towards X) 2D pixel coordinate (homogeneous) 3D scene point 3D scene point in 2 nd camera’s 3D coordinates

16 .X x x’ Epipolar constraint: Calibrated case Given the intrinsic parameters of the cameras: Convert to normalized coordinates by pre-multiplying all points with the inverse of the calibration matrix; set first camera’s coordinate system to world coordinates Define some R and t that relate X to X’ as below for some scale factor

17 .Epipolar constraint: Calibrated case x x’ X (because and are co-planar)          

18 .Essential Matrix (Longuet-Higgins, 1981) Essential matrix X x x’

19 .X Properties of the Essential matrix E x’ is the epipolar line associated with x’ ( l = E x’ ) E T x is the epipolar line associated with x ( l’ = E T x ) E e ’ = 0 and E T e = 0 E is singular (rank two) E has five degrees of freedom (3 for R, 2 for t because it’s up to a scale) Drop ^ below to simplify notation x x’ Skew-symmetric matrix

20 .Epipolar constraint: Uncalibrated case If we don’t know K and K’ , then we can write the epipolar constraint in terms of unknown normalized coordinates: X x x’

21 .The Fundamental Matrix Fundamental Matrix ( Faugeras and Luong , 1992) Without knowing K and K’, we can define a similar relation using unknown normalized coordinates

22 .Properties of the Fundamental matrix F x’ is the epipolar line associated with x’ ( l = F x’ ) F T x is the epipolar line associated with x ( l’ = F T x ) F e’ = 0 and F T e = 0 F is singular (rank two): det (F)=0 F has seven degrees of freedom: 9 entries but defined up to scale, det (F)=0 X x x’

23 .Estimating the Fundamental Matrix 8-point algorithm Least squares solution using SVD on equations from 8 pairs of correspondences Enforce det (F)=0 constraint using SVD on F 7-point algorithm Use least squares to solve for null space (two vectors) using SVD and 7 pairs of correspondences Solve for linear combination of null space vectors that satisfies det (F)=0 Minimize reprojection error Non-linear least squares Note: estimation of F (or E) is degenerate for a planar scene.

24 .8-point algorithm Solve a system of homogeneous linear equations Write down the system of equations   = 0  

25 .8-point algorithm Solve a system of homogeneous linear equations Write down the system of equations Solve f from A f = 0 using SVD Matlab : [U, S, V] = svd (A); f = V(:, end); F = reshape(f, [3 3])’;

26 .Need to enforce singularity constraint

27 .8-point algorithm Solve a system of homogeneous linear equations Write down the system of equations Solve f from A f = 0 using SVD Resolve det (F) = 0 constraint using SVD Matlab : [U, S, V] = svd (A); f = V(:, end); F = reshape(f, [3 3])’; Matlab : [U, S, V] = svd (F); S(3,3) = 0; F = U*S*V’;

28 .8-point algorithm Solve a system of homogeneous linear equations Write down the system of equations Solve f from A f = 0 using SVD Resolve det (F) = 0 constraint by SVD Notes: Use RANSAC to deal with outliers (sample 8 points) How to test for outliers? Solve in normalized coordinates mean=0 s tandard deviation ~= (1,1,1) just like with estimating the homography for stitching  

29 .Homography (No Translation) Fundamental Matrix (Translation) Correspondence Relation Normalize image coordinates RANSAC with 8 points Initial solution via SVD Enforce by SVD De-normalize: Correspondence Relation Normalize image coordinates RANSAC with 4 points Solution via SVD De-normalize: Comparison of homography estimation and the 8-point algorithm Assume we have matched points x x ’ with outliers