**Geometry-based Methods in Vision** **Assignment 3** - Epipolar geometry and Two-view 3D Reconstruction 8-point and 7-point algorithm ============================================================== F matrix using 8-point algorithm -------------------------------------------------------------- - Bench | Viewpoints 1 (Points) | Viewpoint 2 (Epipolar Lines) | |----------|---------| | | |  - Remote | Viewpoints 1 (Points) | Viewpoint 2 (Epipolar Lines) | |----------|---------| | | |  **Implementation details**
We start with the constraint that relates the correspondences with the fundamental matrix.  It helps to normalize the points to have zero mean and unit variance with the help of a transformation matrix for points of both the images. We can then solve for F using SVD by constructing the A matrix of shape 8x9 using the point correspondences as shown below.  After getting F, we need to enforce det(F)=0 or make its rank=2 by taking SVD of F and assigning the smallest singular value to be 0 and recomputing F as shown below.  We need to then unnormalize F using the transformation matrices used before to get the final F as shown below.  The final F can be multiplied with any point on the image to get its corresponding epipolar line on the other image. E matrix using 8-point algorithm -------------------------------------------------------------- - Bench  - Remote  **Implementation details**
Given the fundamental matrix F (from above) and intrinsic matrices K and K_dash, we can compute the essential matrix E using the below relation.  7-point algorithm -------------------------------------------------------------- - Hydrant | Viewpoints 1 (Points) | Viewpoint 2 (Epipolar Lines) | |----------|---------| | | |   - Ball | Viewpoints 1 (Points) | Viewpoint 2 (Epipolar Lines) | |----------|---------| | | |   **Implementation details**
We follow a similar implementation here like the 8-point algorithm with a few differences. Since F has 7 DoF, 7 point correspondences are sufficient to determine F. We follow the same normalization process as 8-point and using the same constraint and construct the A matrix in the form of Af = 0 as shown below. Only difference is here the A matrix is of shape 7x9.  We get two solutions, F1 and F2 from SVD of A by using the last 2 singular vectors of A. A general solution to F is a linear combination of F1 and F2 as shown below and we can enforce the constraint that det(F) = 0 as shown below.  This gives us a 3-degree polynomial equation whose roots can be used to determine F. Once we get this F, we need to enforce rank-2 just like 8-point algorithm and unnormalize the obtained F. RANSAC with 7-point and 8-point algorithm ============================================================== - Bench | Viewpoints 1 (Points) | Viewpoint 2 (Epipolar Lines from 8pt) | |----------|---------| | | | | Viewpoints 1 (Points) | Viewpoint 2 (Epipolar Lines from 7pt) | |----------|---------| | | |   - Remote | Viewpoints 1 (Points) | Viewpoint 2 (Epipolar Lines from 8pt) | |----------|---------| | | | | Viewpoints 1 (Points) | Viewpoint 2 (Epipolar Lines from 7pt) | |----------|---------| | | |   - Hydrant | Viewpoints 1 (Points) | Viewpoint 2 (Epipolar Lines from 8pt) | |----------|---------| | | | | Viewpoints 1 (Points) | Viewpoint 2 (Epipolar Lines from 7pt) | |----------|---------| | | |   - Ball | Viewpoints 1 (Points) | Viewpoint 2 (Epipolar Lines from 8pt) | |----------|---------| | | | | Viewpoints 1 (Points) | Viewpoint 2 (Epipolar Lines from 7pt) | |----------|---------| | | |   **Implementation details**
RANSAC is an iterative approach of finding the best fundamental matrix. In each iteration, we take 8 points or 7 points randomly from the given noisy correspondences and compute F using 8-point or 7-point algorithm. Using this F, the epipolar line is calculated for every point and the distance between them is used as a criteria to determine if its an inlier. If the distance is below a threshold then the point is an inlier. In every iteration, the number of inliers is tracked and the correspondences with the highest inliers is taken to compute the final best F. Threshold and number of iterations has to be tuned based on the images and their correspondences. Triangulation ==============================================================    **Implementation details**
For every point correspondence (x, x_dash), a 3D point X can be determined by using the below relation.  A matrix can be constructed for every correspondence in the form of AX=0 and solved using SVD to obtain the corresponding 3D point as shown below.  Here pts1, pts2 are 2D point correspondences and P1, P2 are camera matrices of camera 1 and camera 2 respectively. These obtained 3D points can be plotted using their corresponding color from either image 1 or image 2. Reconstruct your own scene! ============================================================== - Scene 1 - teddy bear **Example Multi-view images** | | | | |----------|---------|---------| | | | | | | | |  - Scene 2 - ducks with a top **Example Multi-view images** | | | | |----------|---------|---------| | | | | | | | |  Fundamental matrix estimation on your own images ============================================================== - Scene 1 - bottle with hat | Viewpoints 1 (Points) | Viewpoint 2 (Epipolar Lines from 8pt) | |----------|---------| | | | - Scene 2 - cluttered table | Viewpoints 1 (Points) | Viewpoint 2 (Epipolar Lines from 8pt) | |----------|---------| | | |  **Implementation details**
For this, I start by extracting SIFT keypoints and feature descriptors from the images and match the descriptors using brute force kNN matcher. This will give me a set of correspondences which mostly is noisy. I can then use RANSAC to get the best 8 correspondence points and get its corresponding fundamental matrix. Using this F, the epipolar lines are plotted for 20 randomly selected points from the correspondences.