Structure from Motion of COLMAP

요즘 DUSt3R와 MASt3R를 읽고있는데요, Structure-from-Motion (SfM)에 대한 이해 없이 접근하다보니 근본없이 개념을 쌓는 느낌입니다. 제가 아는 SfM 알고리즘 중 가장 유명한 COLMAP [1]의 pipeline을 살펴보며 개념을 잡아보려 합니다.

SfM은 정렬되지 않은 이미지의 집합으로부터 3D reconstruction을 하는 알고리즘을 말합니다. 다양한 각도와 위치에서 촬영된 이미지로부터 3D scene을 복원하기 위해서는 복잡한 과정이 필요한데요, COLMAP은 이를 쉽게 사용할 수 있게 만들어준 라이브러리입니다. COLMAP은 SfM 뿐만아니라 그 결과로부터 dense 3D reconstruction을 만들어내는 Multi-View Stereo (MVS)도 포함하는데요, 이번 글에서는 그 중 SfM pipeline만 따로 살펴보겠습니다.

---

Camera Pose Estimation

• 다양한 각도와 위치에서 촬영된 이미지로부터 3D reconstruction을 하기 위해서는 상대적인 카메라의 포즈 추정이 필수적입니다.
• 두 대의 카메라에 동시에 등장하는 점을 특정할 수 있다면, 그 correspondences를 활용해 두 카메라의 상대적인 포즈를 추정할 수 있습니다.
• 내가 가진 정보에 따라 적당한 알고리즘을 골라 사용하면 되겠습니다.
  1. 2D-2D correspondences를 알고 있을 때: (camera 좌표를 모르는) 어떤 3D point가 두 image plane에 각각 투영된 pixel 좌표를 알고있는 경우입니다. Epipolar geometry에 기반해 (calibrated camera의 경우) essential matrix 또는 (uncalibrated camera의 경우) fundamental matrix를 추정할 수 있습니다.
  2. 2D-3D correspondences를 알고 있을 때: 어떤 3D point의 한 camera 좌표계상의 위치를 알고있고, 그 점이 다른 camera의 image plane에 투영된 pixel 좌표를 알고 있는 경우입니다. Perspective-n-points (PnP) 알고리즘을 이용할 수 있습니다.
  3. 3D-3D correspondences를 알고 있을 때: 어떤 3D point의 두 camera 좌표계상의 위치를 모두 알고있는 경우입니다. 두 대의 RGB-D 카메라를 사용하는 경우가 해당될 수 있습니다. Iterative Closest Point (ICP) 알고리즘을 이용할 수 있습니다.

Structure from Motion of COLMAP

전체적인 파이프라인은 아래와 같습니다.

• 입력으로는 N장의 이미지가 주어지고, 두 단계를 거쳐 3D reconstruction이 수행됩니다. 첫번째 단계인 correspondence search의 출력은 scene graph 입니다. Scene graph의 node는 image이고 두 images가 overlap 된다면 edge로 연결됩니다. 이때, overlapping image pair간 feature correspondences를 구해둡니다. 그 다음 단계인 incremental reconstruction에서는 두 장의 initial image pair에서 시작해 나머지 (N-2)장을 하나씩 추가하며 N대의 카메라의 포즈 추정 및 3D point registration을 수행합니다.
  1. Correspondence Search
     • a) Feature Extraction: 각 이미지에 대해 local features를 뽑는 과정입니다. 같은 물체라도 다양한 각도에서 촬영된 이미지가 사용되기 때문에 radiometric 및 geometric changes에 invariant한 appearance descriptor를 사용하는 것이 중요합니다 (e.g., SIFT [2]).
     • b) Matching: Local features를 비교함으로써 image pair의 overlap을 판단하는 과정입니다. 단순히 모든 local features를 비교하게되면 ((image 1의 local features 수) + (image 2의 local features 수))의 제곱만큼의 computation cost가 들기 때문에 다양한 연구에서 제안된 효율적인 방법들 [3, 4, 5]을 사용해줍니다. 이 과정을 거치면 feature correspondences가 구해집니다.
     • c) Geometric Verification: Local features를 appearance descriptor에서 뽑기 때문에 외형적으로 똑같아 보일 경우 잘못 매칭되기 십상입니다. 이런 경우, 딱 그 feature pair만 local하게 봤을때는 그럴듯하게 매칭된 것 같지만, 전체적인 projective geometry로 봤을때는 모순됨을 쉽게 알 수 있습니다. 이런 noise를 제거하기 위해 epipolar geometry에 기반해 essential matrix를 구함으로써 두 이미지간 transformation 관계를 구합니다 (uncalibrated camera라면 fundamental matrix를 구해야하지만 이 글에서는 calibrated camera를 가정하겠습니다). Transformation을 적용했을 때 corresponding features가 다른 이미지로 잘 mapping 된다면 그 image pair는 geometrically verify 되었다고 할 수 있겠습니다. Corresponding features 중 일부가 잘못 매칭되는 경우도 쉽게 발생할 수 있는데요, RANSAC 등의 알고리즘을 활용해 outlier에 강인하게 만드는 기술도 사용해줍니다. 이런 검증 과정을 거친 후에는 geometrically verified overlapping image pairs와 inlier feature correspondence만 남겨집니다.
  2. Incremental Reconstruction
     • a) Initialization: 한 쌍의 overlapping image pair를 골라 initial 3D points를 등록하는 과정입니다. 어떤 pair를 선택하느냐에 따라 앞으로 반복될 b~e 과정의 성능과 속도가 달라기기 때문에 매우 중요합니다. 예를들어 densely overlapping pair를 고르게되면 좀 더 robust하고 accurate한 결과를 얻을 수 있지만 redundancy로 인해 연산량이 많아지게 됩니다. 본인의 어플리케이션이 정확도보다 속도가 중요하다면 sparsely overlapping pair를 고르면 되겠습니다.
       (여기서부터는 Initialization 이후 단계이지만 initial pair에만 적용되니 그냥 여기에 적겠습니다) Corresponding Search 단계에서 구해두었던 essential matrix로부터 camera pose를 계산할 수 있습니다 (feat. SVD). 두 카메라의 intrinsic과 extrinsic을 알게되었으니, triangulation으로 corresponding features의 3D 좌표값을 구할 수 있습니다. 아래 그림 [6]을 보시면 triangulation의 원리가 좀 더 와닿으실 것 같습니다. 이 과정을 거치면 image와 3D points가 "등록"되었다고 표현합니다.
       
     • b) Image Registration: 이제 새로운 이미지를 "등록"할 차례입니다. 등록할 이미지는 이미 등록된 어떤 이미지와 overlapping이 있는 이미지 중에 고르기 때문에, 이미 등록된 3D points에 대한 feature correspondences를 알고있는 상황입니다. 따라서 2D-3D correspondences가 주어진 상황이므로 PnP 알고리즘을 이용해 camera pose를 구할 수 있습니다.
     • c) Triangulation: 이제 새로운 3D points를 "등록"할 차례입니다. 새로 등록한 이미지의 feature 중에는 그 3D point가 이미 등록된 경우도 있지만, 등록되지 않은 경우도 있을 것입니다. 아직 등록되지 않은 3D point의 feature가 등록된 다른 이미지에도 등장했다면 triangulation을 이용해 그 3D point를 등록할 수 있습니다. 이는 scene coverage를 늘림으로써 새로운 이미지를 잘 등록할 수 있게 만들어줍니다.
     • d) Bundle Adjustment (BA): Camera pose를 구하는 과정 (Image Registration)과 3D point로 올리는 과정 (Triangulation)이 분리되어 있고 반복되다보니 구조상 uncertainty가 누적되게 됩니다. 이는 결과의 drift의 누적을 초래해 결국 unrecoverable state에 도달하게 만드는 경우가 흔히 발생합니다. 중간에 조정을 해줌으로써 이 문제를 막기 위해 도입된 것이 BA인데요, reprojection error가 최소화되도록 camera parameters와 3D points를 같이 최적화합니다 (e.g., Levenberg-Marquardt method [7]).
     • e) Outlier Filtering: 이 과정은 논문에 명시적으로 설명하지 않고있는데요, BA 과정에서 reprojection error를 최소화할 때 error가 큰 3D points는 무시하도록 weights가 적용됩니다. Reprojection error가 유난히 큰 3D points는 camera pose와 모순된다고 볼 수 있기 때문에 outliers라고 할 수 있는데요, 이런 outlier points를 제거하는 과정이 아닐까합니다.

---

COLMAP 논문에서는 registeration할 새로운 이미지를 잘 고르는 방법, triangulation을 효율적으로 잘 하는 방법, 효율적인 bundle adjustment를 위해 overlapping image set을 잘 골라내는 방법 등을 새롭게 제안했습니다. 시간날 때 더 읽어보면 좋은 공부가 될 것 같습니다.

References

1. Structure-from-Motion Revisited, CVPR'16
2. Distinctive Image Features from Scale-Invariant Keypoints, IJCV'04
3. Building Rome in a Day, ICCV'09
4. Building Rome on a Cloudless Day, ECCV'10
5. PAIGE: PAirwise Image Geometry Encoding for Improved Efficiency in Structure-from-Motion, CVPR'15
6. https://web.stanford.edu/class/cs231a/course_notes/04-stereo-systems.pdf
7. Bundle Adjustment - a Modern Synthesis, 2000