Slam 5-1강 (The Basics about Bundle Adjustment) 요약

Cyrill 교수님의 SLAM 강의를 듣고 정리해보자!

0. Today’s Goal

• Bundle Adjustment란?
• Bundle Adjustment 과정
• Bundle Adjustment에서 고려해야 할 것들
• Quality of the Results

1. 강의 및 강의 자료

강의 List는 SLAM KR의 SLAM DUNK seson 2에서 정해준 강의를 따라 정리를 할 것이다.

SLAM DUNK season 2의 Reference는 여기서 확인해 볼 수 있다.

SLAM KR에서 이 강의를 듣고 요약을 세미나 형식으로 준비를 해준다!

이번 포스팅은 다음의 강의들을 참고하여 요약을 해보았다.

• The Basics about Bundle Adjustment (Cyrill Stachniss)
• SLAM DUNK Season 2 - The Basics of Bundle Adjustment

Cyrill Stachniss의 강의 자료는 pdf로 다운 받을 수 있다.

Bundle Adjustment를 이해하기 위해서는 Homogenous coordinates, PnP algorithm, 8 points algorithm (5 points algorithm), RANSAC, Triangulation을 완벽하진 않지만 한번쯤은 들어본 상태에서 강의를 듣는 것을 추천한다.

그만큼 난이도가 있는 강의이다. 😟😟

2. Bundle Adjustment란?

Bundle Adjustment란 카메라의 이미지 data들로부터 3차원 공간으로 이미지에 나타난 정보들을 모델링을 진행할 때, 카메라의 pose와 3차원 공간의 points들의 위치를 추정할 때 필요한 최적화 기법 중 하나이다.

Bundle Adjustment를 설명하기 전에 우선 3D Reconstruction이 무엇인지부터 짚고 넘어가보자.

3D Reconstruction을 진행할 때는 Lidar나 Depth camera같은 거리 값을 이용하는 것이 아니라 2D image들의 묶음(set)으로만 3D 복원을 진행한다.

보통 SIFT와 같은 특징점을 찾는 알고리즘을 이미지에서 수행하고, Triangulation과 같은 과정을 거쳐 3차원 공간에 point들이 어디 위치하고 있는지 추정을 하게 된다.

Triangulation의 경우 다른 포스팅에서 조금 더 자세하게 다룰 예정이다.

예를 들어 한번 3D Reconstruction의 감을 잡아보자.

위와 같은 드론으로 아래쪽에 위치한 카메라를 활용하여 3D Reconstruction을 수행하면 결과는 아래와 같다.

위 그림에서 파란색 사각형 처럼 보이는 것이 이미지이고 아래쪽에 point cloud 형식으로 시각화된 것이 3차원 output이다. Bundle Adjustment의 결과를 활용하여 위와 같은 예제의 output을 만들 수 있는 것이다.

강의에서는 3D Reconstruction과 관련된 이야기를 계속 하는데, 그렇다면 두 장의 이미지가 아닌 더 많은 이미지 set이 필요한 이유는 무엇일까?

왜냐하면 물체를 3차원으로 표현할 때 2장의 이미지로는 물체의 복잡한 표면을 모두 담아낼 수 없기 때문이다. 따라서 조금 더 많은 이미지들을 활용하여 추정한 결과(camera pose or 3D location points)를 조금 더 정교하게 최적화하는 과정이 필수적으로 필요하다.

최적화 과정(Bundle Adjustment)을 수행하면 아래와 같이 대규모의 Map을 만드는 것도 가능하다.

Bundle Adjustment는 Bundle Block Adjustment라고도 부르는데, Bundle Adjustment 과정을 Block 단위로 수행하여 많은 이미지 쌍을 동시에 고려를 해서 최적화를 수행하기 때문이다.

Bundle Adjustment라는 개념은 1950년대 photogrammetry분야의 Aerial Triangulation라는 분야에서 처음 나왔다.

초창기에는 몇몇 3차원 point들이 어디있는지 안다는 가정하에 camera pose를 추정하였는데 이러한 point들을 control point라고 부른다.

대략적인 Bundle Adjustment 개념부터 간략하게 Bundle Adjustment의 역사까지 훑아보았다. 그럼 어떻게 Bundle Adjustment가 동작하는지 알아보자.

3. Bundle Adjustment 과정

앞서 설명했지만, Bundle Adjustment과정은 여러 이미지 정보를 활용하여 camera pose와 3D points를 추정하는데 사용하는 최적화 방법이다.

우선 Bundle Adjustment을 수행하기 위해선 이미지에서 특징점을 추출해야 한다. 어떤 특징점 알고리즘을 사용하는지는 상관이 없다. SIFT,SURF,ORB 등등 다양한 알고리즘을 사용해도 된다. 그리고 뽑힌 특징점만을 3D Reconstruction에 이용을 한다.

Camera pose 추정과 3D point location 추정을 동시에 진행하고 최적화를 진행할 때 정의하는 Error를 Non-linear squares 방법을 활용해서 해결한다.

Non-linear squares 방법을 사용하기 때문에 초기값(Initial guess)이 존재해야 한다. 초기값으로 6-DOF camera pose와 3D points를 정의한다음, 3D points를 정의한 camera pose에 투영하는 과정을 거친다.

3D points들을 이미지로 투영을 시키게 된다면, 이미지상에 투영된 점들이 어느 위치에 있는지 계산을 할 수 있다. 계산된 값과 실제로 Measurement(특징점 알고리즘을 사용하여 측정된 points들)들을 활용해서 얼마나 차이가 있는지 계산을 할 수 있다.

이런 오차를 줄여 나아가는 것이 Bundle Adjustment과정이다. 이렇게 만든 오차를 Reprojection error라고 한다.

만약 오차가 없다면 가정한 Camera pose와 3D points location이 잘 추정된 것이라고 생각할 수 있다.

---

지금까지 설명한 Bundle Adjustment 방법을 정리하면 아래와 같다.

1. 이미지에서 특징점을 추출한다. 3차원 공간에 특징점들의 실제 위치를 추정하는 것을 목표로 한다.
2. 6-DOF camera pose와 3D points들의 위치의 초기값을 정한다.
3. 3D points들을 가정한 camera pose에 투영(projection)을 시킨다.
4. 이미지에 투영된 점들의 위치와 실제 Measurement(특징점을 추출)들의 위치를 활용해서 Reprojection error를 정의한다.
5. Reprojection error를 줄이기 위해 Non-linear squares 방법을 사용한다.

Reprojection error

수식적으로 지금까지 이야기한 내용을 알아보면 아래와 같다.

수식에 Notation이 많아 어질어질하지만 차근차근 살펴보자.

이 수식은 결국 projection matrix $\hat{P_j}$ 및 scale factor $\hat{\lambda_{ij}}$를 활용해서
3D point $\hat{X_i}$를 이미지에 투영시키고, 실제 이미지에서 뽑아낸 특징점 $x’_{ij}$

그리고 그 둘의 픽셀 단위에서 오차값 $\hat{v_{x’_{ij}}}$을 활용해서 식을 정의했다.
$i$는 3D points 중에서 $i$번째 point를 의미하고, $j$는 $j$번째 이미지의 ID를 의미한다.

Uncertainty in the image coordinates란 특징점을 얼마나 정확하게 추출했는지 나타내기 위한 값이다.

이 과정을 수행할 때는 Known Data association을 가정한다. Known Data association이란 3D point $\hat{X_i}$를 이미지에 투영시켰을 때, 어떤 특징점 $x’_{ij}$와 매칭이 되는지 알고 있다는 것이다.

Data association을 확실하게 알고 있어야 Bundle Adjustment도 잘 수행되기 때문에 정확한 Data association을 찾는 것이 굉장히 중요하다!

그렇다면 위 수식에서 unknown parameters는 몇 개일까?

3D location of new point $\hat{X_i}$는 $x,y,z$ 좌표이기 때문에 3개의 parameters가 존재하고,
scale factor $\hat{\lambda_{ij}}$는 1개의 parameter, 6D exterior orientation은 카메라의 extrinsic parameter를 의미한다.

5D projection parameter는 intrinsic parameter를 의미하고, 여러 non-linear한 distortion에 대해 표현을 해줄 paramter $q$까지 unknown parameters이다. $q$는 1~2개의 parameters를 사용한다.

여러 가지 카메라들을 활용하여 이미지를 취득했으면, 또 카메라마다 각각 다른 calibration을 적용했기 때문에, 그에 맞는 parameter를 찾아줘야 한다.

Example of Bundle Adjustment

예를 들어 Bundle Adjustment 과정을 이해해보자.

위에서 말했던 것처럼 10000장의 이미지가 있고, 한 장의 이미지당 1000개의 특징점을 추출한다고 가정하자. 3D point 하나는 평균적으로 10장의 이미지에서 관찰이 된다고 할 때 우선 observation의 크기는 얼마나 될까?

이미지 좌표에서 $x$좌표, $y$좌표가 존재하고, 총 10000장의 이미지, 한 장당 1000개의 특징점이 있으므로, observation의 크기는 2*10000*1000 = 20000000(= 20M)이다.

또한 우리가 구해야 하는 unknown parameters는 1000개의 특징점에 대한 3DOF (3*1000), 10000개의 scale factor, 10000개의 카메라에 대한 6DoF (하나의 카메라로만 이미지를 취득했을 경우, intrinsic parameter는 고정이기 때문)를 모두 합한 값이다. 따라서 약 13000000(= 13M)정도 parameter들을 알아야 한다.

우리가 구해야 하는 parameter의 수를 줄이기 위해서 scale factor를 제거하는 방법을 사용한다.

Homogenous coordinates를 사용하는 대신에 Euclidian coordinates를 사용하는 방법으로 scale factor를 제거할 수 있다.

그 결과 약 13000000(= 13M)정도 parameter들을 3000000(= 3M)정도로 줄일 수 있다.

우리가 구해야 하는 parameter를 알았으면 이제 Least squares 방법을 사용한다.

여기서 $A$는 Jacobian Matrix, $\Sigma$는 covariance matrix 로 나타내였고, 우리가 찾아야 하는 unknown parameters를 $x$, observations를 $l$로 표기하였다.

위 수식에는 많은 parameter가 존재하기 때문에, 실제로 Bundle Adjustment를 사용할 땐 조금 더 효과적인 방법을 사용하는데, 그 방법에 대해서는 다음 포스팅에서 다룰 예정이다.

Bundle Adjustment의 속성

우선 Bundle Adjustment는 statistically optimal solution이라는 특징이 있다. 즉, 우리가 세운 가정이 실제 상황에 잘 부합하는 경우 최적의 해를 찾을 수 있다는 의미이다.

최적의 해를 찾기 위해선 Data association을 잘 수행해야 하고, 이에 대한 uncertainties, correlation도 잘 고려되어야 하며 Gaussian noise model을 따라야 하고, 초기값도 잘 찾아야 한다.

이를 한 장의 슬라이드로 정리하면 아래와 같다.

4. Bundle Adjustment에서 고려해야 할 것들

우리가 카메라 이미지만으로 3D reconstruction을 진행하면 “photogrammetric model”을 얻을 수 있는데, 이는 정확한 scale값이 고려되지 않은 값이다.

따라서 scale까지 고려된 정확한 3D modeling을 수행하려면 몇 가지 추가적인 정보가 필요하다.

Absolute Orientation Through Control Points

Absolute Orientation이란 간단히 이야기하면 3D points의 집합을 정렬할 때 Scale까지 고려를 해서 Transformation을 결정하는 문제이다. 그리고 Control Points란 실제 3차원 공간에서 실제로 points들이 어디에 위치하고 있는지 아는 점들을 의미한다.

Control Points 정보를 Bundle Adjustment를 수행하는데 추가하면 실제 scale까지 고려하여 3D reconstruction을 진행할 수 있게 된다.

그렇다면 이 Control Points를 어떻게 알 수 있을까? 또한 Control Points들을 구할 때 Noise가 있다고 가정해야 할까? 아님 Control Points의 값을 그대로 믿고 쓰면 될까?

이는 우리가 어떤 것에 관심 있는지에 따라 달라진다. 즉, Bundle Adjustment를 수행하는 초반에는 Control Points를 Noise가 있다고 가정하고, Outlier를 제거한 다음에는 남아있는 Control Points들을 고정하고 Bundle Adjustment를 수행한다.

그렇다면 얼마나 많은 Control Points가 필요할까?

Bundle Adjustment는 최소 3개의 Control Points가 필요하다고 강의에서는 이야기했다. 이는 Direct Linear Transform 방법이나 P3P solution보다 훨씬 적은 수인데, 왜냐하면 Bundle Adjustment는 statistically optimal solution이라는 특징이 있기 때문이다.

만약 scale을 고려하지 않고 3D reconstruction을 수행할 경우, Control Points는 없어도 된다.

Initial Guess

Bundle Adjustment는 Least squares 방법으로 최적화를 수행하기 때문에 초기값은 필수이다.

그렇다면 어떻게 초기값을 얻어낼까?

이미지 쌍을 이용한 Direct method 방법을 사용한다.

Direct method 방법이란 초기값 없이 Orientation을 구하는 방법을 이야기 한다. N개의 이미지들에 대한 Direct solution은 아직 없기 때문에 이미지 쌍으로 쪼개서 초기값을 구하는 방법을 생각해볼 수 있다. 8 points algorithm 이나 5 points algorithm으로 카메라와 관련된 Rotation matrix $R$, translation vector $t$를 얻은 후, P3P 알고리즘을 활용해 orientation을 구하는 방법이다.

하지만 이 방법을 사용해야 할 경우, 여러 문제점들이 존재한다.

• Outlier 제거를 잘 수행해야 한다.
• 이미지 쌍들에 대해 충분한 points들이 필요하다.

따라서 Outlier에 대해서 한번 이야기를 해보겠다.

Outliers를 만드는 요인에는 크게 두 가지가 존재한다.

• Wrong correspondences
• Wrong point measurements

Wrong correspondences에 대해서 우선 이야기해보자. 최소 3장 이상의 이미지가 필요하다. 2장의 이미지만으로는 내가 수행한 triangulation의 결과가 맞는 값인지 틀린 값인지 비교를 할 수가 없기 때문이다.

따라서 하나의 3D points에 대해 최소 4개의 서로 다른 view가 필요하고 적어도 5~6개의 서로 다른 view에서 본 이미지 값들이 있을 때 outlier를 판단하고 잘 추정할 수 있다.

Outliers를 제거하는 또다른 방법은 RANSAC 알고리즘을 활용하는 것이다. 계산량이 더 많이 들지만, 조금 더 정확한 data association 값을 얻을 수 있다. 예를 들어 5 point algorithm에 RANSAC을 결합하여 사용할 수 있다.

Robust Kernels

Slam 4-4강 (Robust Least Squares for Graph-Based SLAM) 요약 포스팅에서도 언급했지만, Least Squares 방법을 조금 더 Robust하게 만드는 방법 중 하나가 Robust Kernel을 만드는 방법이다.

Bundle Adjustment 방법 역시 Least Squares 방법이기 때문에 Robust Kernel을 적용하여 outlier에 강인하게 Error minimization을 수행할 수 있다.

---

Bundle Adjustment 방법을 수행하는데 여러 가지를 고려해야 하지만, 다양한 software가 있으므로 이를 모두 직접 설계할 필요는 없다. 다만 정확한 Data association을 찾는 것이 엔지니어에게 필수적인 작업이다.

Cyrill 교수님께서 언급하신 Software는 다음과 같다.

• meshroom
• Photoscan
• Pix4D

5. Quality of the Results

Bundle Adjustment의 결과를 그럼 어떻게 평가를 할까?

Precision을 측정할 수가 있는데 다음과 같은 수식으로 측정을 할 수 있다.

이론적으로는 precision을 우리가 Least squares 방법을 정의할 때 사용한 식을 사용한다.

여기에 variance factor $\hat{\sigma^2_0}$ 을 곱한 값으로 empirical precision(경험적 정밀도)를 정의한다.

Notation이 조금 달라 헷갈릴 수 있지만, 결국 unknown parameter ($\hat x$)끼리의 불확실성을 정밀도를 측정하는데 사용하는 것이다.

그렇다면 어떤 값이 좋은 precision을 가졌다고 이야기할 수 있을까?

variance factor $\hat{\sigma^2_0}$를 통해 precision을 평가하는데, variance factor가 1인 경우 Model이 정확하다는 의미이다.

얼마나 1의 가까운지는 statistical test를 통해 확인 할 수 있다.

주관적인 의견이지만 직관적으로 이해해보면 unknown parameter ($\hat x$)끼리의 불확실성이 작으면 높은 정밀도 값이 나오고, 이에 대한 3D Reconstruction 결과를 직접 확인하여 Bundle Adjustment의 결과를 평가할 수 있다는 것이다.

강의 뒷부분에 Aero/Arial Triangulation 과정을 설명해주는 부분이 나오는데 Bundle Adjustment를 이해하는데 도움이 되지만 이부분에 대한 이야기까지 하면 포스팅이 너무 길어지기 때문에 생략을 하겠다.

6. Summary

이번 강의에서는 Bundle Adjustment가 어떤 것인지 감을 잡았다.

카메라와 관련된 여러 parameter, scale, 3D points를 unknown parameters로 정의하고 Least squares 방법을 통해 unknown parameters에 대해 최적의 해를 구하는 것이 Bundle Adjustment의 핵심이다.

Statistically optimal solution이기 때문에 Control points가 적어도 최적의 해를 구할 수 있으며, 여러 Least squares 방법과 마찬가지로 초기값을 잘 구하는 것과 Robust하게 함수를 설계하는 것이 Bundle Adjustment 결과에 영향을 미치게 된다.

Bundle Adjustment와 관련된 수식적인 내용은 다음 포스팅에서 다룰 예정이다.