In this dissertation, we propose a new method for tracking multiple features from multiple views over time. Features are assumed to move independently. This problem is typically formulated as a multidimensional matching problem (MMP), which is NP-complete with computational complexity $O((n!)^{2m-1})$, where n and m are the number of features and views, respectively. Our method reduces the computational complexity to conceived $O(n^6m^2)$. A mathematical framework, called quantitative relational structure (QRS), is to formulate the multi-views and motion correspondence problem. QRS encodes the correspondence across the view as well as across sequence. Energy function to be optimized in defined QRS.
This multidimensional matching problem is reduced to a manageable one by adopting the split-merge strategy.
The split is the one that divides multi-view into multiple two views. This stage solves stereo-motion correspondence problem. We apply the concept of graduated assignment algorithm, called extended assignment algorithm. Final outcomes of the split are $^mC_2$ stereo-motion correspondence and corresponding energy values. Merge is the process in that sliced stereo-motion correspondences problems are merged to multi-views and motion correspondence one. This method proceeds repeatedly. A structured cluster is proposed. It is very important for the merge and can imply a feature independently moving. A set of structured clusters indicates multi-views and motion correspondence. The overall process is the following. The merge process is started by selecting two views $v_1$ and $v_2$ having maximal energy values among $m_C_2$ stereo-motion correspondences. Then another view $v_3$ is chosen among the rest. Then three stereo-motion correspondences are merged into multi-views $(v_1.v_2,v_3)$ and motion correspondence. This process is repeated until all views are merged or no more increase the energy values.
Experimental results are presented to illustrate the performances of the proposed method. Our algorithm has been tested on various motions, which synthetic and real motion data.
본 논문은 무작위로 움직이는 특징 점들을 추적하는 방법을 제안하고 있다. 대부분의 추적 알고리즘이 과거 추적된 결과를 현재에 반영하고 있는 순차적 추적 방법이 인데 반하여 본 논문의 방법은 인접한 2-3 이미지들을 이용하는 병렬 추적 알고리즘이다. 연구 범위는 물체나 사람에 부착된 마커를 여래(러) 대의 카메라로 그 움직임의 영상을 얻은 후 그 2차원 이미지들을 분석하여 실제 마커의 시간에 따른 정확한 3차원 위치를 복원하고자 한다. 물체의 종류나 그 수에는 제한이 없다. 단 카메라의 내부/외부 매개변수의 값은 알고 있다. 기본적인 접근 방법은 비선형 최적화 기법에 근거한다. 에너지 함수들은 본 논문에서 제안한 정량적 상관구조(quantitative relational structure)기반 위에 만들어진다. 정량적 상관구조는 임의의 시간에 얻어진 이미지들의 관계들을 정량화 된 함수로 표현한 것으로 본 연구의 가장 기초적인 기반을 이루고 있다. 이 구조 위에 시간에 따른 연관관계, 즉 운동에 의한 관계를 나타내는 두 가지 유사성 함수(similarity function)들을 제안하고 있다. 유사성 함수는 추적하는 물체의 움직임에 따라 선택적으로 적용할 수 있다. 움직임이 빠르지 않을 경우 추적하고자 하는 특징 점의 시간에 따른 위치의 변위가 크지 않다는 가정을, 빠른 경우는 속도의 변위가 크지 않다는 가정을 하고 있다. 이 2개의 유사성 함수는 2개의 에너지 함수를 이루는 주요한 요소이다. 제안된 에너지 함수는 비선형 고차식으로 나타나게 되며, 특징 점을 추적하는 문제는 이 함수의 값을 극대화 시키는 대응 관계를 얻는 최적화 문제가 된다. 그러나 이 문제는 NP-complete 문제로 계산의 복잡도는 $O((n!)^{2m-1})$이다. 여기서 n은 영상에서 추출된 특징 점들의 수이고 m은 카메라의 수를 나타낸다.
이 문제를 해결하기 위해 본 연구는 NP-complete 문제의 복잡도를 줄이고자 한다. 제안된 방법은 "분리-병합(split-merge)"로 두 개의 처리 과정으로 구성 되어 있다. 분리 부분은 여러 대의 카메라와 인접한 시간 사이의 대응관계 문제를 두 대의 카메라와 인접한 시간 사이의 대응관계로 문제들로 분할 후 그 문제의 해를 구하는 과정이다. 분할된 문제는 스테레오-운동 대응관계 문제로 두 대 카메라사이의 대응관계와 인접한 시간 사이의 대응관계를 얻게 된다. 이 과정의 최종 결과는 $^mC_2$ 개의 스테레오-운동 대응관계가 된다. 스테레오-운동 대응관계 문제는 graduated assignment algorithm의 개념을 확장, 적용하여 해를 얻었다. 이 방법을 extended graduated assignment algorithm이라 명명한다. 병합(merge) 과정은 앞서 얻은 모든 조합의 2대의 카메라와 시간에 따른 대응 관계들을 하나씩 병합하는 과정이다. 본 논문에서는 구조적인 클러스터(structured cluster)를 제안한다. 이 클러스터는 삼차원 공간에서 움직이는 특징 점을 표현할 수 있다. 분리 과정에서 얻은 스테레오-운동 대응 관계들로부터 그에 대응되는 구조적인 클러스터들의 집합을 쉽게 얻을 수 있다. 이렇게 얻어진 집합들을 반복적으로 병합한다. 합치는 과정에서 가장 중요한 요소는 두 개의 클러스터을 하나의 클러스터로 합치는 처리과정으로 같은 특징 점을 표현하는 클러스터일 경우 하나의 클러스터로 합친다. 병합 과정은 분리 과정에서 얻은 결과 중 가장 에너지 값이 큰 두 대의 카메라와 나머지 중 가장 큰 에너지 값을 가진 카메라에서 시작한다. 이들로부터 얻은 클러스터들의 집합들을 병합함으로써 세 대의 카메라와 운동에 관한 대응관계를 얻게 된다. 이 과정은 반복적으로 모든 카메라와의 대응관계를 얻을 때까지 계속된다. 제안한 알고리즘의 잡음에 대한 안정성을 검증하기 위하여 실제 모션 데이터와 실제 모션의 관절 값으로부터 얻은 모션 데이터에 적용하여 알고리즘의 잡음에 대한 안정성을 검증하였다.
