[cite]http://dx.doi.org/10.1109/34.784291[/cite]

1 Introduction

알고 있는 3D 레퍼런스 지점과 그것의 이미지 위의 지점이 주어졌을 때의 캘리브레이션된 카메라의 위치와 각도를 정하는 문제를 pose estimation 이라고 합니다. 이것은 컴퓨터 비전에서는 고전적인 문제로 3개의 지점이 있다면 풀 수 있다고 알려져 있습니다. 여러가지 알고리즘들이 제안되었고, Fischler와 Bolles의 연구에서 perspective-3-point-problem (P3P)라는 단어를 사용하기 시작했고, 여기에서 n개 점에 대하여 한다는 의미로 PnP라는 표현을 사용하기 시작하였습니다.

많은 수의 점을 사용하는 방법들은 대부분 반복저인 방법을 사용거나 그중 일부를 사용하여 풀이하는 방법을 사용합니다. 반복전인 방법은 초기화와 수렴성의 이슈가 있으며, 대수적으로 푸는 방법의 경우 노이즈의 영향을 많이 받는 문제가 존재합니다.

이 논문에서는 4, 5, n개 지점을 사용하여 카메라 자세를 구하는 알고리즘을 제안합니다. 이는 반복적인 방법을 사용하지 않는다는 점에서 장점을 가진다고 할 수 있습니다.

2 The Camera Pose From Three Points Revisited

캘리브레이션된 카메라 C와 n개의 3D 레퍼런스 지점 $p_i$, 그리고 그것의 이미지 포인트 $u_i$가 있고, 각 대응하는 지점을 $p_i \leftrightarrow u_i $, $p_j \leftrightarrow u_j $라고 합시다. 우리가 알지 못하는 카메라 중심 c로부터의 거리는 $x_i = ||p_i - c|| $, $x_j = || p_j - c || $로 표현될 수 있고, 코사인 법칙에 의하여 다음과 같이 정리할 수 있습니다.

$$d_{ij}^2 = x_i^2 + x_j^2 - 2 x_i x_j \cos \theta_{ij}$$

여기서 $d_{ij}$는 두 레퍼런스 지점 간의 거리, $\theta_{ij}$는 두 지점과 카메라 중심이 이루는 각도를 의미합니다. 이 각도는 다음의 식을 통하여 계산할 수 있습니다.

$$\cos \theta_{ij} = \frac{u_i^T C u_i}{(u_i^T C u_i)^{1/2}(u_j^T C u_j)^{1/2}}$$

여기서 $C=(KK^T)^{-1}$으로 내부 변수 행렬 $K$를 이용하여 계산됩니다.

이 2차 식을 정리하면 다음과 같습니다.

$$f_{ij} (x_i, x_j) = x_i^2 + x_j^2 - 2 x_i x_j \cos \theta_{ij} - d_{ij}^2 = 0$$

점이 3개 이므로 각 쌍에 대하여 3개의 식을 만들 수 있습니다.

$$f_{12}(x_1, x_2) = 0 \\
f_{13}(x_1, x_3) = 0 \\
f_{23}(x_2, x_3) = 0$$

Sylvester resultant를 이용하여 $f_{13}(x_1, x_3)$과 $f_{23}(x_2, x_3)$ 사이에서 $x_3$이 제거된 $h(x_1, x_2)$를 얻을 수 있습니다. 또한 $f_{12}(x_1, x_2) $와 $h(x_1, x_2)$를 이용하면 $x_2$또한 제거된 8차 식을 얻을 수 있습니다. $x = x_1^2$로 치환하고 식을 정리하면 아래와 같습니다.

$$g(x) = a_5 x^4 + a_4 x^3 + a_3 x^2 + a_2 x + a_1 = 0$$

이 식은 x에 대해서 4개의 해를 가집니다. 길이이기 때문에 $x_i$는 양수이고, $x_1 = \sqrt{x}$가 결정됨에 따라 $x_2, x_3$ 또한 계산됩니다.

유일한 해를 얻으려면 1개의 점을 더 추가하여 4개의 점을 사용하면 됩니다. 가장 간단한 방법은 4개의 점 중 3개를 이용하여 식을 푸는 과정을 반복하여 공통적인 해를 선택하면 됩니다. 하지만 같은 계산을 여러번 해야할 뿐더러 공통 해를 골라내는데에도 노이즈의 영향에서 자유로울 수 없습니다.

어쨌든 $x_i$를 구하게 되면 $\hat{p}_i = x_i K^{-1} u_i$를 이용하여 카메라 기준의 3D 좌표를 계산할 수 있습니다.

3 The Linear 4-Point Algorithm

우리의 목표는 많은 점들로부터 생성된 다항식들로부터 직접 해를 구하는 것입니다. 일반적인 선형 다항식의 경우 대수적인 방법으로 Ritt-Wu의 방법을 응용하여 풀곤 하지만 실제로는 연속적으로 항을 소거하는 과정에서 최종 식이 영향을 받아 안정하지 못하는 특징을 갖습니다. 그 대신 여기서는 유일 해가 존재할 때만 답을 주는 numerical linear method를 살펴보고자 합니다.

n개의 점이 주어지면 $f_{ij}(x_i, x_j) $ 꼴의 $ n(n-1) / 2 $개의 2차 식을 생성할 수 있고, 이를 이용하여 $g(x)$와 같은 $ (n-1) (n-2) / 2 $개의 4차 다항식이 만들어집니다. 만약 n=4라면, 4차 다항식은 다음과 같이 생성됩니다.

$$g(x) = a_5 x^4 + a_4 x^3 + a_3 x^2 + a_2 x + a_1 = 0 \\
g(x) = a'_5 x^4 + a'_4 x^3 + a'_3 x^2 + a'_2 x + a'_1 = 0 \\
g(x) = a''_5 x^4 + a''_4 x^3 + a''_3 x^2 + a''_2 x + a''_1 = 0$$

이것은 행렬로 나타낼 수 있습니다.

$$\begin{bmatrix}
a_1 &\ a_2 &\ a_3 &\ a_4 &\ a_5 \\
a'_1 &\ a'_2 &\ a'_3 &\ a'_4 &\ a''_5 \\
a''_1 &\ a''_2 &\ a''_3 &\ a''_4 &\ a''_5
\end{bmatrix}

\begin{bmatrix}
1 \\ x \\ x^2 \\ x^3 \\ x^4
\end{bmatrix}

= A_{3 \times 5} t_5 = 0$$

$$t_5 = (t_0, t_1, ..., t_4)^T = (1, x, ..., x_4)^T$$

A 행렬은 랭크가 최대 3이므로 SVD로 분해하여 나오는 마지막 2개의 singular 벡터를 span하면 A의 null space가 됩니다. 따라서 위 식을 만족시키는 해 $t_5$는 2개의 파라미터를 이용하여 표현할 수 있습니다.

$$t_5 = \lambda v_4 + \rho v_5$$

$t$의 정의에 따라 다음 조건을 만들 수 있습니다.

$$t_i t_j = t_k t_l \text{ for } i + j = k + l,\ 0 \leq i, j, k, l \leq 4$$

이를 만족하는 i,j,k,l은 아래와 같은 경우가 있습니다.

4,2,3,3
4,1,3,2
4,0,3,1
4,0,2,2
3,1,2,2
3,0,2,1
2,0,1,1

이 7가지 경우에 대하여 위의 두 식을 정리하면 아래와 같이 나타낼 수 있습니다.

$$b_1 \lambda^2 + b_2 \lambda \rho + b_3 \rho^2 = 0$$

$$b_1 = v_4^{(i)}v_4^{(j)} - v_4^{(k)}v_4^{(l)} \\
b_2 = v_4^{(i)} v_5^{(j)} + v_5^{(i)}v_4^{(j)} - (v_4^{(k)})v_5^{(l)} + v_5^{(k)}v_4^{(l)}) \\
b_3 = v_5^{(i)}v_5^{(j)} - v_5^{(k)}v_5^{(l)}$$

이들 7개의 식을 행렬의 형태로 나타내면,

$$\begin{bmatrix} b_1 &\ b_2 &\ b_3 \\
b'_1 &\ b'_2 &\ b'_3 \\
\vdots &\ \vdots &\ \vdots \\
b^(6)_1 &\ b^(6)_2 &\ b^(6)_3
\end{bmatrix} \begin{bmatrix} \lambda^2 \\ \lambda \rho \\ \rho^2 \end{bmatrix} = B_{7 \times 3} y_3$$

이 역시 overdetermined 인 식으로 SVD를 이용하여 풀어낼 수 있습니다. 풀어낸 y를 이용하여 $\lambda / \rho $를 구할 수 있습니다. 비율을 알아내면 $t$의 정의에 따라 $1 = \lambda v_4^{(0)} + \rho v_5^{(5)} $에 대입하여 정확한 값을 구할 수 있습니다.

구해진 값을 이용하여 최종적으로 $ x = t_1 / t_0 \text{ or } t_2 / t_1 \text{ or } t_3 / t_2 \text{ or } t_4 / t_3 $ 를 구할 수 있습니다. 마지막으로 $ x = x_i^2 $이므로 $x_i = \sqrt{x}$입니다.

이렇게 4개의 점만으로 카메라 자세를 구할 수 있게 되었습니다. 이 방법은 4개나 4개 이상의 coplanar 지점을 사용하더라도 크게 문제가 없음을 볼 수 있습니다.

4 The Linear Five and n-point Algorithms

5개의 점을 이용한 경우에는 6개의 4차 식을 만들어낼 수 있습니다.

$$A_{6 \times 5} t_5 = 0$$

따라서 SVD를 이용하여 바로 해를 구할 수 있습니다. 5개 보다 더 많은 점에 대해서도 마찬가지로 계산이 가능해집니다.

5 Outline of the Algorithms

알고리즘을 정리하면 다음과 같습니다.

1. 데이터 전처리 : 점들 간 거리 $d_{ij} = || p_i - p_j ||$를 계산하고 그 $ \cos \theta_{ij} $를 계산합니다.
2. 레퍼런스 점들의 거리 계산 : $ At = 0 $ 식을 만들어 SVD를 이용하여 계산합니다.
3. 레퍼런스 점의 깊이로부터 카메라의 방향과 위치를 계산합니다.

6 Experimental Results

6.1 The Linear 4- and 5-Point Algorithm

길이 200을 갖는 큐브 내에 무작위로 3D 점을 생성하고 그 중에서 4개나 5개의 지점을 사용하여 계산을 하였습니다. 100개의 카메라 자세를 만들어냈고, 각 카메라 자세에서 100 세트의 점들을 생성하였습니다. 점들의 위치는 가우시안 노이즈를 포함하도록 하였습니다.

에러의 계산은, $ 2 |\ t_i - t || / (|| t_i|| + ||t||) $ 와 $ R_i R^T$의 오일러 각들의 절대값을 더하는 것으로 계산하였습니다. 그리고 이들 에러의 median, mean, 표준 편차를 표시하였습니다. 5점 계산 방법이 4점 보다 좋은 성능을 보여주었습니다.

6.2 The Linear 4-point Versus the Special Linear Algorithm for Coplanar Points

coplarnar 점들에 대해서는 4점 방식이 special linear 방법과 동일한 성능을 나타내는 것으로 보였고, quasicoplanar 환경에서는 오히려 더 좋은 성능을 나타내었습니다.

---