Journal of the Institute of Electronics Engineers of Korea SP (대한전자공학회논문지SP)

The Institute of Electronics and Information Engineers (대한전자공학회)
권호 표지

A Fast Motion Vector Search in Integer Pixel Unit for Variable Blocks Siz

가변 크기 블록에서 정수단위 화소 움직임 벡터의 빠른 검색

  • 이융기 (세종대학교 컴퓨터공학과) ;
  • 이영렬 (세종대학교 인터넷공학과)
  • Published : 2003.09.01
Download PDF
⟨ Previous Next ⟩

Abstract

In this paper, a fast motion search algorithm that performs motion search for variable blocks in integer pixel unit is proposed. The proposed method is based on the successive elimination algorithm (SEA) using sum norms to find the best estimate of motion vector and obtains the best estimate of the motion vectors of blocks, including 16${\times}$8, 8${\times}$16, and 8${\times}$8, by searching eight pixels around the best motion vector of 16${\times}$16 block obtained from all candidates. And the motion vectors of blocks, including 8${\times}$4, 4${\times}$8, and 4${\times}$4, is obtained by searching eight pixels around the best motion vector of 8${\times}$8 block. The proposed motion search is applied to the H.264 encoder that performs variable blocks motion estimation (ME). In terms of computational complexity, the proposed search algorithm for motion estimation (ME) calculates motion vectors in about 23.8 times speed compared with the spiral full search without early termination and 4.6 times speed compared with the motion estimation method using hierarchical sum of absolute difference (SAD) of 4${\times}$4 blocks, while it shows 0.1dB∼0.4dB peak signal-to-noise ratio (PSNR) drop in comparison to the spiral full search.

본 논문에서 정수단위 화소(integer pixel unit)로 움직임 예측(motion estimation)을 수행하는 빠른 움직임 예측(fast motion estimation) 알고리즘을 제안한다. 제안하는 방법은, sum norm을 사용하여 가장 좋은 움직임 벡터를 찾아내는 연속 제거 기법(SEA : Successive Elimination Algorithm)을 기반으로 16×16블록에서는 전체 영역에 대해 검색을 하고 16×8, 8×16, 8×8블록에서는 16×16블록의 움직임 벡터로부터 그 주위 8개의 위치에서 가장 좋은 벡터를 구하고, 8×4, 4×8, 4×4블록은 8×8블록의 움직임 벡터로부터 그 주위 8개의 위치에서 벡터를 검색하여 그 중에서 가장 좋은 움직임 벡터를 찾아내는 것이다. 이러한 움직임 검색(motion search) 방법을 가변 크기 블록(16×16, 16×8, 8×16, 8×8, 8×4, 4×8, 4×4)으로 움직임 예측을 하는 H.264 부호기(encoder)에 적용하였다. 제안하는 검색 알고리즘을 계산 복잡도 측면에서 보면, 조기 종료가 적용 안 된 나선형으로 전체 영역을 검색(Spiral full search without early termination)하는 방법보다 23.8배가 빨라졌고, 4×4 블록들의 계층적 SAD(Sum of Absolute Difference)를 이용하는 빠른 움직임 예측 방식보다 4.6배의 속도증가를 보인다. 반면에 신호 대 잡음 비(PSNR : Peak Signal to Noise Ratio)는 0.1dB에서 0.4dB정도 떨어짐을 보인다.

Keywords

References

  1. ITU Telecom Standardization Sector, 'Video Codec Test Model Near-Term, Version 10 (TMN10) Draft 1,' H.263 Ad Hoc Group, April 1998
  2. 'Information Technology - Coding of Audio Visual Objects Part2: Visual Amendment 1:Visual Extensions', ISO/IEC JTC1/SC29/WG11N3056, Dec. 1999
  3. 'Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification(ITU-T Rec. H.264 | ISO/IEC 14496-10 AVC)', Joint Vide Team (JVT) of ISO/IEC MPEG and ITU-T VCEG, Mar. 2003
  4. T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, 'Motion compensated interframe coding for video conferencing,' Proc. Nat. Telecommunications Conf., pp. G.5.3.1-G.5.3.5., Nov. 1981
  5. J. R. Jain and A. K. Jain, 'Displacement measurement and its application in interframe image coding,' IEEE Trans. Commun., vol. 29, pp. 1799-1808, Dec. 1981 https://doi.org/10.1109/TCOM.1981.1094950
  6. R. Srinivansan and K. Rao, 'Predictive coding based on efficient motion estimation,' Proc. IEEE IVV'84, pp. 521-526, 1984
  7. S. Zhu and K-K. Ma, 'A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation,' IEEE Trans. Image Processing, vol. 9, no. 2, pp. 287-290, Feb. 2000 https://doi.org/10.1109/83.821744
  8. 윤효순, 손남례, 이귀상, 'A Modified Diamond Search Algorithm for Fast Block Matching Motion Estimation', 대한전자공학회 01 제14회 신호처리 합동 학술대회 논문집 2001,9 v.2001, pp. 393-396
  9. S. G. Kim, T. H. Lee, T. Y. Jung,and D.G. Kim, 'Fast and Efficient Search Algorithm of Block Motion Estimation', 대한전자공학회 00 ITC-CSCC (2) 2000,7 v.2000,pp.885-888
  10. W. Li and E. Salari, 'Successive Elimination Algorithm for Motion Estimation,' IEEE Trans. Image Processing, vol. 9, no. 1, pp.105-107, Jan. 1995 https://doi.org/10.1109/83.350809
  11. M. Brunig and W. Niehsen, 'Fast Full-Search Block Matching,' IEEE Trans. Circuits Syst. Video Technol., vol. 11, no. 2, pp. 241-247, Feb. 2001 https://doi.org/10.1109/76.905989
  12. G. Sullivan and T. Wiegand, 'Rate-Distortion Optimization for Video Compression,' IEEE Signal Processing Magazine, pp. 74-90, Nov. 1998 https://doi.org/10.1109/79.733497
  13. D. M. Young and R. T. Gregory, A Survey of Numerical Mathematics, New York: Dover, vol. 2, pp. 759-762, 1988
  14. http://ftp,imtc-files.org/jevt-experts/reference-software/jm42.zip