번들 조정

1. 개요[편집]

번들 조정 Bundle Adjustment
미지수	카메라 자세·내부파라미터 와 3차원 점 좌표 — 동시에
목적함수	재투영 오차의 제곱합
푸는 도구	가우스-뉴턴법 · 레벤버그-마쿼트 방법
결정적 트릭	슈어 보수로 점 블록 소거 → 축소 카메라계
게이지 자유도	단안 기준 7 (회전 3 + 이동 3 + 스케일 1)
대표 구현	Ceres Solver · g2o · GTSAM

카메라도 모르고 점도 모른다. 아는 것은 “이 점이 이 사진의 이 화소에 찍혔다”뿐이다. 그걸 몇백만 개 모아 놓고 전부 한꺼번에 푼다.

번들 조정(bundle adjustment, BA)은 여러 영상에서 관측된 특징점의 화소 위치를 입력으로, 카메라의 자세(및 필요하면 내부파라미터)와 3차원 점의 좌표를 동시에 미지수로 놓고 재투영 오차의 제곱합을 최소화하는 비선형 최소자승 문제다. Structure from Motion·SLAM·포토그래메트리·다중 시점 스테레오가 마지막에 반드시 한 번씩 지나가는 관문이며, 이 분야에서 “정답”이라 부를 수 있는 유일한 추정량이 여기서 나온다.

이름은 광선의 다발(bundle)에서 왔다. 3차원 점 하나에서 나와 모든 카메라 중심으로 향하는 광선 다발, 그리고 카메라 중심 하나에서 모든 점으로 향하는 광선 다발이 격자처럼 얽혀 있고, 이 다발 전체를 관측과 가장 잘 맞도록 조정(adjust)한다는 뜻이다. 「조정」은 측지·사진측량에서 관측 잉여를 최소자승으로 배분하는 작업을 가리키는 오래된 용어이므로, 번들 조정은 사실 컴퓨터 비전이 발명한 것이 아니라 사진측량에서 물려받은 유산이다.¹

주의할 점 하나. 국내 구조공학·측량 문헌에서 말하는 「근접 번들법」과는 완전히 다른 문제다. 이름이 겹치는 것은 둘 다 사진측량 계열 용어를 번역했기 때문일 뿐이다.

2. 문제 정식화[편집]

카메라 $m$ 대, 3차원 점 $n$ 개, 그리고 점 $j$ 가 카메라 $i$ 에 보였는지를 나타내는 가시성 지시자 $v_{ij}\in\{0,1\}$ 를 두자. 관측 화소를 $\mathbf x_{ij}$, 투영 모형을 $\pi(\cdot)$ 라 하면 목적함수는 한 줄이다.

$$\min_{\{\mathbf P_i\},\,\{\mathbf X_j\}} \; \sum_{i=1}^{m}\sum_{j=1}^{n} v_{ij}\,\bigl\lVert\, \mathbf x_{ij} - \pi(\mathbf P_i,\, \mathbf X_j) \,\bigr\rVert^{2}$$

$\pi$ 는 카메라 보정에서 다루는 그 투영이다. 점을 카메라 좌표계로 옮기고($R\mathbf X + \mathbf t$), 원근분할하고, 렌즈 왜곡을 얹고, 내부행렬 $K$ 를 곱한다. 자세는 벡터 공간이 아니라 리 군 $SE(3)$ 의 원소이므로 증분은 접공간에서 잡아 지수사상으로 되돌린다 — 그러지 않으면 회전행렬의 직교성이 반복마다 조금씩 깨진다.

이 목적함수가 최대우도추정이라는 근거도 분명하다. 화소 관측 잡음이 등방 가우시안이고 관측끼리 독립이라면, 최대우도추정이 정확히 재투영 오차 제곱합의 최소화가 된다. 즉 BA는 “그럴듯해 보이는 비용함수”가 아니라 가정 아래에서 최적인 추정량이다. 반대로 말하면 그 가정(등방·독립·이상치 없음)이 깨지는 순간 최적성도 함께 깨지므로, 아래의 강건 손실 이야기가 반드시 따라붙는다.

규모 감각을 먼저 잡아 두는 게 좋다. 사진 3000장, 점 100만 개짜리 도시 규모 재구성이면 미지수는 대략 $6\times3000 + 3\times10^6 \approx 3{,}018{,}000$ 개, 잔차는 관측 수의 2배로 수천만 개다. 이걸 조밀 행렬로 다루겠다는 생각은 시작부터 폐기해야 한다.

3. 가우스-뉴턴과 레벤버그-마쿼트[편집]

미지수를 모두 이어 붙인 벡터를 $\mathbf p$, 잔차 벡터를 $\mathbf r(\mathbf p)$ 라 하면 표준적인 비선형 최소자승 반복이다. 자코비안 행렬 $J = \partial \mathbf r/\partial\mathbf p$ 에 대해 매 반복

$$(J^{\mathsf T} J)\,\Delta\mathbf p = -J^{\mathsf T}\mathbf r$$

를 풀고 $\mathbf p \leftarrow \mathbf p \oplus \Delta\mathbf p$ 로 갱신하는 것이 가우스-뉴턴법이다. 2차 미분 없이 $J^{\mathsf T}J$ 로 헤세 행렬을 근사하는 것이 최소자승 구조의 선물이며, 그래서 BA는 진짜 뉴턴법을 쓰지 않는다.

실무 표준은 감쇠를 붙인 레벤버그-마쿼트 방법이다.

$$\bigl(J^{\mathsf T} J + \lambda\, \mathrm{diag}(J^{\mathsf T}J)\bigr)\,\Delta\mathbf p = -J^{\mathsf T}\mathbf r$$

BA에서 감쇠가 특히 중요한 이유는 두 가지다. 첫째, 점 하나가 카메라 두 대에만 보이고 그 두 시선의 교차각이 1° 미만이면 그 점의 깊이 방향은 사실상 결정되지 않아 $J^{\mathsf T}J$ 가 특이에 가까워진다(조건수가 폭발한다). 둘째, 아래에서 볼 게이지 자유도 때문에 $J^{\mathsf T}J$ 는 원리적으로 특이하다. $\lambda$ 항이 이 두 문제를 동시에 덮어 주므로, 감쇠 없이 돌린 BA가 촐레스키에서 죽는 것은 버그가 아니라 정상이다.

수렴 감각도 짚어 두자. 좋은 초기값(SfM이나 SLAM 프런트엔드가 준 값)에서 출발하면 재투영 RMS는 보통 5~15 반복 안에 평평해지고, 그 뒤로는 소수점 셋째 자리만 움직인다. 반복을 100번 돌려야 줄어드는 상황은 초기값이나 데이터 연관이 잘못됐다는 신호이지 최적화 설정 문제가 아닌 경우가 압도적으로 많다.

4. 희소성 — 야코비안은 두 갈래로 갈라진다[편집]

BA를 가능하게 만든 것은 알고리즘이 아니라 구조다. 잔차 $\mathbf r_{ij}$ 는 카메라 $i$ 와 점 $j$ 에만 의존하고 나머지 전부에 대해 미분이 0이다. 미지수를 「카메라 전부, 그다음 점 전부」 순으로 정렬하면 $J = [\,A \;\;|\;\; B\,]$ 로 갈라지고 정규방정식 행렬이 다음 2×2 블록 구조를 갖는다.

$$H = J^{\mathsf T}J = \begin{pmatrix} U & W \\ W^{\mathsf T} & V \end{pmatrix}$$

• $U$ — 카메라-카메라 블록. $6\times 6$(또는 내부파라미터를 넣으면 $9\times9$) 블록들의 블록 대각행렬. 두 카메라는 직접 잔차를 공유하지 않기 때문이다.
• $V$ — 점-점 블록. $3\times3$ 블록들의 블록 대각행렬. 두 점도 직접 얽히지 않는다.
• $W$ — 카메라-점 결합 블록. $v_{ij}=1$ 인 자리만 채워진 매우 희소한 행렬.

즉 $H$ 는 대각 두 덩어리와 희소한 연결부로 이루어진 희소행렬이다. 카메라와 점을 뒤섞어 정렬하면 이 구조가 보이지 않게 되므로, 변수 순서가 알고리즘의 일부다.

5. 슈어 보수와 축소 카메라계[편집]

여기서 대규모 BA를 성립시킨 단 하나의 트릭이 나온다. $V$ 가 블록 대각이라 $V^{-1}$ 이 $3\times3$ 역행렬 $n$ 개로 거의 공짜라는 사실을 이용해, 점 증분 $\Delta\mathbf p_{X}$ 를 대수적으로 소거한다. 블록 가우스 소거법을 한 번 적용하면(슈어 보수)

$$\underbrace{\bigl(U - W V^{-1} W^{\mathsf T}\bigr)}_{S}\,\Delta\mathbf p_{C} \;=\; -\,\bigl(\boldsymbol\varepsilon_C - W V^{-1}\boldsymbol\varepsilon_X\bigr)$$

를 얻는다. 여기서 $\boldsymbol\varepsilon_C = A^{\mathsf T}\mathbf r$, $\boldsymbol\varepsilon_X = B^{\mathsf T}\mathbf r$ 다. 이 $S$ 를 축소 카메라계(reduced camera system)라 부르고, 크기가 $6m \times 6m$ — 앞의 도시 규모 예에서 3백만이 1만 8천으로 줄어든다. 이걸 풀어 카메라 증분을 얻은 뒤, 점 증분은 역대입으로

$$\Delta\mathbf p_{X} = -V^{-1}\bigl(\boldsymbol\varepsilon_X + W^{\mathsf T}\Delta\mathbf p_{C}\bigr)$$

로 블록마다 독립적으로 복원한다. 점이 카메라보다 수백 배 많은 구조를 정확히 반대로 이용한 셈이다.

$S$ 의 성김에 대한 감각도 중요하다. $S$ 의 $(i,k)$ 블록은 카메라 $i$ 와 $k$ 가 점 하나라도 공유할 때만 0이 아니다. 즉 $S$ 의 희소 패턴은 곧 공시성 그래프(co-visibility graph)의 인접행렬이다. 그래서 카메라들이 한 줄로 지나가는 주행 영상에서는 $S$ 가 띠행렬에 가깝고, 관광지 사진처럼 모두가 같은 건물을 보는 데이터에서는 $S$ 가 조밀해진다. 전자는 좋은 변수 순서(COLAMD 등)를 얹은 희소 촐레스키 분해로 순식간에 풀리고, 후자는 $6m$ 이 커지는 순간 $O(m^3)$ 에 잡아먹힌다.

그 벽을 넘는 표준 처방이 비정확 뉴턴(inexact Newton)이다. $S$ 를 명시적으로 만들지 않고 행렬-벡터 곱만 정의해 켤레기울기법으로 풀고, 전처리기로는 $S$ 의 블록 대각(블록 자코비) 또는 공시성 그래프의 클러스터를 쓴다. 매 반복을 정확히 풀지 않아도 LM의 신뢰 영역 논리가 유지되기 때문에, 정확도를 거의 잃지 않고 사진 수만 장 규모가 열렸다.²

6. 게이지 자유도 — 답이 하나가 아니다[편집]

BA에는 원리적으로 답이 유일하지 않다. 재구성 전체를 회전·이동시키고 통째로 확대·축소해도 모든 재투영 오차가 정확히 같다. 즉 내부파라미터를 알고 있는 단안 재구성의 해는 유사변환군의 7자유도(회전 3 + 이동 3 + 스케일 1)만큼 불확정하다. 내부파라미터까지 미지수로 두고 아무 제약도 걸지 않으면 사영 재구성이 되어 불확정성이 15자유도까지 늘어난다.

이 자유도가 $H$ 의 영공간으로 나타난다. 따라서 감쇠 없는 가우스-뉴턴은 반드시 특이행렬을 만나고, 감쇠를 넣으면 문제는 풀리지만 해가 반복마다 천천히 떠다닌다. 처방은 셋 중 하나다.

방법	하는 일	대가
고정 게이지	첫 카메라 자세를 상수로 박고, 두 카메라 사이 거리 하나를 1로 고정	구현이 가장 쉽다. 고정한 변수의 오차가 나머지로 몰려 공분산 해석이 왜곡됨
사전정보 게이지	전체 자세에 약한 사전분포를 얹어 정칙화	매끄럽고 안정적. 가중치를 잘못 주면 해가 사전정보에 끌려감
자유 게이지	특이계를 의사역행렬로 풀어 최소노름 증분을 취함	통계적으로 가장 정직(공분산이 최소노름 게이지 기준). 구현이 번거로움

실무에서는 첫 번째가 압도적으로 많이 쓰이고, 논문에서 공분산이나 불확실성을 보고할 때만 자유 게이지가 등장한다. 게이지를 고정하지 않은 채 $H^{-1}$ 을 공분산이라고 보고한 표는 의미가 없다 — 그 숫자는 감쇠 계수 $\lambda$ 가 정한 값이다.³

7. 강건 손실 — 이상치 한 개가 다 망친다[편집]

제곱 손실은 잔차에 제곱으로 반응하므로, 100 픽셀 틀린 오대응 하나가 1 픽셀짜리 정상 관측 1만 개와 맞먹는 발언권을 갖는다. 특징점 매칭에서 오대응이 0인 경우는 존재하지 않으므로 강건화는 선택이 아니다.

잔차 노름 $s=\lVert\mathbf r_{ij}\rVert$ 에 대해 손실 $\rho(s)$ 를 갈아 끼운다.

손실	형태	성격
제곱	$s^2$	최대우도. 이상치에 무방비
후버	$s\le\delta$ 이면 $s^2$, 아니면 $2\delta s - \delta^2$	큰 잔차에 선형 — 영향은 유한하지만 0은 아님
코시	$c^2\log(1+s^2/c^2)$	로그로 자란다. 큰 잔차의 영향이 사실상 소멸
튜키	임계 밖은 상수	완전 절단. 강하지만 국소 최솟값을 만든다

구현은 반복 재가중 최소자승(IRLS)이다. 매 반복 잔차마다 가중치 $w_{ij} = \rho'(s)/s$ 를 계산해 $J$ 와 $\mathbf r$ 을 스케일하면, 위의 희소 구조와 슈어 보수가 그대로 유지된다 — 이것이 강건 손실이 BA에 공짜로 얹히는 이유다. 자세한 배경은 로버스트 통계 문서로 넘긴다.

한계는 분명히 알아 둘 것. 강건 손실은 프런트엔드의 RANSAC을 대체하지 못한다. 강건화는 이미 대략 맞는 해 주변에서 소수의 이상치를 눌러 주는 장치이고, 초기값이 엉망이면 정상 관측조차 큰 잔차를 갖기 때문에 무엇이 이상치인지 구별할 근거가 없다. 그래서 실무 순서는 언제나 「RANSAC으로 걸러내고 → 제곱 손실로 몇 번 → 강건 손실로 정련 → 임계 초과 관측 제거 → 다시 최적화」다. 임계값 $\delta$ 는 보통 예상 화소 잡음의 23배(13 px)로 잡는다.

8. 점진적 BA와 전역 BA[편집]

전체를 매번 다 푸는 것은 사치다. 그래서 두 축으로 타협한다.

부분 BA / 국소 BA. 최근 키프레임과 그와 점을 공유하는 이웃만 미지수로 두고, 나머지 카메라는 상수로 고정한다. 고정된 카메라에 보이는 점의 관측은 잔차로는 살려 두어 스케일과 드리프트를 붙잡아 두는 것이 요령이다. 실시간 시각 SLAM의 백엔드가 대부분 이 형태다.

증분 평활화. 새 관측이 들어올 때 $H$ 의 촐레스키 인자를 처음부터 다시 만들지 않고, 영향받는 부분만 갱신하는 방식(iSAM·iSAM2 계열). 정보행렬의 인자를 트리로 관리해 갱신 범위를 국소화한다.

전역 BA. 모든 카메라와 점을 미지수로 두고 한 번 크게 푼다. 재구성이 일정 비율 이상 커질 때, 루프를 닫은 직후, 그리고 결과물을 내보내기 전에 돌린다. 정확도의 기준선은 언제나 여기다.

정확도-비용 관계는 비대칭적이다. 국소 BA만 돌리면 오차가 국소적으로는 매우 작지만 전역적으로는 천천히 휜다 — 이것이 오도메트리식 드리프트의 정체이고, 전역 BA나 루프 클로저 없이는 원리적으로 없앨 수 없다.

9. 구현체[편집]

• Ceres Solver — 범용 비선형 최소자승 라이브러리. 잔차 블록을 함수 객체로 등록하면 자동 미분으로 야코비안을 만들어 주고, 슈어 보수 기반 solver와 여러 전처리기, 강건 손실, 다양체 파라미터화를 전부 제공한다. BA 전용은 아니지만 사실상 BA의 기준 구현.
• g2o — “일반 그래프 최적화”. 미지수를 정점, 잔차를 간선으로 놓는 그래프 추상화 위에서 희소 블록 solver를 돌린다. 시각 SLAM 연구 코드에 널리 박혀 있다.
• GTSAM — 인자 그래프와 베이즈 트리 기반. 증분 평활화(iSAM2)와 IMU 사전적분 인자가 강점이라 시각-관성 쪽에서 선호된다.
• 그 밖에 SBA·SSBA 같은 고전 전용 구현, 멀티코어·GPU로 비정확 뉴턴을 가속한 구현들이 있다.

세 라이브러리 모두 문제를 어떻게 세우느냐(파라미터화·가중치·다양체·강건 손실) 가 성능의 90%를 좌우한다. 같은 데이터에 같은 solver를 돌려도 회전을 사원수로 두고 4차원 벡터처럼 갱신하는 구현과 접공간에서 갱신하는 구현의 수렴 속도가 몇 배씩 차이 난다.

10. 현업에서의 현실[편집]

• BA는 진단 도구지 마법이 아니다. 재투영 RMS가 이상하게 낮으면(예: 0.05 px) 기뻐하기 전에 관측 수와 미지수 수의 비를 세어 봐야 한다. 두 장에만 보이는 점이 절반이면 그 점들은 자기 좌표를 스스로 맞춘 것이지 검증된 게 아니다.
• RMS는 낮은데 모델이 휘어 있는 경우가 실제로 가장 흔한 사고다. 렌즈 왜곡 모형이 틀렸거나 초점거리가 자세와 뒤엉킨(depth-focal coupling) 것이며, 원인은 거의 언제나 카메라 보정 단계에 있다.
• 야코비안을 손으로 미분해 놓고 부호 하나를 틀리면, 목적함수가 줄기는 하는데 수렴이 이상하게 느려진다. 유한차분과 대조하는 검사(자코비안 검증)를 한 번은 반드시 돌린다. 수치미분이 이럴 때만은 유용하다.
• 반복마다 시간을 재 보면 대개 $S$ 를 만드는 데 절반, 푸는 데 절반이 든다. “solver를 바꿨는데 왜 안 빨라지냐”의 답이 여기 있다.
• 점을 미지수에서 빼고 자세만 남긴 형태가 포즈 그래프 최적화다. 훨씬 싸지만 관측을 압축하는 과정에서 정보를 잃으므로, 정확도가 필요하면 결국 점을 다시 넣어야 한다.

11. 관련 문서[편집]

• Structure from Motion · 카메라 보정 · 오도메트리 · SLAM
• 에피폴라 기하 · 스테레오 비전 · 특징점 검출 · 삼각측량
• 가우스-뉴턴법 · 레벤버그-마쿼트 방법 · 신뢰 영역 방법 · 최소자승법
• 슈어 보수 · 희소행렬 · 촐레스키 분해 · 켤레기울기법 · 전처리기
• 자코비안 행렬 · 헤세 행렬 · 자동 미분 · 조건수
• 리 군 · 회전행렬 · 사원수 · RANSAC · 로버스트 통계
• Ceres Solver · 포토그래메트리

12. Footnotes[편집]

1. 항공사진으로 지형도를 만들던 사람들이 1950~60년대에 이미 광선 다발 조정을 손계산과 초기 전자계산기로 돌리고 있었다. 컴퓨터 비전이 1990년대에 “발견”한 것은 그 방법이 아니라 초기값 없이도 시작할 수 있다는 것(자동 특징 매칭과 상대자세 추정)이었다. 이 계보를 정리해 비전 쪽 용어로 옮겨 준 문헌이 트릭스 등의 Bundle Adjustment — A Modern Synthesis(2000)이고, 지금도 이 분야에서 가장 많이 인용되면서 가장 안 읽히는 논문 중 하나로 꼽힌다. ↩

2. 사진 공유 사이트에서 긁어모은 관광지 사진 수만 장으로 도시를 재구성하는 연구들이 이 방향을 밀어붙였다. 조밀한 축소 카메라계를 촐레스키로 푸는 것이 불가능해지는 지점이 대략 카메라 수천 대이고, 그 위쪽은 전부 전처리된 켤레기울기법 영역이다. 참고로 이때 “행렬을 만들지 않는다”는 말이 곱셈을 안 한다는 뜻이 아니라, 곱셈을 매번 다시 한다는 뜻이라는 점이 초심자의 함정이다. ↩

3. 특이한 $H$ 를 만나면 대각에 $10^{-9}$ 정도를 더해 넘어가는 처방이 인터넷에 널려 있다. 잘 돌아가는 것처럼 보이고 실제로 재구성 형상도 멀쩡한데, 그 순간부터 공분산 출력은 감상용이 된다. 원인을 알고 쓰는 것과 모르고 쓰는 것의 차이가 큰 대표적인 한 줄. ↩