Project 3 / Camera Calibration and Fundamental Matrix Estimation with RANSAC

For this project I estimated the fundamental matrix and used it to find point correspondences between images and the epipolar lines in both images. This project involves three main parts:

  1. Estimating the Projection Matrix
  2. Estimating the Fundamental Matrix
  3. Estimating the fundamental matrix with unreliable SIFT matches using RANSAC
  4. Extra Credit: Normalization of points before computation of the fundamental matrix

Estimating the Projection Matrix

The projection matrix maps the 2D camera coordinates to the 3D world coordinates. In this part of the project we are given both the known 2D and 3D coordinates and I use them to find the camera projection matrix. To do this I set up a homogeneous linear system as matrix A and then solved for the entries of the projection matrix using linear least squares. 

[U, S, V] = svd(A);
M = V(:,end);
M = reshape(M,[],3)';

I then can easily solve for the camera center using the given projection matrix. 

m4 = M(:, 4);
Q = -inv(M(:,1:3));
Center = Q * m4;

For the given images I got the following results for the projection matrix and camera centers: 

The projection matrix is:
-0.4610    0.2945    0.0030    0.0014
0.0507    0.0549    0.5431    0.0529
-0.1092   -0.1796    0.0311   -0.5935

The total residual is: 0.2707

The estimated location of camera is: -1.4948, -2.3472, 0.2793

Estimating the Fundamental Matrix

In this part of the project I estimated the fundamental matrix. I was given two images of the same thing from different angles and the corresponding SIFT features for the images. Using the matching points, I estimated the fundamental matrix by setting up a linear system of equations. I set the system of equations as a matrix A and then used the fact that Af = 0 to solve the system. Then I used the fact that det(F) = 0 to constrain the matrix. Later on I added normalization of the points prior to the computation of the fundamental matrix. From the fundamental matrix I was able to visualize epipolar lines in the corresponding images, the image below is including normalization.

Estimating the Fundamental Matrix

For this part of the project I estimated the fundamental matrix using the same algorithm as above with the addition of RANSAC. In this part for the project I was given matching SIFT features from the two corresponding images from the VLFeat library. The produced SIFT features are not completely reliable and will change slightly each time this program is run so results might vary slightly. The VLFeat library produced between 5000 to 6000 SIFT points per image and around 800 matching features. To calculate the fundamental matrix only 8 points are needed, so in order compute a fundamental matrix to fit the majority of key points in the scene I used the RANSAC algorithm. I ran the RANSAC algorithm for 1000 iterations in which, for each iteration, the algorithm sampled 8 point pairs and calculated the fundamental matrix based on those pairs. Then I tested how many inliers there were for the calculated matrix. To do this I used the fact that x'TFx = 0 to determine if a point pair (x and x') were inliers or not. I set the threshold to .005. The confidence for the fundamental matrix was calculated by (number of inliers / matching points).

Extra Credit: Normalization of points before computation of the fundamental matrix

In order to increase the accuracy of the estimation of the fundamental matrix I needed to normalize the points. To do this I first find the centroids for the individual points. I normalize the points from the two cameras separately. I then figure out how much to offset the points and how much to scale the points in order set the centroids to the origin. Using the scale and offset I construct a transformation matrix which I then apply to the points and this creates the normalized points. In the below images we can see on the left hand side the epipolar lines of a fundamental matrix calculated without normalization and on the right hand side the effects after doing normalization. Normalization helps the epipolar lines go straight through the key points rather than lying tangent to the points.


Results

These are the results for the RANSAC fundamental matrix estimation. I ran the algorithm for 3 different pairs of images and got 4 resulting images for each pair. In the top left image we see the calculated SIFT point matches. In the top right image we see the inlier matched SIFT points for the calculated fundamental matrix. The bottom two images show the epipolar lines on the pair of images.
The confidence for the fundamental matrix was calculated by (number of inliers / matching points). Confidences for the images shown in the results.

  1. Rushmore: .69
  2. Notre Dame: 0.2693
  3. Episcopal Gaudi: 0.2693

Mount Rushmore

Notre Dame

Episcopal Gaudi