Assignment 3

Q1: 8-point and 7-point algorithm 

(A1) F matrix using 8-point algorithm

Epipolar Lines

Methodology:

  1. Load the points and normalize them
  1. If the correspondence consists of points x1=(u1,v1,z1)x_1 = (u_1, v_1, z_1) and (u2,v2,z2)(u_2, v_2, z_2) then:

x1TFx2=0  ⟹  [u1v1w1]TF[u2v2w2]=0[u2u1u2v1u2w1v2u1v2v1v2w1w2u1w2v1w2w1]f=0x_1^TFx_2=0 \implies \begin{bmatrix} u_1&&v_1&&w_1\end{bmatrix}^TF\begin{bmatrix} u_2 \\ v_2 \\ w_2 \end{bmatrix} = 0 \\ \begin{bmatrix} u_2u_1&&u_2v_1&&u_2w_1&&v_2u_1&&v_2v_1&&v_2w_1&&w_2u_1&&w_2v_1&&w_2w_1\end{bmatrix}f=0

where f is the flattened F vector

So each correspondence gives one constraint, constraints from 8 such points can be stacked together to give a matrix of form

Af=0Af=0

Here A is 8x8 matrix, f can be found out by performing SVD decomposition of A and choosing the right singular vector

  1. Denormalize the obtained F
  1. Say F is the fundamental matrix found in step 3, then rank 2 constraint can be imposed by
    U,Σ,VT=SVD(F)Σ[2,2]=0F=UΣVTU, \Sigma, V^T = SVD(F) \\ \Sigma [2,2] = 0 \\ F = U\Sigma V^T

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

Results:

Bench:
E matrix using 8 point algorithm is: 
 [ -0.4152  -8.8175  -2.1506]
 [ -1.3804   0.7907  69.0827]
 [ -3.5889 -68.4744   1.    ]

Remote:
E matrix using 8 point algorithm is: 
 [ 2.5298  -0.6706   7.3309]
 [ -6.6203  -3.0277 -28.2986]
 [-14.5007  26.4182   1.    ]

Methodology:

  1. Once F is found, E can be found using

E=(K′)TFKE = (K')^TFK
  1. Enforce low rank constraint by
U,Σ,VT=SVD(E)Σ=diag(σ1,σ2,σ3)Σ=diag((σ1+σ2)/2,(σ1+σ2)/2,0)E=UΣVTU, \Sigma, V^T = SVD(E) \\ \Sigma = diag(\sigma_1, \sigma_2, \sigma_3) \\ \Sigma = diag((\sigma_1+\sigma_2)/2, (\sigma_1+\sigma_2)/2, 0) \\ E = U\Sigma V^T

(B) 7-point algorithm (20 points)

Epipolar Lines:

Methodology:

  1. Load the points and normalize them
  1. If the correspondence consists of points x1=(u1,v1,z1)x_1 = (u_1, v_1, z_1) and (u2,v2,z2)(u_2, v_2, z_2) then:

x1TFx2=0  ⟹  [u1v1w1]TF[u2v2w2]=0[u2u1u2v1u2w1v2u1v2v1v2w1w2u1w2v1w2w1]f=0x_1^TFx_2=0 \implies \begin{bmatrix} u_1&&v_1&&w_1\end{bmatrix}^TF\begin{bmatrix} u_2 \\ v_2 \\ w_2 \end{bmatrix} = 0 \\ \begin{bmatrix} u_2u_1&&u_2v_1&&u_2w_1&&v_2u_1&&v_2v_1&&v_2w_1&&w_2u_1&&w_2v_1&&w_2w_1\end{bmatrix}f=0

where f is the flattened F vector

So each correspondence gives one constraint, constraints from 7 such points can be stacked together to give a matrix of form

Af=0Af=0

Where A is 7x8 matrix

We can find the basis of null space of A as the last 2 right singular vectors. Say those vectors are

f1,f2f_1, f_2

  1. Denormalize the obtained F’s.
  1. Any F that satisfies Af=0 can be written in terms of f1 and f2 as

    F=λF1+(1−λ)F2F = \lambda F_1 + (1-\lambda) F_2
  1. Since F is not full rank ⇒ determinant (F) = 0; This is a cubic equation in F
  1. Solve the equation to find possible values of λ\lambda and hence F . Out of real solutions, choose the one that minimises epipolar error. The epipolar error is defined by:
epiolar error=Σ(x′TFx+xTFx′)\text{epiolar error} = \Sigma (x'^TFx + x^TFx')
  1. Say F is the fundamental matrix found in step 6, then rank 2 constraint can be imposed by
U,Σ,VT=SVD(F)Σ[2,2]=0F=UΣVTU, \Sigma, V^T = SVD(F) \\ \Sigma [2,2] = 0 \\ F = U\Sigma V^T

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

Methodology

The criterion for selecting inliers is the epipolar error.

For a given correspondence (x,x′)(x,x') the epipolar error is defined as the distance of each point from the epipolar line. Mathematically

e(F,x1,x2)=Σ(x′TFx+xTFx′)e(F,x_1,x_2) = \Sigma (x'^TFx + x^TFx')

Points with epipolar error < tolerance are considered inliers, otherwise outliers

The RANSAC approach is as follows:

Results

bench 8 point

bench 7 point

inlier vs # iters
ball 8 point
ball 7 point
inlier vs # iters

hydrant 8 point
hydrant 7 point
inlier vs # iters
remote 8 point

remote 7 point

inlier vs # iters

Q3: Triangulation

Methodology

  1. For each correspondence (x, X) we can write x=PXx = PX
x×Px=0[x]×Px=0x \times Px = 0 \\ [x]_\times Px = 0
[x]×=[0−x3−x2x30−x1x2−x10][x]_{\times} = \begin{bmatrix} 0 & -x_{3} & -x_{2} \\ x_{3} & 0 & -x_{1}\\ x_{2} & -x_{1} & 0 \end{bmatrix}
The equation can be written as AX = 0, whereA=[x1P3−P1x2P3−P2x1′P3−P1′x2′P3−P2′]X is the right singular vector of AX=XX[−1]\text{The equation can be written as AX = 0, where} A = \begin{bmatrix} x_1 P_3 - P_1 \\ x_2 P_3 - P_2 \\ x'_1 P_3 - P'_1 \\ x'_2 P_3 - P'_2 \end{bmatrix} \\ \text{X is the right singular vector of A}\\ X = \frac{X}{X[-1]}
  1. Similarly compute 3D point X for each correspondence
  1. Assign color to each point based on the images
  1. Plot the points using matplotlib

Visualizations

Q4: Reconstruct your own scene! (20 points)

Scenario 1:

Lab Images

https://drive.google.com/drive/folders/16fzRD1p4BhL05mD7Dge1sWKWIAUE9rN3?usp=sharing

Reconstruction

Scenario 2:

Robotic arms on tabletop:

Images Link : https://drive.google.com/drive/folders/1-5b1NlHhiVevm0cqkBNXTKvZGCyPiE59?usp=sharing

Q5: Bonus 1 - Fundamental matrix estimation on your own images. (10 points)

Methodology: