일반적으로 하나의 사진 만으로는 사진 속 객체의 위치 또는 카메라의 위치를 알아내기 위한 정보가 부족하다. 하지만 다른 시점으로 이동하여 촬영한 사진들이나 여러 대의 카메라에서 촬영된 사진들이 주어진다면, 객체의 위치 또는 카메라의 위치를 추론할 수 있다. 이를 위하여 각 영상 간의 관계 등에 대한 제한 조건(constraint) 등을 활용한다.

Figure 1. Epipolar geometry

위의 그림과 같은 epipolar에 대한 기본적인 설정이며, 여기서 $\mathbf{O},\mathbf{O'}$은 두 카메라의 원점, $\mathbf{P}$는 객체, $\mathbf{x}, \mathbf{x'}$는 객체가 두 영상에서 투영된 위치를 의미한다. 그리고 두 원점 $\mathbf{O},\mathbf{O'}$을 연결한 선을 baseline, baseline이 각 image plane과 만나는 점(어떤 카메라 영상에 투영된 반대편 카메라의 위치)을 epipole, $\mathbf{O},\mathbf{O'},\mathbf{P}$가 이루는 평면을 epipolar plane, epipolar plane과 각 image plane이 만나 생성되는 직선을 epipolar line($\mathbf{l},\mathbf{l'}$)이라고 한다. 이때, $\overline{\mathbf{O} \mathbf{P}}$ 상의 모든 점은 $\mathbf{x}$에 투영되므로, 왼쪽의 첫번째 영상($\mathbf{O}$)에서 $\mathbf{x}$만 가지고 $\mathbf{P}$의 정확한 위치를 추론할 수 없다. 하지만 두번째 영상에 투영된 $\mathbf{x'}$를 이용하면, $\overline{\mathbf{O} \mathbf{P}}, \overline{\mathbf{O'} \mathbf{P}}$의 교점을 통해 $\mathbf{P}$의 위치를 알 수 있으며, $\overline{\mathbf{O} \mathbf{P}}$ 상의 모든 점은 두번째 카메라($\mathbf{O'}$)의 epipolar line, $\mathbf{l'}$상에 투영된다.

1. Epipolar Constraint

위의 그림에서 알 수 있듯이, $\mathbf{O},\mathbf{O'},\mathbf{P}$과 더불어 모든 epipole, epipolar line은 하나의 평면상에 존재하며, 이러한 성질이 epipolar contraint를 구성한다. 먼저, 객체 $\mathbf{P}$가 투영된 점 $\mathbf{x}$는 epipolar line $\mathbf{l}$위에 있으므로 이를 이전 글처럼 homogenous coordinate로 표현하면 다음과 같다.

다만, 위의 표기에서 $\mathbf{x}$는 카메라 그리고 두 카메라 원점을 연결한 선 $\overline{\mathbf{O} \mathbf{O'}}$를 나타내는 벡터를 $\mathbf{b}$라고 하고, 해당 직선과, 투영된 점 $\mathbf{x}, \mathbf{x'}$가 한 평면위에 있다는 점을 사용하면 다음과 같은 contraint도 구성이 가능하다.

두 벡터의 외적은 두 벡터가 그리는 평면에 수직이므로 위의 contraint가 성립하며, 벡터의 외적은 위와 같이 skew-symmetric 행렬을 통해 행렬-벡터 곱으로 표현이 가능하다

2. Essential & Fundamental Matrix

Essential & fundamental matrix는 Fig.1과 같은 환경에서 두 영상 간의 관계를 나타내는 행렬이며, 위의 epipolar contraint에서 유도될 수 있다.

먼저, 두 카메라 간 회전행렬을 $\mathbf{R}$, translation(baseline)을 $\mathbf{b}$라고 하면, $\mathbf{x'}=\mathbf{R}(\mathbf{x}-\mathbf{b})$가 성립하고, epipolar constraint에서 $\mathbf{x} \cdot(\mathbf{b} \times \mathbf{x})=0 \rightarrow \mathbf{x} \cdot(\mathbf{b} \times (\mathbf{x}-\mathbf{b}))=\mathbf{x}^T\hat{\mathbf{b}}(\mathbf{x}-\mathbf{b})=0$임을 알 수 있다. 두 식을 결합하면 다음과 같이 정리할 수 있다.

여기서 $\hat{\mathbf{b}}\mathbf{R}^{T}$를 essential matrix $\mathbf{E}$라고 하며, 위의 또다른 contraint $\mathbf{x}^T\mathbf{l}=0$를 이용하면 $\mathbf{x'}^T\mathbf{l'}=\mathbf{x'}^T(\hat{\mathbf{b}}\mathbf{R}^{T})\mathbf{x}=\mathbf{x'}^T\mathbf{E}\mathbf{x}=0$이므로, $\mathbf{l'}=\mathbf{E}\mathbf{x}$이라고 할 수 있다(반대로 $\mathbf{l}=\mathbf{E}\mathbf{x'}$이기도 함). 즉, essential matrix를 통해 frame 1에 투영된 점 $\mathbf{x}$를 통해 반대편 frame 2에 생성되는 epipolar line을 찾을 수 있다는 것을 의미한다. 추가적으로 epipole $\mathbf{e}$은 epipolar line 위에 존재하므로, $\mathbf{e}^T\mathbf{E}=\mathbf{E}\mathbf{e'}=0$이 성립한다.

여기서 주목해야하는 점은 사용된 행렬과 벡터들이 표현된 좌표계이다. 우선 $(\mathbf{x}, \mathbf{l}), (\mathbf{x'}, \mathbf{l'})$은 각각 $\mathbf{O}, \mathbf{O'}$의 카메라 좌표로 표현되었으며, 3D이다(homogeneous coordinate로 표현하면 원소가 4개, image 좌표계가 아님). $\mathbf{R}, \mathbf{b}$의 경우 frame 1를 기준으로 나타낸 frame 2의 상대적인 회전, 이동 행렬이다. 즉, world 좌표의 중심이 $\mathbf{O}$에 있다고 보고, $\mathbf{E}$는 두 frame의 상대적인 변환 행렬로 구성된 것이라고 할 수 있다.

하지만, 실제로 우리가 데이터를 수집할 때 얻게 되는 정보는 2차원의 영상이며 이는 image 좌표계에서 표현된다. 만약 카메라의 intrinsic parameter를 알고 있다면 image 좌표계에서 camera 좌표를 알아 낼 수 있지만, 그렇지 않다면 위의 식을 다음과 같이 정리하여 image 좌표에 대한 식으로 쓸 수 있다.

여기서 $\mathbf{F}$를 fundamental matrix라고 하며, essential matrix와 비슷하게 $\mathbf{l'}=\mathbf{F}\mathbf{x}$, $\mathbf{e}^T\mathbf{F}=\mathbf{F}\mathbf{e'}=0$이 성립한다(단, image 좌표계임에 주의). 또한 $\mathbf{F}$는 skew-symmetric의 성질을 활용하여 다음과 같이 다양한 형태로 쓸 수 도 있다.

두 epipole $\mathbf{e}, \mathbf{e'}$은 서로 반대편의 카메라 중심이 투영된 지점이다. $\mathbf{e}$의 경우 반대편 카메라 중심 $\mathbf{O'}$가 투영된 점이므로 frame 1의 시점에서 $\mathbf{O'}$의 좌표 $\mathbf{b}$를 투영하면 $\mathbf{e}=\mathbf{K}\mathbf{b}$가 되며 ($\mathbf{O}$를 world 좌표의 중심처럼 생각하므로 회전이 없음), $\mathbf{e'}$의 경우 원점에 있는 $\mathbf{O}$를 $\mathbf{P'}=\mathbf{K'}(\mathbf{R}|-\mathbf{R}\mathbf{b})$를 통해 투영하므로 $\mathbf{e'}=\mathbf{K'}\mathbf{R}\mathbf{b}$가 된다. 따라서 위의 fundamental matrix 표현식 중 일부를 다음과 같이 쓸 수 있다.

Homogeneous coordinate에서 두 점 $\mathbf{e}, {\;}^i\mathbf{x}$를 지나는 직선은 $\mathbf{l}=\mathbf{e} \times {}^i\mathbf{x}=\hat{\mathbf{e}}{\;}^i\mathbf{x}$로 쓸 수 있으며, 이 직선은 epipolar line이다. 따라서 fundamental matrix을 사용하면 epipolar line은 $\mathbf{l}=\hat{\mathbf{e}}{\;}^i\mathbf{x}=\mathbf{F}{\;}^i\mathbf{x'}$인데, $\mathbf{F}=\widehat{\mathbf{e}}\mathbf{K}\mathbf{R}^{T}\mathbf{K'}^{-1}$이므로, $\hat{\mathbf{e}}{\;}^i\mathbf{x}=\widehat{\mathbf{e}}\mathbf{K}\mathbf{R}^{T}\mathbf{K'}^{-1}{\;}^i\mathbf{x'}$가 되어 $\mathbf{K}\mathbf{R}^{T}\mathbf{K'}^{-1}$가 ${\;}^i\mathbf{x'}$를 ${\;}^i\mathbf{x}$로 매핑하는 homography라고 할 수 있다.

또한 $\mathbf{K}, \mathbf{K'}, \mathbf{R}$은 rull rank이고, $\widehat{\mathbf{e}}$는 rank가 2이므로, $\mathbf{F}=\widehat{\mathbf{e}}\mathbf{K}\mathbf{R}^{T}\mathbf{K'}^{-1}$에서 fundamental matrix $\mathbf{F}$의 rank는 2가 됨을 알 수 있다.

이를 보이기 위해 $\mathbf{A}$가 $K \times L$행렬이고, $\mathbf{B}$가 $L \times L$인 full rank 정방행렬이라면, rank($\mathbf{A}\mathbf{B}$)=rank($\mathbf{A}$)이라는 성질을 사용하면 되는데 이에 대한 증명은 이전 글에 있다.

3. 8 Points Algorithm

만약 두 카메라의 내/외부 파라미터를 모두 알고 있다면 위의 식을 통해 essential & fundamental matrix를 구할 수 있다. 하지만 많은 경우 모든 파라미터를 알고 있기 어렵기때문에 DLT와 비슷한 방식으로 몇 개의 corresponding points를 통해 essential & fundamental matrix를 계산한다. 이때, corresponding points란 다음 그림과 같이 두 frame에서 하나의 scene을 촬영했을 때 나타나는 공통된 지점에 대한 point들의 쌍이다.

Figure 2. Correspondence points

만약, fundamental matrix를 구한다고 하였을 때, 우리는 corresponding points를 통해 $\mathbf{{}^{i}x}, \mathbf{{}^{i}x'}$을 알 수 있으며, 이를 통해 다음과 같은 식을 세울 수 있다.

위의 식을 풀어 정리하면 DLT 방법과 같이 $\mathbf{AF=0}$ 형태로 쓸 수 있으며, 다음과 같다.

9개의 $F$들을 알아내기 위하여 최소 8개의 점이 필요하며, 더 많은 점을 사용할 경우 RANSAC 방법 등의 적용도 고려할 수 있다. 위 식의 풀이는 DLT와 마찬가지로 SVD를 사용하며, 가장 작은 특이점에 대응되는 오른쪽 특이 벡터를 해로 사용한다.

다만 위에서 보았듯이 fundamental matrix $\mathbf{F}$는 rank가 2라는 조건이 있으므로 이러한 조건을 만족하도록 해줘야하며, 이 글에서 보았듯이 가장 큰 2개의 특이값 만을 선택하여 rank-2 근사를 할 수 있다. 따라서 종합적으로 다음과 같은 과정을 통해 8 point algorithm이 수행된다.

Figure 3. 8 point algorithm의 과정

4. Recover Relative Orientation

Essential matrix의 경우에도 위와 비슷한 방법으로 구할 수 있으며, 이때 사용되는 $\mathbf{x_n}$들은 image 좌표가 아니라 투영된 점을 카메라 좌표(3D)로 표현한 것이다.

Essential matrix 또한 위와 마찬가지로 식을 구성하여 SVD를 적용하면 1차적으로 해를 찾을 수 있다. Fundamental matrix의 경우 여기에 rank=2라는 constraint를 적용하였지만, essential matrix의 경우 다른 constraint를 적용해야한다.

Essential matrix의 constraint는 SVD를 했을 때 나타나는 3개의 특이값($3 \times 3$ 행렬이므로)중 앞의 두 개는 동일하고, 나머지 하나는 0이라는 것이다. 이러한 성질은 essential matrix $\mathbf{E}=\hat{\mathbf{b}}\mathbf{R}^{T}$에 있는 skew-symmetry 행렬에 의한 것으로, 이전 글에 있듯이 skew-symmetry($3 \times 3$ 행렬)는 $\hat{\mathbf{b}}=k\mathbf{U}\mathbf{Z}\mathbf{U}^T$로 분해된다(이때, $\mathbf{U}$는 orthogonal). 이때, $\mathbf{Z}=diag(1,1,0)\mathbf{W}$이고, 이를 종합하면 essential matrix는 $\mathbf{E}=\hat{\mathbf{b}}\mathbf{R}^{T}=\mathbf{U}diag(1,1,0)(\mathbf{W}\mathbf{U}^T\mathbf{R}^{T})$로 쓸 수 있다. 여기서 $\mathbf{U}, \mathbf{W}\mathbf{U}^T\mathbf{R}^{T}$가 orthogonal하므로 이 정리식을 essential matrix의 SVD 분해식으로 볼 수 있고, essential matrix의 특이값이 1,1,0임을 알 수 있다. 이러한 constraint는 다음과 같이 적용하여 최종적인 essential matrix를 구할 수 있다.

Figure 4. Essential matrix 구하는 과정

여기서 주목할 점은 essential matrix에서 카메라의 변환과 관련된 $\mathbf{R}, \hat{\mathbf{b}}$를 복원할 수 있다는 점이다.

이때, $\mathbf{Z},\mathbf{W}$에 대해서 다음과 같은 여러개의 조합이 존재한다.

따라서 $\mathbf{R}, \hat{\mathbf{b}}$에 대해서도 $\mathbf{R}=\mathbf{U}\mathbf{W}\mathbf{V^T},\mathbf{U}\mathbf{W^T}\mathbf{V^T}$와 $\hat{\mathbf{b}}=\mathbf{U}\mathbf{Z}\mathbf{U^T},\mathbf{U}\mathbf{Z^T}\mathbf{U^T}$의 해가 존재하며, $\mathbf{R}, \hat{\mathbf{b}}$의 조합으로 생각하면 총 4가지의 조합이 가능하다. 여기에 $det(R)=1$이라든지, 여러 점에 대해서 triangulation을 적용했을때 나온 포인트의 위치가 가능한 위치인지(잘못된 값이라면 계산된 포인트의 위치가 카메라 뒤로 나올 수 도 있음)등 여러가지 실험을 수행하여 4개 중 하나를 선택한다.

Figure 5. 가능한 네 가지 조합과, valid한 해

추가적으로 8 points algorithm 계산 시, 수치적인 안정성을 위해 $\mathbf{x}$들을 -1과 1사이의 값으로 normalization 하는 경우가 있다. 예를 들어 fundamental matrix의 경우 $\mathbf{T}:\mathbf{T}\mathbf{{\;}^ix}=\mathbf{{\;}^i\bar{x}}$라는 transformation $\mathbf{T}$를 사용하여 normalization한다고 가정하면 다음이 정리할 수 있다(Essential matrix의 경우도 비슷한 전개를 사용할 수 있음).