pkoch - a3¶
Q1.A1¶
Explanation:¶
To prevent variable scale from influencing the solution, I first normalize both sets of points to roughly unit variance:
$\hat{x}=Tx$, $\hat{x'}=T'x$
Then I construct a constraint matrix $A$ s.t.
$A_i=[x' * x, x' * y, x', y' * x, y' * y, y', x, y, 1]$ for $x_i = [x,y]^T$, $x_i'=[x',y']^T$
This gives me an 8x9 constraint matrix. I find an itial solution via SVD, then enforce rank2-ness via another SVD and reconstruction of $F$ s.t. $F=Udiag(d_0, d_1, 0)V^T$
Finally I un-normalize $F$ via: $F=T'^T \hat{F} T$
Images:¶
2024-10-31 20:37:05,160|MainThread |3534586770.py:run_q1a()|I] loaded bench (8, 2)
for 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]]
2024-10-31 20:37:05,471|MainThread |3534586770.py:run_q1a()|I] loaded remote (8, 2)
for 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]]
Q1.A2¶
Explanation:¶
Given $F$ between two images and the intrinsics $K_1$, $K_2$ of the cameras corresponding to those images, $E=K_2^T F K_1$. To calculate $F$, I used the same procedure as Q1.A2.
E:¶
For bench: $E= \left[\begin{matrix}-0.415242737219187 & -8.81748893504676 & -2.15055808016603\\-1.38035590276841 & 0.790671336591311 & 69.0826503587401\\-3.58890875738069 & -68.4743870056878 & 1.0\end{matrix}\right] $
For remote: $E= \left[\begin{matrix}2.52980639875918 & -0.670561776179074 & 7.33094836644286\\-6.62032748516242 & -3.02768465800714 & -28.2986166467164\\-14.5007109191252 & 26.4182478092727 & 1.0\end{matrix}\right] $
Q1.B¶
Explanation:¶
First I normalized the corresponding points similarly to Q1.A1.
Nex I constructed a constraint matrix $A$ s.t.
$A_i=[x' * x, x' * y, x', y' * x, y' * y, y', x, y, 1]$ for $x_i = [x,y]^T$, $x_i'=[x',y']^T$
This gives me an 7x9 constraint matrix. Two linearly independent solutions are then the last two singular vectors of $A$.
From here we want to find a $\lambda$ such that $det(\lambda F_1 + (1-\lambda)F_2)=0$, which is a cubic polynomial in $\lambda$. On the implementation side, I used sympy to easily determine the coefficients of $\lambda$ and numpy to solve the cubic equation.
I then filtered out the imaginary solutions and constructed 1-3 candidates for $F$ via $F=\lambda F_1 + (1 - \lambda) F_2$
Finally I unnormalized each $F$ candidate and selected the one which most closesly satisfied $x_2^T F x_1 = 0$ for a held out correspondance $x_1$, $x_2$ (of my own annotation).
Found F:¶
for ball $F= \left[\begin{matrix}-3.35078059379162 \cdot 10^{-9} & -2.91545004523187 \cdot 10^{-6} & -0.00674891732687254\\3.51682682943385 \cdot 10^{-6} & -8.84237457497163 \cdot 10^{-7} & -0.0150044163055922\\0.00909398538181961 & 0.014874864908709 & 1.0\end{matrix}\right] $
for hydrant $F= \left[\begin{matrix}1.06836662837854 \cdot 10^{-7} & -3.30854240696489 \cdot 10^{-6} & -0.0013739750860032\\4.79268900746294 \cdot 10^{-6} & 1.63305017766613 \cdot 10^{-7} & -0.0167456793614763\\0.00112974016888409 & 0.0164136612585818 & 1.0\end{matrix}\right]$
Images:¶
2024-10-31 20:37:05,801|MainThread |2622457883.py:run_q1b()|I] loaded ball (7, 2)
found 1 solutions for ball
for ball F=
\left[\begin{matrix}-3.35078059379162 \cdot 10^{-9} & -2.91545004523187 \cdot 10^{-6} & -0.00674891732687254\\3.51682682943385 \cdot 10^{-6} & -8.84237457497163 \cdot 10^{-7} & -0.0150044163055922\\0.00909398538181961 & 0.014874864908709 & 1.0\end{matrix}\right]
2024-10-31 20:37:06,206|MainThread |2622457883.py:run_q1b()|I] loaded hydrant (7, 2)
found 3 solutions for hydrant
errors= [array([[0.00875324]]), array([[0.32820351]]), array([[0.4405238]])]
for hydrant F=
\left[\begin{matrix}1.06836662837854 \cdot 10^{-7} & -3.30854240696489 \cdot 10^{-6} & -0.0013739750860032\\4.79268900746294 \cdot 10^{-6} & 1.63305017766613 \cdot 10^{-7} & -0.0167456793614763\\0.00112974016888409 & 0.0164136612585818 & 1.0\end{matrix}\right]
Q2¶
Explanation:¶
I used a tolerance of $1.0$ and $10000$ iterations. For each iteration, I selected a minimal set of corresponding points, where minimal is $7$ for the seven point algorithm and $8$ for the eightpoint algorithm.
I then calculated $F$ (or a set of $F$s) given those points. Next I determined the error implied by each candidate $F$ on each point pair from the full correspondance set.
The error metric I chose was the sum of the distances of each point in a pair to the epipolar line implied by its corresponding point. I.e., for $N$ point pairs, I calculated $N$ sums of distances. Inliers were then those pairs which had a total distance less than the tolerance (i.e., $1.0$). If there were more inliers for a candidate $F$ than any previous $F$, I would save the set of inliers.
Finally, I calculated the best $F$ using the eightpoint algorithm from the largest set of inliers.
Best F:¶
for bench $F=\left[\begin{matrix}-5.96420404680097 \cdot 10^{-8} & -1.51780265373654 \cdot 10^{-6} & 2.70220598197742 \cdot 10^{-5}\\-1.29050440044822 \cdot 10^{-6} & 5.50379309664694 \cdot 10^{-7} & 0.0243309929858681\\-0.000922862099860083 & -0.0226672582883833 & 1.0\end{matrix}\right]$
for remote $F=\left[\begin{matrix}8.30394679345363 \cdot 10^{-7} & -9.16323656788632 \cdot 10^{-7} & 0.00252485162584614\\-1.05875786063035 \cdot 10^{-6} & -8.39484961631633 \cdot 10^{-7} & -0.00883250496503363\\-0.00438331749419989 & 0.00996171422208053 & 1.0\end{matrix}\right]$
for ball $F=\left[\begin{matrix}-3.08140039763213 \cdot 10^{-8} & -3.1317637584684 \cdot 10^{-6} & -0.00688275634680996\\3.71388743463652 \cdot 10^{-6} & -9.60951732897752 \cdot 10^{-7} & -0.015444290387471\\0.00932124261331626 & 0.0153953255509323 & 1.0\end{matrix}\right]$
for hydrant $F=\left[\begin{matrix}7.8385655237163 \cdot 10^{-8} & -4.77338518992878 \cdot 10^{-6} & -0.00106407849163156\\6.32605327111058 \cdot 10^{-6} & -1.19919184538868 \cdot 10^{-7} & -0.0173634077967683\\0.000756469025146762 & 0.0172778625919603 & 1.0\end{matrix}\right]$
Images:¶
2024-10-31 20:37:06,524|MainThread |1515211418.py:run_q2()|I] Running RANSAC for q1a bench 2024-10-31 20:37:06,535|MainThread |1515211418.py:run_q2()|I] loaded bench (1593, 2)
2024-10-31 20:37:12,538|MainThread |1515211418.py:run_q2()|I] Running RANSAC for q1a remote 2024-10-31 20:37:12,547|MainThread |1515211418.py:run_q2()|I] loaded remote (88, 2) /var/folders/5w/z6tvfvkx08bf8kwyc59jxmfc0000gn/T/ipykernel_64776/1515211418.py:14: RuntimeWarning: divide by zero encountered in divide dist2 = (l2s_3N * pts1_N3.T).sum(axis=0) / np.linalg.norm(l2s_3N[:2, :], axis=0)
2024-10-31 20:37:17,500|MainThread |1515211418.py:run_q2()|I] Running RANSAC for q1b ball 2024-10-31 20:37:17,527|MainThread |1515211418.py:run_q2()|I] loaded ball (1613, 2)
2024-10-31 20:37:23,451|MainThread |1515211418.py:run_q2()|I] Running RANSAC for q1b hydrant 2024-10-31 20:37:23,462|MainThread |1515211418.py:run_q2()|I] loaded hydrant (2170, 2)
Q3¶
Explanation:¶
For a given pair of corresponding points and the project matrices of their cameras, we know
$x \times PX = 0$, $x' \times P'X = 0$
From these equations we can construct a matrix of 4 linear constraints (the 2 additional equations are linearly dependent on the other 4), and solve for $X$ via SVD.
Once I had determined $X$ for each corresponding point pair, I set each point's color to the color of the first image's pixel corresponding to it.
Pointcloud:¶
Cans:
Hydrants:
Q5 Bonus 1¶
Explanation:¶
I used SIFT features / keypoints as suggested. I used cv2's brute force matcher to compare descriptors, and kept those that passed the "ratio test" - those pairs that were at least 25% closer to their partner than any other point.
Then I used RANSAC with the sevenpoint algorithm as in Q2.
Found F:¶
for can $F=\left[\begin{matrix}3.27720950070147 \cdot 10^{-7} & -3.16428826601576 \cdot 10^{-5} & 0.012046651744854\\3.24713585558107 \cdot 10^{-5} & 9.12629154371531 \cdot 10^{-7} & 0.0161622330364023\\-0.0117588646907497 & -0.0185831929970149 & 1.0\end{matrix}\right]$
for hydrant $F=\left[\begin{matrix}4.29928545916206 \cdot 10^{-7} & 1.37966370474616 \cdot 10^{-5} & 0.000726577753596815\\-8.42726335733511 \cdot 10^{-6} & -1.70059103198339 \cdot 10^{-6} & 0.0855767440715541\\-0.00321061943426913 & -0.0857304204042395 & 1.0\end{matrix}\right]$
Images:¶
2024-10-31 20:37:30,889|MainThread |3530935062.py:run_q5()|I] Running can 2024-10-31 20:37:31,301|MainThread |3530935062.py:run_q5()|I] 11369 keypoints in 1, 12521 keypoints in 2 2024-10-31 20:37:31,540|MainThread |3530935062.py:run_q5()|I] 11369 matches 2024-10-31 20:37:31,541|MainThread |3530935062.py:run_q5()|I] 4644 matches after ratio test 2024-10-31 20:37:31,545|MainThread |3530935062.py:run_q5()|I] RANSAC...
2024-10-31 20:37:37,164|MainThread |3530935062.py:run_q5()|I] Running hydrant 2024-10-31 20:37:37,466|MainThread |3530935062.py:run_q5()|I] 5903 keypoints in 1, 5832 keypoints in 2 2024-10-31 20:37:37,523|MainThread |3530935062.py:run_q5()|I] 5903 matches 2024-10-31 20:37:37,524|MainThread |3530935062.py:run_q5()|I] 2152 matches after ratio test 2024-10-31 20:37:37,526|MainThread |3530935062.py:run_q5()|I] RANSAC...
Q6 Bonus 2¶
Explanation:¶
I experimented with reducing the number of images. For the cans sequence, I chose 7 evenly spaced images out of the original 70. Visually, they still have significant overlap. I wanted to see how this would affect COLMAP.
The result was that COLMAP rejected all but three of the input images:
I believe this is because the large baselines between images reduced the visual similarity of potential keypoints; this meant that many image pairings were rejected due to low keypoint matches, and thus incremental SfM could not be performed on them.