HW3: 3D Reconstruction

Andrew ID: pengliaj

Q1: 8-Point and 7-Point Algorithm (40 points)

(A1) F Matrix Using 8-Point Algorithm (15 points)

Explanation of Implementation

• Step 1: Coordinate Normalization

  Normalize the coordinates of points in both images by computing similarity transformations (T₁) and (T₂) for each set of points:

  • Translation: Move the centroid of each point set to the origin.
  • Scaling: Scale the points so that the average distance from the origin is √2.

  This normalization makes subsequent computations more stable and reduces sensitivity to variations in scale and location.

• Step 2: Formulate the Fundamental Matrix Equation

  Given each pair of corresponding points in the first image and the second image:

  • Apply the fundamental matrix constraint.
  • Expand this constraint to obtain a linear equation in the elements of F: $$x_1 x_2 F_{11} + x_2 y_1 F_{12} + x_2 F_{13} + y_2 x_1 F_{21} + y_1 y_2 F_{22} + y_2 F_{23} + x_1 F_{31} + y_1 F_{32} + F_{33} = 0$$
  • Repeat this expansion for all point correspondences to build a system of linear equations, each contributing a constraint on the elements of F.

• Step 3: Solve for F Using SVD

  • Use SVD to solve the system of equations and estimate F.
  • Denormalize F by applying the transformations: $$\mathbf{F} = \mathbf{T}_2^T \mathbf{F} \mathbf{T}_1$$

Epipolar Lines

Viewpoint 1 (Points)	Viewpoint 2 (Epipolar Lines)

(A2) E Matrix Using 8-Point Algorithm (5 points)

Explanation of Implementation

• Step 1: Calculate the Essential Matrix E

  The essential matrix E relates corresponding points in two views and is derived from the fundamental matrix F and the intrinsic matrices K₁ and K₂ of the two cameras. The calculation is as follows:

  E = K₂^T · F · K₁

• Step 2: Normalize E

  To maintain a consistent scale, normalize the essential matrix E such that its last element equals 1:

  E = E / E_3,3

Estimated E

(B) 7-Point Algorithm (20 points)

Explanation of Implementation

1. Matrix Construction: For each matched point pair, create a matrix row that captures their geometric relationship, setting up for solving the fundamental matrix.
2. Compute Fundamental Matrices: Apply SVD to find special vectors, reshape them into preliminary matrices, and combine these with an adjustable factor to satisfy required properties.
3. Solve the Polynomial: Use the combination’s condition to form a cubic equation. Solve it to get values for the factor, yielding potential fundamental matrices.
4. Denormalize the Fundamental Matrix: Convert each candidate matrix back to the original coordinates, providing matrices that capture the true image relationship.

Epipolar Lines

Viewpoint 1	Viewpoint 2

Fundamental Matrices

Q2: RANSAC with 7-Point and 8-Point Algorithm (20 points)

Explanation of Implementation

1. Random Sampling and Model Fitting: Each iteration:

   • Randomly selects 7 or 8 matched points.
   • Calculates F using the appropriate algorithm (selected by compute_F).

2. Error Calculation and Inlier Counting: For each calculated F:

   • Computes epipolar errors for all matched points.
   • Counts inliers (errors below dynamic_threshold) and updates F if this count exceeds the previous best.

3. Dynamic Threshold and Early Stopping: The threshold tightens every 10% of iterations. If inlier counts stabilize for a set number of rounds, iterations stop early.

Epipolar Lines

Viewpoint 1 (Points) (8 points)	Viewpoint 2 (Epipolar Lines) (8 points)	Viewpoint 1 (Points) (7 points)	Viewpoint 2 (Epipolar Lines) (7 points)	% of Inliers vs. # of Iterations

Fundamental Matrices

Object	8 Points	7 Points
Ball
Hydrant
Bench
Remote

Q3: Triangulation (20 points)

Explanation of Implementation

1. Skew-Symmetric Matrix Construction: Convert each 2D point to a skew-symmetric matrix, enabling cross product representation as matrix multiplication, which aids in building constraints.
2. Constraint Matrix Calculation: For each point pair, compute constraints using the skew-symmetric matrices and camera projections for both images. These constraints are key to solving the 3D point.
3. Triangulating 3D Points: Stack the constraints into a system and solve using SVD to find the 3D point in homogeneous coordinates, then normalize to get the final (X, Y, Z) values.
4. Color Extraction: For visualization, retrieve RGB color values from each 2D point in the first image, storing these colors with the corresponding 3D points.

Point Cloud

Q4: Reconstruct Your Own Scene! (20 points)

Example Multi-View Images	Output

Q5: Bonus 1 - Fundamental Matrix Estimation on Your Own Images (10 points)

Description of Implementation

1. Keypoint Detection and Matching: The SIFT detector finds distinctive features in each image. A brute-force matcher then matches descriptors between the two images, and matches are sorted by distance to prioritize closer matches.
2. Homogeneous Coordinates Conversion: The matched keypoints are converted into homogeneous coordinates, a requirement for epipolar geometry computations.
3. Fundamental Matrix Estimation using RANSAC: The RANSAC algorithm estimates the fundamental matrix while minimizing the impact of outliers. Only inliers are retained, which improves the robustness of the estimation.
4. Epipolar Line Visualization: Epipolar lines corresponding to the estimated fundamental matrix are drawn on both images, illustrating the geometric relationship between the matched points.

Epipolar Lines

Viewpoint 1 (Points)	Viewpoint 2 (Epipolar Lines)

Q6: Bonus 2 - Stress Test the Hyperparameters of COLMAP (10 points)

Question 1: What happens if we reduce the number of input images in COLMAP?

• Explanation: Reducing the number of input images decreases the overlap between images, leading to fewer feature matches. This results in incomplete or less accurate 3D reconstructions.
• Evidence:
  • With 30 images of a scene, COLMAP produced a detailed reconstruction.
  • Reducing to 15 images caused gaps and missing details.
  • Using only 5 images led to a sparse and fragmented model.
• Conclusion: A higher number of input images with sufficient overlap is crucial for a complete and accurate reconstruction in COLMAP.

Question 2: How does adjusting tolerance parameters affect the COLMAP reconstruction pipeline?

• Explanation: Changing tolerance parameters like the RANSAC inlier threshold affects outlier rejection during feature matching. Looser tolerances may include more outliers, while stricter tolerances might reject valid matches.
• Evidence:
  • Default RANSAC settings yielded a robust reconstruction.
  • Increasing the inlier threshold allowed more matches but introduced errors due to outliers.
  • Decreasing the threshold resulted in fewer matches, causing the reconstruction to fail in some areas.
• Conclusion: Proper tuning of tolerance parameters is essential. Balancing them helps in rejecting outliers without losing necessary feature matches, ensuring a successful reconstruction.