Geometry-based Methods in Vision: 3D Reconstruction Results
Q1a.1: Summary of 8 point algorithm
The 8 point algorithm utilized constraints on corresponding image points in image 1 and 2 x and x', respectively, to find an F s.t. x'^TFx=0. First we normalize our points using homography T, which we later undo by returning F=T^TFT To enforce these constraints linearly, we perform the matrix premultiplication trick to premultiply x'T and x by creating a matrix A s.t. every point pair creates a single constraint (row) in A=[x1*x2, x2*y1, x2, y2*x1, y2*y1, y2, x1, y1, 1] s.t. Af = 0 if and only if x'^TFx=0 where F is the reshapen matrix of f. We solve for f using SVD and taking the last singular vector.
Q1a.2: Summary of essential matrix algorithm
Using the known intrinsic matrices K' and K, we simply solve for E=K'^TFK
Epipolar Lines from Image 1
3x3 Essential Matrix:
| -0.07274264 0.04166717 3.64054968|
| -0.18912998 -3.60849513 0.05269847 |
Epipolar Lines from Image 2
3x3 Essential Matrix:
| 1.28101882 0.58585033 5.47572011 |
| 2.80585569 -5.11187288 -0.1934978 |
Q1b: Summary of the 7-Point Algorithm
Using the same x'^TFx normalization and then minimization scheme as for the 8=point algorithm, we construct two fundamental matrices F1 and F2 out of the now last two singular vectors of A. Then, we solve for F where F=alpha*F1+(1-alpha)*F2 and det(F)=0. To do this, we expand alpha*F1+(1-alpha)*F2= alpha*P+Q where P=(F1-F2) and Q=F2, and then solve for the determinant as a polynomial of alpha. To do this, I factorized P and Q into their components and explicitly wrote out the degree 3 polynomial. Then, we solve for the roots of the polynomial, and to choose the best F, I took the F with the largest norm (persuming the epipoles would not be visible in the camera frame - that the movement between frames was semi-parallel).
Epipolar Lines from Ball Image
Epipolar Lines from Hydrant Image
Q2: Summary of Algorithm
Performing RANSAC involved writing a loop that iteratively selected random samples of the matched points (either 7 or 8), check for inliers within some distance threshold - I found that the best threshold while comparing normalized coordinates was around 0.001 for manually labeled pairs and 0.01 for the SIFT feature pairs. The iterations continued, keeping track of the best matrix found so far, until either they exceeded the iteration threshold or a sufficient number of inliers were found. We then recomputed the matrix using all the inliers.
Plot of Inlier Counts
Epipolar Lines from 7-Point Algorithm
Final Percent of Inliers: 58.88%
Epipolar Lines from 8-Point Algorithm
Final Percent of Inliers: 44.44%
Q3: Summary of Triangulation Algorithm
Triangulation involved individually solving a 4x3 constraint matrix constructed by projecting points x and x' along their corresponding projection lines, and finding where the lines intersected. To do this, we use the constraint that this intersection point must be on line Px and P'x', which gives us two constraints per point, and thus 4 constraints in total. We then just solve for X using SVD. We do this for every point correspondence and plot the result. To get the color of the 3D point, we average the color of the pixels sampled in both images for the corresponding 3D point.
Triangulation
Q4: 3D reconstruction
For this, I installed pycolmap, created the script, and tried running it for sparse reconstruction. I tried to perform reconstruction on my own image sets, but this did not work because I realized colmap was unable to find a sufficient number of good enough matches between images. So then I tried running colmap on a large dataset I downloaded online. My script ran as shown and successfuly performed triangulation on the dataset. However, I was unable to render the points, even in Meshlab, because the outputs were all .bin files, which I was unable to open.
3D Reconstruction Image
Q5 Bonus: Summary of Algorithm
To find the fundamental matrix on my own images, I computed SIFT features and performed matching between images. Then, the same algorithm was applied on the features, though this time, there were many more matches than 7 or 8 points, and so I selected them by similarity.
7-Point Algorithm Results
Arch Dataset
Final Percent of Inliers: 43.2%
Scaife Dataset
Final Percent of Inliers: 46.0%
8-Point Algorithm Results
Arch Dataset
Final Percent of Inliers: 37.8%
Scaife Dataset
Final Percent of Inliers: 44.2%