Genetic NTSS 기법을 이용한 움직임 추정 = Motion Estimation using Genetic NTSS Method

국문 초록 (Abstract)

기존의 블록 정합 알고리즘인 FS(Full Search)알고리즘은 정확한 움직임 벡터를 구할 수 있으나 요구되는 계산량이 많다. 반면에 국부 탐색을 하는 고속 블록 정합 알고리즘은 FS보다 빠른 탐색을 할 수 있으나 FS 보다 정합 오차가 크다.
본 연구는 전역탐색을 하는 유전자 알고리즘에 빠른 탐색을 하는 블록 정합 알고리즘인 NTSS(New Three Step Search)알고리즘을 제안한다. 제안한 방법에서 각 염색체는 움직임 벡터를 표현하며 초기 염색체는 탐색 공간의 중심 탐색점 가까이에 고정적으로 발생시키고 각 염색체는 MSE(Mean Square Error)값으로 평가된다. 평가된 염색체 중 작은 MSE값을 가지는 염색체가 NTSS의 탐색점 수만큼 다음 세대의 탐색점으로 선택된다. 선택된 염색체는 세대를 거치면서 돌연변이 연산과 교배연산이 행해지고 이때 돌연변이 연산의 크기는 NTSS의 탐색 단계 크기가 된다. 제안한 세대 수 만큼 반복 후 최소의 MSE 값을 가지는 유전자가 해당 블록의 움직임 벡터가 된다.
시뮬레이션 결과 제안한 방법은 가장 우수한 성능을 가지는 FS와 유사한 MSE 값을 얻을 수 있었고 동시에 FS에서 요구되는 계산량에 비해 많은 계산량을 줄일 수 있었다.

다국어 초록 (Multilingual Abstract)

Block-based FS(Full Search) algorithm for motion estimation can find optimal motion vector. However, a heavy computational load is demanded. On the other hand, fast BMAs(Block Matching Algorithm) in local search algorithm take shorter search time than FS to compute motion vector. But the MSE(Mean Square Error) of these fast BMAs is poorer than that of FS.
In this paper, GA(Genetic Algorithm) using NTSS(New Three Step Search) is proposed for global and fast search of motion. The GA is algorithm for searching global maxima and minima and the NTSS is algorithm for fast search. In proposed method, each chromosome represents a motion vector. Initial chromosomes are selected from fixed locations near the central point of the search space. Each chromosome is evaluated by MSE. The chromosomes with smaller MSE are selected as the search points of NTSS in the next generation. And selected chromosome is performed crossover operation and mutation operation. The mutation step size is the same as the search step size of NTSS. After proposed generation, the chromosome with the minimum MSE is the motion vector of the block.
The simulation result shows the proposed method has similar performance to FS in term of MSE. In addition, computational complexity required by the proposed method is lower than computational load of FS.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 블록정합 알고리즘과 유전자 알고리즘
• 3. 제안하는 NTSS 유전자 알고리즘을 이용한 움직임 추정
• 4. 실험 및 결과고찰
• 5. 결론
• 참고문헌
• 저자소개