얼떨결에

1. Introduce

COLMAP은 Structure-from-Motion Revisited 논문을 기반으로 만들어진 라이브러리입니다. COLMAP은 SfM(Structure from Motion)과 MVS(Multi-View Stereo)를 사용할 수 있게 만든 오픈소스 라이브러리며 3D Reconstruction 분야에서 초기 데이터 설정 등에 많이 사용되고 있습니다. 본 논문에서 SfM 등의 알고리즘을 만든 것이 아닌, 그 알고리즘들을 범용적으로 사용할 수 있는 COLMAP을 제공하는 논문이라고 생각하시면 됩니다.

2. Overview

COLMAP의 전체적인 Overview입니다. SfM(Structure-from Motion)인 경우 Figure 2에서 Incremental Reconstruction을 제외한 것이라고 생각하시면 됩니다. (본 논문에서 제시하는 것은 Incremental Reconstruction이 포함된 Incremental SfM)

전체적으로 각기 다른 View Points로부터 3D Reconstruction 하는 방법을 소개합니다.

Figure 2에서 보여지는 순서를 간략하게 설명하자면

1. Multi-View Image 들이 (Input) 으로 들어오면
2. (Correspondence Search) 그 이미지 들의 관련성을 찾습니다.
     - Feature Extraction : 어떻게 특징점을 추출할 것인가
     - Matching : 모든 Feature 쌍을 찾아 가장 오버랩이 많은 Image들을 Pair
     - Geometric Verification : Matching된 Image Pair들을 Geometric 방법을 통해 검증 
3. (Incremental Reconstruction) Matching된 Feature들을 통해 3D로 Reconstruction
     - Initialization : Location 정보가 많은 Pair를 선택해 Initialization
     - Image Registration : Scene Graph를 통해 다음 Edge에 연결된 Pair를 가져옴
     - Triangulation : Pair에서 두개의 Projection Matrices와 매칭된 2D Points를 통해 3D Point Recon
     - Bundle Adjustment : Recon된 3D Points와 Pose를 Reprojection 하고 Error를 최소화시킨다.
     - Outlier Filtering : 잘못된 3D Points들 제거 

3. Method

Correspondence Search

Input : 정렬이 안된 Images

Output : Image Pair들을 Edge로 한 Scene Graph

1. Feature Extraction

- 특징점을 추출하는 단계

𝑥_𝑗 : 이미지 I에서의 특징 위치 (2D 좌표)
𝑓_𝑗 : 해당 위치에서의 descriptor (특징의 시각적 속성을 나타내는 벡터)
𝑁_𝐹𝑖 : 이미지 I에서 감지된 총 특징 개수

- 특징은 Radiometric 및 Geometric 변화에 강해야 합니다. 즉, 조명, 색상, 명암 등이 변화하거나 이미지가 회전, 확대, 왜곡 등의 변화에 강해야 합니다. 

- Feature Extraction은 SIFT(Scale-Invariant Feature Transform) 알고리즘을 전통적으로 사용하는데, 요즘은 SIFT 대신 딥러닝을 많이 사용합니다.) 

(SIFT 알고리즘)

- Gaussian Blur로 다양한 Scale의 이미지를 만들고, 각 픽셀을 주변 8개 및 상하위 18개 픽셀과 비교해 최대값 또는 최대값인지 확인하고, 이를 통해 중요한 점(극점, Extrema)를 탐지합니다. 
- 각 극점의 강도와 환경을 분석하고 노이즈에 민감하지 않고 강한 특징만 남깁니다.

2. Matching

- 여러 이미지에서 같은 장면을 봤던 부분을 찾고, 이들 사이의 특징점을 매칭하는 단계

Input : 𝑥_𝑗, 𝑓_𝑗 을 포함하는 특징 집합 𝐹_𝑖 과 이미지 집합 I
Output : 겹치는 장면을 촬영한 Image pair (𝐼_𝑎, 𝐼_𝑏) 집합인 C /  Image pair에서 매칭된 특징점 쌍(𝑀_𝑎𝑏)의 집합

𝐼_𝑎, 𝐼_𝑏 의 유사성을 비교하기 위해 naïve한 방법으로는 Similarity Metric을 사용하는데 최근에 효율적으로는 ANN, Feature Clustering, 딥러닝 등을 많이 사용합니다.

3. Geometric Verification

- 매칭된 포인트들은 외형을 기준으로 잡았기 때문에, 실제로 같은 Scene에 있는지를 확인하는 과정이 필요합니다. (예를 들어, 같은 모양의 물건이 한 장소에 여러개가 있는 경우 등)

Input : 특징점 쌍(𝑀_𝑎𝑏), Image pair (𝐼_𝑎, 𝐼_𝑏)
Output : 매칭 Image Pairs 𝐶 ̅  /  Outlier를 제거하고 남은 매칭 점 𝑀 ̅_𝑎𝑏 / 수학적 변환 모델 𝐺_𝑎𝑏 / Scene Graph (노드 : 이미지 I, 엣지 : 검증된 이미지 쌍 𝐶 ̅ )

두 이미지 간의 기하학적 관계를 수학적 변환 모델로 바꿉니다.
- Epipolar Geometry
  - 두 이미지 간의 관계는 다음과 같이 설명 가능합니다.
     - Essential Matrix (E) : 내부 카메라 파라미터(Calibration)가 알려진 경우
     - Fundamental Matrix (F) : Calibration 정보가 없는 경우
이미지 두 장의 관계성으로 상대 Pose를 추정한 뒤에, 기준 View의 Feature Point들을 다른 View로 Projection했을 때 Mapping이 잘되는지 검증합니다. 

Incremental Reconstruction

Input : Scene Graph
Output : 최종 Image들의 Pose Estimates P, 3D 공간의 Point Cloud X

1. Initialization

- 겹치는 영역도 많고 기하학적으로 검증된 이미지 Pair (𝐼_𝑎, 𝐼_𝑏) 을 선택합니다.
- 선택된 이미지 Pair에서 Essential Matrix 기반으로 초기 카메라 위치와 방향 (𝑃_𝑎, 𝑃_𝑏) 을 추정합니다.
- 선택된 이미지 Pair의 매칭된 특징점으로 초기 3D Point Cloud (𝑋_𝑘) 을 생성합니다.

2. Image Registration

- 초기화된 Camera pose와 Image Pair를 사용해 2D 매칭점에서 3D Points 계산합니다.

𝑥_𝑗  : 새로운 이미지 𝐼_𝑐 의 2D 특징점
𝑋_𝐾 : 이미 계산된 3D Point Cloud 의 Point

(𝑥_𝑗, 𝑋_𝐾)을 기반으로, 새로운 이미지의 카메라 pose 𝑃_𝑐를 추정합니다.
이러한 Pose 들의 집합인 P로 출력합니다.

3. Triangulation

- 새로운 이미지와 기존 3D 모델간의 관계를 확장하고, 추가적인 3D 포인트를 생성해 Point Cloud를 확장하는 목적 (동일한 3D Point를 여러 이미지에서 관측하면 중복성이 생겨 모델의 안정성을 높입니다.)

- 각 이미지에서 매칭된 2D Point에서 Ray를 생성하고 이 Ray들의 Intersection을 찾습니다.
- Multi-view Triangulation : 다수의 이미지라면 더 정확하지만, 계산량이 많고, 노이즈에 민감합니다.(잘못된 매칭점인 Outlier가 모델에 악영향)  --> RANSAC 등을 사용

4. Bundle Adjustment

- 카메라의 파라미터와 3D Point의 좌표를 동시에 최적화하여 정확도를 올리는 과정
- 특징점 2D와 3D Point 간의 Reprojection Error를 최소화합니다. 

- Image Registration과 Triangulation은 별개의 과정이지만, IR에서 예측한 pose는 3D포인트의 TR에 영향을 주고, 반대로 TR에서 예측한 3D포인트는 IR에서 Pose를 구하는데 영향을 줍니다. 따라서 BA를 통해 동시에 최적화해 정확도를 높입니다. 따라서 BA에서는 Camera pose (𝑃_𝑐)와 3D Point(𝑋_𝑘)를 동시에 최적화합니다. 

4. Conclusion

- 기존 SfM 알고리즘에서의 완전성, 강건성, 정확도, 효율성 문제를 해결한 논문입니다. 본 논문은 COLMAP의 근간이 되는 논문으로 아직까지 많이 사용되기 때문에 완전히 숙지하지는 못해도, 어느정도 어떻게 구성되는지는 알아야 할 것 같습니다. 

1. Introduce

2020년 NeRF 이후로 NeRF분야에서 가장 이슈가 된 3D Gaussian Splatting 논문을 소개하고자 합니다. (본 글은 Xoft님 블로그에서 도움을 많이 받았습니다.) Gaussian Splatting은 NeRF 대비 Training 시간을 대폭 감소시켰고 Quality도 기존 SOTA보다 앞선 기술입니다. 특히 렌더링 속도가 100FPS 이상인 점이 추후 Real-time으로 나아갈 수 있는 길을 제시했다는 점이 Gaussian Splatting 의 특징 중 하나 입니다.
 

 
기존 InstantNGP 나 NeRF 대비해서 렌더링 속도 FPS가 100이상으로 뛰어났고 Training 속도도 NeRF의 48시간 대비, 1시간 이내로 엄청나게 단축시켰습니다. Gaussian Splatting은 NeRF를 수정해 단점을 보완한 기술이 아닌, NeRF와는 다른 기술인 점을 명심하셔아합니다. 하기 내용은 NeRF와 Gaussian Splatting을 비교합니다.

NeRF는 3D 장면을 연속적인 방식으로 표현합니다. 예를 들어 물체를 아주 조각들로 하나하나 계산해서 3D 로 만든다고 생각하시면 됩니다. (카메라에서 장면을 바라보는 여러 Ray를 쏘고 그 Ray 위에서 색과 빛의 밀도를 여러 번 샘플링) 따라서 Training 시간이 오래걸립니다.
--> 볼륨기반으로 Ray에 따라 색과 밀도를 안개같은 연속적인 구름(볼륨)으로 구성합니다.
 
Gaussian Splatting은 Point Cloud와 비슷하게 불연속적인 점들의 집합으로 표현합니다. 예를 들어 장면의 중요한 부분만 골라서 작은 점들로 사용해 그립니다. (3D Gaussian을 Blob으로 표현해서 퍼진 점들로 만들고 이를 부드럽게 표현합니다.) 따라서 더 빠르고 간단하게 생성합니다.
--> 3D Gaussian Blob들이 모여 장면을 구성합니다.
 
그럼 본 논문에서는 왜 3D Gaussian을 사용했을까요? 3D Reconstruction에서 3D Gaussian의 장점은 다음과 같습니다.
1. 미분 가능한 볼륨 표현
- Differentiable : Rendering 과정에서 Parameter 조정할 때 Gradient를 계산할 수 있습니다.
- Volumetric : Gaussian Blob은 점이 아니라 3D Volume이기 때문에 Point Cloud/Triangular 보다 더 부드러운 표현이 가능합니다.
2. 명시적 표현
- Blob의 위치, 크기, 모양, 투명도를 수정할 수 있습니다. 
- Neural Network 기반은 데이터 구조가 신경망 내부에 있어 수정이 어려웠습니다.
3. 효율적인 2D Projection 과 Alpha Blending
- Blob은 2D Projection 시(end user가 이미지로 보게되니까.), 타원형으로 나타나 2D 이미지 상에서도 부드러운 장면을 생성합니다.
- Gaussian 수학적 특성상 간단해서 효율적인 계산으로 빠르게 계산이 가능합니다. (일단 복잡한 표면이나 구조를 다루지 않습니다.)
- Blob들이 서로 겹치는 상황에서도 투명도(Alpha) 기반으로 간단히 색을 혼합하여 계산량을 최소화할 수 있습니다.
 

2. Overview

Gaussian Splatting의 전체적인 방법은 다음과 같습니다. 
1. Initialization
- COLMAP 등으로 얻은 SfM Point, Camera Pose, Point Cloud 데이터 들을 사용해 3D Gaussian으로 만듭니다.
2. Projection
- Camera의 z축으로부터 1 떨어진 Image Plane으로 2D Gaussian으로 Projection됩니다. 이는 Ground Truth(2D 이미지)와 비교해 Parameter 업데이트를 위함입니다.
3. Differentiable Tile Rasterizer
- 미분가능한 형태의 Tile Rasterizer를 통해 2D Gaussian들을 하나의 Image로 생성합니다.
4. Adaptive Density Control
- Gradient 기반으로 Gaussian의 형태를 변화시킵니다. (복잡한 영역은 밀도를 더 세밀하게 하거나, 단순한 영역은 단순하게 하거나 불필요한 부분은 Remove하거나...)
 

3. Method

Xoft님의 아이디어를 착안해 Algorithm Pseudo Code에 따라 리뷰해보도록 하겠습니다. (저는 전체적으로 이해하기 편하더라구요...) 

전체적인 3D Gaussian Splatting의 알고리즘입니다. 먼저 간단하게 설명드리자면 
A : 변수 초기화
B : Inference 후 Loss 계산해 Update하는 부분 
C : 간헐적인 Iteration 마다 Gaussian을 Remove, Split, Clone 하는 부분

Method (A) - 변수 초기화

변수 초기화에 앞서 각 학습 파라미터 M, S, C, A에 대해 설명이 필요합니다.

1) M

- SfM으로 획득한 Point Cloud Positon 데이터입니다. 그 Point 들이 초기 3D Gaussian의 평균값으로 사용되고 Point 수만큼 3D Gaussian이 생성됩니다.
 

2) S

- 3x3 모양의 3D Gaussian Covariance Matrix입니다. (알고리즘과 논문의 변수명이 달라서 임의로 작성했습니다.)

r_m : Rotation Matrix, s_m : Scale Matrix

- Rotation Matrix
3D Gaussian Blob이 회전된 방향을 나타냅니다.
일반적으로 Quaternion q (4x1)을 사용해 Rotation Matrix (3x3)으로 변환됩니다.
- Scale Matrix
3D Gaussian Blob의 x, y, z 축 각각의 Scale을 나타냅니다.
 

S가 Positive Definite일 경우에만 Gaussian Blob이 제대로 렌더링됩니다. Positive Definite기 때문에 모든 x, y, z축의 Gaussian Blob은 0보다 큰 값을 가집니다. (이제부터 S는 Σ로 표현합니다.)

 
- 3D Gaussian을 2D Gaussian으로 Projection 하는 수식은 다음과 같습니다.

World 좌표계에서의 Covarience Matrix 는 Σ.
World 좌표계에서 Camera 좌표계로 변환하는 Viewing Transformation은 W.
Camera 좌표계에서 Image 좌표계로 변환하는 Projective Transformation의 Jacobian은 J.
Covariance 특성으로 Transpose를 뒤에 붙이면 상기 수식이 완성됩니다.
 

3) C

- 3D Gaussian의 Color 값입니다. Color는 Spherical Harmonics (SH) 함수로 설계됩니다.- 3D Gaussian 마다 View 방향에 따라 최적의 SH를 찾도록 하는데요. 간단하게 요약하자면 Max Degree에 따라서 색상의 팔레트의 총 개수가 결정됩니다.

4) A

- 3D Gaussian의 투명도 값 (Alpha)

Method (B) - Optimization

1) Ground Truth 이미지 I ̂  과 그 이미지의 Camera Pose V를 읽습니다.
2) M, S, C, A, V를 입력으로 받아 Rasterize해 Predicted Image를 만드는데, 이 부분은 알고리즘 2로 설명드리겠습니다.

Rasterizer
- 이미지를 16 x 16의 Tile들로 작게 나눕니다. (CUDA 처리를 위한 것으로 보입니다.)
- Duplicate with Keys : 각각의 2D Gaussian이 겹치는 수만큼 instance 화합니다. (각 instance 들은 key K(depth & id)를 갖습니다. / Gaussian을 여러 Tile로 복제한다고 생각하시면 됩니다.)
- Sort by Keys : key K를 정렬해서 카메라와 가장 가까운 Gaussian을 먼저 그립니다.
- Identify Tile Ranges : 같은 Tile ID를 가진 Start-End Gaussian을 식별해 Tile 별 list를 관리합니다.
- Blend in Order : 주어진 하나의 Pixel에 대해 앞에서부터 Color 와 Alpha를 축적하고 그 Pixel에 대한 Alpha 값이 목표 Saturation에 도달하면 Thread를 중지합니다.
 
3) Predicted 이미지와 Ground Truth 이미지와 비교해 Loss를 계산합니다. (Loss Function은 L1, D-SSIM)

4) Optimizer는 ADAM을 사용해 M, S, C, A값을 업데이트합니다.
 

Method (C) - Adaptive Control of Gaussians

- Scene에 맞게 3D Gaussian들을 Adaptive하게 변형하는 단계입니다.
- M, S, C, A는 각 iteration 마다 업데이트되는데, 이 부분은 100 iteration 마다 간헐적으로 수행됩니다.
 
1) Remove Gaussian
- 특정 threshold보다 낮은 Alpha값을 가진 Gaussian은 제거합니다.
 

2) Clone Gaussian
- Under-Reconstruction 에 대해서 작은 Covariance 3D Gaussian들은 같은 크기로 Copy하고 Positional Gradient 방향에 배치합니다.
 
3) Split Gaussian
- Over-Reconstruction 에 대해 큰 Covariance 3D Gaussian들은 작은 크기로 Split합니다. 분리된 Gaussian의 위치는 초기 Gaussian의 확률 밀도 값에 따라 배치합니다.
 
--> Clone은 Gaussian의 개수와 Volume이 모두 증가하고 Split은 Volume은 유지하지만 Gaussian의 개수가 증가합니다.
이러한 현상으로 공간내에 불필요한 Floater가 생성되고 잡음처럼 불필요한 Blob들이 생깁니다.
본 논문에서는 300 iteration 마다 Alpha 값을 0으로 초기화하여 해결했다고합니다.
 

4. Evaluation

NeRF에 비해 Memory를 많이 사용하는 단점을 가지고 있습니다.
렌더링 속도(FPS) 가 빠르고 Quality도 좋은 장점을 가지고 있습니다.

5. Limitation & Conclusion

- 입력 이미지가 부족한 Scene에서는 Artifact가 발생합니다.
- 또한 Large Gaussian을 생성한 경우에도 Artifact가 발생합니다.
- 마지막으로 높은 Memory 사용량으로 HW적으로 한계점이 있어 이 부분은 해결해야할 것으로 보입니다.