HW3: 3D Reconstruction

Submitted by: Kallol Saha

Q1: 8-point and 7-point algorithm

(A1) F matrix using 8-point algorithm

1. Points and corresponding epipolar lines:

Scene	View 1 (Points)	View 2 (Epipolar Lines)	View 2 (Points)	View 1 (Epipolar Lines)
Bench
Remote

2. Brief explanation:

• Given 2D point correspondences between the 2 images, we first assert that there are 8 point correspondences, required for the 8-point algorithm
• We first normalize each correspondence set using a similarity transform T defined by the equations below, and store the transforms for future use.

• Using the normalized points, we can form a matrix A that represents the constraints on the elements of the fundamental matrix.
• The null space of A gives us the 9 elements of the fundamental matrix F which we obtain by reshaping.

• Since F is singular with zero determinant, we set its last singular value to zero using SVD
• Using the stored transforms T we convert the fundamental matrix back to pixel space.
• To plot epipolar lines on the second image corresponding to points on the first image, we use the formula l = F @ x and l = transpose(F) @ x for the epipolar lines corresponding to points on the second image on the first image.

(A2) E matrix using 8-point algorithm

Computed E matrix for Bench:

[[ -0.41524274  -8.81748894  -2.15055808]
 [ -1.3803559    0.79067134  69.08265036]
 [ -3.58890876 -68.47438701   1.        ]]

Computed E matrix for Remote:

[[  2.5298064   -0.67056178   7.33094837]
 [ -6.62032749  -3.02768466 -28.29861665]
 [-14.50071092  26.41824781   1.        ]]

2. Brief explanation:
   • After computing the F matrix as described in Q1A1, we can use the known intrinsics K1 and K2 of the 2 cameras to get the essential matrix as:
   • Essential matrix E = transpose(K2) @ F @ K1

(B) 7-point algorithm

1. Points and corresponding epipolar lines:

Scene	View 1 (Points)	View 2 (Epipolar Lines)	View 2 (Points)	View 1 (Epipolar Lines)
Hydrant
Ball	<			>

2. Brief description:

   • Given 2D point correspondences between the 2 images, we first assert that there are 7 point correspondences, required for the 7-point algorithm
   • We first normalize each correspondence set using a similarity transform T as shown in Q1A1, and store the transforms for future use.
   • Using the normalized points, we can form a matrix A that represents the constraints on the elements of the fundamental matrix, as outlined in Q1A1 above.
   • We extract the two null vectors of A from the last 2 columns of the V matrix obtained from its SVD. These vectors can be reshaped into the matrices F1 and F2.
   • A linear combination of these will gives us the final F matrix that lies in the null space. Since F is singular, we constrain its determinant to be zero, and solve a 3-degree polynomial to find the linear combination that gives us F as shown below.
   
   • The polynomial gives us either 1 or 3 real roots. For each real root found, we find the F matrix.
   • Using the stored transforms T we convert the fundamental matrix back to pixel space.
   • To plot epipolar lines on the second image corresponding to points on the first image, we use the formula l = F @ x and l = transpose(F) @ x for the epipolar lines corresponding to points on the second image on the first image.
   • For the Ball example, there is only one real root. For the Hydrant example, there are 3 real roots, which gives us the following set of epipolar lines:

Scene	View 1 (Points)	View 2 (Epipolar Lines)
Root 1
Root 2
Root 3

• Here, we can see that root 2 is the correct root, as the epipole (intersection of the lines) in roots 1 and 3 do not seem to converge at the point which is the image of the first camera's center. So, we manually pick root 2.

Q2: RANSAC with 7-point and 8-point algorithm

Bench:

Points and corresponding epipolar lines for the best sample from RANSAC:

View 1 (Points)	View 2 (Epipolar Lines)	View 2 (Points)	View 1 (Epipolar Lines)

Fundamental Matrix:

 [[-6.93865685e-07 -1.13181769e-05  2.31499123e-03]
 [ 7.11051241e-06 -3.33135143e-06  3.42320606e-02]
 [-2.90978450e-03 -2.95357848e-02  1.00000000e+00]]

Graph:

Remote:

Points and corresponding epipolar lines for the best sample from RANSAC:

View 1 (Points)	View 2 (Epipolar Lines)	View 2 (Points)	View 1 (Epipolar Lines)

Fundamental Matrix:

 [[ 6.45991378e-07  2.16590736e-06  2.28533038e-03]
 [-5.59589506e-06 -2.29454687e-06 -1.06715464e-02]
 [-3.75526569e-03  1.31886547e-02  1.00000000e+00]]

Graph:

Hydrant:

Points and corresponding epipolar lines for the best sample from RANSAC:

View 1 (Points)	View 2 (Epipolar Lines)	View 2 (Points)	View 1 (Epipolar Lines)

Fundamental Matrix:

 [[ 1.51808689e-07 -6.53853767e-07 -1.82831778e-03]
 [ 2.11379160e-06  6.24757418e-07 -1.60952451e-02]
 [ 1.74527652e-03  1.53647505e-02  1.00000000e+00]]

Graph:

Ball:

Points and corresponding epipolar lines for the best sample from RANSAC:

View 1 (Points)	View 2 (Epipolar Lines)	View 2 (Points)	View 1 (Epipolar Lines)

Fundamental Matrix:

 [[-9.48253498e-08 -2.95858025e-06 -7.61582875e-03]
 [ 3.41222748e-06 -9.59757471e-07 -1.71308787e-02]
 [ 1.07071320e-02  1.71883691e-02  1.00000000e+00]]

Graph:

2. Method:
   • Given a set of noisy point correspondences, we iteratively sample a set of 8 points for the 8-point algorithm, and a set of 7 points for the 7-point algorithm.
   • We use the 7-point and 8-point algorithm implementations from Q1
   • In each iteration, we use the calculated fundamental matrix F from both 7 point and 8 point algorithm to calculate the following product with respect to all the points in the dataset: transpose(pts2) @ F @ (pts1) where pts1 and pts2 are the points in the first and second image respectively.
   • A point correspondence is an inlier if the product transpose(pts2) @ F @ (pts1) is close to zero. We check this by seeing if it is lower than a threshold. In the code, a threshold of 0.01 is used.
   • The sampling is done for 10,000 iterations, and the matrix F with the highest number of inliers is the output.
   • To plot epipolar lines on the second image corresponding to points on the first image, we use the formula l = F @ x and l = transpose(F) @ x for the epipolar lines corresponding to points on the second image on the first image.

Q3: Triangulation

Note: I am using Open3D for just visualizing the 3D RGB points. This is because the matplotlib scatter plot window throws a "not responding" error when plotting a high number of points. Compared to this, Open3D has a much smoother visualizer for debugging and recording results.

Colored Point Cloud:

Visualization in Open3D

Method:

• Given the 2D correspondences, we first homogenize each of the points
• Then, we form a skew-symmetric matrix for each of the points.
• For each of the points, if we matrix multiply the skew symmetric representation of the point with the given corresponding projection matrix P, we get a constraint on the 3D point X. We only use the first two rows since only they form independent constraints
• Extracting the null space of this constraint matrix and scaling it up to 1 will gives us the 3D point X.

Q4: Reconstruct your own scene!

Scene of painted pumpkins:

Note: pycolmap visualizer does not run on my Ubuntu 22.04 system, so I am extraxting the xyz point coordinates and the rgb values from the pycolmap reconstruction object. Then, I am using the rgb and xyz values to visualize in Open3D

Multi-view Input:

Output from pycolmap::

Scene of Logitech controller:

Multi-view Input:

Output from pycolmap::

Q5: Bonus 1 - Fundamental matrix estimation on your own images.

Book:

View 1 (Points)	View 2 (Epipolar Lines)	View 2 (Points)	View 1 (Epipolar Lines)

Controller:

View 1 (Points)	View 2 (Epipolar Lines)	View 2 (Points)	View 1 (Epipolar Lines)

Method:

• Given 2 images, we can apply the SIFT feature extractor to each image. This returns a list of keypoints (pixel coordinates) and a list of features (vectors of length 128) for each keypoint.
• To generate point correspondences, we match each of the features to each other using L2 norm. The feature pairs which are below a distance threshold of 200 are chosen.
• We get the keypoints for the feature pairs and label them as point correspondences.
• These correspondences are passed into the ransac function in Q2 that iteratively runs the 7-point and 8-point algorithm until it finds the fundamental matrix F with the highest number of inliers.
• Using F, we plot epipolar lines on the second image corresponding to points on the first image, we use the formula l = F @ x and l = transpose(F) @ x for the epipolar lines corresponding to points on the second image on the first image.