Assignment 3¶
Yixin Fei (yixinf)¶
Bench:
Remote:
Bench: $$ F = \begin{bmatrix} -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 \end{bmatrix} $$
Remote: $$ F = \begin{bmatrix} 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 \end{bmatrix} $$
Breif explanation of my implementation:
I used the 8-point algorithm. First, we normalize all the points by using matrix $T$. Then, for each pair of correspondence, we have the constraint: $$\mathbf{x}_2^\top F \mathbf{x}_1 = 0$$ We can form this equation into $A\mathbf{x} = 0$ $$A_i = \left[ x'_i x_i, \; x'_i y_i, \; x'_i, \; y'_i x_i, \; y'_i y_i, \; y'_i, \; x_i, \; y_i, \; 1 \right]$$
Then we use Singular Value Decomposition (SVD), and get the fundamental matrix $F$ by getting the last column of matrix $V$ and reshaping it into a $ 3 \times 3 $ matrix.
We then project $F$ to rank 2 matrix. We conduct SVD on $ F $ and then set the smallest singular value to 0.
Finally, we denormalize the fundamental matrix $F$ by computing $T_2^TFT_1$.
(A2) E matrix using 8-point algorithm¶
Bench: $$ E = \begin{bmatrix} -0.41524274 & -8.81748894 & -2.15055808\\ -1.3803559 & 0.79067134 & 69.08265036\\ -3.58890876 & -68.47438701 & 1.0 \end{bmatrix} $$
Remote: $$ E = \begin{bmatrix} 2.5298064 & -0.67056178 & 7.33094837\\ -6.62032749 & -3.02768466 & -28.29861665\\ -14.50071092 & 26.41824781 & 1.0 \end{bmatrix} $$
Breif explanation of my implementation:
Based on the calculation of fundamental matrix $F$, we can get the essential matrix $E$ by $E=K_2^TFK_1$, where $K_1$ and $K_2$ are intrinsic matrices.
(B) 7-point algorithm¶
Ball:
Hydrant:
Ball: $$ F = \begin{bmatrix} -3.35078059e-09 & -2.91545005e-06 & -6.74891733e-03 \\ 3.51682683e-06 & -8.84237457e-07 & -1.50044163e-02 \\ 9.09398538e-03 & 1.48748649e-02 & 1.00000000e+00 \end{bmatrix} $$ $$ E = \begin{bmatrix} -7.87994034e-03 & -6.85618523e+00 & -1.13753916e+01\\ 8.27042679e+00 & -2.07943738e+00 & -1.67226693e+01\\ 1.48533845e+01 & 1.49490598e+01 & 1.00000000e+00 \end{bmatrix} $$
Hydrant: $$ F = \begin{bmatrix} 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 \end{bmatrix} $$ $$ E = \begin{bmatrix} 0.14236494 & -4.40879014 & -3.7364802 \\ 6.38648609 & 0.2176117 & -16.40032786 \\ 4.54672553 & 16.75194526 & 1.0 \end{bmatrix} $$
Brief explanation of my implementation:
I used the 7-point algorithm. Similar to Q1(A1), first, we normalize all the points by using matrix $T$. Then we get the matrix $A$: $$A_i = \left[ x'_i x_i, \; x'_i y_i, \; x'_i, \; y'_i x_i, \; y'_i y_i, \; y'_i, \; x_i, \; y_i, \; 1 \right]$$
By using SVD, we can get two potential linearly independent solutions $F_1$ and $F_2$ from last two singular vectors of $\mathbf{A}$. General solution for $F$ can be written as: $$F = \alpha F_1 + (1-\alpha)F_2$$ Since the fundamental matrix $F$ must have rank 2, the determinant of $F$ should be zero. This equation is a cubic polynomial in $\alpha$, providing up to three real solutions for $\alpha$.
Then, we need find the best $F$ from up to three possible solutions for $F$. For each possible $F$, I calculate the error by computing the distance between the epipolar line and its corresponding point. I choose the best fundamental matrix by selecting the smallest error.
Finally, we denormalize the fundamental matrix $F$ by computing $T_2^TFT_1$.
Q2: RANSAC with 7-point and 8-point algorithm¶
Brief explanation of my implementation:
In each iteration, we start by randomly selecting 7 or 8 point correspondences. Using these points, we compute the fundamental matrix $F$ by applying either the 7-point or 8-point algorithm, as implemented in Q1. Next, we calculate the error, defined as the distance between the epipolar line of a point in the first image and its corresponding point in the second image. We then count the number of inliers—points for which the error is below a predefined threshold. In my implementation, this threshold is set to 2. The algorithm runs for a total of 10,000 iterations. Finally, we get the fundamental matrix computed from the iteration with the highest number of inliers as the final estimate.
RANSAC with 8-point (bench):
RANSAC with 7-point (bench):
Bench:
8-point: $$ F = \begin{bmatrix} -8.98413962e-08 & -2.10160507e-06 & 7.80517321e-05\\ -6.39239456e-07 & 3.99992442e-07 & 2.41600004e-02\\ -9.66400603e-04 & -2.25020792e-02 & 1.00000000e+00 \end{bmatrix} $$ 7-point: $$ F = \begin{bmatrix} -9.38720443e-08 & -2.32779518e-06 & 4.11471867e-05\\ -4.28821263e-07 & 3.98011021e-07 & 2.38102921e-02\\ -9.06602009e-04 & -2.22000741e-02 & 1.00000000e+00 \end{bmatrix} $$
RANSAC with 8-point (remote):
RANSAC with 7-point (remote):
Remote:
8-point: $$ F = \begin{bmatrix} 3.83796184e-07 & 1.28878967e-07 & 2.02315624e-03\\ -1.49399758e-06 & -5.79731950e-07 & -8.03181306e-03\\ -3.54238946e-03 & 8.63398505e-03 & 1.00000000e+00 \end{bmatrix} $$ 7-point: $$ F = \begin{bmatrix} 6.38299162e-07 & 3.15782590e-06 & 2.18183766e-03\\ -7.63341465e-06 & -2.86997916e-06 & -1.22796649e-02\\ -3.55906786e-03 & 1.56516411e-02 & 1.00000000e+00 \end{bmatrix} $$
RANSAC with 8-point (ball):
RANSAC with 7-point (ball):
Ball:
8-point: $$ F = \begin{bmatrix} -1.80752311e-07 & -3.80045103e-06 & -5.82041338e-03\\ 4.38308144e-06 & -1.11166315e-06 & -1.51807179e-02\\ 8.13724643e-03 & 1.53484401e-02 & 1.00000000e+00 \end{bmatrix} $$ 7-point: $$ F = \begin{bmatrix} -1.75005992e-08 & -3.00293950e-06 & -6.45336958e-03\\ 3.59882195e-06 & -8.96597330e-07 & -1.45947413e-02\\ 8.66104190e-03 & 1.44931292e-02 & 1.00000000e+00 \end{bmatrix} $$
RANSAC with 8-point (hydrant):
RANSAC with 7-point (hydrant):
Hydrant:
8-point: $$ F = \begin{bmatrix} 1.51200473e-07 & -1.65227261e-06 & -1.90300658e-03\\ 3.04191493e-06 & 4.06337967e-07 & -1.56899284e-02 \\ 1.74358046e-03 & 1.51140110e-02 & 1.00000000e+00 \\ \end{bmatrix} $$ 7-point: $$ F = \begin{bmatrix} 8.28751907e-08 & -4.36447960e-06 & -1.12605073e-03 \\ 5.89734347e-06 & -2.63224957e-08 & -1.73697578e-02\\ 8.42017462e-04 & 1.72162660e-02 & 1.00000000e+00 \\ \end{bmatrix} $$
Q3: Triangulation¶
Brief explanation of my implementation:
Given the projection matrices $P$ and $P^{'}$, for a 3D point $X$, we can get $\mathbf{x}=PX$, $\mathbf{x'} = P'X$.
We can rewrite it as: $$\mathbf{x} \times (PX) =0$$
First the homogeneous scale factor is eliminated by a cross product to give three equations for each image point, of which two are linearly independent. Therefore, we can get an equation of the form $AX=0$: $$A = \begin{bmatrix} x \mathbf{p}^{3^\top} - \mathbf{p}^{1^\top} \\ y \mathbf{p}^{3^\top} - \mathbf{p}^{2^\top} \\ x' \mathbf{p}'^{3^\top} - \mathbf{p}'^{1^\top} \\ y' \mathbf{p}'^{3^\top} - \mathbf{p}'^{2^\top} \end{bmatrix}$$ where $\mathbf{p}^{i^\top}$ are the rows of $p$.
We can solve it by conducting SVD on matrix $A$ and get $X$ from the last column of the matrix $V$.
| View 1 | View 2 | View 3 |
|---|---|---|
 |
 |
 |
Q4: Reconstruct your own scene!¶
I use the images from the COLMAP dataset (link).
Scene 1: South Building
Multi-view input images: (128 in total)
Scene 2: Gerrard Hall
Multi-view input images: (100 in total)
Q5: Bonus 1 - Fundamental matrix estimation on your own images.¶
Brief explanation of my implementation:
I utilize the SIFT feature detector to detect keypoints and compute descriptors for both input images. Then I use the BFMatcher (Brute Force Matcher) with L2 norm to find matching features between the two images using k-nearest neighbors (k=2). After that, I apply Lowe’s ratio test to filter out poor matches. For each pair of matches (m, n), retain m if m.distance < 0.75 * n.distance. Finally, I extract the coordinates of the "good" matched keypoints. After getting the matching keypoints, I use the RANSAC with 8-point algorithm implemented before to get fundamental matrix $F$.
