A fast algorithm of intra prediction modes pruning for HEVC based on decision trees and a new three-step search

The High Efficiency Video Coding (HEVC) standard is a new generation video coding scheme, succeeding to H.264/AVC. HEVC requires only 50 % bitrate of H.264/AVC at the same perceptual quality by adopting new coding tools and more flexible block structures. HEVC specifies 35 different intra prediction directions that can be associated to different block sizes. Each possible combination needs to be tested within the Rate Distortion (RD) process to enable selecting the optimal intra mode and block splitting depth. This leads to a significant processing weight and therefore any improvement that might be achieved will bring significative increase in the computational efficiency of the algorithm. This paper proposes a novel intra prediction modes pruning method based on decision trees and a new three-step search algorithm, aiming at achieving higher encoding efficiency compared to the standard—HEVC. This fast algorithm is composed of two algorithms. The first algorithm is a modes pruning algorithm depending on decision trees. We first calculate variances of the above side, the left side and all the reference samples of all the PUs (Prediction Units), which are used to divide the PUs into three groups of different candidate intra prediction modes. The first group only includes Planar mode and DC mode, the optimal mode will be selected from the two modes. The second and third groups include 19 and 35 intra modes, respectively. Then the decision trees are trained using the information obtained previously by the software WEKA. The classification process has an accuracy of 85.29 %. The second algorithm is a three-step search algorithm which is defined to be suitable for prediction units classified into class two and class three after the execution of decision trees. The detailed implementations of three-step search algorithms for prediction units belong to those two classes are subtly different. Experimental results verify that, compared with the reference software HM15.0, on average, the proposed algorithm reduces the encoding time by 37.87 % with a slightly decreasing of BD-PSNR (0.058 dB) and increasing of BD-Rate (1.19 %).