Title page for 985202106


[Back to Results | New Search]

Student Number 985202106
Author Yu-Huan Sung(§º¨|¾È)
Author's Email Address No Public.
Statistics This thesis had been viewed 343 times. Download 10 times.
Department Computer Science and Information Engineering
Year 2010
Semester 2
Degree Master
Type of Document Master's Thesis
Language English
Title Fast Mode Decision for H.264/AVC Using Rate-Distortion Clustering and Multi-Phase Classification
Date of Defense 2011-07-21
Page Count 183
Keyword
  • H.264/AVC
  • Mode Decision
  • Video Coding
  • Video Compression
  • Abstract Video coding plays an indispensible role in a wide variety of applications such as TV-broadcast, video conference, monitoring system, filming, video streaming and mobile service. The latest video coding standard, H.264/AVC, adopts several new coding techniques to improve the compression ratio and visual quality. In spite of the better coding efficiency comparing to MPEG-2, H.264/AVC suffers from the extremely high computational burdens in the encoding process induced by those new coding features. Therefore, how to reduce the encoding complexity while keeping nearly the same coding performance is a vital and challenging task. In this paper, a very efficient fast mode decision algorithm using nearest mean method and multi-phase classification scheme is proposed, which reduces encoding time greatly without any noticeable performance degradation.
    Table of Content INTRODUCTION ............................................................................................... 1
    1-1 MOTIVATIONS ............................................................................................................ 1
    1-1.1 Importance of Video Technology ........................................................................... 1
    1-1.2 Needs for Real-Time Video Applications .............................................................. 2
    1-2 KEY NOTES OF CHAPTERS ......................................................................................... 2
    CHAPTER 1 FUNDAMENTALS OF VIDEO CODING ............................... 4
    1-1 HISTORY OF VIDEO CODING...................................................................................... 4
    1-1.1 Draft of Standard .................................................................................................... 4
    1-1.2 Progress of Video Coding ...................................................................................... 5
    1-2 VIDEO COMPRESSION ................................................................................................ 6
    1-2.1 Progressive and Interlacing Displays ..................................................................... 6
    1-2.2 Block Based Coding ............................................................................................... 7
    1-2.3 Perceptual Redundancy and Discrete Cosine Transform ....................................... 7
    1-2.4 Temporal Redundancy and Motion Estimation .................................................... 12
    1-2.5 Spatial Redundancy And Interpolation ................................................................ 15
    1-2.6 Motion Compensation .......................................................................................... 17
    1-2.7 Types of Frame ..................................................................................................... 18
    1-2.8 Slice of Frame ....................................................................................................... 20
    1-2.9 Blocking Artifacts ................................................................................................ 21
    1-3 TYPICAL CODING PROCESS ..................................................................................... 21
    1-3.1 Encoding ............................................................................................................... 21
    1-3.2 Decoding ............................................................................................................... 23
    1-4 H.264/AVC STANDARD ........................................................................................... 23
    1-4.1 Overview .............................................................................................................. 23
    1-4.2 Variable Block-Size .............................................................................................. 24
    1-4.3 Multiple References .............................................................................................. 25
    1-4.4 Quarter-Pel Motion Estimation ............................................................................ 26
    1-4.5 Directional Intra Prediction .................................................................................. 27
    1-4.6 Motion Compensation of Multiple Directions ..................................................... 28
    1-4.7 Mode of Block ...................................................................................................... 28
    1-4.8 DCT-Like 4x4 Integer Transform ........................................................................ 30
    CHAPTER 2 RELATED WORKS AND LITERATURES REVIEW ........ 33
    2-1 OVERVIEW ................................................................................................................ 33
    2-2 SKIP-MODE DETECTION ........................................................................................ 33
    - iii -
    2-2.1 Threshold Method ................................................................................................ 34
    2-2.2 Probabilistic Modeling ......................................................................................... 35
    2-3 INTER/INTRA DETERMINATION ............................................................................... 36
    2-4 MODE PREDICTION .................................................................................................. 36
    2-4.1 Mode Correlation .................................................................................................. 36
    2-4.2 Phase Correlation .................................................................................................. 37
    2-4.3 Other Prediction Methods ..................................................................................... 37
    2-5 MODE CLASSIFICATION ........................................................................................... 37
    2-5.1 Pixel Domain Analysis ......................................................................................... 38
    2-5.2 DCT Coefficients Analysis ................................................................................... 38
    2-5.3 Motion Vector Analysis ....................................................................................... 38
    2-5.4 Machine Learning ................................................................................................. 39
    2-5.5 Fuzzy Classifier .................................................................................................... 40
    CHAPTER 3 PROPOSED FAST MODE DECISION ............................... 41
    3-1 INTRODUCTION ........................................................................................................ 41
    3-2 FEATURE SELECTION ............................................................................................... 42
    3-3 CLASSIFIERS ............................................................................................................. 44
    3-3.1 Nearest Mean Method .......................................................................................... 46
    3-3.2 1-Norm Distance .................................................................................................. 46
    3-4 MULTI-PHASE CLASSIFICATION .............................................................................. 47
    3-4.1 Flow of Classification ........................................................................................... 48
    3-5 DYNAMICALLY ADJUSTMENT .................................................................................. 49
    3-5.1 Curve-Fitting for Moving Means ......................................................................... 51
    3-5.2 Adjustments of Means and Variances .................................................................. 52
    3-6 PERFORMANCE CONTROL ....................................................................................... 53
    3-6.1 Early Termination ................................................................................................. 53
    3-6.2 Error Propagation and Performance Control ........................................................ 54
    3-6.3 Slack Coefficients ................................................................................................. 55
    3-7 OVERALL FAST MODE DECISION ALGORITHM ...................................................... 55
    CHAPTER 4 EXPERIMENTAL RESULTS ................................................. 58
    4-1 ENVIRONMENT OF EXPERIMENTS ........................................................................... 58
    4-1.1 Training of Category Means ................................................................................. 58
    4-1.2 Testing Conditions ................................................................................................ 59
    4-2 PERFORMANCE EVALUATIONS ................................................................................ 59
    CHAPTER 5 CONCLUSION AND REMARKS .......................................... 63
    REFERENCES .................................................................................................. 64
    Reference [1] ITU-T Rec. H.264/ISO/IEC 14496-10 AVC. Joint Video Team (JVT) of ISO MPEG and ITU-T VCEG, JVT-G050, 2003.
    [2] T. Wiegand, G. J. Sullivan, G. Bjontegaard, and A. Luthra, "Overview of the H.264/AVC video coding standard, " IEEE Trans. Circuits Syst. Video Technol., vol. 13, no. 7, pp. 560 - 576, 2003.
    [3] 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¡V603, July 2003
    [4] 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¡V636, July 2003
    [5] C. S. Tseng, H. M. Wang, and J. F. Yang, ¡§Enhanced intra-4x4 mode decision for H.264/AVC coders,¡¨ IEEE Trans. Circuits Syst. Video Technol., vol. 16, no. 8, pp. 1027¡V1032, Aug. 2006.
    [6] J. C. Wang, J. F. Wang, J. F. Yang, and J. T. Chen, ¡§A fast mode decision algorithm and its VLSI design for H.264/AVC intra-prediction,¡¨ IEEE Trans. Circuits Syst. Video Technol., vol. 17, no. 10, pp.1414¡V1422, Oct. 2007.
    [7] A. C. Tsai, A. Paul, J. C. Wang, and J. F. Wang, ¡§Intensity Graditent Technique for Efficient Intra-Prediction in H.264/AVC,¡¨ IEEE Trans. Circuits Syst. Video Technol., vol. 18, no. 5, pp. 694¡V698, May 2008.
    [8] Y. H. Huang, T. S. Ou, H. Chen, ¡§Fast decision of block size, prediction mode, and intra block for H.264 intra prediction,¡¨ IEEE Trans. Circuits. Syst. Video Technol., vol. 20 no. 8, pp. 1122¡V1132, Aug 2010.
    [9] M. Paul, M. R. Frater, and J. F. Arnold, ¡§An efficient mode selection prior to the actual encoding for H.264/AVC encoder,¡¨ IEEE Trans. Multimedia, vol. 11, no. 4, pp. 581¡V588, Jun. 2009.
    [10] L. Yang, K. Yu, J. Li, and S. Li, ¡§An effective variable block-size early termination algorithm for H.264 video coding,¡¨ IEEE Trans. Circuits Syst. Video Technol., vol. 15, no. 6, pp. 784¡V788, Jun. 2005.
    [11] M. G. Sarwer, and Q.M. Jonathan Wu ¡§Adaptive Variable Block-Size Early motion estimation termination algorithm for H.264/AVC Video Coding Standard.¡¨ IEEE Trans. Circuits Syst. Video Technol., vol. 19, no. 8, pp. 1196-1201, Aug 2009.
    [12] C. Kannangara et al., ¡§Low-complexity skip prediction for H.264 through Lagrangian cost estimation,¡¨ IEEE Trans. Circuits Syst. Video Technol., vol. 16, no. 2, pp. 202¡V208, Feb. 2006.
    - 65 -
    [13] Y.-C. Lin, T. Fink, and E. Beller, ¡§Fast mode decision for H.264 based on rate-distortion cost estimation,¡¨ in Proc. ICASSP2007, Honolulu, Hawaii, pp. 1137¡V1140, Apr. 15-30 2007.
    [14] Y. Zhao, M. Bystrom, and I. E. G. Richardson, ¡§A MAP framework for efficient skip/code mode decision in H.264,¡¨ in Proc. ICIP2006, Atlanta, GA, Oct. 8¡V11, 2006.
    [15] I. Choi, J. Lee, and B. Jeon, ¡§Fast coding mode selection with rate-distortion optimization for MPEG-4 part-10 AVC/H.264,¡¨ IEEE Trans. Circuits Syst. Video Technol., vol. 16, no. 12, pp. 1557¡V1561, Dec. 2006.
    [16] C. Kim and C. C. Jay Kuo, ¡§Feature-based intra-/inter coding mode selection for H.264/AVC,¡¨ IEEE Trans. Circuits and Syst. Video Technol., vol. 17, no. 4, pp. 441¡V453, Apr. 2007.
    [17] B. G. Kim, ¡§Novel inter-mode decision algorithm based on macroblock (MB) tracking for the P-slice in H.264/AVC video coding,¡¨ IEEE Trans. Circuits Syst. Video Technol., vol. 18, no. 2, pp. 273¡V279, Feb. 2008.
    [18] Y. H. Kim and B. G. Kim, ¡§Fast block mode decision algorithm in H.264/AVC video coding,¡¨ Journal of Visual Communication and Image Representation, vol.19, no. 3, pp.175-183, Apr. 2008.
    [19] S. H. Ri, Y. Vatis, and J. Ostermann, ¡§Fast inter-mode decision in an H.264/AVC encoder using mode and lagrangian cost correlation,¡¨ IEEE Trans. Circuits Syst. Video Technol., vol. 19, no. 2, pp. 302¡V306, Feb. 2009.
    [20] M. Paul, W. Lin, C. T. Lau, and B. Lee, ¡§Direct inter-mode selection for H.264 video coding using phase correlation,¡¨ IEEE Trans. Image Processing, vol. 20, no. 2, pp. 461 - 473, Feb. 2011.
    [21] J. R. Ding, ¡§Class-based Search Algorithm for Inter Mode Prediction of H.264/AVC,¡¨ IWWSIP2009, Chalkida, Greece, pp. 1137¡V1140, 18 - 20 Jun. 2009.
    [22] B. Zhan, B. Hou, and R. Sotudeh, "Fast mode selection to reduce the encoding complexity of H.264/AVC," ISCAS2008, Seattle, WA, USA, pp. 3570-3573, 18 ¡V 20 May 2008.
    [23] W. P. Ma, S. Y. Yang, L. Gao, and C. K. Pei, "An Efficient Fast Mode Decision Algorithm Based on Motion Cost for H.264 Inter Prediction," IITAW2008, New York, New York, USA, pp. 550-553, Jun. 28 ¡V Jul. 3, 2009.
    [24] D. Wu, F. Pan, K. P. Lim, and S. Wu et al., ¡§Fast intermode decision in H.264/AVC video coding,¡¨ IEEE Trans. Circuits Syst. Video Technol.,vol.15,no.7,pp. 953¡V958, Jul. 2005.
    [25] Y. Huang, Q. Liu, and T. Ikenaga, ¡§Macroblock feature and motion involved multi-stage fast inter mode decision algorithm in h.264/avc video coding,¡¨ IEICE Trans. Fundamentals, pp. 1041¡V1044, Nov. 2009.
    [26] S. Su, Q. Liu, and Y. Su, ¡§An inter block mode decision method based on gradient and
    - 66 -
    RDO,¡¨ ISECS2009, Sanya, China, pp. 23¡V25, 8-9 Aug. 2009.
    [27] S. H. Chen, H. M. Chen and M. C. Shie, et al., ¡§Adaptive fast block mode decision algorithm for H.264/AVC,¡¨ ICIEA2010, Taichung, Taiwan, pp. 2002¡V2007, Jun. 2010.
    [28] H. Wang, S. Kwong, and C.-W. Kok, ¡§An efficient mode decision algorithm for H.264/AVC encoding optimization,¡¨ IEEE Trans. Multimedia, vol. 9, no. 4, pp. 882¡V888, Jun. 2007.
    [29] Y. M. Lee and Y. Lin, ¡§Zero-block Mode Decision Algorithm for H.264/AVC,¡¨ IEEE Trans. Image Processing, vol. 18, no. 3, pp. 524-533, Mar. 2009.
    [30] A. C. W. Yu, G. R. Martin, and H. Park, ¡§Fast inter-mode selection in the H.264/AVC standard using a hierarchical decision process,¡¨ IEEE Trans. Circuits Syst. Video Technol., vol. 18, no. 2, pp. 186¡V195, Feb. 2008.
    [31] G. Lu, L. Chen, "Fast mode decision for H.264 base on DC coefficient," ICIT2010, Las Vegas, Nevada, USA, pp. 382-386, Apr. 2010.
    [32] T.-Y. Kuo and C.-H. Chan, ¡§Fast variable block size motion estimation for H.264 using likelihood and correlation of motion field,¡¨ IEEE Trans. Circuit Syst. Video Technol., vol. 16, no. 10, pp. 1185¡V95, Oct. 2006.
    [33] L. Shen, Z. Liu, Z. Zhang, and X. Shi, ¡§Fast inter mode decision using spatial property of motion field,¡¨ IEEE Trans. Multimedia, vol. 10, no. 10, pp. 1208¡V1214, Oct. 2008
    [34] H. Zeng, C. Cai, and K.-K. Ma, ¡§Fast mode decision for H.264/AVC based on macroblock motion activity,¡¨ IEEE Trans. Circuits Syst. Video Technol., vol. 19, no. 4, pp. 491¡V499, Apr. 2009
    [35] Z. Liu, L. Shen, and Z. Zhang, ¡§An efficient intermode decision algorithm based on motion homogeneity for H.264/AVC,¡¨ IEEE Trans. Circuits Syst. Video Technol., vol. 19, no. 1, pp. 128¡V132, Jan. 2009.
    [36] T. Zhao, H. Wang, S. Kwong, C.-C. Jay Kuo, ¡§Fast mode decision based on mode adaptation,¡¨ IEEE Trans. Circuits and Syst. Video Technol., vol. 20, no. 5, pp. 697¡V705, May. 2010.
    [37] W. Geng and W. Lenan, ¡§Low complexity mode decision for H.264 based on macroblock motion classification,¡¨ ISISE2009, Shanghai, China, pp. 227¡V230, 26-28 Dec. 2009.
    [38] M. Yang and W. Wang, ¡§Fast macroblock mode selection based on motion content classification in H.264/AVC,¡¨ in Proc. IEEE Int. Conf. Image Process., vol. 2, pp. 24¡V27, Oct. 2004.
    [39] C. H. Lampert, ¡§Machine learning for video compression: macroblock mode decision,¡¨ ICPR2006, Hong Kong, China, vol. 1, pp. 936¡V940, Aug. 2006.
    [40] P. Carrillo, ¡§ Low complexity H.264 video encoder design using machine learning techniques,¡¨ MS Thesis, Department of Electrical Engineering, Florida Atlantic University, Boca Raton, FL, USA, Nov. 2008.
    - 67 -
    [41] W. Ma, S. Yang and L. Gao et al., ¡§ Fast mode selection scheme for h.264/AVC inter prediction based on statistical learning method,¡¨ ICME2009, New York, New York, USA, pp. 17-20 ,Jun. 28-Jul. 3 2008.
    [42] A. Jagmohan and K. Ratakonda, ¡§Time-efficient learning theoretic algorithms for h.264 mode selection,¡¨ ICIP2004, Singapore, vol. 2 pp. 749¡V752, Oct. 2004.
    [43] Y. Vatis, L. Lu, and A. Jagmohan, ¡§Inter mode selection for H.264/AVC using time-efficient learning-theoretic algorithms.¡¨ ICIP2009, Cairo, Egypt, pp. 3413-3416, Nov. 2009.
    [44] J. Kim, M. Kim, S. Hahm, I. Cho, C. Park, ¡§Block-mode classification using SVMs for early termination of block mode decision in H.264|MPEG-4 Part 10 AVC,¡¨ ICAPR2009, Kolkata, Feb. 2009.
    [45] M. Yang and B. Bourbakis, ¡§H.264/AVC intra-only coding (iAVC) and neural network based fast prediction mode decision,¡¨ ICTAI2010, Arrass, France, pp. 57-60, Oct. 2010.
    [46] P. J. Lee, H. K. Chang, S. H. Huang, W. J. Wang, ¡§Coding mode determination by using fuzzy logic in H.264 motion estimation,¡¨ NAFIPS2009, Cincinnati, Ohio, USA, Jun. 2009.
    [47] Voronoi diagram from Wikipedia, [Online]. Available: http://en.wikipedia.org/wiki/Voronoi_diagram.
    [48] G. Bjontegaard, "Calculation of Average PSNR Differences Between RD Curves," Doc. VCEG-M33, Apr. 2011.
    [49] H.264/AVC Reference Software JM17.0, [Online]. Available: http://iphome.hhi.de/suehring/tml/download/old_jm/jm17.0.zip.
    [50] S. Haykin, Neural Networks and Learning Machines. Englewood Cliffs, NJ: Prentice-Hall, 2009.
    [51] J. Kennedy and R. Eberhart, ¡§Particle swarm optimization.¡¨ Proc. IEEE International Conf. on Neural Networks (Perth, Australia), IEEE Service Center, Piscataway, NJ, 1995.
    Advisor
  • Jia-Ching Wang(¤ý®a¼y)
  • Files
  • 985202106.pdf
  • disapprove authorization
    Date of Submission 2011-08-21

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have dissertation-related questions, please contact with the NCU library extension service section.
    Our service phone is (03)422-7151 Ext. 57407,E-mail is also welcomed.