多視角電腦視覺筆記（一）

本文為讀了 An Invitation to 3-D Vision 書中 Chapter 8 的筆記。

點與線的多視角約束

對於三維空間中的點 $\mathbf{X}$ 與第 i 個視角的圖片上對應座標 $\mathbf{x}_i$ 來說，我們可以寫出以下關係式： $$\lambda_i \mathbf{x}_i = \Pi_i\mathbf{X}$$ 其中 $\lambda_i$ 是點的深度，$\Pi_i$ 是第 i 視角的投影矩陣，$\Pi_i = K(t_i)\Pi_0g(t_i)$，g 為旋轉平移的變換矩陣。另外，對於多視角的點 $\mathbf{x}_i$ 來說，其 preimage 為一條直線，而理論上這些 preimage 必須交會在點 $\mathbf{X}$。

另外對於空間中的一條線 $\mathbf{L}=\{\mathbf{X}|\mathbf{X}=\mathbf{X}_0+\mu \mathbf{V}\}$ 來說，其 preimage 為一個平面 $P_i$，而平面 $P_i$ 的法向量為 $\mathbf{l}_i$。理論上所有的preimage 平面們應該要交會在直線 $\mathbf{L}$ 上。另外，由於 $\mathbf{x}_i$ 在平面 $P_i$ 上，且 $\mathbf{l}_i$ 為平面的法向量，因此 $\mathbf{l}_i^T\mathbf{x}_i = 0$，以及： $$\mathbf{l}_i^T \Pi_i \mathbf{X}_0 = \mathbf{l}_i^T \Pi_i \mathbf{V} = 0$$

Rank Conditions

在兩個視角的情況下，我們能用一些技巧將上面約束式子中的變數消去得到 epipolar constraints，而接下來的部分是說明在多視角的情況下如何將變數消去並轉換成矩陣的 rank conditions。

點的約束

前面介紹過的點約束式可以寫成以下式子： $$\mathit{I}\doteq \begin{bmatrix} \mathbf{x}_1 & 0 & \cdots & 0\\ 0 & \mathbf{x}_2 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \mathbf{x}_m \end{bmatrix}_{3m \times m} \\ \mathbf{\lambda} \doteq \begin{bmatrix} \lambda_1\\ \lambda_2\\ \vdots\\ \lambda_m \end{bmatrix} \\ \Pi \doteq \begin{bmatrix} \Pi_1\\ \Pi_2\\ \vdots\\ \Pi_m \end{bmatrix}_{3m \times 4} \\ \mathit{I}\mathbf{\lambda}=\Pi \mathbf{X}$$ 由於 $mathit{I}$ 的每一個 column 都在由矩陣 $Pi$ 的 column 展開的四維空間上，因此此兩個矩陣為 linear dependent。我們可以將此 linear dependent 關係式寫成： $$N_p \doteq \begin{bmatrix} \Pi_1 & \mathbf{x}_1 & 0 & \cdots & 0\\ \Pi_2 & 0 & \mathbf{x}_2 & \cdots & 0\\ \vdots & 0 & 0 & \ddots & 0\\ \Pi_m & 0 & 0 & \cdots & \mathbf{x}_m \end{bmatrix}_{3m \times (m+4)} \\ rank(N_p)\leq m+3$$ 也可以將此約束寫成另一種形式： $$I^{\perp}=\begin{bmatrix} \widehat{\mathbf{x}}_1 & 0 & \cdots & 0\\ 0 & \widehat{\mathbf{x}}_2 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \cdots & \widehat{\mathbf{x}}_m \end{bmatrix}_{3m \times 3m} \\ I^{\perp}I=0 \Rightarrow I^{\perp} \Pi \mathbf{X}=0 \\ W_p\doteq I^{\perp} \Pi =\begin{bmatrix} \widehat{\mathbf{x}}_1\Pi_1\\ \widehat{\mathbf{x}}_2\Pi_2\\ \vdots\\ \widehat{\mathbf{x}}_m\Pi_m \end{bmatrix}_{3m \times 4} \\ rank(W_p) \leq 3$$ 結合以上兩個約束，我們可以寫出點的約束式： $$rank(W_p)=rank(N_p)-m \leq 3$$

線的約束

由前文我們可以用類似的方法來得到線的約束式： $$W_l\doteq \begin{bmatrix} l_1^T\Pi_1\\ l_2^T\Pi_2\\ \vdots\\ l_m^T\Pi_m \end{bmatrix}_{m \times 4}$$ 由於此矩陣的 null space 至少二維 ($\mathbf{X_o}$ 與 $\mathbf{V}$)，所以可以得到此矩陣的 rank condition： $$rank(W_l) \leq 2$$

Multi-view Matrix of a Point 

在不失一般性的情況下假設第一個相機的座標系為參考座標系，則可以假設所有的投影矩陣為：$\Pi_1=[I, 0], \Pi_2 = [R_2, T_2], \cdots \Pi_m=[R_m, T_m]$。我們用一個技巧將前面提到的 $W_p$ 與另一個矩陣 $D_p$ 相乘可以得到以下結果： $$W_pD_p=\begin{bmatrix} \widehat{\mathbf{x}_1}\Pi_1\\ \widehat{\mathbf{x}_2}\Pi_2\\ \vdots\\ \widehat{\mathbf{x}_m}\Pi_m \end{bmatrix}_{3m \times 4} \begin{bmatrix} \widehat{\mathbf{x}_1} & \mathbf{x}_1 & 0\\ 0 & 0 & 1 \end{bmatrix}_{4 \times 5} =\begin{bmatrix} \widehat{\mathbf{x}_1}\widehat{\mathbf{x}_1} & 0 & 0\\ \widehat{\mathbf{x}_2}R_2\widehat{\mathbf{x}_1} & \widehat{\mathbf{x}_2}R_2\mathbf{x}_1 & \widehat{\mathbf{x}_2}T_2\\ \vdots & \vdots & \vdots\\ \widehat{\mathbf{x}_m}R_m\widehat{\mathbf{x}_1} & \widehat{\mathbf{x}_m}R_m\mathbf{x}_1 & \widehat{\mathbf{x}_m}T_m \end{bmatrix} \\ M_p\doteq \begin{bmatrix} \widehat{\mathbf{x}_2}R_2\mathbf{x}_1 & \widehat{\mathbf{x}_2}T_2\\ \vdots & \vdots\\ \widehat{\mathbf{x}_m}R_m\mathbf{x}_1 & \widehat{\mathbf{x}_m}T_m \end{bmatrix} \\ rank(W_p) \leq 3 \Leftrightarrow rank(M_p) \leq 1$$ $M_p$ 即為一個點 p 的 multi-view matrix。$\mathbf{x}_1$ 為點 p 在第一個視角的座標，而 $\widehat{\mathbf{x}_i}$ 為 coimages。$W_pD_p$ 的前三個 column 的維度為二，所以後兩個 column 的維度最多為一。把以上的 rank condition 整理出來可得： $$rank(M_p)=rank(W_p)-2=rank(N_p)-(m+2) \leq 1$$

一些 Multi-view Matrix 的性質

• 由於 $\widehat{\mathbf{x}_i}T_i$ 與 $\widehat{\mathbf{x}_i}R_i\mathbf{x}_1$ linearly dependent，可以推得 $\mathbf{x}_i^T\widehat{T_i}R_i\mathbf{x}_1=0$，也就是 bilinear epipolar 約束。
• 由此矩陣還可以推導出 trilinear constraint：$\widehat{\mathbf{x}_i}(T_i\mathbf{x}_1^T R_j^T-R_i\mathbf{x}_1 T_j^T)\widehat{\mathbf{x_j}}=0$。
• Uniqueness of the preimage 的定理，可用於檢查特徵的配對過程中是否產生沒配對好的點或是 degenerate 的情形。
  
• $rank(M_p)=2$：沒有點的對應關係，也沒有 preimage。
  
• $rank(M_p)=1$：存在唯一的 preimage。
  
• $rank(M_p)=0$：degenerate，preimage 不為唯一。