포스트

SfM 파이프라인 — 순서 없는 사진 더미에서 카메라와 점을 세우기

게시 업데이트
By gomunamu
25 분읽는 시간
SfM 파이프라인 — 순서 없는 사진 더미에서 카메라와 점을 세우기

서론

3D Gaussian Splatting의 입력이 무엇이었는지 다시 봅시다.

사진 여러 장, 각 사진의 카메라 포즈, 그리고 초기값으로 쓸 희소 점군.

사진은 그냥 찍으면 됩니다. 나머지 둘은 어디서 오는가 — 답은 SfM(Structure-from-Motion) 이고, 실무에서는 거의 언제나 COLMAP입니다.1

이 블로그에서 그동안 다룬 에피폴라 기하, 삼각측량과 번들 조정은 SfM의 부품이었습니다. 이 글은 그 부품들이 어떤 순서로 조립되는지, 그리고 조립 과정에만 존재하는 문제들 — 어떤 사진 쌍으로 시작할지, 다음에 어떤 사진을 넣을지, 실패는 어디서 나는지 — 를 다룹니다.

SfM 파이프라인 전체 구조 증분 SfM(incremental SfM)의 표준 구조. 위쪽 파란 단계는 이미지끼리의 관계만 따지는 “대응 탐색”이고, 아래쪽 초록 단계는 실제로 3차원을 세우는 “재구성”이다.

1. 무엇을 푸는 문제인가

사진 $N$ 장, 3차원 점 $M$ 개라고 두면 미지수는 이렇습니다.

\[\underbrace{6N}_{\text{카메라 포즈}} + \underbrace{3M}_{\text{점 좌표}} \;(+\; 5N \;\text{내부 파라미터, 보정 안 됐다면})\]

관측은 “점 $j$ 가 이미지 $i$ 에서 픽셀 $(u,v)$ 에 보였다”는 2차원 값들입니다. 점 하나가 평균 $k$ 장에 보인다면 관측 개수는 $2kM$ 입니다.

\[2kM \;\gg\; 6N + 3M\]

점 하나가 3장 이상에 보이면 $2kM > 3M$ 이 되어 점 쪽은 과결정입니다. 문제는 관측이 넘친다는 게 아니라, 어느 관측이 같은 3차원 점을 가리키는지 모른다는 것입니다. SfM 파이프라인의 절반이 이 “대응 문제”에 쓰이는 이유입니다.

그리고 마지막까지 결정되지 않는 것이 하나 남습니다. 전체 스케일입니다. 장면과 카메라 배치를 통째로 두 배로 키우면 모든 사진이 똑같이 나옵니다. 단안 SfM의 결과는 언제나 스케일을 모르는 상태이고, 이건 데이터가 부족해서가 아니라 자유도 계산이 그렇게 말해 주는 원리적 한계입니다.

2. 특징 — 무엇을 대응시킬 것인가

픽셀을 통째로 비교할 수는 없습니다. 시점이 바뀌면 밝기도 모양도 다 변하니까요. 그래서 다시 찾기 쉬운 지점만 골라 씁니다.

어떤 지점이 다시 찾기 쉬울까요. 평평한 벽 한가운데의 점은 주변이 다 똑같아서 못 찾습니다. 직선 모서리 위의 점은 모서리를 따라 어디든 될 수 있습니다(구멍 문제, aperture problem). 두 방향 모두로 밝기가 변하는 지점, 즉 코너만이 위치를 하나로 특정합니다.

SIFT는 여기에 두 가지를 더합니다.2

  • 스케일 불변성 — 이미지를 여러 배율로 흐려 가며(스케일 공간) 극값을 찾으므로, 가까이서 찍든 멀리서 찍든 같은 지점이 검출됩니다.
  • 회전 불변 기술자 — 주변 그래디언트의 지배적 방향으로 좌표를 돌린 뒤, 4×4 격자 × 8방향 히스토그램 = 128차원 벡터로 기술합니다.

결과적으로 이미지 한 장이 위치 + 128차원 벡터의 목록 수천 개로 요약됩니다. 이제 이미지 비교가 벡터 비교가 됩니다.

SIFT 말고도 Harris, FAST, ORB 등 검출기와 기술자의 계보가 넓습니다. 한국어로는 다크프로그래머의 영상 특징점(keypoint) 추출방법이 이 지형도를 한 번에 보여 줍니다.

3. 매칭 — 그리고 매칭만으로는 안 되는 이유

이미지 $A$ 의 기술자 각각에 대해 이미지 $B$ 에서 가장 가까운 것을 찾습니다. 그런데 최근접 이웃을 그냥 받아들이면 오매칭이 쏟아집니다. 반복되는 창문, 벽돌, 나뭇잎처럼 비슷한 게 여러 개인 곳에서 특히 그렇습니다.

Lowe의 비율 검정(ratio test) 이 표준 해법입니다. 1등과 2등의 거리를 비교해서, 1등이 압도적이지 않으면 아예 버립니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

import numpy as np

def match_ratio(desc_a, desc_b, ratio=0.8):
    """비율 검정 + 상호 일치 검사. desc_*: (n, 128) L2 정규화된 기술자."""
    # 정규화된 벡터끼리는 내적이 클수록 가깝다
    sim = desc_a @ desc_b.T
    order = np.argsort(-sim, axis=1)[:, :2]         # 각 행의 1등, 2등
    best, second = order[:, 0], order[:, 1]

    d1 = np.sqrt(np.maximum(2 - 2 * sim[np.arange(len(sim)), best], 0))
    d2 = np.sqrt(np.maximum(2 - 2 * sim[np.arange(len(sim)), second], 0))
    keep = d1 < ratio * d2                          # 1등이 2등보다 확실히 가까울 때만

    back = np.argmax(sim, axis=0)[best]             # B에서 되짚어도 같은 것을 가리키나
    keep &= back == np.arange(len(sim))
    return np.c_[np.nonzero(keep)[0], best[keep]]

비율 0.8은 Lowe가 실험으로 고른 값입니다. 낮출수록 매칭 수가 줄고 정확도가 오릅니다.

그래도 오매칭은 남습니다. 기술자는 이미지의 국소적인 모양만 보기 때문에, 실제로 서로 다른 두 창문이 같은 모양이면 구별할 방법이 없습니다. 여기서 기하가 등장합니다.

4. 기하 검증 — 대응이 물리적으로 말이 되는가

두 이미지의 대응 집합이 주어졌을 때, 그것이 하나의 3차원 장면을 두 시점에서 본 결과일 수 있는지를 검사합니다. 이 검사의 근거가 에피폴라 기하입니다.

\[x'^\top F\, x = 0\]

절차는 RANSAC입니다.

  1. 대응 중 무작위로 7~8개를 뽑아 $F$ 를 계산한다.
  2. 전체 대응에 대해 에피폴라 선까지의 거리를 재고, 임계값 안에 드는 것(내점)을 센다.
  3. 이걸 수백~수천 번 반복해 내점이 가장 많은 $F$ 를 고른다.
  4. 내점만으로 $F$ 를 다시 정밀하게 추정한다.3

핵심은 오매칭이 서로 다른 방향으로 틀리기 때문에, 일관된 $F$ 를 만들어 내지 못한다는 것입니다. 반면 올바른 매칭들은 같은 $F$ 를 지지합니다. 다수결이 성립합니다.

RANSAC 자체를 — 반복 횟수를 어떻게 정하는지, 임계값이 결과를 얼마나 좌우하는지, M-estimator나 LMedS와는 무엇이 다른지 — 제대로 보고 싶다면 다크프로그래머의 RANSAC의 이해와 영상처리 활용이 한국어 자료 중 가장 잘 정리돼 있습니다.

이 단계에서 세 가지 모델을 함께 맞춰 보는 것이 보통입니다.

모델자유도최소 대응언제 잘 맞나
기본 행렬 $F$77일반적인 두 시점, 내부 파라미터 모를 때
필수 행렬 $E$55내부 파라미터를 알 때
호모그래피 $H$84장면이 평면이거나 카메라가 제자리 회전만 했을 때

호모그래피 자체가 어떤 변환인지 — 강체·유사·아핀을 거쳐 왜 자유도 8짜리 사영변환에 도달하는지 — 는 다크프로그래머의 2D 변환(Transformations)에 단계별로 정리돼 있고, 실제로 추정한 $H$ 가 물리적으로 말이 되는지 검사하는 방법은 Homography 보완 편이 다룹니다.

$H$ 가 $F$ 만큼 잘 맞으면 위험 신호입니다. 그 쌍은 삼각측량이 불가능한 퇴화 상황이라는 뜻이기 때문입니다. 왜 그런지는 기초 수학 글의 Q2·Q3에서 다뤘습니다. 베이스라인이 0이면 $E = 0$ 이 되고, 광선 두 개가 겹쳐 교점이 정해지지 않습니다.

5. 뷰 그래프 — 살아남은 쌍들의 지도

기하 검증을 통과한 쌍만 남기면 뷰 그래프가 만들어집니다. 노드는 이미지, 간선은 “믿을 만한 대응이 충분히 있는 쌍”입니다.

공유 점 개수 행렬과 뷰 그래프 물체 하나를 12장으로 빙 둘러 찍은 상황을 실제로 계산한 것. 왼쪽은 각 이미지 쌍이 공유하는 점 개수. 이웃한 시점끼리는 수백 개를 공유하고 반대편끼리는 0이라, 대각선 근처만 진하다. 오른쪽 위와 왼쪽 아래 모서리가 밝은 것은 1번과 12번이 다시 만나기 때문 — 즉 한 바퀴를 돌았다는 사실이 행렬에 나타난다. 오른쪽은 같은 정보를 그래프로 그린 것.

이 그림에서 읽을 것이 몇 가지 있습니다.

  • 연결이 끊기면 복원도 끊깁니다. 그래프가 두 덩어리로 나뉘면 SfM 결과도 서로 스케일과 좌표계가 다른 두 조각으로 나옵니다. 촬영할 때 시점 간격을 너무 벌리면 안 되는 이유입니다.
  • 모서리의 밝은 칸이 루프입니다. SLAM의 루프 클로저와 정확히 같은 정보이고, 이게 있으면 누적 드리프트를 잡아 줍니다.
  • 행렬이 희소합니다. $N$ 장이면 쌍은 $N(N-1)/2$ 개지만 실제로 이어지는 건 극히 일부입니다. 이 희소성이 뒤에 번들 조정을 풀 수 있게 만들어 주는 바로 그 성질입니다.

6. 어디서 시작할 것인가 — 초기 쌍 선택

이제 3차원을 세웁니다. 그런데 첫 두 장을 잘못 고르면 거기서 생긴 오차가 이후 전부에 퍼집니다. 좋은 초기 쌍의 조건은 서로 충돌합니다.

  • 대응이 많아야 한다 → 시점이 가까울수록 좋다.
  • 베이스라인이 넓어야 한다 → 시점이 멀수록 좋다.

삼각측량 글에서 봤듯, 베이스라인이 좁으면 광선 두 개가 거의 평행해져서 깊이 오차가 폭발합니다. 그래서 실무 기준은 대략 이렇습니다.

  1. 내점이 충분히 많을 것 (수백 개 이상).
  2. 호모그래피로는 잘 설명되지 않을 것. $H$ 의 내점 비율이 $F$ 의 내점 비율에 육박하면 탈락시킵니다. 평면이거나 회전뿐이라는 뜻이니까요.
  3. 삼각측량된 점들의 시차각(triangulation angle) 이 충분할 것.

고른 쌍에서 $E$ 를 분해해 $R, t$ 를 얻고(부호 조합 네 가지 중 점이 두 카메라 앞에 오는 것 하나를 고릅니다), 대응을 삼각측량하면 첫 점군이 생깁니다. 여기서 $|t| = 1$ 로 두는데, 이 임의의 선택이 곧 전체 재구성의 스케일이 됩니다.

7. 한 장씩 늘려 가기 — PnP와 다음 이미지 선택

이제 반복입니다. 이미 3차원 점이 좀 생겼으니, 새 이미지에 대해서는 2D–3D 대응이 생깁니다. “이 이미지의 이 특징은, 이미 복원된 저 3차원 점이다.”

이 상태에서 카메라 포즈만 구하는 문제를 PnP(Perspective-n-Point) 라고 합니다. 최소 3점이면 유한 개의 해가 나오고(P3P), 네 번째 점으로 그중 하나를 고릅니다. 실제로는 여기서도 RANSAC을 씁니다 — 2D–3D 대응에도 오류가 섞여 있으니까요. OpenCV로 직접 돌려 볼 때의 함수 사용법과 회전 표현 변환은 다크프로그래머의 solvePnP 함수 사용법과 Rodrigues 표현법에 정리돼 있습니다.

다음에 어떤 이미지를 넣을지는 단순한 기준으로 정합니다. 지금까지 복원된 점을 가장 많이 보는 이미지입니다.

1
2
3
4
5
6
7
8
9
10
11

def next_image(registered, vis, point_registered):
    """vis[i, j] = 이미지 i가 특징 j를 봤는가.
       point_registered[j] = 특징 j에 대응하는 3D 점이 이미 복원됐는가."""
    best, best_n = None, 0
    for i in range(len(vis)):
        if i in registered:
            continue
        n = int((vis[i] & point_registered).sum())   # 2D-3D 대응 개수
        if n > best_n:
            best, best_n = i, n
    return best, best_n        # best_n 이 임계 미만이면 더는 붙일 이미지가 없다는 뜻

새 이미지를 등록할 때마다 새 점을 삼각측량하고, 재투영 오차가 큰 점을 걷어내고, 주기적으로 번들 조정을 돌립니다. 매번 전체를 최적화하면 비싸므로 보통 방금 추가된 근처만 푸는 지역 BA를 자주 돌리고, 전체 BA는 가끔 돌립니다. 이 구조는 SLAM의 프론트엔드/백엔드 분리와 같은 발상입니다. 다른 점은 SfM에는 실시간 제약이 없어서 훨씬 자주, 훨씬 크게 풀 수 있다는 것입니다.

8. 증분 SfM과 전역 SfM

지금까지 설명한 방식이 증분(incremental) SfM입니다. 강건하지만 이미지 수에 대해 대략 제곱에 가깝게 느려지고(반복되는 BA 때문), 드리프트가 쌓입니다.

전역(global) SfM은 순서를 바꿉니다.4 먼저 모든 쌍의 상대 회전을 구해 회전 평균화(rotation averaging) 로 전역 회전을 한꺼번에 풀고, 그다음 위치를 풀고, 마지막에 BA를 한 번 돕니다. 훨씬 빠르지만 잘못된 상대 포즈 하나에 전체가 흔들리기 쉽습니다. 실무에서 COLMAP(증분)이 기본값처럼 쓰이는 이유는 결국 강건성입니다.

9. 결과물, 그리고 실패하는 곳

COLMAP의 출력은 세 덩어리입니다.

  • cameras — 내부 파라미터 $K$ 와 왜곡 계수
  • images — 이미지마다 회전(쿼터니언)과 평행이동, 그리고 2D 특징이 어느 3D 점에 대응하는지
  • points3D — 3차원 좌표, 색, 그리고 이 점을 본 이미지 목록(track)

3DGS는 이 셋을 전부 씁니다. 포즈로 렌더링하고, 점군 자리에 가우시안을 하나씩 놓고 시작합니다.

실패는 대체로 정해진 곳에서 납니다.

상황무슨 일이 일어나나
텍스처 없는 벽·하늘특징이 안 잡혀 대응이 없다. 그 영역은 점군에 구멍으로 남는다
반복 패턴 (타일, 창문)오매칭이 일관되게 생겨 RANSAC도 속는다. 재구성이 접히거나 겹친다
제자리 회전만 한 촬영베이스라인이 0이라 삼각측량 불가. $H$ 검사에서 걸러진다
반사·투명 물체특징의 3차원 위치가 시점마다 달라 애초에 강체 가정이 깨진다
사진이 너무 적거나 간격이 넓음뷰 그래프가 끊겨 조각난 재구성이 나온다

3DGS 입장에서 중요한 건, 이 실패가 조용하다는 점입니다. SfM은 실패해도 그럴듯한 숫자를 내놓습니다. 포즈가 조금 틀어진 채 3DGS를 돌리면 학습은 진행되지만, 가우시안이 그 오차를 흡수하려고 엉뚱한 모양으로 뭉개집니다. 결과물이 이상하면 3DGS 하이퍼파라미터부터 만지기 쉬운데, 먼저 의심할 곳은 대개 SfM 쪽입니다.

10. 그래서 SfM 점군이 왜 좋은 초기값인가

3DGS가 가우시안을 무작위로 뿌려도 학습은 됩니다. 다만 훨씬 오래 걸리고 결과도 나쁩니다. SfM 점군이 좋은 출발점인 이유는 이렇습니다.

  • 이미 기하 검증을 통과한 점들입니다. 여러 시점에서 일관되게 보였다는 증거가 있습니다.
  • 표면 위에 있습니다. 빈 공간에 놓인 가우시안은 학습 과정에서 지워지는 데 시간이 걸리는데, 그 낭비가 없습니다.
  • 밀도가 장면의 정보량을 따라갑니다. 무늬가 많은 곳에 점이 많이 생기는데, 마침 거기가 가우시안이 많이 필요한 곳입니다.

다만 SfM 점군은 희소하고 편향돼 있습니다. 텍스처 없는 면에는 점이 없습니다. 3DGS가 학습 도중 가우시안을 복제·분할하는 밀도 조정(densification) 을 하는 이유가 이 결핍을 메우기 위해서입니다.

그리고 이 “희소한 점군을 촘촘하게 만든다”는 문제는 3DGS가 처음 푼 게 아닙니다. 고전적인 답이 이미 있었고, 그게 다음 글의 주제인 MVS입니다.

이 시리즈 — 3DGS를 읽기 위한 기초지식

  1. MLP와 역전파
  2. SGD에서 Adam까지
  3. SfM 파이프라인 ← 지금 읽는 글
  4. MVS — 밀집 복원
  5. 래스터화
  6. 알파 블렌딩과 볼륨 렌더링
  7. 구면 조화 함수
  8. 미분 가능 렌더링
  9. NeRF
  10. 3D Gaussian Splatting ← 도착지

참고문헌

  1. Schönberger, J. L., & Frahm, J.-M. (2016). Structure-from-Motion Revisited. CVPR. — COLMAP 논문. 초기 쌍 선택, 다음 뷰 선택, 삼각측량 강건화의 실무적 개선이 정리돼 있다. ↩︎

  2. Lowe, D. G. (2004). Distinctive image features from scale-invariant keypoints. IJCV, 60(2), 91–110. — SIFT. 비율 검정은 7.1절. ↩︎

  3. Fischler, M. A., & Bolles, R. C. (1981). Random sample consensus. Communications of the ACM, 24(6), 381–395. — RANSAC 원논문. 예제가 마침 PnP다. ↩︎

  4. Hartley, R., & Zisserman, A. (2004). Multiple View Geometry in Computer Vision (2nd ed.). Cambridge University Press. — 18장이 SfM 전체 파이프라인. ↩︎

Robotics Vision
sfm structure-from-motion colmap feature-matching sift ransac pnp bundle-adjustment view-graph 3d-reconstruction
이 기사는 저작권자의 CC BY-NC-ND 4.0 라이센스를 따릅니다.

License

CC BY-NC-ND 4.0

이 포스트는 CC BY-NC-ND 4.0 라이선스로 제공됩니다. 출처 표시는 필요하며, 상업적 이용과 변경은 허용되지 않습니다.