Bundle adjustment란?

Posted on Edited on In , , Views:

예상 면접 질문

  1. Bundle adjustment가 무엇인가요?
  2. Bundle adjustment의 과정에 대해 설명해주세요.
  3. Bundle adjustment에서 matrix sparsity가 중요한 이유가 무엇인가요?

답

  • Structure from Motion을 수행할 때, 다수의 프레임에 존재하는 Visual keypoint 들의 위치 (i.e. 2D pixel location)를 기반으로 추정할 수 있는 3D landmark position과 카메라 프레임간의 3D relative motion을 동시에 최적화하는 과정
  • SLAM에서는 다음과 같은 방법으로 사용한다.
    1. Sliding window optimisation
      • 실시간으로 SLAM 프로그램을 돌리면서, 마지막 N개의 keyframe 정보를 기반으로 Bundle adjustment를 수행하여 실시간으로 local map + pose를 보정하는 작업
    2. Loop closure
      • 실시간으로 SLAM을 돌리면서, Loop closure detection이 일어났을 때 Loop closure optimisation을 다른 쓰레드에서 비실시간으로 수행하여 loop에 대한 pose + global map을 보정하는 작업
    3. Global optimisation
      • 실시간으로 SLAM을 돌리면서, 종종 다른 쓰레드에서 비실시간으로 모든 map + pose를 보정하는 작업. (잘 안쓰임)
    4. Global optimisation as 후처리
      • SLAM이 끝나고나서, 모든 map + pose를 비실시간으로 보정하는 작업.
  • 보통 closed-form 방식으로 initial guess 정보가 있음.
    • Initialization 단계에서 Homography/Fundamental matrix를 이용하여 얻어낸 relative motion 정보 + 이후 PnP로 추가해내간 relative motion 정보.
    • Initialization 단계에서 초기 R|t로 얻어낸 3D landmark position 정보 + 이후 triangulation으로 추가해내간 3D landmark position 정보.
    • 하지만 이러한 정보들은 어쩔 수 없이 error를 내포하고 있음.
  • 위의 error를 보정하기 위해 최적화를 진행함.
    • 3D landmark에서 카메라 coordinate의 원점까지의 직선을 ‘ray’로 표현할 수 있음.
    • 이러한 ray가 다수 있을 경우 ‘bundle of ray’라고 표현함.
    • 이 ‘bundle of ray’를 보정 (i.e. adjust) 한다는 의미로 bundle adjustment라는 이름을 사용함.

Cost function - reprojection error

  • 최적화에 대한 cost function은 reprojection error임.
    • 2D visual keypoint 위치가 , 3D landmark 위치가 , 3D camera pose가 , projection 과정이 일 때, reprojection error는 로 표현됨.
    • Projection 과정은 Image projection 과정과 Distort 과정이 함께 들어가있음.
Projection 관련 수식 --- - Image projection - Radial / Tangential distortion ---
  • 이러한 Image projection 과정은 Non-linear하기 때문에, Gauss-Newton이나 Levenberg-Marquardt optimisation과 같은 non-linear optimisation을 통해 최적화해야한다.
    • Least-squares 형태로 최적화 문제를 만들고 모든 입력 데이터가 Gaussian 형태를 따른다는 전제를 만들면, 최적화 문제가 Maximum likelihood estimation이 된다.
      • 즉, 이 최적화 문제의 해가 statistically optimal하게 된다.
    • Gauss-Newton이나 Levenberg-Marquardt 에 대한 자세한 내용은 이 글에서 설명한다.
    • Gauss-Newton을 예시로 들면, iteration을 수행하기 위해 문제를 풀어 iteration을 위한 이동치를 구한다.

Parameter 갯수

  • 우리가 구해야하는 parameter는 3D landmark position (3) + Extrinsic parameters (6) + Intrinsic parameters (5) + Scale factor (1), 1개의 3D landmark당 총 15개이다.
    • 물론 동일한 포인트를 다른 시점에서 보면 당연히 더 늘어난다.
    • 아래 예시를 보면, parameter의 수는 엄청나게 커진다.

이미지 출처: Cyrill Stachniss 교수님 렉처

  • Parameter의 수가 많으면, 문제에서 매트릭스도, 매트릭스도 엄청나게 커진다.
    • 위의 예제를 예시로 들면, 매트릭스만 보았을 때 2.5TB의 용량을 차지한다.
  • 하지만 매트릭스의 대부분은 비어있다 (i.e. sparse matrix)
    • 왜냐하면 연결되어있는 Factor 끼리만 error를 측정할 수 있기 때문이다.

Sparsity

  • 2개의 Factor간의 매트릭스는 sparse matrix 형태를 가진다.
    • 하지만 매트릭스 전체는 들의 sum이기 때문에, dense matrix 형태를 가진다.
  • 2개의 Factor간의 매트릭스 역시 sparse matrix 형태를 가진다.
    • Dense matrix의 형태를 가지는 매트릭스와는 다르게, 매트릭스는 sparse matrix 형태를 가진다.

이미지 출처: AirLab Summer School SLAM backend 영상
(마지막 H 매트릭스 그림이 symmetric 해야하는데… 잘못 그렸다 :( )

Sparse matrix 계산

  • matrix는 symmetric하고 positive-definite하다는 특성을 보인다.
    • 그렇기 때문에, 거대한 dense matrix의 inverse를 구하는것보다 decomposition하는 것이 훨씬 효율적이다.
  • Symmetric하고 positive-definite한 매트릭스에 걸 수 있는 decomposition 방식에는 2가지가 있다.
    • Cholesky decomposition
    • LU decomposition
    • 보통 Cholesky decomposition이 LU decomposition 보다 약 2배정도 빠르기 때문에 이 방법을 많이 사용한다.