5. Structure From Motion (SFM)

Structure From Motion (SFM)

이제 카메라를 두 개에서 그 이상으로 나아가 본다. 이것은 structure from motion이라고도 알려져 있다.

가장 기본적인 아이디어는 여러개의 카메라에서 얻은 scene geometry와 camera parameters를 결합하여 다수의 view를 통해 3D points를 알아내는 것이다. 아래 그림에서 camera matrix를 모르는 카메라가 m개 있고, n개의 3D points가 있으며, 각 카메라에는 그에 상응하는 n개의 픽셀 좌표들이 있다.

SFM은 오직 카메라에서의 포인트 좌표 mxn개만 알고 있을 때, 3D objects의 좌표 n개의 Structure와 m개의 projection matrix Motion을 모두 알아내는 문제이다.

SFM

Affine Structure From Motion

아래 그림은 perspective scaling이 제거된 Affine Structure From Motion모델이다.
앞서 내용을 생략한 부분이 있어 보충하자면, 아래 식에서 matrix M의 맨 아래 row는 scale factor 정보가 들어가는 자리이다. 그런데 여기서는 0으로 모두 생략되어 있다. 

위 방정식의 우변을 euclidian system으로 다시 작성하면 아래와 같다.

위 방정식에는 몇개의 unknown parameter가 있을까?
정답은 8m+3n 개이다. 우선 matrix A, b 에서 8개, X에서 3개이다. 이 때 i는 m개의 카메라를 나타내고, j는 n개의 포인트를 나타내므로 8m+3n 개가 된다. 그렇다면, SFM 문제에서는 각 카메라 마다의 포인트 픽셀좌표를 안다고 가정했으므로, 2mn개의 값을 알고 있다. 2mn >= 8m+3n 을 만족하는 m과 n이라면 카메라의 motion matrix M을 구할 수 있다.

 

Factorization Method - Tomasi & Kanade algorithm

• Data Centering
  각 이미지 안의 포인트 픽셀좌표 x_ij에서 그들의 무게중심을 뺀 값으로 좌표를 재설정한다.
• Factorization
  그렇게 얻어진 방정식을 SVD로 해결한다.

 

Perspective SFM

일반적인 경우는 perspective SFM으로 표현된다. 우리는 projection matrix M에서 scale factor 또한 찾아야한다.

위 방정식에는 몇개의 unknown parameter가 있을까?
정답은 11m+3n-15 개이다. 일단 affine에서 scale factor 3개가 늘어나 11m인데 15는 왜 뺀걸까?

 

Algebraic Approach (by fundamental matrix)

8-point algorithm으로 두개의 view 사이의 fundamental matrix F를 구한다. 그리고 이 F를 이용해 camera matrix를 구한다. 마지막으로 이 matrix들을 이용해 structure points를 구한다.

Factorization Method (by SVD)

affine SFM에서 보았던 Tomasi-Kanade method의 방식과 같다. 다만 여기에서는 3D points의 거리를 대략적으로 알고있다는 가정이 들어간다. 이것은 어떤 케이스에서는 합리적일 수 있지만 일반적으로는 그렇지 않다는 문제가 있다.

Bundle Adjustment

Bundle adjustment에 대해 이야기 하기 전에 위의 두 가지 methods의 주요 문제점들을 살펴보자.

1. factorization method는 모든 points가 모든 view에서 visible하다고 가정한다.
   • occulusion
   • failure in establishing correspondences
2. algebraic mehtod는 2 view 사이에서만 pairwise한 결과를 내며 전체 view에 대한 최적화가 이뤄지지 않는다.

Bundle adjustment는 이러한 문제를 해결해준다.

Bundle adjustment는 non-linear한 method로 픽셀 단위의 reprojection-error를 줄이는 방식으로 최적화한다. 즉 reconstructed point와 ground truth point사이의 거리를 모든 카메라 view에 대해 계산하여 이것을 최소화하는 점을 찾는다. 이것은 triangulation에서 3D point를 찾는 방식과 매우 유사하다. 최적화 문제를 풀 때에는 non-linear 최적화 기법을 사용하는데 Newton's method, Levenberg-Marquardt algorithm을 흔히 사용한다.

Bundle adjustment

장점

• it handles large number of views
• it handles missing data

단점

• it’s a large minimization problem (parameters grow with number of views)
• it requires good initial condition, which we often find with one of the other methods we’ve discussed.

이러한 이유로, bundle adjustment는 algebraic method나 factorization method로 initial solution을 구한 다음의 단계로써 사용된다.