基于H.264的运动估计算法的研究
|
摘要
H.264是由ITU-T视频编码专家组VCEG( Video Coding Experts Group)和ISO/IEC运动图象专家组MPEG ( Moving Picture Experts Group)共同制定的视频编码标准,这一编码标准可获得更高的编码效率,尤其是在低码率方面比MPEG-4有明显提高,适合低宽带、高质量网络视频应用的需要。
但H.264在提高编码质量、减少码率的同时,却极大的增加了编解码运算的复杂度。通过对H.264编码部分的分析可以得出,运动估计是视频压缩编码中的核心技术之一,也是耗费时间最多的部分。在采用单参考帧和多参考帧预测的情况下,运动估计的运算量分别占整个编码过程运算量的60%、80%左右。因此,如何提高运动估计的效率,使运动估计算法搜索过程更健壮、更快速、更高效成为目前研究的热点之一。
论文首先对H.264标准原理及运动估计部分算法进行了详细阐述,然后从以下三个方面对运动估计部分进行优化: (1)动态搜索范围算法,通过当前编码块运动矢量预测值来动态设置运动搜索的范围,从而减少所需搜索的点数。(2)固定模式快速运动估计算法,主要是在现有UMHexagonS算法的基础上进行改进,来进一步提高运算速度。(3)宏块分块模式的快速抉择,利用各种预测模式出现概率的差异及时、空相关性,缩小当前编码块所需计算的分块模式。经过充分的实验测试,改进后的运动估计算法在保证编码图象质量的同时,能显著减少运动估计的时间,从而加快编码速度。
H.264 is the latest video coding standard, jointly developed by ITU-T VCEG (Video Coding Experts Group) and ISO / IEC MPEG (Moving Picture Experts Group). It can achieve higher coding efficiency than MPEG-4, especially in low bit-rate , and is more suitable for low-bandwidth, high-quality network video applications.
But while improving the quality and reducing the bit-rate, H.264 increased the codec complexity of computation dramatically. After extensive analysis of H.264, motion estimation is one of the core technology, but also the most time-consuming part. For example , in a single-reference frame and multi-reference frame prediction, the computation of motion estimation respectively account for about 60%, 80% of the total computation . Therefore, how to improve the efficiency of motion estimation, and make the search process more robust, faster and more efficient has become a focus of current research.
This thesis introduces the protocol and principle of H.264 and the algorithm of motion estimation in detail firstly, then optimizes the algorithms of the motion estimation from the follow three aspects to accelerate the process of motion estimation. (1) Adaptive Dynamic Search Range Algorithm, determining adaptively the unsymmetrical search range in negative/positive direction of horizontal/vertical axis according to the Predictive Motion Vectors set to reduce the search points. (2) Fixed-mode Fast Motion Estimation Algorithm, mainly focus on the improvements of the existing UMHexagonS algorithm, to further enhance the computational performance of Motion Estimation. (3) Fast Mode Selection Algorithm of Macroblock, utilizing the probability distribution of the various modes and Spatio-Temporal correlation of macroblocks to reduce the number of modes required to compute. Extensive experiments show that these algorithms can achieve significant computational reduction of motion estimation, compared with the previous algorithms in Joint Model (JM) , while maintaining almost the same quality of reconstructed pictures.
但H.264在提高编码质量、减少码率的同时,却极大的增加了编解码运算的复杂度。通过对H.264编码部分的分析可以得出,运动估计是视频压缩编码中的核心技术之一,也是耗费时间最多的部分。在采用单参考帧和多参考帧预测的情况下,运动估计的运算量分别占整个编码过程运算量的60%、80%左右。因此,如何提高运动估计的效率,使运动估计算法搜索过程更健壮、更快速、更高效成为目前研究的热点之一。
论文首先对H.264标准原理及运动估计部分算法进行了详细阐述,然后从以下三个方面对运动估计部分进行优化: (1)动态搜索范围算法,通过当前编码块运动矢量预测值来动态设置运动搜索的范围,从而减少所需搜索的点数。(2)固定模式快速运动估计算法,主要是在现有UMHexagonS算法的基础上进行改进,来进一步提高运算速度。(3)宏块分块模式的快速抉择,利用各种预测模式出现概率的差异及时、空相关性,缩小当前编码块所需计算的分块模式。经过充分的实验测试,改进后的运动估计算法在保证编码图象质量的同时,能显著减少运动估计的时间,从而加快编码速度。
H.264 is the latest video coding standard, jointly developed by ITU-T VCEG (Video Coding Experts Group) and ISO / IEC MPEG (Moving Picture Experts Group). It can achieve higher coding efficiency than MPEG-4, especially in low bit-rate , and is more suitable for low-bandwidth, high-quality network video applications.
But while improving the quality and reducing the bit-rate, H.264 increased the codec complexity of computation dramatically. After extensive analysis of H.264, motion estimation is one of the core technology, but also the most time-consuming part. For example , in a single-reference frame and multi-reference frame prediction, the computation of motion estimation respectively account for about 60%, 80% of the total computation . Therefore, how to improve the efficiency of motion estimation, and make the search process more robust, faster and more efficient has become a focus of current research.
This thesis introduces the protocol and principle of H.264 and the algorithm of motion estimation in detail firstly, then optimizes the algorithms of the motion estimation from the follow three aspects to accelerate the process of motion estimation. (1) Adaptive Dynamic Search Range Algorithm, determining adaptively the unsymmetrical search range in negative/positive direction of horizontal/vertical axis according to the Predictive Motion Vectors set to reduce the search points. (2) Fixed-mode Fast Motion Estimation Algorithm, mainly focus on the improvements of the existing UMHexagonS algorithm, to further enhance the computational performance of Motion Estimation. (3) Fast Mode Selection Algorithm of Macroblock, utilizing the probability distribution of the various modes and Spatio-Temporal correlation of macroblocks to reduce the number of modes required to compute. Extensive experiments show that these algorithms can achieve significant computational reduction of motion estimation, compared with the previous algorithms in Joint Model (JM) , while maintaining almost the same quality of reconstructed pictures.
引文
[1] ThomasWiegand, Gary J. Sullivan.Overview of the H.264/AVC video coding standard [J].IEEE Transactions on Circuits and Systems for Video Technology,2003,13(7):560-579.
[2] MPEG-1 Commitee Draft. ISO/IEC JTCI/SC29/WGII(MPEG-1), ISO/IEC CD 11172: Information technology. Dec. 1991.
[3] Generic Coding of Moving Pictures and Associated Audio Information-Part 2: Video,ITU-T and ISO/IEC JTC 1, ITU-T Recommendation H.262 and ISO/IEC 13 818-2(MPEG-2), 1994.
[4] ITU-T Recommendation H.263. Video Coding for Low Rate. May 1996.
[5] Coding of audio-visual objects—Part 2: Visual,”in ISO/IEC 14 496-2 (MPEG-4 Visual Version 1), Apr. 1999.
[6] T.Wiegand,G.Sullivan,A.Luthra,Draft ITU-T Recommendation and final draft international standard of joint video specification(ITU-T Rec.H.264|ISO/IEC 14496-10 AVC),JVT-G050r1,Geneva,May 2003.
[7] Iain E.G.Richardson. H.264 / MPEG-4 Part 10 White Paper[EB/01].www.vcodex.com,December 2004
[8] Iain E.G.Richardson著,欧阳和译.H.264 and MPEG-4视频压缩[M].长沙:国防科技大学出版社,2004.165-238.
[9]薛全.H.264/ AVC中运动估计、变换与解码器优化[D].浙江:浙江大学博士学位论文,2004.6-8.
[10] A.Murat Tekalp.Digital Video Processing [M].北京:清华大学出版社,1998.156-325.
[11] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro.Motion compensated interframe coding for video conferencing [J].USA:New Orleans,1981.
[12] JASWANT R. JAIN, ANIL K. JAIN.Displacement Measurement and Its Application in Interframe Image Coding [J].IEEE TRANSACTIONS ON COMMUNICATIONS,1981,29(12):1799-1808.
[13] M. GHANBARI . The Cross-Search Algorithm for Motion Estimation[J] . IEEE TRANSACTIONS ON COMMUNICATIONS,1990,38(1):950-953 .
[14] Min-Cheol Hong, Young Man Park.Dynamic Search Range Decision for Motion Estimation [R].VECG-N33. USA:Santa Barbara ,2001
[15] Renxiang Li, Bing Zeng, and Ming L. Liou.A New Three-Step Search Algorithm for Block Motion Estimation [J].IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY,1994,4(4):438-442.
[16] Lai-Man Po and Wing-Chung Ma.A Novel Four-Step Search Algorithm for Fast Block Motion Estimation [J].IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY,1996,6(3):313.317.
[17] Lurng-Kuo Liu and Ephraim Feig.A Block-Based Gradient Descent Search Algorithm for Block Motion Estimation in Video Coding [J].IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY,1996,6(4):419-422.
[18] Luo L J ,Zou C R ,Gao X Q.A new prediction search algorithm for block motion estimationin video coding [J].IEEE Trans on Consumer Electronics,1997,43(1):56-60
[19] Xu J B, Po L M, Cheng C K.Adaptive motion tracking block matching algorithms for video coding [J].IEEE Trans CASVT,1999,9(7):1025-1029.
[20] Shan Zhu and Kai-Kuang Ma.A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation [J].IEEE TRANSACTIONS ON IMAGE PROCESSING,2000,9(2):287-290.
[21] MPEG-4 video verification model version 14.0. ISO/IEC JTCl/SC29/WGII N2 932.1999;301-303.
[22] M.Bierling.Displacement estimation by hierarchical block matching [J].SPIE Visual Communication and Image Processing,1988,1001(5):942-951.
[23]陈涛,王维东,谢磊,张明,王匡.基于矢量加权中值滤波的快速分层运动估计算法[J].浙江大学学报,2004,38(7):811-815.
[24]张旭东,王德生,彭应宁.空时相关多分辨率运动估计算法[J].电子科学学刊,1998,20(3):315-320.
[25] Jae Hun Lee, Kyoung Won Lim.A fast multi-resolution block matching algorithm and its LSI architecture for low bit-rate video coding [J].IEEE Trans.CASVT,2001,11(12):1289-1301.
[26] YK. Tu, J.F. Yang, YN. Shen, M.T. Sun.Fast variable size block motion estimation using merging procedure with an adaptive threshold [J].Proceedings of International Conferenceon ICME' 03,2003,2(3):789-792.
[27] AMTourapis J.Boyce P.Yin.Fast mode decision and motion estimation for JVT/ H.264 [J].International Conference on Image Processing,2003,3:853.856.
[28] S.Wu, KP Lim, F.Pan, X.Lin, D.Wu.Block inter mode decision for fast encoding of H.264 [J].in Proc. IEEE International Conference on Speech,2004,3:181-184
[29] D.J. Wu, S.Rahardja, X.Lin, K.P.Lim, S. Wu.Fast inter mode selection [J].Tech. Rep.,9th Joint Video Team( JVT) Mtg,2003,2 .
[30]李翔,吴国威.一种适用于H. 264的基于自适应搜索范围的快速运动估计算法[J].中国图象图形学报,2004,9(4):471～476.
[31] M.-C. HONG and Y. M. PARK.Dynamic Search Range Decision for Motion Estimation [J].VCEG-N33,2003 .
[32] M.-C. HONG and H.H. OH.Range Decision for Motion Estimation of VCEG-N33 [R].JVT-B022,2002. Switzerland.
[33] M.C. HONG, C.W. KIM, and S.W. RHIE.Further Improvement of MotionSearch Range [R].JVT-C065,2002 .
[34] Zhibo Chen, Jianfeng Xu, Yun He, Junli Zheng.Fast integer-pel and fractional-pel motion estimation for H.264/AVC [J].Journal of Visual Communication&Image Representation,2006,17 :264–290.
[35] Ce Zhu, Xiao Lin, and Lap-Pui Chau.Hexagon-Based Search Pattern for Fast Block Motion Estimation [J].IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY,2002,12(5):349-355.
[36] Z.B.Chen, P Zhou, and Y He.Fast integer pel and fractional pel motion estimation for JVT [R].JVT-F017,2002,6th meeting:Awaji,Japan .
[37]刘根林.H.264实时视频编码技术研究及其DSP实现[硕士毕业论文].刊名,年,卷(期):起止页码.
[38] Alexis M. Tourapis1, Oscar C. Au2, Ming L. Liou.Predictive Motion Vector Field Adaptive Search Technique (PMVFAST)- Enhancing Block Based Motion Estimation [J].Visual Communications and Image Processing,2001.
[39]陈洪新.H.264快速模式选择算法研究[D].武汉:武汉理工大学硕士学位论文,2007.17-28.
[40]毕厚杰.新一代视频压缩编码标准-H.264 / AVC[M].北京:人民邮电出版社,2005.96-103.
[41] Gary J.Sullivan and Thomas Wiegand.Rate-Distortion Optimization for Vedio Compression [J].IEEE Signal Processing Magazine,1998,1:74-90.
[42] Keng-Pang Lim, Gary Sullivan, Thomas Wiegand.Text Description of Joint Model Reference Encoding Methods and Decoding Concealment Methods [R].JVT-O079. 2005. Korea: Busan.7-34 .
[43] Alexis Michael Tourapis, Feng Wu and Shipeng Li.Direct Mode Coding for Bipredictive Slices in the H.264 Standard [J].IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY,2005,15(1):119-126.
[2] MPEG-1 Commitee Draft. ISO/IEC JTCI/SC29/WGII(MPEG-1), ISO/IEC CD 11172: Information technology. Dec. 1991.
[3] Generic Coding of Moving Pictures and Associated Audio Information-Part 2: Video,ITU-T and ISO/IEC JTC 1, ITU-T Recommendation H.262 and ISO/IEC 13 818-2(MPEG-2), 1994.
[4] ITU-T Recommendation H.263. Video Coding for Low Rate. May 1996.
[5] Coding of audio-visual objects—Part 2: Visual,”in ISO/IEC 14 496-2 (MPEG-4 Visual Version 1), Apr. 1999.
[6] T.Wiegand,G.Sullivan,A.Luthra,Draft ITU-T Recommendation and final draft international standard of joint video specification(ITU-T Rec.H.264|ISO/IEC 14496-10 AVC),JVT-G050r1,Geneva,May 2003.
[7] Iain E.G.Richardson. H.264 / MPEG-4 Part 10 White Paper[EB/01].www.vcodex.com,December 2004
[8] Iain E.G.Richardson著,欧阳和译.H.264 and MPEG-4视频压缩[M].长沙:国防科技大学出版社,2004.165-238.
[9]薛全.H.264/ AVC中运动估计、变换与解码器优化[D].浙江:浙江大学博士学位论文,2004.6-8.
[10] A.Murat Tekalp.Digital Video Processing [M].北京:清华大学出版社,1998.156-325.
[11] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro.Motion compensated interframe coding for video conferencing [J].USA:New Orleans,1981.
[12] JASWANT R. JAIN, ANIL K. JAIN.Displacement Measurement and Its Application in Interframe Image Coding [J].IEEE TRANSACTIONS ON COMMUNICATIONS,1981,29(12):1799-1808.
[13] M. GHANBARI . The Cross-Search Algorithm for Motion Estimation[J] . IEEE TRANSACTIONS ON COMMUNICATIONS,1990,38(1):950-953 .
[14] Min-Cheol Hong, Young Man Park.Dynamic Search Range Decision for Motion Estimation [R].VECG-N33. USA:Santa Barbara ,2001
[15] Renxiang Li, Bing Zeng, and Ming L. Liou.A New Three-Step Search Algorithm for Block Motion Estimation [J].IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY,1994,4(4):438-442.
[16] Lai-Man Po and Wing-Chung Ma.A Novel Four-Step Search Algorithm for Fast Block Motion Estimation [J].IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY,1996,6(3):313.317.
[17] Lurng-Kuo Liu and Ephraim Feig.A Block-Based Gradient Descent Search Algorithm for Block Motion Estimation in Video Coding [J].IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY,1996,6(4):419-422.
[18] Luo L J ,Zou C R ,Gao X Q.A new prediction search algorithm for block motion estimationin video coding [J].IEEE Trans on Consumer Electronics,1997,43(1):56-60
[19] Xu J B, Po L M, Cheng C K.Adaptive motion tracking block matching algorithms for video coding [J].IEEE Trans CASVT,1999,9(7):1025-1029.
[20] Shan Zhu and Kai-Kuang Ma.A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation [J].IEEE TRANSACTIONS ON IMAGE PROCESSING,2000,9(2):287-290.
[21] MPEG-4 video verification model version 14.0. ISO/IEC JTCl/SC29/WGII N2 932.1999;301-303.
[22] M.Bierling.Displacement estimation by hierarchical block matching [J].SPIE Visual Communication and Image Processing,1988,1001(5):942-951.
[23]陈涛,王维东,谢磊,张明,王匡.基于矢量加权中值滤波的快速分层运动估计算法[J].浙江大学学报,2004,38(7):811-815.
[24]张旭东,王德生,彭应宁.空时相关多分辨率运动估计算法[J].电子科学学刊,1998,20(3):315-320.
[25] Jae Hun Lee, Kyoung Won Lim.A fast multi-resolution block matching algorithm and its LSI architecture for low bit-rate video coding [J].IEEE Trans.CASVT,2001,11(12):1289-1301.
[26] YK. Tu, J.F. Yang, YN. Shen, M.T. Sun.Fast variable size block motion estimation using merging procedure with an adaptive threshold [J].Proceedings of International Conferenceon ICME' 03,2003,2(3):789-792.
[27] AMTourapis J.Boyce P.Yin.Fast mode decision and motion estimation for JVT/ H.264 [J].International Conference on Image Processing,2003,3:853.856.
[28] S.Wu, KP Lim, F.Pan, X.Lin, D.Wu.Block inter mode decision for fast encoding of H.264 [J].in Proc. IEEE International Conference on Speech,2004,3:181-184
[29] D.J. Wu, S.Rahardja, X.Lin, K.P.Lim, S. Wu.Fast inter mode selection [J].Tech. Rep.,9th Joint Video Team( JVT) Mtg,2003,2 .
[30]李翔,吴国威.一种适用于H. 264的基于自适应搜索范围的快速运动估计算法[J].中国图象图形学报,2004,9(4):471～476.
[31] M.-C. HONG and Y. M. PARK.Dynamic Search Range Decision for Motion Estimation [J].VCEG-N33,2003 .
[32] M.-C. HONG and H.H. OH.Range Decision for Motion Estimation of VCEG-N33 [R].JVT-B022,2002. Switzerland.
[33] M.C. HONG, C.W. KIM, and S.W. RHIE.Further Improvement of MotionSearch Range [R].JVT-C065,2002 .
[34] Zhibo Chen, Jianfeng Xu, Yun He, Junli Zheng.Fast integer-pel and fractional-pel motion estimation for H.264/AVC [J].Journal of Visual Communication&Image Representation,2006,17 :264–290.
[35] Ce Zhu, Xiao Lin, and Lap-Pui Chau.Hexagon-Based Search Pattern for Fast Block Motion Estimation [J].IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY,2002,12(5):349-355.
[36] Z.B.Chen, P Zhou, and Y He.Fast integer pel and fractional pel motion estimation for JVT [R].JVT-F017,2002,6th meeting:Awaji,Japan .
[37]刘根林.H.264实时视频编码技术研究及其DSP实现[硕士毕业论文].刊名,年,卷(期):起止页码.
[38] Alexis M. Tourapis1, Oscar C. Au2, Ming L. Liou.Predictive Motion Vector Field Adaptive Search Technique (PMVFAST)- Enhancing Block Based Motion Estimation [J].Visual Communications and Image Processing,2001.
[39]陈洪新.H.264快速模式选择算法研究[D].武汉:武汉理工大学硕士学位论文,2007.17-28.
[40]毕厚杰.新一代视频压缩编码标准-H.264 / AVC[M].北京:人民邮电出版社,2005.96-103.
[41] Gary J.Sullivan and Thomas Wiegand.Rate-Distortion Optimization for Vedio Compression [J].IEEE Signal Processing Magazine,1998,1:74-90.
[42] Keng-Pang Lim, Gary Sullivan, Thomas Wiegand.Text Description of Joint Model Reference Encoding Methods and Decoding Concealment Methods [R].JVT-O079. 2005. Korea: Busan.7-34 .
[43] Alexis Michael Tourapis, Feng Wu and Shipeng Li.Direct Mode Coding for Bipredictive Slices in the H.264 Standard [J].IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY,2005,15(1):119-126.