HEVC의 소수 단위 움직임 추정을 위한 보간 필터 중복 연산 감소 방법

학위논문 (석사)-- 서울대학교 대학원 : 전기·컴퓨터공학부, 2016. 8. 이혁재.High-Efficiency Video Coding (HEVC) [1] is the latest video coding standard established by Joint Collaborative Team on Video Coding (JCT-VC) aiming to achieve twice encoding efficiency with comparatively high video quality compared to its predecessor, the H.264 standard. Motion Estimation (ME) which consists of integer motion estimation (IME) and fractional motion estimation (FME) is the bottleneck of HEVC computation. In the execution of the HM reference software, ME alone accounts for about 50 % of the execution time in which IME contributes to about 20 % and FME does around 30% [2].The FMEs enormous computational complexity can be explained by two following reasons: • A large number of FME refinements processed: In HEVC, a frame is divided into CTU, whose size is usually 64x64 pixels. One 64x64 CTU consists of 85 CUs including one 64x64 CU at depth 0, four 32x32 CUs at depth 1, 16 16x16 CUs at depth 2, and 64 8x8 CUs at depth 3. Each CU can be partitioned into PUs according to a set of 8 allowable partition types. An HEVC encoder processes FME refinement for all possible PUs with usually 4 reference frames before deciding the best configuration for a CTU. As a result, typically in HEVCs reference software, HM, for one CTU, it has to process 2,372 FME refinements, which consumes a lot of computational resources. • A complicated and redundant interpolation process: Conventionally, FME refinement, which consists of interpolation and sum of absolute transformed difference (SATD), is processed for every PU in 4 reference frames. As a result, for a 64x64 CTU, in order to process fractional pixel refinement, FME needs to interpolate 6,232,900 fractional pixels. In addition, In HEVC, fractional pixels which consist half fractional pixels and quarter fractional pixels, are interpolated by 8-tap filters and 7-tap filters instead of 6-tap filters and bilinear filters as previous standards. As a result, interpolation process in FME imposes an extreme computational burden on HEVC encoders. This work proposes two algorithms which tackle each one of the two above reasons. The first algorithm, Advanced Decision of PU Partitions and CU Depths for FME, estimates the cost of IMEs and selects the PU partition types at the CU level and the CU depths at the coding tree unit (CTU) level for FME. Experimental results show that the algorithm effectively reduces the complexity by 67.47% with a BD-BR degrade of 1.08%. The second algorithm, A Reduction of the Interpolation Redundancy for FME, reduces up to 86.46% interpolation computation without any encoding performance decrease. The combination of the two algorithms forms a coherent solution to reduce the complexity of FME. Considering interpolation is a half of the complexity of an FME refinement, then the complexity of FME could be reduced more than 85% with a BD-BR increase of 1.66%Chapter 1. Introduction 1 1. Introduction to Video Coding 1 1.1. Definition of Video Coding 1 1.2. The Need of Video Coding 1 1.3. Basics of Video Coding 2 1.4. Video Coding Standard 2 2. Introduction to HEVC 6 2.1. HEVC Background and Development 6 2.2. Block Partitioning Structure in HEVC 9 Chapter 2. Fractional Motion Estimation in HEVC and Related Works on Complexity Reduction 21 1. Motion Estimation 21 2. Fractional Motion Estimation 22 2.1. Interpolation 22 2.2. Sum of Absolute Transformed Difference Calculation 27 2.3. Fractional Motion Estimation Procedure 28 Chapter 3. Complexity Reduction for FME 31 1. Problem Statement and Previous Studies 31 1.1. Problem Statement 31 1.2. Previous Studies 32 2. Proposed Algorithms 34 2.1. Advanced Decision of PU Partitions and CU Depths for Fractional Motion Estimation in HEVC 34 2.2. Range-based interpolation algorithm 40 Chapter 4. Experiment Results 43 1. Advanced Decision of PU Partitions and CU Depths for Fractional Motion Estimation in HEVC Algorithms 43 1.1. Advanced Decision of PU Partitions 43 1.2. Advanced Decision of CU Partitions 47 1.3. Combination of Advanced PU Partition and CU Depth Decision 47 1.4. Comparison with Other Similar Works 48 2. Range-based Algorithm 49 2.1. Software Implementation 49 2.2. Hardware Implementation of the Algorithm 50 Chapter 5. Conclusion 61 Bibliography 64 Abstract in Korean 66Maste