基于MPEG-4的视频压缩编码运动估计算法研究
|
摘要
计算机技术和网络技术的发展和普及,大大推动了视频技术的发展和应用,数字视频技术在当前的信息社会中日益发挥着重要的作用。MPEG-4作为新一代的视频压缩编码标准,由于其本身具有诸多的优越性能和高效的压缩效率,使其在Internet多媒体应用、实时可视通信等诸多方面得到了广泛应用。
影响MPEG-4视频压缩编码质量和效率的因素很多,运动估计是其中最有影响力的因素之一。运动估计越准确,解码出来的视频图像质量越好。而且运动估计在整个视频压缩编码系统中耗时最多。因此快速、准确的运动估计算法是视频压缩编码技术的研究重点。
本文首先对MPEG-4标准的特性作了一个简要的介绍,然后对MPEG-4中的关键算法——基于块匹配的运动估计的基本原理和要素进行了阐述,并分析了一些快速算法的特点,在此基础上分别对运动估计算法从速度和准确度两个方面进行改进:
提出了基于内部预测的快速菱形算法,通过对菱形算法进行内部预测从而减少搜索点数,并利用运动矢量的相关性来进行起点预测,将宏块划分成不同的运动类型从而选用不同的搜索方式。实验结果表明此算法大大提高了运动估计的速度。
传统的快速算法都是基于误差函数呈单峰分布的假设,在搜索过程易陷入局部最优,从而导致搜索精度不高,视频编解码质量下降。本文又提出的基于模拟退火的自适应运动估计算法,它针对传统快速算法的不足,在搜索的过程中加入了模拟退火,并引人了自适应机制,根据宏块的特性而设置参数,因而具有很强的自适应性,在模拟退火结束后还进行了梯度下降搜索,进一步提高匹配的精度。实验结果表明此算法极大的降低了搜索陷入局部最优的可能,提高了视频编解码质量。在应用中可以根据对速度和质量的侧重点不同在两种运动估计算法中进行选择。
With the development and popularization of computer and network technology, video technology has been widely applied to various applications and plays a more and more important role nowadays. MPEG-4 is a popular video compression coding standard, which is applied to plenty of relative areas such as internet multimedia, real-time visual communication and etc. because of its powerful performance and high compression efficiency.
Among the factors which influence the coding quality and efficiency for MPEG-4, motion estimation technology is the most important one. It is known that the accuracy of motion estimation usually determines the quality of decoded images to a great extent. However, motion estimation contributes to the most part of computational load in the whole video coding system. Thus research on efficient motion estimation algorithm becomes a focus in video coding field.
At first, this paper gives an overview of the specialties of MPEG-4,then introduce the basic theory and key points of its core technology, which is block-matching motion estimation. On the basis of the analysis on popular fast block-matching algorithms, two novel algorithms are respectively proposed, aiming at the improvement of quality and speed.
In this paper, a new algorithm called inner predictive diamond fast motion estimation is proposed, applying inner predictive technique to speed up original diamond search. It also takes advantage of the correlation of adjacent macro-blocks to predict the initial search point, and uses appropriate search strategy for different motion style macro-blocks. Experimental results show that the proposed algorithm greatly improves searching speed.
Traditional estimation algorithms based on the local unimodal error surface assumption have an inherent shortcoming of getting into the local optima, which leads to degeneration on the quality of video images. Therefore, an adaptive motion estimation algorithm using simulated annealing is proposed to overcome this shortcoming. It is highly adaptive since its parameters are setup according to the characteristic of macro-block in search process. Moreover, there is refined search after SA to enhance matching precision. The simulations show that this proposed algorithm is robust against local minima and improves searching accuracy remarkably. In conclusion, it depends on the different requirement between quality and speed to choose the more suitable one of above proposed algorithms.
影响MPEG-4视频压缩编码质量和效率的因素很多,运动估计是其中最有影响力的因素之一。运动估计越准确,解码出来的视频图像质量越好。而且运动估计在整个视频压缩编码系统中耗时最多。因此快速、准确的运动估计算法是视频压缩编码技术的研究重点。
本文首先对MPEG-4标准的特性作了一个简要的介绍,然后对MPEG-4中的关键算法——基于块匹配的运动估计的基本原理和要素进行了阐述,并分析了一些快速算法的特点,在此基础上分别对运动估计算法从速度和准确度两个方面进行改进:
提出了基于内部预测的快速菱形算法,通过对菱形算法进行内部预测从而减少搜索点数,并利用运动矢量的相关性来进行起点预测,将宏块划分成不同的运动类型从而选用不同的搜索方式。实验结果表明此算法大大提高了运动估计的速度。
传统的快速算法都是基于误差函数呈单峰分布的假设,在搜索过程易陷入局部最优,从而导致搜索精度不高,视频编解码质量下降。本文又提出的基于模拟退火的自适应运动估计算法,它针对传统快速算法的不足,在搜索的过程中加入了模拟退火,并引人了自适应机制,根据宏块的特性而设置参数,因而具有很强的自适应性,在模拟退火结束后还进行了梯度下降搜索,进一步提高匹配的精度。实验结果表明此算法极大的降低了搜索陷入局部最优的可能,提高了视频编解码质量。在应用中可以根据对速度和质量的侧重点不同在两种运动估计算法中进行选择。
With the development and popularization of computer and network technology, video technology has been widely applied to various applications and plays a more and more important role nowadays. MPEG-4 is a popular video compression coding standard, which is applied to plenty of relative areas such as internet multimedia, real-time visual communication and etc. because of its powerful performance and high compression efficiency.
Among the factors which influence the coding quality and efficiency for MPEG-4, motion estimation technology is the most important one. It is known that the accuracy of motion estimation usually determines the quality of decoded images to a great extent. However, motion estimation contributes to the most part of computational load in the whole video coding system. Thus research on efficient motion estimation algorithm becomes a focus in video coding field.
At first, this paper gives an overview of the specialties of MPEG-4,then introduce the basic theory and key points of its core technology, which is block-matching motion estimation. On the basis of the analysis on popular fast block-matching algorithms, two novel algorithms are respectively proposed, aiming at the improvement of quality and speed.
In this paper, a new algorithm called inner predictive diamond fast motion estimation is proposed, applying inner predictive technique to speed up original diamond search. It also takes advantage of the correlation of adjacent macro-blocks to predict the initial search point, and uses appropriate search strategy for different motion style macro-blocks. Experimental results show that the proposed algorithm greatly improves searching speed.
Traditional estimation algorithms based on the local unimodal error surface assumption have an inherent shortcoming of getting into the local optima, which leads to degeneration on the quality of video images. Therefore, an adaptive motion estimation algorithm using simulated annealing is proposed to overcome this shortcoming. It is highly adaptive since its parameters are setup according to the characteristic of macro-block in search process. Moreover, there is refined search after SA to enhance matching precision. The simulations show that this proposed algorithm is robust against local minima and improves searching accuracy remarkably. In conclusion, it depends on the different requirement between quality and speed to choose the more suitable one of above proposed algorithms.
引文
[1] International Telecommunication Union. Video Code for Audio-visual Services at p x 64kbit/s. ITU-T Recommendation H.261. 1993
[2] ISO/MPEG-1 ISO11172-2. Coding of Moving Picture and Associated Audio for Digital Storage Media at up to about 1.5Mbit/s. 1991
[3] International Telecommunication Union. Video Coding for Low Bit Rate Communication. ITU-T Recommendation H.263. 1995
[4] ISO/IEC JTC1/SC29/WG11, ISO/IEC CD13818.Information Technology MPEG-2 Committee Draft.1993
[5] ISO/IEC JTC1/SC29/WG11 N2687. MPEG-4 Video Verification Model Version 13.0. 1999
[6] ISO/IEC JTC1/SC29/WG11 N2194. MPEG98.MPEG-4 Requirements.1998
[7] Thomas Sikora ,Senior Member. The MPEG-7 Visual Standard for Content Descriotion An Overview. IEEE Trans.Circuits Syst.Video Technol. 2001,11(6)
[8] Olivier Avaro,et al. MPEG7 System. IEEE Trans .Circuits Syst. Video Technol. 2001.11.(6)
[9] lain E.G.Richardson. H.264 and MPEG4 video compression.Video coding for next-generation multimedia. 2003
[10] 赵巍,艾斯卡尔. MPEG4 视频压缩编码技术及应用.信息技术.2005.9
[11] 张益贞,刘滔. Visual C++实现 MPEG/JPEG 编解码技术. 人民邮电出版社. 2002: 173-408.
[12] 王川. MPEG 编码国际标准技术的特点及应用. 大众科技. 2006.No.7
[13] ISO/IEC JTC1/SC29/WG11 N3342. Overview of the mpeg-4 Standard. 2000.3
[14] ISO/IEC JTC1/SC29/WGllN3908. Weiping Li, Jens-Rainer Ohm, Mihaela van der Schaar, Hong Jiang, Shipeng Li. MPEG-4 Video Verification Model version 18.0. January 2001/Pisa
[15] 李强,贺晓华. 数字电视视频压缩标准. 湖南人文科技学院学报. 2006.(6).3
[16] Andre Kaup. Object-based texture coding of moving video in MPEG-4. IEEE Trans.on CSVT. 1999.2.vol.9.No.1.
[17] 向友君,郭宝龙.运动估计快速块匹配算法.计算机工程. 2003.Vol.29 13.
[18] 丁贵广,计文平,郭宝龙等. Visual C++ 6.0 数字图像编码. 北京:机械工业出版社. 2004:101～103.
[19] T.Koga,et al. Motion compensated interframe coding for video conferencing. Proc.National Telecommun.Conf. 1981: 5.3.1-5.3.5
[20] S.Kappagantula, K.R.Rao, Motion compensated interframe image prediction, IEEE.Trans. Commun., vol.COM-33:1011-1015. Sept.1985.
[21] J.Jain, A.Jain. Displacement measurement and its application in interframe image coding. IEEE.Transactions on Communications. 1981.12. vol. 29:1799-1806.
[22] R. Li, B. Zeng, and M.L. Liou, A new three-step search algorithm for block motion estimation. IEEE Transactions on Circuits and Systems for Video Technology.1994.8. vol.4, No.4 :438-442
[23] L.M.Po, W.C.Ma, A novel four-step search algorithm for fast block motion estimation, IEEE Transactions on CSVT. 1996.7 vol.6, no.3:313-317
[24] Liu L K, Feig E. A block-based gradient descent search algorithm for block motion estimation in video coding. IEEE Transactions on Circuits Systems Video Technology. 1996.6 (4):.419～422.
[25] J.Y.Tham,S.Ranganath,M.Ranganath. A novel unrestricted center-biased diamond search algorithm for block motion estimation. IEEE Trans. Circuits Syst.Video Technol. 1998.8.vol.8,: 369-377
[26] 白波. 自适应视频运动估计搜索算法及其在视频会议中的应用. [学位论文]. 重庆大学. 2004.6
[27] P.I. Hosur and K.K. Ma, Motion Vector Field Adaptive Fast Motion Estimation, Second International Conference on Information, Communications and Signal Processing (ICICS ’99), Singapore,7-10 Dec.1999
[28] K.K.Ma and P.I.Hosur, Performance Report of Motion Vector Field Adaptive Search Technique(MVFAST), MPEG2000/M5851,March 2000
[29] Ce Zhu, X.Lin, L.P.Chau, and L.M.Po. Enhanced Hexagonal Search for Fast Block Motion Estimation. IEEE Transactions on Circuits and systems for video technology.2004. vol.14.No.10
[30] Lou L J,Zou C R,Gao X Q.etal. A New Prediction Search Algorithm for Block Motion Estimation in Video Coding. IEEE Trans.on Consumer Electronics. 1997.9. Vol.4.: 56-60.
[31] Jou J M,Chen P Y,Sun J M,The Gray Prediction Search Algorithm for Block Motion Estimation. IEEE Trans.On Circuits and System for Video Technology. 1999.3. Vol.9.: 843-848.
[32] Adaptive Irregular Pattern Search With Matching Prejudgment for Fast Block-Matching Motion Estimation IEEE Trans. On Circuits and System for Video Technology., 2005.6.vol.15.No.6
[33] 魏星,蒋建国,齐美彬. 基于选择预测的自适应运动估计算法. 中国图象图形学报. 2005.7.Vol. 10, No. 7.
[34] 李子印,朱善安. 基于运动矢量预测的六边形块运动估计搜索算法. 信号处理. 2006.4.Vol22.No.2
[35] H. Nisar,T.S.Choi. An adaptive block motion estimation algorithm based on spatio-temporal correlation. IEEE.2006.
[36] Ishfaq Ahmad, Weiguo Zheng, Jiancong Luo. A Fast Adaptive Motion Estimation Algorithm. IEEE Trans. On Circuits and System for Video Technology. 2006.3.vol.16, No.3.
[37] Zbigniew Michalewicz, David B.Fogel.曹宏庆,李艳,董红斌. 如何求解问题——现代启发式方法. 中国水利水电出版社. 2002.: 88-93
[38] P.J.M. Van Laarhoven and E.H.L. Aarts, Simulated Annealing:Theory and Applications, Kluwer Academic Publishers, Dordrecht,Holland,1987
[39] 冯玉蓉. 模拟退火算法的研究及其应用. [学位论文]. 昆明理工大学.2005 4-6
[40] Mon-Chuau SHIE, Wen-Hsien FANG. Fast,Robust Block Motion Estimation Using Simulated Annealing. IEICE Trans.Fundamentals.vol.E83-A.NO.1.2000.1. 121-126
[41] Kirkpatrick S, Gelatt C.D, Vecchi M P. Optimization by Simulated Annealing. Science. 1983.220:671-680
[42] 陈华根,吴健生,王家林等.模拟退火算法机理研究.同济大学学报(自然科学版).2004.vol32.6:802-805
[2] ISO/MPEG-1 ISO11172-2. Coding of Moving Picture and Associated Audio for Digital Storage Media at up to about 1.5Mbit/s. 1991
[3] International Telecommunication Union. Video Coding for Low Bit Rate Communication. ITU-T Recommendation H.263. 1995
[4] ISO/IEC JTC1/SC29/WG11, ISO/IEC CD13818.Information Technology MPEG-2 Committee Draft.1993
[5] ISO/IEC JTC1/SC29/WG11 N2687. MPEG-4 Video Verification Model Version 13.0. 1999
[6] ISO/IEC JTC1/SC29/WG11 N2194. MPEG98.MPEG-4 Requirements.1998
[7] Thomas Sikora ,Senior Member. The MPEG-7 Visual Standard for Content Descriotion An Overview. IEEE Trans.Circuits Syst.Video Technol. 2001,11(6)
[8] Olivier Avaro,et al. MPEG7 System. IEEE Trans .Circuits Syst. Video Technol. 2001.11.(6)
[9] lain E.G.Richardson. H.264 and MPEG4 video compression.Video coding for next-generation multimedia. 2003
[10] 赵巍,艾斯卡尔. MPEG4 视频压缩编码技术及应用.信息技术.2005.9
[11] 张益贞,刘滔. Visual C++实现 MPEG/JPEG 编解码技术. 人民邮电出版社. 2002: 173-408.
[12] 王川. MPEG 编码国际标准技术的特点及应用. 大众科技. 2006.No.7
[13] ISO/IEC JTC1/SC29/WG11 N3342. Overview of the mpeg-4 Standard. 2000.3
[14] ISO/IEC JTC1/SC29/WGllN3908. Weiping Li, Jens-Rainer Ohm, Mihaela van der Schaar, Hong Jiang, Shipeng Li. MPEG-4 Video Verification Model version 18.0. January 2001/Pisa
[15] 李强,贺晓华. 数字电视视频压缩标准. 湖南人文科技学院学报. 2006.(6).3
[16] Andre Kaup. Object-based texture coding of moving video in MPEG-4. IEEE Trans.on CSVT. 1999.2.vol.9.No.1.
[17] 向友君,郭宝龙.运动估计快速块匹配算法.计算机工程. 2003.Vol.29 13.
[18] 丁贵广,计文平,郭宝龙等. Visual C++ 6.0 数字图像编码. 北京:机械工业出版社. 2004:101～103.
[19] T.Koga,et al. Motion compensated interframe coding for video conferencing. Proc.National Telecommun.Conf. 1981: 5.3.1-5.3.5
[20] S.Kappagantula, K.R.Rao, Motion compensated interframe image prediction, IEEE.Trans. Commun., vol.COM-33:1011-1015. Sept.1985.
[21] J.Jain, A.Jain. Displacement measurement and its application in interframe image coding. IEEE.Transactions on Communications. 1981.12. vol. 29:1799-1806.
[22] R. Li, B. Zeng, and M.L. Liou, A new three-step search algorithm for block motion estimation. IEEE Transactions on Circuits and Systems for Video Technology.1994.8. vol.4, No.4 :438-442
[23] L.M.Po, W.C.Ma, A novel four-step search algorithm for fast block motion estimation, IEEE Transactions on CSVT. 1996.7 vol.6, no.3:313-317
[24] Liu L K, Feig E. A block-based gradient descent search algorithm for block motion estimation in video coding. IEEE Transactions on Circuits Systems Video Technology. 1996.6 (4):.419～422.
[25] J.Y.Tham,S.Ranganath,M.Ranganath. A novel unrestricted center-biased diamond search algorithm for block motion estimation. IEEE Trans. Circuits Syst.Video Technol. 1998.8.vol.8,: 369-377
[26] 白波. 自适应视频运动估计搜索算法及其在视频会议中的应用. [学位论文]. 重庆大学. 2004.6
[27] P.I. Hosur and K.K. Ma, Motion Vector Field Adaptive Fast Motion Estimation, Second International Conference on Information, Communications and Signal Processing (ICICS ’99), Singapore,7-10 Dec.1999
[28] K.K.Ma and P.I.Hosur, Performance Report of Motion Vector Field Adaptive Search Technique(MVFAST), MPEG2000/M5851,March 2000
[29] Ce Zhu, X.Lin, L.P.Chau, and L.M.Po. Enhanced Hexagonal Search for Fast Block Motion Estimation. IEEE Transactions on Circuits and systems for video technology.2004. vol.14.No.10
[30] Lou L J,Zou C R,Gao X Q.etal. A New Prediction Search Algorithm for Block Motion Estimation in Video Coding. IEEE Trans.on Consumer Electronics. 1997.9. Vol.4.: 56-60.
[31] Jou J M,Chen P Y,Sun J M,The Gray Prediction Search Algorithm for Block Motion Estimation. IEEE Trans.On Circuits and System for Video Technology. 1999.3. Vol.9.: 843-848.
[32] Adaptive Irregular Pattern Search With Matching Prejudgment for Fast Block-Matching Motion Estimation IEEE Trans. On Circuits and System for Video Technology., 2005.6.vol.15.No.6
[33] 魏星,蒋建国,齐美彬. 基于选择预测的自适应运动估计算法. 中国图象图形学报. 2005.7.Vol. 10, No. 7.
[34] 李子印,朱善安. 基于运动矢量预测的六边形块运动估计搜索算法. 信号处理. 2006.4.Vol22.No.2
[35] H. Nisar,T.S.Choi. An adaptive block motion estimation algorithm based on spatio-temporal correlation. IEEE.2006.
[36] Ishfaq Ahmad, Weiguo Zheng, Jiancong Luo. A Fast Adaptive Motion Estimation Algorithm. IEEE Trans. On Circuits and System for Video Technology. 2006.3.vol.16, No.3.
[37] Zbigniew Michalewicz, David B.Fogel.曹宏庆,李艳,董红斌. 如何求解问题——现代启发式方法. 中国水利水电出版社. 2002.: 88-93
[38] P.J.M. Van Laarhoven and E.H.L. Aarts, Simulated Annealing:Theory and Applications, Kluwer Academic Publishers, Dordrecht,Holland,1987
[39] 冯玉蓉. 模拟退火算法的研究及其应用. [学位论文]. 昆明理工大学.2005 4-6
[40] Mon-Chuau SHIE, Wen-Hsien FANG. Fast,Robust Block Motion Estimation Using Simulated Annealing. IEICE Trans.Fundamentals.vol.E83-A.NO.1.2000.1. 121-126
[41] Kirkpatrick S, Gelatt C.D, Vecchi M P. Optimization by Simulated Annealing. Science. 1983.220:671-680
[42] 陈华根,吴健生,王家林等.模拟退火算法机理研究.同济大学学报(自然科学版).2004.vol32.6:802-805