Motion Estimation Skipping Strategies for Low-Complexity HEVC Encoding : 저복잡도 HEVC 부호화를 위한 움직임 예측 생략 전략

다국어 초록 (Multilingual Abstract)

In video coding, motion estimation (ME) that predicts a block among temporally correlated frames has had a crucial impact on not only the compression efficiency, but also the computational complexity. Particularly, fast ME algorithms has been a pivot in much research that attempts to reduce the complexity of video encoder while preserving the compression efficiency as much as possible. However, the overall complexity of ME including time and memory complexity was increased much further in the high efficiency video coding (HEVC) codec to meet twice better coding efficiency than AVC/H.264 codec due to the diversified changes: more various motion partitions, more various motion directions, and more elaborated motion accuracy. Since encoder has to encode huge pixels due to the increased video resolution such as 4K ultra-high-definition (UHD) and 8K UHD, the complexity of ME should be overcome for low-complexity HEVC encoding.
To relieve the complexity of HEVC, two ME skipping strategies are proposed in this dissertation by considering those various changes of HEVC. One is a bidirectional motion estimation (BME) skipping strategy that avoids most compression-inefficient search points for bidirectional motion that has high computational complexity due to additional interpolation process in contrast with unidirectional motion estimation (UME). The proposed method exploits the stochastic correlation of the context of prediction units (PUs)—one of the special characteristic of HEVC—to determine whether BME is critical or not. The other is a skipping strategy of sub-pixel motion estimation (SME) that avoids inefficient search points of half-pixel and of quarter-pixel motions and skips associated interpolation process. Utilizing the correlation of the context of PUs, the second proposed method determines whether SME is critical or not during the encoding of UME and BME. The proposed method additionally checks SME for far reference frames from the current frames to decrease the complexity of SME further. When utilizing two proposed strategies, low-complexity HEVC encoding could be achieved, sustaining reasonable compression performance.
To demonstrate the performance of motion estimation skipping strategies, the following complexity measurement methods were carefully chosen: the number of related function calls, running time, and memory access count. Through experimental results, the proposed BME skipping strategy showed that the time complexity of bi-prediction can be reduced to 36% on average while losing a 0.5% increase of BD-rate, outperforming existing methods in view of encoding time, number of function calls, and memory access. In addition, the proposed SME skipping strategy showed that the time complexity of ME can be reduced to 51% (random access case) and 52% (low-delay case) on average, outperforming existing method. Therefore, the proposed two ME skipping strategies should be considered in low-complexity HEVC encoder for real-time broadcasting systems, surveillance applications, and mobile video encoding devices of battery-constraint.

목차 (Table of Contents)

• Contents i
• List of Figures iii
• List of Tables v
• Glossary vii
• Abstract ix
• CHAPTER 1 Introduction 1
• CHAPTER 2 Motion Estimation in HEVC 7
• 2.1. Overview of Motion Estimation in HEVC 7
• 2.2. Bidirectional Motion Estimation in HEVC 13
• 2.3. Sub-pixel Motion Estimation in HEVC 14
• 2.4. Related Work 17
• CHAPTER 3 Complexity Analysis of Motion Estimation in HEVC 19
• 3.1. Time Complexity of Motion Estimation during HEVC encoding 19
• 3.2. Complexity Analysis of Bidirectional Motion Estimation in HEVC 21
• 3.3. Complexity Analysis of Sub-pixel Motion Estimation in HEVC 25
• CHAPTER 4 Motion Estimation Skipping Strategies 28
• 4.1. Bidirectional Motion Estimation Skipping Strategy for Low-complexity HEVC Encoding 28
• 4.1.1. Correlation of Bi-prediction with Previously Encoded ME Information 28
• 4.1.2. Proposed Method 32
• 4.1.3. Experimental Results 34
• 4.2. Sub-pixel Motion Estimation Skipping Strategy for Low-complexity HEVC Encoding 47
• 4.2.1. Correlation of Sub-pixel MV with Previously Encoded ME Information 47
• 4.2.2. Proposed Method 51
• 4.2.3. Experimental Results 55
• 4.3. Results of Combined Motion Estimation Skipping Strategies 64
• CHAPTER 5 Conclusion 68
• Bibliography 70
• Acknowledgement 74
• List of Publications 77
• List of Patents 80
• List of Contributions 81
• 국문요지 85
• 감사의 글 87