# VFX Project2
## Members
#### R10922017 許博翔
#### R10944007 曾宏鈞

## Implemetation
0. Taking Photo
1. Image Warping
2. Feature Detection –– Harris
3. Feature Description –– SIFT
4. Feature Matching
5. Image Stiching

### 0. 使用腳架定點旋轉拍照

### 1. Image Warping
將原始圖像的座標x, y，投影到圓柱上，得到圓柱座標theta, h，產生warp的影像。
實作上從圓柱對應到原始影像取值，投影後的影像高度與原始影像相同，寬度則是弧長（focal_len * theta）。

### 2. Feature Detection
1. 利用 Harris Corner Detection Algorithm 找到 corner response R 及 orientation。
- R: 求 $R=detM-k(trace M)^{2}$
1. 輸入灰階圖片 $I_{gray}$
2. 透過Scharr kernel求出x及y方向的derivative dx、dy
3. 計算$I_{xx}$、$I_{yy}$、$I_{xy}$ ($I_{xy}=dx*dy$)
4. 透過GaussianBlur求出$S_{xx}$
5. 帶入下面式子求出 $detM$、$traceM$
$$M=
\begin{pmatrix}
S_{xx} & S_{xy} \\
S_{yx} & S_{yy}
\end{pmatrix}
$$
- orientation: 透過前面計算過的dx, dy計算$arctan2(dx,dy)$

2. 將對比度較低的點移除
- 首先使用Laplacian Filter，讓比四周還大的值更大；和四周差不多的變小
- 設定threshold挑選部分點作為特徵點。


### 3. Feature Description
實作 SIFT Algorithm 將每個 keypoint 周圍 16 x 16 的 pixel 分成 4 x 4 的 grids，然後每個 grid 中 的 16 個 pixel 根據 gradient 的大小作為權重，統計成每 45 度角為一組的 histogram，最後得到 128 維的 descriptors

### 4. Feature Matching
- 取相鄰兩相片 $I_{i}$ 、 $I_{i+1}$ ，利用 KDTree 找出 $I_{i+1}$ 上每個特徵點在 $I_{i}$ 上 discriptor 最接近的兩個特徵點。
- 若 $I_{i+1}$ 上一個特徵點和 $I_{i}$ 上找到的兩個最接近的特徵點 discriptor 距離差不多（相除 < 0.8），則移除該 match 。反之，與距離小者作為一個 match。

### 5. Image Stiching
- 首先使用 `estimateAffinePartial2D()` 計算兩張圖片拼接最適當的距離，其中該函式會使用 RANSAC 演算法消除 outlier ，避免誤差。
- 接著計算頭尾兩張圖垂直方向的 shift ，透過調整所有圖片 shift 的方式，讓拼接結果較不會歪掉。
- 最後算出輸出大小，把圖片一張一張貼上去，利用 $1-(\frac{d}{D})^2$ 的方式，將重疊部分做 blending。

## Results
### Testing Data
### Ours (focal length 1200)
## Discussion
### 過濾太多餘的特徵點
一開始實作完 Harris Corner Detection 之後，我們發現取得的特徵點數量非常多，而且有很多幾乎黏在一起，但這會讓計算時間變更多，因此我們找到了 Laplacian 這個 filter ，它會每個 pixel 和四周的差加起來，如果算出來是正的，代表這個 pixel 可能比四周都還大，這樣就能做出 local maximun 的效果，來過濾一些不必要的特徵點。

### 避免 accumlated error
就像老師上課提到的，隨著圖片一張一張拼接，有可能會因為垂直方向上的誤差，讓拼出來的結果斜斜地往上或往下拼，為了避免這種狀況，我們計算了頭尾兩張圖的垂直偏差，把它分散到所有圖片，這樣一來就能拼出較方正的結果了。

### 拍攝照片亮度不一
我們在拍攝照片之後，才發現相機選到了自動模式，因此每張照片的f值和曝光時間都不太一樣。後來我們利用 $\mathrm{EV}=\log _{2} \frac{f值^{2}}{曝光時間}$ 的公式，把每張照片的曝光都調成一樣之後，再進行拼接。

## 參考資料
1. https://github.com/tsai-you-shin/Image-stitching
2. https://docs.opencv.org/4.x/d1/de0/tutorial_py_feature_homography.html