Geometry-based Methods for Vision

Assignment 3

Aviral Agrawal (avirala)

Q1 (A1) F matrix using 8-point algorithm

The algorithm for the 8-point algorithm is as follows:
  1. Normalize the points in both images for stability purposes while estimating the fundamental matrix. Let the normalization matrix be \(T\). The normalization can be defined by the following equation: \(x_{norm} = T x\)
  2. Construct the system of linear equations based on the equation \(x_2^T F x_1 = 0\).
  3. This gives you a system of linear equations of the form \(Af = 0\), where \(f\) is the vectorized form of the fundamental matrix.
  4. Construct the matrix A by stacking the equations for all (eight) the point correspondences.
  5. Extract the fundamental matrix from the last row of \(V^T\)
  6. Enforce the rank-2 constraint on the fundamental matrix by setting the smallest singular value to zero.
  7. Denormalize the obtained fundamental matrix using the following equation: \(F = T^T F T\)
  8. Get the epipolar lines by the following equation: \(l_2 = F x_1\)

    9. The Fundamental matrix computed from the 8-point algorithm for the Bench scene is: \[ F_{bench} = \begin{bmatrix} -1.19265833 \times 10^{-7} & -2.53255522 \times 10^{-6} & 2.07584109 \times 10^{-4} \\ -3.96465204 \times 10^{-7} & 2.27096267 \times 10^{-7} & 2.48867750 \times 10^{-2} \\ -1.06890748 \times 10^{-3} & -2.30052117 \times 10^{-2} & 1.00000000 \end{bmatrix} \]
    Snow
    Fig1. Results on Bench scene


    The Fundamental matrix computed from the 8-point algorithm for the Remote scene is: \[ F_{remote} = \begin{bmatrix} 7.19006698 \times 10^{-7} & -1.90583125 \times 10^{-7} & 2.36215166 \times 10^{-3} \\ -1.88159055 \times 10^{-6} & -8.60510729 \times 10^{-7} & -8.45685523 \times 10^{-3} \\ -3.98058321 \times 10^{-3} & 9.46500248 \times 10^{-3} & 1.00000000 \end{bmatrix} \]
    Snow
    Fig2. Results on Remote scene


    Q1 (A2). E matrix using 8-point algorithm

    The algorithm for computing the Essentil matrix given the Fundamental matrix (using the eight point algorithm) is as follows:
    1. Compute the Essential matrix using the following equation: \(E = K_2^T F K_1\), where \(K_1\) and \(K_2\) are the camera calibration matrices of the two cameras.
    2. Enforce the rank-2 constraint on the Essential matrix by setting the smallest singular value to zero and making the other two singular values equal by taking the average of the two.

      3. The Essential matrix computed from the 8-point algorithm for the Bench scene is: \[ E_{bench} = \begin{bmatrix} -0.18528359 & -3.93441194 & -0.95959081 \\ -0.61592238 & 0.35280189 & 30.82505761 \\ -1.60139078 & -30.55364717 & 0.44620549 \end{bmatrix} \]

      The Essential matrix computed from the 8-point algorithm for the Remote scene is: \[ E_{remote} = \begin{bmatrix} 1.01667679 & -0.26948489 & 2.9461563 \\ -2.66057249 & -1.21676375 & -11.37262789 \\ -5.82753537 & 10.6169466 & 0.40187929 \end{bmatrix} \]



      Q1 (B). 7-point algorithm

      The algorithm for the 7-point algorithm is as follows for computing the Fundamental matrix is as follows:
      1. Normalize the points in both images for stability purposes while estimating the fundamental matrix. Let the normalization matrix be \(T\). The normalization can be defined by the following equation: \(x_{norm} = T x\)
      2. Construct the system of linear equations based on the equation \(x_2^T F x_1 = 0\).
      3. This gives you a system of linear equations of the form \(Af = 0\), where \(f\) is the vectorized form of the fundamental matrix.
      4. Construct the matrix A by stacking the equations for all (seven) the point correspondences.
      5. Extract the candidate fundamental matrices, \(F1_1\) and \(F1_2\), from the last row of \(V^T\)
      6. Now we construct the equation \(F = \alpha F1_1 + (1 - \alpha) F1_2\) and solve for \(\alpha\) by setting the \(det(F) = 0\)
      7. For the root obtained for the equation in the previous step, eliminate the imaginary roots and get the real root that minimizes the error. This gives the fundamental matrix.
      8. Enforce the rank-2 constraint on the fundamental matrix by setting the smallest singular value to zero.
      9. Denormalize the obtained fundamental matrix using the following equation: \(F = T^T F T\)
      10. Get the epipolar lines by the following equation: \(l_2 = F x_1\)

        11. The Fundamental matrix computed from the 7-point algorithm for the Ball scene is: \[ F_{ball} = \begin{bmatrix} -3.35078059 \times 10^{-9} & -2.91545005 \times 10^{-6} & -6.74891733 \times 10^{-3} \\ 3.51682683 \times 10^{-6} & -8.84237457 \times 10^{-7} & -1.50044163 \times 10^{-2} \\ 9.09398538 \times 10^{-3} & 1.48748649 \times 10^{-2} & 1.00000000 \end{bmatrix} \]
        Snow
        Fig3. Results on Ball scene


        The Fundamental matrix computed from the 7-point algorithm for the Hydrant scene is: \[ F_{hydrant} = \begin{bmatrix} 1.06836663 \times 10^{-7} & -3.30854241 \times 10^{-6} & -1.37397509 \times 10^{-3} \\ 4.79268901 \times 10^{-6} & 1.63305018 \times 10^{-7} & -1.67456794 \times 10^{-2} \\ 1.12974017 \times 10^{-3} & 1.64136613 \times 10^{-2} & 1.00000000 \end{bmatrix} \]
        Snow
        Fig4. Results on Hydrant scene


        ̊

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

        The RANSAC algorithm is used to estimate the best Fundamental matrix using the 8-point (or 7-point) algorithms. The algorithm is as follows:
        1. Randomly select 8 points (or 7 points) from the set of correspondences.
        2. Estimate the Fundamental matrix using the selected points.
        3. Compute the error for each point by computing the epipolar line and the distance of the point from the epipolar line.
        4. Count the number of inliers by checking if the error is less than a threshold.
        5. Repeat the above steps for a fixed number of iterations and store the Fundamental matrix with the maximum number of inliers.

          6. NOTE: For the visualization of the results below, we show only 50 points and their corresponding epipolar lines.

          Table 1. Q2 results on Bench scene
          Algorithm Viewpoint 1 (points) and Viewpoint 2 (epipolar lines) Estimated best F matrix
          Ransac on Eightpoint algorithm Cathedral \( F_{bench} = \begin{bmatrix} -1.17732480 \times 10^{-8} & -5.96492484 \times 10^{-7} & -9.25459194 \times 10^{-5} \\ -2.11574661 \times 10^{-6} & 7.33247733 \times 10^{-7} & 2.38472741 \times 10^{-2} \\ -8.40950559 \times 10^{-4} & -2.23150919 \times 10^{-2} & 1.00000000 \end{bmatrix} \)
          Ransac on Sevenpoint algorithm Cathedral \( F_{bench} = \begin{bmatrix} -6.00278924 \times 10^{-8} & -1.89901309 \times 10^{-6} & -1.01789158 \times 10^{-4} \\ -8.35050242 \times 10^{-7} & 6.35592554 \times 10^{-7} & 2.34660431 \times 10^{-2} \\ -7.75197644 \times 10^{-4} & -2.20073479 \times 10^{-2} & 1.00000000 \end{bmatrix} \)

          Snow
          Fig5. Percentage inliers vs. number of iterations plot for the Bench scene

          Table 2. Q2 results on Remote scene
          Algorithm Viewpoint 1 (points) and Viewpoint 2 (epipolar lines) Estimated best F matrix
          Ransac on Eightpoint algorithm Cathedral \( F_{remote} = \begin{bmatrix} 3.31549792 \times 10^{-7} & 1.83719791 \times 10^{-6} & 1.65131980 \times 10^{-3} \\ -4.99599151 \times 10^{-6} & -1.96519828 \times 10^{-6} & -1.09521744 \times 10^{-2} \\ -3.16482952 \times 10^{-3} & 1.34098309 \times 10^{-2} & 1.00000000 \end{bmatrix} \)
          Ransac on Sevenpoint algorithm Cathedral \( F_{remote} = \begin{bmatrix} 9.07903785 \times 10^{-7} & 9.52425153 \times 10^{-6} & 2.80375262 \times 10^{-3} \\ -2.37640159 \times 10^{-5} & -1.12324145 \times 10^{-5} & -3.28032408 \times 10^{-2} \\ -5.52592264 \times 10^{-3} & 4.79981947 \times 10^{-2} & 1.00000000 \end{bmatrix} \)

          Snow
          Fig5. Percentage inliers vs. number of iterations plot for the Remote scene

          Table 3. Q2 results on Ball scene
          Algorithm Viewpoint 1 (points) and Viewpoint 2 (epipolar lines) Estimated best F matrix
          Ransac on Eightpoint algorithm Cathedral \( F_{ball} = \begin{bmatrix} 3.71042537 \times 10^{-7} & -2.25290945 \times 10^{-6} & -1.29575359 \times 10^{-2} \\ 2.83902820 \times 10^{-6} & -9.48009479 \times 10^{-7} & -2.08477087 \times 10^{-2} \\ 1.68824336 \times 10^{-2} & 2.03637835 \times 10^{-2} & 1.00000000 \end{bmatrix} \)
          Ransac on Sevenpoint algorithm Cathedral \( F_{ball} = \begin{bmatrix} -1.12736128 \times 10^{-8} & -2.69063603 \times 10^{-6} & -5.47932562 \times 10^{-3} \\ 3.29220226 \times 10^{-6} & -7.78788925 \times 10^{-7} & -1.30644532 \times 10^{-2} \\ 7.31943242 \times 10^{-3} & 1.29175883 \times 10^{-2} & 1.00000000 \end{bmatrix} \)

          Snow
          Fig5. Percentage inliers vs. number of iterations plot for the Ball scene

          Table 4. Q2 results on Hydrant scene
          Algorithm Viewpoint 1 (points) and Viewpoint 2 (epipolar lines) Estimated best F matrix
          Ransac on Eightpoint algorithm Cathedral \( F_{hydrant} = \begin{bmatrix} 1.15137573 \times 10^{-7} & -3.55180795 \times 10^{-6} & -1.44531518 \times 10^{-3} \\ 5.07452803 \times 10^{-6} & 8.62427635 \times 10^{-8} & -1.69450956 \times 10^{-2} \\ 1.18864639 \times 10^{-3} & 1.66666913 \times 10^{-2} & 1.00000000 \end{bmatrix} \)
          Ransac on Sevenpoint algorithm Cathedral \( F_{hydrant} = \begin{bmatrix} 8.03014968 \times 10^{-8} & -4.41774279 \times 10^{-6} & -1.17500281 \times 10^{-3} \\ 5.91955998 \times 10^{-6} & -6.29390198 \times 10^{-8} & -1.74127183 \times 10^{-2} \\ 9.10060610 \times 10^{-4} & 1.72900940 \times 10^{-2} & 1.00000000 \end{bmatrix} \)

          Snow
          Fig5. Percentage inliers vs. number of iterations plot for the Hydrant scene



          ̊

          Q3. Triangulation

          The algorithm for triangulation is as follows:
          1. We are given the camera matrices \(P_1\) and \(P_2\).
          2. Lets say that \(X\) is the 3D point we want to compute. Then, we use the equation \(x_1 = P_1 X\) and \(x_2 = P_2 X\) to get 4 constraints.
          3. Now, we solve the equation \(AX = 0\) where \(A\) matrix is formed by stacking the 4 constraints.
          4. Now, we solve the equation \(AX = 0\) using SVD and get the 3D point \(X\) using the last singular vector.
          5. Repeat the above steps for all the points and get the colored 3D point cloud.

            6. The colored point cloud formed by the given images:
            Snow
            Fig6. Colored point cloud


            ̊

            Q4. Reconstruct your own scene!


            In this question, we use COLMAP to reconstruct the scene given multiview images of the scene. The reconstructed scene is shown below:

            Table 5. Q4 COLMAP results on scene 1
            Multiview input images Output
            Cathedral Cathedral


            Table 6. Q4 COLMAP results on scene 2
            Multiview input images Output
            Cathedral Cathedral


            ̊

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

            The algorithm for computing the Fundamental matrix on own images is as follows:
            1. Extract the ORB features from the images to get the keypoints.
            2. Match the features using the Brute force matcher from CV2.
            3. Use the RANSAC algorithm to estimate the best Fundamental matrix using the 8-point algorithm.
            4. Display the epipolar lines and the points on the images like in the previous questions.

              5. NOTE: For the visualization of the results below, we show only 10 points and their corresponding epipolar lines.

              The Fundamental matrix computed from the 8-point algorithm for own scene 1 is: \[ F_{scene1} = \begin{bmatrix} 5.74826515 \times 10^{-7} & -1.26092227 \times 10^{-5} & 9.57701649 \times 10^{-3} \\ 1.36101425 \times 10^{-5} & -2.23535990 \times 10^{-7} & -6.07640109 \times 10^{-3} \\ -1.12669879 \times 10^{-2} & 5.34900814 \times 10^{-3} & 1.00000000 \end{bmatrix} \]
              Table 7. Q5 Input images in scene 1
              Image 1 Image 2
              Cathedral Cathedral


              Snow
              Fig7. Results on own scene 1


              The Fundamental matrix computed from the 8-point algorithm for own scene 2 is: \[ F_{scene2} = \begin{bmatrix} -2.60929762 \times 10^{-7} & 3.72036573 \times 10^{-6} & -3.98388544 \times 10^{-3} \\ -3.32332766 \times 10^{-6} & -7.31945265 \times 10^{-9} & 3.97720202 \times 10^{-3} \\ 4.04310031 \times 10^{-3} & -5.04795628 \times 10^{-3} & 1.00000000 \end{bmatrix} \]
              Table 8. Q5 Input images in scene 2
              Image 1 Image 2
              Cathedral Cathedral


              Snow
              Fig8. Results on own scene 2


              ̊