3D Reconstruction

Andrew ID: schittup

(A1) F matrix using 8-point algorithm

Bench

ViewPoint 1 ViewPoint 2
enter image description here enter image description here

Remote

ViewPoint 1 ViewPoint 2
enter image description here enter image description here

Implementation

Given pixel correspondences between 2 image viewpoints (xi<−>xi′)(x_{i} <-> x^{'}_{i}).

  1. We first normalize the pixel values by mean centering them and enforcing unit variance.

  2. We create a constraint matrix AA. Each correspondence gives one constraint. For 8-point algorithm we use 8 correspondences. Each row of constraint matrix is made by:
    [ui′ui ui′vi ui′wi vi′ui vi′vi vi′wi wi′ui wi′vi wi′wi] [u_{i}^{'}u_{i} \space u_{i}^{'}v_{i} \space u_{i}^{'}w_{i} \space v_{i}^{'}u_{i} \space v_{i}^{'}v_{i} \space v_{i}^{'}w_{i} \space w_{i}^{'}u_{i} \space w_{i}^{'}v_{i} \space w_{i}^{'}w_{i}]

  3. SVD(A)SVD(A) and find the vector in the null-space of AA.

  4. Project F to a rank 2 matrix.
    Udiag(d1,d2,d3)VT−>Udiag(d1,d2,0)VT U diag(d_{1}, d_{2}, d_{3}) V^{T} -> U diag(d_{1}, d_{2}, 0) V^{T}

  5. Transform solution to pixel space by denormalising the F matrix.

(A2) E matrix using 8-point algorithm

Bench

Estimated E

[−0.41524274−8.81748899−2.15055809−1.380355910.7906713469.08265072−3.58890878−68.474387381.0000000] \begin{bmatrix} -0.41524274 & -8.81748899 & -2.15055809\\ -1.38035591 & 0.79067134 & 69.08265072 \\ -3.58890878 & -68.47438738 & 1.0000000 \end{bmatrix}

Remote

Estimated E

[2.52980643−0.670561787.33094845−6.62032757−3.02768469−28.29861695−14.5007110926.418248081.0000000] \begin{bmatrix} 2.52980643 & -0.67056178 & 7.33094845\\ -6.62032757 & -3.02768469 & -28.29861695 \\ -14.50071109 & 26.41824808 & 1.0000000 \end{bmatrix}

Implementation

E is calculated from F using the formula EE = K′TFKK^{'T}FK
E is projected to a rank 2 matrix using
Udiag(d1,d2,d3)VT−>Udiag(dˉ,dˉ,0)VT U diag(d_{1}, d_{2}, d_{3}) V^{T} -> U diag(\bar{d}, \bar{d}, 0) V^{T}
where,
dˉ=d12+d22 \bar{d} = \frac{d_{1}}{2} + \frac{d_{2}}{2}

7-point algorithm

Hydrant

ViewPoint 1 ViewPoint 2
enter image description here enter image description here

Ball

ViewPoint 1 ViewPoint 2
enter image description here enter image description here

Implementation

  1. We first normalize the pixel values by mean centering them and enforcing unit variance.

  2. We create a constraint matrix AA. Each correspondence gives one constraint. For 7-point algorithm we use 7 correspondences. Each row of constraint matrix is made by:
    [ui′ui ui′vi ui′wi vi′ui vi′vi vi′wi wi′ui wi′vi wi′wi] [u_{i}^{'}u_{i} \space u_{i}^{'}v_{i} \space u_{i}^{'}w_{i} \space v_{i}^{'}u_{i} \space v_{i}^{'}v_{i} \space v_{i}^{'}w_{i} \space w_{i}^{'}u_{i} \space w_{i}^{'}v_{i} \space w_{i}^{'}w_{i}]

  3. SVD(A)SVD(A) and find 2 vector corresponding to the last 2 eigenvalues of AA. General solution for F is λF1+(1−λ)F2\lambda F_{1} + (1 - \lambda) F_{2}

  4. We enforce another constraint i.e. find λ.\lambda . such that det(λF1+(1−λ)F2)=0det(\lambda F_{1} + (1 - \lambda) F_{2}) = 0. This gives us a 3-degree polynomial

  5. Get all real roots. If multiple real roots find the one with the max number of inliers.

Q2 RANSAC with 7-point and 8-point algorithm

Hydrant

ViewPoint 1 ViewPoint 2
enter image description here enter image description here

F=[9.57509703e−08−4.80940974e−06−1.18501445e−036.38696126e−06−1.22691718e−07−1.74469073e−028.55325918e−041.73533043e−021.00000000e+00] F = \begin{bmatrix} 9.57509703e-08 & -4.80940974e-06 & -1.18501445e-03\\ 6.38696126e-06 & -1.22691718e-07 & -1.74469073e-02 \\ 8.55325918e-04 & 1.73533043e-02 & 1.00000000e+00\\ \end{bmatrix}

Ball

ViewPoint 1 ViewPoint 2
enter image description here enter image description here

F=[−1.02433530e−07−3.51118459e−06−6.86901075e−034.08160969e−06−1.03239356e−06−1.57172423e−029.37315493e−031.56927078e−021.00000000e+00] F = \begin{bmatrix} -1.02433530e-07 & -3.51118459e-06 & -6.86901075e-03\\ 4.08160969e-06 & -1.03239356e-06 & -1.57172423e-02 \\ 9.37315493e-03 & 1.56927078e-02 & 1.00000000e+00 \\ \end{bmatrix}

Bench

ViewPoint 1 ViewPoint 2
enter image description here enter image description here

F=[−5.47469431e−09−9.89016743e−07−3.18743395e−04−1.36876512e−066.51133769e−072.17319709e−02−6.00789296e−04−2.05866302e−021.00000000e+00] F = \begin{bmatrix} -5.47469431e-09 & -9.89016743e-07 & -3.18743395e-04 \\ -1.36876512e-06 & 6.51133769e-07 & 2.17319709e-02 \\ -6.00789296e-04 & -2.05866302e-02 & 1.00000000e+00 \\ \end{bmatrix}

Remote

ViewPoint 1 ViewPoint 2
enter image description here enter image description here

F=[1.28882469e−06−2.31300006e−062.83735459e−03−8.25185050e−07−1.16043957e−07−9.21371716e−03−4.32332866e−031.00296159e−021.00000000e+00] F = \begin{bmatrix} 1.28882469e-06 & -2.31300006e-06 & 2.83735459e-03\\ -8.25185050e-07 & -1.16043957e-07 & -9.21371716e-03\\ -4.32332866e-03 & 1.00296159e-02 & 1.00000000e+00 \\ \end{bmatrix}

Implementation

Given corresponding points from two images. The RANSAC implementation is a s follows:

  1. Randomly select 7 / 8 points based on the algorithm to run.
  2. Estimate F based on the selected points.
  3. Calculate error by finding the distance of all points in pts2 to the epipolar line calculated by epipolar_line = pts1 @ F.T
  4. Select points which are at a distance less than the set threshold. These points are considered inliers. In the code I have set the threshold to be 1 and max_iterations to be 10000.
  5. Save the Fundamental matrix which gives the maximum inliers.

Q3 Triangulation

Point cloud reconstruction

enter image description here

Implementation

We use the Linear Triangulation method which is the direct analogue of DLT method.

  1. Each image has a measurement x=PXx = PX and x′=P′Xx^{'} = P^{'}X
  2. These equatiions are combined to form AX=0AX=0 which is a linear in xx.
  3. For each image and for each point we can write xx x (PX)=0(PX) = 0
  4. We get 2 equations from each image. Therefore from a correspondence we get 4 constraints. of the form

A=[xp3⊤−p1⊤yp3⊤−p2⊤x′p3⊤−p′1⊤y′p3⊤−p′2⊤] \begin{equation} A = \begin{bmatrix} x \mathbf{p}^{3^\top} - \mathbf{p}^{1^\top} \\ y \mathbf{p}^{3^\top} - \mathbf{p}^{2^\top} \\ x' \mathbf{p}^{3^\top} - \mathbf{p}'^{1^\top} \\ y' \mathbf{p}^{3^\top} - \mathbf{p}'^{2^\top} \end{bmatrix} \end{equation}

Q4 Reconstruct your own scene

Multi view images - Banana

ViewPoint 1 ViewPoint 2 Viewpoint 3
enter image description here enter image description here enter image description here
ViewPoint 4 ViewPoint 5 Viewpoint 6
enter image description here enter image description here enter image description here

3D Reconstruction - Banana

enter image description here

Multi view images - Angry Octopus and Pengu

ViewPoint 1 ViewPoint 2 Viewpoint 3
enter image description here enter image description here enter image description here
ViewPoint 4 ViewPoint 5 Viewpoint 6
enter image description here enter image description here enter image description here

3D Reconstruction - Angry Octopus and Pengu

enter image description here