---
# System prepended metadata

title: 3DCV HW1 PEPORT

---


# **3DCV HW1 REPORT**
HackMD連結（在 Github 上無法看到圖片）：https://hackmd.io/EhIblDxuR2i_LEia-KnWKQ?both 
## **Before Starting**

* ### **環境設置** 
    * Python == 3.8
    * OpenCV == 4.5.1.48
    * Numpy == 1.24.3 
* ### **操作指令** 
    * Problem 1 Image Pair #1 (1-0.png -> 1-1.png)
        ```
        Python3 1.py images/1-0.png images/1-1.png groundtruth_correspondences/correspondence_01.npy 0`
        ```
    * Problem 1 Image Pair #2 (1-0.png -> 1-2.png)
        ```
        Python3 1.py images/1-0.png images/1-2.png groundtruth_correspondences/correspondence_02.npy 1
        ```
    * Problem 2 
       ```
       Python3 2.py images/IMG_NTHU.png 
       ```
* ### **作業 Youtube 影片連結** 
    * Link : https://www.youtube.com/watch?v=7hiyVgdsN_c
        
        {%youtube 7hiyVgdsN_c %}
---

## **Problem 1: Homography Estimation**
> 第一題使用 RAMSAC 演算法取點，每次執行都會取到不同點，以下以其中一次作為範例。
* ### **Image Pair #1** 
    * **Screenshots**
        * 4 Correspondance
            
            ![](https://hackmd.io/_uploads/SJBxEGDx6.jpg)

        * 8 Correspondance
            
            ![](https://hackmd.io/_uploads/rJxTx4fvga.jpg)

        * 20 Correspondance
        
            ![](https://hackmd.io/_uploads/HyXWVfPga.jpg)
    
    * **Compare Errors**
        * 4 Correspondance

            ```
            DLT:     error = 0.7610830509931134
            NDLT:    error = 0.7610830511474711
            ```
        * 8 Correspondance
        
            ```
            DLT:     error = 0.26402157736819765
            NDLT:    error = 0.23270667482416615
            ```
        * 20 Correspondance
        
            ```
            DLT:     error = 0.19504600882141884
            NDLT:    error = 0.18428342788278684
            ```
* ### **Image Pair #2** 
    * **Screenshots**
        * 4 Correspondance
        
            ![](https://hackmd.io/_uploads/Hy5JGfvlT.jpg)

        * 8 Correspondance
        
            ![](https://hackmd.io/_uploads/rkSeMMvgp.jpg)

        * 20 Correspondance
            
            ![](https://hackmd.io/_uploads/H1aeGfwe6.jpg)

    * **Compare Errors**
        * 4 Correspondance
            ```
            DLT:     error = 8.494533132439095
            NDLT:    error = 8.49453313173649
            ```
        * 8 Correspondance
            ```
            DLT:     error = 2.4494230441818594
            NDLT:    error = 2.1268804020479446
            ```
        * 20 Correspondance
         
            ```
            DLT:     error = 1.5774181313493174
            NDLT:    error = 1.4916830711829854
            ```
* ### **My Method**
    * **RAMSAC 演算法**
    
         使用 RAMSAC 演算法以達到自動提取 inliers，可大幅節省手動挑選對應點的時間。
        * **參數設定**
        
            1. 最小參考點數 ＝ **k**
                 > 在每個回合中隨機取最少 **k** 個點來計算 Homography
            2. 誤差閥值 ＝ **t**
                > 計算 inliers 時，使用 Homography 轉換後的點與原本 SIFT 得出的原對應點，來計算歐幾里德範數，若誤差值 < **t** 則視為 inlier，反之視為 oulier
            3. 比例閥值 ＝ **r**
                > 若使用隨機點得出的 Homography 對所有點集做運算，得到的 inliers 數量佔所有點的 **r％** 則跳出 RAMSAC 迴圈
            4. 迴圈數 ＝ **i**
                > 若 RAMSAC 迴圈執行超過 **i** 次，則跳出迴圈
        * **演算法步驟**
            1.  在 i 個迴圈內，執行以下步驟：
            3.  隨機選擇 SIFT 所得出的 k 個對應點，來計算 Homography
            4.  將所有點以上述得到的 Homography 做計算，以得到對應點，並將此對應點與原本使用 SIFT 方式得出的原對應點做歐幾里德範數計算，若誤差小於t ，則視為 inlier
            5.  若此迴圈計算出的 inliers 數量為過去所有迴圈當中最多的一次，則紀錄此次的 inliers 集為「最佳 inliers 解」
            6.  檢查迴圈數是否超過 i，或是「最佳 inliers 解」的 inliers 總數目佔所有點集中的 r% 以上，則跳出迴圈，否則重複上述迴圈
            7.  最後使用「最佳 inliers 解」的所有 inliers，來計算新的 Homography，並回傳用此 Homography 所計算出的所有 inliers 
        
     * **對應點組挑選演算法**
    
        雖然使用 RAMSAC 演算法可以自動獲得所有可能的 inliers，但如果我們使用的 inliers 對應點在圖中太過於接近其他點，則所計算出的 Homography 依然可能會產生巨大的誤差，因此我使用在 implement RAMSAC 演算法時所獲得的靈感，來做出可以挑選合適對應點組的演算法。
        * **參數設定**
        
            1. 對應點數 ＝ **k**
                 > 在每個回合中取 **k** 個點來計算 Homography
            2. 迴圈數 ＝ **i**
                > 若迴圈執行超過 **i** 次，則跳出迴圈
        * **演算法步驟**
            1.  在 i 個迴圈內，執行以下步驟：
            2.  隨機在 RAMSAC 演算法中獲得 inliers 中選取 k 個點
            3.  計算此 k 個點彼此之間的曼哈頓範數的總和，若總和為歷次迴圈中的最大值（代表此 k 個點相距最遠），紀錄此 k 個點
            4.  檢查迴圈次數是否超過 i 個迴圈，是則離開迴圈，否則重複上述步驟
            5.  回傳最後紀錄的 k 個點
        * **比較結果**
            1.  在不使用此演算法前，可能會遇到的情形：![](https://hackmd.io/_uploads/r1G0TpDlT.jpg)

                
                這些對應點皆有良好的對應關係，但因距離太過接近，或太接近於同一條直線，使計算出來的 Homography 誤差巨大：
                ```
                DLT:     error = 1742.5663511263274
                NDLT:    error = 1742.5663508258729
                ```

            2.  使用此演算法過後，所計算出的誤差大部分都小於 10 (如上方 Image Pair #1 與 #2)。
            
* ### **Discussion**
    * **DLT 與 NDLT 比較**
    
        如果我們使用 NDLT 來計算 Homography，在多數情況下，若有選取夠好得對應點組，計算出來的誤差值通常會比使用 DLT 來得好一些，但有時也會有比較差的情況，如上述的 Image Pair #1 的 4 Correspondance 所計算出來的誤差為：
        ```
        DLT:     error = 0.7610830509931134
        NDLT:    error = 0.7610830511474711
        ```
    * **SIFT 演算法的弱點**
    
        當我在對 Image Pair #2 進行實驗的當下，我發現了某個 4 Correspondence 對應點組，計算出來的 DLT 與 NDLT 出現了奇怪的情況：
        ```
        DLT:     error = 88.55769680126714
        NDLT:    error = 1528.6367983364046
        ```
        於是我將此對應點組的對應點印出來，我得到了以下的圖片：
        
        ![](https://hackmd.io/_uploads/SyRGQRDlT.jpg)
        
        我發現在給定 4 組對應點的情況下，圖片中卻只出現三組對應點。後來才發現是因為 SIFT 所計算出來的不同對應點組，可能會有完全重疊的情形，因此隨機找點可能會找到重疊的對應點，從而導致誤差變大。
        
------------
        
## **Problem 2: Document Rectification**
> 第一題使用 RAMSAC 演算法取點，每次執行都會取到不同點，以下以其中一次作為範例。
* ### **Input Image** 
    ![](https://hackmd.io/_uploads/ryZQn0Pe6.jpg)

* ### **Output Image**
    ![](https://hackmd.io/_uploads/SkYSh0PlT.jpg)

* ### **My Method**
    1. 使用 mouse_click_example.py 點出四個角落，並記錄四個角落的 Pixels 的座標位置 。
    2. 建立一張空白但尺寸相同的圖片檔案（以下簡稱此圖片為圖Ａ），並將上述記錄的四個角落，與此圖片的四個角落一一對應，計算出圖Ａ到原始圖片的 Homography（可省去 Inverse 的步驟）。
    3. 計算出 Homography 後，計算圖Ａ的所有 Pixels 會對應到原圖的哪個座標，在使用 Bilinear Interpolation 將此座標附近的四個 Pixels' Value 做運算，最後即可得到相對應的新值。

* ### **Discussion**   
    * **使用 Bilinear Interpolation 與不使用之結果比較**  
        
        * Screenshots Before/After：
    
            
            ![](https://hackmd.io/_uploads/Bk-vBbOea.jpg)
       
            ![](https://hackmd.io/_uploads/HyWvr-Og6.jpg)
        
            可以從上圖中看到，使用 Bilinear Interpolation 後，Warping 的顆粒感消失了，邊緣也得更加自然。

        