효과적인 조기 중단 기법을 위한 변형된 3단계 탐색 움직임 추정 알고리즘 = Modified 3-step Search Motion Estimation Algorithm for Effective Early Termination

국문 초록 (Abstract)

움직임 추정은 동영상 압축에서 가장 많은 연산량을 차지하는 부분으로 막대한 연산량을 줄이기 위한 많은 고속 탐색 기법이 제안되어 왔다. 움직임 추정에서 가장 많은 연산량을 차지하는 SAD (sum-of-absolute difference) 계산의 경우, 연산량을 줄이기 위해 SAD 계산 중간에 지금까지 계산된 중간값이 지금까지 찾아진 최소 SAD를 넘을 경우 더 이상의 SAD 계산을 중단하고 다음 탐색으로 넘어가는 조기 중단 기법이 많이 사용되고 있다. 본 논문에서는 대표적인 고속 탐색 기법인 3단계 탐색기법을 변형하여 조기 중단이 자주 일어나도록 탐색 위치의 탐색 순서만을 적응적으로 재배열하는 움직임 추정 기법을 제안하였다. 모의 실험 결과, 제안하는 움직임 추정 기법은 추가 연산량이 거의 없이 기존의 3단계 탐색 기법에 비해 동일한 성능을 유지하면서 연산량을 17~30% 감소시켰다.

다국어 초록 (Multilingual Abstract)

Motion estimation occupies most of the required computation in video compression, and many fast search algorithms were propsoed to reduce huge computation. SAD (sum-of-absolute difference) calculation is the most computation-intensive process in the motion estimation. Early termination is widely used in SAD calculation, where SAD calculation is terminated and it proceeds to next search position if partial SAD during SAD calculation exceeds current minimum SAD. In this paper, we proposed a modified 3-step search algorithm for effective early termination where only search order of search positions are adaptive rearranged. Simulation results show that the proposed motion estimation algorithm reduces computation by 17~30% over conventional 3-step search algorithm without extra computation, while maintaining same performance.

목차 (Table of Contents)

• 요약
• Abstract
• Ⅰ. 서론
• Ⅱ. 움직임 추정 방법 및 조기 중단 기법
• Ⅲ. 제안하는 알고리즘
• Ⅲ. 모의 실험 결과
• Ⅳ. 결론
• 참고문헌
• 저자소개

참고문헌 (Reference)

1 Wiegand, T., Sullivan, "Overview of the H.264/AVC video coding standard" 13 (13): 560-576, 2003

2 T. Koga, "Motion compensated interframe coding for video conferencing" 1-5,

3 "ITU-T Recommendation and Final Draft International Standard of Joint Video Specification"

4 W.Choi, "Hierarchical motion search for H.264 variable block-size motion compensation" 45 (45): 1-9, 2006

5 C. Zhu, "Hexagon-Based search pattern for fast block motion estimation" 12 (12): 349-355, 2002

6 L.Winger, "H.264/AVC reference model version JM15.0"

7 Y.W.Huang, "Global elimination algorithm and architecture design for fast block matching motion estimation" 14 (14): 898-907, 2004

8 Z.-B.Chen, "Fast integer-pel and fractional-pel motion estimation for H.264/AVC" 17 (17): 264-290, 2006

9 A.M. Tourapis, "Enhanced Predictive Zonal Search for Single and Multiple Frame Motion Estimation"

10 Guevorkian D, "Architecture for the sum of absolute differences operation"

11 S.Y.Huang, "Adaptive fast block-matching algorithm by switching search patterns for sequences with wide-range motion content" 15 (15): 1373-1384, 2005

12 C.-Y. Su, "Adaptive early termination for fast H.264 Video Coding" 72-76, 2007