16-822: Geometry Based Methods in Vision

Assignment 3: 3D Reconstruction

Q1: 8-point and 7-point algorithm

(A1) F Matrix using 8-point algorithm

Approach:

1. Use the $x'^T F x = 0$ constraint to create a system of linear equations of the form $Af = 0$
2. Solve $Af = 0$ using SVD, take the last singular vector as $f$ and rearrange to a matrix to get $F$
3. Enforce rank-2 constraint on F by performing SVD and setting $\sigma_3 = 0$
4. Get epipolar lines using $l' = Fx$

Viewpoint 1 (Points)	Viewpoint 2 (Epipolar Lines)

(A2) E Matrix using 8 point algorithm

Approach:

1. Get normalized points $\tilde{x} = K^{-1}x$
2. Use the $\tilde{x}'^T E \tilde{x} = 0$ constraint to create a system of linear equations of the form $Ae = 0$
3. Solve $Ae = 0$ using SVD, take the last singular vector as $e$ and rearrange to a matrix to get $E$
4. Enforce rank-2 constraint on E by performing SVD and setting $\sigma_3 = 0$ as well as $\sigma_1, \sigma_2 = \frac{\sigma_1+\sigma_2}{2}$

$$ E_{bench} = \begin{bmatrix} -0.00410057 & -0.08707371 & -0.0392206 \\ -0.01363117 & 0.00780797 & 0.71576 \\ -0.03921632 & -0.6897431 & 0.0319451 \\ \end{bmatrix} $$$$ E_{remote} = \begin{bmatrix} 0.05924111 & -0.01570271 & 0.17167066 \\ -0.15502987 & -0.07090005 & -0.6626758 \\ -0.33956678 & 0.61864274 & 0.02341725 \\ \end{bmatrix} $$

(B) 7-point algorithm

Approach:

1. Use the $x'^T F x = 0$ constraint to create a system of linear equations of the form $Af = 0$
2. Solve $Af = 0$ using SVD, take the two last singular vectors as $f_1$ and $f_2$ and rearrange to a matrix to get $F_1$ and $F_2$
3. Let $F = \lambda F_1 + (1 - \lambda F_2)$ and solve for lambda using $det(\lambda F_1 + (1 - \lambda) F_2) = 0$
4. If there is only one real root, then $\lambda$ takes that value
5. For three real roots, calculate the epipole $e_i'$ for each $F_i$
6. Since the images provided seem to be from almost a parallel stereo setup, pick the $F_i$ with the fathest epipole $e_i'$

Viewpoint 1 (Points)	Viewpoint 2 (Epipolar Lines)

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

Approach:

1. In a for loop, select 8 or 7 random point correspondences for 8-point or 7-point algorithm
2. Evaluate the fundamental matrix using the functions from the previous question
3. Evaluate the inliers for this $F$ by taking the sum of distances from the epipolar lines for both the images for each point (points closer than a threshold distance to epipolar lines are taken as inliers)
4. If number of inliers is greater than max observed till now, update $F$ and max number of inliers
5. Return the F with the max number of inliers

Viewpoint 1 (Points)	Epipolar Lines (Eight-point)	Epipolar Lines (Seven-point)	Plots

Q3: Triangulation

Approach:

1. For each point, use the constraint $x \times PX = 0$ where $x$ is the $P_2$ point and $X$ is the corresponding $P_3$ point to get two sets of constraints
2. Repeat for the other camera to get two more constraints and create the equation $Ax = 0$ where $A$ has 4 rows and 4 columns
3. Solve for $X$ using SVD by taking the last singular vector
4. Repeat for all the points

Q4: Reconstruct your own scene

Multiview Images	Output

Q5: Fundamental matrix estimation on your own images

Approach:

1. Use SIFT to get features in both images
2. Use CV2s BFMatcher with L2 norm to get correspondences between both images
3. Use eight point algrithm RANSAC from the previous question to get the correct fundamental matrix $F$
4. Get epipolar lines using $l' = Fx$

Multiview Images	Output