In order to achieve greater coding efficiency compared with the previous video coding standards, various advanced coding techniques are used in the High Efficiency Video Coding (HEVC) standard, such as a flexible partition and a large number of intra prediction modes. However, these techniques lead to much greater complexity that restricts HEVC from realtime applications. To solve this problem, a fast intra mode decision algorithm is proposed in this paper that uses the block's textural properties to determine the partition depth range and decide whether to split or skip smaller sizes of the coding unit. Besides that, the number of candidate modes for the rough mode decision process is also reduced depending on the block's property. Experimental results for the recommended test sequences by the JCT-VC show that the proposed algorithm can save an average of 44% encoder time with a slight loss in performance compared to the reference software HM-16.20.
The rapid development of social networks and the exchange of multimedia content sets
many new requirements for transmission and storage systems. In terms of video
compression, although H.264/AVC (Advanced Video Coding) [
This paper focuses on improving the intra-frame coding - one important process in HEVC by early deciding to split the block and select the best suitable candidate modes. The rest of this paper is organized as follows. In Section 2, the intra-frame coding is briefly introduced. The proposed algorithm is presented in Section 3. Section 4 provides the experimental results, and Section 5 concludes this paper.
Instead of using macroblock as in H.264, HEVC uses the coding tree unit (CTU). Using
the quad-tree partitioning technology, CTU can be split into coding units (CU) - the
basic unit of separation, which has sizes from 64 64 to 8 8, corresponding to a depth of
0 to 3 (Fig. 1a). Based on the partition depth, CU can be recursively split into four equal
CUs. The optimal CTU partition is determined using the rate-distortion cost (RDcost).
In intra-frame coding, each CU is divided into prediction units (PU), which will select
the optimal predictions from 35 modes, including Planar mode (mode 0 - for a slowly
changing area), DC mode (mode 1 - more suitable for a homogeneous area) and 33
angular modes (mode 2 - 34 for different texture directions) (Fig. 1b). Thus, the efficiency
of intra coding increases, but with a significant computational load, even though the
official reference software HM [
a) b)
Recently, much work has been published that offers various solutions to reduce the
computational complexity of the intra mode decision process in HEVC. In general, they
can be divided into two main types: optimization of the partitioning process of CU or
PU [
Fast Intra Mode Decision Algorithm for HEVC 3
decisions [
Based on the analysis of existing works, this paper proposes a fast algorithm for intra-frame coding in HEVC, which allows making an early decision on CTU splitting and adaptively choosing candidates for the prediction process. 3
3.1
CU can have a size from 64 64 to 8 8, with the intra PU varying from 64 64 to 4 4. The flexible structure in HEVC shows its effectiveness since the encoder can use CU in different sizes for different areas in the frame. To analyze the correlation between the quad-tree partition and the textural features of a region, Fig. 3 shows an enlarged part of the frame of the ”BasketballDrive” sequence encoded by the HM. It can be shown that in homogeneous areas or areas with a smooth texture, CUs are always selected in large sizes, while small CUs are suitable for more complex areas with rich details. The optimal CU is determined for each area by checking all possible sizes, in other words, all separation depths. This process can cause redundancy and increase computational complexity since in some homogeneous areas, there is no need to check the small sizes of the CU. If the optimal CU size or partition depth range can be decided at the early stage, the wasteful search process of intra mode will be skipped, and thus a considerable amount of complexity can be significantly reduced in HEVC.
Based on the relationship between CU size and texture complexity, an algorithm will be proposed for quickly determining the depth of the CTU, according to which the encoder can collapse the search area to reduce the computational burden of the partitioning process.
The texture complexity of an area or block is strongly related to its samples’ luminance value. The degree of variation in the luminance value in an N N block is determined as follows:
LN N =
1 where Y (i; j) and Ya(i; j) are the luminance values at (i; j) and the average luminance value of the current block, respectively. LN N represents the different luminance parameter of the current block. The more sharply the different luminance values change, the larger value of LN N is obtained.
The value of LN N changes very quickly when the luminance value in the block changes. According to LN N , we classify the block into homogeneous, middle texture, and complex texture. The encoder may terminate the split if the block is homogeneous. Otherwise, a split decision may be made early for blocks with the complex textural property.
8L > <
P1 < L < P2 >:L P2
P1 homogeneous block; middle texture block; complex texture block, (2) where P1; P2 are lower and upper thresholds.
In our algorithm, to avoid calculating complexity for all block sizes, 16 16 CU is selected as the base block. A 32 32 CU is considered complex if at least one of the four 16 16 CUs inside it is complex. Similarly for 64 64 CU. In other cases, the texture of the 32 32 CU is determined by the value L1M6ax16 following Eq. 3, while Eqs. 1 and 2 are used for 32 32 CU, and the textural property of the block of size 64 64 is obtained from L3M2ax32.
>8LNMaxN < >:LNMaxN
P1
P2 P1 < LNMaxN < P2 homogeneous block; middle texture block; complex texture block, (3) where LNMaxN = maxfLkN N g; k = 0; : : : ; 3.
Fast Intra Mode Decision Algorithm for HEVC 5
Since a split decision was made for the CU, the depth of the CTU can be determined in advance, so that the encoder can skip unnecessary depths. Let Dmin and Dmax denote the minimum and maximum depth of the current CTU: (4) (5) Dmin = Dmax = 80 if CU64 64 homogeneous; > <
1 if 9 CU32 32 middle texture; >:2 otherwise. 80 if CU64 64 homogeneous; > > ><1 if 4 CU32 32 homogeneous; >2 if 16 CU16 16 homogeneous; > >:3 if 9 complex texture block CU16 16:
Thus, based on texture complexity, the early decision to split or terminate splitting is made at the CU level, while the optimal depth range is made for the CTU. As a result, the computational cost of determining the optimal block is reduced. 3.2
Statistical analysis of common test sequences shows that the optimal modes’ distributions are not similar for all 35 intra modes. In most of the cases, modes 0 (Planar), 1 (DC), 10 (horizontal mode), and 26 (vertical mode) have larger proportions than other modes, where mode 0 has the highest proportion, and mode 1 has a second proportion, as many PU have relatively smooth textures after CU partition and most of them choose mode 0 or 1 as the optimum mode. Since the textural feature of most sequences has clear vertical or horizontal directions, the proportions of modes 10 and 26 are higher than other angle modes. Furthermore, the adjacent modes to those modes are relatively higher, while the proportions of the rest are insignificant. Hence, the number of input modes for intra prediction can be reduced, focusing on high probability modes to cut-off the complexity of the prediction process.
The original intra mode selection in HM will be modified as follows: instead of all 35, at the first stage of the prediction process, only most probability modes and angular modes in equal distances (List1) are tested using the RMD process to find modes with the lowest cost. After that, one more rough mode decision step (RMD2) was added to check a maximum of 4 more modes surrounding the best results of the first RMD. As a result, the minimum and the maximum number of modes that need to calculate the Hadamard costs are 11 and 15.
List1 = f0; 1; 2; 6; 10; 14; 18; 22; 26; 30; 34g: (6)
The block’s texture properties can also be used to further reduce the total number of candidate modes for intra prediction. Let classify PUs into three categories depending on their sizes: low complex (homogeneous) (PU 64 64), middle complex (PU 32 32, PU 16 16), and complex (PU 8 8, PU 4 4). Table 1 shows the distribution of optimal modes for PU in low and middle complex groups. It can be seen that for homogeneous or middle complex PU, the number of candidate modes can be reduced to save the computational load.
Candidate modes for different PUs are given in Table 2, where for blocks of high complexity (PU 8 8 and PU 4 4) we will leave as in Eq. 6.
The overall algorithm, including early determination of the CTU depth range, early decision of the CU splitting and adaptive selection of candidate modes, is as follows: Step 1. Classify CUs into a homogeneous, middle, and complex texture.
Step 2. Predict the depth range [Dmin; Dmax] based on the texture properties of the CUs.
Step 3. Select a candidate list for PU in different areas. Calculate RMD. Step 4. Calculate RMD2 for additional modes. Add most probable modes (MPM).
Step 5. Calculate the RDO. Choose the best mode. 4
The proposed algorithm was implemented in HM-16.20, and several standard test
sequences of different categories were selected for testing. All frames were encoded with
the All Intra-Main configuration and four values of the quantization parameter (QP):
22, 27, 32, 37 [
The proposed algorithm’s effectiveness is estimated using two metrics: Bjontegaard
delta bitrate (BD-BR) and Bjontegaard delta peak-signal-to-noise (BD-PSNR) [
The comparative results of the proposed algorithm and the original HM-16.20 are shown in Table 3. The proposal can reach up to 63% of time-saving, while BD-BR increased on average by 2.54%, and the loss of BD-PSNR was 0.074dB.
Fast Intra Mode Decision Algorithm for HEVC 7 In order to reduce the computational complexity of the intra mode decision process in HEVC, this paper proposes a fast algorithm that uses the correlation between the textural property of an area and the CTU partitioning process. The variation degree of the luminance value is used to evaluate a block, from which the encoder can make a decision on CU splitting and determine the CTU depth range. Also, based on the PU sizes, the number of candidate modes for the selection process is significantly reduced. Experimental data show that the proposed algorithm can save about 44% of the encoding time while maintaining almost the same performance.