Project 3: Camera Calibration and Fundamental Matrix Estimation with RANSAC

In this project, I need to estimate the camera projection matrix which maps 3D world coordinates to image coordinates. Also, I need to find the fundamental matrix which relates points in one scene to epipolar lines in another. In the end, RANSAC will be implemented to find the fundamental matrix with the most inliers.

  1. Camera Projection Matrix
  2. Fundamental Matrix Estimation
  3. Fundamental Matrix with RANSAC

Camera Projection Matrix

In camera projection matrix, I used nonhomogeneous linear system to solve for m's entries using linear least squares.

  1. Setup a homogenous set of equations using the corresponding 2D and 3D paris
    M = zeros(3,4);

[row, ~] = size(Points_3D);
%nonhomogeneous linear system
Co3D = [Points_3D, ones(row,1)];
% A*x = b
A = zeros(row*2, 11);
b = zeros(row*2, 1);
%linear least squares
for i = 1:row
    
    X = Points_3D(i,1);
    Y = Points_3D(i,2);
    Z = Points_3D(i,3);
    
    u = Points_2D(i,1);
    v = Points_2D(i,2);
    
    A(2*i - 1,:)=[Co3D(i,:),zeros(1,4),-u*X -u*Y -u*Z];
    A(2*i,:)=[zeros(1,4), Co3D(i,:),-v*X -v*Y -v*Z];
    b(2*i - 1) = u;
    b(2*i) = v;
end
  2. Then I solve the nonhomogeneous linear system by which also can be written as 
    M = A\b;
M = [M;1];
M = reshape(M,[],3)';
    3. After solving nonhomogeneous linear system, I can get which is the projection Matrix M.
  3. To find the camera coordinates, I used my projection matrix where Q is the first 3x3 elments and m4 is the 4th column of M. 
    
Q = M(1:3,1:3);
Center = -inv(Q)*M(:,4);

Fundamental Matrix Estimation

In fundamental matrix estimation, it is pretty similar to part 1. To build fundamental matrix, I need to get two sets of correspondences of two images. And then use 8-point algorithm: least squars solution using SVD on equations from 8 pairs of correspondences; enforce det(F)=0 constraint using SVD on F. 


A = zeros(row, 9);

for i = 1:row
    u = Points_a(i,1);
    v = Points_a(i,2);
    u2 = Points_b(i,1);
    v2 = Points_b(i,2);
    
    A(i,:) = [u*u2 u2*v u2 v2*u v*v2 v2 u v 1];
end
%Solve f from Af=0 using SVD
[U, S, V] = svd(A);
f = V(:,end);
F = reshape(f, [3 3])';

%Resolve det(F) = 0 constraint using SVD
[U, S, V] = svd(F);
S(3,3) = 0;
F_matrix  = U * S* V';
F_matrix

Results without normalizing coordinates

In this part, I did the extra credits by normalize coordinates. At first, I center the image data at the origin and scale the coordinates such that the average squared distance from the origin is 2 and then using to find the transform matrix for the mean coordinates. 


norm = sqrt(2);
if norm == sqrt(2)
    %mean coordinates
    c = mean(Points_a);
    c_u = c(1,1);
    c_v = c(1,2);
    
    c2 = mean(Points_b);
    c_u2 = c2(1,1);
    c_v2 = c2(1,2);
    
    sqdist = 0;
    sqdist2 = 0;
    for i = 1:row
        sqdist = sqdist + (Points_a(i,1)-c_u)^2 + (Points_a(i,2)-c_v)^2;
        sqdist2 = sqdist2 + (Points_b(i,1)-c_u2)^2 + (Points_b(i,2)-c_v2)^2;
    end
    
    %scale the coordinates such that the average squared distance from the origin is 2
    s = sqrt(2/(sqdist / row));
    s2 = sqrt(2/ (sqdist2 / row));
    
    T = [s 0 0; 0 s 0; 0 0 1] * [1 0 -c_u; 0 1 -c_v; 0 0 1];
    T2 = [s2 0 0; 0 s2 0; 0 0 1] * [1 0 -c_u2; 0 1 -c_v2; 0 0 1];
    
    Pa_T = zeros(row,2);
    Pb_T = zeros(row,2);
    
    for i = 1:row
        pt = transpose(T * [Points_a(i,1);Points_a(i,2);1]);
        Pa_T(i,:) = pt(1,1:2);
        pt2 = transpose(T2 * [Points_b(i,1);Points_b(i,2);1]);
        Pb_T(i,:) = pt2(1,1:2);
    end
    
    Points_a = Pa_T;
    Points_b = Pb_T;
end
After that, to calculate fundamental matrix by 

if norm == sqrt(2)
    F_matrix = transpose(T2)*F_matrix*T;
end

Results with normalizing coordinates

As the result, we can see the normalizing do improve the result of fundamental matrix.

Fundamental Matrix with RANSAC

In fundamental matrix with RANSAC, we need to use random sampling consensus to compute fundamental matrix with unreliable point correspondences computed with SIFT. I use 8 points algorithm to fit a line and find the fundamental matrix of it. Then, using the threshold I can decide which points are inliers. I set the threshold as 0.005 to make sure I can get enough inliers with a high accuracy. Then,I manully set the interation to 1000 instead of using formula N = log(1-p)/log(1-(1-e)^s). 


[row, ~] = size(matches_a);
Num = 0;
correctInd = [];
max = 0;

%set interation to 1000
for itera= 1:1000
    %fit a line by chosing 8 random points
    indices = randperm(row, 8);
    Fmatrix = estimate_fundamental_matrix(matches_b(indices,:),matches_a(indices,:));
    
    tempNo = 0;
    temp = [];
    for i = 1:row
        %possible inlier inside the threshold 0.005
        if abs([matches_b(i,:) 1] * Fmatrix * [matches_a(i,:) 1]') < 0.005
           tempNo = tempNo + 1;
           temp = [temp; i];
        end
    end
    
    if tempNo == row
        Best_Fmatrix = Fmatrix;
        correctInd = temp;
        break;
    end
    
    if tempNo > Num
        Num = tempNo;
        Best_Fmatrix = Fmatrix;
        correctInd = temp;
    end
end

if max == 0 || max>size(correctInd,1)
    max = size(correctInd,1);
end

inliers_a = matches_a(correctInd(1:max),:);
inliers_b = matches_b(correctInd(1:max),:);

end

Observations

In this project, I learned the knowledge of the camera and scene geometry in computer vision. Furthermore, I want to improve my part3 which is the fundamental matrix with RANSAC because it do have some ouliers that did not remove by my code and the number of inliers need to be more large. In addition, this project is a basic project but it can be learned much more and help me a lot in future projects such as 3D reconstruction.