[cite]10.1109/ICCV.2007.4409116[/cite]

1. Introduction

PnP (Perspective-n-Point) 문제의 목적은 카메라의 위치와 방향을 구하는 것입니다. 이 때, 내부 변수와 n개의 서로 대응하는 2D 점과 3D 점 쌍들이 주어져야 합니다. 여기서는 비반복적(non-iterative) 방법으로 더 정확하고 계산복잡도가 적은 방법을 제안하고 있습니다. 당연히 반복적인 방법보다 더 빠름은 물론입니다. 기본의 방법들은 같은 수준의 정확도를 얻고자 할 경우 $O(n^5)$이나 $O(n^8)$의 복잡도를 가지지만, 이 방법은 $ n \geq 4 $일 경우 $O(n)$의 복잡도를 갖습니다.

이 방법의 아이디어는 주어진 n개의 3D 점 좌표를 4개의 가상 제어점(virtual control point)의 가중치 합으로 표현하는 것입니다. 이것을 통하여 직접적으로 점 좌표를 계산하기 보다는 가상 제어점을 계산하는 문제로 줄여주어 $O(n)$ 복잡도로 계산하는데 핵심적인 역할을 하게 됩니다.

2. Related Work

자세 추정(pose estimating)에 관한 많은 연구들이 있지만 여기서는 비반복적 접근법에만 집중해도록 합니다. 많은 비반복적 방법은 먼저 카메라 좌표계 기준에서의 3D 좌표를 추정하는 것으로 시작하고 다음 카메라 위치와 방향을 계산합니다. P3P의 경우에는 8차 다항식을 풀어야 하고 4개의 답을 얻어지기에 이 disambiguation을 풀어내기 위해서는 일반적으로 4개의 점이 필요합니다.

또한 4개의 점으로 문제를 풀어내는데 충분하더라도 노이즈에 대한 민감도를 줄이기 위해서 더 많은 점을 활용하고자 합니다. Quan과 Lan의 방법은 $(n-1)(n-2) / 2 \times 5$개의 4차 식을 꾸민 뒤, SVD(singular value decomposition)을 이용하여 $O(n^5)$의 복잡도로 점의 좌표를 구해냅니다. 또한 Ansar와 Daniilidis의 방법의 경우 $O(n^8)$의 복잡도를 이용하여 더 정확한 결과를 얻어내고자 하였습니다. 위의 두 방법은 두 점 사이의 거리를 제한조건으로 이용하여 계산이 복잡하기에 Fiore는 이를 무시할 수 있는 계산법을 찾아내어 $O(n^2)$까지 빠른 방법을 제안하였습니다.

여기에서는 비선형적 제한조건을 통하여 $O(n)$의 계산만이 필요한 방법을 제안하였습니다. 그러면서도 오히려 더 정확한 결과를 보여주었습니다. 이 방법은 호모그래피를 구하는 Direct Linear Transformatino (DLT) 방법과 비슷하기도 하지만 내부 변수를 이용한다는 점에서 차이가 있습니다.

3. Our Approach to the PnP Problem

레퍼런스 점들의 월드 좌표계에서의 3D 좌표와 그 프로젝션의 2D 좌표를 안다고 하여봅시다. 많은 연구들은 카메라 좌표계에서 레퍼런스 점의 거리를 이용하고 있습니다. 하지만 여기에서는 그 좌표들을 가상 제어점들의 가중치 합으로 표현하고자 합니다. 여기서는 일반적인 경우 4개의 non-coplanar가 필요하며, planar 환경에서는 3개의 지점만 있으면 됩니다. 주어지는 식으로터 가상 제어점의 좌표가 우리가 풀어야 할 미지수가 됩니다. 많은 n이 주어지는 상황일수록 기존의 n개 점에 대해 계산하는 방법보다 이렇게 가상 제어점을 이용하여 계산하는 방법이 미지수의 수가 상대적으로 작아지게 되므로 계산 속도 개선의 핵심적인 사항이 됩니다.

미지수의 해는 3D 점과 그 2D 투영 점을 이용하여 만들어진 2n 12 혹은 2n 9 크기의 행렬로 표현할 수 있습니다. 이 행렬을 M이라고 합니다. 해는 M의 null eigenvector의 가중치 합으로 표현할 수 있습니다. 기타 여러 계산들이 더 있지만 사실 n이 커질 수록 영향을 받는 부분은 $M^T M$을 구하는 계산으로 이는 n이 늘어날 수록 선형적으로 증가합니다.

3.1 Parameterization in the General Case

이제 n개 3D 점을 $p_i$ 라고 표현합시다. 그리고 4개의 가상 제어점을 $ c_j$라고 표현하여 봅시다. 필요할 경우, 월드 좌표계일 경우 $^w$를, 카메라 좌표계일 경우 $^c$를 사용할 것입니다.

정의에 따라 3D 점은 다음과 같이 가상 제어점의 가중치 합으로 표현할 수 있습니다.

$$P_i^w = \sum_{j=1}^4 \alpha_{ij}c_j^w, \ \sum_{j=1}^4 \alpha_{ij} = 1$$

카메라 좌표계에서도 같은 표현이 성립합니다.

$$P_i^c = \sum_{j=1}^4 \alpha_{ij}c_j^c, \ \sum_{j=1}^4 \alpha_{ij} = 1$$

이론적으로 가상 제어점은 어느 지점이라도 상관이 없으나, 안정적인 계산을 위해서는 레퍼런스 지점들의 중심점을 가상 제어점 중 하나로 놓고, 나머지는 데이터의 주축(principal direction)들에 대한 점들로 정하는 것이 좋은 것을 알아냈습니다. 이는 기존의 DLT 알고리즘에서도 추천되는 normalization 방법입니다.

3.2 The Solution as Weighted Sum of Eigenvectors

이제 레퍼런스 점의 2D 좌표를 이용하여 행렬 M을 유도해 내고자 합니다. A를 카메라의 내부 변수라고 하고 $u_i$를 $p_i$의 2D 프로젝션이라고 합시다. 이제 우리는 다음을 얻습니다.

$$w_i \begin{bmatrix} \bf{u}_i \\ 1 \end{bmatrix} = A p_i^c = A \sum_{j=1}^4 \alpha_{ij} c^c_j$$

여기서 $w_i$는 scalar projective 파라미터입니다.

이를 풀어내면 다음과 같이 됩니다.

$$w_i \begin{bmatrix} u_i \\ v_i \\ 1 \end{bmatrix} = \begin{bmatrix} f_u &\ 0 &\ u_c \\ 0 &\ f_v &\ v_c \\ 0 &\ 0 &\ 1 \end{bmatrix} \sum_{j=1}^4 \alpha_{ij} \begin{bmatrix} x_j^c \\ y_j^c \\ z_j^c \end{bmatrix}$$

미지수는 가상 제어점에 대한 수 12개와, 각 점에 대한 파라미터 n개가 됩니다.

마지막 행에 대한 계산을 하면 $w_i = \sum_{j=1}^4 \alpha_{ij} z_j^c $ 이 되며, 이를 첫번째, 두번째 행 계산에 대입하면 다음 두 식을 얻습니다.

$$\sum_{j=1}^4 \alpha_{ij} f_u x_j^c + \alpha_{ij} (u_c - u_i) z_j^c = 0$$

$$\sum_{j=1}^4 \alpha_{ij} f_v y_j^c + \alpha_{ij} (v_c - v_i) z_j^c = 0$$

이제 각 점에 대한 $w_i$는 제거되었습니다. n개의 점에 대한 위 식을 토대로 $Mx=0$ 행렬식을 꾸밉니다. 여기서 $x = [{c_1^c}^T, {c_2^c}^T, {c_3^c}^T, {c_4^c}^T ]^T $ 으로 미지수 행렬입니다.

M은 2n * 12 크기의 행렬로, 위의 두 식의 계수들을 담고 있습니다.

해 x는 M의 null space에 포함되므로 다음과 같이 표현할 수 있습니다.

$$x= \sum_{i=1}^N \beta_i v_i$$

여기서 $v_i$는 M의 오른쪽 i번째 singular vector입니다. 이것은 $M^TM$의 null eigenvector로 계산할 수 있으며, 12 * 12의 고정된 크기를 갖습니다. $M^TM$을 계산하는 것은 $O(n)$의 계산복잡도를 가지며, 대부분의 계산 시간을 차지합니다. n이 15정도 되면 충분한 크기입니다.

3.3 Choosing the Right Linear Combination

이론 상으로 6개의 점이 주어질 경우, 위의 식에서 $ M^T M $은 null space의 차원은 scale ambiguity에 해당하는 1이 될 것이지만 노이즈 때문에 때때로 0이나 아주 작은 값을 갖는 eigenvalue가 찾아지지 않을 때도 있습니다.

따라서 여기서 가상 제어점 사이의 거리들이 유지되어야 효과적으로 $\beta_i, \ N=1,2,3,4$를 계산할 수 있다는 점을 이야기하고자 합니다. 이것은 $N \geq 5 $인 경우에까지 확장될 수 있습니다.

일단 eigenvalue들이 비슷한 값들을 가질 경우 얼마만큼의 eigenvector를 쓸 것인지의 N을 단순히 결정하는 것은 오류를 내기 쉽기 때문에, 그 대신 일단 $N=1,2,3,4$에 대한 해를 모두 구하고, 그 중 가장 작은 리프로젝션 에러를 가지도록 유지합니다.

$$res = \sum_i \text{dist}^2(A[R|t]\begin{bmatrix} c_i^w \\ 1 \end{bmatrix}, u_i)$$

여기서 dist는 2D 거리를 이야기합니다.

사실 이것은 별다른 계산 패널티 없이 진행되는데, $M^T M $의 계산에서 대부분의 시간이 소요되고 그 뒤의 계산은 약간의 이차식 정도만 풀면 되기 때문입니다. 각각의 경우에 대한 설명은 논문을 참고하도록 합시다.

3.4 The Planar Case

Planar 인 경우, 3개의 제어 점만 있으면 됩니다. M과 eigenvector v의 차원은 줄어들게 됩니다. 가장 큰 차이점은 quadratic constraints가 6에서 3으로 줄어드는 것입니다.

4 Results

합성 이미지와 실제 이미지의 실험을 진행하였으며, 합성 이미지의 경우 non-planar와 planar case를 따로 실험하였습니다.

---