Assignment 3

Andrew ID: roshanr

Late Days: 2

Q1. 8 point and 7 point Algorithms

(A1) F matrix using 8-point algorithm

Bench

[[-1.19197327e-07 -2.53110054e-06  2.07464874e-04]
 [-3.96237477e-07  2.26965824e-07  2.48724802e-02]
 [-1.06829351e-03 -2.29919977e-02  9.99425607e-01]]

Remote

[[-7.18941087e-07  1.90565734e-07 -2.36193611e-03]
 [ 1.88141885e-06  8.60432205e-07  8.45608352e-03]
 [ 3.98021997e-03 -9.46413878e-03 -9.99908748e-01]]

Implementation Steps

• Normalization of Annotations
  • Center the points by translating them so that their mean is at the origin.
  • Scale the points so their average distance from the origin is approximately $\sqrt{2}$
  • Construct the transformation matrix $T$ for each image that includes both translation and scaling.
  • Apply $T$ to each set of points to obtain normalized coordinates, $x1^′$ and $x2^′$.

• Setup and Solve Linear system of Equations
  • For each point correspondence, construct a row of the $A$ matrix.
  • $Row_i​=[x^′x,x^′y,x^′,y^′x,y^′y,y^′,x,y,1]$
  • Construct the $A$ matrix by stacking the row of points.

• Compute the $F$ matrix as the right singular vector of the $V$ matrix

• Enforce rank 2 constraint on $F$
  • Perform SVD on $F$: $F = U\Sigma V^T$
  • Set the smallest singular value to 0 and multiply to get $F$

• Un-normalize the $F$ matrix
  • $F_{final} = T_2^T F T_1$

(A2) E matrix using 8-point algorithm

Bench

[[-0.60133678 -0.36677794 -0.04236738]
 [-0.18918018  0.20048949  0.38542375]
 [-0.15246417  0.25850307  0.43297485]]

Remote

[[-0.67687562  0.17417721 -0.10308397]
 [ 0.05872327  0.17898718  0.10989449]
 [ 0.09012205  0.58104542  0.32799084]]

Implementation Steps

• Normalization of Points
  • $x' = K^{-1} x$

• Setup and Solve Linear system of Equations
  • Same as previous question.

• Compute $E$ as the right singular vector of $V$ matrix in SVD decomposition.

• Enforce rank 2 constraint on $E$
  • Perform SVD on $E$: $E = U\Sigma V^T$
  • Set the smallest singular value to 0, first two singular values equal, and multiply to get $E$

(B) F matrix using 7-point algorithm

Ball

[[-5.55434154e-05 -4.08536711e-04  2.93116678e-01]
 [ 3.19669171e-04 -6.60633894e-05 -3.53700009e-02]
 [-2.80575748e-01  1.02093143e-01  9.07571231e-01]]

Hydrant

[[ 1.89190883e-05  2.58858331e-04 -7.97953131e-02]
 [-2.25614947e-04  2.59890984e-05  2.50075252e-01]
 [ 5.72694169e-02 -2.92356316e-01  9.17792436e-01]]

Implementation Steps

• For seven pairs of point correspondences $(x, x')$, each correpondence must satisfy $x'^T F x = 0$

• Normalization of Annotations
  • Same as previous question.

• Setup and Solve Linear system of Equations
  • Same as previous question.
  • This time, we only have 7 point correspondences instead of 8.

• Solve for the Null Space of A
  • $Rank(A) = 7$ and $dim(RNS(A)) = 2$
  • $F = \alpha F_1 + (1-\alpha) F_2$ , where $F_1, F_2$ are the right singular vectors of V reshaped
  • Enforce determint constraint $det(F) = 0$
  • Solve the cubic equation to solve for $\alpha$.
  • Grab the real roots of the equation, and manually choose the first one. Then, plug into $F$ equation.

• Enforce rank 2 constraint on $F$
  • Same as previous question.

• Un-normalize the $F$ matrix
  • Same as previous question.

Q2. RANSAC with 7-point and 8-point algorithm

Bench

8-point:

[[ 9.49630170e-07  6.11096405e-06 -1.95948648e-03]
 [-4.29880099e-06  4.61500914e-06  1.99126813e-03]
 [ 1.93271282e-04 -5.31979334e-03  9.99981929e-01]]

7-point:

[[-2.63628141e-05 -4.88282934e-04  8.39715497e-02]
 [ 4.49963502e-04 -2.68016218e-04 -2.14139752e-01]
 [-8.33954721e-02  3.23268716e-01  9.14130715e-01]]

Remote

8-point:

[[-4.02406582e-07  2.29231785e-06 -9.33679868e-04]
 [-2.49682311e-06  4.53746667e-06 -1.25411792e-03]
 [ 1.48199778e-03 -3.23865226e-03  9.99992435e-01]]

7-point:

[[-4.06568039e-05  3.03679329e-04 -1.27881725e-01]
 [-1.66315934e-04 -6.05167544e-05  8.19275644e-02]
 [ 1.06477281e-01 -7.20818095e-02 -9.80000416e-01]]

Ball

8-point:

[[-1.41194277e-07 -5.71462671e-07  5.33183683e-04]
 [ 1.92805384e-06  1.13195106e-07 -1.17639774e-03]
 [-1.99590783e-03  1.57207309e-04  9.99997162e-01]]

7-point:

[[ 1.54235907e-05 -3.37675808e-04  2.63031970e-01]
 [ 1.99921898e-04  4.19920592e-05 -1.15362779e-01]
 [-2.29744516e-01  1.16789585e-01  9.22541655e-01]]

Hydrant

8-point:

[[ 1.43499442e-06  2.40359924e-06 -2.00336729e-03]
 [ 1.25818028e-07  1.40739291e-06 -9.39993204e-04]
 [-2.31511071e-04 -1.44735544e-03  9.99996477e-01]]

7-point:

[[-1.64223012e-06 -7.96862426e-06  9.02035449e-03]
 [ 7.09386208e-06 -8.35985816e-07  1.12599273e-03]
 [-8.07753656e-03  7.03725744e-04 -9.99925809e-01]]

Implementation Steps

• For each algorithm (x=7/8 points)

• Set a maximum number of iterations to perform RANSAC over, and set a $\epsilon$ (error threshold) for $F$ matrix constraint error.

• For each iteration
  • Choose a random subset of x point correspondences
  • Calculate the $F$ matrix using the chosen algorithm
  • Calculate the number of inliers (amongst all matches) for this $F$ matrix
    • We know that $x'^T F x = 0$ for a perfect $F$
    • Inlier criteria: $x'^T F x < \epsilon$
  • If current inlier count is higher than best inlier count, update F matrix.

Q3. Triangulation

Implementation Steps

• Given correspondences $(x, x')$, we know that $x = Px'$ or in projective geometry terms $[x]_{x} Px' = 0$

• Stack equations into an A matrix with the correspondences. Solve using SVD, and $x$ is the right singular vector of A

• 3D point can be calculated in the same manner. Color of the 3D point is extracted from the input image

Q4. Reconstruct your own scene

Scene 1: Seating 1

Images Link

Scene 2: Seating 2

Images Link

Q5. Fundamental matrix estimation on your own images

Scenario 1

Scenario 2

Implementation

• Use CV2 to extract SIFT feature descriptors

• Use a matching algorithm to match these descriptors (top-k, used 2 here)

• Use RANSAC with 8/7 point algorithm to find the $F$ matrix from noise matches with inlier pct $~0.5$