隨著視訊會議、視訊監控、電視等……多媒體技術的迅速發展以及高畫質視訊(720P,1080P)的普及。人們對視訊解析度需求越來越高，因此國際組織ITU-T的視頻編碼專家組和ISO/IEC聯合制定了新一代的高效率視訊編碼規格(High Efficiency Video Coding, HEVC或H.265)，與前一代視訊編碼標準H.264相比，在相同視訊質量的條件下，可以節省50%左右的編碼位元率，但其編碼計算複雜度也相對提高。
H.265/HEVC視訊壓縮標準在進行畫面間預測時，會針對每個模式進行RDO(Rate Distortion Optimization)的計算與比較，從中挑選出最佳的模式做為當前預測單元的編碼模式，由於每個模式都必須計算，因此H.265在模式選擇所花費的計算複雜度是相當高的。本論文主要採用3個test sequences做為統計樣本，統計Merge模式在不同深度下被編碼為最佳模式的機率，並利用此統計結果搭配 1.殘差經過轉換量化後大多數為0的特性 2.Inter NxN移動估測的資訊來做提早決策，提早決定最佳模式，跳過後續的模式選擇，以達到減少編碼時間的目的。
實驗結果顯示，我們所提出的提早終止模式選擇演算法與HEVC參考軟體HM16.14原本的模式選擇演算法相比，能節省35%~51%(平均43%)左右的編碼時間，但只有少量的位元率增加與視訊品質損失。

With the rapid development of multimedia technology, video conferencing, video surveillance, television, etc, international organizations ITU-T video coding expert group and ISO / IEC jointly developed a new generation of high efficiency video coding (High Efficiency Video Coding, HEVC or H.265), which needs only half the bit rate of its predecessor, the H.264. In the mode decision of its inter-frame prediction, H.265/HEVC computes the rate-distortion (RD) cost of each mode. After comparing all computed RD costs, it choose the mode having the lowest RD cost as the inter-frame prediction mode. Hence, the computational complexity of the inter-frame prediction of the H.265/HEVC standard is very high.
In this thesis, we employ 3 commonly used test video sequences as samples to get the statistical Merge mode distribution, RTQ, and the motion estimation information to help us design a method for early termination decision. The method can help to reduce the encoding time.
The experimental results show that the proposed algorithm of early termination mode selection can save approximately 35% ~ 51%(average 43%) coding time compared with the HEVC reference software HM16.14’s original mode selection algorithm. Only a small amount of bitrate increasing and quality loss are observed.

[1] K. Choi, S.-H. Park, and E. S. Jang, "Coding Tree Pruning Based CU Early Termination," document JCTVC-F092, JCT-VC, https://hevc.hhi.fraunhofer.de/, Jul 2011.
[2] J. Yang, J. Kim, K. Won, H. Lee, and B. Jeon, "Early SKIP Detection for HEVC, " document JCTVC-G543, JCT-VC, https://hevc.hhi.fraunhofer.de/, Nov 2011.
[3] Jinlei Zhang, Bin Li, "An Efficient Fast Mode Decision Method for Inter Prediction in HEVC," IEEE Transactions on Circuits and Systems for Video Technology, vol. 26, no. 8, pp. 1502-1515, Aug. 2016.
[4] Kuang-Han Tai, Min-Yuan Hsieh, Mei-Juan Chen, Chia-Yen Chen, Chia-Hung Yeh, “A Fast HEVC Encoding Method Using Depth Information of Collocated CUs and RD Cost Characteristics of PU Modes,” IEEE Transactions on Broadcasting, vol 63, no. 4,pp.680-692, 2017.
[5] Zhaoqing Pan, Sam Kwong, Ming-Ting Sun and Jianjun Lei, "Early MERGE Mode Decision Based on Motion Estimation and Hierarchical Depth Correlation for HEVC," IEEE Transactions on Broadcasting, vol. 60, no. 2, pp. 405-412, Jun. 2014.
[6] Koga, T, "Motion-Compensated Interframe Coding for Video Conferencing," in National Telecommunication Conference, New Orleans, pp. G5.3.1-G5.3.5. 1981.
[7] J. Y. Tham, S. Ranganath, M. Ranganath, and A. A. Kassim, "A novel unrestricted center-biased diamond search algorithm for block motion estimation," IEEE Transactions on Circuits and Systems for Video Technology, vol. 8, pp. 369-377, Aug. 1998.
[8] Ce Zhu, Xiao Lin, and Lap-Pui Chau, "Hexagon-Based Search Pattern for Fast Block Motion Estimation," IEEE Transactions on Circuits and Systems for Video Technology, vol. 12, no. 5, pp. 349-355, May. 2002.
[9] Phong Nguyen, Hieu Tran, Hai Nguyen, "Asymmetric diamond search pattern for motion estimation in HEVC," in International Conference on Communications and Electronics (ICCE), Danang, Vietnam, 2014, pp. 434-439.
[10] Hassan Kibeya, Fatma Belghith, Mohamed Ali Ben Ayed and Nouri Masmoudi, "Adaptive Motion Estimation Search Window Size for HEVC Standard," in 7th International Conference on Sciences of Electronics, Technologies of Information and Telecommunications (SETIT), Hammamet, Tunisia, 2016, pp. 410-415.
[11] Gary J. Sullivan, Jens-Rainer Ohm, Woo-Jin Han, Thomas Wiegand,, "Overview of the High Efficiency Video Coding," IEEE Transactions on Circuits and Systems for Video Technology, vol. 22, no. 12, pp. 1649-1668, Dec. 2012.
[12] Maxim P. Sharabayko, Oleg G. Ponomarev, Roman I. Chernyak, "Intra compression efficiency in VP9 and HEVC," Applied Mathematical Sciences, vol. 7, no. 137, pp. 6803-6824, Nov. 2013.
[13] JVT of ISO/IEC MPEG, ITU-T VCEG, "MVC software Reference Manual-JMVC 8.2," https://hevc.hhi.fraunhofer.de/, May. 2010.
[14] ISO/IEC JTC 1/SC 29/WG 11 (MPEG), "High efficiency video coding, ITU-T Recommendation,"http://www.itu.int/ITUT/recommendations/rec.aspx?rec=11885&lang=zh, Apr. 2013.
[15] Marpe, D., Schwarz, H., and Wiegand, T,, "Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC Video Compression Standard," IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, no. 7, pp. 620-636, Jul. 2003.
[16] Andrey Norkin, Gisle Bjøntegaard, Arild Fuldseth, Matthias Narroschke, Masaru Ikeda,, "HEVC Deblocking Filter," IEEE Transactions on Circuits and Systems for Video Technology, vol. 22, no. 12, pp. 1746-1754, Dec. 2012.
[17] Sio-Kei Im, Ka-Hou Chan,, "Multi-lambda search for improved rate-distortion optimization of H.265/HEVC," in International Conference on Information, Communications and Signal Processing (ICICS), Singapore, Singapore, 2015.
[18] Frank Bossen, "Common test conditions and software reference configurations," https://hevc.hhi.fraunhofer.de/, Jan. 2013.
[19] R. H. Gweon and Y.-L. Lee, "Early Termination of CU Encoding to Reduce HEVC Complexity," document JCTVC-F045, JCT-VC, https://hevc.hhi.fraunhofer.de/, Jul. 2011.
[20] Rui Fan, Yongfei Zhang, Bo Li, "Motion Classification-Based Fast Motion Estimationfor High-Efficiency Video Coding," "IEEE Transactions on Multimedia, vol. 19, no. 5, pp. 893-907, May. 2017.
[21] Stéphane Pateux, Joel Jung, "An excel add-in for computing Bjontegaard metric and its evolution," https://hevc.hhi.fraunhofer.de/, Jan. 2007.