H.264/AVC視頻編碼標準比以往的標準，如MPEG-2, MPEG-4, 以及H.263，編碼效率有顯著的提高。為增進編碼效率，H.264/AVC編碼器在畫面內編碼上運用了多種的預測模式以採用及率失真優化(RDO)來決定最佳的模式。因為編碼器要運算所有可能的模式，運算的複雜度也隨之劇烈地增加。
本研究針對在H.264/AVC中的畫面內編碼減少運算複雜度，提出階層式高效率畫面內編碼演算法。該演算法共有四個主要部分，即1.快速的畫面內過濾決策;2.基於量化的區塊大小選擇決策;3.基於方向的預測模式決策;與4.快速的畫面內部分過濾決策。
本研究的實驗結果顯示階層式高效率畫面內編碼演算法，其低解析的視訊編碼中可達到平均85%以上的時間節省，在高解析的視訊編碼中可達到平均90%以上的時間節省，同時在品質下降方面是可被忽略的，在編碼長度的上昇是非常微小的。

The H.264/AVC video coding standard can achieve higher coding efficiency than any other previous coding standards, such as MPEG-2, MPEG-4, and H.263. In order to improve the coding efficiency, the H.264/AVC encoder employs various prediction modes in the intra coding and adopts the rate-distortion optimization (RDO) method for selection of an optimum mode. Since the encoder computes the rate-distortion (RD) costs of all possible coding modes to decide the optimum mode, the computational complexity is dramatically increased.
In this study, an efficient hierarchical approach which consists of the four algorithms: 1) fast intra skip decision; 2) quant-based block size selection decision; 3) direction-based prediction mode decision; and 4) fast partial intra skip decision for H.264/AVC intra encoding is proposed to reduce the computational complexity. 
Our experimental results have shown that the proposed algorithms outperform the previous methods. Our overall algorithm can significantly reduce above 85% encoding time for low-resolution video sequences on average, and reduce above 90% encoding time for high-resolution video sequences on average, while the PSNR degradation is negligible and the bit rate increment is minimal.

Contents
Chapter 1.	Introduction	1
1.1.	H.264/AVC Overview	1
1.2.	H.264/AVC Intra Prediction Overview	4
1.3.	H.264/AVC compliant encoder	8
1.4.	Organization of Dissertation	10
Chapter 2.	Related Works	11
2.1.	Related Works on Intra Skip Decision	11
2.2.	Related Works on Block Size Selection Decision	14
2.3.	Related Works on Fast Prediction Mode Decision	15
Chapter 3.	Pre-Experimental Analysis	19
3.1.	Intra Skip Decision	19
3.2.	Block Size Selection Decision	32
3.3.	Prediction Mode Decision	34
3.4.	Partial Intra Skip Decision	39
Chapter 4.	The Proposed Algorithms	42
4.1.	Fast Intra Skip Decision	42
4.2.	Quant-based block size selection decision	44
4.3.	Direction-based prediction mode decision	55
4.4.	Fast Partial Intra Skip Decision	58
Chapter 5.	Experimental Results	60
5.1.	Fast Intra Skip Decision	60
5.2.	Quant-based Block Size Selection Decision and Direction-based Prediction Mode Decision	67
5.3.	Fast Partial Intra Skip Decision and Overall Algorithm	72
Chapter 6.	Conclusion and Future Work	78
Bibliography	80
Publication List	88

List of Figures
Fig. 1-1.　H.264 Encoder Block Diagram.	3
Fig. 1-2.　I4MB prediction block.	7
Fig. 1-3.　I16MB prediction block.	7
Fig. 1-4.　H.264 encoder flowchart.	9
Fig. 1-5.　 Mode decision hierarchy of an H.264 compliant encoder.	10
Fig. 3-1.　The percentage of the intra MB occupied in P-slice.	23
Fig. 3-2.　CIF format Foreman test sequence. (a) the 89th frame, (b) the 90th frame.	29
Fig. 3-3.　Integer 8 × 8 DCT.	33
Fig. 3-4.　Sum up the absolute quantization AC coefficients.	34
Fig. 3-5.　Calculation of variance for (a) vertical, (b) horizontal, (c) down-right, and (d) down-left modes.	36
Fig. 3-6.　Candidate modes selection.	37
Fig. 3-7.　Partial intra skip decision.	40
Fig. 4-1.　Flowchart of the proposed algorithm.	44
Fig. 4-2.　H.264 compliant intra encoder flowchart.	45
Fig. 4-3.　An ideal distribution of QuantACsum for I4MB, I8MB, and I16MB.	45
Fig. 4-4.　Distribution of QuantACsum for I4MB, I8MB, and I16MB (unbalanced error).	48
Fig. 4-5.　Distribution of QuantACsum for I4MB, I8MB, and I16MB (I8MB curve bias error).	51
Fig. 4-6.　Flowchart of the proposed algorithm.	59
Fig. 5-1.　RD curves of Mobile.	75
Fig. 5-2.　RD curves of Shields.	76

List of Tables
Table 3-1.　Video properties.	20
Table 3-2.　Skipping all intra MBs in the inter frame.	24
Table 3-3.　The probability of the hit rate and skip rate, and RD performance using adaptive thresholds.	28
Table 3-4.　The proportion of the corresponding MB of the proceeding frame is the resulting optimal intra mode.	30
Table 3-5.　The proportion of the upper or left MB of the current frame is the resulting optimal intra mode.	30
Table 3-6.　The Probability of the hit rate and skip rate, and RD performance when applying an additional rule.	31
Table 3-7.　The probability of the hit rate and skip rate, and RD performance using adaptive thresholds.	40
Table 3-8.　The Probability of the hit rate and skip rate, and RD performance when applying an additional rule.	41
Table 4-1.　Hit rate for block size selection algorithms.	50
Table 4-2.　Percentages for four conditions.	54
Table 4-3.　Hit rate and filter rate for direction-based intra prediction mode algorithm.	58
Table 5-1.　Results of the simulation with 300 frames for each test sequence.	61
Table 5-2.　Results of the simulation with 100 frames for each test sequence.	62
Table 5-3.　Performance comparison of the proposed and Fuzz_HR algorithms.	64
Table 5-4.　Performance comparison of proposed algorithm and algorithm of Kim BG.	65
Table 5-5.　Performance comparison of proposed algorithm and algorithm of Kim et al.	65
Table 5-6.　Results of simulations with 200 frames for each test sequence.	67
Table 5-7.　Performance of our proposed algorithms.	68
Table 5-8.　Average performance comparison.	71
Table 5-9.　Results of simulations with 200 frames for each test sequence.	73
Table 5-10.　Results of simulations with 200 frames for each test sequence.	73

[1]	ISO/IEC 14496-10: “Information technology – coding of audio-visual objects – Part 10: advanced video coding,” December 2003.
[2]	T. Wiegand, G. J. Sullivan, G. Bjontegaard, and A. Luthra, “Overview of the H.264/AVC video coding standard,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, no. 7, pp. 560–576, July 2003.
[3]	I. G. Richardson, “H.264 and MPEG-4 Video Compression,” Wiley, 2003.
[4]	G. J. Sullivan and T. Wiegand, “Rate-distortion optimization for video compression,” IEEE Signal Processing Magazine, vol. 15, no. 6, pp. 74–90, 1998.
[5]	T. Wiegand, H. Schwarz, A. Joch, F. Kossentini, and G. J. Sullivan, “Rate-constrained coder control and comparison of video coding standards,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, no. 7, pp. 688–703, 2003.
[6]	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, January–March 2004.
[7]	Y. W. Huang, B. Y. Hsieh, S. Y. Chien, S. Y. Ma, and L. G. Chen, “Analysis and complexity reduction of multiple reference frames motion estimation in H.264/AVC,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 16, no. 4, pp. 507–522, April 2006.
[8]	G. J. Sullivan, P. Topiwala, and A. Luthra, “The H.264/AVC Advanced Video Coding Standard: Overview and Introduction to the Fidelity Range Extensions,” in proceedings of the SPIE conference on Applications of Digital Image Processing (ADIP), pp. 454–474, August 2004.
[9]	T. Wiegand, and S. Gordon, “H.264/MPEG4-AVC fidelity range extensions: tools, profiles, performance, and application areas,” in proceedings of the 2001 IEEE International Conference on Image Processing (ICIP), pp. 593–596, September 2005.
[10]	A. M. Tourapis, “Enhanced predictive zonal search for single and multiple frame motion estimation,” in proceedings of Visual Communications and Image Processing (VCIP-2002), pp. 1069–1079, January 2002.
[11]	Z. B. Chen, P. Zhou, and Y. He, “Fast integer pel and fractional pel motion estimation for JVT,” document JVT-F017, 6th Meeting, Awaji, Japan, December 2002.
[12]	X. Yi, J. Zhang, N. Ling, and W. Shang “Improved and simplified fast motion estimation for JM,” document JVT-P021, 16th Meeting, Poznan, Poland, July 2005.
[13]	I. Choi, J. Lee and B. Jeon, “Fast coding mode selection with rate-distortion optimization for MPEG-4 part-10 AVC/H.264,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 16, no. 12, pp. 1557- 1561, December 2006.
[14]	B.-G. Kim, “Fast selective intra-mode search algorithm based on adaptive thresholding scheme for H.264/AVC encoding,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 18, no. 1 pp. 127-133, January 2008.
[15]	P.-J. Lee and Y.-J. Shih “Fast inter-frame coding with intra skip strategy in H.264 video coding,” IEEE Transactions on Consumer Electronics, vol. 55, no. 1, pp. 158-164, February 2009.
[16]	T.-J. Kim, J.-E. Hong, and J.-W. Suh “A Fast Intra Mode Skip Decision Algorithm Based on Adaptive Motion Vector Map,” IEEE Transactions on Consumer Electronics, vol. 55, no. 1, pp. 179-184, February 2009.
[17]	M. Kim, S. Jung, C.-S. Kim, and S. Sull, “An Efficient Inter-Frame Coding with Intra Skip Decision in H.264/AVC,” IEEE Transactions on Consumer Electronics, vol. 56, no. 2, pp. 856-862, May 2010.
[18]	A. Yu, G. Martin, and H. Park, “Fast inter-mode selection in the H.264/AVC standard using a hierarchical decision process,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 18, no. 2, pp. 186–195, Februray 2008.
[19]	Y.-H. Huang, T.-S. Ou, and H. H. Chen, “Fast Decision of Block Size, Prediction Mode, and Intra Block for H.264 Intra Prediction,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 20, no. 8, pp. 1122-1132, August 2010.
[20]	T. Zhang, G. Tian, and S. Goto, “A frequency-based fast block type decision algorithm for intra prediction in H.264/AVC high profile,” in proceedings of the IEEE Asia Pacific Conference Circuits and Systems (APCCAS), pp. 1292–1295. November 2008.
[21]	Y. C. Wei and C. H. Tseng, “Transformed domain block size and intra mode decision for advanced video coding,” Computer Communication Control and Automation (3CA), 2010 International Symposium, vol. 1, no. 1, pp. 221–224, 2010.
[22]	Y. Lin, Y.-M. Lee, and C.-D. Wu, “Efficient Algorithm for H.264/AVC Intra Frame Video Coding,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 20, no. 10, pp. 1367-1372, October 2010.
[23]	K. Lim, S. Kim, J. Lee, D. Pak, and S. Lee, “Fast Block Size and Mode Decision Algorithm for Intra Prediction in H.264/AVC,” IEEE Transactions on Consumer Electronics, vol. 58, no. 2, pp. 1367–1372, May 2012.
[24]	C.-H. Tseng, H.-M. Wang, and J.-F. Yang, “Enhanced intra-4×4 mode decision for H.264/AVC coder,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 16, no. 8, pp. 1027–1032, August 2006.
[25]	Y.-M. Lee, Y.-T. Sun, and Y. Lin, “SATD-Based Intra Mode Decision for H.264/AVC Video Coding,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 20, no. 3, pp. 463–469, March 2010.
[26]	F. Pan, X. Lin, S. Rahardja, K. P. Lim, Z. G. Li, D. Wu, and S. Wu, “Fast mode decision algorithm for intra prediction in H.264/AVC video coding,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 15, no. 7, pp. 813–822, July 2005.
[27]	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 Transactions on Circuits and Systems for Video Technology, vol. 17, no. 10, pp. 1414–1422, October 2007.
[28]	A.-C. Tsai, A. Paul, J.-C. Wang, and J.-F. Wang, “Intensity gradient technique for efficient intra-prediction in H.264/AVC,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 18, no. 5, pp. 694–698, May 2008.
[29]	H. Li, K. N. Ngan, and Z. Wei, “Fast and efficient method for block edge classification and its application in H.264/AVC video coding,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 18, no. 6, pp. 756–768, June 2008.
[30]	A.-C. Tsai, J.-F. Wang, J.-F. Yang, and W.-G. Lin, “Effective subblock-based and pixel-based fast direction detections for H.264 intra prediction,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 18, no. 7, pp. 975–982, July 2008.
[31]	K. Bharanitharan, B.-D. Liu, J.-F. Yang, and W.-C. Tsai, “A low complexity detection of discrete cross differences for fast H.264/AVC intra prediction,” IEEE Transactions on Multimedia, vol. 10, no. 7, pp. 1250–1260, November 2008.
[32]	D.-Y. Kim, K.-H. Han, and Y.-L. Lee, “Adaptive single-multiple prediction for H.264/AVC intra coding,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 20, no. 4, pp. 610–615, April 2010.
[33]	D. Quan and Y.-S. Ho, “Categorization for fast intra prediction mode decision in H.264/AVC,” IEEE Transactions on Consumer Electronics, vol. 56, no. 2, pp. 1049–1056, May 2010.
[34]	Y. Adibelli, M. Parlak, and I. Hamzaoglu, “Pixel Similarity Based Computation and Power Reduction Technique for H.264 Intra Prediction,” IEEE Transactions on Consumer Electronics, vol. 56, no. 2, pp. 1079–1097, May 2010.
[35]	H. Zeng, K.-K. Ma, and C. Cai, “Hierarchical intra mode decision for H.264/AVC,” IEEE Transactions on Consumer Electronics, vol. 20, no. 6, pp. 907–912, June 2010.
[36]	S.-K. Kwon, A. Punchihewa, D. G. Bailey, S.-W. Kim, and J. Lee, “Adaptive Simplification of Prediction Modes for H.264 Intra-Picture Coding,” IEEE Transactions on Broadcasting, vol. 58, no. 1, pp. 125–128, March 2012.
[37]	JVT reference software [Online]. Available: http://iphome.hhi.de/suehring/tml/download/
[38]	G. Bjontegaard, “Calculation of average PSNR differences between RD-curves,” ITU-T SC16/Q6, Document VCEG-M33, 13th VCEG Meeting, Austin, Texas, USA, April 2001.
[39]	M. T. Pourazad, C. Doutre, M. Azimi, and P. Nasiopoulos, “HEVC: The New Gold Standard for Video Compression,” IEEE Consumer Electronics Magazine, vol. 1, no. 3, pp. 36–46, July 2012.
[40]	G. J. Sullivan, J.-R. Ohm, W.-J. Han, and T. Wiegand, “Overview of the High Efficiency Video Coding (HEVC) Standard,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 22, no. 12, pp. 1649–1668, December 2012.