臺灣博碩士論文加值系統

隨著高畫質視訊產品的需求以及手持式影像傳輸的普及化，國際組織ITU VCEG與MPEG於西元2010年組成JCT-VC團隊制定新一代之視訊壓縮標準，高效率視訊編碼(High Efficiency Video Coding)。與進階視訊編碼(H.264/AVC)標準相比，高效率視訊編碼將目標訂為在維持相同影像品質下將壓縮效率增加一倍，或在保持相同壓縮效率下，減少編碼運算複雜度。由於傳統混和式編碼(hybrid coding)架構的優良特性，高效率視訊編碼使用類似於進階視訊編碼之編碼系統架構，並針對各部份編碼工具加以改進，提高整體壓縮效能。差值四元分割(Residual Quadtree; RQT)編碼技術被納入編碼系統中轉換編碼(Transform Coding)部分。雖然有效地提高了編碼效率，同時也付出額外的運算量作為代價。因此，在這個論文中，我們針對差值四元分割編碼之模式決定(Mode Decision)設計快速演算法。考慮不同大小轉換單元(Transform Unit; TU)之位元率-失真(Rate-Distortion)效率，我們提出以”合併與分割”(Merge-and-Split)為基礎之模式決定架構取代原本採用之縱向優先(Depth-first)模式決定流程。此外，由於大量的零值方塊(zero-blocks)在量化處理與模式決定中產生，我們利用零值方塊的階層繼承特性，提出終止條件有效率地減少不必要之計算量。並且針對非零值方塊設計了兩種終止模式決定流程的方法個別應用在轉換單元合併與轉換單元分割過程當中。此外，我們也使用零值方塊預先偵測演算法來節省運算量。與HEVC高效率視訊編碼標準參考軟體(HM 2.0)比較，在維持相似之影像品質下我們的方法可以減少43%至65%差值四元分割編碼之運算量。

With the demand for high resolution video application and the prevalence of video streaming in wireless networking, recently ITU VCEG and MPEG formed the Joint Collaborative Team on Video Coding (JCT-VC) to develop the next generation video coding standard, High Efficiency Video Coding (HEVC). The target aims to achieve 50% bit rate reduction at about the same video quality, or keep the same compression ratio with less computing power, compared with the state-of-art ITU/MPEG H.264/AVC standard. Taking advantage of the conventional hybrid coding good performance, HEVC keep a similar basic structure to the H.264/AVC coder but with further enhancement on each coding tool to increase the compression efficiency. Among them, a Residual Quadtree (RQT) coding scheme is added to the conventional transform coding procedure. The compression efficiency is increased but at the cost of additional computational complexity compared to the traditional fixed-size transform. In this thesis, we design a fast algorithm for deciding the Residual Quadtree mode. After evaluating the Rate-Distortion efficiency of Transform Unit (TU) sizes, we replace the original depth-first mode decision process by a Merge-and-Split decision process. Furthermore, because a substantial numbers of zero-blocks are produced after quantization and mode decision, we develop a termination condition to eliminate the unnecessary computation by using the inheritance property of zero-blocks. In addition, for nonzero-blocks, two early termination schemes are developed for both TU Merge and TU Split procedures, respectively. The early zero-blocks detection algorithm also saves computing power. Comparing to HM 2.0, our method saves the RQT encoding time from 43% to 65% for a number of test videos with negligible coding loss.

摘要 I
ABSTRACT III
誌謝 V
TABLE OF CONTENTS VII
LIST OF FIGURES IX
LIST OF TABLES X
CHAPTER 1 INTRODUCTION 1
SECTION 1.1 RESEARCH CONTRIBUTIONS 2
SECTION 1.2 THESIS ORGANIZATION 3
CHAPTER 2 OVERVIEW OF HIGH EFFICIENCY VIDEO CODING 4
SECTION 2.1 OVERALL STRUCTURE OF HIGH EFFICIENCY VIDEO CODING 4
2.1.1 Coding Unit Definition 5
2.1.1.1 Coding Unit 5
2.1.1.2 Prediction Unit 6
2.1.1.3 Transform Unit 7
2.1.2 Architecture Overview of HM 2.0 8
2.1.3 Enhanced Coding Tool Features 8
2.1.3.1 Large Block Size Extension 10
2.1.3.2 Intra Prediction 10
2.1.3.3 Inter prediction 10
2.1.3.4 Interpolation Filter 11
2.1.3.5 Transform 11
2.1.3.6 Quantization 11
2.1.3.7 Entropy Coding 11
2.1.3.8 Loop Filtering 12
2.1.3.9 Internal bit-depth increasing 12
SECTION 2.2 EXPERIMENT CONDITIONS 13
CHAPTER 3 RESIDUAL QUADTREE CODING 15
SECTION 3.1 OVERVIEW OF RESIDUAL QUADTREE CODING 15
SECTION 3.2 MODE DECISION FLOW OF RESIDUAL QUADTREE 18
SECTION 3.3 PROBLEM FORMULATION 22
3.3.1 Performance Analysis of RQT 22
SECTION 3.4 DESIGN GOAL 24
CHAPTER 4 FAST RQT MODE DECISION ALGORITHM DESIGN 26
SECTION 4.1 ANALYSIS OF NESTED QUADTREE-BASED TRANSFORM 26
4.1.1 Zero-Block Inheritance 27
4.1.2 RD cost Analysis of Zero-Block 28
4.1.3 Statistics of Transform Unit Partition Size 29
4.1.3.1 Zero-Block TU Partition Mode Distribution 30
4.1.3.2 Nonzero-Block TU Partition Mode Distribution 35
4.1.4 Summary of this Section 36
SECTION 4.2 EARLY TERMINATION SCHEME ON ZERO-BLOCKS 37
SECTION 4.3 PRIORITIZATION OF TU SIZES IN MODE DECISION 37
SECTION 4.4 EARLY TERMINATION SCHEMES FOR TU-MERGE PROCESS 40
4.4.1 ZBI Early Termination for TU Merge 40
4.4.2 Block Adaptive RD Cost Threshold 41
4.4.2.1 Bitrate Prediction 41
4.4.2.2 Block-Level Adaptive Distortion Model 43
4.4.2.3 RD Cost Threshold 50
SECTION 4.5 EARLY TERMINATION SCHEMES FOR TU-SPLIT PROCESS 50
4.5.1 ZBI Early Termination for TU Split 51
4.5.2 RD Cost Prediction by Partial subTUs 51
SECTION 4.6 ENHANCED EARLY DETECTION OF ZERO-BLOCKS 54
SECTION 4.7 OVERVIEW OF PROPOSED ALGORITHM 58
CHAPTER 5 EXPERIMENTS AND DISCUSSIONS 62
SECTION 5.1 PERFORMANCE MEASURE 62
SECTION 5.2 EXPERIMENTAL RESULTS 63
5.2.1 ZBI Early Termination 65
5.2.2 Nonzero-Block Early Termination 66
5.2.3 ZBI plus Nonzero-Block Early Termination 67
5.2.4 Fast RQT Mode Decision Algorithm 70
CHAPTER 6 CONCLUSIONS AND FUTURE WORK 73
SECTION 6.1 CONCLUSIONS 73
SECTION 6.2 FUTURE WORK 74
BIBLIOGRAPHY 76

[1] T. Wiegand, G. Sullivan, and A. Luthra, “Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification (ITU-T Rec. H.264 | ISO/IEC 14496-10 AVC),” ISO/IEC JTC/SC29/WG11 and ITU-T SG16 Q.6, JVT-Go50r1, Mar.2003.
[2] T. Wiegand et al. “Special Section on the Joint Call for Proposals on High Efficiency Video Coding (HEVC) Standardization,” IEEE Trans. Circuits Syst. Video Technol., vol. 20, no. 12, pp. 1661–1666, 2010.
[3] H. M. Hang, W. H. Peng, C. H. Chan and C. C. Chen, “Towards the Next Video Standard: High Efficiency Video Coding,” Asia-Pacific Signal and Information Processing Association Annual Summit and Conference, 2010.
[4] B. Girod, “The Efficiency of Motion-Compensating Prediction for Hybrid Coding of Video Sequences,” IEEE Journal on Selected Areas in Communications, vol. 5, no. 7, pp. 1140-1154, 1987
[5] JCT-VC, “High Efficiency Video Coding (HEVC) Test Model 2 (HM 2) Encoder Description”, JCTVC-D502, April 2011.
[6] JCT-VC, “Common test conditions and software reference configurations”, JCTVC-D600, February 2011.
[7] D. Marpe et al. “Video Compression Using Nested Quadtree Structures, Leaf Merging, and Improved Techniques for Motion Representation and Entropy Coding,” IEEE Trans. Circuits Syst. Video Technol., vol. 20, no. 12, pp. 1676–1687, 2010.
[8] P. A. Chou, T. Lookabaugh, and R. M. Gray, “Optimal pruning with applications to tree-structured source coding and modeling,”IEEE Trans. Inform. Theory, vol. 35, no. 2, pp. 299–315, Mar.1989.
[9] G. J. Sullivan and R. L. Baker, “Efficient quadtree coding of images and video,” IEEE Trans. Image Process., vol. 3, no. 3, pp. 327–331, May1994.
[10] 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, no. 10, October 2006
[11] C.-S. Park, B.-K. Dan, H. Choi, S.-J. Ko, “A Statistical Approach for Fast Mode Decision in Scalable Video Coding,” IEEE Trans. Circuits Syst. Video Technol., vol. 19, no. 12, pp. 1915–1920, 2009.
[12] 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, 1999.
[13] Z. Fan, O. C. Au, and N. M. Cheung, “Transform-Domain Adaptive Correlation Estimation(Trace) for Wyner-Ziv Video Coding,” IEEE Trans. Circuits Syst. Video Technol., vol. 20, no. 11, pp. 1423–1436, 2010.
[14] G. J. Sullivan, “Efficient scalar quantization of exponential and Laplacian random variables,” IEEE Trans. Inform. Theory, vol. 42, no. 5, pp. 1365–1374, Sep. 1996.
[15] G. J. Sullivan and S. Sun, “On dead-zone plus uniform threshold scalar quantization,” in Proc. SPIE Visual Commun. Image Process., Beijing, China, Jul. 2005, pp. 1041–1052.
[16] E. Y. Lam, and J. W. Goodman, “A Mathematical Analysis of the DCT Coefficient Distributions for Images,” IEEE Trans. Image Process., vol. 9, no. 10, pp1661-1666, 2000
[17] H. Wang, S. Kwong, and C. Kok, “Fast Video Coding Based on Gaussian Model of DCT Coefficients,” in Proc. IEEE ISCAS, Island of Kos, Greece, May 21-24 2006, pp. 1073-1076.
[18] H. Wang and S. Kwong, “Hybrid Model to Detect Zero Quantized DCT Coefficients in H.264,” IEEE Trans. Multimedia, vol. 9, no. 4, pp. 728-735, Jun. 2007.
[19] G. Bjontegaard, “Calculation of Average PSNR Differences between RD-curves,” Document VCEG-M33, Apr. 2001
[20] JCT-VC, “CE2: Asymmetric Motion Partition, Non-Square Quadtree Transform and Overlapped Block Motion Compensation”, JCTVC-F582, July 2011