Structure from motion (SfM) is a process to obtain scene structure information from images from different viewpoints. One of the fundamental problems in on-line SfM system is the tradeoff between accuracy and processing time. For this, batch or sequential algorithm need to be adopted for on-line SfM algorithms. However, batch and sequential algorithms have their own advantage, according to the characteristics of input data. Therefore both batch and sequential algorithms are needed to build a reliable system for on-line SfM.
In this paper, we provide a unifying analysis on batch algorithm and sequential algorithm for SfM. Based on the analysis we devise schemes for SfM, based on expectation-maximization (EM) algorithm. The proposed method has no restriction to any specific motion model or input data type. Moreover the proposed method is a schematic structure that can be extended to any implementation.
The proposed method is tested on both virtual and real data, and is compared to conventional optimization-based algorithms e.g. sparse bundle adjustment (SBA). The result shows, even with simplistic sub-procedure for each step, the proposed method gives comparable results to optimization based algorithms. And the sequential algorithm converges to a good solution without any assumption on the camera movement.
Structure from Motion (SfM)은 서로 다른 시점을 가지는 영상으로부터, 화면 내의 3D 구조 정보와 카메라의 움직임을 찾아내는 과정이다. SfM에서 가장 중요한 문제 중 한가지는, 알고리즘 추정 정확도와 수행 속도 사이의 균형을 맞추는 것이다. 그렇기 때문에 SfM을 수행하는 on-line 시스템을 구현하기 위해서는, 최적화 기반 알고리즘의 적용은 적절하지 않으며 batch나 sequential 알고리즘을 이용해야 한다. 하지만 batch 알고리즘이나 sequential 알고리즘은 각각의 장단점이 있는데, 이는 입력 영상들의 특징이 달라질 수 있다는 데에서 기인한다. 따라서, on-line SfM을 위한 신뢰할 수 있는 시스템은 batch/sequential의 두 가지 알고리즘을 모두 필요로 한다.
본 논문에서는, SfM을 위한 batch와 sequential 알고리즘에 대한 통합적인 접근법을 제시한다. 그리고 expectation-maximization (EM) 알고리즘에 기반하여, SfM을 위한 방법적인 구조를 제안한다. 제안하는 방법은 카메라의 움직임이나 입력 영상에 대한 제한이 없으며, 유연성 있는 구조를 가지기 때문에 다양한 방식으로 구현될 수 있다.
실험적 분석을 위해, 가상으로 생성된 영상과 실제 영상에 제안 방법을 적용하였고 기존의 최적화 기반 알고리즘과 성능 비교를 수행하였다. 제안 기법의 구현에서 각 과정에 매우 간단한 계산 기법을 이용하였으며, 이럼에도 불구하고 최적화 기반 기법과 비교할만한 성능을 나타내고 있다. 또한 sequential 알고리즘은 카메라의 움직임이나 입력 영상에 대한 특별한 가정이 없이도 좋은 해를 향하여 수렴하는 것을 확인하였다.
