• COLMAP은
  • SfM(Structure from Motion)과 MVS(Multi-View Stereo)를 범용적으로 사용 할 수 있게 만든 라이브러리
  • https://github.com/colmap/colmap
  • https://openaccess.thecvf.com/content_cvpr_2016/papers/Schonberger_Structure-From-Motion_Revisited_CVPR_2016_paper.pdf
• 개념
  • SfM: 이미지들을 입력으로 받아 Camera Parameter(intrinsic과 extrinsic 모두 포함) 와 Point Cloud를 생성
  • MVS: 'SfM 결과값'을 입력으로 받아 3D 모델을 Reconstruction
• 2016년에 만들어진 알고리즘인데, 글 작성 시점인 2024년에도 3D Reconstruction 분야에서 큰 비중으로 사용되고 있습니다.

1. SfM의 역사

• SfM 연구들은 incremental, hierarchical, global 총 3가지 접근법으로 발전하게 됩니다.
• 이 중 incremental SfM은
  • 이미지를을 sequential하게 반복적으로 처리하는 기법으로써
  • (2016년 시점) 가장 인기있는 접근법이었지만,
  • robustness, accuracy, completeness, scalability 관점에서 general-purpose한 SfM을 만들기 어려웠고
  • COLMAP 논문에서 이를 해결하고자 했다고 합니다.

2. Incremental SfM pipeline

• 
• 아래 1~5번 과정을 거친 후에, 2번 과정으로 다시 돌아가서 진행할 떄는
  • 등록되지 않은 이미지들 중에서, 등록된 이미지들과 feature matching이 많이 된 이미지를 선택하는 과정이 추가로 포함
• 입력 이미지들에서 장면이 겹쳐지는(overlap) 부분을 찾고,
  • 겹쳐지는 이미지들에서 동일한 3D point를 각 이미지로 projection하여 식별
• 출력값은 이미지 Pair집합과,각 점에 대한 이미지 projection 그래프

2.1. Correspondence Search

• 목적
  • 이미지간 feature들의 관계성을 추정

2.1.1. Feature Extraction

• 
• 목적
  • 각 이미지들의 feature를 추출
• feature extraction 알고리즘은 많은 논문에서 (feature) descriptor라고도 부릅니다.
• 여러 이미지들간의 관계성은 각 이미지 feature를 기반으로 만들어지기 때문에,
  • geometric(하고 radiometric)한 변화에도 불변(=invariant)하는 feature를 추출
• 논문에서는 scale, rotation에도 불변하는 SIFT(1999)기법(link)을 사용하고 있습니다.
  • SIFT는 현재까지도 feature exraction 분야에서 표준기법입니다.
  • https://velog.io/@hsbc/SIFT-알고리즘
• 그 외 다른 알고리즘 사용 가능
  • HOG, BRIEF, ORB

2.1.2. Matching

• 
• 목적
  • 2개 이미지 간 feature를 매칭
• 추출한 feature를 바탕으로,
  • 2개 이미지에서 같은 scene part를 찾고,
  • overlap되는 이미지 pair들을 결과로 출력
• 대표 알고리즘
  • Nearest Neighbor 매칭
    • 특징 디스크립터 간의 거리를 계산하여, 가장 가까운 특징 디스크립터를 매칭시키는 방법
    • 이때, 이웃과의 거리가 일정 이상 차이나면 매칭을 거부하는 방식으로 거리 임계값을 설정할 수 있다.
  • RANSAC(Random Sample Consensus)
    • 일부 잘못된 매칭을 걸러내기 위한 방법으로,
    • 일정 개수의 매칭을 무작위로 선택하여 이를 이용하여 모델을 생성하고,
    • 이 모델을 이용하여 나머지 매칭들을 검증하고 정확도가 높은 매칭들만을 선택한다.
  • brute-force matching, FLANN matching
    • cv2.BFMatcher() , cv2.FlannBasedMatcher()
    • https://velog.io/@hsbc/Feature-Matching
• Image마다 Feature를 비교하기 때문에, 시간복잡도가 O(N_i^2, N_Fi^2)
  만큼 됩니다.
  • 이를 해결하기 위해 scalable하고 efficient한 matching 알고리즘들이 제안 되었습니다.
• 최근 matching 알고리즘들
  • ViT기반 LoFTR: https://do-my-best.tistory.com/entry/LoFTR

2.1.3. Geometric Verification

• 목적
  • 매칭을 검증
• Feature matching을 통해 매칭한 포인트들은 모양만 보고 매칭한 결과이기 때문에 실제로 동일한 포인트 끼리 매칭되었다는 보장은 없없다.
  • 굉장히 유사하게 보이는 부분이면 실제로 다른 위치이지만 매칭이 될 수도 있기 때문이다.
• 검증하는 한가지 예시를 들어보겠습니다.
• (https://velog.io/@hsbc/Epipolar-Geometry) 꼭 읽어보기
• 이미지 2장의 관계성을 다루는 Epipolar Geometry분야의
  • relative camera pose를 추정하는 알고리즘들로 상대 pose를 추정한 후에,
  • 기준 view의 feature point들을 -> 다른 view로 projection 했을 때 mapping되는지로 검증 할 수 있습니다.
• 상대 pose 추정은 essential matrix 또는 fundametnal matrix를 계산을 통해서 이루어지며,
  • eight-point, five-point, RANSAC, LMedS, QDEGSAC 등의 기법이 있습니다.
• 2개 이미지에서 확장해서 3개 이상의 이미지에 대해선 trifocal tensor를 사용하게 됩니다.
• 검증시 어떤 기하학적 모델을 사용할지 결정할 때는 GRIC과 같은 기법이 사용하게됩니다.
  • 기하학적 모델의 종류: Essential Matrix, Trifocal Tensor ,Projective Matrix, Calibration Matrix, Rigid Transformation, Affine Transformation 등
• 해당 stage의 결과값은 verified image pair와 correspondence map이며,
  • 선택적으로 geometric relation에 관한 description이 추가
  • 이는 이미지가 node이고 관련있는 이미지 pair가 edge인 scene graph 형태로써 구성되어 집니다.

2.2. Incremental Reconstruction

• 목적:
  • 카메라 parameter와 3D points들을 반복적으로 추정하여
    • camera intrinsic/extrinsic parameter와 3D pointcloud를 결과값으로 획득

2.2.1. Initialization

• 목적
  • 강인한 feature를 갖고 있는 2개의 이미지를 선택

2.2.2. Image Registration

• 목적
  • 선택된 이미지들을 3D reconstruction process에 등록

2.2.3. Triangulation

• 목적
  • 선택된 이미지들의 feature에 삼각함수를 사용해서 3D point들을 임의로 추가

2.2.4. Bundle Adjustment

• 목적
  • 이미지들의 feature와 임의로 추가된 3D point들로, 카메라 parameter를 최적화

2.2.5. Outlier filtering

• 목적
  • Outlier point를 찾아 제거