[개념 정리] SfM(Structure from Motion) of COLMAP - 1부

COLMAP은 SfM(Structure from Motion)과 MVS(Multi-View Stereo)를 범용적으로 사용 할 수 있게 만든 라이브러리입니다.

• SfM은 이미지들을 입력으로 받아 Camera Parameter와 Point Cloud를 생성하고
• MVS는 'SfM 결과값'을 입력으로 받아 3D 모델을 Reconstruction합니다.

 

2016년에 만들어진 알고리즘인데 글 작성 시점인 2024년에도 3D Reconstruction 분야에서 큰 비중으로 사용되고 있습니다. 본 글에서는 COLMAP에서 소개하고 있는 SfM 논문인 Structure-from-Motion Revisited (CVPR2016) 에 대해 다루고자합니다. 총 2개 글로 구성하였으며, 1부는 SfM의 역사와 개념에 대해 다루고, 2부는 해당 논문의 주요 알고리즘에 대해 다루겠습니다.

 

 

 

SfM의 역사

SfM의 시초는 self-calibrating metric reconstruction system이었다고 합니다. 정확한 의미는 모르겠지만 camera parameter metric을 구성하는 연구이지 않을까합니다. 1996년부터 시작되었습니다.

- "3d model acquisition from extended image sequences", 1996.

- "Structure from motion without correspondence", CVPR, 2000.

- "Automatic camera recovery for closed or open image sequences", ECCV, 1998.

- "Relative 3d reconstruction using multiple uncalibrated images", IJR, 1995.

- "Visual modeling with a hand-held camera", IJCV, 2004.

 

이 연구들을 foundation으로 사용하여, 인터넷 photo들과 도시 scene reconstruction에 적용되었습니다.

- "Multi-view matching for unordered image sets, or How do I organize my holiday snaps?", ECCV, 2002.

- "Photo tourism: exploring photo collections in 3d", ACM TOG, 2006.

- "Detailed real-time urban 3d reconstruction from video", IJCV, 2008.

 

그 이후 입력 이미지 수를 점차 늘리는 연구들이 등장하게 됩니다.

수천(1000)장 이미지 입력을 처리하는 연구

- "Building rome in a day", ICCV, 2009.

 

수백만(1,000,000)장 이미지를 처리하는 연구

- "Building Rome on a Cloudless Day", ECCV, 2010.

- "Towards linear-time incremental structure from motion", 3DV, 2013.

- "From Single Image Query to Detailed 3D Reconstruction", CVPR, 2015.

- "From Dusk Till Dawn: Modeling in the Dark", CVPR, 2016.

 

수억(100,000,000)장 이미지를 처리하는 연구

- "Reconstructing the World* in Six Days *(As Captured by the Yahoo 100 Million Image Dataset)", CVPR, 2015.

 

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

 

 

 

Incremental SfM pipeline

Incremental SfM 전체 구조는 아래와 같습니다. 설명을 위해 번호를 매겨봤습니다.

큰 Block 위주로 먼저 설명하겠습니다.

이미지들이 입력으로 주어지면,

1) Correspondence Search단계에서 이미지간 feature들의 관계성을 추정하고,

2) Incremental Reconstruction단계에서 카메라 parameter와 3D points들을 반복적으로 추정해서,

camera intrinsic/extrinsic parameter와 3D pointcloud를 결과값으로 획득합니다.

 

좀 더 자세히 설명하자면,

1) Correspondence Search단계에서,

1-1) 이미지들의 feature를 추출(=Feature Extraction)하고,

1-2) 이미지들간의 feature를 매칭(=Matching) 한 후,

1-3) 매칭을 검증(=Geometric Verification)합니다.

 

2) Incremental Reconstruction단계에서,

2-1) 강인한 feature를 갖고 있는 2개의 이미지를 선택(=Initialization)하고,

2-2) 선택된 이미지들을 3D reconstruction process에 등록(=Image Registration)시키고, 

2-3) 선택된 이미지들의 feature에 삼각함수를 사용해서 3D point들을 임의로 추가(=Triangulation)하고,

2-4) 이미지들의 feature와 임의로 추가된 3D point들로 카메라 parameter를 최적화(=Bundle Adjustment)하고,

2-5) 최종적으로 Outlier point를 찾아 제거(=Outlier Filtering)함으로써, 3D를 reconstruction합니다.

2-2) 그 후에 다시 Image Registration를 진행할 때는, 등록되지 않은 이미지들 중에서 등록된 이미지들과 feature matching이 많이 된 이미지를 선택하는 과정이 추가로 포함됩니다.

 

각 단계에 대해 좀 더 상세히 정리해보겠습니다.

 

 

 

1) Correspondence Search

입력 이미지들에서 장면이 겹쳐지는(overlap) 부분을 찾고, 겹쳐지는 이미지들에서 동일한 3D point를 각 이미지로 projection하여 식별합니다. 출력값은 이미지 Pair집합와 각 점에 대한 이미지 projection 그래프입니다.

 

1-1) Feature Extraction

각 이미지마다 feature를 추출합니다. 여러 이미지들간의 관계성은 각 이미지 feature를 기반으로 만들어지기 때문에, geometric(하고 radiometric)한 변화에도 불변(=invariant)하는 feature를 추출합니다. 논문에서는 scale, rotation에도 불변하는 SIFT(1999)기법(link)을 사용하고 있습니다. SIFT는 현재까지도 feature exraction 분야에서 표준기법입니다.(그림출처 : link)

논문에선 robustness를 갖는 다른 알고리즘으로 대체가 가능하다고 나와 있습니다. 따로 찾아보니 HOG, BRIEF, ORB와 같은 다양한 알고리즘(link)이 있습니다. feature extraction알고리즘은 많은 논문에서 (feature) descriptor라고도 부릅니다.

 

1-2) Matching

2개 이미지를 매칭합니다. 추출한 feature를 바탕으로 2개 이미지에서 같은 scene part를 찾고, overlap되는 이미지 pair들을 결과로 출력합니다. Image마다 Feature를 비교하기 때문에, 시간복잡도가 $ O(N_I^2 N_{F_i}^2) $만큼 됩니다. 이를 위해 scalable하고 efficient한 matching 알고리즘들이 제안 되었습니다.

- "Building Rome in a day", ICCV, 2009.

- "Building Rome on a Cloudless Day", ECCV, 2010.

- "Vocmatch: Efficient multiview correspondence for structure from motion", ECCV, 2014.

- "Reconstructing the World* in Six Days *(As Captured by the Yahoo 100 Million Image Dataset)", CVPR, 2015.

- "MatchMiner: Efficient Spanning Structure Mining in Large Image Collections", ECCV, 2012.

- "PAIGE: PAirwise Image Geometry Encoding for Improved Efficiency in Structure-from-Motion", CVPR, 2015.

- "Towards linear-time incremental structure from motion", 3DV, 2013.

그 외, 최근 제가 알고 있는 연구들로는 CNN기반 SuperGlue(2019, link), ViT기반 LoFTR(2021, link)들이 있습니다.

 

1-3) Geometric Verification

matching 결과의 퀄리티를 보장 할 수 없기 때문에 검증과정이 추가됩니다. 검증하는 한가지 예시를 들어보겠습니다. 이미지 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 등의 기법이 있습니다. Epipolar Geometry에 관해서는 이전글을 참고바랍니다. 2개 이미지에서 확장해서 3개 이상의 이미지에 대해선 trifocal tensor를 사용하게 됩니다.

eight points algorithm

검증시 어떤 기하학적 모델을 사용할지 결정할 때는 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) Incremental Reconstruction

scene graph를 입력으로 하여, 결과값으로 각 이미지에 대해 3x3 matrix형태의 pose값과, point set형태의 scene structure를 만듭니다.

 

2-1) Initialization

최초로 등록할 이미지 2개를 선택합니다. robustness하고 accuracy하고 performance 좋은 reconstruction 결과를 만들기 위해서, 이 과정은 매우 중요합니다.

초기 2장을 잘못 선택하면 reconstruction이 불가능 합니다. 여러 카메라로부터 많이 overalp되는 이미지로 선택하게 되면, 중복되는 영역이 반복적으로 최적화되면서 좀더 robust하고 accurate한 reconstruction결과를 만들게 됩니다.

반대로 빈도가 낮은 (sparse한) 영역을 커버하는 이미지들로 선택하게 되면, 뒷단에 Bundle Adjustment단계에서 반복적으로 처리해야 할 feature수가 적어지므로 reconstruction 성능은 낮아지지만 전체적인 연산시간이 줄어들게 됩니다.

때문에 목적에 맞게 선택적으로 초기 이미지 2장을 선택하는 전략을 취하는게 필요합니다.

 

2-2) Image Registration

처음 등록되는 2장 이미지에 대해서는 이미지의 카메라 Pose를 World 좌표계로 등록(Register)합니다. 1-2) Matching으로부터 2개 이미지에 대한 feature matching이 되어 있고, 1-3)에서 상대 포즈와 intrinsic을 정보를 포함하고 있는 fundamental matrix가 계산되었기 때문에, 해당 matrix로 카메라 extrinsic(=카메라 Pose)와 intrinsic을 추정 할 수 있습니다.

그 이후(2-5)에는 이미지는 PnP알고리즘을 사용하여 카메라 Pose를  등록(Register)합니다. PnP알고리즘은 3D 공간에서의 점들의 위치와 해당 점들의 2D 이미지 내 위치를 기반으로 카메라의 포즈(위치와 방향)를 추정하는데 쓰이는 알고리즘입니다. 이미 등록된 이미지들과의 feature correspondence를 사용해서, 새로 등록되는 이미지에 대한 카메라 extrinsic(=카메라 Pose)를 추정하고, intrinsic을 추정합니다. (그림 출처 : link )

PnP Algorithm

잘못된 Outliner가 있을 수 있기 때문에, (주어진  데이터 집합에서 무작위로 선택하여 모델을 추정하고, 이 모델이 전체 데이터 집합에 얼마나 잘 맞는지를 평가하는) RANSAC기법과 minimal pose solver기법을 많은 연구에서 사용하고 있습니다.

 

2-3) Triangulation

최초에는 Epipolar Geometry 개념을 이용하여 3D points를 등록 합니다. 그 이후(2-5) 새로 등록한 이미지의 3d point들을 triangulation(삼각측량법)을 사용해서 이전에 등록한 3d point들에 추가합니다. 이전에 등록된 3d points들을 새로운 이미지로 projection하면 관측 된다는(=Image Registration이 잘됬다는) 전제 하에 이뤄집니다. 이 과정은 반복 loop에서 stability를 증가시키게 되므로 중요한 단계입니다. 많은 multi-view triangulation이 제안되었으며, robustness를 제한하거나 많은 연산량이 필요로 하게 됩니다.

 

2-4) Bundle Adjustment

앞선 과정들은 에러를 내재하고 있으므로, 비선형 최적화를 추가적으로 수행합니다. registration과 triangulation이 구분되어 있으므로, 불확실한 카메라 pose정보는 point로 전파되고 반대로도 될 수 있습니다. 때문에 추가적인 refinement가 필요하며, 이를 Bundle Adjustment(BA)를 통해 수행합니다. BA는 아래 reprojection error을 최소화하기 위해 카메라 parameter P와 point X를 non-linear refinement를 수행합니다. $pi$는 projection 함수이고 $rho$는 outlier를 down-weight하기 위한 factor 입니다.

$$ E = \sum_j \rho_j \left( \| \pi(P_c, X_k) - X_{j} \|_2 \right)^2 $$

BA문제를 풀기 위해서 Levenberg-Marquardt 비선형 최적화 알고리즘 (이전글)을 수행합니다. Gradient-Descent방식과 Gauss-Newton방식을 서로 보완하는 형태로 만든 알고리즘입니다. 이미지수가 많은 경우에 시간복잡도가 증가하게되며, 이를 해결하는 연구들이 존재합니다. (Bundle Adjust에 대해서는 별도 글로 정리해보겠습니다.)

 

 

 

이 글에서는 SfM에 대한 history와 SfM pipeline의 요소를 설명하면서 기본 개념에 대해 다뤄봤습니다. 다음 글에서는 COLMAP 연구에 대해서 다뤄보겠습니다. (글 작성까지는 몇일 소요 될 것 같습니다. 숙제를 만들어 내는 글이되었네요.)