Project 3: Scene Geometry

This project has three parts distict parts and takes in two images for each part. I will discuss the algorithms to accomplish each of the three steps. I also implmented the normalization of points to generate the fundemental matrix; I will discuss the effects of that in parts one and two.

  1. Create the camera projection matrix
  2. Create the fundemental matrix
  3. Use RANSAC and the epipolar lines to filter out spurious SIFT matches

1. Create the camera projection matrix

Part one consisted of two separate steps: computing the projection matrix and computing the camera center.

Projection matrix 1 I must create the projection matrix that converts the 3D coorindates to the 2D coordinates. The desired projection matrix is on the right.
Projection matrix 2 The first step is to set up the system of linear equations derived from the homogenous coordinates and the projection matrix. I loop through all the points to cenerate the system of linear equations; there are two equations per points.
Projection matrix 3 Next, I used SVD to solve the system of linear equations. The solution is the projection matrix. The matrix I obtained with the normalized points is to the right.
-0.4583 0.2947 0.0140-0.0040
0.0509 0.0546 0.5411 0.0524
-0.1090-0.1783 0.0443-0.5968
Camera Center With the projection matrix, computing the camera center is relatively easy. It is the negative inverse of the first three columns of the projection matrix multiplied by the last column. The coordinates of the camera center obtained through the normalized points is shown to the side. -1.5127, -2.3517, 0.2826

2. Create the Fundemental Matrix

The fundemental matrix is the matrix that represents the distortions between to images such that xTFx' = 0 Where x and x' are points on the two images. I implement the 8-point algorithm to estimate the fundemental matrix.

Setting up the Matrix I first set up the system of linear eqations derived from the matrix on the right
Solving the matrix I use SVD to solve the system on linear equations I set up in the previous step. The explicit equation is on the right. There needs to be at least 8 points available to find a solution. The solution gives out fundemental matrix.
Resolving the rank 2 constriaint To resolve the rank 2 constraint, I use SVD to split F into U,S,V. I then took the smallest value along the diagonal and set it to 0. This ensure the rank 2 constraint. The resulting fundemental matrix for the set of normalized points is shown on the right.
-0.0000 0.0000-0.0019
0.0000 0.0000 0.0172
-0.0009-0.0264 0.9995
Generating the epipolar lines The fundemental matrix allows me to generate the epipolar lines on the images shown to the right. As you can see each line goes through a point. Although, there appears to be some small error between some lines and their corresponding points.
Normalizing the matrix Normally, the fundemental matrix takes in normalized points for better accuracy. I tried normalizing the points so that the mean was 0 and the average magnitude is one. I then changed the fundemental matrix back into the original scale before resolving any possible rank issues. The aquired matrix is shown on the right.
-0.0000 0.0000-0.0005
0.0000-0.0000 0.0042
-0.0000-0.0058 0.1399
Generating the epipolar lines The new fundemental matrix allows me to generate the epipolar lines on the images shown to the right. The normalization has largely gotten rid of the errors.

Use RANSAC and the epipolar lines to filter out spurious SIFT matches

RANSAC is an algorithm for searching for the best set of points to use to generate the best fundemental matrix between the two images. Implemeneted it in the following steps.

There are two free parameters in RANSAC: the number of iterations and the inlier threshold. I set the number of iterations to 7000 and the inlier threshold to .0055 because those values were giving me visible and accurate results.

Pick Points I choose 8 random points for each iteration and estimate the fundemental matrix with them.
Calculate Distance With the estimated fundemental matrix, I can set up the a distance measure for every point using xTFx'. This works as a distance measure since the desired vallue for this expression is 0.
Get Inliers Next, found the points whose distances that were below the threshold I set at .0055.
Get Best Fundemental Matrix I store the fundemental matrix with the most inliers of all the points. I then report that matrix and the inliers at the end of the loop.

RANSAC Results

I was able to obtain the results with and without normalization. The reulst with normalization were much more accurate.

Image Set Matches Epipolar Lines A Epipolar Lines B
Notre Dame without normilization
Notre Dame with normilization
Mount Rushmore without normilization
Mount Rushmore with normilization
Episcopal Gaudi without normilization
Episcopal Gaudi with normilization