H.264运动估计技术研究与改进
摘要
H.264/AVC视频编码标准是由ITU-T SG16 Q.6视频编码专家组联合ISC/IEC运动图象专家组共同制定的。H.264为了提高压缩率应用了一些计算度很高的算法,其中运动估计是计算度最高的,这个算法通过在参考帧或者参考块中寻找与当前块相似度最高的匹配块来达到减少需要传输的比特数和占用的网络带宽之目的。由于H.264在运动估计中不仅采用了整象素估计还采用了高精度的分数象素估计,同时引入了多参考帧技术----在多个参考帧中寻找最佳运动矢量,导致它在提高匹配精度的同时也大幅增加了编码复杂度。为了降低运动搜索的复杂度,H.264的官方模型采用了基于预测子集的运动估计算法,这些算法比起只专注于搜索模式的快速搜索算法(三步搜索算法,钻石搜索算法,四步搜索算法)大幅度提高了搜索的效率,因为充分利用了图象的空间与时间相关性。
本文首先介绍了H.264视频编码算法采用的关键技术以及一些重要的基于块匹配的运动搜索算法。接着重点介绍了最新JM模型中采用的快速运动搜索算法EPZS,该算法在运动幅度较小并且没有突变运动的视频序列中能达到一个很好的效果,但是当序列有突变或者运动加大的时候它的搜索时间就相对更长。针对这个问题通过对各种运动复杂度的视频序列进行验证,提出了一种能够降低视频序列搜索时间同时保持信噪比在一定波动水平的的改进EPZS算法。
EPZS算法中当预测子集S1中的中值预测矢量不满足搜索终止条件的时候,接着会把另外三个预测子集的预测矢量都与门限值T2进行比较。本文的改进算法在检测完预测子集S1后如果没有终止,只检测子集S2和S3中的预测值,如果低于门限值T2就终止算法,否则才检测子集S4。这种把针对大运动和突变运动的预测子集S4与预测子集S2、S3分别与门限值T2进行比较,减少了运动速度偏小的视频序列的不必要搜索。该算法还对基于搜索窗口的预测子集S4根据时间域和空间域的相关性进行了进一步精选,减少了不必要的搜索点数,同时图象还能保持一个较好的信噪比。
H.264 is a video coding standard jointly developed by ITU-T SG16 Q.6 Video Coding Experts Group and ISO/IEC Moving Picture Experts Group. This coding standard has high coding efficiency by intrucding some new features including motion estimation, which dedicates to reduce the bit rate and the occupation of bindwith by searching the most similar block in the reference frames.The high accuracy fractional-pel motion estimation and the multi-reference frames make the H.264 having extreme coding complexity. In order to reduce the searching complexity, the standard uses some search algorithms based on MV predication subsets, the two algorithms have rapidity improve search efficiency compared to some fast search algorithms which only focus on search mode .
This paper first discusses the basic principles and key technologies of H.264 video coding standard, then in depth analyses the H.264 recommended core algorithm of motion estimation EPZS. The EPZS can achieve a good performance if the video sequence only has low motion and no sudden motion, however when the sequence having charp change and accelerated motion there will be some influence on the performance. This paper does some improve on EPZS to reduce the motion estimation time of various video sequence and maintain the image quality .
EPZS will calculate all the remain three predicted subsets, if the subset S1 does’t satisfy the termination condition, the improved EPZS algorithm of this paper just check the subsets of S2 and S3, only when they all don’t meet the temiantion condition then examines the subset S4. This improvement can reduce the unnecessary calculation for the smooth picture. At last the improved EPZS algorithm also selects the subset S4 member for incressing the chance of searching the optimal MV.
本文首先介绍了H.264视频编码算法采用的关键技术以及一些重要的基于块匹配的运动搜索算法。接着重点介绍了最新JM模型中采用的快速运动搜索算法EPZS,该算法在运动幅度较小并且没有突变运动的视频序列中能达到一个很好的效果,但是当序列有突变或者运动加大的时候它的搜索时间就相对更长。针对这个问题通过对各种运动复杂度的视频序列进行验证,提出了一种能够降低视频序列搜索时间同时保持信噪比在一定波动水平的的改进EPZS算法。
EPZS算法中当预测子集S1中的中值预测矢量不满足搜索终止条件的时候,接着会把另外三个预测子集的预测矢量都与门限值T2进行比较。本文的改进算法在检测完预测子集S1后如果没有终止,只检测子集S2和S3中的预测值,如果低于门限值T2就终止算法,否则才检测子集S4。这种把针对大运动和突变运动的预测子集S4与预测子集S2、S3分别与门限值T2进行比较,减少了运动速度偏小的视频序列的不必要搜索。该算法还对基于搜索窗口的预测子集S4根据时间域和空间域的相关性进行了进一步精选,减少了不必要的搜索点数,同时图象还能保持一个较好的信噪比。
H.264 is a video coding standard jointly developed by ITU-T SG16 Q.6 Video Coding Experts Group and ISO/IEC Moving Picture Experts Group. This coding standard has high coding efficiency by intrucding some new features including motion estimation, which dedicates to reduce the bit rate and the occupation of bindwith by searching the most similar block in the reference frames.The high accuracy fractional-pel motion estimation and the multi-reference frames make the H.264 having extreme coding complexity. In order to reduce the searching complexity, the standard uses some search algorithms based on MV predication subsets, the two algorithms have rapidity improve search efficiency compared to some fast search algorithms which only focus on search mode .
This paper first discusses the basic principles and key technologies of H.264 video coding standard, then in depth analyses the H.264 recommended core algorithm of motion estimation EPZS. The EPZS can achieve a good performance if the video sequence only has low motion and no sudden motion, however when the sequence having charp change and accelerated motion there will be some influence on the performance. This paper does some improve on EPZS to reduce the motion estimation time of various video sequence and maintain the image quality .
EPZS will calculate all the remain three predicted subsets, if the subset S1 does’t satisfy the termination condition, the improved EPZS algorithm of this paper just check the subsets of S2 and S3, only when they all don’t meet the temiantion condition then examines the subset S4. This improvement can reduce the unnecessary calculation for the smooth picture. At last the improved EPZS algorithm also selects the subset S4 member for incressing the chance of searching the optimal MV.
引文
[1]沈兰荪等著。视频编码与低速率传输。北京:电子工业出版社,2001:1~319
[2] S. Yazbeck. The US road to 3G: an overview of telecom regulations, carrier strategies, and the consumer market. 10th International Conference on Telecommunications, 2003, 1: 25~32
[3] Miah, A and Tan, K. An overview of 3G mobile network infrastructure. 2002. SCOReD 2002. Student Conference on research and development, 2002: 16-17: 228~232
[4]王汇源.数字图象通信原理与技术.北京:国防工业出版社,2000:11~65
[5] ITU-T, Recommendation H.261: Video Codec for Audiovisual Services at p×64kbits/s, Mar 1993.
[6] ISO/IEC JTCI/SC29/WG11.“MPEG-1 Committee Draft”, CD11172: Information Technology. Dec,1991
[7] ISO/IEC JTCI/SC29/WG11, ISO/IEC,“MPEG-2 Committee Draft”, CD13818: Information Technology. Dec,1993
[8] ISO/IEC JTCI/SC29/WG11, ISO/IEC, Coding of Audio-Visual Object-Part 2: Visual ,ISL/IEC 14496-2(MPEG-4 Visual Version 1),Apr 1999
[9] ITU-T Rec. H.264/ISO/IEC 11496-10. Advanced Video Coding. Final Committee Draft,Document JVT-G050,2003
[10] ITU-T, Recommendation H.263: Video Codec for Low Bit Rate Communication, ITU-T Recommendation H.263 Draft, July 1995
[11] Iain E.G.Riehardson, H.264 and MPEG-4 Video Compression,John Wiley & Sons Ltd, 2003
[12] F. Fu, X. Lin, L. Xu. Fast intra prediction algorithm in H. 264-AVC. Proceedings of 2004 7th International Conference on Signal Processing, 2004, 2: 1191-1194
[13] B. Meng, O. C. Au, W. Chi-Wah, et.al. Efficient intera-prediction mode selection for 4x4 blocks in H.264. Proceedings of the 2003 International Conference on Multimedia and Expo, 2003, 3: 521-524.
[14]张真,黄登山,汤加跃.视频编码中帧内预测算法研究及性能比较.计算机测最与控制,2007,15(2):228-231
[15] Y. Q. Zhang, S. Zafar. Predictive block-matching motion estimation for tv coding. II.Inter-frame prediction. IEEE Transactions on Broadcasting, 1991,37(3): 102-105
[16]梁亚玲,刘静,杜明辉.H.264中运动估计及其发展趋势.数字电视与数字视频,2005,18(5):40-43
[17] H. Hsieh. A fast recursive algorithm for computing the discrete cosine transform. IEEE Transactions on Acoustics, Speech and Signal Processing, 1987, 35(10): 1455-1461
[18] N. Ahmed, T. Natarajan, K. Rao. Discrete cosine transfom. IEEE Transactions on Computers, 1974, 100(23): 90-93
[19] Iain E G Richardson. H.264/MPEG-4 Part 10 White Paper.http://www.vcodex.com,2002
[20] D. Marpe, H. Schwarz, T. Wiegand. Context-based adaptive binary arithmetic coding in the H. 264/AVC video compression standard. IEEE Transactions on Circuits and Systems for Video Technology, 2003, 13(7): 620-636
[21] A.M.Tekalp. Digital video processing. Englewood Clifs: Printice Hall, 1995
[22]毕厚杰.新一代视频压缩编码标准——H.264/AVC.北京:人民邮电出版社,2005:249
[23] J. Ribas-Corbera, L. Shaw-Min. A frame-layer bit allocation for h.263+. IEEE Transactions on Circuits and Systems for Video Technology, 2000, 10(7): 1154-1158
[24] J. Xue, L. Shen. A bit rate control algorithm used for H.264 video encoder. Journal of Electronics, 2003, 20(6): 456-460
[25] L. Won-Yeol, J. Yeonsik, L. Jae Cheol, et.al. A practical rete control algorithm for VBR MPEG-2 video transmission over ATM networks. IEEE Transactions on Consumer Electronics, 2000, 46(2): 257-264
[26] J. Byun, J. Choi, J. Base, et.al. Fast multi-reference picture motion estimation algorithm using a relation of motion vector with distance of each frame. Dept. of the Electr. & Electron. Eng. Yonsei Univ., Seoul, South Korea
[27] M. Kim, Y. Lee, J. Ra. A fast multi-resolution block matching algorithm for multiple-frame motion estimation. IEICE Transactions on Information and Systems Eseries D, 2005, 88(12): 2819-2827
[28] A. M. Tourapis, O. C. Au, M. L. Liou. Highly efficient predictive zonal algorithms for fast block-matching motion estimation. IEEE Transactions on Circuits and Systems for Video Technology, 2002, 12(10): 934-947
[29] A. Tourapis. Enhanced predictive zonal search for single and multiple frame motion estimation. Proceedings of Visual Communications and Image Processing, 2002: 1069-1079
[30] L. Gwo-Long, C. Mei-Juan, L. Hung-Ju, et.al. Efficient search and mode prediction algorithmsfor motion estimation in H.264/AVC. IEEE International Symposium on Circuits and Systems (ISCAS 2005), 2005, 6: 5481-5484
[31] T. Wiegand, B. Girod. Multi-frame motion-compensated prediction for video transmission. Springer, 2001
[32] T. Koga, A. Hirano, K. Iinuma, et.al. A 1.5 Mb/s interframe codec with motion-compensation. Teleconferencing, 1985: 161
[33] L. Po, W. Ma. A novel four-step search algorithm for fast block motion estimation. IEEE Transactions on Circuits and Systems for Video Technology, 1996, 6(3): 313-317
[34] Z. Shan, M. Kai-Kuang. A new diamond search algorithm for fast block matching motion estimation. Proceedings of 1997 International Conference on Information, Communications and Signal Processing (ICICS 1997), 1997: 292-296
[35] C. Chun-Ho, P. Lai-Man. A Novel Cross-diamond search algorithm for fast block motion estimation. IEEE Transaction on Circuits and Systems for Video Technology, 2002, 12(12): 1168-1177
[36] Z. Ce, L. Xiao, C. Lap-Pui. Hexagon-based search pattern for fast block motion estimation. IEEE Transactions on Circuits and Systems for Video Techonlogy, 2002,12(5): 349-355
[37] P. Hosur, K. Ma. Motion vector field adaptive fast motion estimation. Second International Conference on Information, Communications and Singal Processing (ICICS’99), 1999: 7-10.
[38] A. Tourapis, O. Au, M. Liou. Predictive motion vector field adaptive search technique (pmvfast)-enhancing block based motion estimation. Proceedings of Visual Communication and Image Processing 2001 (VCIP-2001), 2001
[39] Z. Chen, J. Xu, Y. He, et.al. Fast integer-pel and fractional-pel motion estimation for h. 264/avc. Journal of Visual Communication and Image Representation, 2006, 17(2): 264-290
[40] A. Tourapis. Enhanced predictive zonal search for single and multiple frame motion estimation. Proceedings of Visual Communications and Image Processing, 2002: 1069-1079
[41] A. Tourapis, O. Au, M. Liou. Highly efficient predictive zonal algorithms for fast block-matching motion estimation. IEEE Transaction on Circuits and Systems for Video Technology, 2002, 12(10): 934-947
[42] T. Wiegand, G. Sullivan, G. Bjontegaard, et.al. Over view of the H.264/AVC video coding standard. IEEE Transactions on Circuits and Systems for video technology, 2003, 13(7): 560-576
[43] Joint Video Team (JVT) of ISO/IEC MPEG and ITU-T VCEG, JVT-P026.July 2005
[2] S. Yazbeck. The US road to 3G: an overview of telecom regulations, carrier strategies, and the consumer market. 10th International Conference on Telecommunications, 2003, 1: 25~32
[3] Miah, A and Tan, K. An overview of 3G mobile network infrastructure. 2002. SCOReD 2002. Student Conference on research and development, 2002: 16-17: 228~232
[4]王汇源.数字图象通信原理与技术.北京:国防工业出版社,2000:11~65
[5] ITU-T, Recommendation H.261: Video Codec for Audiovisual Services at p×64kbits/s, Mar 1993.
[6] ISO/IEC JTCI/SC29/WG11.“MPEG-1 Committee Draft”, CD11172: Information Technology. Dec,1991
[7] ISO/IEC JTCI/SC29/WG11, ISO/IEC,“MPEG-2 Committee Draft”, CD13818: Information Technology. Dec,1993
[8] ISO/IEC JTCI/SC29/WG11, ISO/IEC, Coding of Audio-Visual Object-Part 2: Visual ,ISL/IEC 14496-2(MPEG-4 Visual Version 1),Apr 1999
[9] ITU-T Rec. H.264/ISO/IEC 11496-10. Advanced Video Coding. Final Committee Draft,Document JVT-G050,2003
[10] ITU-T, Recommendation H.263: Video Codec for Low Bit Rate Communication, ITU-T Recommendation H.263 Draft, July 1995
[11] Iain E.G.Riehardson, H.264 and MPEG-4 Video Compression,John Wiley & Sons Ltd, 2003
[12] F. Fu, X. Lin, L. Xu. Fast intra prediction algorithm in H. 264-AVC. Proceedings of 2004 7th International Conference on Signal Processing, 2004, 2: 1191-1194
[13] B. Meng, O. C. Au, W. Chi-Wah, et.al. Efficient intera-prediction mode selection for 4x4 blocks in H.264. Proceedings of the 2003 International Conference on Multimedia and Expo, 2003, 3: 521-524.
[14]张真,黄登山,汤加跃.视频编码中帧内预测算法研究及性能比较.计算机测最与控制,2007,15(2):228-231
[15] Y. Q. Zhang, S. Zafar. Predictive block-matching motion estimation for tv coding. II.Inter-frame prediction. IEEE Transactions on Broadcasting, 1991,37(3): 102-105
[16]梁亚玲,刘静,杜明辉.H.264中运动估计及其发展趋势.数字电视与数字视频,2005,18(5):40-43
[17] H. Hsieh. A fast recursive algorithm for computing the discrete cosine transform. IEEE Transactions on Acoustics, Speech and Signal Processing, 1987, 35(10): 1455-1461
[18] N. Ahmed, T. Natarajan, K. Rao. Discrete cosine transfom. IEEE Transactions on Computers, 1974, 100(23): 90-93
[19] Iain E G Richardson. H.264/MPEG-4 Part 10 White Paper.http://www.vcodex.com,2002
[20] D. Marpe, H. Schwarz, T. Wiegand. Context-based adaptive binary arithmetic coding in the H. 264/AVC video compression standard. IEEE Transactions on Circuits and Systems for Video Technology, 2003, 13(7): 620-636
[21] A.M.Tekalp. Digital video processing. Englewood Clifs: Printice Hall, 1995
[22]毕厚杰.新一代视频压缩编码标准——H.264/AVC.北京:人民邮电出版社,2005:249
[23] J. Ribas-Corbera, L. Shaw-Min. A frame-layer bit allocation for h.263+. IEEE Transactions on Circuits and Systems for Video Technology, 2000, 10(7): 1154-1158
[24] J. Xue, L. Shen. A bit rate control algorithm used for H.264 video encoder. Journal of Electronics, 2003, 20(6): 456-460
[25] L. Won-Yeol, J. Yeonsik, L. Jae Cheol, et.al. A practical rete control algorithm for VBR MPEG-2 video transmission over ATM networks. IEEE Transactions on Consumer Electronics, 2000, 46(2): 257-264
[26] J. Byun, J. Choi, J. Base, et.al. Fast multi-reference picture motion estimation algorithm using a relation of motion vector with distance of each frame. Dept. of the Electr. & Electron. Eng. Yonsei Univ., Seoul, South Korea
[27] M. Kim, Y. Lee, J. Ra. A fast multi-resolution block matching algorithm for multiple-frame motion estimation. IEICE Transactions on Information and Systems Eseries D, 2005, 88(12): 2819-2827
[28] A. M. Tourapis, O. C. Au, M. L. Liou. Highly efficient predictive zonal algorithms for fast block-matching motion estimation. IEEE Transactions on Circuits and Systems for Video Technology, 2002, 12(10): 934-947
[29] A. Tourapis. Enhanced predictive zonal search for single and multiple frame motion estimation. Proceedings of Visual Communications and Image Processing, 2002: 1069-1079
[30] L. Gwo-Long, C. Mei-Juan, L. Hung-Ju, et.al. Efficient search and mode prediction algorithmsfor motion estimation in H.264/AVC. IEEE International Symposium on Circuits and Systems (ISCAS 2005), 2005, 6: 5481-5484
[31] T. Wiegand, B. Girod. Multi-frame motion-compensated prediction for video transmission. Springer, 2001
[32] T. Koga, A. Hirano, K. Iinuma, et.al. A 1.5 Mb/s interframe codec with motion-compensation. Teleconferencing, 1985: 161
[33] L. Po, W. Ma. A novel four-step search algorithm for fast block motion estimation. IEEE Transactions on Circuits and Systems for Video Technology, 1996, 6(3): 313-317
[34] Z. Shan, M. Kai-Kuang. A new diamond search algorithm for fast block matching motion estimation. Proceedings of 1997 International Conference on Information, Communications and Signal Processing (ICICS 1997), 1997: 292-296
[35] C. Chun-Ho, P. Lai-Man. A Novel Cross-diamond search algorithm for fast block motion estimation. IEEE Transaction on Circuits and Systems for Video Technology, 2002, 12(12): 1168-1177
[36] Z. Ce, L. Xiao, C. Lap-Pui. Hexagon-based search pattern for fast block motion estimation. IEEE Transactions on Circuits and Systems for Video Techonlogy, 2002,12(5): 349-355
[37] P. Hosur, K. Ma. Motion vector field adaptive fast motion estimation. Second International Conference on Information, Communications and Singal Processing (ICICS’99), 1999: 7-10.
[38] A. Tourapis, O. Au, M. Liou. Predictive motion vector field adaptive search technique (pmvfast)-enhancing block based motion estimation. Proceedings of Visual Communication and Image Processing 2001 (VCIP-2001), 2001
[39] Z. Chen, J. Xu, Y. He, et.al. Fast integer-pel and fractional-pel motion estimation for h. 264/avc. Journal of Visual Communication and Image Representation, 2006, 17(2): 264-290
[40] A. Tourapis. Enhanced predictive zonal search for single and multiple frame motion estimation. Proceedings of Visual Communications and Image Processing, 2002: 1069-1079
[41] A. Tourapis, O. Au, M. Liou. Highly efficient predictive zonal algorithms for fast block-matching motion estimation. IEEE Transaction on Circuits and Systems for Video Technology, 2002, 12(10): 934-947
[42] T. Wiegand, G. Sullivan, G. Bjontegaard, et.al. Over view of the H.264/AVC video coding standard. IEEE Transactions on Circuits and Systems for video technology, 2003, 13(7): 560-576
[43] Joint Video Team (JVT) of ISO/IEC MPEG and ITU-T VCEG, JVT-P026.July 2005