# Fundamental Computer Vision
[TOC]
## 1. Camera Models
### 1.1 Pinhole cameras
- $f$ 代表 focal length
- $o$ 可以稱作 pinhole = aperture = center of the camera
---
- 使用座標系來表示此系統
---
- 使用相似三角形可以以舊座標表示投影後的座標
---
- image plane 上所呈現的 Digital Image
---
- 在 image plane 上的座標，改以中心點 $C_x, C_y$ 來表示其他位置
---
- 原本的位置，都是以距離作為單位
- 如果我們用 pixel 來表示，就需要多乘上 $k, l$ 來轉換基礎單位
- 而我們把
- $f * k$ 寫作 $\alpha$
- $f * l$ 寫作 $\beta$
---
- 我們可以得出 $eq.5$ 表示方式
:::danger
:warning: 但 projective 是線性轉換嗎？
- 不是，因為 $z$ 的位置在 $P\prime$ 分母
- 我們不可能利用線性轉換，將 $P$ 內的 $z$ 轉換到 $P\prime$ 的分母
:::
:::info
:bulb: 那 Projective 還可以用 matrix 的形式來表達嗎？
- 可以
- 不使用 Euclidean coordinates 而是使用 **Homogeneous coordinates**
:::
---
- 在 Euclidean system 多加一個維度的 scalar，值為 1
- 即為 Homogeneous system
- 如果要轉換回 Euclidean，則統一除以此 scalar
---
- 而 projective transformation 就可以用此 matrix 來表示
---
- $3*3$ 的部分，就稱作 Camera matrix $K$
---

---

---
### 1.2 The geometry of pinhole cameras
- 剛剛的討論，都只有相機內部的系統(camera reference system)
- 但我們也要討論外部世界的系統(world reference system)
- 也就是圖上的 $R, T$
- 先以 $2D$ 世界作為範例
---
- 以 Homogeneous coordinates 表示 $2D$ 的 shift
---
- $2D$ 的 scale
---
- $2D$ 的 rotate
---
- $2D$ 的 shift + rotate + scale
---
:::success
轉換到 3D 亦然
:::
- $3D$ 移動
- $3D$ 旋轉
- $3D$ 平移＋旋轉
- 現實情況，Rigid 不會有 scale
- 6 degree of freedom
---
- 將 camera reference system (Internal parameter) 與 world reference system (External parameter) 兩者整合
---
- 共有 11 個 degrees of freedom
---
- 轉回尤拉座標系
---
- 當目標很遠時，會出現 Horizon line (vanishing line)
- 因此研究多點成相的時候（前面只有研究單點），可以是坐在同一個面上面
---
- Projective 可以簡化為 Weak perspective
---
- Weak perspective 數學上表 $m_3$ 項為 $1$

## 2. Camera Calibration
### 2.1 Camera calibration problem
- Internal parameters 與 External parameters 乘開後可以得到 $M$
---
- 我們從照片的資料點，來回推 $M$ 這個 matrix，就是 Calibration problem
---
- 上一章得知，$M$ 有 11 個參數，因此需要 11 個 equation 才能解出
- 而每一的點可以提估 2 個 equation (x and y)
- 因此需要 6 個點
- 但在實務上，我們會使用超過 6 個對應點，加強 Robustness
---
- 投影點 $p_i = [u_i, v_i]$ 與被投影點 $P_i$ 的關係
---
- 移項
---
- 取 $n$ 個點來解聯立
---
### 2.2 Camera calibration with radial distortion
---

---
- Distortion 就會用一個 $\lambda$ 來表達
---
- 如果 $\lambda$ 只跟 camera 有關就會非常容易
- 但實際上還會跟 **2D point** 本身的位置 $(u, v)$ 有關，也就是參數 $d$
- 此外也有一個參數 $\kappa_p$ 有關
---
- 直覺方式
- 求 $\lambda$ 的方式跟前面沒有 distortion 一樣，只是這裡將 $\lambda$ 跟 Camera matrix $M$ 合成 $Q$
- 但會遇到的問題
- 是 $\lambda$ 跟位置 $(u, v)$ 有關
- 所以這個式子也不再是 linear 的，沒辦法用解方程式的方式解
---
- 可以用的方式
- Newton Method
- Levenberg-Marquardt Algorithm (LM)
- 一開始先初始化
- Esitmated 一個 solution
- 再慢慢逼近最後的結果
- 因此我們先假設是 linear 的結果當成是初始值
- 再進一步使用 Newton 或 LM 來繼續解

---
- 傳統的假設
- zero-skew
- quare pixel
- 那 $(u_0, v_0)$ 就是 image 的中心
- 那如此一來，每一個點我們可以都改寫成上面的形式
---
- 如果我們把每一個點的 $u,v$ 來相除，那這樣就可以把 $\lambda$ 給消去
- 那系統就回到 linear 的狀態，就能把 $m_1, m_2$ 解出來

---
- 接著再把 $\lambda$ 跟 $m_3$ 這兩個 nonlinear 的值，利用前述的 LM 解開
---
## 3. Single View Geometry
### 3.1 Review calibration and 2D transformations
---
- 在已知 Camera Matrix (Intrinsic + Extrinsic) 的條件下，我們可以將 point 從 3D 的空間投影到 2D 的平面上
- $O_w$ 經過 Extrincsic $R,T$ 轉換到 $C$ 這個空間
- 再利用 Intrincsic $K$ 投影到圖像上
- 那我們可以反過來，從 2D 的點，重建回 3D 的點嗎？
- No in general
- 但我們可以知道 $P$ 會在哪一條線上
- 是由 $C$ 與 $p$ 所決定的
---
- 假設 $R$ 為 $I$、$T$ 為 $0$
- 根據關係，我們可以得到上面的數學表示式
- 由此可以找到在 3D 上面的 line $P_E$
- 由 C 和 p 所定義
---
- 這是一條線的表達方式

---
- 而因為中心點就是 camera center
- 所以出發點為 $(0, 0, 0)$
- 向量 $d$ 也可以藉此被求出
- 所以我們只需要知道 $K$ 與 2D 在 homogenious coordinate 上的點 $p_h$
- 就可以知道 3D 的線 $P_E$
---
- 以下複習 2D 的 transformation
- Isometries
- Rotation(1 DOF) + Translation (2 DOF)
- 共 3 DOF
- Regulate motion of rigid object
---
- Similarity
- 比 Isometries 多了 scale $s$
- 4 DOF
---

- Affinities
- 6 DOF
- 可以視為
- 2 DOF 是 Translation $t_x, t_y$
- 2 DOF 是 scale，$S_x, S_y$
- 2 DOF 是 Rotation，$\theta, \phi$
- 平行 依然會維持
- Ratio of lengths on collinear lines
- 
- 線上的點之間的距離會成比例
- 可以使用 $SVD$ 來分解
- 
---
- Projective
- 多了 $v$，是一個 $1*2$ 的 row matrix，所以比 Affinities 多 2 DOF
- $6+2=8$ DOF
- 保持 Collinearity，也就是從 line still map to line
- 但平行不會維持了
- cross ratio of 4 collinear points 會維持
- 
- example
- 
---
### 3.2 Vanishing points and lines
---
- 一組平行線在照片上的交點
- 最遠的綠點稱作 Vanishing point
- 最遠的青線稱作 Vanishing line
---
- 在考慮如何表示 Vanishing line 之前
- 我們先複習如何在 2D 平面上來表示一直線
- 可以利用點 $[x_1, x_2]^T$ 的在 homogeneous coordinate 與線向量 $[a,b,c]$ 的**內積** $=0$
---
- 如何找兩條線的交點
- 使用 cross product **外積**

:::success
- 表示線用 **內積**
- 交點用 **外積**
:::
---
- 那如何表示無窮遠的焦點呢？
- 讓 homogenious coordinate 的 $z$ 為 0
- 證明就是利用自己假設的兩條平行線，$l\cross l \prime$ 來求交點
---
- 補充 cross product 的公式
---
- 得證，無窮遠的點的表示方法
---
- 回頭帶入，就可以知道
- 無窮遠的點 $x_\infty = [b, -a, 0]^T$
- 跟線向量 $[a, b, c]$ 內積為 $0$
- 表示會經過線 $I = [a, b, c]$
- 一組平行線，也就是一個方向，會對應到一個 vanishing point
---
- 每一個位在無限遠的點，都會 lie on a line，這個 line 是 $l_\infty = [0, 0, 1]$
- 因為每個 infinite point $[x_1, x_2, 0]$ 跟其內積都會 $=0$
---
- 在已經知道無限遠的點時，如果我們將他 project，那他還會保持無窮遠嗎？
---
- 經過投影 matrix 可以知道
- Projective 投影不會保持 infinity
- Affine 會保持
---
- 前面在對點做 transform 時，乘上的是 $H^T$
- 但如果要對線做 transform，需要乘上的是 $H^{-T}$
- 如此一來，無窮遠的點才會落在無窮線上
---
- 如果對無窮遠的線做 Affine 與 Projective Transformation 呢？
---
- 跟點一樣
- Projective Transformation 不會維持 infinity
- Affine 會維持
---
- 移到 3D 的情況下，點和面的表示方法
---
- 一樣是利用 homogenious coordinate 最後一項為 $0$ 來表示位於無窮遠的點
---
- 利用一點與線向量來表示 $3D$ 上的線
- 也可以用兩張平面的交界，來表示一條直線
---
- 在理解點、線、面在 2D 與 3D 的關係後
- 此時我們將處在 3D 空間的無窮遠的點
- 投影在 2D 的平面上，結果就會是 vanishing point
---
- 如果要找 vanishing point
- 可以利用 3D 的 parallel line 線向量 \* camera matrix
- 而 3D 的線向量 $d$ 可以藉由 2D 投影點與 camera matrix $K$ 來計算得出
---
- vanishing point 2D 與 3D 的圖示對應
- 之所以也可以稱作 horizon line，因為 vanishing line 可以代表觀測者的水平位置、水平軸線、地平線資訊
- 1、2、3 個字的 horizon line 可以從圖上看到
- [](https://www.youtube.com/watch?v=4H-DYdKYkqk)
- infinity point 會在 infinity line 上
- 有些垂直方向的 vanishing point 不會出現，但這些點是例外
- 

---
- 如果兩線(yello)在 horizon line(orange) 上有交點，則兩線在 3D 平面上為平行線
---
- 3D 的面，投影到 2D，就會是線
- 現在我們有 2D 的 vanishing line，要回推 3D，稱為 Vanishing plane
- vanishing plane 的求法為
- 利用 2D 的 horizon line (vanishing line)乘上 camera parameter 的 transpose $K^T$
- 就可以找到 3D 的 vanishing plane
- 也就是 Vanishing line 的延伸
---
:::warning
:100: **重點複習**
- parallel line 的交會是 infinity point
- infinity point 會在 infinity line 上（有些垂直的例外）
- infinity point 經過投影是 vanishing point
- infinity line 經過投影是 vanishing line
- 另外有一個 vanishing plane 為一條 vanishing line 的延伸
:::
---
- 這裡也順便定義 infinity plane，也就是任何一條 infinity 都會經過的 plane
---
- 在定義完所有的名詞後
- 因為我們前面知道，一組平行線，也就是一個方向都會對應到一個 vanishing point
- 因此我們可以去找尋兩個 Vanishing point 之間的角度
- 我們先前也知道 3D 的線向量 $d$ 可以藉由 2D 投影點與 camera matrix $K$ 來計算得出，因此可以將其帶入到餘弦公式
---
- 在代入後，我們定義 $\omega = (KK^T)^{-1}$
- 並且得知，在 $\theta = 90$ 時，分子項 $v_1^T\omega v_2 = 0$
---

- 接著我們可以來討論 $\omega$ 的 property
- 可以得知是一個 symmetric
- $\omega_2 = 0$ 表示 camera 沒有偏移
- 如果 $\omega_2 = 0, \omega_1 = \omega_3$，圖像最後呈現為方形的像素點 square pixel
---
- 最後的 summary 表示，我們可以利用已知的 2D image、camera information
- 來 estimate 出 camera
- 跟 3D 的世界

---

### 3.3 Estimating geometry from a single image
---
- 接著要使用實例來解，因為我們從圖片上可以看出

---
- 因為我們可以知道圖像上的相對 $90^{。}$關係，所以可以來解出 $\omega$
- 總共是 $3$ degree of freedom，因為 up-to-scale 可以再減一個 dof
- 進而知道 $K$

---
- 在知道 $K$ 之後，我們接著利用圖形上可以看出的 horizon line，來求出 infinity plane
---
- 所以我們可以單純利用 vanishing point、vanishing line、90度資訊，以及推算出來的 camera parameter $K$
- 也就是 camera sysytem，去建構真實的結構
- 但還是沒辦法知道實際的 scale 大小
---
## 4. Epipolar geometry
### 4.1 Triangulation
---
- 剛剛我們是利用 Single view
- 去建構出 Structure of scene、Camera information $K$
- 然而，我們必須先知道圖上 Knowledge，如 $90^{。}$ 關係，或是 infinity line 等等資訊
- 但我們並不可能知道每張圖的這種關係，也可能未必存在
- 在 3D 投影到 2D 容易產生 intrinsic ambiguity，例如深度資訊就很難被估計
- 因此需要 Epipolar geometry，來判斷 Scene 的結構
- 利用雙眼可以建構出 3D 的 Scene
- 這樣的成像方式，稱為 triangulation
---
- 我們利用圖片上已知的資訊 $p$
- 估計出 $P^*$ 以接近實際情況的 $P$
---

---
### 4.2 Example
---
- 實際例子
- 在 $3D$ 情況是平行時
- $2D$ 圖片並不會平行，而是會收斂至 epipoles $e$
---
- 在兩張圖片都 parallel 的例子
- Baseline 跟 image 不會有交點
- epipoles line 跟 $u$ 平行
- epipoles 不存在
---
- 兩張 image 是前後的情況，稱為 Forward translation
- 都是收斂到同一個 epipole
---
### 4.3 Epipolar Constraint
---
- 給兩張相同物件的圖片
- 固定一張圖片的 $p$ 點，找尋 corresponding point $p\prime$
---
- 先找到對應到的 epipolar line
- 再去 fit color 來找到對應的點
---
- 基礎設定
---
- 兩張圖片分別對應到的 camera matrix $M, M\prime$
- Camera intrinsic 假設位在 canonical space，所以為單位矩陣
---
- 根據幾何關係
- 紫色指外積 cross product，得出紅色的向量
- 綠色指垂直，所以粉紅色與紅色向量內積為 $0$
- 最後可以得到 $[Ep. 7]$
---
- 外積可以化簡
---
- 所以可以得到 $[Eq. 9]$ 的形式
- 而 $[T_x]\cdot R$ 就定義為 ==$E$, Essential matrix==
---
- 根據 $[Ep. 10]$ 我們可以先定義 $l, l\prime$，此式可以得出 $l, l\prime$ 會經過 $p, p\prime$（$p, p\prime$ 可以變動）
- 觀察圖形，即可得知 $l, l\prime$ 就是 epipolar line
- 
- 從此推論可以得知 $e$ 與 $E$ 的關係
- $E$ 的 DOF 是 $5$
- $T$ 有 $3$ DOF
- $R$ 有 $3$ DOF
- 此結構為 up-to-scale，也就是如果 $P$ 的深度和 Baseline 都長度變兩倍，但他們的投影情況是一樣的，因此 up-to-scale 要剪掉 $1$ DOF
- 所以最後的 $DOF=3+3-1=5$
- 而由此也可知 $E$ 是 singular (rank $=2$)
---
- 剛剛我們假設 $K$ 是位在 canonical space
- 所以剛剛算出來的 $p$ 其實是 $p_c$
- 但實際情況 $K$ 並不是在 canonical space
- 所以可以將剛剛算出來的 $p_c$ 用實際的 $p, K$ 來表示
---

- 經過整理後的參數們，得到 ==$F,$ Fundamental matrix==
---
- DOF 比 $E$ 多出兩個，就是 $K$ 與 $K\prime$
---
- 假設已知 $F$
- 那如果我們知道左圖的 $p$，就可以直接找到另一張圖的 epipolar line $l\prime$
- 因為 $F$ 包含了
- $2$ view 的 epipolar geometry 資訊
- camera parameters
---
- The Eight-Point Algorithm
- 我們最少需要得到 8 組的點，才能 estimate $F$
---
- 在一組情況下的列示，可以進行整理成 $[Eq. 14]$
---
- $8$ 組就能夠利用 SVD 來 estimate $F$
---
- estimated 出來的 $\hat F$ 可能會是 full rank $(det(\hat F) ≠0)$
- 但實際上 fundamental matrix $F$ 要為 $Rank=2$
- 所以需要上圖的限制，盡量得到趨近於 $Rank=2$ 的 $\hat F$
---
### 4.4 Parallel image planes
---
- 兩張 image 是平行的情況
---
- 此時的 Essential matrix
---
- epipolar line 是 horizontal
---
- 由公式可以知道 $v= v\prime$
---
- Rectification 就是讓兩張圖片平行
- 達到 Epipolar constraint $v= v\prime$
---
- 為什麼需要 Parallel image planes？
- 我們就可以直接利用 linear interpolation 來得出新的 View
- 這就叫做 **View morphing**
---
- View morphing 也可以使用 Deep learning 的 model 來達成
---
- parallel 第一個用處是產生 triangulation
---
- 有了 parallel images 我們就可以得到 Point triangulation
- 進而計算出
- $x$ 方向誤差 disparity $p_u-p_u\prime$
- 深度 $z$ 等資訊
---
- 利用相似三角形，計算表達出 $Z$
---
- 第二個用處是能夠讓 correspondence 的任務比較簡單
- 因為兩者就是在同一個水平面上
- 方便直接比對
---
### 4.5 Correspondence problem
---
- 最直覺的方式，在 epipolar line 上將顏色比對
- 相同的就是對應點
- 遇到的問題
- line 上可能有多個相同顏色的點
- 兩張圖片可能整體亮度會改變
---
- 改以一個 window 來計算
- 並且使用 normalization
---
- 在不同 window size 下的結果
---
- 兩張 image 的投影像會遇到不佳的情況
- Shortening effect
- 兩張圖像距離 $B$ 過遠，無法捕捉到好的細節
- Occlusions
- object 距離 image $z$ 太近，可能兩張圖像抓到的內容會不同
---
- 為了降低 foreshortening and occlusions
- $B$ 越小越好、$z$ 越大越好
- $\frac{B}{z}$ 越小越好
- 然而 Measurement error
- 會因為 $\frac{B}{z}$ 越小，從圖看出 Measurement error 反而上升（紅點與實際 GT 綠點的距離）
- 因此兩者為 trade-off 必須取一個平衡
---
- 除此之外，也會遇到其他比對上的問題
- homogenous regions，有相似顏色的區塊
- 或是 repetitive patterns，相似的 pattern 結構
---
- 這時候我們就會需要使用 non-local 的 constraint
1. Uniqueness，對應必須是一對一
2. Ordering，每一個對應的內容，相對順序 order 會相同
3. Smoothness，disparity 是一個 smooth 的 function
- 利用這三個內容來修正會遇到的種種 issue
---
## 5. Multi-view geometry
---
### 5.1 The SFM problem
---
- sturcture from motion 問題
- 利用輸入的 $m$ 張圖片，來建構出 $3D$ 結構裡的 $n$ 的點，產生出 $3D$ 點圖

---
- $m$ 張照片就是 motion
- $n$ 個點就是 structure

### 5.2 Affine SFM
---
- Affine SFM 指的是 $3D$ 點投射到 image 上時，利用 Affine transformation
---
- 複習 Affine 與 Perspective 兩種 transformation
- 差別在 $m_3$ 的值，Affine 比較簡單
---
- 目標就是
- 根據已知的 image 上的點 $x_{ij}$
- 預測 estimate 出正確的 $A_i, b_i, X_j$
---
- 共 $8m +3n-8$ DOF
- 分析
- $8m$：為 $m$ 張圖片，每張有 $8$ DOF（$A$ 有 $2*3$、$b$ 有 $2*1$）
- $3n$：為 $n$ 個 $3D$ 點，每個點有 $3$ 個座標
- $8$：沒辦法完整預估的 constraint 限制
---
- 有兩種預測的方式
- 先介紹 Factorization method
- 又稱作 Tomasi & Kanade algorithm
---
- 先對所有資料點做 centering
---
- 根據 $[Eq.8]$ 推導，可以知道
- 我們想求的 $2D$ 投影後再減去質心的值
- 就是計算出 $3D$ point 減掉質心、再經過 Affine transform
---
- 可以理解為轉換 world reference system 座標
---
- 因為每個 camera 都有 $x, y$ 兩個方向，共 $2m$
- 又有 $n$ 個點
- 所以總共可以產生 $2m*n$ 個 data 的 matrix
---
- 此 matrix 也可以拆分、理解為 camera * points
- 根據幾何上的性質（$X$ 有 $x, y, z$ 三個方向），分解的兩個子 matrix 的 rank $=3$
---
- 分解的目標
---
- 利用 SVD 方式來拆分
---
- 因為剛剛知道 $A$ 與 $X$ 兩個 Matrix 的 $rank = 3$
- 所以我們只取部分的黃色部份來當作 estimate 結果
---
- Affine ambiguity
- 但如果這時，我們針對 $M, S$ 分別乘上 $H, H^{-1}$
- 條件依然會成立
- 此一現象稱為 Affine ambiguity
---
- 圖形上的觀點，可以看出兩張圖
- 他們在投影後的 $2D$ image 上的點會是一樣的
- 所以 $8m +3n-8$ DOF 中的 $8$ 就是因為此 ambiguity
---
### 5.3 Perspective SFM
---
- Perspective 的 $M$ 中的 data 變得更多
- 共 $11m+3n – 15$ DOF
- 11：一個 camera $3*4 - 1$，共 $m$ 個 cameras
- 3：一個 point $x, y, z$ 共 3 個值
- 15：projective ambiguity
---
- projective ambiguity 的圖示
---
- 處理 the perspective ambiguity 的方式為 metric reconstruction，其中一個方式為 self-calibration
---
- 現在介紹另外一種預測 SFM 的方式
- Algebraic approach
---
- 利用前面學過的 $2$ 個 view 的 $8$ point pairs
- 去預測出 Fundamental matrix $F$
---
- 由已知的 $F$，去得出 $[b_x]A$
---
- 利用 SVD 求出 $b$
---
- 再求出 $A$
- 就可以知道 camera matrix $\tilde M_1, \tilde M_2$
---
- 而 $b$ 其實就是 epipole
---
- 有了 camera matrix $\tilde M_1, \tilde M_2$
- 就可以利用已知的 $x$，來預測出 $3D$ point $X$
---
- 剛剛都是兩個 view 的情況
- 在多個 view 時，就是做很多次的 2-view pairs
- 遇到不一致的 3D 點，$X$ 時
- 可以使用第三種處理 SFM 的 method
- **bundle adjustment**
---

---
- 在介紹 bundle adjustment 之前，先概述前面方式會遇到的問題
- **Factorization**
- 會需要 input 所有的資料，因此圖像不能遇到 occur 遮擋的情形，否則會出現 failure
- **Algebraic**
- 只適用在 2-view
---
- non-linear 的方式
- 就是去 minimize re-projection 的 error
---
- minimize 的方式
- 可以使用 Newton method
- 或是使用 Levenberg-Marquardt Algorithm
---
- 可以克服另外兩個 method 的缺點
- 但如果初始狀態的參數太糟，computatioon cost 就會太大
- 因此我們可以先使用前面兩種方式的結果，來作為 Bundle adjustment 的初始參數，如此一來就可以解決 cost 太大的狀況
---
### 5.4 Self-calibration
---
- 為了處理 similarity 的問題
- 我們可以經過運算（較難跳過）來得出 $[Eq. 15]$ 的這個限制（也是利用 Bundle adjustment），進而解決
- 就只會剩下 similarity ambiguity 了（比例），而不會有奇形怪狀的 transformation 也符合 $2D$ image
---
### 5.5 Summary
---

---

## #參考資料
- [EE 6485 Computer Vision 計算機視覺](https://aliensunmin.github.io/teaching/cv2023/index.html)