Two View Geometry

Homographies

Definition

Def Projective Transformation

Definition

Def Cross Ratio The cross ratio of four points , , and is defined as:

Proposition

Prop Projective transformation preserves colinearity.

Proposition

Prop Projective transformation preserves cross ratio of collinear points:

Proposition

Prop Transformation of 2D Points and Lines Suppose we have transformation from points into points , i.e. , then for any line , it maps to . Proof .

Definition

Def Homography (Matrix) Homography is a projective transformation between two images of the same planar surface. It is represented by a transformation matrix under a homogenous coordinates.

Homography Estimation

Algorithm

Algorithm Direct Linear Transformation Given an equation of the form in the presence of noise. The DLT solution is obtained by computing the SVD of and taking the last column of as the solution for .

Algorithm

Algorithm Direct Linear Transformation for Homography Estimation Goal: Given 2D-2D point correspondences , determine the homography matrix such that .

1. For each correspondence compute matrix , taking only the first rows.
2. Assemble the matrices into a single matrix .
3. Compute the SVD of .
4. Take the last column of as the solution for .
5. Rearrange to obtain .

where for and

Algorithm

Algorithm Normalised DLT for Homography Estimation Goal: Given 2D-2D point correspondences , determine the homography matrix such that .

1. Normalise 2D points: , .
2. Apply the DLT algorithm to , get .
3. Denormalise the recovered solution using .

e.g. Example normalisation matrices: where , and , are image widths and heights respectively.

Algorithm

Algorithm Gold Standard Goal: Given 2D-2D point correspondences , determine the homography matrix such that .

1. Initialisation: Compute an initial estimate using normalised DLT or RANSAC.
2. Geometric minimisation of reprojection error:
3. Minimise using Levenberg-Marquardt over the entries of .
4. Compute initial estimate for optimal .
5. Minimise cost
6. Denormalise the recovered solution.

Epipolar Geometry

Comment

Epipolar geometry is the intrinsic geometry of 2 different views of the same 3D scene.

Definition

Def Baseline and Epipole Baseline is the line joining the camera centers. Epipole is the point of intersection of baseline with image plane. Epipolar plane is the plane containing baseline and world point. Epipolar line is the intersection of epipolar plane with the image plane. e.g. In the following diagram, we have world point , camera centers and , then is the baseline, and is the epipolar line, is the epipolar plane.

Proposition

Prop All epipolar lines intersect at the epipole.

Proposition

Prop Epipole is the projection of one optical centre in the other image.

Essential and Fundamental Matrices

Definition

Def Essential Matrix The essential matrix encapsulates the epipolar geometry constraints between two views of a 3D scene, with calibrated cameras and contains the intrinsic camera parameters. It is where is the rotation matrix in and is the translation crossproduct matrix in of rank :

Prop The essential matrix has following properties:

• It has a rank of .
• It is singular, has singular values and .
• .

Algorithm Recovering and from

1. Implement SVD: .
2. Output and where
3. To get all 4 solutions, solve for combinations of and .
4. Select solution where all of the 3D points are in front of both cameras.

Definition

Def Fundamental Matrix The fundamental matrix encodes the relationship between two images of a 3D scene by encapsulating the epipolar geometry constraints, while the intrinsics of both cameras are not known. Mathematically, such matrix is the unique rank matrix that satisfies for all corresponding points and .

Prop The fundamental matrix has following properties:

• If is fundamental matrix for ,then is the fundamental matrix for .
• maps from a point in one image to a line in the other image.
• Lie on all epipolar lines, thus for all implies .

Algorithm

Algorithm DLT for Fundamental Matrix Estimation It is also called the 8-point algorithm. Given 2D-2D point correspondences , determine the fundamental matrix such that .

1. Let , and
2. Construct the matrix . And construct the vector .
3. Minimise subject to , get as the least right singular vector of .
4. Reshape to get .
5. But since , replace with by computing the SVD of and setting the smallest singular value to . That is to solve the following optimization problem: Concretely, decompose and set where
6. Return .

Comment

The 8-Point Algorithm has advantage of being simple and fast, but it is sensitive to noise, and it optimises a non-physical algebraic quantity.

Algorithm Normalised DLT for Fundamental Matrix Estimation

1. Transform the points using normalisation matrices and : and .
2. Apply the DLT algorithm to , get .
3. Then denormalise the recovered solution using .

Triangulation

Def Triangulation Problem The triangulation problem is to compute the 3D location , given image points and in correspondence across two or more images (taken from calibrated cameras with known intrinsics and extrinsics).

Algorithm DLT Triangulation Given camera projection matrix , and corresponding points , :

1. Precondition points and projection matrices.
2. Create matrix .
3. Compute SVD of .
4. Extract from the last column of .
5. Then refine with respect to a geometric error. sample code can be found here.

Stereo Vision

Comment

Humans do 3D perception well from a single image and very well from stereo (binocular) images. An intermediate goal of computer vision was to mimic the functionality of the biological system.

Definition

Def Disparity Disparity is the positional difference between the two retinal projections of a given point in space. e.g. In the following setting, we have disparity .

Proposition

Prop If optical axes are parallel and heights of the camera centers are identical, then for points at a fixed depth, the disparity between the corresponding points in the two images is constant.

Def Rectified Stereo Images We say the stereo images are rectified if

• Image planes of cameras are parallel;
• Principal axes are at same height;
• Identical focal lengths.

Prop The epipolar lines fall along the horizontal scan lines of the images in a rectified stereo setting.

The Correspondence Problem

Def Correspondence Problem The correspondence problem in stereo vision is the problem of measuring the disparity of each point in the two eye (camera) projections.

Law Colour Constancy Constraint Same world point has same intensity (or colour) in both images.

Def Sum of Squared (Pixel) Differences Suppose and are corresponding by windows of pixels. Define the following window function: The sum of squared difference cost measures the intensity differences as a function of disparity:

Interpretation Problem

Def Interpretation Problem The interpretation problem in stereo vision is about how to use disparity information to recover the orientation and distance of surfaces in the scene.