[Paper] [Github]
Schonberger, J. L., & Frahm, J. M.
CVPR 2016

NeRF와 3DGS를 공부하다 보니 SfM 기법이 공통적으로 사용이 되고 image로 부터 3D reconstruction을 진행할 때 중요한 기법이라고 생각이 들어서 논문을 일게 되었다. SfM 방법은 이 논문 이전에 등장한 방법이며 2006년도에 나온 Photo tourism: exploring photo collections in 3D 논문은 처음으로 SfM을 이용해 인터넷 사진들에 적용한 논문으로써 기념비적 연구를 수행했다.

그리고 오늘 Review할 논문은 기존 SfM 파이프라인에서 5가지 측면에서 향상시키고 오픈소스인 COLMAP의 논문이라고 보시면 된다.

먼저 SfM의 파이프라인을 살펴보겠다.

Figure 1. Incremental Structure-from-Motion pipeline

1. Correspondence Search

1-1 Feature Extraction

각 이미지에서 feature를 추출하는 단계다. 논문에서는 scale, rotation에도 불변하는 SIFT 기법을 사용하고 있다.

Figure 2. Feautre extraction

1-2 Matching

Feature extraction에서 추출한 특징점을 바탕으로 2개의 이미지에서 동일한 장면 부분을 매칭한다. 모든 특징점을 찾아 유사한 특징점끼리 대응점을 검색하는데 이 접근법은 $O(N_{I}^{2}N_{F_{i}}^{2})$의 계산 복잡도를 가지는데 대규모 이미지에서는 사실상 불가능하다.

Figure 3. Matching

1-3 Geometric Verification

Figure 4. Scene Graph

Matching 단계에서 이어진 특징점들이 올바른지 확인하기 위해 검증하는 단계이다. matching은 외형에 따라 진행되기 때문에 투영 기하학(Projective Geometry)을 사용하여 이미지 간의 특징점을 매칭하는 변환(Transformation)을 추정함으로써 매핑을 검증한다.

이미지 쌍이 공간에서 어떻게 촬영되었는지에 따라 기하학적 관계를 설명하는 수학적 모델이 달라진다.
1. 호모그래피 (Homography, $H$)

• 카메라가 제자리에서 회전만 했거나(파노라마 촬영), 카메라가 이동하긴 했지만 평평한 평면(벽, 바닥 등)을 촬영했을 때 발생하는 기하학적 변환을 설명

2. 에피폴라 기하학 (Epipolar Geometry)

• 에센셜 행렬 (Essential Matrix, $E$) : 카메라의 초점 거리 등 내부 파라미터를 알고 있을 때(Calibrated) 사용함
• 펀더멘탈 행렬 (Fundamental Matrix, $F$) : 카메라 내부 파라미터를 모를 때(Umcalibrated) 사용함

또한 특징점 매칭 결과에는 outlier가 섞여 있기 때문에 RANSAC을 사용하여 outlier들을 걸러내고 두 이미지 간의 촬영 관계가 위에서 설명한 $H$, $E$, $F$인지 모델을 결정해야 하는데 이를 GRIC을 사용하여 가장 적절한 기하학적 모델을 선택하게 해준다.

최종적으로는 Scene Graph(장면 그래프)라는 거대한 뼈대를 출력하게 된다.(Figure 4 참조)

• node : 등록될 이미지들
• edge : 기하학적으로 검증을 통과한 이미지 쌍

2. Incremental Reconstruction

위에서 Correspondence Search로 나온 Scene Graph를 Input으로 받는 단계이다. 최종 출력으로는 이미지들의 포즈 추정치와 점들의 집합이다.

2-1 Initialization

SfM은 잘 선택된 두 장의 이미지로 모델의 초기값을 설정한다.

2-2 Image Registration

처음에 등록된 두 장의 이미지를 World 좌표계의 원점으로 둔다. 첫 번째 카메라를 기준으로 두 번쨰 카메라는 얼만큼 떨어져 있고 어느 각도로 붙어져 있는지 상대 포즈를 계산해 낸다.

이후 세번째 이미지부터는 PnP 알고리즘을 활용하여 남은 사진들을 하나식 3D 공간에 이어 붙인다. 그러나 PnP 알고리즘으로 카메라 위치를 계산할 때 outlier가 발생할 수 있으므로 RANSAC 기법을 사용한다.

Figure 5. PnP Algorithm

2-3 Triangulation

최초에는 Epipolar Geometry 개념을 이용하여 3D points를 등록한다. 이후부터 새로 등록한 이미지의 3D points들은 traingulation(삼각측량법)을 사용해서 3D point들에 추가한다.

2-4 Bundle Ajustment

Image Registration과 Triangulation 단계에서 에러를 발생시킬 수 있으므로 비선형 최적화를 추가적으로 수행한다. 이를 Bundle Ajustment(BA) 단계에서 진행한다.

$E = \sum_j \rho_j \left( \left\| \pi(\mathbf{P}_c, \mathbf{X}_k) - \mathbf{x}_j \right\|_2^2 \right)$

위 수식은 Levenberg-Marquardt 비선형 최적화 알고리즘인데 Gradient-Descent방식과 Gauss-Newton방식을 서로 보완하는 형태로 만든 알고리즘이다.

3. Contribution

SfM의 파이프라인은 위와 같으며 위 논문에서는 총 5가지의 측면에서 SfM 파이프라인을 향상시키는 방법을 제시한다.

3-1 Scene Graph Augmentation

correspondence Search 단계에서 오류가 발생하기 쉽다. 그래서 Scene Graph에 이 두 이미지는 기하학적으로 어떤 관계인지 라벨링을 달아주는 과정을 거친다.

1 일반적인 3D 환경인가? (Fundamental vs Homography)
매칭된 점들이 평면/제자리 회전 모델($H$)보다 일반적인 3D 이동 모델($F$)을 더 많이 따른다면 일반적인 환경에서 카메라가 이동하며 찍은 사진으로 분류한다.

2 파노라마인가, 진짜 평면인가? (Essential & 사잇각 계산)
카메라 내부 정보(렌즈 등)가 정확한지 검증($E$)한다. 그리고 가상으로 3D 점을 쏘아 올려 사잇각을 계산한다. 이를 통해 카메라가 제자리에서 고개만 돌려 찍은 파노라마인지 진짜 평평한 벽을 찍은 평면인지 확실하게 구별한다.

3 가짜 매칭(WTFs) 삭제
전혀 다른 장소의 사진이라도 워터마크, 날짜, 테두리가 같으면 잘못 매칭될 수 있다. 이미지 테두리의 패턴만 비정상적으로 일치하는 쌍은 가짜 매칭(WTF)으로 간주하여 그래프에서 아예 삭제한다.

4 가장 좋은 Initialization 찾기
위 검증을 마친 이미지 쌍들에 라벨(일반/파노라마/평면)을 붙는데 3D 복원을 시작할 때 "파노라마가 아니며 카메라 정보가 정확하게 보정된 쌍"을 찾아 가장 안정적인 복원 출발점으로 삼는다.

5 파노라마는 3D 계산(삼각측량) 안함
제자리에서 회전만 한 파노라마 사진은 카메라 간의 이동 거리(Baseline)가 없어 3D 점을 계산하려고 하면 수학적으로 무한대로 발산하는 오류(Degenerate)가 발생한다. 따라서 파노라마 쌍에서는 아예 삼각측량을 하지 않도록 막아 붕괴를 예방한다.

3-2 Next Best View Selection

SfM의 Image Registration 단계에서는 아직 등록되지 않은 수많은 사진 중 "어떤 이미지를 다음 순서로 추가할 것인지" 결정하는 것이 전체 3D 모델의 퀄리티를 좌우한다.

단 한 번의 잘못된 선택(불안정한 사진 등록)이 카메라 오등록과 삼각측량 실패의 연쇄 반응(Drift)을 일으켜 3D 맵 전체를 망가뜨릴 수 있기 때문이다. 따라서 가장 안정적이고 중요한 이미지를 평가하여 최우선으로 등록해야 한다.

과거에는 단순히 3D 점들이 가장 많이 보이는 사진을 선택했지만 오차가 있기 때문에 COLMAP은 점들이 이미지 전반에 얼마나 고르게 분포(Uniform)되어있는지를 동시에 평가한다. 이를 multi-resolution 분석이라고 한다.

Figure 6. Next Best View Selection

3-3 Robust and Efficient Triangulation

SfM에서 2D 픽셀들을 3D 공간의 한점으로 쏘아 올리는 과정을 triangulation(삼각측량)이라고 하는데 COLMAP에서는 강건하고 효율적인 triangulation(삼각측량) 기법을 소개한다.

1 Transitive Correspondence (전이적 연결)
A-B 사진, B-C 사진에 찍힌 공통된 점을 건너건너 연결하면 A-C 사이의 연결고리(특징점 트랙, Feature Track)를 만들 수 있다. 이렇게 두 카메라 사이의 거리(Baseline)를 멀게 만들면 삼각측량 시 3D 점의 위치를 훨씬 정확하게 계산할 수 있다.

하지만 이미지를 여러 장 엮다 보면 outlier 들이 발생한다.
그래서 COLMAP은 재귀적 RANSAC 기법을 제안한다.

2 RANSAC
모든 조합을 계산하는 대신 트랙에서 무작위로 딱 2장의 관측치($\overline{x}_a,\overline{x}_b$)를 뽑아 임시 3D 점($X_{ab}$)을 계산한다.
$X_{ab} \sim \tau(\overline{x}_a, \overline{x}_b, P_a, P_b)$
여기서 $\tau$는 삼각측량 함수(주로 DLT 방식)를 의미하며, $P_a, P_b$는 두 카메라의 포즈다.
만들어진 임시 3D점이 물리적으로 말이 되는지 두 가지 수식으로 검증한다.

• 충분한 사잇각 ($\alpha$): 두 카메라 위치($t_a, t_b$)에서 점($X_{ab}$)을 바라보는 각도가 너무 좁지 않은지 확인한다.
  $\cos \alpha = \frac{t_a - X_{ab}}{\|t_a - X_{ab}\|_2} \cdot \frac{t_b - X_{ab}}{\|t_b - X_{ab}\|_2}$
• 카메라 앞면 위치 (Cheirality 제약): 3D 점의 깊이($d$)가 양수여야 한다. (즉, 점이 카메라 렌즈 뒤가 아닌 '앞'에 있어야 함)
  $d = \begin{bmatrix} p_{31} & p_{32} & p_{33} & p_{34} \end{bmatrix} \begin{bmatrix} X_{ab} \\ 1 \end{bmatrix} > 0$

3 오차 계산
트랙에 남은 다른 카메라($P_n$)들에 이 임시 3D 점을 투영해보고, 원래 픽셀 위치($\overline{x}_n$)와의 차이인 재투영 오차(Reprojection Error, $e_n$)를 계산한다.
$e_n = \left\| \overline{x}_n - \begin{bmatrix} x'/z' \\ y'/z' \end{bmatrix} \right\|_2 < t$
오차가 임계값($t$)보다 작으면 해당 카메라는 이 3D 점의 위치에 '동의(Inlier)'하는 것으로 간주한다. 이 무작위 뽑기와 투표 과정을 반복(K번)하여 가장 많은 동의를 얻은 점을 진짜 3D 점으로 최종 확정한다.

4 제거 후 반복
확정된 진짜 3D 점과 사진들은 트랙에서 제거한다. 그리고 남은 데이터들끼리 다시 반복함으로써 남은 데이터 속에 숨어있는 실수로 잘못 병합되었던 또 다른 3D 점을 계속해서 찾아낸다.

3-4 Bundle Adjustment

이미지를 하나씩 이어 붙여 3D 맵을 만들다 보면 미세한 계산 오차가 나타나는 현상(Drift)이 발생한다. 이를 해결하기 위해 카메라의 위치(Pose)와 3D 점들의 위치를 동시에 미세 조정하여 오차를 최소화하는 과정이 Bundle Adjustment(BA) 과정이다.

COLMAP이 설계한 BA 과정을 살펴보겠다.

1 Local BA와 Global BA
사진을 한 장 추가할 때마다 전체 3D 맵을 수정(Global BA)하는 것은 연산량이 너무 많다.

• Local BA : 사진이 새로 추가되면 그 사진과 가장 밀접하게 연결된 주변 카메라들만 묶어서 부분적으로 최적화를 진행함
• Global BA : 모델이 특정 비율(%) 이상 커졌을 때만 전체 맵을 한 번에 다듬어 줌

2 Parameterization
카메라 파라미터를 최적화할 때 outlier에 휘둘리지 않도록 수학적 장치를 마련했다.

• outlier의 영향을 줄이기 위해 손실 함수인 Cauchy 함수를 사용함
• 카메라 개수가 100여 대 이하일 때는 정밀한 해를 구하는 도구(Sparse direct solver)를 그 이상일 때는 가볍고 빠른 도구(PCG)를 사용함

3 Filtering
최적화가 끝난 후에도 모델과 맞지 않는 outlier들이 있다면 삭제함

4 Re-Triangulation
BA를 거치면 카메라의 위치와 각도가 정확해지기 때문에 3D점으로 못 만들었던 픽셀들을 다시 계산하는데 이를 Post-BA RT라고 한다.

5 Iterative Refinement
기존 SfM은 BA 최적화 -> 필터링을 한 번만 했지만 COLMAP은 BA 최적화 -> Re-Triangulation -> Filtering 이 전체 과정을 outlier가 나오지 않을 때까지 iterative 한다.

3-5 Redundant View Mining

수만 장의 이미지를 3D로 만들 때 가장 큰 문제는 연산 시간이다. 기존 BA는 이미지 한장씩 계산하느라 시간이 많이 걸렸는데 COLMAP은 비슷한 사진들을 묶어서 계산을 함으로써 연산 시간을 줄였다.

어떤 기준으로 그룹을 나눌지가 중요하다.

• Affected : 방금 3D map에 새로 추가되었거나 오차가 커서 정밀 조정이 필요한 사진들은 기존 방식대로 카메라 파라미터를 최적화함
• Unaffected : 전에 추가되었고 안정적으로 자리를 잡은 사진들이 그룹화의 대상이 된다

Unaffected 그룹을 대상으로 COLMAP은 두 카메라가 같은 3D 점을 얼마나 많이 공유를 하는가를 기준으로 묶는다.

1 이진 가시성 벡터
어떤 카메라가 1번 점을 보면 1, 못 보면 0으로 표기하여 0과 1로 이루어진 긴 벡터($v_a$)를 만든다.

2 겹침 점수 계산
두 카메라 $a, b$가 얼마나 겹치는지 비트 연산 수식으로 계산한다.
$V_{ab} = \frac{\|v_a \wedge v_b\|}{\|v_a \vee v_b\|}$ (두 카메라가 공통으로 보는 점의 수 / 두 카메라가 보는 전체 점의 수)

3 그룹화 하기

3-1 정보가 많은 순서대로 줄 세우기(sorting)

$\bar{I} = \{I_i \mid \|v_i\| \ge \|v_{i+1}\|\}$
우선 모든 이미지들이 3D 점을 가장 많이 보고 있는(정보량이 많은) 사진부터 리스트를 만드는데 이 리스트를 $\bar{I}$라고 한다.

3-2 그룹의 첫 이미지 뽑기
정렬된 리스트 $\bar{I}$의 맨 앞에 있는(정보량이 많은) 첫 번째 이미지 $I_a$를 뽑아서 새로운 그룹 $G_r$의 첫 번째 이미지로 넣는다. 이제 $I_a$는 이 그룹의 기준이 된다.

3-3 가장 비슷한 이미지 찾기
이제 남은 이미지들 중에서 기준인 $I_a$와 가장 비슷한 이미지 $I_b$를 찾고 이때 $V_{ab}$(두 사진의 겹침 점수)가 가장 높게 나오는(Maximum) 이미지를 1순위로 둔다.

3-4 그룹 넣기
가장 비슷한 이미지로 뽑힌 $I_b$가 $G_r$ 그룹에 들어가려면 두 가지 조건을 동시에 통과해야 한다.

• $V_{ab} > V$ : 두 사진의 겹침 점수가 우리가 정한 커트라인($V$)보다 높아야 함
• $|G_r| < S$ : 그룹에 속한 멤버 수가 최대 정원($S$)을 넘지 않아야 함

위 두 조건을 만족하면 $I_b$가 $G_r$ 그룹에 들어가고 만족하지 않으면 다른 그룹의 첫 번째 기준으로 시작하게 된다.

3-5 Heuristic Search
모든 이미지를 비교하면 시간이 오래 걸리기 때문에 COLMAP은 GPS 위치상 가장 가까운 $K_r$개의 이미지 중에서 렌즈가 바라보는 방향이 $\pm\beta$도 이내로 비슷한 사진들만 골라서 비교한다.

출처

---

1. Figure 2. Feautre extraction, Figure 3. Matching