1. Introduction

이전 강의 노트에서는 epipolar geometry를 통해 현실에서 하나의 3D point가 두 이미지 평면에서 각각 어떤 위치에 투영되는지의 관계를 나타낼 수 있다는 것을 배웠다.
즉, 3D 정보 없이도 두 이미지 평면간의 관계를 알아 낼 수 있다는 것이다.
이번 강의 노트에서는 이를 이용해 여러 장의 2D 이미지로부터 3D 정보를 복원하는 방법에 대해 다루고 있다.

2. Triangulation (삼각측량)

multiple view geometry에서 가장 기본적인 문제는 바로 triangulation(삼각측량)이다.
삼각측량은 말 그대로 동일한 3D point($P$)가 투영된 2장 이상의 이미지로부터 실제 $P$의 위치를 복원하는 것이다.

이를 $P$를 알기 위해서는 두 카메라의 intrinsic parameter($K, K'$), 두 카메라간의 상대적인 회전 및 이동 정보($R, T$)가 필요하다.
카메라의 중심($O_1, O_2$)으로 부터 $P$가 이미지 평면에 투영된 점 $p, p'$를 향한 ray($l, l'$)를 쏠 경우, 이 ray는 한 점에서 교차하게 되며 이 점이 $P$가 된다.
이를 통해 임의의 3D scene의 위치 정보를 좌표계로 나타낼 수 있게 된다. (3D 정보 복원)

이는 매우 간단해보이지만, 사실 현실에서는 카메라의 parameter 정보에는 오차가 있고, 투영된 점 $p, p'$에도 오차가 발생할 수 있어 두 ray가 교차하지 않을 수 있다.

2.1 A linear method for triangulation

선형 방정식을 통해 두 ray가 교차하지 않는 문제를 해결해 볼 수 있다.

$p$는 3D ponit $P$가 카메라의 변환 행렬 $M$에 의해 변환된 결과이므로 $p, p'$를 각각 다음과 같이 정의할 수 있다.

$p = MP = (x, y, 1)$
$p' = M'P' = (x', y' 1)$

동일한 벡터를 cross product하면 영벡터가 되므로 다음과 같은 제약식을 세울 수 있다.

$p \times (MP) = [y(M_3P) - M_2P, M_1P - x(M_3P), x(M_2P) - y(M_1P)] = 0$

참고 - Cross_product#Computing

위 제약식을 이용하여 $AP = 0$으로 만드는 어떠한 변환 행렬 $A$를 다음과 같이 정의할 수 있다.

식 2.2는 두 카메라의 변환 행렬($M, M'$)과 투영된 점의 위치($p, p'$)만으로 A를 구할 수 있음을 나타내며,
이후로는 SVD를 통해 $AP=0$이 되도록하는 최적의 $P$를 찾는 linear estimate 문제를 통해 $P$ 정보를 복원할 수 있다.

하지만 이 선형방정식을 이용한 방법은 projective-invariant(투영불변)하지 않다는 문제가 있다.

projective-invariant는 말 그대로 투영 변환에 대해 불변하다는 의미인데, 카메라의 변환 행렬 $M$에서 투영 변환의 영향을 제거하기 위해 $MH^{-1}$으로 식을 변경할 경우 아래와 같이 방정식이 바뀐다.

$(AH^{-1})(HP) = 0$

SVD에서는 $\|P\| = 1$이 되어야 하는데, P의 scale이 투영 변환 $H$에 의해 변하게 되므로 투영 변환된 공간에 대해서는 적용할 수 없다.

즉 이 방법은 간단하지만, 대부분의 상황에서 적용할 수 없다는 문제가 있다.

2.2 A nonlinear method for triangulation

최적의 $\hat{P}$를 찾는 문제를 다시 정의해보면, $\hat{P}$를 이미지 평면에 재투영했을 때 $p, p'$와의 거리(reprojection error)를 최소화하는 문제로 볼 수 있다. (식 2.3)

이미지가 2장 이상으로 늘어나도 단순히 각 이미지의 거리를 합하는 방식으로 적용이 가능하다. (식 2.4)

이 minimization 문제를 풀기 위한 세련된 접근법이 많이 존재하지만, 이번 강의 노트에서는 Gauss-Newton algorithm 하나만을 다룰 것이다.

일반적인 $x \in \mathbb{R}^n$에 대한 nonlinear least squares problem은 다음과 같이 나타낼 수 있다.

$r$은 $r(x) = f(x) - y$ input $x$를 사용한 function $f$와, 관측값 $y$와의 잔차를 계산하는 residual function이다.

함수 $f$가 linear하다면 이 문제를 linear least square problem으로 간소화 할 수 있다.
그러나 일반적으로 homogeneous 좌표를 사용할 경우 $p = (x, y, w)$와 같은 꼴이며 이를 이미지 좌표로 변환할 때 $w$로 나누어주는 과정이 포함되므로 $f$가 nonlinear이다.
즉, linear least square로 표현할 수 없다.

이러한 문제를 해결하기 위해 2 x 1 크기의 벡터 $e_i = M\hat{P}_i - p_i = (\hat{x}-x, \hat{y} - y)^T$ 를 적용하여 최적화 문제를 다음과 같이 변경하여 나타낼 수 있다.

위 식 2.6이 최적의 3d point $\hat{P}$를 찾기 위한 least squares problem을 완벽히 나타낸 표현이다.

이제 이 문제를 Gauss-Newton 알고리즘을 통해 어떻게 풀 수 있는지 알아볼 것이다.
Gauss-Newton 알고리즘은 현재의 예측값($\hat{P}$)의 에러를 최소화 하는 쪽으로 보다 나은 예측값으로 업데이트 하는 것을 목표로 한다.

알고리즘의 각 스탭마다 $\delta_P: \hat{P} = \hat{P} + \delta_P$의 업데이트가 발생한다.
여기서 중요한 것은 $\delta_P$를 선택하는 것인데, Gauss-Newton 알고리즘의 핵심 아이디어는 현재의 예측값 $\hat{P}$ 근처의 residual function의 선형 근사치를 찾는 것이다(linearize)

이 문제의 경우 오차를 미분하여 오차의 변화율을 구하는 것을 통해 오차를 선형적으로 근사하는 단계를 적용할 수 있다.

위 식을 통해 업데이트가 된 예측치의 오차를, 기존 예측치의 오차와 오차의 변화율 $\times$ 변화량의 합으로 근사하였다.

이제 minimization proble을 다음과 같이 바꾸어 표현할 수 있다.

$\underset{\delta_P}{min} \| e(\hat{P} + \delta_P) \|$

↓

이렇게 잔차를 정의하는 것을 통해 standard linear least squeares problem으로 문제를 표현할 수 있다.

N개의 이미지에 대해, linear least squares solution은 다음과 같다.

사실 이부분을 전혀 이해하지 못했다..
Gauss-Newton Method에 대한 내용이라 이 부분은 별도로 공부하도록 하자.

결론적으로 e는 (N $\times$ 1) 벡터이며, 이미지가 2개인 가장 단순한 경우에 e는 2 $\times$ 1 벡터가 된다.

또한, $\delta_P$를 계산하여 업데이트 하는 것을 $e(\hat{P})$가 수렴할 때 까지 단순히 반복하는 것을 통해 $\hat{P}$를 최적화 할 수 있다.

정리

이렇게 두 개 이상의 이미지로부터 3D 정보를 복원하는 방법에 대해 알아 보았다.

이 방법은 각 카메라의 intrinsic parameter와 카메라간의 상대적인 회전 및 이동을 알고 있을 때 적용할 수 있다.

하지만 실제로는 이 정보가 주어지지 않는 경우가 많다.
때문에 다음 게시글에서 다룰 강의 노트의 나머지 부분에서는 multi view 이미지로부터 3d scene의 구조와 camera parameter를 동시에 복원하는 structure from motion에 대해 배울 것이다.