HW3: 3D reconstruction

Zoë LaLena

Q1: 8-point and 7-point Algorithm

(A1) F matrix using 8-point algorithm

Points and Epipolar Lines: Bench

Fundamental Matrix: Bench

-1.193e-07 -2.533e-06 2.076e-04
-3.965e-07 2.271e-07 0.025
-0.001 -0.023 1.000

Points and Epipolar Lines: Remote

Fundamental Matrix: Remote

7.190e-07 -1.906e-07 0.002
-1.882e-06 -8.605e-07 -0.008
-0.004 0.009 1.000

Explanation

1) We are provided corresponding points between two images, we first normalize them.

2) We build an A matrix for SVD from the correspondences such that for a correspondence between x and x' we have

In the end A should be an 8X9 matrix. We get this formulation from x'^TFx = 0, giving us the linear equation we turn into A.

3) Once we have A, we can perform SVD on A, taking the reshaped last row of V^T has F.

4) We perform SVD on F, setting the last element of sigma to 0. This ensures F is rank 2.

5) F is U.dot(diag(sigma).dot(V^T)), where sigma[-1] is zero.

6) We then unnormalize F.

(A2) E matrix using 8-point algorithm

Estimated E: Bench

-843.043 -18144.056 -4980.099
-474.640 -10201.675 -2769.449
-1.332 -28.657 -7.866

Estimated E: Remote

-1612.311 3835.889 1823.439
-2879.523 6839.367 3234.905
-4.759 11.316 5.370

Explanation

1) To get E, we use the equation

and our given intrinsics.

(B) 7-point Algorithm

Points and Epipolar Lines: Hydrant

Points and Epipolar Lines: Ball

Explanation

1) We are provided corresponding points between two images, we first normalize them.

2) We build an A matrix for SVD from the correspondences such that for a correspondence between x and x' we have

In the end A should be an 9X7. We get this formulation from x'^TFx = 0.

3) Once we have A, we can perform SVD on A, taking the reshaped last two rows of V as F1 & F2.

4) We have the constraint that F should have a determinate of 0, which we enforce with the following equation

We can use numpy's polyroots to solve.

5) If we are left with multiple real solutions we can test all for inliers.

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

Results: Best Solution

For a good mix of accuracy and speed we use 1000 iterations and a tolerance of 10.

8-point Algorithm

Points and Epipolar Lines: Bench

Points and Epipolar Lines: Remote

7-point Algorithm

Points and Epipolar Lines: Hydrant

Points and Epipolar Lines: Ball

Graph

Explanation

1) For a desired number of iterations we do the following.

2) We choose 7 or 8 random points (depending on the algorithm) and use the points to get F from our 7 or 8 point algorithm from Q1.

3) We calculate an error as the distance from the epipolar line a given point is for all the points in an image. We do this for both images.

4) If the distance from the above step is less than some tolerance, we use 10, it's considered an inlier.

5) After the desired number of iterations the F with the highest number of inliers is chosen as our final F.

Q3: Triangulation

Colored Point Cloud

Image 2 Image 2 Image 2 Image 2 Image 2

Explanation

Explanation

1) From the first equation, we can construct a way to use SVD.

2) For each pair of correspondences and camera matrices we construct A as the following.

3) We then use SVD to get the 3D points.

Q4: Single View Reconstruction

Data Set Example Multi-view images Output Still View
Lego Image 2 Image 2 Image 2
Controller Image 2 Image 2 Image 2

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

Box Result

Points and Epipolar Lines

Fundamental Matrix

1.236e-07 -1.299e-07 6.918e-05
8.567e-08 1.579e-07 -5.312e-04
-4.660e-04 -4.995e-05 1.000

Book Result

Points and Epipolar Lines

Fundamental Matrix

-7.957e-08 6.473e-08 -1.564e-04
-1.133e-07 -1.207e-07 -7.050e-04
-4.148e-04 0.001 1.000

Explanation

We use the same 8-point Ransac method from Q2, but we need to gather correspondences somehow. We use sift, conveniently a part of OpenCV, to find key points in each image. Then we use a brute force KNN matcher to then match key points between images, taking only the best matches as input for our 8-point Ransac algorithm.