Probability Constrained Search Range Determination for Fast Motion Estimation

ETRI Journal

关键词: adaptive search range;    H264/AVC;    Motion estimation;   

Others  :  1186371
DOI  :  10.4218/etrij.12.0111.0200

【 摘 要 】

In this paper, we propose new adaptive search range motion estimation methods where the search ranges are constrained by the probabilities of motion vector differences and a search point sampling technique is applied to the constrained search ranges. Our new methods are based on our previous work, in which the search ranges were analytically determined by the probabilities. Since the proposed adaptive search range motion estimation methods effectively restrict the search ranges instead of search point sampling patterns, they provide a very flexible and hardware-friendly approach in motion estimation. The proposed methods were evaluated and tested with JM16.2 of the H.264/AVC video coding standard. Experiment results exhibit that with negligible degradation in PSNR, the proposed methods considerably reduce the computational complexity in comparison with the conventional methods. In particular, the combined method provides performance similar to that of the hybrid unsymmetrical-cross multi-hexagon-grid search method and outstanding merits in hardware implementation.

   

【 参考文献 】

• [1]ITU-T VCEG and ISO/IEC MPEG, “Advanced Video Coding for Generic Audiovisual Services,” ITU-T Recommendation H.264 and ISO/IEC 14496-10 (MPEG-4 AVC), May 2003.
• [2]J. Jain and A. Jain, “Displacement Measurement and Its Application in Interframe Image Coding,” IEEE Trans. Commun., vol. 29, no. 12, Dec. 1981, pp. 1799-1808.
• [3]L.-M. Po and W.-C. Ma, “A Novel Four-Step Search Algorithm for Fast Block Motion Estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 6, no. 3, June 1996, pp. 313-317.
• [4]S. Zhu and K.-K. Ma, “A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation,” IEEE Trans. Image Process., vol. 9, no. 2, Feb. 2000, pp. 287-290.
• [5]C. Cheung and L. Po, “A Novel Cross-Diamond Search Algorithm for Fast Block Motion Estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 12, no. 12, Dec. 2002, pp. 1168-1177.
• [6]C. Zhu, X. Lin, and L.P. Chau, “Hexagon-Based Search Pattern for Fast Block Motion Estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 12, no. 5, May 2002, pp. 349-355.
• [7]Z. Chen, P. Zhou, and Y. He, “Fast Integer and Fractional Pel Motion Estimation for JVT,” JVT-F017r, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, Dec. 2002.
• [8]X. Yi et al., “Improved and Simplified Fast Motion Estimation for JM,” JVT-P021, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, July 2005.
• [9]W. Li and E. Salari, “Successive Elimination Algorithm for Motion Estimation,” IEEE Trans. Image Process., vol. 4, no. 1, Jan. 1995, pp. 105-107.
• [10]M. Brunig and W. Niehsen, “Fast Full-Search Block Matching,” IEEE Trans. Circuits Syst. Video Technol., vol. 11, no. 2, Feb. 2001, pp. 241-247.
• [11]T. Komarek and P. Pirsch, “Array Architectures for Block Matching Algorithms,” IEEE Trans. Circuits Syst., vol. 36, no. 10, Oct. 1989, pp. 1301-1308.
• [12]Y. Jehng, L. Chen, and T. Chiueh, “An Efficient and Simple VLSI Tree Architecture for Motion Estimation Algorithms,” IEEE Trans. Signal Process., vol. 41, no. 2, Feb. 1993, pp. 889-900.
• [13]C. Ou, C. Le, and W. Hwan, “An Efficient VLSI Architecture for H.264 Variable Block Size Motion Estimation,” IEEE Trans. Consum. Electron., vol. 51, no. 4, Nov. 2005, pp. 1291-1299.
• [14]M.-C. Hong and H.H. Oh, “Range Decision for Motion Estimation of VCEG-N33,’’ JVT-B022, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, Feb. 2002.
• [15]M.-C. Hong, C.-W. Kim, and K.S. In, “Further Improvement of Motion Search Range,” JVT-D117, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, July 2002.
• [16]X. Xu and Y. He, “Modification of Dynamic Search Range for JVT,” JVT-Q088, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, Oct. 2005.
• [17]T. Song et al., “Adaptive Search Range Motion Estimation Algorithm for H.264/AVC,” Proc. Int. Symp. Circuits Syst., 2007, pp. 3956-3959.
• [18]S.W. Lee, S.M. Park, and H.S. Kang, “Fast Motion Estimation with Adaptive Search Range Adjustment,” Optical Engineering, vol. 46, no. 4, April 2007, pp. 040504-1-040504-3.
• [19]Z. Chen et al., “A Macroblock Level Adaptive Search Range Algorithm for Variable Block Size Motion Estimation in H.264/AVC,” Proc. Int. Symp. Intell. Signal Process. Comm. Sys., 2007, pp. 598-601.
• [20]H.S. Kang and J.H. Park, “Fast Motion Estimation Based on Search Range Adjustment Using Neighboring MVDs,” Lecture Note in Computer Science, vol. 6455, 2010, pp. 239-248.
• [21]K.-P. Lim, G. Sullivan, and T. Wiegand, “Text Description of Joint Model Reference Encoding Methods and Decoding Concealment Methods,” JVT-N046, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, Jan. 2005.
• [22]H.264/AVC Reference Software JM16.2. http://iphome.hhi.de/suehring/tml/download/
• [23]K. Andersson, R Sjöberg, and A. Norkin, “Reliability Measure for BD Measurements,” ITU-T SG16 Q.6 Document, VCEG-AL22, July 2009.
• [24]S. Lee, S. Park, and J. Park, “270 MHz Full HD H.264/AVC High Profile Encoder with Shared Multibank Memory-based Fast Motion Estimation,” ETRI J., vol. 31, no. 6, Dec. 2009, pp. 784-794.