Early CU Termination Based on SKIP/Merge RD Cost for B Frames in HEVC
Jing Shen, Xiaoyun Zhang, Zhiyong Gao, Jia Wang
Institute of Image Communication & Information Processing
Shanghai Jiao Tong University
Shanghai, China
jingshen1990@gmail.com, {xiaoyun.zhang, zhiyong.gao, jiawang}@sjtu.edu.cn
Abstract—Compared to H.264/AVC, High Efficiency Video
Coding (HEVC) aims to deliver the same video quality at half
the bit rate. However, it imposes enormous computational
complexity because of taking advantage of a more adaptive
quad-tree structure, rate distortion optimization (RDO) and
etc. In this paper, a fast decision method is proposed to reduce
HEVC encoder complexity of B frames which avoids
unnecessary mode decision and rate distortion optimization
(RDO). It is found that there exist strong correlations between
PU modes, depth distribution and SKIP/Merge RD cost. We
statistically analyze the prediction mode distribution according
to SKIP/Merge RD cost of current CU depth and depth
distribution according to SKIP/Merge RD cost of 64x64 and
32x32 CUs. Based on the analysis results, the proposed
algorithm includes an early detection of SKIP mode and a
depth pruning to skip searching for 8x8 and 16x16 CUs. This
algorithm enables us to skip unnecessary RDO by early
termination of mode decisions in CUs. Experimental results
show that the encoding complexity can be reduced by 50% on
average with only 1.25% BD-rate increase compared to the
HEVC test model (HM) 12.0 reference software.
Keywords-HEVC, Mode Decision, SKIP/Merge RD cost,
RDO
I.
INTRODUCTION
HEVC is the latest video coding standard developed by
ITU-T Video Coding Experts Group and the ISO/IEC
Moving Picture Experts Group. The main goal of the HEVC
standardization effort is to enable significantly improved
compression performance relative to existing standard - to
reduce 50% bit rate on average for equal perceptual video
quality [1]. To achieve this goal, several efficient coding
algorithms were introduced to HEVC which also made
HEVC encoders several times more complex than
H.264/AVC encoders. In [2], the authors described several
complexity-related aspects that were considered in the
standardization process, including quad-tree-based block
partitioning, motion estimation, RDO and so on.
HEVC adopts a more adaptive quad-tree structure based
on a coding tree unit (CTU) instead of a macroblock in
H.264/AVC. This allows HEVC to support coding unit (CU)
size from 64x64 to 8x8. Kim et al [3] show that the benefits
from the use of larger CU size become really significant
when the test sequences are high-resolution video sequences.
CU is a basic unit of region splitting used for intra/inter
prediction, which allows recursive subdividing into four
equally sized blocks. Additionally, in inter frames, each CU
enables different prediction unit (PU) modes: SKIP mode,
Merge mode, Inter 2Nx2N, Inter Nx2N, Inter 2NxN, Inter
2NxnU, Inter 2NxnD, Inter nLx2N, Inter nRx2N, Inter NxN
(only available for the smallest CU), Intra 2Nx2N and Intra
NxN (only available for the smallest CU). To obtain the best
CU block partitioning and coding modes, the HEVC
encoder needs to test all the possible modes and select the
one which provides the smallest RD cost by means of rate
distortion optimization (RDO) process. This greatly
increases computational complexity of the encoder. Tan et
al [4] illustrates that using a fixed CU size of 16x16
involves 1584 times of RDO process, while using a CTU
structure of 64x64 and a maximum quad-tree depth of 4
involves 8415 times of RDO process.
RD cost of coding modes is computed through the RDO
process by a Lagrange cost function (𝐽
𝑚𝑜𝑑𝑒
) as follows:
𝐽
𝑚𝑜𝑑𝑒
=
(
𝑆𝑆𝐸
𝑙𝑢𝑚𝑎
+ 𝜔
𝑐ℎ𝑟𝑜𝑚𝑎
∙ 𝑆𝑆𝐸
𝑐ℎ𝑟𝑜𝑚𝑎
)
+ 𝜆 ∙ 𝐵
𝑚𝑜𝑑𝑒
(1)
where 𝐵
𝑚𝑜𝑑𝑒
is the bitrate cost of corresponding coding
mode, SSE is the sum of square error between original
pixels and reconstructed pixels, 𝜔
𝑐ℎ𝑟𝑜𝑚𝑎
is a weighting
factor for chroma component and 𝜆 is the Lagrange
multiplier. To obtain reconstructed pixels and bitrate,
Motion Estimation (ME), Motion Compensation (MC),
Transform, Quantization, Entropy Coding, Inverse
Quantization, Inverse Transform are conducted at the
HEVC encoder, which make RD cost computation really
complex. However, RD cost computation of SKIP and
Merge mode is simple because there is no residue
information for SKIP mode and Merge mode doesn’t need
ME process. In addition, SKIP mode has a very high
occurrence probability in HEVC. So it is worthwhile to take
advantage of SKIP/Merge RD cost to skip other complex
RDO process. Our proposed algorithm is mainly based on
this idea.
The rest of the paper is organized as follows. Section 2
briefly reviews some relevant fast algorithms. Section 3
introduces the proposed fast algorithm in details.
Performance evaluations and analysis are presented in
Section 4. At last, the conclusion is drawn in Section 5.