[ 딥러닝 논문 리뷰 - PRMI Lab ] - COLMAP about SfM (Structure from Motion)

3D-GS, NeRF등을 공부하다보면, COLMAP을 이용해서 3d point cloud도 뽑아내고, camera pose도 뽑아냅니다. COLMAP에서 쓰는 SfM에 대해서는 간단히 공부해서 알고있었지만, 이번 기회에 자세히 정확한 원리에 대해 알면 좋을거 같아서 정리합니다.

 

COLMAP은 오늘 다룰 SfM과 MVS를 사용하기 쉽게 랩핑한 라이브러리입니다. SfM의 주요 결과물은 이미지를 입력으로 받아서 Camera Parameter와 3D Point Cloud를 생성하는 것이고, MVS는 SfM결과를 이용해 3D Reconstruction하는 것에 있습니다.

 

먼저 SfM 논문인 Structure-from-Motion Revisited (CVPR 2016)을 다루겠습니다. 해당 논문은 SfM을 발전시킨 논문입니다. SfM연구들은 incremental, hierarchical, global으로 발전하게 됩니다. incremental SfM은 이미지를 순차, 반복적으로 처리하는 기법이었지만 robustness, completness, scalability, accuracy관점에서 general한 SfM을 만들기 어려워서 해당 논문에서 이를 해결하고자 합니다.

Feature Extraction, Matching

Feature Extraction에서는 영상 내부의 작은 영역이 모든 방향에 대해 gradient가 큰 경우를 corner로 만들어 각 특징점을 추출합니다. 이러한 방법은 영상의 rotation, translation, scale에 취약한데, 이를 보안한 Diiference of Gaussian을 발전시킨SIFT, SURF, BRISK, ORB, FAST같은 기법들이 사용됩니다.

 

Feature를 만들었다면 각 Feature간의 높은 유사도를 가진 descriptor끼리 매칭시켜주는 과정을 Matching이라고 합니다. 추후에 이러한 Matching은 epipolar geometry로 검증합니다.

Geometric Verification

위에서 feature extraction, matching한 결과를 검증할 필요가 있습니다. 매칭된 특징점 중에는 outlier가 포함될 가능성이 높기 때문에,  RANSAC을 이용한 outlier제거를 합니다.

 

✅ RANSAC 기반의 Geometric Verification 방법

1. 매칭된 특징점에서 일부 샘플을 랜덤하게 선택합니다 (ex: 8-point)
2. 랜덤 선택된 점을 이용해 F-matrix, H-matrix을 추정합니다. (epipolar geometry)
3. 이를 이용해 다른 점들에 대해 추정된 모델과의 오차를 계산합니다. (epipolar constraint)
4. 오차가 임계값 이하인 경우, 해당 경우 inlier로 판단합니다.
5. 위 과정을 여러번 반복 후, 최대 개수의 inlier를 포함하는 모델을 선택합니다.

✅ Epipolar Constraint 검증

1. Fundamental matrix \(F\)를 이용해 점의 정합이 기하학적으로 맞는지 확인합니다.
2. \({p^{'}}^{T}Fp=0\) 과 같이 매칭된 점 \( p, p^{'}\)가 Epipolar Line위에 존재해야 합니다.

✅ Final Refinement

1. RANSAC을 통해 선택된 inliner를 이용해 최종 Fundamental Matrix or Essential Matrix를 재계산합니다.
2. 필요하면 뒤에서 설명할 비선형 최적화 (Bundle Adjustment)를 수행하여 정밀한 정합을 얻습니다.

Initialization

최초로 이미지 2개를 등록합니다. 이는 robustness하고 performance를 위해 중요한 과정입니다. 만약 여기서 여러 카메라로부터 overlap되는 이미지를 선택하면, 중복되는 영역이 반복적으로 최적화되면서 robust, accurate한 reconstruction결과가 만들어집니다. 이와 반대로, 빈도가 낮은 영역을 가지는 이미지들로 선택하면 Bundle Adjustment단계에서 반복적으로 처리할 feature가 적어지므로 reconstruction성능은 줄어들고 연산시간이 줄어들게되는 trade-off가 발생합니다.

 

Image Registration

위 Geometric Verification단계에서 fundamental matrix가 계산되었고, (self)-calibration으로 intrinsic matrix를 구하고, 이로부터 essential matrix를 만든 후 extrinsic을 추정합니다.

 

Triangulation

Triangulation(삼각측량)은 두 개 이상의 이미지에서 매칭된 특징점을 이용해 3D 점을 추정하는 것입니다. 이렇게 구한 3D 포인트들은 SfM의 3D Point Cloud를 구성하는 데이터가 됩니다. 이는 이전에 등록된 3d points를 새로운 이미지로 projection하면 잘 관측된다는 전제하에 이루어집니다. 

triangulation

⭐️Bundle Adjustment

(i, j): (3개 카메라, 4개의 point) 예시

앞선 과정들의 에러를 조정해주기 위해, 비선형 최적화를 합니다. image registration에서 등록된 카메라 pose가 triangulation으로 전파되어 불확실한 3d point 정보로 이어질 수 있습니다. 이를 위해 Bundle Adjustment(BA)를 수행합니다. BA는 reprojection error를 최소화하기 위해 camera parameter P와 3d point X를 non-linear refinement를 수행합니다. \(\pi\)는 projection함수이고, \(\rho_{j}\)는 outlier를 down-weight하기 위한 요소입니다.

위 식을 풀기 위해서 Levenberg-Marquardt라는 비선형 최적화 알고리즘을 수행합니다. 이는 Gradient-Descent + Gauss-Newton이라고 보면 됩니다. Gradient-Descnet의 Jacobian을 사용한다는 성질 + Gauss-Newton의 Hessian을 사용한다는 특성을 합쳐 최적점을 찾습니다. 해당 과정을 수행하지 않으면 3D point가 실제 구조와 다를 수 있어 매우 중요한 과정입니다.

 

Outlier Filtering

PnP (Perspective-n-Point)을 통해 새로운 이미지의 카메라 포즈를 추정합니다. 이는 3D point <-> 2D image 특징점 간 매칭 정보를 통해 R, t를 계산하는 알고리즘입니다. 새로운 이미지에서 기존 3D포인트와의 대응점을 찾아 카메라의 위치를 PnP로 추정하는 과정에서 RANSAC을 사용하여 이상치를 제거하는 과정이 Outlier Filtering입니다. RANSAC-PNP 알고리즘의 주요 순서는 아래와 같습니다.

 

1. 임의로 4개의 2D-3D 매칭된 점을 선택합니다. (Minimal Sample Set)
2. 이 4개의 점을 이용해 PnP로 카메라 포즈 (R,t)를 계산합니다.
3. 계산된 (R, t)로 다른 3D point를 투영한 후 reprojection error를 계산합니다.
   1. 원래 매칭된 2D포인트와 3D->2D로 투영한 포인트와의 거리를 비교합니다.
      1. Reprojection error가 임계값 이하면 inlier로 분류
   2. 이 과정을 반복하면서 가장 많은 inlier를 포함하는 모델을 선택합니다.

 

정리

unordered input image가 들어오면 SIFT같은 알고리즘으로 Feature를 만듭니다. 그리고 Feature Matching을 해주고 Epipolar geometry를 통해 Feature를 correspondence시킵니다. 그 후, Initialization에서 이미지 1쌍을 구하고 Image Registration에서 Fundamental Matrix --> Essential matrix --> R, T를 분해합니다. 이러한 방향정보를 저장하고, 이 정보를 활용해 Triangulation을 해주어 3D point를 구합니다. 그리고 Bundle Adjustment와 outlier filtering으로 에러를 줄이고 이러한 일련의 과정을 이미지가 들어올때마다 반복하여 camera pose와 3d point를 반복적으로 수정합니다.