An Efficient Solution to the Five-Point Relative Pose Problem
1. Introduction
씬의 구조와 카메라 위치의 복원을 위해서 J. Philip은 그의 연구에서 5개의 점을 이용하여 13차의 다항식을 구성한 뒤 그 해를 이용하는 방법을 제안하였다. 이 논문은 그것을 다듬은 것이다. 더 좋은 소거법을 사용함으로써 닫힌 형태의 10차 다항식을 만들어낼 수 있었다.
더 강인하고 정확한 답을 얻기 위해서 5개가 넘는 점을 활용할 수 있다. 전통적인 방법으로는 모든 점에 대해서 리스트 스퀘어를 구하여 이를 최소화하는 방법이 있을 수 있으나 여기서는 RANSAC 내에서 5점 알고리즘을 가설로 사용하여, 가장 좋은 가설을 계속적으로 갱신해가는 식이다.
2. Preliminaries and Notation
3. The Five-Point Algorithm
5개의 대응점에 대해서 에피폴라 제한 $ q'^T E q = 0 $을 이용하여 다음 식을 만들 수 있다.
$$ \tilde{q}^T \tilde{E} = 0 $$
여기서 $\tilde{q}^T$ 는 모든 5개의 점을 벡터로 쌓은 것으로 5 x 9의 크기를 갖는다. 여기서 $E$를 4개의 벡터 $X, Y, Z, W$로 이루어지는 널스페이스로 표현한다. 보통 이를 구하기 위한 방법으로는 SVD를 생각할 수 있지만 여기서는 QR-factorisation이 더 효율적이었다.
$$ E = xX + yY + zZ + wW $$
4개의 스칼라는 공통된 스칼라 팩터에서 정의되므로 $w=1$라고 가정할 수 있다. 따라서 알고리즘은 5점 이상의 점을 사용할 경우로 확장될 수 있으며 이 경우 가장 작은 특이값을 사용하면 될 것이다. 위의 식을 $ EE^T E - 1/2 \text{trace}(EE^T) E = 0$에 삽입한 뒤, Gauss-Jordan 소거법을 사용한뒤 정리하면 $x, y, z, w$를 계산할 수 있게 된다.
3.1 Recovering R and t from E
E에서 추출할 수 있는 R은 $R_a = UDV^T$와 $R_b = UD^T V^T$ 두가지, $t \sim t_u \equiv [u_{13}, u_{23}, u_{33} ]^T $ 이기에 이들 중 어느것을 조합하여도 에피폴라 제한을 만족한다. 이러한 모호성을 해결하기 위해 첫번째 카메라 행렬을 $[I | 0]$으로, 유닛 길이를 $t$로 정의한다. 다음 4개의 가능한 해들을 두번째 카메라에 대해서 시험해본다. 4개 중 하나는 올바른 구성이며, 나머지 하나는 하나의 뷰를 180도 돌린 것이다. 나머지 두개는 제대로된 구성을 뒤집은 것과 그것을 서로 반대로 구성한 것이다. 올바른 구성인지 확인하기 위해서는 cheirality 제한을 사용한다.
3.2 Efficiency Considerations
정리하자면 계산은 다음과 같다.
- 5 x 9 행렬의 널스페이스를 계산한다.
- 큐빅 제한 조건을 확장한다.
- Gauss-Jordan 소거법을 9 x 20 행렬 A에 적용한다.
- 2개의 4 x 4 다항 행렬 B, C 를 확장한 다음 소거법을 이용하여 10차 다항식을 얻는다.
- 이 다항식의 해를 구한다.
- 구해진 해에 대하여 R과 t를 복원하고, 모호성을 제거한다.
1,5,6 단계에서 SVD를 사용하는 것이 불문율이지만 QR-factorisation이 효율적이었다.
4. Planar Structure Degeneracy
5. Applying the Algorithm Together with Random Sample Consensus
RANSAC에 적용하는 방법을 2뷰와 3뷰가 있는 경우로 나누어 보았다. 랜덤 샘플링을 할 때 각각 5개의 대응점을 추출해야 한다. 추출된 대응점에 5점 알고리즘을 적용할 것이기 때문에 여러개의 가설들이 생성된다. 2뷰의 경우 각 가설들은 모든 점 대응에 대하여 평가한 뒤, 가장 점수가 높은 것을 선택한다. 최종적으로 가장 좋은 가설은 반복적인 정교화를 통해 더욱 좋아진다. 만약 3개 혹은 더 많은 뷰가 있을 경우, 5개의 대응점 샘플을로부터 유일한 해를 계산할 수 있어 모호성을 제거할 수 있고, 점들이 서로 평면에 있을 경우에도 해를 구할 수 있다. 각 5점 샘플에서 첫번째와 마지막 뷰에 대해서 5점 알고리즘은 적용한다음, 가능한 카메라 행렬을 구한다. 나머지 뷰에 대해서는 3점 캘리브레이티드 원근 알고리즘을 적용하도록 한다. 5점을 모든 뷰에 대해서 리프로젝션 해보는 것만으로도 가설의 좀수를 내기에 충분하다. 마지막으로 모든 샘플들에 대한 점수를 매길 수 있다.