Creston Bunch

Project 3 / Camera Calibration and Fundamental Matrix Estimation with RANSAC

Part 1

Part 1 was straightforward. To solve for the projection matrix I set up a system of linear equations and solved using SVD, enforcing the constraint that the solutions are not all 0.

To solve for the camera center, I followed the method from class which splits the transformation matrix into Q and m4 to find the world coordinates of the camera.

The output of my code is:

The projection matrix is:
    0.4583   -0.2947   -0.0140    0.0040
   -0.0509   -0.0546   -0.5411   -0.0524
    0.1090    0.1783   -0.0443    0.5968


The total residual is: <0.0445>

The estimated location of camera is: <-1.5127, -2.3517, 0.2826>

Part 2

To estimate the fundamental matrix I first normalized the points in each image so that they are centered around 0,0 and scaled from -1 to 1. This helps improve the accuracy of the estimation (as proposed by Hartly).

After normalization, I estimate F using the 8-point algorithm by solving a system of homogeneous linear equations using SVD. Then I enforce rank(F) = 2 by setting the smallest singular value to 0 and reconstructing it.

Results With Normalization

F_matrix =

   -0.0000    0.0000   -0.0001
    0.0000   -0.0000    0.0011
   -0.0000   -0.0015    0.0345

Results Without Normalization

Closeup difference

Original	Normalized	Difference

F_matrix =

   -0.0000    0.0000   -0.0019
    0.0000    0.0000    0.0172
   -0.0009   -0.0264    0.9995

If you look close enough, you will see that the epipolar lines from the normalized fundamental matrix are closer to the original points in the images. So it makes sense to normalize the points first to improve accuracy.

Part 3

For this part I implemented RANSAC to estimate the fundamental matrix using matched SIFT features. This process helps remove spurious matches in the SIFT pipeline by looking for the best fundamental matrix to describe the image transformation and the best inliers that fit the fundamental matrix.

The fundamental matrix can describe a transformation from one image to another. In the ideal scenario x^TFx' = 0. But since our fundamental matrix is an estimate, we are looking for inliers within a specific threshold. For most cases I set the threshold to 0.1.

There is nothing special about my implementation, but I do normalize the points for estimating the fundamental matrix. You can see the effect it has on the Gaudi image pair below. Since RANSAC is a randomized algorithm, we may want to know how many iterations it will require for 99% accuracy. There is a bound we can calculate, but intuitively the longer we run it the better we should do. For most cases I ran 100,000 iterations.

Mount Rushmore

This was the easiest image pair. My best results are shown below:

Sift Matches

RANSAC Matches

Epipolar Lines

Summary

The low number of bad SIFT matches leads to a pretty good fundamental matrix estimation. You can see RANSAC filtered most of the bad matches out, but there are still a couple. The epipolar lines are very reasonable, however. We should expect each corresponding line to cover the same points in each image. In this case the lines may not be perfect matches, but it is easy to see they are pretty close.

Mount Rushmore 100 iterations

I ran Mount Rushmore again using only 100 instead of 100000 iterations

RANSAC Matches

Epipolar Lines

Summary

It does slightly worse, but still performs an admirable job at filtering out bad matches. We can attribute this to the theoretical bounds on how many iterations are necessary to be 99% certain at least one sample is free of outliers. In particular, if there is only a 30% chance of sampling an outlier then we need only about 78 iterations. Due to the low number of bad SIFT matches, we can estimate the chance of sampling an outlier is probably around 10%-30%.

Notre Dame

Sift Matches

RANSAC Matches

Epipolar Lines

Summary

This image pair is pretty hard since the images are relatively planar, and the fundamental matrix is degenerate on planar images. However we still see a rather successful reduction in spurious matches. The epipolar lines don't quite correspond however, so we can expect this to be a somewhat bad estimate of the fundamental matrix.

Gaudi

Sift Matches

RANSAC Matches

Epipolar Lines

Summary

Once again RANSAC shows its ability to filter bad matches. Although not perfect we can see a substantial improvement. The epipolar lines are still not quite right though.

Gaudi Without Normalization

Sift Matches

RANSAC Matches

Epipolar Lines

Summary

Without changing any RANSAC parameters, RANSAC can be seen performing slightly worse using the original coordinates to estimate F. In particular you can see an increased number of bad matches in the sky and on the ground. So it seems to always be a good idea to normalize points before estimating the fundamental matrix.

Woodies

Sift Matches

RANSAC Matches

Epipolar Lines

Summary

I think the effect of RANSAC filtering bad matches is most evident on this image pair. You can clearly see a ton of matches, especially close to the image boundaries where they are very different, are removed by RANSAC. The epipolar lines are not quite right, however. They look as if they are showing up on the wrong image pairs.

Woodies For 500000 Iterations

Sift Matches

RANSAC Matches

Epipolar Lines

Summary

Since there are more bad matches to start with, the chance of sampling an outlier is much higher on this image pair. Running it longer shows that you can do slightly better as expected. However there are still a couple noticeably bad matches and the epipolar lines are still very wrong.