[cite]10.1109/34.601246[/cite]

1 Introduction

8개의 점을 이용하여 essential matrix를 계산하는 방법은 Longuest-Higgins에 의해 처음 소개되었습니다. 그는 캘리브레이션이 이미 행해진 카메라들에서의 두개의 시점으로부터 씬의 구조(structure)를 계산해 내었습니다. 이 방법의 장점은 선형이고 빠르며 쉽게 구현이 가능하다는 점입니다. 8개의 매칭된 점들만 알면 선형 방정식이 세워지며, 그보다 더 많은 점을 알면 선형 least square를 이용하여 문제를 풀 수 있습니다. 또한 어떤 알고리즘들은 캘리브레이션되지 않은 카메라로부터 어떤 행렬을 계산해 내는데 이는 결국 fundamental matrix라고 부르는 행렬입니다.

하지만 8점 알고리즘은 종종 매칭 결과의 노이즈에 취약하다고 평을 받습니다. 이를 극복하기 위하여 많은 방법들이 제안되었습니다. 이 논문에서는 점들의 간단한 변형(translation, scaling)을 통하여 이 취약점을 극복하고 안정된 성능을 얻고자 하는 방법을 소개합니다.

2 Outline of the Eight-Point Algorithm

2.1 Notation

2.2 Linear Solution for the Fundamental Matrix

Fundamental matrix는 다음과 같은 식으로 정의됩니다.

$\mathbf{u}'^T F \mathbf{u} = 0$

여기서 $\mathbf{u}' \leftrightarrow \mathbf{u}$는 두 이미지에서의 매칭되는 점을 나타냅니다.8개보다 많은 충분히 많은 매칭 점 $\mathbf{u}'_i \leftrightarrow \mathbf{u}$가 주어졌을 때, 행렬 F를 계산할 수 있게 됩니다.

매칭되는 한 점을 $\mathbf{u} = (u, v, 1)^T, \mathbf{u}' = (u', v', 1)^T$라고 하였을 때 행렬 식을 풀어내면 다음과 같은 식을 얻을 수 있습니다.

$uu'F_{11} + uv'F_{21} + uF_{31} + vu' F_{12} + vv' F_{22} + v F_{32} + u' F_{13} + v' F_{23} + F_{33} = 0$

모든 점에 대해서 위의 식을 얻은 뒤 F를 하나의 벡터 $\mathbf{f}$로 표현하여 행렬 식으로 표현할 수 있습니다.

$A\mathbf{f} = 0$

이 때, 해 $\mathbf{f}$는 알지 못하는 스케일에 갖는 벡터로 정의되므로 추가적으로 제한 조건을 걸어주도록 합시다.

$|| \mathbf{f} || = 1$

이렇게 하면 최소한 8개의 점이 있고, 이 식이 해를 갖는다면 그 해를 찾을 수 있습니다. 다시 말하면 행렬 A는 rank-deficient이어서 랭크를 9가 아닌 8을 갖습니다.

하지만 매칭된 점의 관측이나 정의가 부정확하기 때문에 행렬 A는 rank-deficient가 아니게 되어 랭크 9를 갖습니다. 따라서 least-squares 방법을 이용하여 이 식의 해를 찾도록 하고 있습니다. 이것은 $A^T A$의 가장 작은 eigenvalue를 갖는 eigenvector를 구하는 문제로 잘 알려져 있습니다. $A^T A$는 positive semi-definite이고, symmectric하므로 모든 eigenvector는 실수이고 양수이거나 0입니다. 편의상 이 벡터를 least eigenvector라고 부르도록 합시다.

2.3 The Singularity Constraint

Fundamental matrix의 중요한 성질 중 하나는 그것이 singular하다는 것입니다. 즉 랭크 2를 갖습니다. 또한 F의 왼쪽 오른쪽의 null-spaces들은 두개의 epipole들을 나타내는 벡터로 생성됩니다. 때문에 위의 식들에서 F를 직접 풀어내면 랭크가 2가 아닌 행렬이 구해져버립니다. 이를 푸는 가장 편리한 방법은 $F$를, Frobenius norm$||F-F'||$를 최소화하면서 $\det F' = 0$인 $F'$로 교체하는 것입니다. 이를 찾는 방법은 Singular VAlue Decomposition (SVD)를 이용하는 것인데, $F = UDV^T$에서 $D = \text{diag}(r, s, t)$라고 하였을 때, $F' = U \text{diag}(r,s,0)V^T$로 놓는 것입니다. 이 방법은 Tsai와 Huang이 제안한 것으로 Frobenius norm을 최소화하는 것이 증명되었습니다.

다시 8점 방법으로 돌아와 정리하자면, 8개의 점으로 fundamental matrix를 구하는 방법은 두가지 단계로 이루어집니다.

1. Linear solution : 매칭된 점들이 주어지고 $\mathbf{u}'_i F \mathbf{u}_i = 0$ 식들을 풀어냅니다. 해는 least eigenvector $\mathbf{f}$입니다.
2. Constraint enforcement : $F$를 $F'$로 교체하고 가장 근접한 singular matrix를 계산합니다. 이는 SVD를 이용하여 계산합니다.

3 Transformation of the Input

이미지에서의 원점은 늘 이미지의 중심에 있는 것은 아닙니다. 이는 fundamental matrix의 계산에 영향을 끼치기 때문에 사용하는 좌표계에 따라 다른 결과를 가져옵니다. 8점 알고리즘에서 또한 마찬가지입니다. 만약 F를 계산하기 전에 이미지 좌표계가 affine이나 projective transformation이 이루어진다면 결과는 어떻게 바뀌게 될지 생각해보도록 합시다.

어떤 변환 $T$에 대하여 매칭되는 두 점이 변환되었다고 합시다.

$\hat{\mathbf{u}} = T \mathbf{u}, \hat{\mathbf{u}}' = T \mathbf{u}'$

이를 Fundametal matrix 식에 대입하면 아래와 같습니다.

$\hat{\mathbf{u}}'^T T'^{-T} F T^{-1} \hat{\mathbf{u}} = 0$

결국 $T'^{-T} F T^{-1}$는 변환된 두 점 사이에 대한 fundamental matrix입니다. 역으로 이를 이용하여 원래의 F를 구하는 방법은 아래와 같습니다.

1. 변환된 두 점을 계산합니다. $\hat{\mathbf{u}} = T \mathbf{u}, \hat{\mathbf{u}}' = T \mathbf{u}'$
2. 변환된 두 점에 해당하는 fundamental matrix $\hat{F}$를 계산합니다.
3. $F = T'^T \hat{F} T$ 입니다.

위의 식에 따라 변환 T에 대하여 $F$와 $\hat{F}$는 1대 1 대응 관계를 갖습니다. 하지만 모든 점에 대해서 계산하였을 때 $F$와 $\hat{F}$가 동일하게 에러 $\epsilon$을 최소화하는 것은 아닙니다. 또한 두 행렬이 동일한 에러를 갖도록 계산하더라도 $|| F || = 1$의 조건은 $||\hat{F}||=1$과 동등하지 않습니다.

식 $A \mathbf{f} = 0$에 T에 대한 변환을 반영한 수식을 $AS \mathbf{f} = 0$로 나타내어봅시다. $S$는 변환 T에 대한 추가 항을 나타낸 9 * 9 행렬입니다. 그렇다면 $\hat{\mathbf{f}} = S^{-1} \mathbf{f}$가 되어 원래의 $\mathbf{f}$를 얻을 수 있을 것입니다. 하지만 이처럼 쉽게 풀리지만은 않습니다. $A \mathbf{f} = 0$과 $AS \mathbf{f} = 0$의 두 식은 서로 연관성이 없기 때문입니다. 즉 두 식에 해당하는 $A^T A$와 $(AS)^T (AS)$의 least eigenvector는 다르기 때문입니다.

정리하자면 점의 변환이 이루어지면 fundamental matrix 또한 달라진다고 이야기 할 수 있습니다. 이는 8점 알고리즘에서는 원치 않은 결과이며 이를 해결하기 위해 normalization을 통해야 fxied canonical frame에서 표현하고자 합니다.

4 Condition of the System of Equations

F를 구하는 linear 방법은 $A^T A$의 least eigenvector를 구하는 과정을 포함하고 있습니다. 이는 $A^A = UDU^T$로 표현하는 것으로 마무리하게 되는데, U는 orthogonal하고 D는 diagonal합니다. 보통 D는 작아지는 순서로 되어있기 때문에 least eigenvector는 U의 마지막 컬럼입니다. $\kappa = d_1 / d_8$라고 정의하여 봅시다. 이는 $A^T A$의 condition number 인데, linear problem의 안정성을 알 수 있는 한 조건입니다.

$|| A^T A || = (\sum_{i=1}^9 d_i^2)^{1/2}$ 이기 때문에, 만약 이 $\kappa$가 매우 크면, $d_8$은 Frobenius norm의 매우 작은 영향을 가지게 됩니다. 따라서 $d_8$에 노이즈로 인한 변화가 있더라도 $A^T A$는 상대적으로 작은 변화만을 가져올 것입니다. 이는 동시에 least eigenvector에는 큰 변화를 가져오게 됩니다.

그런데 항 $A^T A$는 두 쌍의 점에 의해서 직접 만들어지기 때문에, 데이터에 가해지는 작은 변화는 우리가 구하는 해에는 매우 큰 변화를 가져온다는 뜻이 됩니다.

이제 어떻게 condition number를 작게 만들 것인지 생각하여봅시다. 논문에서는 translation과 scaling의 두가지 종류의 변환을 언급하였습니다.

4.1 Translation

이미지의 좌표계 중심이 좌측 상단에 있다고 생각하여봅시다. 따라서 좌표들은 모두 양수를 가질 것입니다. 이러한 경우 주어진 점들의 중심으로 좌표계 중심을 옮기는 것으로 matrix의 condition을 향상 시킬 수 있습니다. 그 이유는 논문에 간단히 언급되어있습니다.

5 Normalizing transformations

Normalization 또한 8점 알고리즘 전에 적용하면 좋은 결과를 낼 수 있습니다.

5.1 Isotropic Scaling

일단 앞의 translation을 통하여 중심을 이동하였다고 가정한 상태에서 출발합니다. 좋은 결과를 내는 스케일링 방법은, 모든 점들의 평균 점 $\mathbf{u} = (u, v, w)^T$에서 각 u, v, w가 같은 평균 magnitude를 갖도록 하는 것입니다. 따라서 각 점과 원점과의 평균 거리는 $\sqrt{2}$가 되고, 평균 지점은 $(1, 1, 1)^T$이 되어버리는 것입니다. 정리하면 아래와 같습니다.

1. 모든 점들의 평균을 원점으로 translation 합니다.
2. 각 점들은 원점으로부터 평균 거리가 $\sqrt{2}$가 되도록 scaling합니다.
3. 위의 방법을 두 이미지에 각각 독립적으로 적용합니다.

5.2 Non-Isotropic Scaling

Non-isotropic 방법에서는 원점은 똑같이 이동하고나서, 점들을 나타내는 2개의 주축(principal moments) 방향으로 스케일을 갖도록 조절합니다. 따라서 결과적으로 점들이 반지름 1을 갖는 원형으로 분포하도록 조절됩니다.

이 방법은 한번의 계산하는 방법은 논문을 참고하도록 합시다.

6 Scaling in Stage 2

F를 찾기 위해 선형 식을 푸는 과정에서 scaling을 하였지만 한 번 더 scaling을 거치고자 합니다. 바로 singularity constraint $\det{F} = 0$을 만족하는 F를 찾는 단계에서 적용하는 것입니다.

위에서 언급했듯 이러한 F를 찾는 것은 Frobenius norm으로 보았을 때 F에서 가장 가까운 singular matrix $\hat{F}$를 찾는 것입니다. 이 방법의 문제점은 행렬의 모든 요소들에 대하여 그들의 magnitude를 동등하게 취급된다는 것입니다. 따라서 F의 작은 요소들은 상대적으로 큰 값에 비하여 진동하기 쉽게 되는 경향이 있습니다.

만약 모든 점들이 homogeneous 좌표계에서 normalize되었다고 한다면 fundamental matrix의 각 요소들 또한 모두 같은 magnitude를 가질 것으로 생각할 수 있습니다.

만약 normalization된 점들을 100으로 스케일은 늘려 평균 $(100, 100, 1)^T$의 좌표를 갖게 만들었다고 생각해봅시다. 이러한 경우 F의 3 * 3 개의 요소 중 좌측 상단 2 * 2 행렬은 $10^{-4}$의 스케일을, 우측 하단을 제외한 나머지 4개의 요소는 $10^{-2}$를 우측 하단은 1의 스케일의 magnitude를 갖게 될 것입니다. 이는 결국 마지막 요소에 대하여 노이즈가 작게 영향을 주는 것을 모든 요소에 대하여 동등하게 영향을 주도록 하여줍니다. 결국 마지막 요소에 대한 영향이 커지게 되므로 행렬 F를 계산하는 과정은 안정하게 됩니다.

7 Experimental Evaluation

사전에 좌표계 변환 과정을 거친 후 8점 알고리즘을 적용한 방법을 normalized eight-point algorithm 이라고 부르기로 합니다.

실험 순서는 아래와 같이 진행되었습니다.

1. 매칭 점들을 자동적인 방법으로 계산하고 아웃라이어 또한 제거합니다.
2. 일부 점들을 사용하여 Fundamental matrix를 계산합니다.
3. 8점 알고리즘의 경우 SVD를 이용하여 가장 가까운 singular matrix를 계산합니다.
4. 각 점 $\mathbf{u}_i$에 대하여 epipolar line $F \mathbf{u}_i$를 계산하고 이것과 $\mathbf{u}'_i$와의 거리를 계산합니다. 이것은 반대 경우로도 계산하여 평균 거리를 fundamental matrix를 평가하는데 사용합니다.

비교를 위하여 기존의 Eight-Point 알고리즘, Eight-Point Isotropic Scaling, Eight-Point Non-Isotropic Scaling, Minimizing Epipolar Distnaces, Gradient-based Technique, Minimizing Point Displacement, Approximate Calibration, Iterative Linear를 알고리즘을 사용하였습니다.

이미지는 5개의 이미지 쌍을 사용하였습니다.

8 Conclusions

8점 알고리즘은 그대로 사용하면 그 에러가 10픽셀이나 떨어질 정도로 결과가 좋지 않지만 normalization을 사용하면 iterative 알고리즘에 비슷할 정도로 겨로가가 좋아졌습니다. 또한 normalization에 iterative 알고리즘까지 동시에 사용하면 더욱 높은 정확도를 기대할 수 있습니다.

---