Hardware-oriented adaptive motion estimation

Research description

Block-based motion estimation (BBME) is the key element of contemporary video coding systems and the element which can consume over 90% of available computation and external memory bandwidth. Effective hardware implementation is a must to obtain high-quality real-time video coder. The most popular and simplest approach is full search (FS) method which checks all the search points (SPs) within the search area and is characterized by simple data flow and low control overhead. However, it is very costly regarding the computation and memory transfer. Thus, many fast ME algorithms have been proposed which check only a subset of the search space and base on the assumption about unimodality of the error surface. Such algorithms as three step search (TSS) [1] or diamond search (DS) [2] in some cases can obtain results very close to the optimal. However, when encoder supports several spatial resolutions (e.g. QCIF (176×144), CIF (352×288), 4CIF (704×576)) and frame-rates (e.g. 15, 30 fps), these algorithms face the problem of efficient resources utilization. They stop only when all necessary SPs are checked. By this time, the available computational power may be exhausted, making real-time implementation impossible. When the search procedure is interrupted to meet real-time specification, the obtained results may be far from optimal. On the other hand, when computational resources are abundant, traditional ME algorithms are not able to utilize the excess efficiently. Adaptive, computation-aware algorithms [3], [4] can fulfill real-time requirements without significant performance degradation and improve the performance when additional resources are available. These algorithms usually combine several search strategies and select them adaptively according to amount of available resources and estimated motion activity within currently coded video frame [4]. Rapid progress in the microelectronics technology, which makes it possible to integrated even billions of elements within one chip causes that adaptive, computation-aware ME algorithms become more attractive from the hardware viewpoint. Also ubiquity of battery-powered video recording devices such as mobile cameras creates demand for video coding chips able to reduce their power consumption without significant performance degradation.

[1] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, “Motion Compensated Interframe Coding for Video Conferencing”, Proc. Nat. Telecom. Conf., 1981, pp. C9.6.1–C9.6.5.
[2] S. Zhu and K. K. Ma, „A New Diamond Search Algorithm for Fast Block Matching Motion Estimation”, Proc. IEEE Int. Conf. Image Processing (ICIP’97), 1997, pp. 292–296.
[3] C. Y. Chen, Y. W. Huang, C. L. Lee, L. G. Chen, “One-Pass Computation-Aware Motion Estimation with Adaptive Search Strategy”, IEEE Trans. Multimedia, vol. 8, no. 4, pp. 698-706, Aug. 2006
[4] M. Jakubowski, G. Pastuszak, “An Adaptive Computation-Aware Algorithm for Multi-Frame Variable Block-Size Motion Estimation in H.264/AVC”, Proc. The International Conference on Signal Processing and Multimedia Applications SIGMAP ‘09, 2009, pp. 182-185.