[CV 논문] Structure-from-Motion Revisited

 

 

아래 글에서 이 블로그에서 리뷰한 논문들의 흐름과 분야별 분류를 한 눈에 볼 수 있다.

읽은 논문들 정리

읽은 논문들 정리

 

 

이번 논문은 SfM이라고 불리는 기술에 대한 설명이다.

여러 장의 2D이미지에서 카메라가 어디에서 이 물체를 찍었는지, 그 물체의 3차원 형태를 복원한다.

3DGS등에 자주 사용되는 COLMAP이라는 소프트웨어의 토대 이론이 되었다.

 

이 논문이 처음 SfM이라는 개념을 만든 것은 아니고 이전에 증분형 SfM이라는 것이 있었다.

이를 개선하는 방법에 대해 설명하는 논문이다.

---

---

이전의 SfM

먼저 논문의 파트2에서 얘기하는 이전의 전통적인 증분형 SfM의 과정에 대해 간단히 살펴보자.

크게 아래의 두 단계로 나눠진다.

 

1. 대응점 찾기 (Correspondence Search)

2. 증분적 복원 (Incremental Reconstruction)

---

1. 대응점 찾기 (Correspondence Search)

여러 이미지 사이에서 연결고리를 찾는 과정이다.

총 3개의 단계로 이루어진다.

 

1-1. Feature Extraction

1-2. Matching

1-3. Geometric Verification

 

 

---

1-1. Feature Extraction

입력으로 여러 개의 이미지를 받는다.

각 이미지에 대해 주변 변화에 상관없이 고유하게 식별 가능한 지점들을 찾는 단계이다.

보통 SIFT라는 방법을 사용하는데, 이 방법은 특정 점 주변의 기울기 방향을 숫자로 표현한 것이다.

이렇게 주변 정보를 담은 것을 Descriptor라고 한다.

이 패턴이 비슷하면 같은 점이라고 추론할 수 있다.

 

1-2. Matching

추출된 특징점들을 비교하여 서로 다른 두 이미지가 같은 장면을 보고 있는지 확인하는 단계이다.

방법: 이미지 $I_a$의 특징점 Descriptor $f_j$와 가장 유사한 Descriptor를 이미지 $I_b$에서 찾아 대응 쌍($\mathcal{M}_{ab}$)을 만든다.

 

1-3. Geometric Verification

외형적 유사성만으로 매칭된 점들이 실제 3D 공간의 동일한 지점인지 수학적으로 검증하는 단계이다.

매칭은 어떤 점의 주변을 보고 비교하는 것이기 때문에 나뭇잎처럼 비슷한 것들이 많을 경우 서로 다른 점이 매칭되는 경우가 생길 수 있다.

수학적 모델을 사용해서 실제 3D공간상에서 같은 점을 매칭한 것이 맞는지 검증한다.

 

 

---

2. 증분적 복원 (Incremental Reconstruction)

이 단계는 4개의 단계로 구성되어있다.

2-1. Initialization

2-2. Image Registration

2-3. Triangulation

2-4. Bundle Adjustment

---

2-1. Initialization

3D모델을 처음 그리기 시작할 두 이미지 쌍을 골라서 초기 모델을 구성한다.

보통 겹치는 점이 많은 이미지를 골라 사용한다.

 

2-2. Image Registration

위에서 만든 모델에 이미지를 한 장씩 추가하면서 위치를 맞춘다.

새로 추가하는 이미지의 특징점들이 이미 만들어진 모델의 어느 점과 같은지를 파악해서 새 카메라를 배치하는 과정이다.

 

2-3. Triangulation

이렇게 위치가 결정된 카메라들을 이용해서 새로운 3D 점을 만든다.

여러 카메라가 동시에 보고 있는 점을 하나 잡고 이 점에서 각 카메라까지 광선을 그려 광선의 교점을 새로운 3D점으로 만들 수 있다.

 

2-4. Bundle Adjustment

2-2, 2-3 과정이 반복되면 오차가 조금씩 쌓일 수 있다.

이를 방지하기 위해 한번에 최적화를 하는 과정이다.

---

---

논문의 핵심 기술 제안

이전의 SfM방식은 몇가지 문제가 있었다.

먼저 사진 이미지의 양이 많다보니 매칭 과정을 간소화하였는데, 실제로 연결되어야할 이미지들이 연결되지 못하는 현상이 있었다.

또 위 과정에서 보이다시피, 새 이미지는 이미 존재하는 3D구조가 있어야 이를 뼈대삼아 붙혀질 수 있고,

새 3D구조는 이미지가 있어야 삼각측량을 통해 새로 만들어질 수 있다.

이런 서로 의존하는 현상으로 인해 미세한 오차가 쌓이게 된다.

 

따라서 이 논문에서는 크게 5가지 정도의 기술을 제안했다.

1. Scene Graph Augmentation

2. Next Best View Selection

3. Robust and efficient Triangulation

4. Bundle Adjustment

5. Redundant View Mining

 

---

1. Scene Graph Augmentation

이미지 사이의 관계를 파악한다.

한 자리에서 카메라만 회전하며 찍은 파노라마 식인지, 일반적인 경우처럼 카메라가 이동하면서 장면을 찍은 사진들인지 등을 파악한다.

1-1. 수학적 모델 기반 기하 검증

하나의 이미지 쌍을 검증할 때 여러 수학적 모델($F, H, E$)을 순차적으로 적용하여 장면의 특성을 분류한다.

 

기초 행렬($F$) 추정

가장 먼저 두 이미지 사이의 기초 행렬을 구한다.

기초행렬은 한 이미지의 점을 다른 이미지의 점으로 옮겨주는 행렬이다.

두 점 $x_2,x_1$에 대해 $x_2^T F x_1 =0$라는 식을 계산했을 때 오차가 거의 없다면 일치하는 점(inlier)로 취급한다.

이때 inlier의 개수 $N_F$가 기준치 이상이면 기하학적으로 연결된 쌍으로 인정한다.

 

일반 장면 분류

동일한 쌍에 대해 호모그래피($H$) inlier 개수 $N_H$를 구한다.

호모그래피는 평면적인 관계를 나타낸다. $x_2 = H x_1$이라는 식을 통해 한 이미지의 점을 다른 이미지의 점으로 옮길 수 있다.

만약 카메라가 이동하며 건물처럼 입체적인 대상을 찍었다면 위 식처럼 계산이 되지 않는다.

만약 $N_H / N_F < \epsilon_{HF}$라면, 장면이 평면이 아니고 카메라가 이동하며 찍은 일반적인 장면으로 판단한다.

 

카메라 보정 확인

카메라 렌즈의 초점거리 등의 보정 정보가 있는 경우 본질 행렬($E$)을 추정한다.

$N_E / N_F > \epsilon_{EF}$ 조건을 만족하면 카메라의 내부 파라미터가 정확하다고 신뢰한다.

 

파노라마 vs 평면 구분

보정이 정확하고 일반 장면일 때, 본질 행렬을 분해해 점들을 삼각측량해본 뒤 그 사이각의 중간값($\alpha_m$)를 계산한다.

이 각도 $\alpha_m$을 통해 이 관계가 제자리에서 회전한 파노라마인지, 아니면 평면 장면인지를 최종 구분한다.

 

---

1-2. 인터넷 사진의 문제인 WTF 탐지

WTF는 워터마크(Watermarks), 타임스탬프(Timestamps), 프레임(Frames)을 얘기한다.

서로 다른 장소인데도 이 WTF 때문에 '같은 곳'으로 오해받는 경우가 많다.

 

탐지 방법: 보통 WTF는 이미지의 변두리에 있기 때문에 이미지 테두리 부근에서 유사성 변환(Similarity transformation)을 따르는 inlier 개수($N_S$)를 측정한다.

 

필터링: $N_S$의 비율이 일정 기준($\epsilon_{SF}, \epsilon_{SE}$)을 넘어서면 이를 실제 장면이 아닌 'WTF'로 간주하여 버린다.

 

---

1-3. 복원 프로세스에서의 활용

이렇게 상세히 General, Panoramic, Planar로 분류를 한 결과는 이후 복원 단계에서 중요하게 사용된다.

 

안전한 초기화

복원의 출발이 되는 초기 이미지 쌍을 고를 때, 파노라마가 아니면서 보정 정보가 확실한 쌍을 우선적으로 선택하여 복원 시작을 한다.

 

Degeneracy 방지

파노라마 이미지 쌍은 한 장소에서 카메라를 회전시키는 것이기 때문에 카메라 사이의 거리가 없어 3D 점을 만들기에 부적합하다.

따라서 논문에서는 파노라마 쌍에서는 삼각측량을 수행하지 않는 방법을 제시했다.

---

2. Next Best View Selection

초기화한 3D모델에 어떤 사진들을 붙여나갈지 정하는 과정이다.

 

그리드 기반 점수 (Grid-based Scoring)
이미지를 일정한 격자(Grid)로 나눈다.
각 격자 칸(Cell)은 '비어 있음' 또는 '가득 참' 상태만 가지고 있다.
특정 칸에 3D 점이 하나라도 보이면 그 칸은 '가득 참'이 되고 점수를 얻는다.

따라서 한곳에 많은 점이 몰린 경우보다 전반적으로 점이 많은 이미지가 높은 점수를 얻게 된다.

 

멀티 해상도 피라미드 (Multi-resolution Pyramid)

격자의 크기가 너무 크거나 작으면 분포를 제대로 측정하기 어렵다.

이를 해결하기 위해 여러 단계의 해상도($l=1...L$)를 가진 피라미드 구조를 사용한다.

낮은 해상도(큰 격자)부터 높은 해상도(작은 격자)까지 각 레벨에서 얻은 점수를 합산한다.

 

아래 그림은 격자가 촘촘해질수록 점수에 곱해지는 가중치를 각각(2,4,8)로 설정해 계산한 점수이다.

촘촘한 격자에서 채워진 칸에서 생성되는 점수가 그렇지 않은 칸에서 생성되는 점수보다 높다.

 

왜 점이 퍼져있는 사진에 대해 높은 점수를 책정하는 방식을 사용할까?

인터넷에서 얻어지는 사진은 찍은 카메라의 렌즈 스펙같은 내부 정보가 없기 때문에 균일한 분포가 있는 이미지여야 이런 내부 정보를 정확히 추정할 수 있기 때문이다.

---

3. Robust and efficient Triangulation

어떻게 정확히 많은 3D점을 만드는지에 대한 설명이다.

 

먼저 보통의 매칭은 겉모양이 비슷한 이미지끼리 이루어지는데 이렇게 되면 카메라 사이의 거리가 보통 짧기 때문에 삼각측량에서 오차가 발생한다.

그래서 논문에서는 점A-점B가 매칭되고 점B-점C가 매칭되었으면 점A-점C도 연결한 걸로 치는, 즉 공간상의 같은 점에 대해 다른 이미지에서 찍힌 정보들을 연결한 특징점 트랙이란 것을 만들어서 해결한다.

 

트랙 $T$에서 임의의 두 측정치($x_a, x_b$)와 해당 카메라 포즈($P_a, P_b$)를 샘플링하여 3D 점 $X_{ab}$를 추정한다.

$$X_{ab} \sim \tau(\bar{x}_a, \bar{x}_b, P_a, P_b)$$

여기서 $\tau$는 DLT(Direct Linear Transformation) 알고리즘이다.

그냥 삼각측량을 하는 방법 중 하나라고 생각하면 된다.

 

추정된 3D 점 $X_{ab}$가 믿을만한지 몇가지 조건을 확인한다.

 

1. 충분한 삼각측량 각도 ($\alpha$)

두 카메라가 점을 바라보는 각도가 너무 좁으면 거리 계산이 부정확하므로, 코사인 유사도를 통해 각도를 체크한다.

$$\cos \alpha = \frac{t_a - X_{ab}}{\|t_a - X_{ab}\|_2} \cdot \frac{t_b - X_{ab}}{\|t_b - X_{ab}\|_2}$$

 

2. 치랄리티 제약 (Cheirality Constraint, $d > 0$)

3D 점이 카메라의 앞쪽에 있어야 한다는 물리적 제약이다.

$d$는 카메라 좌표계에서의 깊이이다.

$$d = [p_{31} \ p_{32} \ p_{33} \ p_{34}] \begin{bmatrix} X_{ab} \\ 1 \end{bmatrix}$$

 

3. 재투영 오차 ($e_n$)

3D 점을 다시 이미지 평면에 쐈을 때 실제 2D 특징점($\bar{x}_n$)과의 거리 오차가 임계값($t$)보다 작아야한다.

$$e_n = \left\| \bar{x}_n - \begin{bmatrix} x'/z' \\ y'/z' \end{bmatrix} \right\|_2$$

 

 

 

트랙이 이론상으로는 같은 점을 찍은 여러 점의 정보의 집합이어야 한다.

하지만 여러개의 창문, 많은 나뭇잎 등 비슷한 부분이 많을 때는 다른 부분을 같은 점이라고 판단해 트랙이 잘못 구성될 수 있다.

아래는 한 트랙 안에 다른 점을 구성하는 정보들을 분리하는 과정이다.

 

RANSAC를 돌려서 트랙 안에서 가장 많은 지지표(Inliers)를 얻은 3D 점을 하나 찾는다.

해당 점의 지지표로 쓰인 점의 정보들을 트랙에서 제외한다.

남은 측정치들을 가지고 다시 위의 과정으로 돌아가 새로운 3D 점을 찾는다.

이 과정을 통해 잘못 합쳐진 트랙 안에서도 여러 개의 실제 3D 점을 각각 복원해낼 수 있다.

이전에는 트랙에서 한 점의 정보만 뽑고 버렸지만, 이 방법은 한 트랙 안의 모든 점 정보를 얻을 수 있다.

 

전체적인 흐름은 아래와 같다.

트랙에서 점 정보 추출 → RANSAC및 삼각측량 알고리즘에 적용 → 최종 3D점 생성

 

---

4. Bundle Adjustment

오차를 해결하고 완성도를 높이는 기술에 대한 설명이다.

 

1. BA

항상 전체 최적화를 하는 것은 비효율적이기 때문에 두 가지 방식으로 최적화를 진행한다.

1. local BA : 새 이미지가 등록될 때마다 진행한다. 현 이미지와 가장 많이 연결된 이미지 세트만을 대상으로 최적화 한다.

2. global BA : 모델이 일정 비율 이상 커졌을 때 전체를 대상으로 최적화 한다.

 

2. Parameterization , Filtering

loss function : outlier의 영향을 줄이기 위해 Cauchy function이라는 loss function을 사용한다.

카메라 : 인터넷 사진처럼 정보가 없는 경우 단순한 카메라 모델을 사용해서 자기 보정을 한다.

필터링 : BA이후 재투영 오차가 큰 점 정보는 제거한다. 삼각측량 각도가 작거나 비정상적인 화각을 가진 카메라도 제거한다.

 

3. 재삼각측량(Re-Triangulation, RT)

BA를 사용해서 정밀한 3D점들과 카메라를 얻으면, 실패했던 데이터들을 다시 살려내보는 과정이다.

Post BA RT : 원래 BA전에만 RT를 했었는데 COLMAP은 BA이후에도 RT를 한다.

 

4. 반복적 정밀화

BA → 재삼각측량 → 필터링 

이 과정을 계속 반복해서 필터링 되는 점이 없을 때까지 한다.

 

 

---

5. Redundant View Mining

대규모 사진 데이터셋에서 SfM은 BA과정이 가장 큰 병목이 된다.

따라서 거의 동일한 위치에서 찍은 사진들에 대해 독립적으로 처리하는 것은 큰 낭비이다.

 

논문은 기존의 복잡한 방법 대신 효율적인 binary visibility vector 방식을 제안한다.

$$V_{ab} = \frac{\|v_a \wedge v_b\|}{\|v_a \vee v_b\|} \text{}$$

 

각 이미지 $i$가 어떤 3D점들을 보고 있는지 0,1로 표현한 벡터 $v_i$를 만든다.

위 식의 값이 크다는 것은 많은 지점들을 같이 보고 있다는 것이 된다.

 

가장 처음에는 가장 많은 점을 보고 있는 이미지에서 시작한다.

이 이미지와 가장 많이 겹치는 이미지를 찾아 그룹으로 묶는다.

물리적으로 가깝고 바라보는 방향이 비슷한 이미지들을 대상으로 계속 조사해 그룹에 추가한다.

 

$$E_g = \sum_{j} \rho_j (\|\pi_g (G_r, P_c, X_k) - x_{jk}\|_2^2) \text{}$$

$E_g$는 이 카메라 그룹 안의 모든 이미지에서 나오는 전체 재투영 오차이다.

$\rho_j$는 위에서 얘기한 cauchy function등의 손실 함수이다.

$\pi_g (G_r, P_c, X_k)$여기서 $P_c$는 그룹 전체의 공통 좌표계를 나타낸다.

$X_k$는 3D공간상의 점이다.

$x_{jk}$는 이미지의 2D특징점 좌표이다.