[CV] SFM (Structure From Motion) : 연속된 2D 이미지들로 카메라 포즈와 3D shape 재구성하기

본 포스팅에서는 visual localization에 필수적인 2D 영상으로 3D 정보를 추출하는 SFM (Structure From Motion) 에 대해 최대한 수식없이 각 단계의 목적과 의미에 집중하여 소개하려 한다

 

SFM은 GUI가 있는 범용 SFM (Structure From Motion), MVS (Multi View Stereo) 파이프라인인 COLMAP 등의 visual localization task 에서 사용된다. COLMAP의 경우 정렬된 또는 정렬되지 않은 이미지의 reconstruction 기능을 제공한다.(Multi-view 이미지들만 넣으면 camera pose + 3D shape을 복원해줍니다.)

 

* SFM과 유사한 알고리즘?

SFM과 유사한 알고리즘으로 많이 알려져 있는 SLAM, Visual Odometry 등이 있다. 차이점으로는 Visual Odometry에 loop closure이 추가되면 SLAM이고, SLAM에서 real-time으로 동작하지 않아도 되는 경우에 SFM 알고리즘이다. SLAM은 loop closure 기능이 있으며 real-time으로 동작해야하기 때문에 알고리즘이 가벼운 특징이 있고, SFM은 real-time으로 동작하지 않아도 되기 때문에 상대적으로 더 오차가 적고 연산량이 많은 알고리즘이다.
즉 두 알고리즘의 output은 동일하지만 로봇, 자율주행차, AR/VR 기기 등에서 사용자의 위치를 실시간으로 파악할 때는 SLAM이 적절하고, 3D 공간을 복원할 때는 SFM이 적절하다고 볼 수 있다.

 

* COLMAP의 SFM 은 2016년 CVPR에 "Structure-from-Motion Revisited" 논문에 설명되어 있음

 

SFM (Structure From Motion)

Structure From Motion

SFM (Structure From Motion)은 동일한 객체를 다른 시점에서 중첩되도록 찍은 multi-view 이미지들로부터 3D structure와 camera pose를 복원하는 프로세스로 흔히 아래 세가지 단계를 가진다.

1. Feature detection and extraction
2. Feature matching and geometric verification
3. Structure and motion reconstruction

그리고 COLMAP에서는 아래와 같은 주의사항이 있어서 네가지 조건이 잘 충족되지 않으면 3D reconstruction 결과가 좋지 않다. 특히 texture 정보가 많이 없는(패턴이 거의 없는) 객체는 형상이 많이 망가진채로 복원된다.

• Texture 가 좋은 이미지 사용
• 유사한 조명 조건의 이미지 사용
• 시각적으로 많이 중첩된 이미지 사용
• 다양한 viewpoints에서 관측한 이미지 사용

 

Incremental Structure-from-Motion pipline

COLMAP에서는 Incremental Structure-from-Motion 방식을 제안하고, 이는 itreative한 reconstruction 구성 요소가 있는 sequential 프로세스 파이프라인이다.

 

요약하면 input images에서 고유한 feature를 뽑고(Feature Extraction) 이미지 간의 유사한 feature 위치를 matching 시키고 Epipolar geometry 관점에서 이미지 간의 feature의 대응 관계를 본다. 이후 Incremental Reconstruction 단계에서 삼각 측량법을 통해 3D 좌표를 추정하고(Triangulation), Bundle Adjustment와 Outlier Filtering으로 에러를 최소화한다. 마지막으로 이러한 과정을 새로운 이미지가 들어올 때마다 반복해서 camera pose와 3D 좌표를 최종적으로 추정한다.

 

1. Correspondence Search

첫 번째 단계는 Scene overlap 즉, 이미지 간의 동일한 위치를 찾는 correspondence search이다. 이 단계의 output은 기하학적으로 검증된 image pair 들의 집합과 각 point 에 대한 image projection graph이다.

 

1.1. Feature Extraction

Feature는 SFM이 여러 이미지에서 고유한 모양을 인식할 수 있도록 radiometric과 geometric 변화에 불변해야 한다. 때문에 SIFT 같은 feature descriptor 를 사용하여 feature 를 추출한다.

 

1.2. Matching

Feature Matching

각 이미지에서 추출한 feature를 기반으로 이미지 사이에서 동일한 point를 보는 부분을 찾아서 서로 matching. 이 단계까지는 기하학적인 의미가 포함되어 있지는 않다.

 

1.3. Geometric Verification

Epipolar Geometry

Feature matching을 통해 매칭한 포인트들은 모양만 보고 매칭한 결과이기 때문에 실제로 동일한 포인트 끼리 매칭되었다는 보장은 없없다. 굉장히 유사하게 보이는 부분이면 실제로 다른 위치이지만 매칭이 될 수도 있기 때문이다.

 

따라서 SFM은 Epipolar geometry 관점에서 이미지 간의 feature points 를 mapping하는 transformation을 추정하여 기하학적인 일치 여부를 확인한다. Epipolar geometry에서 essential matrix E (calibrated)  또는 fumdamental matrix F (uncalibrated) 를 통해 움직이는 카메라에 대한 관계를 표현할 수 있다. 유효한 transformation이 이미지 사이에 충분한 수의 feature를 mapping하면 기하학적으로 검증된 것으로 간주한다. 즉, 이미지 간의 matching 된 point 들로 부터 적절한 Essential/Fundamental matrix 를 찾는다는 말이다. 그리고 Essential matrix를 SVD(Single Value Decomposition)을 사용하여 linear least squares를 풀면 camera pose(Rotation, Translation) 를 구할 수 있다.

 

 

Feature Matching after RANSAC

Matching 으로부터의 correspondence는 종종 outlier로 오염되기 때문에 RANSAC 등의 robust estimation 기술이 필요하다. RANSAC 알고리즘은 모든 경우의 수 중에서 최대 inlier를 갖는 Essential(또는 Fundamental) matrix를 선택한다. 이 단계에서 output은 기하학적 검증이 완료된 image pair set과 이들 사이의 inlier correspondence와 이들의 geometric relation 이다.

 

 

2. Incremental Reconstruction

Reconstruction 단계에서 입력은 scene graph 이고, 출력은 register된 이미지에 대한 pose estimates 와 reconstruct된 scene structure 이다.

 

2.1. Initialization

SFM은 신중하게 선택된 2-view reconstruction으로 모델을 초기화한다. Reconstruction의 성능은 incremental 프로세스의 seed 위치에 따라 달라지기 때문에 초기화 작업이 매우 중요하다. 카메라 중첩이 많은 곳에서 image graph 의 dense한 위치에서 초기화하면 중복성 증가로 성능이 좋아진다. 

 

2.2. Image Registration

Register 된 이미지(2D-3D correspondences)에서 triangulate된 points에 대한 feature correspondences를 사용하여 Perspective-n-Point(PnP) 문제를 해결하여 새 이미지를 현재 모델에 register할 수 있다. PnP 문제에는 pose와 calibrate 되지 않은 카메라의 intrinsic 파라미터 추정이 포함된다.

 

*Perspective-n-Point (PnP) : Camera intrinsic parameter, 3D points와 이에 대응하는 이미지상의 2D projection points가 주어질 때 camera pose를 구하는 문제

 

2.3. Triangulation

 

오차로 인해 각 이미지 상의 매칭된 두 point에서 ray를 쏘면 3차원 상에 정확하게 일치하지 않는다. 이 때 삼각 측량을 통해 3차원 상에서 x1과 x2의 중점인 x를 구한다.

삼각 측량은 중복성을 통해 기존 모델의 안정성을 높이고 추가 2D-3D correspondece를 제공하여 새 이미지를 등록할 수 있기 때문에 SFM에서 중요한 단계이다.

 

2.4. Bundle Adjustment

 

이전 단계에서 계산한 camera pose 와 3D points를 refine 하여 reprojection error 를 최소화하는 작업이다. 3D point(landmark)에서 카메라 좌표계의 원점까지의 직선을 ray로 표현할 수 있고, 이러한 ray가 여러개 있을 때 'bundles of ray' 라고 표현한다. Reprojection한 위치와 이미지 상의 위치의 차이인 reprojection error 를 cost function으로 사용하여 최적화를 진행하는데, image projection 과정은 non-linear 하기 때문에 Gauss-Newton 등의 non-linear optimization 방법을 사용해야 한다.