Assignment 3

Q1: 8-point and 7-point algorithm (40 points)

(A1) F matrix using 8-point algorithm (15 points)

Bench:

F=[-1.19265833e-07 -2.53255522e-06  2.07584109e-04]
  [-3.96465204e-07  2.27096267e-07  2.48867750e-02]
  [-1.06890748e-03 -2.30052117e-02  1.00000000e+00]

Remote:

F=[ 7.19006698e-07 -1.90583125e-07  2.36215166e-03]
  [-1.88159055e-06 -8.60510729e-07 -8.45685523e-03]
  [-3.98058321e-03  9.46500248e-03  1.00000000e+00]

Explanation:

I implemented the normalized 8 point algorithm (Algorithm 11.1 in Hartley & Zisserman)

Mean center and l2 normalize points in both images by multiplying points with 3x3 T1 and 3x3 T2 transformations for image 1 and 2 respectively.

T1 = # m: mean, s: scale
    [1/s, 0, -m[0]/s]
    [0, 1/s, -m[1]/s]
    [0,   0,       1]

Every two correspondences create a constraint of the following form:

[x'*x, x'*y, x', y'*x, y'*y, y', x, y , 1]

Stack 8 of these constraints, compute the SVD and get the null vector and reshape it into the 3x3 F matrix

Decompose F using SVD, set smallest singular value to 0 to enforce rank 2 constraint and recompute F as U@S@Vh

Denormalize to get the final F

F=T1.T @ F @ T2

For epipolar line computation x’.T @ F to get lines in image 2 and F@x to get lines in image 1. A line [a, b, c] describes the y = (-ax - c ) / b euclidian line which can be easily plotted.

(A2) E matrix using 8-point algorithm (5 points)

Given intrinsics and F we can compute E as follows:

E=K'.T @ F @ K

For bench

E=
 [ -0.41524274  -8.81748894  -2.15055808]
 [ -1.3803559    0.79067134  69.08265036]
 [ -3.58890876 -68.47438701   1.        ]

For remote:

E=
 [  2.5298064   -0.67056178   7.33094837]
 [ -6.62032749  -3.02768466 -28.29861665]
 [-14.50071092  26.41824781   1.        ]

(B) 7-point algorithm (20 points)

Approach:

Same construction of the constraint matrix as part A however the matrix will be 7x9 since we only have 7 constraints and hence the null space will be 2 dimensional.

Using SVD we select the two right null vectors as F1 and F2. F will be a linear combination of F1 and F2 and can be written up to a scale ambiguity as $F=\alpha * F1 + (1-\alpha) * F2$

Enforcing the constraint that F must be singular or rank 2 in particular we can assert that det(F) = 0. Algebraically, this gives us a third degree polynomial in alpha. I used sympy to perform the algebra efficiently as (Assuming A is the constraint matrix):

from sympy import MatrixSymbol, Matrix
U, S, Vt = np.linalg.svd(A)
F1 = Vt[-1].reshape(3,3)
F2 = Vt[-2].reshape(3,3)
F1_s = Matrix(F1)
F2_s = Matrix(F2)
F = alpha * F1_s + (1-alpha) * F2_s
poly = sy.Poly(F.det())
coeffs = poly.coeffs()
roots = np.roots(coeffs)

Given a value of alpha we can obtain a solution for F which we can visualize the epipolar lines for and either accept as a solution or discard as the wrong solution. In some cases alpha is imaginary in which case the solution is directly discarded.

Ball Scene

3 solutions for alpha only one is real and that is the one visualized below

[-0.7009503 +1.34514841j -0.7009503 -1.34514841j 0.70248801]

F=
 [-3.35078059e-09 -2.91545005e-06 -6.74891733e-03]
 [ 3.51682683e-06 -8.84237457e-07 -1.50044163e-02]
 [ 9.09398538e-03  1.48748649e-02  1.00000000e+00]
E=
 [-7.87994034e-03 -6.85618523e+00 -1.13753916e+01]
 [ 8.27042679e+00 -2.07943738e+00 -1.67226693e+01]
 [ 1.48533845e+01  1.49490598e+01  1.00000000e+00]

Hydrant Scene

In this scene, we have 3 real solutions for alpha

[3.09573324 0.59398353 0.27324368]

The first two solutions are clearly wrong since the epipole should be the image of the other camera center and the images of camera centers in both images are clearly not in the image. Thus only alpha = 0.27… is feasible.

F=
 [ 1.06836663e-07 -3.30854241e-06 -1.37397509e-03]
 [ 4.79268901e-06  1.63305018e-07 -1.67456794e-02]
 [ 1.12974017e-03  1.64136613e-02  1.00000000e+00]
E=
 [  0.14236494  -4.40879014  -3.7364802 ]
 [  6.38648609   0.2176117  -16.40032786]
 [  4.54672553  16.75194526   1.        ]

Q2: RANSAC with 7-point and 8-point algorithm (20 points)

Approach:

Sample 7 or 8 (Depending on the algorithm) points and compute F as in Q1.

Compute residual error as the distance metric for each correspondence.
$l=[a, b, c], x=[x_0, y_0, 1], d(x,l)=\frac{|ax_0+by_0+c|}{\sqrt{a^2+b^2}}$

error=d(x',Fx)+d(x,F^Tx')

A correspondence is an inlier if error < 2 pixels.

If we have multiple Fs from a 7-point algorithm then the solution with the most number of inliers is considered the correct one.

Repeat 1 through 4 N times and choose the F with the most inliers.

Epipolar lines visualized below are for 30 randomly selected points from the set of inliers. Since the set of inliers is huge.

Bench

7-Point

Best F=
[-9.88713594e-08 -2.26560181e-06  1.21278726e-04]
[-6.61536559e-07  2.31817791e-07  2.48928997e-02]
[-9.97643478e-04 -2.30036383e-02  1.00000000e+00]

8-Point

Best F=
 [-9.14094196e-08 -2.09535492e-06  1.00812291e-04]
 [-6.36148238e-07  3.91694238e-07  2.42036771e-02]
 [-9.81978419e-04 -2.25625178e-02  1.00000000e+00]

Ball

7-Point

Best F=
 [-6.63322574e-08 -3.16493166e-06 -5.86670688e-03]
 [ 3.76835724e-06 -9.35546586e-07 -1.42202577e-02]
 [ 7.97324855e-03  1.41889931e-02  1.00000000e+00]

8-Point

Best F=
 [ 8.14492599e-08 -2.42704592e-06 -7.98154344e-03]
 [ 2.98751162e-06 -7.93181768e-07 -1.58598768e-02]
 [ 1.06900175e-02  1.55630745e-02  1.00000000e+00]

Remote

7-Point

Best F=
 [ 2.56586584e-06 -2.28367789e-05  4.99321297e-03]
 [ 3.13672371e-05  7.50548872e-06  4.40254986e-03]
 [-8.45651045e-03 -1.30927080e-02  1.00000000e+00]

8-Point

Best F=
 [ 1.09284791e-06 -2.38904781e-05  2.80827874e-03]
 [ 3.67359825e-05  1.33938134e-05  1.26173526e-02]
 [-4.68846437e-03 -2.77691089e-02  1.00000000e+00]

Hydrant

7-Point

Best F=
 [ 1.20476479e-07 -2.81930352e-06 -1.56557214e-03]
 [ 4.28304084e-06  2.32507706e-07 -1.63766309e-02]
 [ 1.36314054e-03  1.59615357e-02  1.00000000e+00]

8-Point

Best F=
 [ 1.40794023e-07 -2.39643801e-06 -1.73116724e-03]
 [ 3.83245903e-06  2.68313090e-07 -1.59221224e-02]
 [ 1.51955793e-03  1.54587791e-02  1.00000000e+00]

Q3: Triangulation (20 points)

Approach:

I used the Homogeneous DLT method as follows:

For each point correspondence, construct a 4x4 constraint matrix as:

A=\begin{bmatrix} xp^{3T}-p^{1T}\\ yp^{3T}-p^{2T}\\ x'p'^{3T}-p'^{1T}\\ x'p'^{3T}-p'^{2T} \end{bmatrix}

where $p^{iT}$ corresponds to the ith row of the P matrix.

Use SVD and choose the right singular vector that corresponds to the smallest singular value as our triangulated X in projective 3 space. Normalize by 4th element to extract x,y,z in Euclidian 3 space.

As for the color I directly use x and x’ to index into img1 and img2 to retrieve two matching colors. I then take the average and use that as the color for the 3D point.

I then repeat the process for every point correspondence to triangulate all points.