[CV] Epipolar Geometry [작성중]

Epipolar Geometry

Epipolar geometry는

• 두 개의 카메라 images에서
• 대응하는 점들 사이의 기하학적 관계를 설명하는 데 사용되는 용어

Epipolar geometry는 각 카메라 image 상의 각 point(점)이 epipolar line을 통해 어떻게 연결되었는지를 나타냄.

• Stereo calibration 으로 얻어진 $R$과 $\mathbf{t}$를 이용하여 계산됨.
• Stereo vision과 3D Reconstruction에 사용된다.

 

CV에서는 Epipolar Geometry에서 주로
Epipolar Constraint와
Triangulation을 이용함

---

주요 용어

각 용어에 대해서는 아래 그림을 참조하라.

다음 그림은 3차원의 공간상의 점 $\mathbf{P}$가 2개의 카메라에 의해 촬영되었고,

각 카메라에 의해 $\mathbf{p}_1$와 $\mathbf{p}_2$로 normalized image planes에 투영된 것을 보여줌.

https://medium.com/@sarcas0705/computer-vision-epipolar-geometry-36b032d697a3

 

• baseline: camera의 원점(center)를 잇는 선. $\overline{oo'}$
• epipoles: $e$와 $e'$, 두 카메라 원점을 잇는 선과 normalized image plane이 만나는 점.
• epipolar plane: camera의 원점들과 3차원의 촬영대상 $\mathbf{P}$가 이루고 있는 평면.
• epiline (or "epipolar line"):
  • "$\mathbf{P}$의 투영된 점인 $\mathbf{p}_1$와 같은 image plane에 있는 epipole $e$"을 이은 line $l$과,
  • "$\mathbf{P}$의 투영된 점인 $\mathbf{p}_2$와 같은 image plane에 있는 epipole $e'$"을 잇는 line $l'$임.
  • 왼쪽의 카메라에서 촬영대상 $\mathbf{P}$와 투영점 $\mathbf{p}_1$를 잇는 line을
  • 오른쪽의 카메라의 image plane상에 투영한 것이 epiline $l'$임.

왼쪽의 카메라(오른쪽도 마찬가지)에서 depth information이 없을 경우,

• line $\overline{\mathbf{P},\mathbf{p}_1}$ 상에 있는 모든 점들이 모두 같은 투영점 $\mathbf{p}_1$를 가지게 되어
• 왼쪽의 카메라 image 상의 $\mathbf{p}_1$에 대응하는 point $\mathbf{p}_2$를 유일하게 매핑할 수 없으나
• 대응하는 $\mathbf{p}_2$이 존재하는 epiline $l'$은 유일하게 결정할 수 있음.

Epipolar Geometry는

• 두 개의 카메라에서 촬영된 images에서
• 한 쪽의 image에서의 특정 point로부터 다른쪽 image 상의 epiline을 구해주는데 사용되는
• Essential Matrix $E$ 와 Fundamental Matrix $F$ 를 추출하고,
• 이 matrixs로 정의되는 변환관계를 바탕으로 3D 정보를 계산해냄.

---

Essential Matrix

두 개의 카메라에서 얻어진

두 개의 이상적인 normalized image planes (=camera calibration이 수행된)에서의
correspondance 사이의 geometrical relationship을 정의하는 matrix $E$.

• Essential Matrix를 얻기 위해선 $o$ 에 대한 camera coordinate를 $o'$의 camera coordinate로 변경해주는
• Extrinsic Matrix $\begin{bmatrix}R&\mathbf{t}\end{bmatrix}$ 를 알아야 함.

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

Essential Matrix를 통해, camera calibration이 수행된 normalized image plane의 $\mathbf{p}_1$에 대해

대응하는 epiline $l'$을 다음과 같이 구함.

$$l' = E\mathbf{p}_1 \\ l =E^\top \mathbf{p}_2$$

---

Epipolar Constraint

Epiploar geometry의 관계에 의해서

다음과 같은 epipolar constraint (or essential constraint)가 성립.

$$\mathbf{p}_2^\top\color{red}{E}\mathbf{p}_1 = \mathbf{p}_2^\top\color{red}{[\mathbf{t}]_{\times}R}\mathbf{p}_1=0 \tag{ec}$$

위의 식을 Longuet-Higgins Equation이라고도 부름 : 카메라1에 좌표계로  $\mathbf{p}_2$를 회전시키고 $\mathbf{t}$와 cross product한 결과벡터는 $\mathbf{p}_1$과 orthogonal.

 

Epipolar Constraints에 의해 다음이 성립함.

• $\mathbf{p}_1\cdot (\mathbf {t}\times \mathbf{p}_1) = 0$
• $\mathbf{p}_2\cdot (\mathbf{t} \times \mathbf{p}_2) =0$

참고로, $[t]_{\times} \mathbf{x}$ 는 vector $\mathbf{t}$와 vector $\mathbf{x}$의 cross product를 matrix form으로 나타낸 것임.

2024.06.28 - [.../Linear Algebra] - [LA] Matrix Multiplication for Cross Product

[LA] Matrix Multiplication for Cross Product

 

---

이에 대한 유도는 다음과 같음.

 

우선 첫번째 camera coordinate에서의 사물의 좌표를 $\mathbf{p}_{c1}$ 라고 하고,

두번째 camera coordinate에서의 사물의 좌표 $\mathbf{p}_{c2}$라고 하면 다음이 성립함.

$$\mathbf{p}_{c2} = R\mathbf{p}_{c1}+\mathbf{t}$$

이 $\mathbf{p}_{c2}$과 $\mathbf{p}_{c1}$를 가지고 다음이 성립함.

$$\begin{aligned}\mathbf{p}_{c2}^\top E\mathbf{p}_{c1}&=\mathbf{p}_{c2}^\top [\mathbf{t}]_{\times} R \mathbf{p}_{c1} \\ &= \mathbf{p}_{c2}^\top [\mathbf{t}]_{\times} (\mathbf{p}_{c2}-\mathbf{t}) \\ &= \mathbf{p}_{c2}^\top \{ (\mathbf{t} \times \mathbf{p}_{c2})-(\mathbf{t} \times \mathbf{t})\} \\ &= \mathbf{p}_{c2} ^\top \{ (\mathbf{t} \times \mathbf{p}_{c2}) - \mathbf{0} \} \\&= \mathbf{p}_{c2}^\top (\mathbf{t} \times \mathbf{p}_{c2}) \\ &= 0 \\ \end{aligned}$$

참고로, 위의 식에서 $\mathbf{p}_{c2}^\top E\mathbf{p}_{c1}=0$인 이유는 다음에 기반함.

• 자기자신과의 cross product는 항상 zero vector,
• cross product는 두 operand에 orthogonal한 vector를 결과로 가짐:
  • $\mathbf{p_{c2}}$ 와 $\mathbf{t}$의 cross product의 결과는
  • $\mathbf{p_{c2}}$와 $\mathbf{t}$와 orthogonal

위의 결과에

normalized image plane의 $\mathbf{p}_{2}=\begin{bmatrix}x_n & y_n & 1\end{bmatrix}^\top$이 camera space의 $\mathbf{p}_{c2}$와 함께 성립하는 다음 관계를 대입한다.

$$\mathbf{p}_{c2} = \begin{bmatrix} x_{\text{c2}} \\ y_{\text{c2}} \\ z_{\text{c2}} \end{bmatrix} = z_{\text{c2}}\begin{bmatrix} \frac{x_{\text{c2}}}{z_\text{c2}} \\ \frac{y_\text{c2}}{z_\text{c2}} \\ \frac{z_\text{c2}}{z_\text{c2}} \end{bmatrix}  = z_{\text{c2}} \begin{bmatrix} x_n \\ y_n \\ 1 \end{bmatrix}=z_{\text{c2}}\mathbf{p}_2$$

$\mathbf{p}_{c2}^\top E \mathbf{p}_{c1}=0$에 위를 대입하면, 다음이 성립함.

$$\mathbf{p}_{c2}^\top E\mathbf{p}_{c1}=z_\text{c2}\mathbf{p}_{2}^\top E z_\text{c1}\mathbf{p}_{1} = \mathbf{p}_2^\top E \mathbf{p}_1 = 0 $$

• $z_{\text{c2}} \ne 0$ 이고, $z_{\text{c1}}\ne0$ 이기 때문임..

$E=[\mathbf{t}]_\times R$은 항상 존재하며 $\mathbf{p}_{2}^\top E \mathbf{p}_{1}=0$이 성립함.

---

Essential Matrix는 다음의 성질을 가짐.

$\mathbf{E}$는 singular matrix이며, rank가 2임.

• $\mathbf{t}$와의 cross product를 matrix multiplication으로 표현할 경우,
• $[\mathbf{t}]_\times$가 skew-symetric matrix가 되어 rank=2임.
• 이를 rank=3 인 $\mathbf{R}$와 곱한 것이 $\mathbf{E}$이며, 때문에 $\mathbf{E}$는 rank=2임. 

2024.07.16 - [.../Linear Algebra] - [LA] Skew-Symmetric Matrix 란

[LA] Skew-Symmetric Matrix 란

 

$\mathbf{E}$를 통해 epipolar line을 다음과 같이 구할 수 있음.

• $E\mathbf{p}_1=l'$ 과 $E^\top\mathbf{p}_2= l$
• $Ee=\mathbf{0}$와 $e'^\top E=\mathbf{0}$

2024.07.16 - [Programming/DIP] - [CV] Example: Essential Matrix and Epipolar Line

[CV] Example: Essential Matrix and Epipolar Line

 

---

Scale Ambiguity of Essential Matrix

Essential Matrix는 두 카메라 간의 $R$과 $\mathbf{t}$를 통해 얻어지는데,
translation $\mathbf{t}$에서 방향만 알 수 있을 뿐 실제 크기(즉, scale)는 알 수 없음.

 

Scale Ambiguity는
두 카메라 간의 평행 이동 벡터 ( $\mathbf{t}$ )의 크기(스케일)를
알 수 없는 상태를 의미함.

원인

1. Homogeneous Coordinates:
   • Essential matrix는 homogeneous coordinates를 사용하여 표현됨.
   • Homogeneous coordinates에서 점의 좌표는 스케일링에 의해 영향을 받지 않음.
   • 즉, $\begin{bmatrix}x & y & z\end{bmatrix}^\top$와 $\begin{bmatrix}kx & ky & kz\end{bmatrix}^\top$는 동일한 점을 나타내며, 이로 인해 스케일 정보를 알 수 없게 됨.
2. Relative Motion:
   • Essential matrix는 두 카메라의 상대적인 회전 $R$과 평행 이동 $\mathbf{t}$ 를 나타냄.
   • 이때, $\mathbf{t}$ 는 방향 벡터로 간주되며, 그 크기는 실제 이동 거리가 아닌 상대적인 방향만을 제공함.
   • 따라서 $\mathbf{t}$ 의 크기는 알 수 없음.
3. Normalization:
   • 카메라의 내부 파라미터를 사용하여 이미지 좌표를 정규화할 때, 좌표의 스케일 인자가 제거됨.
   • 이로 인해 두 카메라 간의 절대적인 거리를 측정할 수 없고, 상대적인 위치와 방향만 알 수 있음.

---

예시

두 카메라가 동일한 장면을 다른 각도에서 촬영했다고 가정할 때:

• 카메라 간의 실제 이동 벡터가 $\begin{bmatrix}t_x & t_y & t_z\end{bmatrix}^\top$라면,
• Essential matrix는 이 벡터의 방향만을 포함하고 크기 정보는 알 수 없게 됨.
• 동일한 장면에서 이동 벡터가 $\begin{bmatrix}2t_x & 2t_y & 2t_z\end{bmatrix}^\top$ 라면, 두 벡터는 방향은 같지만 크기는 다름.
• 그러나 Essential matrix는 두 경우 모두 동일한 방향 벡터로 간주함.

---

DoF of Essential Matrix

$R$ (DoF=3)과 $\mathbf{t}$ (DoF=3)가 필요한데,

앞서 설명한 Scale Ambiguity에 의해 $\mathbf{t}$에서 DoF가 하나 줄어들어,

Essential Matrix의 경우 DoF가 5에 해당함. 

 

Epipolar constraint $x'^\top Ex=0$ 에 의해 1개의 correspondance마다 1개의 식이 주어지므로,

최소한 5개의 correspondance가 있어야 함.

---

Fundamental Matrix

Epipolar constraint를 의미하는 Essential Matrix에

Camera의 intrinsic parameters를 고려한 것이 fundamental matrix임.

• Fundamental matrix $F$는 일종의 Essential Matrix $E$의 generalization으로
• intrinsic camera parameters를 고려함

$$F=(K_2^{-1})^\top E K_1^{-1}$$

 

앞서 normalized image plane의 포인트 $\mathbf{p}_1$와 $\mathbf{p}_2$은

Camera의 intrinsic parameters $K_1$, $K_2$에 의해

실제로 얻는 image상의 포인트 $\mathbf{p}_\text{img,1}$와 $\mathbf{p}_\text{img,2}$와 다음의 관계를 가짐.

 

$$ \mathbf{p}_1 = K_1^{-1} \mathbf{p}_\text{img,1} \\\\ \mathbf{p}_2 = K_2^{-1} \mathbf{p}_\text{img,2}$$

 

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

[CV] Geometric Camera Model

 

 

이를 앞서 Essential matrix $E$로 표현된 Epipolar constraint에 적용하면 다음과 같음.

$$ \mathbf{p}_2^\top E \mathbf{p}_1 = (K_2^{-1} \mathbf{p}_\text{img,2})^\top E (K^{-1} \mathbf{p}_\text{img,2}) = \mathbf{p}^\top_\text{img,2} (K_2^{-1})^\top E K_1^{-1} \mathbf{p}_\text{img,1} =0$$

 

위의 식에서 $(K_2^{-1})^\top E K_1^{-1}$을 $F$라 하고 fundamental matrix라고 부름.

 

$$ F=(K_2^{-1})^\top EK_1^{-1} $$

 

결국, $F$는 실제 image상의 특정 point $\mathbf{p}_\text{img}=\begin{bmatrix} u & v & 1 \end{bmatrix}$에 대응하는 epiline을 대응시킴.

---

$\mathbf{E}$와 마찬가지로, rank=2 이다.

이는, $\text{det }\mathbf{E}=0$임을 의미하므로 $\mathbf{E}$는 singular matrix임.

 

다음과 같이 essential matrix와 같은 특성을 가짐: 실제 image 에 대한 것으로 변경됨.

• $F^\top\mathbf{p}_\text{img,2}=l_\text{img}$ 와 $F\mathbf{p}_\text{img}= l'_\text{img}$
• $Fe_\text{img}=\mathbf{0}$ 와 $e'_\text{img}F=\textbf{0}$ 

2024.07.16 - [Programming/DIP] - [CV] Example: Fundamental Matrix and Epipolar Line (등극선)

[CV] Example: Fundamental Matrix and Epipolar Line (등극선)

---

DoF of Fundamental Matrix

$3 \times 3$ matrix이지만, rank=2여야 하는 제한 조건과 scale ambiguity로 인해 DoF가 2가 줄어서 DoF=7임.

• Epipolar constraints인 matrix equation에 해당하는 식이 1개의 correspondance당 1개 주어지므로
• 최소 7개의 correspondances가 필요함.

 

하지만 일반적으로 8개의 correspondances를 이용하는 알고리즘이 주로 사용된다.

---

Practical Implications 

1. 3D Reconstruction:
   • Essential matrix를 사용하여 두 이미지 간의 대응점을 찾고 3D 구조를 재구성할 경우,
   • 절대적인 거리 정보가 부족하여 스케일을 결정할 수 없음.
   • 추가적인 정보(예: 실제 거리 측정값 또는 더 많은 카메라 뷰)가 있어야마 절대적인 스케일을 추정 가능.
2. Applications:
   • 스테레오 비전, 컴퓨터 비전 등의 응용 분야에서 Essential matrix는 중요한 역할을 하지만,
   • 절대적인 거리 추정이 필요할 경우 다른 방법과 결합해야만 함:Triangulation.

결론적으로,

Essential matrix (Fundamental Matrix 포함)는 두 카메라 간의 상대적인 위치와 방향을 제공하지만,

스케일 정보가 포함되지 않아 절대적인 거리를 알 수 없는 상태를 Scale Ambiguity라고 함.

2024.07.04 - [Programming/DIP] - [CV] Triangulation: Simple Version

[CV] Triangulation: Simple Version

 

---

같이보면 좋은 자료

https://darkpgmr.tistory.com/83

[영상 Geometry #7] Epipolar Geometry

https://youtu.be/6kpBqfgSPRc?si=_eBDu6u0bEsB0vsg

 

https://www.robots.ox.ac.uk/~vgg/hzbook/

Multiple View Geometry in Computer Vision<BR>Second Edition

HZepipolar09.pdf

0.25MB

 

---