This thesis presents a structure-from-motion (SfM) based system to build a large-scale 3D scene structure with high accuracy and scalability. A number of approaches have been proposed to this application, but yet unavoidable difficulties exist for applying SfM to real-world applications. Moreover, the situation becomes worse as the scale of the problem gets larger. To overcome the limitations of the conventional SfM, we present a breakthrough in the area of optimization methods and camera-range sensor fusion.
This work consists of two parts: improving the scalability by a novel bundle adjustment and improving accuracy by sensor fusion based SfM with hybrid bundle adjustment.
Bundle Adjustment (BA) is the key and inevitable optimization step in SfM. However, its tremendously high complexity degrades the scalability of the SfM. In the first part of this work, how the proposed bundle adjustment improves the efficiency of computation and convergence of BA is explained. By adapting to the naturally arising block-sparsity and the use of block-based preconditioned conjugate gradients, the computational complexity of the bundle adjustment is substantially reduced. The novel embedded point iterations further help bundle adjustment reduce the number of the wasted iterations.
In the second part of this work, we propose to use a fusion of cameras and range sensors and a novel hybrid bundle adjustment (HBA) to overcome an intrinsic limitation of the traditional image-based SfM, the depth ambiguity. For the sensor fusion, we design a new SfM framework using correspondence-level fusion and multiple feature pool sampling to seamlessly integrate the range measurements with images. For the optimization stage, HBA robustly minimizes different types of errors by augmenting additional damping and gradients generated by range measurement constraints. A scale optimization method is also proposed for the cases that the available amount of range measurements is very limited. Lastly, the hybrid bundle adjustment is applied to camera-3D ToF sensor fusion with a few modifications such as the use of mean-point constraint. The application of HBA to camera-ToF sensor fusion demonstrates that the proposed hybrid bundle adjustment is generally applicable to various types of camera-range sensor sensor fusion.
The improved scalability by the proposed BA is demonstrated by intensive experiments on tens of synthetic and real datasets. The complexity of one BA iteration, speed of convergence, and minimum point after hundreds of iterations of various bundlers are compared and the proposed bundlers outperform other conventional bundlers. The high accuracy of the proposed sensor fusion method with HBA is also demonstrated by a number of comparisons with previous state-of-the-art methods and manual refinement - loop closing by a human operator. The tested sequences were captured at various environments including indoor/outdoor and static/dynamic scenes by several types of sensor fusion systems. Some sequences are in very large-scale and include up to hundreds of thousands of image frames with range measurements to verify the level of accuracy by checking the accumulated errors. The proposed sensor fusion SfM with HBA shows higher accuracy than previous methods for most of sequences. For some sequences, the results obtained by the proposed method are comparable or even better than that of the manual refinement. The proposed method also handles the degenerate cases of conventional SfM by resolving the depth ambiguity problem.
이 논문은 높은 정확도(accruacy)와 뛰어난 확장성(scalability)을 가지는 움직임 기반 구조 복원(structure-from-motion, SfM) 기술에 대하여 논의한다. 최근까지 이를 위한 다수의 접근법들이 제안되어 오고 있느나, 여전히 SfM을 실용적인 애플리케이션에 적용하기에는 많은 어려움이 존재하고 있다. 게다가 적용 될 문제의 크기가 커질수록 더 많은 어려움이 초래된다. 본 논문에서는 기존의 SfM 방법론들이 가지는 한계점들을 극복하기 위한 돌파구를 최적화 및 영상-거리 센서 융합(camera-range sensor fusion)에서 찾고자 하였다.
본 연구는 크게 ``새로운 BA 에 의한 확장성의 개선" 과 ``센서 융합과 혼성 BA(hybrid bundle adjustment, HBA)에 의한 정확도 개선" 으로 나뉜다. 번들 어드저스트먼트(bundle adjustment, BA)는 SfM의 필수적인 최적화 과정이지만, 매우 높은 계산 복잡도로 인해 SfM 의 확장성을 크게 떨어뜨린다. 본 연구의 전반부에서는 제안된 새로운 BA가 어떻게 기존의 BA 의 계산 및 수렴 효율을 향상시키는 지가 설명되었다. 자연적으로 나타나는 블록 성김(block sparsity)을 활용하고 블록 기반의 전처리된 복소구배법(block-based preconditioned conjugate gradients)을 사용함으로써, BA의 계산 복잡도가 크게 감소되었다. 또한 새로운 내장형 구조 반복 최적화(embedded point iterations)는 낭비되던 BA 반복 계산 횟수를 줄여 줌으로써 수렴 효율을 개선하였다.
본 연구의 후반부에서는 기존의 영상 기반 SfM 의 본질적 한계인 깊이 모호성(depth ambiguity)을 극복하기 위하여 카메라와 거리 센서의 융합 방법 및 새로운 HBA 가 제안되었다. 센서 융합에서는 영상과 거리 정보를 매끄럽게 융합하기 위하여 대응점 수준 융합(correspondence-level fusion)과 복수 특징점 집합 기반 표본 추출법(multiple feature pool sampling)이 제안되었다. 최적화 단계에서는 거리 정보의 제한 조건에서 만들어진 감폭(damping) 및 변화도(gradient)를 기존의 최적화 문제에 증강하여 서로 다른 종류 및 단뤼를 가지는 오차가 HBA에 의하여 강인하게 최소화된다. 또한 사용 가능한 거리 정보의 양이 매우 제한적인 상황에 대비하기 위한 비율 최적화(scale optimization)방법도 제안되었다. 끝으로 평균점 제약 조건(mean-point constraint)을 이용하여 카메라-3D ToF 센서 융합에 적합한 형태로 HBA를 적용함으로써, 제안된 HBA가 다양한 형태의 카메라 거리센서 융합에 적용가능함을 보였다.
제안된 BA 로 인하여 향상된 확장성은 수십 가지의 가상(synthetic) 및 실제(real)로 만들어진 복원 자료를 이용한 실험에 기반하여 검증되었다. 계산 복잡도, 수렴 속도, 수백 번 반복된 BA 계산 후의 최소점 등을 비교하였으며, 제안된 방법을 이용하는 BA 들이 기존의 BA 들 보다 뛰어난 성능을 보였다. 제안된 센서 융합 및 혼성 BA 로 향상된 정확도 또한 기존의 방법들 및 수동 개선(manual refinement) 결과와의 다수의 비교 실험을 통하여 입증된다. 실험에 사용된 영상 시퀀스들은 실내/실외 및 정적/동적 환경의 장면들에 걸쳐 다양한 융합 센서에 의하여 촬영되었다. 일부 시퀀스들은 정확도를 누적 오차를 통해 확인할 수 있도록 매우 큰 규모이며 수십만 장의 영상 및 거리 정보를 포함한다. 제안된 센서 융합 기반 SfM 및 혼성 BA 를 이용한 방법론은 대부분의 영상 시퀀스를 대상으로 기존의 방법론보다 뛰어난 정확도를 보인다. 일부 시퀀스에 대해서는 수동 개선된 결과와 유사한 혹은 뛰어난 결과를 보인다.
