ZOE

 객체의 움직임 추출에 있어서 Motion Estimation(ME) 알고리즘이란, 일반적으로 동영상 비디오에서 각 객체 혹은 처리 단위 블록이 시간상 앞뒤 프레임에서 어느 위치로 움직였는지를 추정(Estimation)하는 것을 말하는 것으로 MPEG등의 동영상 압축과 화소 디모자이킹(pixel Demosaicjing), 프레임 보간(Frame Interpolation)등의 비디오 영상처리에서 광범위하게 이용된다.

 Motion Estimation 의 방법에는 여러가지가 있으나 최근의 MPEG4/H.264 압축표준과 같은 이용에 있어서는, 매크로 블록(MacroBlock) 단위로 현재 압축하고자 하는 매크로 블록과, 앞뒤 여러장의 프레임의 주변 매크로 블록과의 각 픽셀간의 명도(Luminance)차이를 최소로 하는 블록을 검색하여 움직임 벡터(Motion Vector)를 결정하게 된다. 본 프로젝트에서는 프레임을16x16의 블록으로 나누어 ME 알고리즘을 적용한다.

 블록 정합 알고리즘에서는 한 블록내의 모든 화소들이 같은 방향으로 평행 이동한다는 것을 가정하여 움직임 추정을 하는 방법으로서, 일정한 탐색 범위에서 모든 화소에 대한 블록을 순차적으로 비교해보는 전 탐색 블록 정합 알고리즘(Full Search Block Matching Algorithm)을 기준으로 하고 있으며, 이는 최적의 움직임 벡터를 구할 수 있지만 계산량이 많은 단점을 갖는다.
 이와 같은 단점을 줄이기 위해 탐색 점의 수를 줄임으로서 움직임 벡터를 보다 고속으로 추정할 수 있는 방법들이 연구되었다. 대표적인 고속 알고리즘으로는 2차원 로그 탐색(Two Dimensional Logarithm Search: 2-D LOG) 알고리즘, 3단계 탐색(Three Step Search: TSS) 알고리즘, 교차 탐색(Cross Search) 알고리즘, 다이아몬드 탐색(Diamond Search: DS) 알고리즘등이 있다.

 움직임 벡터를 추정하는 알고리즘으로 본 과제에서는 정합의 척도인 평균 절대 오차(Mean Absolute Difference: MAD)를 기준으로 지정된 값이상의 MAD를 가진 블록의 움직임 벡터를 추정한다.