16-822 Geometry Based Methods for Vision

Q1: Affine Rectification

In this task, we aim to perform affine rectification to restore the parallelism of lines that appear skewed in the image due to perspective distortion. The key goal is to compute the homography matrix H that "restores" the parallelism up to an affine transformation. We follow the steps outlined below:

1: Find Points at Infinity
We begin by identifying pairs of parallel lines in the image. Each pair of parallel lines, when extended, meet at a point on the line at infinity. These points at infinity can be computed as the intersection of the lines. Given two pairs of parallel lines, we calculate the intersection points using the cross-product of the lines. These intersection points, P_∞1 and P_∞2, lie on the line at infinity. The equation for finding the point at infinity is:

l1 = cross(annotated_point1, annotated_point2)
l2 = cross(annotated_point3, annotated_point4)
P∞1 = cross(l1, l2)

2: Compute the Vanishing Line
Once we have the points at infinity, we compute the vanishing line, which is the line passing through both points at infinity. The vanishing line l'_∞ is used to construct the affine rectification homography matrix H using the equation:

l'∞ = cross(P∞1, P∞2)
l∞ = H−T l'∞ 

3: Affine Rectification Homography
Therefore the homography H that restores the parallelism by applying an affine transformation is given as:

 H = [1    0    0]
     [0    1    0]
     [l1   l2   l3]

Q2: Metric Rectification

In this task, we aim to further refine the rectified image from the affine stage to achieve metric rectification, restoring both parallelism and orthogonality of lines. We follow these key steps:

1. Circular Points at Infinity
After affine rectification, the remaining distortion is captured by the conic at infinity, denoted as C_∞. For metric rectification, we need to compute the homography H that transforms this conic into a circular conic, restoring the image's Euclidean properties. The relationship is given by the equation:

C∞ = H · C'∞ · HT

2. Affine Rectified Image Properties
The conic C'_∞ takes the form as shown bellow. Since we know that the affine rectified image satisfies
d = e = f = 0, the simplified conic reflects that certain distortion has already been corrected.

C'∞ = [ a   b/2   d/2]
      [b/2   c    e/2]
      [d/2  e/2    f ]

3. Perpendicular Lines and Constraints
To compute the metric rectification, we utilize the condition that Perpendicular lines in the real world satisfy the constraint expressed below:

l'T C'∞ m' = 0

where l' and m' are the lines in the image. From this, we can compute the unknown components of C'_∞.

4. Applying SVD and Eigenvalues
To solve for the conic, we apply Singular Value Decomposition (SVD) to the equation, extracting the eigenvalues and eigenvectors. Once C'_∞ is known, we can compute the homography H by using the diagonal matrix of the square roots of the eigenvalues of C'_∞. This homography corrects the remaining distortion, yielding the final metric rectified image.

Q3: Planar Homography from Point Correspondences

The goal of planar homography is to compute a 3x3 matrix H that maps points from one plane to another, based on known correspondences between the two planes. This matrix has 8 degrees of freedom (DOF), with the 9th degree constrained by scale. We follow these steps to compute H:

1. Relation Between Points and Homography
The points on the two planes are related by the homography matrix using the equation below where X' is the point in the transformed plane and X is the point in the original plane.

X' = H · X

2. Constraints using Point correspondences
To derive the constraints, let's assume the point X is represented as a homogeneous coordinate [x y w] and the corresponding point X' as [x' y' w']. If we flatten the homography matrix H into a column vector h (containing all elements of H), we can express the relationship as:

A · h = 0

where A is a matrix built from the point correspondences. For each point correspondence, the matrix A is formed by two rows:

[0   -w'X.T   y'X.T]
[w'X.T   0   -x'X.T]

3. Computing Homography
Since each point correspondence provides two constraints, we need at least four point correspondences to fully determine the homography matrix H. With four correspondences, we construct the full matrix A by stacking the rows for each point correspondence.

4. Solving for Homography Using SVD
Once the matrix A is constructed, we solve for the vector h using Singular Value Decomposition (SVD). The solution h corresponds to the right singular vector of A associated with the smallest singular value. Finally, the vector h is reshaped back into the 3x3 homography matrix H.

Input images for planar homography

Input images for planar homography

Q4: Metric Rectification from Perpendicular Lines

In this task, we aim to achieve metric rectification directly by considering all annotated points. This method involves constructing a matrix A that captures the geometric relationships of the annotated points and the coefficients of C'_∞ matrix. Then, applying Singular Value Decomposition (SVD) to obtain the transfromation matrix. The following key steps outline the process:

1. Perpendicular Lines and Constraints
To compute the metric rectification, we utilize the condition that Perpendicular lines in the real world satisfy the constraint expressed below:

l'T C'∞ m' = 0

where l' and m' are the lines in the image. From this, we can compute the unknown components of C'_∞.

2. Populating the Matrix A
We populate the matrix A by appending the following values to solve for A C'_∞ = 0:

A = [l1*m1,  (l1*m2 + l2*m1)/2,  l2*m2,  (l1*m3 + l3*m1)/2,  (l3*m2 + l2*m3)/2,  l3*m3] 

3. Applying SVD and Eigenvalues
To solve for the conic, we apply Singular Value Decomposition (SVD) to the equation, extracting the eigenvalues and eigenvectors. Once C'_∞ is known, we can compute the homography H by using the diagonal matrix of the square roots of the eigenvalues of C'_∞ ans shown in the equation below:

Q5: More Planar Homography from Point Correspondences

Used the Homography matrix computation algorithm from Question 3 to determine the H matrix by selecting point correspondences on the input image and the wall.