[CV] 8-point algorithm: Fundamental Matrix

1. SIFT 등을 이용하여 reliable corresponding features 를 8쌍 이상 추출.

 

---

2. 1번 과정에서 찾은 correspondance에 Epipolar Constraint를 적용하여 matrix equation을 얻음.

2024.06.28 - [Programming/DIP] - [CV] Epipolar Geometry [작성중]

[CV] Epipolar Geometry [작성중]

 

예를 들어 $i$-th correspondance $(\mathbf{p}_R^{(i)}, \mathbf{p}_L^{(i)})$에 다음이 성립.

$${\mathbf{p}_L^{(i)}}^\top \mathbf{F} {\mathbf{p}_R^{(i)}}= 0$$

 

이를 풀어서 쓰면 다음과 같음.

$$\begin{bmatrix} u_L^{(i)} & v_L^{(i)} & 1 \end{bmatrix} \begin{bmatrix} f_{11} & f_{12} & f_{13} \\ f_{21} & f_{22} & f_{23} \\ f_{31} & f_{32} & f_{33}=1 \end{bmatrix} \begin{bmatrix} u_R^{(i)} \\ v_R^{(i)} \\ 1 \end{bmatrix} = 0$$

 

위 matrix equation은 다음의 linear equation과 같음.

$$(f_{11}u_R^{(i)}+f_{12}v_r^{(i)}+f_{13})u_L^{(i)} +(f_{21}u_R^{(i)}+f_{22}v_R^{(i)}+f_{23})v_L^{(i)}+(f_{31}u_R^{(i)}+f_{32}v_R^{(i)}+f_{33})=0$$

 

8개의 coorespondance를 모두 사용하면 다음을 얻음.

$$\begin{bmatrix} u_R^{(1)}u_L^{(1)} & v_R^{(1)}u_L^{(1)} & u_L^{(1)} & u_R^{(1)}v_L^{(1)} & v_R^{(1)}v_L^{(1)} & v_L^{(1)} & u_R^{(1)} & v_R^{(1)} & 1 \\ \vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\ u_R^{(8)}u_L^{(8)} & v_R^{(8)}u_L^{(8)} & u_L^{(8)} & u_R^{(8)}v_L^{(8)}& v_R^{(8)}v_L^{(8)} & v_L^{(8)} & u_R^{(8)} & v_R^{(8)} & 1 \end{bmatrix} \begin{bmatrix} f_{11} \\ f_{12} \\f_{13}\\f_{21}\\f_{22}\\f_{23}\\f_{31}\\f_{32}\\f_{33}=1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$$

 

이를 다음과 같이 기재할 수 있음.

$$\mathbf{A} \mathbf{f} = \mathbf{0}$$

 

여기서 $\mathbf{A}$는 8쌍의 correspondance로 부터 구할 수 있고, zero vector $\mathbf{0}$는 상수이므로, unknown이 8개인 $\mathbf{f}$를 충분히 구할 수 있음.

---

3. Fundamental Matrix는 scale ambiguity 를 통해 $\|\mathbf{f}\|^2=1$이라는 constraint를 주어 하나의 $\mathbf{F}$를 얻도록 함.

$${ \mathbf{p}_L^{(i)} }^\top \mathbf{F} \mathbf{p}_R^{(i)} = 0 ={\mathbf{p}_L^{(i)} }^\top k \mathbf{F} \mathbf{p}_R^{(i)}$$

 

$\mathbf{F}$와 $k\mathbf{F}$는 같은 epipolar geometry에 해당하므로, scale을 고정하여 하나의 $\mathbf{F}$를 구해야함.

때문에 $\|\mathbf{f}\|^2=1$을 앞서 구한 equation의 constraint로 추가함.

---

4. 이는 다음의 constrained least squares problem이 유도됨.

$\|\mathbf{f}\|^2=1$이라는 제한 조건 하에서 이상적으로 $\mathbf{A}\mathbf{f}=0$이 만족하는 $\mathbf{f}$를 구해야 하나,

측정의 noise 등으로 인해 최대한 0에 가까워지도록 해주는 $\mathbf{f}$를 구하면 됨.

 

이는 다음과 같은 constrained minization problem이 된다.

 

$$\underset{\mathbf{f}} {\text{argmin }} \|\mathbf{Af}\|^2 \text{ s.t. } \|f\|^2=1$$

 

이는 constrained least squares 등의 Direct Linear Transform을 푸는 방법으로 쉽게  $\mathbf{f}$를 구할 수 있음을 뜻함.

2024.07.16 - [분류 전체보기] - [ML] Constrained Least Squares: Lagrangian 을 활용.

[ML] Constrained Least Squares: Lagrangian 을 활용.

 

실제로는 u-v pixel coordinates를 그대로 사용하지 않고,

Hartley's normalization을 수행하여 normalizaed constrained least squares 를 함.

(이 경우 수치적인 안정성이 보다 높음)

2024.07.17 - [Programming/DIP] - [CV] Hartley’s Normalization

[CV] Hartley’s Normalization

 

least square로 구해진 $\hat{\mathbf{f}}$를 rearrange하여 구한 $\hat{\mathbf{F}}$는 singular matrix가 아닐 수 있음(noise 등으로 인해).

때문에 $\text{det } F$ 가 되도록 rank-2 approximation을 수행하기도 함.

 

마지막으로 least squares를 수행하기 전의 normalization을 되돌리기 위한 denoramlization을 수행하여 $\mathbf{F}$를 구함.

---

5. 각 카메라의 intrinsic parameters $\mathbf{K}_L$와 $\mathbf{K}_R$ 를 통해 Essential Matrix $\mathbf{E}$를 구함.

$$\mathbf{E}=\mathbf{K}_L^\top \mathbf{F} \mathbf{K}_R$$

2024.06.22 - [Programming/DIP] - [CV] Geometric Camera Model

[CV] Geometric Camera Model

 

---

6. $\mathbf{E}$로부터 SVD를 통해, $\mathbf{R}$과 $\mathbf{t}$를 구한다.

$$ \mathbf{E} = [\mathbf{t}]_\times \mathbf{R}$$

 

2024.06.28 - [Programming/DIP] - [CV] Epipolar Geometry [작성중]

[CV] Epipolar Geometry [작성중]

 

---

같이 보면 좋은 자료들

https://velog.io/@cjkangme/CS231A-%EA%B0%95%EC%9D%98-%EB%85%B8%ED%8A%B8-3-epipolar-geometry-2

CS231A 강의 노트 3 - epipolar geometry (2)