16-822 Assignment 3: 3D reconstruction

Q1: 8-point and 7-point algorithm (40 points)

(A1) F matrix using 8-point algorithm (15 points)

Brief introduction of implementation:

• First, normalizes the input points using a transformation matrix ( T ), making it zero mean and unit variance.

• Each pair of point correspondence gives us a constraint on F. The constraint can be expressed as: x₂^⊤Fx₁ = 0

• Then, we construct equation matrix A to solve F, where each row of A are in the following format

$$ A[i]=\left[\begin{array}{lllllllll} x_i^{\prime} x_i & x_i^{\prime} y_i & x_i^{\prime} & y_i^{\prime} x_i & y_i^{\prime} y_i & y_i^{\prime} & x_i & y_i & 1 \end{array}\right] $$

• Using SVD, the function finds the solution for ( F ) by computing the null space of ( A ). The vector corresponding to the smallest singular value of ( A ) is reshaped into a 3 × 3 matrix to yield an initial estimate of ( F ).

• The fundamental matrix ( F ) must be rank-2. Thus, another SVD is performed on ( F ) to zero out its smallest singular value, ensuring it meets the rank-2 constraint: $ F=U diag (d_1, d_2, 0) V^{T}$

• Finally, denormalizes ( F ) using the transformation matrices ( T1 ) and ( T2 ), reversing the scaling and centering applied initially to the points. This produces the final fundamental matrix in the original coordinate space: $ F = T_2^{T} F T_1 $

Viewpoint 1 (Points)	Viewpoint 2 (Epipolar Lines)

(A2) E matrix using 8-point algorithm (5 points)

Given intrinsic matrices K1 and K2, we can use equation $E=K_2^{T} F K_1 $ to compute essential matrix E.

My estimated E:

$$ E = \begin{bmatrix} -1.29362504e-02 & -1.12555838e+01 & -1.86746229e+01 \\ 1.35772998e+01 & -3.41374700e+00 & -2.74530807e+01 \\ 2.43843346e+01 & 2.45414016e+01 & 1.64166858e+00 \end{bmatrix} $$

(B) 7-point algorithm (20 points)

Brief introduction of implementation:

• First, normalizes the input points using a transformation matrix ( T ), making it zero mean and unit variance.

• Each pair of point correspondence gives us a constraint on F. The constraint can be expressed as: x₂^⊤Fx₁ = 0

• Then, we construct A to solve F, where each row of a are in the following format

$$ A[i]=\left[\begin{array}{lllllllll} x_i^{\prime} x_i & x_i^{\prime} y_i & x_i^{\prime} & y_i^{\prime} x_i & y_i^{\prime} y_i & y_i^{\prime} & x_i & y_i & 1 \end{array}\right] $$

• Using SVD, the function finds the solution for ( F ) by computing the null space of ( A ). Given the seven points, this yields two potential solutions, ( F_1 ) and ( F_2 ), from the last two singular vectors of ( A ).

• A linear combination of ( F_1 ) and ( F_2 ) with scalar a is used to enforce the rank-2 constraint on ( F ): $ F(a) = a F_1 + (1 - a) F_2 $

• To ensure ( F ) has rank 2, we set the determinant of ( F(a) ) to zero, yielding a cubic equation in a: det(F(a)) = 0. Solving this cubic equation gives up to three real roots, each corresponding to a possible fundamental matrix.

• I calculate the point line distance between a point’s corresponding epipolar line and its corresponding point in the other image. Pick the solution with least sum of distances between point correspondences to be the final solution of fundamental matrix.

• Finally, denormalizes ( F ) using the transformation matrices ( T1 ) and ( T2 ), reversing the scaling and centering applied initially to the points. This produces the final fundamental matrix in the original coordinate space: $ F = T_2^{T} F T_1 $

Viewpoint 1 (Points)	Viewpoint 2 (Epipolar Lines)

Q2: RANSAC with 7-point and 8-point algorithm (20 points)

Brief introduction of implementation:

• First, randomly select N (7 or 8) points from the given correspondenses, and use the selected points to estimate the fundamental matrix using 7-point or 8-point algorithm.

• Calulate the projection error over all correspondences. Here, the projection error is defined as the point line distance between a point’s corresponding epipolar line and its corresponding point in the other image. I calculate the line point distance on both image1 and image2 for more precise projection error evaluation. Then, calculate the number of inliers that has epipolar error below a threshold (set as 2 in my code).

• RANSAC will iterate over the above step 10000 times and choose the best F with most inliers.

• Finally, we use all the inliers to construct an equation matrix A and use SVD to derive the final fundamental matrix.

Results:

• bench

Method	Viewpoint 1 (Points)	Viewpoint 2 (Epipolar Lines)	Fundamental Matrix
8 points
7 points

• remote

Method	Viewpoint 1 (Points)	Viewpoint 2 (Epipolar Lines)	Fundamental Matrix
8 points
7 points

• ball

Method	Viewpoint 1 (Points)	Viewpoint 2 (Epipolar Lines)	Fundamental Matrix
8 points
7 points

• hydrant

Method	Viewpoint 1 (Points)	Viewpoint 2 (Epipolar Lines)	Fundamental Matrix
8 points
7 points

Q3: Triangulation (20 points)

Reconstruction View 1	Reconstruction View 2	Reconstruction View 3

Brief introduction of implementation:

• For each pair of correspondences, we use the following equation to construct 4 rows of the equation matrix A.

$$ \left[\begin{array}{c} {[\mathbf{x}]_{\times} \mathbf{P}} \\ \left.\left[\mathbf{x}^{\prime}\right]_{\times} \mathbf{P}^{\prime}\right] \end{array}\right] \quad \mathbf{X}=\mathbf{0} $$

• Using SVD, the function finds the solution for ( X ) by computing the null space of ( A ). The vector corresponding to the smallest singular value of ( A ) is reshaped into a vector to yield an initial estimate of the coordinates ( X ) in projective 3D space.

Q4: Reconstruct your own scene! (20 points)

I use images from mid-nerf 360 dataset as input image sequence and reconstruct two scenes (bicycle and kitchen) using COLMAP.

Scenes:

• bicycle

• kitchen

Q5: Bonus 1 - Fundamental matrix estimation on your own images. (10 points)

Brief explanation of your implementation:

• First, convert the RGB image to grayscale image and extract the SIFT features.

• Then, find a keypoint’s correspondence by selecting the keypoint in another image with the least distance (defined as sum of element-wise square difference) between their descriptor.

• Consider a valid correspondence only when point A selects point B as the cloest neighbor in descriptor space and point B also selects point A.

• Using the 8-point RANSAC with the above point correspondences to get the estimate the final fundamental matrix

Viewpoint 1 (Points)	Viewpoint 2 (Epipolar Lines)