7.132 번들 조정 문제와 희소 구조 활용

1. 번들 조정의 정의

번들 조정(Bundle Adjustment, BA)은 다시점 영상으로부터 카메라 포즈와 3차원 점의 위치를 동시에 최적화하는 비선형 최소 제곱 문제이다. “번들“은 3차원 점에서 카메라 중심으로 향하는 광선 다발(bundle of rays)을 의미하며, 이 광선들이 영상 평면에서의 관측과 최적으로 일치하도록 파라미터를 조정한다.

2. 문제의 정식화

$N_c$ 개의 카메라와 $N_p$ 개의 3차원 점이 주어질 때, 재투영 오차(reprojection error)를 최소화한다.

$\min_{\{\mathbf{c}_i\}, \{\mathbf{p}_j\}} \quad \sum_{(i,j) \in \mathcal{O}} \lVert \mathbf{z}_{ij} - \pi(\mathbf{c}_i, \mathbf{p}_j) \rVert^2_{\boldsymbol{\Sigma}_{ij}^{-1}}$

여기서 $\mathbf{c}_i$ 는 $i$ 번째 카메라의 파라미터(위치, 자세, 내부 파라미터), $\mathbf{p}_j$ 는 $j$ 번째 3차원 점, $\mathbf{z}_{ij}$ 는 카메라 $i$ 에서 관측된 점 $j$ 의 영상 좌표, $\pi$ 는 투영 함수, $\mathcal{O}$ 는 관측 가능한 (카메라, 점) 쌍의 집합이다.

3. 야코비안의 희소 구조

번들 조정의 야코비안 $\mathbf{J}$ 는 특징적인 블록 희소(block-sparse) 구조를 갖는다. 각 잔차 $\mathbf{r}_{ij} = \mathbf{z}_{ij} - \pi(\mathbf{c}_i, \mathbf{p}_j)$ 는 카메라 $\mathbf{c}_i$ 와 점 $\mathbf{p}_j$ 에만 의존하므로, 야코비안의 비영(nonzero) 블록은 해당 카메라 열과 해당 점 열에만 존재한다.

$\frac{\partial \mathbf{r}_{ij}}{\partial \mathbf{c}_k} = \begin{cases} \mathbf{A}_{ij} & k = i \\ \mathbf{0} & k \neq i \end{cases}, \quad \frac{\partial \mathbf{r}_{ij}}{\partial \mathbf{p}_l} = \begin{cases} \mathbf{B}_{ij} & l = j \\ \mathbf{0} & l \neq j \end{cases}$

따라서 야코비안을 카메라 부분과 점 부분으로 분할하면 다음과 같다.

$\mathbf{J} = [\mathbf{J}_c \; \mathbf{J}_p]$

정규 방정식 $\mathbf{J}^T\mathbf{J}\mathbf{d} = -\mathbf{J}^T\mathbf{r}$ 의 행렬은 다음의 블록 구조를 갖는다.

$\begin{bmatrix} \mathbf{U} & \mathbf{W} \\ \mathbf{W}^T & \mathbf{V} \end{bmatrix} \begin{bmatrix} \Delta\mathbf{c} \\ \Delta\mathbf{p} \end{bmatrix} = \begin{bmatrix} \mathbf{e}_c \\ \mathbf{e}_p \end{bmatrix}$

여기서 $\mathbf{U} = \mathbf{J}_c^T\mathbf{J}_c$ 는 카메라-카메라 블록 대각, $\mathbf{V} = \mathbf{J}_p^T\mathbf{J}_p$ 는 점-점 블록 대각, $\mathbf{W} = \mathbf{J}_c^T\mathbf{J}_p$ 는 카메라-점 교차 블록이다. $\mathbf{V}$ 는 블록 대각(각 점이 독립)이므로 역행렬이 용이하다.

4. 슈어 보수에 의한 효율적 해법

점 변수를 슈어 보수로 소거하면 카메라 변수만의 축소 시스템을 얻는다.

$(\mathbf{U} - \mathbf{W}\mathbf{V}^{-1}\mathbf{W}^T)\Delta\mathbf{c} = \mathbf{e}_c - \mathbf{W}\mathbf{V}^{-1}\mathbf{e}_p$

축소된 카메라 시스템(Reduced Camera System)의 크기는 $6N_c \times 6N_c$ (또는 내부 파라미터 포함 시 더 큼)로, 원래 시스템의 크기 $(6N_c + 3N_p) \times (6N_c + 3N_p)$ 에 비해 현저히 작다. 통상 $N_p \gg N_c$ 이므로 이 축소가 매우 효과적이다.

축소 시스템을 풀어 $\Delta\mathbf{c}$ 를 구한 후, 후방 대입으로 $\Delta\mathbf{p}$ 를 결정한다.

$\Delta\mathbf{p} = \mathbf{V}^{-1}(\mathbf{e}_p - \mathbf{W}^T\Delta\mathbf{c})$

5. 계산 복잡도

방법	복잡도
밀집 정규 방정식	$O((6N_c + 3N_p)^3)$
슈어 보수 축소	$O(N_c^3 + N_c^2 N_p)$
희소 촐레스키	구조 의존
PCG(사전 조건화 CG)	반복당 $O(N_c N_p)$

대규모 번들 조정(수천 카메라, 수십만 점)에서는 축소 시스템조차 밀집 행렬로 처리하기 어렵고, 사전 조건화 켤레 그래디언트법(PCG)이 사용된다.

6. 로봇 공학에서의 번들 조정 응용

시각 SLAM의 백엔드: 키프레임(keyframe) 기반 시각 SLAM에서 키프레임의 포즈와 맵 포인트를 번들 조정으로 정밀화한다. ORB-SLAM, VINS-Mono 등의 시스템에서 국소 번들 조정(local BA)과 전역 번들 조정(global BA)이 사용된다.

다중 카메라 캘리브레이션: 다수의 카메라로 구성된 시스템의 외부 파라미터를 번들 조정으로 동시 캘리브레이션한다.

로봇-카메라 시스템 캘리브레이션: 로봇 매니퓰레이터에 장착된 카메라의 핸드-아이 캘리브레이션을 포함한 전체 시스템의 파라미터를 번들 조정 프레임워크로 최적화한다.

7. 대표적 소프트웨어

Ceres Solver: 구글 개발, 범용 비선형 최소 제곱 해법기. 번들 조정의 희소 구조를 자동으로 활용한다.
g2o: 그래프 기반 최적화 프레임워크. SLAM과 번들 조정에 특화되어 있다.
GTSAM: 조지아텍 개발, 인수 그래프(factor graph) 기반 최적화. 증분적(incremental) 번들 조정을 지원한다.

8. 참고 문헌

Triggs, B., McLauchlan, P. F., Hartley, R. I., & Fitzgibbon, A. W. (2000). “Bundle Adjustment — A Modern Synthesis.” Vision Algorithms: Theory and Practice, Lecture Notes in Computer Science, 298–372.
Hartley, R., & Zisserman, A. (2003). Multiple View Geometry in Computer Vision (2nd ed.). Cambridge University Press.
Agarwal, S., Mierle, K., et al. (2022). Ceres Solver. http://ceres-solver.org.
Kümmerle, R., Grisetti, G., Strasdat, H., Konolige, K., & Burgard, W. (2011). “g2o: A General Framework for Graph Optimization.” Proceedings of ICRA, 3607–3613.

version: 1.0