16-822 Assignment3

Q1: 8-point and 7-point algorithm (40 points)

(A1) F matrix using 8-point algorithm (15 points)

We have 2 sets of corresponding points, and we can normalize them by $\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}$. After normalizing, 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 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 (20 points)

Similar to 8-point algorithm, we can still adopt the same way to construct of $Af=0$$Af=0$. But this time, after SVD decomposition, 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$, we should find $\lambda$$\lambda$ that satisfies $det(\lambda F_1+(1-\lambda F_2))=0$$det(\lambda F_1 + (1-\lambda F_2))=0$. So we need to solve a cubic equation, and we can construct its equation parameters 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 (20 points)

For both 7-point and 8-point algorithm, we use the similar RANSAC strategy. For 10,000 iterations, we randomly select 7 or 8 points from all the points for each algorithm, and we can get the corresponding F. With this F, we can calcualte the errors for every point pairs by using their distance between the corresponding epipolar lines. We set the threshold to 5 to determine the number of inliers in each epoch. If the number of inliers is larger than ever, we choose such F as our best F.

1. 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 (20 points)

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! (20 points)

In this problem, we run on two examples from colmap.

The first example is south building, its example multiview images are as follows:

Here is the gif to visualize the reconstruction:

The second example is gerrard hall, its example multiview images are as follows:

Here is the gif to visualize the reconstruction:

Q5: Bonus 1 - Fundamental matrix estimation on your own images. (10 points)

I use SIFT feature extractor and cv2.BFMatcher to find the potential matches. After finding those corresponding points, I use the RANSAC with 8-point algorithm as illustrated in Q2.

The estimated $F$$F$ and visualization of epipolar lines are as follows:

F: [[ 1.42406574e-08 -5.21837850e-07 1.42762761e-03] [ 4.65758813e-07 2.16924155e-07 3.21347904e-03] [-1.18422972e-03 -4.19713612e-03 1.00000000e+00]]