多功能影片編碼 (Versatile Video Coding, VVC) 是由聯合視頻探勘小組 (Joint Video Exploration Team, JVET) 提出的新一代視訊壓縮標準。不同於目前的標準高效率視訊編碼 (High Efficient Video Coding, HEVC)，VVC在編碼樹單元(Coding Tree Unit, CTU)劃分結構中引入了QTMT (Quadtree with nested multi-type tree)的編碼技術，並將畫面內預測模式從原先的35種增加至67種，與HEVC相比，能夠大幅提升影像壓縮率，然而編碼複雜度同時增加了數倍，整體編碼過程所花費的時間相當地可觀。為了讓VVC能在高壓縮率下減少編碼所需時間，同時獲得較好的峰值信噪比 (Peak Signal to Noise Ratio, PSNR)以及較少的Bjøntegaard delta bit rate (BDBR)損失，因此，我們需要在VVC中的CTU劃分結構以及畫面內預測中，加入較有效率的快速決策演算法以加速編碼計算時間。
本論文提出的畫面內編碼單元快速分割決策法，主要分成兩個部份：第一部份於編碼樹劃分中，提出了區塊紋理偵測及重疊覆蓋範圍檢測的方法；第二部份於畫面內預測中，利用基於區塊紋理偵測的粗略角度選擇、修正最可能的模式 (Most probable mode)，以及使用SATD (Sum of absolute transformed differences) 分類，以降低H.266/VVC在編碼樹劃分以及畫面內預測的編碼複雜度，且保持位元率-失真 (Rate-distortion, RD) 的性能。實驗結果顯示，我們所提出的方法與VVC的參考軟體VTM-4.0比較，在All-Intra的配置下能夠節省42.47%的計算複雜度，並且僅只有1.1%的BDBR損耗。

Versatile Video Coding (VVC) is a new generation of video compression standards proposed by the Joint Video Exploration Team (JVET). Different from the previous generation of video coding standard H.265/HEVC, VVC adopts QTMT (Quadtree with nested multi-type tree) based on Coding Unit Tree (CTU) structure and add the number of intra prediction modes from 35 to 67. Compared with HEVC, it can significantly improve the compression rate. However, the encoding complexity also increases several times, and spends much more time on encoding. It is necessary to propose an efficient method to reduce the encoding time and maintain high compression ratio and less Bjøntegaard delta bit rate (BDBR) loss at the same time. Therefore, we provide a fast and efficient decision method which applied for VVC CTU structure and intra prediction to speed up time in encoding.
In this dissertation, we propose a fast decision algorithm which is divided into two parts. First, the architecture of the proposed CTU partition method, includes block texture detection and overlapping coverage detection. Second, our fast intra mode decision method based on rough mode decision, modified most probable mode (MPM) and SATD (Sum of absolute transformed differences) classification are proposed to reduce the encoding complexity of VVC CTU partition and intra coding while maintaining the rate-distortion (RD) performance. Experimental results show that our proposed method could save 42.47% of computational complexity on average with a 1.1% BDBR increases for the VVC reference software VTM-4.0 under all-intra configuration.

[1]. G. J. Sullivan, J. Ohm, W. Han and T. Wiegand, "Overview of the High Efficiency Video Coding (HEVC) Standard," in IEEE Transactions on Circuits and Systems for Video Technology, vol.22, no. 12, pp. 1649-1668, Dec. 2012, doi: 10.1109/TCSVT.2012.2221191
[2] B. Bross, “Versatile Video Coding (Draft 1)”, JVET-J1001, Joint Video Exploration Team (JVET), Apr. 2018.
[3] F. Bossen, X. Li, K. Suehring, and A. Norkin, AHG Report: Test Model Software Development (AHG3), document JVET-N0003, Joint Video Experts Team (JVET) of ITU-T and ISO/IEC, Mar. 2019.
[4] VTM-4.0 reference software,
https://vcgit.hhi.fraunhofer.de/jvet/VVCSoftware_VTM/-/releases/VTM-4.0
[5] N. Choi, Y. Piao, K. Choi, and C. Kim “CE3.3 related: Intra 67 modes coding with 3MPM,” Joint Video Exploration Team (JVET) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, JVET-K0529, Ljubljana, SL, Jul. 2018.
[6] A. Said, X. Zhao, M. Karczewicz, J. Chen, and F. Zou, “Position Dependent Prediction Combination for Intra-frame Coding,” in IEEE International Conference on Image Processing, pp. 534–538, Phoenix, USA, Sep. 2016.
[7] C. Tsai et al., "Adaptive Loop Filtering for Video Coding," in IEEE Journal of Selected Topics in Signal Processing, vol. 7, no. 6, pp. 934-945, Dec. 2013, doi: 10.1109/JSTSP.2013.2271974.
[8] H. Yang, L. Shen, X. Dong, Q. Ding, P. An and G. Jiang, “Low-Complexity CTU Partition Structure Decision and Fast Intra Mode Decision for Versatile Video Coding,” in IEEE Transactions on Circuits and Systems for Video Technology, vol. 30, no. 6, pp. 1668-1682, June 2020, doi: 10.1109/TCSVT.2019.2904198
[9] S. Park and J. Kang, "Context-Based Ternary Tree Decision Method in Versatile Video Coding for Fast Intra Coding," in IEEE Access, vol. 7, pp. 172597-172605, 2019, doi: 10.1109/ACCESS.2019.2956196.
[10] N. Tang et al., "Fast CTU Partition Decision Algorithm for VVC Intra and Inter Coding," 2019 IEEE Asia Pacific Conference on Circuits and Systems (APCCAS), Bangkok, Thailand, 2019, pp. 361-364, doi: 10.1109/APCCAS47518.2019.8953076.
[11] Pan F, Lin X, Rahardja S, Lim K-P, Li Z-G, Wu D, Wu S, “Fast mode decision algorithm for intra prediction in H. 264/AVC video coding,” IEEE Trans Circ Syst Vi Technol 15(7):813–822, 2005.
[12] Jiang W, Ma H, Chen Y, “Gradient based fast mode decision algorithm for intra prediction in HEVC,” Int Conf Consum Electron Commun Netw (CECNet), 1836–1840, 2012.
[13] da Silva T L, Agostini L V, da Silva Cruz L A, “Fast HEVC intra prediction mode decision based on EDGE direction information,” Proc Eur Signal Process Conf (EUSIPCO), 1214–1218, 2012.
[14] Fang C-M, Chang Y-T, Chung W-H, “Fast intra mode decision for HEVC based on direction energy distribution,” IEEE Int Symp Consum Electron (ISCE), 61–62, 2013.
[15] Tsai A-C, Wang J-F, Lin W-G, Yang J-F, “A simple and robust direction detection algorithm for fast H. 264 intra prediction,” IEEE Int Conf Multimedia Expo, 1587–1590, 2007.
[16] Miso Park and Jechang Jeong, "Fast HEVC Intra Prediction Algorithm with Enhanced Intra Mode Grouping Based on Edge Detection in Transform Domain," Journal of Advances in Computer Networks vol. 3, no. 2, pp. 162-166, 2015.
[17] T. Zhang, M. T. Sun, D. Zhao and W. Gao, "Fast Intra-Mode and CU Size Decision for HEVC," in IEEE Transactions on Circuits and Systems for Video Technology, vol. 27, no. 8, pp. 1714-1726, Aug. 2017.
[18] Chen, J.; Ye, Y.; Kim, S.-H.: Algorithm description for Versatile Video Coding and Test Model 2 (VTM 2), document JVET-K1002, in Proc. of 11th JVET meeting, Ljubljana, SI, July 2018.
[19] Zhang Qiuwen, Xinpeng Huang, Xiao Wang and Weiwei Zhang. “A Fast Intra Mode Decision Algorithm for HEVC Using Sobel Operator in Edge Detection,” International Journal of Multimedia and Ubiquitous Engineering, Vol. 10, No.9, 2015, pp. 81-90.
[20] B. Chung, J. Kim and C. Yim, "Fast rough mode decision method based on edge detection for intra coding in HEVC," The 18th IEEE International Symposium on Consumer Electronics (ISCE 2014), JeJu Island, 2014, pp. 1-2, doi: 10.1109/ISCE.2014.6884419.
[21] M. Jamali, S. Coulombe and F. Caron, "Fast HEVC Intra Mode Decision Based on Edge Detection and SATD Costs Classification," 2015 Data Compression Conference, Snowbird, UT, 2015, pp. 43-52.
[22] G. Bjontegaard, “Calculation of Average PSNR Difference Between RD-curves,” ITU-T Q.6/SG16 VCEG 13th Meeting, Doc. VCEG-M33, 2001.
[23] J. Chen, H. Sun, J. Katto, X. Zeng and Y. Fan, "Fast QTMT Partition Decision Algorithm in VVC Intra Coding based on Variance and Gradient," 2019 IEEE Visual Communications and Image Processing (VCIP), Sydney, Australia, 2019, pp. 1-4, doi: 10.1109/VCIP47243.2019.8965674.