# **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


* 8 Correspondance


* 20 Correspondance


* **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


* 8 Correspondance


* 20 Correspondance


* **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. 在不使用此演算法前，可能會遇到的情形：

這些對應點皆有良好的對應關係，但因距離太過接近，或太接近於同一條直線，使計算出來的 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

於是我將此對應點組的對應點印出來，我得到了以下的圖片：


我發現在給定 4 組對應點的情況下，圖片中卻只出現三組對應點。後來才發現是因為 SIFT 所計算出來的不同對應點組，可能會有完全重疊的情形，因此隨機找點可能會找到重疊的對應點，從而導致誤差變大。

------------

## **Problem 2: Document Rectification**
> 第一題使用 RAMSAC 演算法取點，每次執行都會取到不同點，以下以其中一次作為範例。
* ### **Input Image**

* ### **Output Image**

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

* ### **Discussion**
* **使用 Bilinear Interpolation 與不使用之結果比較**

* Screenshots Before/After：



可以從上圖中看到，使用 Bilinear Interpolation 後，Warping 的顆粒感消失了，邊緣也得更加自然。