Robust Deterministic Fitting of Multiple Structures Using Data Subset Selection
데이터 부분 선택을 이용한 강건한 결정론적 다중구조 피팅 방법
- 주제(키워드) 도움말 Fitting of Multiple Structures , Maximum Feasible Subsystem , Deterministic Method
- 발행기관 서강대학교 영상대학원
- 지도교수 이상욱
- 발행년도 2014
- 학위수여년월 2014. 2
- 학위명 박사
- 학과 및 전공 도움말 영상대학원 미디어공학
- 실제URI http://www.dcollection.net/handler/sogang/000000053381
- 본문언어 영어
- 저작권 서강대학교 논문은 저작권 보호를 받습니다.
초록/요약 도움말
많은 컴퓨터 비전 문제들에서, 데이터는 자주 아웃라이어와 노이즈에 의해 오염된다. RANSAC (Random Sample Consensus) 알고리즘은 널리 사용되는 강건한 파라미터 추정 기법이고, 최근 대부분의 방법들은 랜덤 샘플링에 기반하고 있다. 대부분의 랜덤 샘플링 기반의 기법들은 최적의 반복횟수를 결정하기 위해서, 인라이어의 비율과 같은 데이터에 대한 사전지식이 필요하다. 그러나, 많은 실제 상황에서 정확한 인라이어의 비율을 미리 알 수 없기 때문에, 사용자에 의해 결정되는 것이 일반적이다. 랜덤 샘플링 기반의 기법들은 결과의 강건함에도 불구하고, 무작위적 본질로 인해 결과의 일관성을 보장할 수가 없다. 게다가, 멀티 스트럭쳐들이 존재할 경우 다른 스트럭쳐에 속하는 인라이어들이 아웃라이어로 간주되기 때문에 문제는 더 어려워진다. 최근에 컴퓨터 비전에서 모델 파라미터 추정 문제를 해결하기 위해 전역 최적화 기법이 연구되었다. 이들 방법들은 전역 최적 해를 보장하는 반면, 일반적으로 높은 계산 비용이 요구된다. 많은 데이터셋에 대해서는 전역 최적화 기법들은 RANSAC보다 훨씬 더 많은 계산 시간을 필요로 한다. 본 논문에서, 데이터 부분 선택을 이용한 강건한 결정론적 다중구조 피팅 기법 을 제안한다. 본 논문에서 제안하는 방법들은 결정론적 가설 생성 기법 (deterministic hypothesis generation)과 결정론적 피팅 기법 (deterministic fitting method)의 두 가지로 구분할 수 있다. 결정론적인 방법을 위해 공통적으로 적용되는 주요 아이디어는 전체 데이터 셋을 작은 서브 셋으로 나누고, 나누어진 서브 셋에서 maximum feasible subsystem (MaxFS) 문제를 푸는 것이다. MaxFS 문제를 해결하는데 있어서 데이터의 감소는 알고리즘의 계산적인 실용성을 높여준다. 첫 번째 결정론적인 가설 생성 부분에서, MaxFS 알고리즘이 일관된 초기 가설(hypothesis)들을 생성하기 위해, 공간적으로 겹쳐진 일부 이미지 영역에 속하는 데이터의 서브 셋에 대해서 수행된다. 서브 셋으로부터 생성된 초기 가설(hypothesis)들을 개선하고 residual tolerance 의존도를 제거하기 위해, iterative re-weighted L1 (IRL1) minimization이 전체 데이터에 대해서 수행된다. 두 번째 결정론적인 멀티스트럭쳐 피팅 부분에서, iterative MaxFS with inlier scale (IMaxFS-ISE)은 모델 파라미터들과 인라이어 스케일을 반복적으로 추정한다. 제안된 알고리즘은 매칭 스코어와 데이터 피팅 residual을 기반으로 결정된 top-n ranked subset로부터 가설(hypothesis)을 생성한다. 순차적인 “fitting-and-removing” 방법이 전체 에너지 함수가 더 이상 감소하지 않을 때까지 반복된다. 실험 결과들은 많은 아웃라이어를 포함하는 데이터에서 multi-structure들을 추정하는데 있어서, 본 논문에서 제안하는 두 가지 결정론적인 방법이 랜덤샘플링 기반의 기법들과 비교하여 더 정확하고, 일관적인 가설(hypothesis)들을 생성 할 수 있는 것을 보여 준다. 제안한 방법들은 인라이어 비율과 인라이어 스케일, 스트럭쳐의 갯수와 같은 사전지식 없이 강건하고 효율적으로 동작한다.
more초록/요약 도움말
In many computer vision problems observations or measurements are frequently contaminated with outliers and noise. The Random Sample Consensus (RANSAC) algorithm is a widely used robust estimation technique, and most state-of-the-art methods are based on random sampling. In the majority of random sampling-based methods, to determine the number of optimal iterations, a prior knowledge such as the inlier ratio, is required. However, since the true inlier ratio is a priori unknown in many practical situations, it is necessary for users determine it. Despite their robustness, random sampling-based methods provide no guarantee of consistency in their solutions, due to their randomized nature. Furthermore, the existence of multiple structures makes the problem more difficult since the inliers belonging to other structures are regarded as outliers (pseudo-outliers). Global optimization has recently been actively investigated for model fitting problems in computer vision. While these methods guarantee globally optimal solutions, high computational costs are generally required. For a large dataset, the global optimization methods require a great deal more running time than RANSAC. In this dissertation, robust methods for deterministic fitting of multiple structures using data subset selection are proposed. The main body of this dissertation is composed of two parts: (1) deterministic hypothesis generation, (2) deterministic fitting methods. The commonly used main idea of both methods is solving maximum feasible subsystem (MaxFS) problems for small subsets acquired by dividing the whole dataset. This reduction of data for the MaxFS problem makes the algorithm computationally realistic. In the deterministic hypothesis generation part, the MaxFS algorithm is used to generate consistent initial hypotheses from subsets of data in spatially overlapping local image regions. To refine initial hypotheses estimated from subsets and to remove residual tolerance dependency of the MaxFS algorithm, iterative re-weighted L1 (IRL1) minimization is performed for all image data. In the deterministic fitting part, the presented algorithm, called iterative MaxFS with an inlier scale (IMaxFS-ISE), iteratively estimates model parameters and inlier scale. The proposed algorithm generates hypotheses only with top-n ranked subsets based on matching scores and data fitting residuals. A sequential “fitting-and-removing” procedure is repeated until overall energy function no longer decreases. Experimental results show that proposed methods in this dissertation can generate more reliable and consistent hypotheses than random sampling-based methods for estimating multiple structures from data with many outliers. Both deterministic hypothesis generation and fitting methods can work robustly and efficiently without prior knowledge such as the inlier ratio, inlier scale and number of structures.
more