Project 3 / Camera Calibration and Fundamental Matrix Estimation with RANSAC

In this project I implemented functions that will:

  1. Identify the 3-D world coordinates of a camera, given labeled correspondences from 2D points in an image to their 3D world coordinates.
  2. Estimate the fundamental matrix associated with two images of the same scene
  3. Use the fundamental matrix and RANSAC to find good keypoint matchings between two images of the same scene.

Implementation details

For part 1, I first checked that we had enough data points to calculate the projection matrix and find the camera's location, which should be 6 data points. Then, I constructed the matrix A and the vector b using the input 2D and 3D coordinates, according to the matrix equation from the slides. The projection matrix was found by inverting the matrix A. Finally, we compute the camera center by inverting the rotation matrix multiplied by the intrinsic matrix Q=KR, and multiplying the result by Kt, where t is the translation vector.

Example image showing good agreement between the corresponding points and the epipolar lines.

In part 2, I estimate the fundamental matrix with the eight-point algorithm, after ensuring we have at least 8 points, of course. I construct the matrix A and vector b as shown. After solving for F, I reduce its rank to 2. This is done with singular value decomposition: Decompose F into U,S,V, where S holds the singular values of F. Set the smallest singular value in S to 0, and reconstruct F = USV'. The resulting epipolar lines for the test image are shown here as well.

Finally, part 3 was implemented by running thousands of RANSAC iterations over a set of possible keypoint matches. I implemented RANSAC in the straightforward way, by: a) Drawing 8 points at random. b) Estimating a fundamental matrix F. c) Count the number of inliers out of all input pairs of points, using the absolute value of the distance x_a'*F*x_b as a metric. The parameters that I had to tweak in this implementation were the number of iterations and the threshold for determining inliers. Finally, for visualization, I returned only a random sample of 50 inliers for the best fundamental matrix, which was defined as the matrix that produced the most inliers.

Example code

The MATLAB code below is a snippet from part 3 that runs the RANSAC algorithm with fundamental matrix estimation. 

while (num_it < max_it)
    if (mod(num_it,100)== 0)
        fprintf('running RANSAC iteration number %i\n', num_it);
    end
    % choose random indices
    indices = randsample(length(matches_a), sample_size);
    % estimate F
    F_matrix = estimate_fundamental_matrix(matches_a(indices,:), matches_b(indices,:));
    % set the threshold
    threshold = 0.05;
    tmp_inliers_a = [];
    tmp_inliers_b = [];
    % check if each candidate point is an inlier with this matrix
    for i = 1:length(matches_a)
        x_a = [matches_a(i,:)'; 1];
        x_b = [matches_b(i,:)'; 1];
        distance = abs(x_a'*F_matrix*x_b);
        if distance < threshold
            tmp_inliers_a(end+1,1:2) = matches_a(i,:);
            tmp_inliers_b(end+1,1:2) = matches_b(i,:);
        end
    end
    num_inliers = length(tmp_inliers_a);
    if (num_inliers > max_inliers)
        fprintf('num inliers: %i\n', num_inliers);
        max_inliers = num_inliers;
        Best_Fmatrix = F_matrix;
        fprintf('here is F:\n');
        disp(Best_Fmatrix);
        inliers_a = tmp_inliers_a;
        inliers_b = tmp_inliers_b;
    end
    num_it = num_it + 1;
end

Results in a table

In the examples below, we see that the keypoint matching is done well, but the epipolar lines produced don't seem to be consistent.

Example of epipolar lines and keypoint matching (50 random inliers) for the Notre Dame example.

Example of epipolar lines and keypoint matching (50 random inliers) for the Mt. Rushmore example.

Example of epipolar lines and keypoint matching (50 random inliers) for the Gaudi example.