> For the complete documentation index, see [llms.txt](https://sejkai.gitbook.io/academic/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sejkai.gitbook.io/academic/ncku-robotic-navigation-and-exploration/multi_view_geometry.md). # Computer Vision / Multi-view Geometry ## Structure from Motion (SfM) 圖學的 SfM 和 SLAM 十分相似，只是 SLAM 是 realtime 版本的 SfM SfM 透過多個圖像來復原 camera motion 和 scene structure ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2F3ae93048d01810ae079089ac4d1c6060958111b1.png?generation=1589085288016038\&alt=media) 而 SfM 流程可以大致列為 ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2F991df3ded729fcef3b7d52b4fe76f385f631dfea.png?generation=1589085286897416\&alt=media) 1. 找 feature points (SIFT: NN 以外最好) 2. 預測 points 對應到真實 3D 場景會變怎樣 (geometry) 3. 優化預測 (bundle adjustment) 4. 找出 rotation 或 translation 是否合理 ### SIFT 以下介紹 SIFT 如何萃取 feature points ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2F657971af3d049fdb92df2616c6be81fddeadf050.png?generation=1589085287505866\&alt=media) SIFT idea 是將圖像的內容轉換成 local feature coordinates，這些座標不受到 translation, rotation, scale 或其他 imaging parameters 的影響而改變 ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2F829bec37a691819b035a78de70dc67ccd3a903d7.png?generation=1589085290239844\&alt=media) SIFT 應用有 * Object recognition (matching) 找兩張圖 matching 地點 * Image Stitching 找多張圖 overlap 的部分並拼接 * Photosynth #### SIFT Process **1. Scale-space extrema detection** 搜索多種比例和圖像位置，找出圖片變化較大的點，做法是使用 Gaussian pyramid **2. Keypoint localization** 利用模型以確定位置和比例，根據穩定性來選擇 keypoints 在產生的 pyramid 找極值 1. 跟鄰居比較 2. 用 taylor 找出更精確的預測 3. check 是否為平坦區域或 edge 並 reject ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2F4a13e58715b9ab3245a45ef53404bd53a752735b.png?generation=1589085287807314\&alt=media) **3. Orientation assignment** 計算每個 keypoints 的最佳方向，以就是為 keypoint 找出描述 (任意方向都是在描述同一點) **4. Keypoint descriptor** 用現有 feature 做出一致性的 feature descriptor，在選定的 scale, rotation 上利用 local image gradients，來描述 keypoints 一種做法是 Lowe's keypoint descriptor ## Camera Calibration 為了更了解 RANSAC 做法要先講到 camera calibration Camera calibration 就是求出 intrinsics 和 extrinsics 所有參數 而 world coordinate (x, y, z) 投影到 camera coordinate (u, v) 可以寫成公式 ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2F486fde374c4e6e324f2f8fe1ca52f5a47e113d46.png?generation=1589085287659582\&alt=media) * A 矩陣為 intrinsics matrix * \[R t] 矩陣為 extrinsics matrix ### Pinhole Camera Projection Model 我們可以利用 image coordinate 和 world coordinate 的對應，來找出沒有做任何 rotation, translation 的 intrinsic, extrinsic matrix 其中的 extrinsic 等於 rotation (3-d identity matrix) + translation ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2Fc808100866226a789bb4020155837f62272790c7.png?generation=1589085288362648\&alt=media) 為了解決 offset ，我們要加入 $$x\_0, y\_0$$ 做為 principle point 和原點的 offset ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2Fa1b27a04d4c8335e38cd8dc3835f5dc1a752007b.png?generation=1589085286183299\&alt=media) 為了解決 distortion，我們要加入 a, s 來進行校正 ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2F2e535c946020d48daf8e0fa9b7d3093daab5fa46.png?generation=1589085285583324\&alt=media) ### Transformation Matrix Estimation by Reprojection 一組 x, y, z 可以和 u 或 v 分別產生兩個對應的方程式，所以假設 extrinsic 有 8 個要解，只需要 4 組對應點 所以原本需要六組 point pair 才能解出 C = A|AT，現在只需要三組就能解出 這種解法稱為 Perspective-n-Point (PnP) ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2Faba0d7c5d8572f3bcdfdadbc57a47ab6d249bb4e.png?generation=1589085291187024\&alt=media) 傳統是利用 AR marker 來解 ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2Fcfa5f944f418d93d48770d6c2ce7c06f9d14e45e.png?generation=1589085290215351\&alt=media) 但現實中沒有 AR marker，也不知道 x, y, z 是如何對應 u, v 的 ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2F0fdffb4f9e591eab7b9fc3ed6a5bbdea8ae3117d.png?generation=1589085286431988\&alt=media) 我們假設有一連串 frame ($$sx\_1, sx\_2, \cdots$$)，寫成 KMP = intrinsic *extrinsic* 3d coordinate ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2F74ab98bc63ff1172d72c527d000c45f8a21e8f13.png?generation=1589085298921254\&alt=media) 可以看到這個做法就像是 bundle adjustment，其中 intrinsics K 是給定的，要求的是 extrinsics M 其中 s (scale) 要猜測，除非用 marker 有固定比例尺 ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2Ffecea450760adc13537ddaefa95927a9c361146a.png?generation=1589085291758791\&alt=media) ### Unknown Structure Initialization ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2F439d3c3af26e57289365f97bb5dd91b2909f44e8.png?generation=1589085298016531\&alt=media) 兩個 camera 中心對到點 P，會產生 ($$C\_0, C\_1, P$$) 這個三角形平面 (epipolar plane) ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2F5b3e3b185e4bc121a1ec327b4ce45fc2a6d86a1d.png?generation=1589085291360529\&alt=media) * $$\vec{C\_0C\_1} (t)$$ 可看成 $$C\_0$$ 到 $$C\_1$$ 的 translation * $$\vec{C\_1p\_1} (Rp\_1)$$ 可看成對 $$p\_1$$ 做 rotation ($$R$$) 我們就可以列出多組已知 $$p0, p1$$ 來求 E 用多組對應來解 E，可以寫成 Ax = 0 來求解 ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2Fa4f64625eea847159f0b9b82aedb0ea60ff52e57.png?generation=1589085288672716\&alt=media) 另外，找對應點時不用全部 SIFT points 都找，可用 epipolar line 找，從 $$p\_0$$ 投影來的 $$p\_1$$ 這幾個點會連成一直線，稱為 epipolar line 透過 epipolar line 可以得到兩個畫面對同一點所產生的投影關係方程 #### Essential Matrix Decomposition 得到 E 就可以用 SVD 來拆解回 t 跟 R ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2F17a5a94555e70aa997b5dd37259e6b1706b53cea.png?generation=1589085290558239\&alt=media) 因為矩陣拆解可能有正負影響得到多種結果，意思是 p 點到底坐落在 A, B 相機的前方還是後方 (所以有四種可能)，所以必須要都在 A, B 前方的那一個解才行 ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2F7c46353e52b87c30732534596ab1dce1aed4ba4a.png?generation=1589085288161087\&alt=media) #### 3D Structure Recovering (Triangulation) 有了 t, R 接著要來猜 p 的 3D structure P ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2F188e1c94183932bf3c13cc029ad9ea09a708ae36.png?generation=1589085288872302\&alt=media) ## Basic Initialization and Tracking 整個 SfM 用於 SLAM 的流程大致上如下 ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2F499e384c6eea91339276b0c4bd6d4ce29e1c56b6.png?generation=1589085289187152\&alt=media) ### Initialization (Feature Matching) 首先從共同看到的點來求得 Essential Matrix (E) ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2F8dd9bfce88521fff02f650c37bfd4e1a36dc0f44.png?generation=1589085286734688\&alt=media) 再來是 extract pose 的步驟，將 E 拆成 R 和 t ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2Fe0b86beb2fb42be9cb334eeba347c5796d00aee7.png?generation=1589085289255863\&alt=media) 接著是從 R 和 t 來復原 P 的 3D structure (紅色點) ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2F290f12d03b17521e673c430c9cbf2e6d80635a33.png?generation=1589085289040166\&alt=media) ### Tracking 新的 frame 進來，用 feature matching 找出 overlap 的部分 ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2Fa02d4e0dc90116ebc469cd54887e657cbd50f284.png?generation=1589085286761704\&alt=media) 用 PnP 和 Recover 還原 P (紅色點) 的 3D structure ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2F298a33bf9c24c21c2266cee30e1e0626f8d160f8.png?generation=1589085292054556\&alt=media) ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2F6aaa7dc43a03b561e0effb6793a62de9df3a1827.png?generation=1589085291370615\&alt=media) 重復上述動作就是 tracking 的部份 ### Scaling Drift Problem 在進行 SfM 時，不只要猜 R, t 還要猜 scale (s)，因為每個 frame 進來會改變 s ，這個問題稱為 scaling drift problem，有一些方法可以校正 scale (這裡不討論) ### Image Matching 因為要討論 SLAM 中最後一個 loop detection 所以要採用 image matching 一種方法是觀察 SIFT point pair 的 similarity，目標是找出 transformation T 可以解釋 similarity ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2Fbd29b0b3c853e430f1f454b5257cd0d46fef04ff.png?generation=1589085289752092\&alt=media) Find a transformation T that explains the movement of the matched features transformation 可以表示成以下形式，有 6 個參數要解 ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2Fcb702a9f7d6a8f0043ab23c35895868f87c4e579.png?generation=1589085286954350\&alt=media) 越多組 pair (三組以上) 可以越精準的猜出 transformation，但挑的點不好就會造成錯誤 ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2F6899fa8bf1e01a5b496fd40c3ba39da7bdac561d.png?generation=1589085298858158\&alt=media) 一種除掉錯誤 outliers 的做法就是 RANSAC #### RANSAC RANdom SAmple Consensus (RANSAC)，在一組數據點中找到一條最適合的線 (省略掉 outliers) ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2F89aed4ee45a821bc62054ac6c3ee29a11725710e.png?generation=1589085287866256\&alt=media) 1. Select two points at random 2. Solve for the line (L) between these two points 3. Count the number of inliers to the line L 4. If L has the highest number of inliers so far, save it 5. Repeat for N rounds, return the best L ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2Fsync%2F4176e8c63a27fac4fe6bf5b6be3fb94a66229d34.png?generation=1589085299597176\&alt=media) 在實作上會把 match 失敗的定為 outliers 來移除掉，然後再重新計算 inliners