臺灣博碩士論文加值系統

H.264為最新的國際視訊壓縮標準，相較於先前的標準 (例如MPEG-2、MPEG-4和H.263) ，它增添許多先進技術以達到更高的進編碼效能，這些技術包括多重方塊大小移動估測、多重參考畫面、位元率-失真最佳化之模式選擇…等。雖然壓縮效率提昇不少，編碼複雜度(運算量)卻大幅增加。
本論文以H.264最佳化為目標，針對移動估測和模式選擇兩項關鍵模組，深入研究。在移動估測方面，研究可調變式搜尋策略 (包括動態移動向量預估器、提前終止，與動態搜尋樣式) 與動態多重參考畫面選擇技術，將編碼速度增為原本參考軟體 (JM 8.5) 的六倍左右。在模式選擇方面，利用方塊模式在空間與時間上的相關性，發展快速模式選擇演算法，將編碼速度提升約兩倍左右。整合這兩種快速演算法於編碼器中，總編碼速度增加約十二倍，而編碼效能僅受非常輕微影響。

H.264/AVC achieves higher compression efficiency than previous video coding standards such as MPEG-4 and H.263. However, this performance gain comes at the cost of an increased computational complexity due in part to the use of variable block-size motion estimation, multiple reference frames, and rate-distortion mode decision.
This thesis focuses on improving the computational efficiency of two core modules of H.264: motion estimation and mode decision. For motion estimation, we develop a fast algorithm with adaptive search strategy and flexible multi-frame search scheme. Compared with the H.264 reference software JM 8.5, this algorithm achieves, on the average, a 600% reduction of encoding time. For mode decision, we exploit the correlation between neighboring image blocks to predict the best possible mode. Compared with the reference software, this method achieves about 204% reduction of encoding time with negligible PSNR drop and bit rate increase. Integrating these two fast algorithms in the H.264 reference software, this combined method, on the average, is about 12.1 times faster in the total encoding time, at the cost of a slight PSNR drop.

Abstract… iii
Chapter 1 Introduction 1
1.1 Video Coding Standards 1
1.2 H.264 Standard Overview 2
1.3 H.264 Profiles and Levels 4
1.4 Thesis Organization 6
Chapter 2 Overview of the H.264 Video Coding Standard 7
2.1 Temporal Prediction 7
2.1.1 Variable Block-Size Motion Compensation 7
2.1.2 Multiple Reference Frames 9
2.1.3 Quarter-Pixel-Accurate Motion Compensation 11
2.1.4 Motion Vector Prediction 13
2.2 Intra Prediction 14
2.3 Entropy Coding 16
2.3.1 Exp-Golomb Code 17
2.3.2 Context-Based Adaptive Variable Length Coding 18
2.4 Lagrangian Rate-Distortion Optimization 21
2.5 Analysis of Computational Complexity 23
Chapter 3 Review of Previous Work 25
3.1 Fast Mode Decision Algorithm 25
3.1.1 Fast Inter Mode Decision [30] 25
3.1.2 Fast Mode Decision for H.264 [29] 27
3.2 Fast Motion Estimation Algorithm 27
3.2.1 Unequal-Arm Adaptive Rood Pattern Search [21] 28
3.2.2 Hybrid Unsymmetrical-Cross Multi-Hexagon- Grid Search (UMHexagonS) Algorithm [26] 31
Chapter 4 Proposed Fast Multi-Frame Motion Estimation and Mode Decision for H.264 Encoders 35
4.1 Proposed Fast Mode Decision Algorithm 35
4.1.1 Analysis 35
4.1.2 Algorithm Description 42
4.2 Proposed Fast Multi-Frame Motion Estimation Algorithm 46
4.2.1 Adaptive Search Strategy 46
4.2.2 Flexible Multi-Frame Search Scheme 57
4.3 Architecture for Combined Algorithm 59
Chapter 5 Simulation Results 61
5.1 Proposed Fast Mode Decision Algorithm 62
5.2 Proposed Fast Motion Estimation Algorithm 63
5.2.1 CIF Resolution 64
5.2.2 D1 Resolution 70
5.3 Combined Algorithm 71
Chapter 6 Conclusion 75
Bibliography 77

[1]“Draft ITU-T recommendation and final draft international standard of joint video specification (ITU-T Rec. H.264/ISO/IEC 14 496-10 AVC),” in Joint Video Team (JVT) of ISO/IEC MPEG and ITU-T VCEG, JVT-G050, 2003.
[2]“Coding of moving pictures and associated audio for digital storage media up to about 1.5 Mbit/s,” ISO/IEC JTC 1/SC29, ISO/IEC 11172-2 (MPEG-1), 1994.
[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]T. Wiegand, G. J. Sullivan, G. Bjontegaard, and A. Luthra, “Overview of H.264 video coding standartd,” IEEE Trans. Circuits Syst. Video Technol., vol. 13, no. 7, pp. 560-576, Jul. 2003.
[5]T. Wedi, “Motion compensation in H.264/AVC,” IEEE Trans. Circuits Syst. Video Technol., vol. 13, pp. 577–586, Jul. 2003.
[6]T. Wiegand, X. Zhang, and B. Girod, “Long-term memory motion-compensated prediction,” IEEE Trans. Circuits Syst. Video Technol., vol. 9, pp. 70–84, Feb. 1999.
[7]M. Flierl and B. Girod, “Generalized B pictures and the draft JVT/H.264 video compression standard,” IEEE Trans. Circuits Syst. Video Technol., vol. 13, pp. 587–597, Jul. 2003.
[8]T. Wiegand, H. Schwarz, A. Joch, F. Kossentini, and G. J. Sullivan,“Rate-constrained coder control and comparison of video coding standards,” IEEE Trans. Circuits Syst. Video Technol., vol. 13, pp. 688–703, Jul. 2003.
[9]S. Wenger, “H.264/AVC over IP,” IEEE Trans. Circuits Syst. Video Technol., vol. 13, pp. 645–656, Jul. 2003.
[10]M. Karczewicz and R. Kurceren, “The SP and SI frames design for H.264/AVC,” IEEE Trans. Circuits Syst. Video Technol., vol. 13, pp. 637–644, Jul. 2003.
[11]D. Marpe, H. Schwarz, and T. Wiegand, “Context-adaptive binary arithmetic coding in the H.264/AVC video compression standard,” IEEE Trans. Circuits Syst. Video Technol., vol. 13, pp. 620–636, Jul. 2003.
[12]H. Malvar, A. Hallapuro, M. Karczewicz, and L. Kerofsky, “Low-Complexity transform and quantization in H.264/AVC,” IEEE Trans. Circuits Syst. Video Technol., vol. 13, pp. 598–603, Jul. 2003.
[13]P. List, A. Joch, J. Lainema, G. Bjontegaard, and M. Karczewicz, “Adaptive deblocking filter,” IEEE Trans. Circuits Syst. Video Technol., vol. 13, pp. 614–619, Jul. 2003.
[14]J. Ostermann, J. Bormans, P. List, D. Marpe, M. Narroschke, F. Pereira, T. Stockhammer, and T. Wedi, “Video coding with H.264/AVC: tools, performance, and complexity,” IEEE Circuits and Systems Magazine., vol. 4, no. 1, pp. 7-28, First Quarter 2004.
[15]G. J. Sullivan and T. Wiegand, “Rate-distortion optimization for video compression,” IEEE Signal Processing Magazine, pp. 74-90, Nov. 1998.
[16]A. Joch, F. Kossentini, H. Schwarz, T. Wiegand, and G. Sullivan, “Performance comparison of video coding standards using Lagrangian coder control,” in Proc. IEEE Int. Conf. on Image Processing, pp. 501–504, Sept. 2002.
[17]S. Zhu and K. K. Ma, “A new diamond search algorithm for fast block-matching motion estimation,” IEEE Trans. Image Processing, vol. 9, pp. 287-290, Feb. 2000.
[18]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, pp. 349-355, May 2002.
[19]P. I. Hosur and K. K. Ma, “Motion vector field adaptive fast motion estimation,” in Proc. 2nd Int. Conf. Information, Communications and Signal Processing, Dec. 1999.
[20]H.-Y, C. Tourapis, A. M. Tourapis, and P. Topiwala, “Fast motion estimation within the JVT codec,” JVT-E023.doc, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, 5th meeting, Oct. 2002.
[21]K. K. Ma and G. Qiu, “Unequal-arm adaptive rood pattern search for fast block-matching motion estimation in the JVT/H.26L,” in Proc. IEEE Int. Conf. on Image Processing, Sept. 2003.
[22]A. M. Tourapis, O. C. Au, and M. L. Liou, “Predictive motion vector field adaptive search technique (PMVFAST)- enhancing block based motion estimation,” in Proc. Visual Communications and Image Processing, pp. 883-892, Jan. 2001.
[23]A. M. Tourapis, O. C. Au, and M. L. Liou, “New results on zonal based motion estimation algorithms- advanced predictive diamond zonal search,” in Proc. IEEE Int. Symposium on Circuits and Systems, vol.5, pp.183-186, May 2001.
[24]A. M. Tourapis, O. C. Au, and M. L. Liou, “Highly efficient predictive zonal algorithms for fast block-matching motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 12, pp. 934–947, Oct. 2002.
[25]Z. Chen, P. Zhou, and Y. He, “Fast integer pel and fractional pel motion estimation for JVT,” JVT-F017r1.doc, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, 6th meeting, Dec. 2002.
[26]Z. Chen, P. Zhou, and Y. He, “Fast motion estimation for JVT,” JVT-G016.doc, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, 7th Meeting, Mar. 2003.
[27]Y.-W. Huang, et al., “Analysis and reduction of reference frames for motion estimation in MPEG-4 AVC/JVT/H.264,” in Proc. IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, Apr. 2003.
[28]I-M. Pao and M.-T. Sun, “Modeling DCT coefficients for fast video encoding,” IEEE Trans. Circuits Syst. Video Technol., vol. 9, no. 4, pp. 608-616, Jun. 1999.
[29]P. Yin, H.-Y. Tourapis, A. M. Tourapis, and J. Boyce, “Fast mode decision and motion estimation for H.264,” in Proc. IEEE Int. Conf. on Image Processing, vol. III, pp. 853-856, Sept. 2003.
[30]D. Wu, S. Wu, K. P. Lim, F. Pan, and X. Lin, “Block inter mode decision for fast encoding of H.264,” in Proc. IEEE Int. Conf. on Speech, Acoustics, and Signal Processing, vol. 3, pp. 181-184, May 2004.
[31]F. Pan, X. Lin, S. Rahardja, K. P. Lim, and Z. G. Li, “A directional field based fast intra mode decision algorithm,” in Proc. IEEE Int. Conf. on Multimedia and Expo 2004, Jun. 2004.
[32]C. Blanch and K. Denolf, “Memory complexity analysis of the AVC codec JM 1.7,” ISO/IEC JTC1/WG11 MPEG02/M8378 Fairfax, May 2002.
[33]W. I. Choi, J. Lee, S. Yang, and B. Jeon, “Fast motion estimation and mode decision with variable motion block sizes,” in Proc. SPIE Visual Communications and Image Processing, vol. 5150, pp. 1561-1572, 2003.
[34]B. Meng and O. C. Au, “Fast intra-prediction mode selection for 4x4 blocks in H.264,” in Proc. IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, vol. 3, pp. 389-392, Apr. 2003.
[35]A. Ahmad, N. Khan, S. Masud, and M. A. Maud, “Selection of variable block sizes in H.264,” Proc. IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, vol. 3, pp. 173-176, May 2004.
[36]D. S. Turaga and T. Chen, “Estimation and mode decision for spatially correlated motion sequences,” in Proc. IEEE Trans. Circuits Syst. Video Technol., vol. 11, no. 10, pp. 1098-1107, Oct. 2001.
[37]A. C. Yu, “Efficient block-size selection algorithm for inter-frame coding in H.264/MPEG-4 AVC,” in Proc. IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, vol. 3, pp. 169-172, May 2004.
[38]L. P. Kondi, “A rate-distortion optimal hybrid scalable/multiple-distortion video codec,” in Proc. IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, vol. 3, pp. 269-272, May 2004.
[39]X. Li, J. R. Jackson, A. K. Katsaggelos, and R. M. Mersereau, “An adaptive coding scheme using affine motion model for MPEG P-VOP,” in Proc. IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, vol. 3, pp. 717-720, May 2004.
[40]Y. J. Liang and K. El-Maleh, “Low-complexity intra/inter mode-decision for H.264/AVC video coder,” in Proc. IEEE Int. Symposium on Intelligent Multimedia, Video and Speech Processing, pp 53-56, Oct. 2004.
[41]J. Chen, Y. Qu, and Y. He, “A fast mode decision algorithm in H.264,” Picture Coding Symposium, Dec. 2004.
[42]Y. Su and M.-T. Sun, “Fast multiple reference frame motion estimation for H.264,” in Proc. IEEE Int. Conf. on Multimedia and Expo 2004, vol. 1, pp. 695-698, Jun. 2004.
[43]C.-Y. Chang, C.-H. Pan, and H. H. Chen, “Fast mode decision for P-frames in H.264,” Picture Coding Symposium, Dec. 2004.
[44]S.-F. Lin, M.-T. Lu, C.-H. Pan, and H. H. Chen, “Fast multi-frame motion estimation for H.264 and its applications to complexity-aware streaming,” in Proc. IEEE Int. Symposium on Circuits and System, pp. 1505-1508, May 2005.
[45]S.-F. Lin, C.-Y. Chang, C.-C. Su, Y.-L. Lin, C.-H. Pan, and H. H. Chen, “Fast multi-frame motion estimation and mode decision for H.264 encoders,” in Proc. Int. Conf. on Wireless Networks, Communications, and Mobile Computing, Maui, Hawaii, Jun. 2005.
[46]http://bs.hhi.de/~suehring/tml/download/, JVT reference software.
[47]G. Bjontegaard, "Calculation of average PSNR differences between RD-curves," Doc. VCEG-M33, Apr. 2001.
[48]G. Sullivan, "Recommended simulation common conditions for H.26L coding efficiency experiments on low-resolution progressive-scan source material", Doc. VCEG-N81, Sep. 2001.