This is my webpage submission for 16822 assignment 1.

Q1: 8-point and 7-point algorithm

Q1a: F matrix using 8-point algorithm

I solved the fundamental matrix equation $x'^TFx = 0$ with 8 point correspondences between images using the following steps:

• Normalize the image pixels in each image so that they are mean-centered with root-mean-squared distance to the origin equal to $\sqrt{2}$. This normalizing transformation uses a scale factor of $s$ and mean x and y values of $c_x$ and $c_y$. It has the form $T = \begin{pmatrix} s & 0 & -sc_x \\ 0 & s & -sc_y \\ 0 & 0 & 1 \end{pmatrix}$
• Use constraints reminiscent of DLT from prior assignments. That is, each row of the A matrix has the form $\begin{pmatrix} x_1'x_1 & x_1'y_1 & x_1' & y_1'x_1 & y_1'y_1 & y_1' & x_1 & y_1 & 1 \end{pmatrix}$.
• With 8 such correspondences, I obtain an 8x9 A matrix from which I can solve for the 9x1 matrix f via SVD: $Af = 0$.
• Reforming the resulting 9 values into a 3x3 matrix, I enforce the additional constraint that the determinant is equal to 0 by setting the last element of the diagonal matrix to 0. I reconstruct F using this new diagonal matrix and the same U and V^T matrices that SVD yielded.
• I denormalize the F matrix according to T'^TFT and divide the resulting matrix by the last element.
• I compute the essential matrix as $E = K'FK$

Bench results:

Estimated E for bench: $\begin{pmatrix} -0.41524274 & -8.81748894 & -2.15055808 \\ -1.3803559 & 0.79067134 & 69.08265036 \\ -3.58890876 & -68.47438701 & 1 \end{pmatrix}$

Remote results:

Estimated E for remote: $\begin{pmatrix} 2.5298064 & -0.67056178 & 7.33094837 \\ -6.62032749 & -3.02768466 & -28.29861665 \\ -14.50071092 & 26.41824781 & 1 \end{pmatrix}$

Q1b: 7-point algorithm

I solved the fundamental matrix equation $x'^TFx = 0$ with 8 point correspondences between images using the following steps:

• Normalize each point using a transformation identical to that described in part a above.
• Create an A matrix using the same constraints as described in part a above, except using 7 instead of 8 point correspondences
• Solve with SVD now provides $F_1$ and $F_2$ matrices due to the larger null space from having 7 instead of 8 constraints.
• Represent $F = \alpha F_1 + (1-\alpha)F_2$ and solve the cubic polynomial that arises from setting its determinant equal to 0. Specifically, I choose arbitrary $\alpha$ values of 0, 0.31, 0.68, and 1 and plug these into the cubic polynomial. These coefficients give the A matrix for the next solution. The b matrix for which I am solving is the determinant of F with each $\alpha$ value.
• Solving this system of equations gives roots from which I solve for F. If the root has a nonzero imaginary component, I discard it, which yields either 1 or 3 possible F matrices.
• To decide on the correct F matrix, I observe the epipolar lines that each produces. In the case of the ball object, there is only one F matrix. In the case of the hydrant object, there are three F matrices and I conclude through observation that the third F matrix is correct.

Ball annotations:

Ball results:

Hydrant annotations:

Hydrant results. The third set of epipolar lines represent the correct F matrix:

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

To implement RANSAC in the 8pt algorithm:

• Normalize all points similar to Q1
• Sample eight of the many provided point correspondences
• Compute the F matrix using these sampled points
• For each correspondence, use this calculated F to determine the Sampson error
• If the error is less than a predetermined threshold (I used 0.5), then classify those points as inliers
• Track the best F as the one that produces the most inliers
• Repeat a predetermined number of times (I ran 10,000 iterations)

To implement RANSAC with the 7pt algorithm was largely the same as the 8pt algorithm. A key difference was that I computed the error for all F matrices if there were more than one produced from the 7pt algorithm. Also, my sample of point correspondences only included 7 instead of 8 for this exercise.

Note that for the following results, many image pairs produced more than one F matrix using the 7pt algorithm. For the sake of readability, in these results, I show only the best results. These results have been hand-picked based on the appearance of their epipolar lines.

8pt Bench results:

Best F: $\begin{pmatrix} -1.43391108e-07 & -2.90583671e-06 & 3.02620285e-04 \\ -9.27002442e-08 & 2.54945574e-07 & 2.51935268e-02 \\ -1.14221489e-03 & -2.32675030e-02 & 1.00000000e+00 \end{pmatrix}$

7pt Bench results:

Best F: $\begin{pmatrix} -7.16551895e-08 & -1.95227668e-06 & -1.05650737e-05 \\ -9.16780150e-07 & 3.82041574e-07 & 2.43876291e-02 \\ -8.74012444e-04 & -2.26454361e-02 & 1.00000000e+00 \end{pmatrix}$

Comparison of 7pt vs. 8pt algorithms for Bench

8pt Remote results:

Best F: $\begin{pmatrix} 1.81496664e-06 & -1.33152268e-07 & 3.09432203e-03 \\ -6.25315407e-06 & -1.39286815e-06 & -1.17648259e-02 \\ -4.39200342e-03 & 1.45596740e-02 & 1.00000000e+00 \end{pmatrix}$

7pt Remote results:

Best F: $\begin{pmatrix} 1.02427317e-06 & 1.17606920e-07 & 2.60290852e-03 \\ -3.55432803e-06 & -1.56076230e-06 & -1.01099221e-02 \\ -4.25880656e-03 & 1.21573246e-02 & 1.00000000e+00 \end{pmatrix}$

Comparison of 7pt vs. 8pt algorithms for Remote

8pt Ball results:

Best F: $\begin{pmatrix} 3.79242198e-08 & -2.81287023e-06 & -6.72388101e-03 \\ 3.40854975e-06 & -8.70737012e-07 & -1.45432565e-02 \\ 8.91864450e-03 & 1.44043905e-02 & 1.00000000e+00 \end{pmatrix}$

7pt Ball results:

Best F: $\begin{pmatrix} -1.58895816e-07 & -3.31042336e-06 & -6.49711691e-03 \\ 3.84358342e-06 & -9.31357129e-07 & -1.54382394e-02 \\ 9.06528994e-03 & 1.53623697e-02 & 1.00000000e+00 \end{pmatrix}$

Comparison of 7pt vs. 8pt algorithms for Ball

8pt Hydrant results:

Best F: $\begin{pmatrix} 9.83590525e-08 & -4.74603263e-06 & -1.17059748e-03 \\ 6.31769701e-06 & -1.30673063e-07 & -1.72794523e-02 \\ 8.30289487e-04 & 1.71940163e-02 & 1.00000000e+00 \end{pmatrix}$

7pt Hydrant results:

Best F: $\begin{pmatrix} 1.14869100e-07 & -2.88997281e-06 & -1.48587121e-03 \\ 4.33394304e-06 & 2.17393889e-07 & -1.63989254e-02 \\ 1.26550572e-03 & 1.60085438e-02 & 1.00000000e+00 \end{pmatrix}$

Comparison of 7pt vs. 8pt algorithms for Hydrant

Q3: Triangulation

Triangulating allows us to reconstruct a 3D scene from 2D point correspondences. To accomplish this, I took the following steps:

• For each point correspondence, construct an A matrix of the form $A = \begin{pmatrix} x\bf{p}^{3T} - \bf{p}^{1T} \\ y\bf{p}^{3T} - \bf{p}^{2T} \\ x'\bf{p'}^{3T} - \bf{p'}^{1T} \\ y'\bf{p'}^{3T} - \bf{p'}^{1T} \end{pmatrix}$
• Solving for the world coordinate X via SVD and dividing by the fourth element produces homogeneous world coordinates ready for plotting. For this 3D point's color, I take an average of the colors at the corresponding pixel points.
• Repeating this for all point correspondences gives an array of world coordinates that can be plotted to illustrate a 3D point cloud.

Q4 Reconstruct your own scene!

Multi-view sloth images:

Multi-view mug images:

Results using COLMAP GUI:

Results using pycolmap package. The green spheres represent the cameras used to capture each image.

Q5 Fundamental matrix estimation on your own images

Q6 Stress test the hyperparameters of COLMAP

Chosen questions for stress tests:

• What happens if we reduce the number of input images
• What happens if we play with some tolerance parameters? I chose the number of SIFT features and the peak threshold

Cutting the number of images in half (choosing every other image) results in a far poorer 3D reconstruction. It stands to reason from this result that more images of the scene lead to a more faithful reconstruction

The number of SIFT features defaults to a maximum of 8192. Limiting this to 1000 leads to a sparser reconstruction, because there are fewer features on which to match between the provided images. Fewer matches means fewer correspondences and therefore fewer 3D points projected. By similar logic, doubling the number of SIFT features to 16384 yields a denser reconstruction.

The peak_threshold parameter in COLMAP defaults to 0.006667 and is the cutoff for a pixel to be marked as a keypoint when using SIFT and the difference-of-Gaussians metric to compare pixel neighborhoods at varying scales. A lower threshold means that regions with lower contrast will be identified as keypoints, thereby typically increasing the number of keypoints. Conversely, a higher threshold means that the region around a given pixel must have a higher contrast to be considered a keypoint, thereby typically decreasing the number of keypoints. I observe this impact in my reconstructions, where the affect of halving this threshold is a denser reconstruction with more background points included. Conversely, the impact of doubling this threshold is that the reconstruction is a bit sparser.