[들어가며] 

Structure from Motion은 컴퓨터 비전, 그래픽스에서 흔히 사용되는 방법으로 영상으로부터 3D scene을 복원하는 방법입니다. 3D scene의 복원과 함께 카메라 파라미터 추정도 가능하기 때문에 COLMAP이나 VisualSFM과 같은 공개된 툴이 많이 사용되고 있습니다.

SFM은 아래의 과정을 거쳐 3D scene을 복원합니다.

1. 각각의 영상에서 feature를 추출하고 서로 비교하여 대응점(correspondence)을 찾습니다.
2. 처음 두 개의 이미지에 대해 카메라 포즈를 추정하고, 3D point를 복원합니다.
3. 새로운 이미지에 대해 기존의 복원된 점들과의 대응점을 바탕으로 카메라 포즈를 추정하고 새로운 3D point들을 복원합니다.
4. 카메라 파라미터, 복원된 점들에 대해 bundle adjustment를 진행합니다.
5. 3번과 4번의 과정을 반복합니다.

[Camera model]

3D 복원에는 카메라 정보가 필요합니다. 카메라 모델은 pinhole, fisheye 등이 있지만, 본 글에서는 pinhole camera를 가정하겠습니다.

그림 1. Camera projection

카메라는 3차원 세상을 2차원 영상으로 투영(projection)하는 함수로 그림 1과 같이 표현될 수 있습니다. 3D World coordinate system 상의 한 점은 2D image coordinate system 상의 한 점으로 projection됩니다. 이 과정은 다음과 같은 수식으로 표현될 수 있습니다.

K는 내부(intrinsic) 파라미터로 초점 거리(focal length)와 같은 카메라의 특성을 나타내며, [R|t]는 외부(extrinsic) 파라미터로 카메라의 회전(rotation)과 이동(translation)에 대한 정보를 나타냅니다. 3D point가 2d image plane에 projection될 때, 카메라 중심과 3D point를 연결하는 선 위의 모든 점이 하나의 2D point로 projection됩니다. 따라서 특정한 점이 아닌 선 위의 모든 점을 표현하기 위해 scale factor인 s가 사용됩니다.

카메라의 파라미터는 camera calibration을 통해 추정되기도 합니다. 여러 각도에서 촬영된 checker board 영상을 바탕으로 Direct Linear Transform(DLT)을 이용하면 쉽게 추정할 수 있지만, bundle adjustment 과정을 통해서도 추정이 가능하기 때문에 SFM에서 필수적인 과정은 아닙니다.

[Feature matching]

그림 2. 3D 공간의 컵이 서로 다른 위치에서 촬영된 예시

Feature matching은 특정한 3D point에 대해 서로 다른 영상에서 대응점을 찾는 과정입니다. 그림 2와 같이 3D 공간에 컵이 놓여있고, 3개의 다른 방향으로 컵을 촬영했을 때, 왼쪽 그림에서 손잡이의 2D 좌표는 가운데 그림에서 손잡이의 2D 좌표와 다르지만 서로 같은 3d point가 projection된 결과입니다. 각 영상에서 손잡이의 2D 좌표는 대응점이 됩니다. 손잡이 외에도 다양한 위치에 대해서도 대응점을 찾는 과정을 반복합니다. 반복된 과정을 통해 찾은 대응점은 matching table에 저장을 합니다.

대응점을 찾는 과정은 SIFT나 SURF와 같은 알고리즘 기반이나 neural network를 활용한 딥러닝 기반 feature extractor를 사용합니다. 우선 모든 영상에서 feature를 추출합니다. 추출된 각각의 feature는 영상의 특정한 포인트에 대한 정보가 담겨있고, 이 정보를 다른 영상의 정보와 비교하여 각각의 대응 관계를 알 수 있습니다.

[Triangulation]

그림 3. 두 영상의 관계를 나타내는 Fundamental matrix F

Triangulation은 두 영상의 대응점을 3D point로 복원하는 과정입니다. 두 영상의 대응점들로부터 fundamental matrix 또는 essesntial matrix를 계산하고 이를 통해 3D point를 복원합니다. fundamental matrix, essesntail matrix는 두 영상이 촬영된 카메라의 포즈(R,t)의 관계를 나타내는 행렬입니다. essentail matrix는 두 카메라 포즈(R,t)의 정보로만 구성된 행렬이며, fundamental matrix는 카메라의 내부 파라미터 정보도 포함하는 행렬입니다.

그림 3과 같이 3D point X가 존재하고, 이 점이 projection된 x, x’이 있다고 가정합니다. 두 카메라의 관계는 R,t로 표현됩니다. 이 때 fundamental matrix F는 다음의 식을 만족하는 행렬입니다.

4쌍 이상의 대응점이 존재한다면, F는 direct linear transform(DLT)을 통해 쉽게 구해집니다. F로부터 각각의 projection matrix P, P’은 P=K[I|0], P’=K’[R|t]로 계산됩니다. DLT를 통해 계산된 F는 algebric error를 최소화하는 방법으로 추정되었습니다. 하지만 algebric error가 낮아도 geometric(projection) error는 높을 수 있습니다. 따라서 geometric error를 최소화하는 non-linear optimization을 수행해 더 정확한 3D point를 복원할 수 있습니다.

2개의 영상을 통해 3D point를 복원한 후, 새로운 영상을 가져옵니다. matching table을 통해 우리는 복원된 3D point와 새로운 영상의 2D point 사이의 대응 관계를 알 수 있습니다. 이 2D-3D 대응 관계에 대한 Perspective-n-Point(PnP) 문제를 해결하여 새로운 영상의 (R, t)를 구하고, 기존 영상들과의 triangulation을 통해 새로운 3D point들을 복원합니다.

[Bundle adjsutment]

Bundle adjustment는 복원된 3D point와 추정된 카메라 파라미터들을 전부 non-linear optimization 하는 과정입니다.

P: 카메라 파라미터 / X: 3D point / C: 이미지 혹은 카메라 위치의 개수 / N: 복원된 point 개수 / s: 해당 뷰 포인트에서 3D point가 보이는지에 대한 visible matrix / π: projection 함수 

최적화를 위해서는 Jacobian과 Hessian의 역행렬을 구해야 합니다. Jacobian matrix의 경우 모든 영상에서 모든 3D point가 보이지 않기 때문에 많은 부분의 값이 0이 되고, Hessian matrix 또한 sparse한 특성을 갖게 됩니다. Hessian matrix는 복원하려는 3D point가 많을수록 커지기 때문에 많은 연산량을 필요로 합니다. 이 경우 Schur complement 방법을 이용하여 Hessian matrix를 4개의 작은 행렬로 나누어 역행렬을 구할 수 있습니다.

Bundle adjustment 이후에는 새로운 영상의 2D point와 복원된 3D point를 비교하여 새로운 영상에 대한 (R, t)를 계산합니다. (R, t)를 계산한 후 기존의 영상들과의 triangulation을 통해 3D point를 복원한 후 Bundle adjustment를 다시 진행합니다.

[마치며]

본 글에서는 3D scene을 복원하는 방법 중 하나인 SFM에 대해 살펴 보았습니다. 최근에는 딥러닝의 발달과 함께 neural radiance field(nerf)와 같은 딥러닝 기반의 방법들이 지배적이지만, 임의의 영상에 대해 pseudo ground-truth와 같이 카메라의 대한 정보를 얻을 수 있는 방법으로 SFM은 여전히 자주 사용되고 있습니다.

[References]

그림 1 https://www.researchgate.net/figure/Pinhole-Camera-Model-ideal-projection-of-a-3D-object-on-a-2D-image_fig1_326518096

그림 2 https://kr.mathworks.com/help/vision/ug/structure-from-motion.html

그림 3 https://www.researchgate.net/figure/Epipolar-geometry-depiction-the-fundamental-matrix-case-Two-cameras-C-1-and-C-2-are_fig1_347835748

https://web.stanford.edu/class/cs231a/course_notes/04-stereo-systems.pdf

https://www.ipb.uni-bonn.de/html/teaching/photo12-2021/2021-pho1-22-Zhang-calibration.pptx.pdf

https://cvg.cit.tum.de/_media/members/demmeln/qu2018msc.pdf