Review: An Efficient Solution to the Five-Point Relative Pose Problem

Nistér, D. (2004). An efficient solution to the five-point relative pose problem. IEEE transactions on pattern analysis and machine intelligence, 26(6), 756-770.

Abstract

이 논문은 고전적인 Five-Point relative pose 문제에 대한 효율적인 알고리즘 솔루션을 제공한다. 핵심은 5개의 해당 포인트가 주어지면 두 개의 calibrated view 사이에서 상대적인 카메라 포즈를 찾는 것이다. 알고리즘은 10차 다항식의 계수를 closed form으로 계산한 다음 그 근을 찾는 것으로 구성된다. 문제의 고유한 복잡도에 해당하는 numerical implementation에 적합한 최초의 알고리즘이다. 우리는 알고리즘의 수치 정확도를 평가한다. 또한 최소한의 경우와 과잉된 경우에 대해 노이즈가 많은 조건에서의 성능을 비교한다. 그리고 이미 잘알려진 8-point와 7-point 방식의 성능과 비교한다. 이 알고리즘은 robust한 가설과 테스트 프레임워크를 사용하여 structure와 motion을 낮은 딜레이의 실시간으로 추정한다. 그리고 이 실시간 시스템은 주요 컨퍼런스에서 visual input만 사용하여 시연되었다.

1. Introduction

Structure estimation 및 Motion estimation이 robust하고 정확하려면 실제로(보통) 5개 이상의 포인트를 사용해야한다. 많은 점을 사용하는 기존의 고전방법들은 모든 점에 대해 least squares measure(최소자승법)을 최소화 하는 것이다. [18] 우리는 five-point 알고리즘을 위해서 RANSAC [8], [26] 내의 hypothesis generator를 응용했다. five-point 대응을 포함하는 많은 랜덤 샘플을 취한다. 각 샘플은 두 개 이상의 view에서 모든 포인트에 대해 robust한 statistical 측정으로 relative orientation으로 여러 hypotheses를 산출해낸다. 그런 다음 가장 적합한 hypothesis를 반복적으로 다듬는다. 이러한 hypothesis 및 test architecture는 일치하지 않는 point correspondence를 처리하는 표준 방법이 되었으며 [41], [48], [14], [24], 수 백개의 view에 걸친 automatic reconstruction을 가능하게 만들었다. [1], [34], [7], [25].

기존의 intrinsic calibration의 요구 조건은 지난 10년 동안 완화되어 [5], [12], [14] , 덜 복잡하고 더 연한 알고리즘으로 발전했다. 그렇다면 왜 calibrated setting을 이용하는가? 이론적인 관심과 별도로 이는 솔루션의 안정성(stability)과 고유성(uniqueness)을 위한 것이다. 고유한 calibration constraint를 적용하면 structure 및 motion estimation의 정확성과 robustness에 모두 중요한 개선을 제공한다. 현재 이를 달성하는 표준 방법은 반복적으로, calibrate되지 않은 초기 estimate에 이어, calibration constraint와 일치하도록 estimate를 가져오는 refinement를 통해 이루어진다. intrinsic parameter가 priori하게 알려진 경우, five-point 알고리즘은 calibration constraint 조건을 정확하게 적용하고 Euclidean reconstruction을 얻는 가장 좋은 방법이다.

uncalibrated 방법은 가능한 솔루션의 연속성이 있기 때문에 동일 평면의 scene point에 마주쳐서 실패한다. [43], [35]에선 모델 선택을 사용하여 이러한 degeneracy를 다루고 homographic 모델과 일반 uncalibrated 모델 사이를 적절하게 전환하는 것이 제안되었다. calibrated setting에서 동일 평면의 scene point는 최대 2배의 ambiguity를 유발한다. [21], [23]. 세 번째 관점에서 ambiguity는 일반적으로 해결된다. 이를 고려하여, 3개 이상의 뷰에 대해 5점 알고리즘을 사용하는 RANSAC 방식을 제안한다. 이는 일반 구조에 적용되면서도 scene의 planarity에도 robust하며, degeneracy에 의존하거나 명백하게 찾아내지않고 계속 올바르게 작동한다. 본질적으로, calibrated 모델은 평면 및 일반 structure 케이스를 완벽하게 커버할 수 있다. 이것은 거의 평면인 경우를 처리할 수 있다는 여지를 준다. (planar 또는 uncalibrated된, 일반 structure 모델이 잘 적용되지 않는 경우도 처리 할 수 있을 것이다.)

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

정리하자면 계산은 다음과 같다.

1. 5 x 9 행렬의 널스페이스를 계산한다.

2. 큐빅 제한 조건을 확장한다.

3. Gauss-Jordan 소거법을 9 x 20 행렬 A에 적용한다.

4. 2개의 4 x 4 다항 행렬 B, C 를 확장한 다음 소거법을 이용하여 10차 다항식을 얻는다.

5. 이 다항식의 해를 구한다.

6. 구해진 해에 대하여 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점을 모든 뷰에 대해서 리프로젝션 해보는 것만으로도 가설의 좀수를 내기에 충분하다. 마지막으로 모든 샘플들에 대한 점수를 매길 수 있다.