16-822 Geometry-based Methods in Vision

Assignment 3: 3D Reconstruction

Zihan Wang (zihanwa3), Fall 2024

Q1: 8-point and 7-point algorithm

(A1) F matrix using 8-point algorithm

We have 2 sets of normalized corresponding points $\hat{x}=Tx$$\hat{x}=Tx$ where $\begin{array}{c}T=\left[\begin{array}{ccc}s& 0& -s{x}_0\\ 0& s& -sy\\ 0& 0& 1\end{array}\right]\end{array}$$T = \begin{bmatrix} s & 0 & -sx_0 \\ 0 & s & -sy \\ 0 & 0 & 1\end{bmatrix}$. Therefore, we can contruct a matrix form of $A\hat{f}=0$$A\hat{f}=0$, where each row of $A$$A$ is $A_i=[u_i^{\prime }{u}_i,u_i^{\prime }{v}_i,u_i^{\prime },v_i^{\prime }{u}_i,v_i^{\prime }{v}_i,v_i^{\prime },u_i,v_i]$$A_i = [u'_i u_i, u'_i v_i, u'_i, v'_i u_i, v'_i v_i, v'_i, u_i, v_i]$. With this matrix A, we can apply SVD on it and solve the $\hat{f}$$\hat{f}$ using the last row of $V^T$$V^T$. We can also enforce the rank 2 constraint by decomposing $\hat{F}$$\hat{F}$ again and setting the last singular value to 0. Finally, with such $\hat{F}$$\hat{F}$, we can denormalize it by $F=T^{\prime T}\hat{F}T$$F = T'^T \hat{F} T$.

For the bench example, the estimated $F$$F$ and visualization of epipolar lines are as follows:

F: [[-1.19265833e-07 -2.53255522e-06 2.07584109e-04] [-3.96465204e-07 2.27096267e-07 2.48867750e-02] [-1.06890748e-03 -2.30052117e-02 1.00000000e+00]]

For the remote example, the estimated $F$$F$ and visualization of epipolar lines are as follows:

F: [[ 7.19006698e-07 -1.90583125e-07 2.36215166e-03] [-1.88159055e-06 -8.60510729e-07 -8.45685523e-03] [-3.98058321e-03 9.46500248e-03 1.00000000e+00]]

 

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

We can calculate $E$$E$ using the intrinsic matrices and $F$$F$ by $E=K^{\prime T}FK$$E = K'^T F K$.

For the bench example, the $E$$E$ is:

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

For the remote example, the $E$$E$ is:

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

 

(B) 7-point algorithm

Similar to 8-point algorithm, we can still adopt the same way to construct of $Af=0$$Af=0$. The difference here is after SVD we should get two $F$$F$ by selecting the last two rows of $V^T$$V^T$. With $F_1$$F_1$ and $F_2$$F_2$, to find $\lambda$$\lambda$ that satisfies $det(\lambda F_1+(1-\lambda F_2))=0$$det(\lambda F_1 + (1-\lambda F_2))=0$, need to solve a cubic equation by substituting $\lambda =-1,0,1,2$$\lambda=-1,0,1,2$. After solving for the real value roots of such a equation, we can get all the possible $F$$F$. We choose the $F$$F$ that has the minimize the error.

For the ball example, the estimated $F$$F$ and visualization of epipolar lines are as follows:

F: [[-3.35078059e-09 -2.91545005e-06 -6.74891733e-03] [ 3.51682683e-06 -8.84237458e-07 -1.50044163e-02] [ 9.09398538e-03 1.48748649e-02 1.00000000e+00]]

For the hydrant example, the estimated $F$$F$ and visualization of epipolar lines are as follows:

F: [[ 1.06836663e-07 -3.30854241e-06 -1.37397509e-03] [ 4.79268901e-06 1.63305018e-07 -1.67456794e-02] [ 1.12974017e-03 1.64136613e-02 1.00000000e+00]]

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

Steps in the Algorithm:

1. Random Sampling:

   • Randomly sample 7 or 8 point correspondences to compute a candidate fundamental matrix.

2. Reprojection and Inlier Counting:

   • Use fundamental matrix to reproject points from the second image onto the first to get the epipolar line.

   • Measure the distance of each point in the second image to the epipolar line and count inliers whose sum distances below threshold.

3. Inlier Ratio Evaluation:

   • Compute the ratio of inliers to total correspondences. If the ratio is higher than any previous iteration, update best estimated fundamental matrix.

4. Iterate and Select Best Model:

   • Repeat this process, retaining fundamental matrix that maximizes the inlier ratio.

For the bench example, the visualization (graph plot) of % of inliers vs. # of RANSAC iterations:

RANSAC with 8-point results are as follows: F: [[-1.92395063e-07 -3.98637277e-06 3.58390838e-04] [ 9.76470194e-07 -2.19440493e-07 2.51422815e-02] [-1.15659998e-03 -2.30886805e-02 1.00000000e+00]]

RANSAC with 7-point results are as follows:

F: [[-1.06745741e-07 -2.56784447e-06 7.88289386e-05] [-2.31905535e-07 2.51495527e-07 2.41805627e-02] [-9.37432897e-04 -2.24758871e-02 1.00000000e+00]]

2. For the remote example, the visualization (graph plot) of % of inliers vs. # of RANSAC iterations:

RANSAC with 8-point results are as follows:

F: [[ 4.94228952e-07 -1.78309087e-07 2.07870586e-03] [-1.44717993e-06 -3.86418454e-07 -8.04693202e-03] [-3.48114568e-03 8.50582289e-03 1.00000000e+00]]

RANSAC with 7-point results are as follows:

F: [[ 2.24009193e-06 -3.99495480e-06 3.98001941e-03] [-9.01801147e-07 -8.38163830e-07 -1.13465404e-02] [-5.93169224e-03 1.34755145e-02 1.00000000e+00]]

3. For the ball example, the visualization (graph plot) of % of inliers vs. # of RANSAC iterations:

RANSAC with 8-point results are as follows:

F: [[-3.85293031e-08 -3.15784357e-06 -7.03554893e-03] [ 3.72620577e-06 -1.00245191e-06 -1.58804967e-02] [ 9.61780541e-03 1.58897996e-02 1.00000000e+00]]

RANSAC with 7-point results are as follows:

F: [[-2.77460041e-08 -2.89765184e-06 -6.55468330e-03] [ 3.47679767e-06 -8.49770567e-07 -1.45957327e-02] [ 8.83170495e-03 1.44185603e-02 1.00000000e+00]]

4. For the hydrant example, the visualization (graph plot) of % of inliers vs. # of RANSAC iterations:

RANSAC with 8-point results are as follows:

F: [[ 6.06381990e-08 -5.38367018e-06 -8.90646029e-04] [ 6.92565753e-06 -1.84686785e-07 -1.76920320e-02] [ 5.54842010e-04 1.76686648e-02 1.00000000e+00]]

RANSAC with 7-point results are as follows:

F: [[ 7.60374410e-08 -3.93180816e-06 -1.21370129e-03] [ 5.38148705e-06 5.75852498e-08 -1.73749242e-02] [ 9.99048841e-04 1.71740235e-02 1.00000000e+00]]

Q3: Triangulation!

With correponding points and projection matrices, we can construct the $A$$A$ by $\left[\begin{array}{c}[\mathbf{x}{]}_{\times }\mathbf{P}\\ [{\mathbf{x}}^{\prime }{]}_{\times }{\mathbf{P}}^{\prime }\end{array}\right]$$\begin{bmatrix} [\mathbf{x}]_{\times} \mathbf{P}\\ [\mathbf{x'}]_{\times} \mathbf{P'} \end{bmatrix}$. With this matrix, we can calculate the 3D points coordinates by applying SVD, and select the last row of $V^T$$V^T$.

The output colored 3D point cloud is as follows:

 

 

 

Q4: Reconstruct your own scene!