基于H.264/AVC视频编码运动估计算法的优化
|
摘要
H.264/AVC是由ITU-T视频编码专家组VCEG(Video Coding Experts Group)和ISO/IEC运动图象专家组MPEG(Moving Picture Experts Group)共同制定的视频编码标准,这一编码标准可获得很高的编码效率,尤其是在低码率方面比MPEG-4有明显提高,适合低宽带、高质量网络视频应用的需要。为了方便H.264在低码率高实时性应用系统中的实现,须对其编码算法进行优化。经过对H.264编码器的分析可以得出,运动估计是视频压缩编码中的核心技术之一,采用运动估计和运动补偿技术可消除视频信号的时间冗余以提高编码效率。因此,如何提高运动估计的效率,使运动估计算法搜索过程更健壮、更快速、更高效成为目前研究的热点之一。
本文首先论述了H.264视频编码标准的基本原理和关键技术;然后介绍了几种已有的经典块匹配运动估计算法,并分析了它们的优缺点;随后本文深入的分析了H.264推荐的运动估计核心算法UMHexagonS,针对该算法运动估计实时性不足的缺点,对该算法进行了四方面的优化,分别是初始搜索点的确定(即参考搜索窗口的位置);参考搜索窗口大小的动态生成;大六边形搜索和小六边形(小钻石)搜索模式。优化后的UMHexagonS算法能够高效快速的定位参考搜索窗口的位置和大小,在整个搜索过程中改进的大小六边形搜索模式可以显著减少搜索点数量并能达到较好的匹配效果。
在H.264参考软件模型JM10.1下,经过VC6.0编译,实现该算法,通过对各种测试序列的实验证明,优化后的算法与UMHexagonS算法相比,在重建图象质量和码率接近的情况下,运动估计时间平均节省了18.102%,降低了算法的复杂度,提高了编码器的实时性。
H.264/AVC is the video coding standard jointly developed by ITU-T Video Coding Experts Group (VCEG) and ISO / IEC Moving Picture Experts Group (MPEG). This coding standard has high coding efficiency which is significantly increased in the low bit-rate compared with MPEG-4, and is available for the low-bandwidth, high-quality network video applications. In order to facilitate the realization of H.264 in the low bit rate and real-time application system the coding algorithm has to be optimized. After the analysis of H.264 encoder we can get that, motion estimation is one of the mainly technology for the video compression coding, and with the motion compensation technology they can eliminate time redundant of video signal to improve the coding efficiency. As a result, how to improve the efficiency of motion estimation to make the search process more robust, faster and more efficient becomes one of the hot spots of the current study.
This paper first discusses the basic principles and key technologies of H.264 video coding standard; then introduces several existing classical Block-Matching Motion Estimation and analyses their strengths and weaknesses respectively; whereafter, in depth analyses the H.264 recommended core algorithm of motion estimation– UMHexagonS. Aimed at improving the lack of motion estimation algorithm, four aspects of the algorithm were optimized, which are identification in the initial search point (the location of the reference search range), the dynamically generation of reference search range size as well as big hexagon and small hexagon search mode. Optimized UMHexagonS algorithm can fast and efficient identify the location and size of the reference search range. The improving big and small hexagonal search mode in the entire search process can significantly reduce the number of search point and achieve a better match results.
The optimized algorithm is realized in the H.264 reference software model JM10.1, compiled by VC6.0. Experimenting with some typical video sequences proves that, compared to UMHexagonS algorithm, our optimized algorithm can save about 18.102% ME time and reduce the complexity of original scheme as well as enhance the real-time performance of the encoder but has almost no changing in the reconstructed picture quality and bitrate.
本文首先论述了H.264视频编码标准的基本原理和关键技术;然后介绍了几种已有的经典块匹配运动估计算法,并分析了它们的优缺点;随后本文深入的分析了H.264推荐的运动估计核心算法UMHexagonS,针对该算法运动估计实时性不足的缺点,对该算法进行了四方面的优化,分别是初始搜索点的确定(即参考搜索窗口的位置);参考搜索窗口大小的动态生成;大六边形搜索和小六边形(小钻石)搜索模式。优化后的UMHexagonS算法能够高效快速的定位参考搜索窗口的位置和大小,在整个搜索过程中改进的大小六边形搜索模式可以显著减少搜索点数量并能达到较好的匹配效果。
在H.264参考软件模型JM10.1下,经过VC6.0编译,实现该算法,通过对各种测试序列的实验证明,优化后的算法与UMHexagonS算法相比,在重建图象质量和码率接近的情况下,运动估计时间平均节省了18.102%,降低了算法的复杂度,提高了编码器的实时性。
H.264/AVC is the video coding standard jointly developed by ITU-T Video Coding Experts Group (VCEG) and ISO / IEC Moving Picture Experts Group (MPEG). This coding standard has high coding efficiency which is significantly increased in the low bit-rate compared with MPEG-4, and is available for the low-bandwidth, high-quality network video applications. In order to facilitate the realization of H.264 in the low bit rate and real-time application system the coding algorithm has to be optimized. After the analysis of H.264 encoder we can get that, motion estimation is one of the mainly technology for the video compression coding, and with the motion compensation technology they can eliminate time redundant of video signal to improve the coding efficiency. As a result, how to improve the efficiency of motion estimation to make the search process more robust, faster and more efficient becomes one of the hot spots of the current study.
This paper first discusses the basic principles and key technologies of H.264 video coding standard; then introduces several existing classical Block-Matching Motion Estimation and analyses their strengths and weaknesses respectively; whereafter, in depth analyses the H.264 recommended core algorithm of motion estimation– UMHexagonS. Aimed at improving the lack of motion estimation algorithm, four aspects of the algorithm were optimized, which are identification in the initial search point (the location of the reference search range), the dynamically generation of reference search range size as well as big hexagon and small hexagon search mode. Optimized UMHexagonS algorithm can fast and efficient identify the location and size of the reference search range. The improving big and small hexagonal search mode in the entire search process can significantly reduce the number of search point and achieve a better match results.
The optimized algorithm is realized in the H.264 reference software model JM10.1, compiled by VC6.0. Experimenting with some typical video sequences proves that, compared to UMHexagonS algorithm, our optimized algorithm can save about 18.102% ME time and reduce the complexity of original scheme as well as enhance the real-time performance of the encoder but has almost no changing in the reconstructed picture quality and bitrate.
引文
1 ITU-T Recommendation H.261. Video codec for Audio visual Services at px64kbit/s. 1993
2 ITU-T Recommendation H.263. Video Coding for Low bit rate Communication. version1, 1995; version2, 1998; version3, 2000
3 ISO/IEC 11172. Information technology-coding of moving pictures and associated audio for digital storage media at up to about 1.5 Mbit/s. Geneva, 1993
4 ISO/IEC13818-2. Generic coding of moving pictures and associated audio information-Part 2. Video. 1994
5 ISO/IEC 14496-2: Information technology-coding of audio visual objects-part 2: visual, Geneva, 2000
6 ITU-T Rec. H.264/ISO/IEC 11496-10. Advanced Video Coding. Final Committee Draft, Document JVT-G050, 2003
7余兆明,查日勇,黄磊等.图象编码校准H.264技术.北京:人民邮电出版社. 2006
8毕厚杰.新一代视频压缩编码标准—H.264/AVC.人民邮电出版社,2005.5.
9 ITU-T.通用视听业务的先进的视频编码. 2005
10 P. List, A. Joch, J. Lainema et al. Adaptive Deblocking Filter. IEEE Transactions on Circuits and Systems for Video Technology, 2003
11 UB Video Inc. Emerging H.264 Standard: Overview and TMS3200DM642-Based Solutions for Real-Time Video Applications. http://www.ubvideo.com.Dec.2002
12 Nejat Kamaci, Yucel Altunbasak. Performance comparison of the emerging H.264 video coding standard with the existing standards. ICME. 2003
13丁贵广,计文平,郭宝龙.Visual C++6.0数字图像编码.北京:机械工业出版社,2004
14 M. Ghanbari. The cross-search algorithm for motion estimation. Communications. IEEE Transactions on. 1990, 38(7): 950~953
15 R. Li, B. Zeng, M. L. Liou. A new three-step search algorithm for block motion estimation. IEEE Trans. On Circuits and Systems for Viedo Technology. 1994, 4(4): 438~442
16 L. M. Po, W. C. Ma. A Novel Four Step Search Algorithm for Fast Block motion Estimation. IEEE Tran. Circuits and Systems for Video Technology. 1996, 16(3): 313-317
17 L. Liu, E. Feig. A block-based Gradient Descent Search Algorithm for block Motion Eestimation in Video Coding. IEEE Trans. Circuits Syst. Video Technol. 1996, 6(4): 419~420
18 S. Zhu, K. Ma. New Diamond Search Algorithm for Fast Block Matching Motion Estimation. IEEE Transactions on Image Processing. 2000, 9(2): 287~290
19 Ce Zhu, Xiao Lin, Lap-Pui Chau. Enhanced hexagonal search for fast block motion estimation. IEEE Trans.on Circuits and Systems for Video Technology. 2004, 14(10):1210-1214
20 Z. Chen, J. Xu, Y.He, J. Zheng. Fast integer-pel and fractional-pel motion estimation for H.264/AVC. Journal of Visual Communication and Imag Representation, vol. 17, Special Issue on Emerging H.264/AVC Video Coding Standard. 2006, 264~290
21白然施.视频压缩中运动估计技术的研究.[硕士学位论文],广东:汕头大学, 2003.
22崔之枯,江春,陈丽鑫译.数字视频处理.北京:电子工业出版社,1997.
23 Ce Zhu, Xiao Lin, Lap-Pui Chau. Hexagon-Based Search Pattern for Fast Block Motion Estimation. IEEE Transactions on Circuits and Systems for Video Technology, 2002, 12: 345~355
24 Spyridom K. Kapotas, Athanassion N. SKodars. A New Spatio-Temporal Predictor for Motion Estimation inH.264 Video Coding. Eight International Workshop on Image Analysis for Multimedia Interactive Services. 2007
25 JVT of ISO/IEC MPEG&ITU-T VCEG. Fast Motion Estimation within the JVT codec, Document of JVTE 023, Geneva, Switzerland, 09-17 October, 2002
26 JVT of ISO/IEC MPEG&ITU-T VCEG. Fast ME in the JM reference software, Document of JVT P026. 2005: 24~28
27 Zhen Xing Chen, Yang Song, Ikenaga et al. A Dynamic Search Range Algorithm for Variable Block Size Motion Estimation in H.264/AVC. Information, Communication&Siqnal Processing, 2007 6th InternationalConference on 10-13. 2007: 1~4
28 X. Z. Xu, Y. He. Modification of Dynamic Search Range for JVE. JVT-Q088, Virginia, USA. 2007
29 Thambidurai, P, Ezhilarasan, M, Ramachandran. D. Efficient Motion Estimation Algorithm for Advanced Video Coding. Conference on Computational Intelliqence and Multimedia Application, 2007. International Conference. 2007, 3(13): 47~52
30 J. Jain, A. Jain. Displacement measurement and its application in interframe image coding. IEEE Trans. Commun., vol COM-29, 1981: 1799-1808
31 Z. Chen, P. Zhou, Y. He et al. Fast motion estimation for JVTJVT-G016. 2003
32 X. Yi, J. Zhang, N. Ling, et al. Improved and simplified fast motion estimation for JM JVT-P021. 2005
33 L. Yang, Y. K, J. Li, S. Li. An effective variable block-size early termination algorithm for H.264 video coding. IEEE Trans. Circuits Syst.Video Technol. 2005, 15(6): 784~788
34 J. Xu, Z. Chen, Y. He. Efficient Fast ME predictions and earyly termination strategy based on H.264 statistical character. In The 2003 IEEE Pacific-Rim Conference On Multimeda. 2003, 1: 218~222.
35 JM10.1. Reference Software of H.264. http://iphome.hhi.de/suehring/tml/
36 Mobile.qcif, News.qcif. http://trace.eas.asu.edu/yuv/index.html
37 Joint Video Team(JVT) of ISO/IEC MPEG&ITU-T VCEG(ISO/IEC JTC1/SC29/WG11 and ITU-T SG16 Q.6)17th Meeting: Nice FR, 14-12 October. 2005
38 T. Koga, K.Linuma, A.Hirano et al. Moting compensated interframe coding for video conferencing. Proc. Nat. Thlecommun. Conf., New Orleans, LA. 1981
39 C. H. Tseng, H. M. Wang, J. F. Wang. Enhanced intra-4x4 mode decision for H.264/AVC coders. IEEE Trans. Circuit Syst. Video Technol. 2006, 16(8): 1027~1032
40 H. Schwarz, D. Marpe, G.Blattermanne et al. Improved CABAC. in Joint Video Team of ISO/IEC JTC1/SC29/WG11&ITU-T SG16/Q.6 Doc.JVT-C061, Fairfax,VA. 2002
41 Z. He, S. K. Mitra. A linear source model and a unified rate control algorithm for DCT video coding. IEEE Trans. Ciruits Syst. Video Technol., 2002, 12(11): 970~982
42王军宁,何迪,马娟,胡启龙. TI DSP/BIOS用户手册与驱动开发.北京:清华大学出.2007
43彭启琮.达芬奇技术-数字图象/视频信号处理新平台.北京:电子工业出版社, 2008
44 TMS320 DSP/BIOS User’s Guide, Literature Number:SPRU423E,March 2004
45卞红雨,纪祥香,乔钢等. TMS320C6000系列DSP的CPU与外设.北京:清华大学出.2007
2 ITU-T Recommendation H.263. Video Coding for Low bit rate Communication. version1, 1995; version2, 1998; version3, 2000
3 ISO/IEC 11172. Information technology-coding of moving pictures and associated audio for digital storage media at up to about 1.5 Mbit/s. Geneva, 1993
4 ISO/IEC13818-2. Generic coding of moving pictures and associated audio information-Part 2. Video. 1994
5 ISO/IEC 14496-2: Information technology-coding of audio visual objects-part 2: visual, Geneva, 2000
6 ITU-T Rec. H.264/ISO/IEC 11496-10. Advanced Video Coding. Final Committee Draft, Document JVT-G050, 2003
7余兆明,查日勇,黄磊等.图象编码校准H.264技术.北京:人民邮电出版社. 2006
8毕厚杰.新一代视频压缩编码标准—H.264/AVC.人民邮电出版社,2005.5.
9 ITU-T.通用视听业务的先进的视频编码. 2005
10 P. List, A. Joch, J. Lainema et al. Adaptive Deblocking Filter. IEEE Transactions on Circuits and Systems for Video Technology, 2003
11 UB Video Inc. Emerging H.264 Standard: Overview and TMS3200DM642-Based Solutions for Real-Time Video Applications. http://www.ubvideo.com.Dec.2002
12 Nejat Kamaci, Yucel Altunbasak. Performance comparison of the emerging H.264 video coding standard with the existing standards. ICME. 2003
13丁贵广,计文平,郭宝龙.Visual C++6.0数字图像编码.北京:机械工业出版社,2004
14 M. Ghanbari. The cross-search algorithm for motion estimation. Communications. IEEE Transactions on. 1990, 38(7): 950~953
15 R. Li, B. Zeng, M. L. Liou. A new three-step search algorithm for block motion estimation. IEEE Trans. On Circuits and Systems for Viedo Technology. 1994, 4(4): 438~442
16 L. M. Po, W. C. Ma. A Novel Four Step Search Algorithm for Fast Block motion Estimation. IEEE Tran. Circuits and Systems for Video Technology. 1996, 16(3): 313-317
17 L. Liu, E. Feig. A block-based Gradient Descent Search Algorithm for block Motion Eestimation in Video Coding. IEEE Trans. Circuits Syst. Video Technol. 1996, 6(4): 419~420
18 S. Zhu, K. Ma. New Diamond Search Algorithm for Fast Block Matching Motion Estimation. IEEE Transactions on Image Processing. 2000, 9(2): 287~290
19 Ce Zhu, Xiao Lin, Lap-Pui Chau. Enhanced hexagonal search for fast block motion estimation. IEEE Trans.on Circuits and Systems for Video Technology. 2004, 14(10):1210-1214
20 Z. Chen, J. Xu, Y.He, J. Zheng. Fast integer-pel and fractional-pel motion estimation for H.264/AVC. Journal of Visual Communication and Imag Representation, vol. 17, Special Issue on Emerging H.264/AVC Video Coding Standard. 2006, 264~290
21白然施.视频压缩中运动估计技术的研究.[硕士学位论文],广东:汕头大学, 2003.
22崔之枯,江春,陈丽鑫译.数字视频处理.北京:电子工业出版社,1997.
23 Ce Zhu, Xiao Lin, Lap-Pui Chau. Hexagon-Based Search Pattern for Fast Block Motion Estimation. IEEE Transactions on Circuits and Systems for Video Technology, 2002, 12: 345~355
24 Spyridom K. Kapotas, Athanassion N. SKodars. A New Spatio-Temporal Predictor for Motion Estimation inH.264 Video Coding. Eight International Workshop on Image Analysis for Multimedia Interactive Services. 2007
25 JVT of ISO/IEC MPEG&ITU-T VCEG. Fast Motion Estimation within the JVT codec, Document of JVTE 023, Geneva, Switzerland, 09-17 October, 2002
26 JVT of ISO/IEC MPEG&ITU-T VCEG. Fast ME in the JM reference software, Document of JVT P026. 2005: 24~28
27 Zhen Xing Chen, Yang Song, Ikenaga et al. A Dynamic Search Range Algorithm for Variable Block Size Motion Estimation in H.264/AVC. Information, Communication&Siqnal Processing, 2007 6th InternationalConference on 10-13. 2007: 1~4
28 X. Z. Xu, Y. He. Modification of Dynamic Search Range for JVE. JVT-Q088, Virginia, USA. 2007
29 Thambidurai, P, Ezhilarasan, M, Ramachandran. D. Efficient Motion Estimation Algorithm for Advanced Video Coding. Conference on Computational Intelliqence and Multimedia Application, 2007. International Conference. 2007, 3(13): 47~52
30 J. Jain, A. Jain. Displacement measurement and its application in interframe image coding. IEEE Trans. Commun., vol COM-29, 1981: 1799-1808
31 Z. Chen, P. Zhou, Y. He et al. Fast motion estimation for JVTJVT-G016. 2003
32 X. Yi, J. Zhang, N. Ling, et al. Improved and simplified fast motion estimation for JM JVT-P021. 2005
33 L. Yang, Y. K, J. Li, S. Li. An effective variable block-size early termination algorithm for H.264 video coding. IEEE Trans. Circuits Syst.Video Technol. 2005, 15(6): 784~788
34 J. Xu, Z. Chen, Y. He. Efficient Fast ME predictions and earyly termination strategy based on H.264 statistical character. In The 2003 IEEE Pacific-Rim Conference On Multimeda. 2003, 1: 218~222.
35 JM10.1. Reference Software of H.264. http://iphome.hhi.de/suehring/tml/
36 Mobile.qcif, News.qcif. http://trace.eas.asu.edu/yuv/index.html
37 Joint Video Team(JVT) of ISO/IEC MPEG&ITU-T VCEG(ISO/IEC JTC1/SC29/WG11 and ITU-T SG16 Q.6)17th Meeting: Nice FR, 14-12 October. 2005
38 T. Koga, K.Linuma, A.Hirano et al. Moting compensated interframe coding for video conferencing. Proc. Nat. Thlecommun. Conf., New Orleans, LA. 1981
39 C. H. Tseng, H. M. Wang, J. F. Wang. Enhanced intra-4x4 mode decision for H.264/AVC coders. IEEE Trans. Circuit Syst. Video Technol. 2006, 16(8): 1027~1032
40 H. Schwarz, D. Marpe, G.Blattermanne et al. Improved CABAC. in Joint Video Team of ISO/IEC JTC1/SC29/WG11&ITU-T SG16/Q.6 Doc.JVT-C061, Fairfax,VA. 2002
41 Z. He, S. K. Mitra. A linear source model and a unified rate control algorithm for DCT video coding. IEEE Trans. Ciruits Syst. Video Technol., 2002, 12(11): 970~982
42王军宁,何迪,马娟,胡启龙. TI DSP/BIOS用户手册与驱动开发.北京:清华大学出.2007
43彭启琮.达芬奇技术-数字图象/视频信号处理新平台.北京:电子工业出版社, 2008
44 TMS320 DSP/BIOS User’s Guide, Literature Number:SPRU423E,March 2004
45卞红雨,纪祥香,乔钢等. TMS320C6000系列DSP的CPU与外设.北京:清华大学出.2007