簡易檢索 / 詳目顯示

回結果列表
研究生： 柯達人
Bharanitharan, Karunanithi
論文名稱： H.264/AVC視訊編碼器外框與內框預測之快速演算法設計
Efficient Fast Algorithms for Inter/Intra Predictions in H.264/AVC Encoders
指導教授： 劉濱達
Liu, Bin-Da
楊家輝
Yang, Jar-Ferr
學位類別： 博士
Doctor
系所名稱： 電機資訊學院 - 電機工程學系
Department of Electrical Engineering
論文出版年： 2009
畢業學年度： 97
語文別： 英文
論文頁數： 101
中文關鍵詞： 邊緣方向偵測 、外框編碼 、內框編碼 、快速演算法
外文關鍵詞： H.264/AVC, inter prediction, intra prediction, edge detection, fast algorithm
相關次數： 點閱：106  下載：3 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • H.264為最新的數位視訊壓縮標準，藉由引進不同的編碼特點以獲得更高的壓縮效率。其中，以外框不同大小區塊編碼與內框預測編碼具有較高的運算複雜度。外框/內框預測，是由編碼時藉由影像品質與資訊量最佳化所獲得，這表示編碼器必需計算所有的外框/內框模式預測的編碼組合，但這個最佳化的計算過程對於即時應用卻是一大挑戰。因此，本論文提出兩個內框及一個外框編碼之快速演算法。
    　　首先，在所設計的內框模式選擇演算法中，提出一個低複雜度的快速決定模式演算法，基於使用畫面內既有的資訊，進而從編碼最佳化中移除不相似的模式計算，經由不同的位置去計算垂直與水平的差值，可正確找出邊緣的方向。實驗結果顯示，此演算法可減少約56%的編碼時間。此演算法也以硬體架構方式實現，該架構包含差值計算與方向偵測單元，整個硬體架構利用Synopsys的Design Compiler以UMC 0.18 μm的製程合成，並利用Verilog-XL模擬，由合成的模擬結果得知，此硬體可操作在50 MHz的頻率。此外，我們對內框模式預測提出另一個有效的快速演算法，是利用區塊的相似性來判斷該模式是否需要經由編碼最佳化去計算碼率。所提出的演算法能有效地偵測出紋理，藉此在區塊中預測出方向，因此能減少最佳化模式的計算量，此演算法約可減少63%的內框編碼時間。
    　　除了內框預測外，我們對外框編碼提出一種階層式的交叉取差值演算法，以分析預編碼區塊與參考區塊的相似性，此低複雜度演算法能有效地減少79%的外框模式編碼時間。

    H.264, MPEG-4 Part 10, is the latest digital video coding standard that achieves very high data compression by using several new coding features. Among various key features, intra prediction and variable block sizes for inter prediction are vital to compression efficiency. The inter/intra prediction is based on the rate distortion optimization (RDO) procedure, which requires a true encoding of the inter/intra block by trying all inter/intra prediction modes. The computational burden of inter/intra prediction with the RDO procedure is extremely high for real time applications.
    In this dissertation, we propose three fast algorithms, two for intra prediction and one for inter prediction. A low complexity fast mode decision algorithm for H.264/AVC intra prediction that uses discrete cross differences (DCD) to reduce unlikely candidate modes in the RDO calculation is proposed. By using horizontal and vertical differences in different locations, the directions of the edges can be precisely detected. Experimental results show that the proposed fast mode decision algorithm reduces the encoding time by about 56%, with negligible loss of video quality in terms of PSNR and bit-rate. To realize the proposed algorithm, a VLSI design, which comprises a cross difference unit and a direction detection unit, is implemented for the mode pre-selection stage of intra prediction. The design is synthesized using UMC 0.18 µm CMOS technology and simulated with Verilog-XL. The operating frequency of the synthesized core can exceed 50 MHz.
    We also propose an efficient fast intra mode decision method that uses the bi-region similarity detection (BSD) algorithm to reduce the number of candidate modes required for the RDO procedure. The proposed BSD algorithm effectively estimates the texture direction of the block to narrow down the predictive modes to reduce RDO computation. Experimental results show that the proposed algorithm achieves a time reduction of more than 63% with negligible PSNR loss and bit rate increase.
    Finally, we propose a hierarchal cross differences (HCD) algorithm that analyzes the spatial and temporal homogeneity of a block to reduce the number of candidate modes which are required for RDO calculation for the inter mode decision. The proposed low computational complexity algorithm reduces the complexity by up to 79% on average without affecting the video quality.

    Abstract… i Acknowledgement iv Table of Contents v List of Tables viii List of Figures ix Chapter 1 Introduction 1 1.1 Motivation 1 1.2 Main Contribution 2 1.3 Dissertation Outline 3 Chapter 2 Basic Concepts of the H.264/AVC Intra and Inter Prediction 4 2.1 Overview of H.264/AVC Standard 4 2.2 Basic Concept of Luma 4×4 Intra Prediction 5 2.2.1 Vertical prediction mode 7 2.2.2 Horizontal prediction mode 8 2.2.3 DC prediction mode 8 2.2.4 Diagonal_Down_Left prediction mode 9 2.2.5 Diagonal_Down_Right prediction mode 10 2.2.6 Vertical_Right prediction mode 11 2.2.7 Horizontal_Down prediction mode 12 2.2.8 Vertical_Left prediction mode 13 2.2.9 Horizontal_Up prediction mode 14 2.3 Basic Concept of Luma 16×16 Intra Prediction 15 2.4 Basic Concept of Chroma 8×8 Intra Prediction 16 2.4.1 Intra_Chroma_DC prediction mode 17 2.4.2 Intra_Chroma_Plane prediction mode 18 2.5 Cost Function 19 2.6 Basic Concepts of Inter mode prediction 19 2.7 Literature Review of Inter/Intra Prediction 21 Chapter 3 Low Complexity Detection of Discrete Cross Differences (DCD) Algorithm for Fast H.264/AVC Intra Prediction 25 3.1 Introduction 25 3.2 Proposed DCD Algorithm 25 3.2.1 DCD Pattern Analysis 27 3.2.1.1 Inner cross differences pattern 27 3.2.1.2 Diagonal cross differences pattern 29 3.2.2 Candidate Mode Decision Analysis 30 3.2.2.1 Normal approach analysis 30 3.2.2.2 Improved approach analysis 33 3.3 Simplified Discrete Cross Difference (SDCD) 34 3.4 Proposed Algorithm for Intra 16×16 and 8×8 35 3.5 Algorithm Complexity Analysis 36 3.6 Experimental Results and Discussion 38 3.7 Algorithm Coding Mode Verification 49 3.8 VLSI Implementation of the Proposed SDCD Algorithm 51 3.8.1 Discrete differencing unit 51 3.8.2 Direction detection unit 53 3.9 Verification 55 3.10 Summary 57 Chapter 4 Bi-Region Similarity Detection Algorithm (BSD) for Fast H.264/AVC Intra Mode Decision 58 4.1 Introduction 58 4.2 Proposed BSD Algorithm 58 4.2.1 Mode decision analysis 60 4.2.2 Boundary block analysis 62 4.3 Overall Flow of Bi-region Similarity Detection (BSD) Algorithm 64 4.4 BSD Algorithm for 16×1 6 Luma and 8×8 Chroma blocks 67 4.5 Experimental Results and Discussion 68 4.6 Summary 72 Chapter 5 Hierarchical Cross Difference Algorithm (HCD) for Fast Inter Mode Prediction in H.264/AVC Encoder 73 5.1 Introduction 73 5.2 Brief Overview of the Conventional Inter Mode Decision 73 5.3 Statistical Analyses of Block Sizes in Video Sequences 75 5.4 Proposed HCD Algorithm 79 5.4.1 Spatial homogeneity 82 5.4.2 Temporal homogeneity 82 5.5 Overall flow of the Hierarchical Cross Difference Algorithm 83 5.6 Experimental Results and Discussion 86 5.7 Summary 89 Chapter 6 Conclusion and Future Work 90 6.1 Conclusion 90 6.2 Future Work 91 References 92 Publication List 100

    [1] Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification (ITUT Rec. H.264/ISO/IEC 14496-10 AVC), Mar. 2003.

    [2] T. Wiegand, G. J. Sullivan, G. Bjontegaard, and A. Luthra, “Overview of the H.264 / AVC Video Coding Standard,” IEEE Trans. Circuits and Syst. Video Technol., vol. 13, pp. 560–576, Jul. 2003.

    [3] G. Sullivan, T. Wiegand, and K.-P. Lim, “Joint model reference encoding methods and decoding concealment methods,” JVT Meeting (JVT-I049d0), San Diego, CA, Sep. 2003.

    [4] C. L.Yang and L.-M. Po, “A fast H.264 intra prediction algorithm using macroblock properties,” in Proc. IEEE ICIP, Oct. 2004, vol. 2, pp. 461 – 464.

    [5] C. C. Wang, T. S. Chen, and C. W. Tung, “Fast intra-mode Decision in H.264 using interblock correlation,” in Proc. IEEE ICIP, Oct. 2006, vol. 2, pp. 1345-1348.

    [6] C. L. Yang, L. M. Po, and W. H. Lam, “A fast H.264 intra prediction algorithm using macroblock properties,” in Proc. IEEE ICIP, Oct. 2004, vol. 2, pp. 461- 464.

    [7] Y. D. Zhang, F. Dai, and S. X. Lin, “Fast 4×4 intra-prediction mode selection for H.264,” in Proc. IEEE ICME, Jun. 2004, vol.1, pp. 1151-1154.

    [8] J. B. Song, B. Li, W. Li, and L. Jiang, “A novel fast intra prediction algorithm applied in H.264/AVC,” in Proc. ICSP, Nov. 2006, pp.16- 20.

    [9] Y. D. Zhang, F. Dai, and S. X. Lin, “Fast 4×4 intra-prediction mode selection for .264,” in Proc. IEEE ICME, Jun. 2004, vol. 3, pp. 1151-1154.

    [10] R. Su, G. Liu, and T. Zhang, “Fast mode decision algorithm for intra prediction in H.264/AVC,” in Proc. IEEE ICASSP, May 2006, vol. 2, pp. 921-924.

    [11] C. H. Tsai, Y. W. Huang, and L. G. Chen, “Algorithm and architecture optimization for full-mode encoding of H.264/AVC intra prediction,” in Proc. MWSCAS, Aug. 2005, vol. 2, pp. 47-50.

    [12] M. Jafari, and S. Kasaei, “Fast intra-prediction mode decision in H.264 Advanced Video Coding,” in Proc. IEEE ICCS, Oct. 2006, vol. 2, pp.1-6.

    [13] G. Y. Jiang, S. P. Li, M. Yu, and F. C. Li, “An efficient fast mode selection for intra prediction,” in Proc. IEEE IWVDVT, May 2005, vol. 3, pp. 357-360.

    [14] Y. N. Sairam. N. Ma, and N. Sinha, “A novel partial prediction algorithm for fast 44 intra prediction mode decision in H.264/AVC,” in Proc. IEEE DCC, Mar. 2008, vol.2, pp. 232-241.

    [15] C. L. Hsu, M. H. Ho, and J. J. Hong, “An efficient algorithm for intra-prediction in H.264,” in Proc. IEEE ICCE, Jan. 2006, vol. 2, pp. 35-36.

    [16] Information Technology–Coding of Audio-Visual Objects–Part2: Visual, ISO/IEC 14496 -2, 1999.

    [17] Video Coding for Low Bit Rate Communication, ITU-T Rec. H.263, 1998.

    [18] I. E. G. Richardson, H.264 and MPEG-4 Video Compression. Chichester, UK: John Wiley & Sons, 2003.

    [19] V. Bhaskaran and K. Konstantinides, Image and Video Compression Standards: Algorithms and Architectures. Boston, MA: Kluwer Academic, 1997.

    [20] C. H. 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-1032, Aug. 2006.

    [21] C. Kim, H.-H Shih, C.-C. J. Kuo “Feature-based intra-prediction mode decision for H.264”, in Proc. IEEE ICIP, Oct. 2004, vol. 2, pp.769 - 772.

    [22] 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 Trans. Circuits Syst. Video Technol., vol. 15, no. 7, Jul. 2005, pp. 813-822.

    [23] A. K. Jain and A. Vailaya, “Image retrieval using color and shape,” Pattern Recogn., vol. 29, Aug. 1996, pp. 1233–1244,

    [24] H. Li and K. - N. Ngan, “Fast and efficient method for block edge classification,” in Proc. ACM IWCMC, Jul. 2006, vol. 2, pp. 67-72.

    [25] S.-W. Lee, Y.-M. Kim, and S. W. Choi, “Fast scene change detection using direct feature extraction from mpeg compressed videos,” IEEE Trans. Multimedia, vol. 2, no. 4, Dec. 2000, pp. 240–254.

    [26] H. S. Chang and K. Kang, “A compressed domain scheme for classifying block edge patterns,” IEEE Trans. Image Processing, vol.14, no. 2, Feb.2005, pp.145–151.

    [27] 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, Jun. 2007, pp.882-888.

    [28] P. A. A. Assuncao and M. Ghanbari, “Transcoding of MPEG-2 video in the frequency domain,” in Proc. IEEE ICASSP, Apr. 1997, vol. 4, pp. 2633-2636.

    [29] T. Shanableh, and M. Ghanbari, “Hybrid DCT/pixel domain architecture for heterogeneous video transcoding,” Signal Processing: Image Commun., vol.18, no. 8, Sep. 2003, pp. 601-620.

    [30] G. Hwang, J. Park, B. Jung, K. Choi, Y. Joo, Y. Oh, and B. Jeon, “Efficient fast intra mode decision using transform coefficients,” in Proc. IEEE ICAT, Feb. 2007, vol.1, pp. 399-402.

    [31] K. R. Rao and P. Yip, Discrete Cosine Transform: Algorithm, Advantages, Applications. London, UK: Academic Press, 1990.

    [32] T. Tsukuba, I. Nagayoshi, T. Hanamura, and H. Tominaga, “H.264 fast intra-prediction mode decision based on frequency characteristic,” in Proc. EUSIPCO, Sep. 2005, vol. 2, pp.234-238.

    [33] T. Hattori and K. Ichige, “Intra-prediction mode decision in H.264/AVC using DCT coefficients,” in Proc. IEEE ISPACS, Dec. 2006, vol.3, pp. 135-138.

    [34] Z. Wang, J. Yang, Q. Peng, Z. Ma, and C. Zhu, “A fast transform domain based algorithm for H.264/AVC intra prediction,” in Proc. IEEE ICME, Jul. 2007, vol.4, pp. 1563-1566.

    [35] B. Meng and O. C. Au, “Fast intra-prediction mode selection for 4x4 blocks in H.264”, in Proc. IEEE ICASSP, Mar. 2003, vol. 3, pp. 389-392.

    [36] B. Meng, O. C. Au, C. W. Wong, and H. K. Lam, “Efficient intra-prediction mode selection for 44 blocks in H.264,” in Proc. IEEE ICME, Jul. 2003, vol. 4, pp. 521-524.

    [37] J. W. Chen, C. H. Chang, C. C. Lin, Y. H. Ouyang, J. I. Guo, and J. S. Wang, “A condition-based intra prediction algorithm for H.264/AVC,” in Proc. IEEE ICME, Jul. 2006, vol. 3, pp. 1077-1080.

    [38] 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 1411-1422, Oct. 2007.

    [39] G. Fernandez-Escribano, J. Bialkowski, J. A. Gamez, H. Kalva, P. Cuenca, L. Orozco-Barbosa, and A. Kaup, “Low-complexity heterogeneous video transcoding using data mining,” IEEE Trans. Multimedia, vol. 10, pp. 286-299, Feb. 2008.

    [40] 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. Circuits Syst. Video Technol., vol. 16, pp.1185-1195, Oct. 2006.

    [41] J. K. Lin, “Fast H.264 inter mode decision based on hierarchical homogeneous detection and cost analysis,” Master Thesis, National Cheng Kung University, Tainan, Taiwan, July 2006.

    [42] 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-788, Jun. 2005.

    [43] E. A., Al Q., and T.S Chang, “Fast variable block motion estimation by adaptive early termination,” IEEE Trans. Circuits Syst. Video Technol., vol. 16, no. 8, pp.1053-1057, Aug. 2006.

    [44] Z. Zhou. and M.T Sun, “Fast macroblock inter mode decision and motion estimation for H.264/MPEG4 AVC,” in Proc. IEEE ICIP, Oct. 2004, vol. 3, pp. 243-263.

    [45] Y. H. Moon, G. Y. Kim, and J. H. Kim, “An improved early detection algorithm for all-zero blocks in H.264 video encoding,” IEEE Trans. Circuits Syst. Video Technol., vol. 15, no. 8, pp.1053–1057, Aug. 2005.

    [46] 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–888, Jun. 2005.

    [47] B. Feng, G.X Zhu, and W.Y Liu, “Fast adaptive inter-prediction mode decision method for H.264 based on spatial correlation,” in Proc. IEEE ISCAS, May 2006, vol. 2, pp. 1804-1807

    [48] C.-H. Kuo, M. Shen, and C.-C. J. Kuo, “Fast inter-prediction mode decision and motion search for H.264,” in Proc. IEEE ICME, Jun. 2004, vol. 1, pp. 663–666.

    [49] J.You, W. Kim and J. Jeong, “16x16 Macroblock Partition Size Prediction for H.264 P Slices,” IEEE Trans. Consumer Electron., vol. 52, no. 4, pp. 1377-1383. Nov 2006.

    [50] C. Crecos and M. Y. Yang, “Fast inter-mode prediction for P slices in the H264 video coding standard,” IEEE Trans. Broadcast., vol. 51, no. 2, pp. 256–263, Jun. 2005.

    [51] 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–279, Feb. 2008.

    [52] D. Wu, F. Pan, K. P. Lim, S. Wu, Z. G. Li, X. Lin, S. Rahardja, and C. C. Ko, “Fast intermode decision in H.264/AVC video coding,” IEEE Trans. Circuits Syst. Video Technol., vol. 15, no. 6, pp. 953–958, Jul. 2005.

    [53] D. S. Turaga and T. Chen, “Classification based mode decisions for video over networks,” IEEE Trans. Multimedia, vol. 3, no. 1, pp. 41–52, Mar. 2001.

    [54] C. J. Kuo, “Feature-based intra-/inter coding mode selection for H.264/AVC,” IEEE Trans. Circuits Syst. Video Technol., vol. 17, no. 4, pp. 441–453, Jul. 2007.

    [55] 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–1561, Dec. 2006.

    [56] L. Salgado and M. Nieto, “Sequence independent very fast mode decision algorithm on H.264/AVC baseline profile,” in Proc. IEEE ICIP, Oct. 2006, pp. 41–44.

    [57] X. Jing and L.-P. Chau, “Fast approach for H.264 inter-mode decision,” Electron. Lett., vol. 40, no. 17, pp. 1050–1052, Sep. 2004.

    [58] T. Uchiyama, N. Mukawa, and H. Kaneko, “Estimation of homogeneous regions for segmentation of textured images,” in Proc. IEEE ICPR, Sep. 2000, vol.4, pp. 1072–1075.

    [59] X. W. Liu, D. L. Liang, and A. Srivastava, “Image segmentation using local spectral histograms,” in Proc. IEEE ICIP, Oct. 2001, vol. 2, pp. 70–73.

    [60] H.264/AVC Reference Software JM. Available: http://iphome.hhi.de/suehring/tml

    [61] G. Bjontegaard, “Calculation of average PSNR differences between RD-curves,” VCEG-M33, Austin, TX, Apr. 2001.

    [62] R. C. Gonzalez and R. E. Woods, Digital Image Processing, Prentice Hall, 2002

    [63] C. W. Ku, C. C. Cheng, G. S. Yu, M. C. Tsai, and T. S. Chang, “A high-definition H.264/AVC intra-frame codec IP for digital video and still camera applications, ” IEEE Trans. Circuits Syst. Video Technol., vol. 16, no. 8, pp. 917-928, Aug. 2006.

    [64] E. Sahin and I. Hamzaoglu, “An efficient hardware architecture for H.264 intra prediction algorithm,” in Proc. IEEE DATE, Apr. 2007, pp. 1-6.

    [65] E. Sahin and I. Hamzaoglu, “An efficient intra prediction hardware architecture for H.264 video decoding,” in Proc. IEEE DSD, Aug. 2007, vol. 2, pp. 448-454.

    [66] S. B. Wang, X. L. Zhang, and Z. Wang, “H.264 intra prediction architecture optimization,” in Proc. IEEE ICME, Jul. 2007, vol. 3, pp. 1571-1574.

    [67] K. Suh, S. Park, and H. Cho, “An efficient hardware architecture of intra prediction and TQ/IQIT module for H.264 encoder,” ETRI Journal, vol. 27, pp. 511-524, Oct. 2005.

    [68] C. H. Tsai, Y. W. Huang, and L. G. Chen, “Algorithm and architecture optimization for full-mode encoding of H.264/AVC intra prediction,” in Proc. IEEE MWSCAS, Aug. 2005, vol. 2, pp. 47-50.

    [69] Z. Y. Cheng, C. H. Chen, B. D. Liu, and J. F. Yang, “High throughput 2-D transform architecture for H.264 advanced video coders,” in Proc. IEEE APCCAS, Dec. 2004, vol. 3, pp. 1141-1144.

    [70] Y. W. Huang, B. Y. Hsieh, T. C. Chen, and L. G. Chen, “Analysis, fast algorithm, and VLSI architecture design for H.264/AVC intra frame coder,”IEEE Trans.Circuits Syst. Video Technol., vol. 15, no. 3, pp. 378–401, Mar. 2005.

    下載圖示 校內：2012-02-26公開
    校外：2013-02-26公開
    QR CODE