Slam 5-2강 (Numeric of the Bundle Adjustment) 요약

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

0. Today’s Goal

• Bundle Adjustment 파헤치기
• Example of Bundle Adjustment
• BA without Control Points
• Summary

1. 강의 및 강의 자료

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

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

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

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

• The Numerics of Bundle Adjustment (Cyrill Stachniss)
• SLAM DUNK Season 2 - Numeric of the Bundle Adjustment

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

2. Bundle Adjustment 파헤치기

이번 강의 요약은 지난 포스팅 “Slam 5-1강 (The Basics about Bundle Adjustment) 요약“에서 진행했던 Bundle Adjustment를 실제로 어떻게 사용하는지 설명을 해보겠다.

강의 초반에는 Bundle Adjustment의 개념 설명을 간략히 해주신다.

위 슬라이드의 내용을 이해한 다음, 이번 포스팅을 참고하는 것을 추천한다.
위 슬라이드에 대한 내용은 지난 포스팅 (Slam 5-1강)에 해놓았다.

식을 정의하였다면 Least squares approach를 사용하여 최적화를 진행한다.

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

하지만 우리가 아는 Least squares approach를 사용하기 위해 식을 위와 같이 세우면 우리가 원하는 시간 안 (real-time)에 이 문제를 해결하지 못한다. 따라서 이번 강의에서 어떤 기술로 우리가 원하는 시간에 Bundle Adjustment를 수행할 수 있는지 알아볼 것이다.

3. Example of Bundle Adjustment

예를 들어 한번 알아보도록 하자.

검은색 line을 따라 UAV가 움직이고 있고, 49개의 map points가 있다고 가정하자. 그리고 꼭지점쪽에 삼각형으로 되어있는 points는 control points로 map points의 위치를 정확히 아는 points이다. 즉, 최적화를 하는 대상이 아니다. (최적화 해야할 map points는 전체 49개에서 4개의 control points를 뺀 45개의 map points이다.) 정사각형으로 표시된 것이 한 이미지를 나타낸 것인데, 첫번째 이미지에서는 총 6개의 map points들이 관찰되었고, 두번째부터 9개의 map points들이 관찰되었다.

이 예시의 구성은 아래와 같다.

• 6개의 image에서 6개의 points가 관찰된다.
• 15개의 image에서 9개의 points가 관찰된다.
• Observation의 갯수는 342이다.
  (관찰되는 이미지 points : $(66) + (159) = 171$ , x좌표와 y좌표가 있으므로 2배를 해준다.)
• Unknown parameters : 261이다.
  (45개의 map points에 대해서 x,y,z 좌표 정보 : $45 * 3 = 135$,
  21개의 이미지에 대한 6DoF 정보 : $21*6 = 126$, 이 두 정보를 더한 값)

식 변형하기

우리가 계산의 편의성을 위해서 식을 변형해준다.

$\Delta l$ : Observation
$v$ : correction
$A$ : Jacobian Matrix
$\Delta x$ : unknown variables

이라고 정의를 하고 $\Delta x$ 를 3D map points에 대한 변수와 6DoF에 대한 정보로 쪼개준다.

그럼 변형된 식은 다음과 같다. 쪼개진 $\Delta x$ 에 맞추어 $A$ 행렬도 나누어준다.

따라서 $i$번째 3D Map point, $j$번째 이미지(=카메라)에서 바라본 error equation은 아래와 같다.

$U$는 unknown paraeters의 갯수이다. 그냥 변형된 식에 맞추어 쪼갰다고 생각하면 된다.

Jacobian matrix를 쪼개는 것이 이 식 변형의 핵심인데, 이렇게 되면 우리가 고려하는 parameter에 필요한 성분을 가지고 있는 Matrix만 가지고 계산을 진행할 수 있기 때문이다. 즉, Jacobian matrix의 크기를 줄여 우리가 원하는 시간(real-time)에 계산을 진행하는 것이다.

조금만 생각해보면 Jacobian Matrix $A$에는 우리가 고려하는 성분 이외에는 무수히 많은 0으로 채워져 있는데, 이는 사실 최적화를 고려할 대상이 아니다. 따라서 식의 변형을 통해서 볼 필요 없는 성분 (0으로 채워져 있는 성분)을 제거하여 계산량을 줄였다고 생각하면 된다.

Jacobian matrix를 시각화하면 아래와 같다. 검은색 부분을 제외하면 모든 성분은 0이다.

$B$ Matrix와 $C$ Matrix의 모양이 규칙적인 이유는 UAV의 trajectory가 일정하기 때문이다.

$C$ Matrix에 대해서 특징은 아래와 같다.

• 2x3 크기의 sub-martices $C^T_{ij}$로 이루어져 있다.
• 성분들이 의미하는 것은 실제 이미지에서 뽑아낸 특징점 $x’_{ij}$과 3D point $\hat{X_i}$의 관계이다.

$B$ Matrix에 대해서 특징은 아래와 같다.

• 2x6 크기의 sub-martices $B^T_{ij}$로 이루어져 있다.
• 성분들이 의미하는 것은 실제 이미지에서 뽑아낸 특징점 $x’_{ij}$과 카메라(이미지) orientation $j^{th}$의 관계이다.

변형한 식으로 최적화 진행하기

그렇다면 일반적인 경우에 $B$ Matrix와 $C$ Matrix를 어떻게 계산하고 찾아낼까?

실제로는 여러 math tool들을 활용한다.

• Compute Jacobians analytically : 식을 세우고 미분 값을 구하는 정석적인 방법
• Compute Jacobians numerically : 이번 강의에서 주로 다루눈 내용

우리가 결국 하려고 하는 것은 Least squares approach로 non-linear optimization을 하는 것이다.

따라서 우리는 아래와 같은 Matrix를 구해야 한다.

이러한 Normal Matrix를 $C$ Matrix, $B$ Matrix를 활용해서 나타내보면 다음과 같다.

조금 더 자세한 설명은 아래 슬라이드를 참고하자.

Orientation parameter $\Delta t$ 계산

최적화를 수행할 때 Orientation parameter만을 최적화 하는 방법을 한번 살펴보자.

여기서 간단한 식 변형을 사용할 것인데 직관적으로 보면 왜 하는지 이해가 되지 않지만, Orientation parameter만을 최적화를 하기 위해서 강제로 식 변형을 해줬다고 생각하자.

순서대로 진행하여 맨 아래의 block에서 식을 만들어 낸다.

Matrix를 시각화하면 아래와 같다. 검은색 부분이 non-zero 성분이고, 하얀색이 zero 성분이다.

이제 실제로 계산을 진행하면 아래와 같다.

슬라이드에서도 언급했지만, $N_{kk}$ Matrix는 Diagonal Matrix이기 때문에, 계산량이 그렇게 많지 않다.

이 식을 풀게 되면 Orientation parameter $\Delta t$를 알 수 있게된다.

Map points parameter $\Delta k$ 계산

이제 $\Delta t$를 구했으므로, 얻은 값을 이용해서 Map points parameter $\Delta k$를 구한다.

위 식에서 Upper block의 식을 활용하여 $\Delta k$에 대한 식을 구하면 아래와 같다.

위 식을 $\Delta k$에 대해 정리하면 아래와 같다.

지금까지 이야기한 과정을 정리해보면 다음과 같다.

우선 $N$ Matrix의 성분을 계산한다.

그 다음 아래 슬라이드의 $\overline{N_{tt}}$ 와 $\overline{h_{t}}$ 를 계산한다.

위 식에서 $\Delta t$ 를 계산한 후, 아래의 식을 이용하여 $\Delta k$ 를 계산한다.

4. BA without Control Points

Control Points는 Map points들 중에서 위치를 알고 있는 Points들을 뜻한다.
Control Points가 없다는 것은 Reference frame이 정의되어 있지 않다는 것과 같은 의미이다.

이러한 경우 어떤 문제가 발생할까?

Normal equation에서 Rank deficiency가 일어난다. 이러한 현상을 Gauge-freedom이라고 한다.

따라서 추가적인 Constraints를 붙여 Datum(기준)을 만들어준다.

추가할 수 있는 Constraints는 다음과 같다.

• 3D points들의 무게 중심은 변하지 않는다고 가정한다. (Translation에 대한 Constraints)
• Main direction을 고정한다. (Rotation에 대한 Constraints)
• Points간의 평균적인 거리를 고정한다. (Scale에 대한 Constraints)

Constraints Matrix를 $H$로 정의하고, 최적화를 진행할 때 Matrix에 대한 정보를 활용하면 Rank deficiency를 해결할 수 있다.

Outlier 제거하기

기본적으로 Noise를 Gaussian distribution으로 가정을 하기 때문에 이차식을 만들어 최적화를 진행했는데, 실제 현실 세계에서는 그렇지 않은 경우가 훨씬 많다.

이 때 Robust kernel을 활용하여 Outlier에 강인한 Error minimization을 수행할 수 있다.

좋은 Initial guess를 가지고 있다면 Blake-Zisserman과 같은 kernel을 사용하는 것이 효율적이지만, Initial guess를 좋게 만들 수 없다면 Huber kernel을 사용하는 것을 추천하셨다.

계속 강조하지만 아래와 같은 Robust Kernel의 사용도 추천하셨다.

5. Summary

이번 강의로 Bundle Adjustment를 실제로 수행할 때 사용하는 기법들에 대해서 알아보았다.

Bundle Adjustment란 불확실성을 고려하여 Relative 그리고 Absolute Orientation을 찾아내는 방법이고, 여기서 사용하는 error를 reprojection error라고 한다. Least squares appraoch를 사용하여 최적화를 진행한다.

효울적으로 Bundle Adjustment를 푸는 방법의 핵심은 Sparse solver에 있다. 즉, 행렬에 0 성분이 많은 점을 활용하여 효율적으로 계산을 진행하는 것이다.

우리가 찾아야 하는 paramters는 Orientation parameters와 Map point parameters로 이루어져 있다. Orientation parameters를 먼저 계산하여 찾은 다음, Map point parameters를 찾으면 조금 더 빠르게 parameters를 구할 수 있다.

이번 강의를 통해서 실제로 Bundle Adjustment를 어떻게 수행하는지 상세히 알 수 있었다. 😄😄