Fast Intra/ Inter Mode Decision Algorithms for High Efficiency Video Coding (HEVC)


Student thesis: Doctoral Thesis

View graph of relations


  • Junaid TARIQ

Related Research Unit(s)


Awarding Institution
Award date20 Sep 2016


Demand for High Definition (HD) videos is increasing day by day, as they provide realistic viewing experience to the user. However, this dramatically increases the data volume associated with the HD videos for bandwidth-limited applications such as live video streaming, HD video conferencing, HD TV broadcasting, and others. To address this issue, video coding was introduced which enables us to squeeze a huge amount of data through bandwidth-limited channels. In order to meet the requirement of today and tomorrow’s video applications, the efficiency of video coding has been pushed to the limit repeatedly, resulting in standards like H.262, H.263, MPEG-4, H.264/ Advance Video Coding (AVC), and H.265/ High Efficiency Video Coding (HEVC). HEVC is the most recent state-of-the-art video coding standard with significant improvements over the old standards including H.264/AVC, and attains about 50% bit-rate saving compared to H.264/AVC while retaining the same reconstruction quality.
HEVC achieves high compression efficiency by adopting advanced coding techniques such as: extending coding unit (CU) size from 8×8 to 64×64 compared to maximum macro block (MB) size of 16×16 in H.264/AVC; supporting up to 35 intra modes for Luma component compared to maximum of only 9 intra modes in H.264/AVC; availability of eight inter modes in HEVC compared to seven inter modes in H.264/AVC; an enlarged integer pixel level motion estimation (ME) search window from 65×65 to 129×129 in HEVC, and so on. These extensions in HEVC significantly improves the compression efficiency, but at the cost of intensive computational complexity. Therefore, it is necessary to build fast and efficient algorithms that are practical for real-time application.
To reduce the computational complexity of HEVC codec, five algorithms are proposed in this thesis. Firstly, an adaptive and efficient intra modes selection model is proposed for HEVC codec that is based on the investigation of the correlation between the statistical properties of the reference samples and the current intra block, to find out which modes will be efficient for the current block. In this work, intra modes are efficiently shortlisted by calculating the Euclidean distance between the statistical features of the reference samples and the current block. Then, an efficient most-probable-mode (MPM) selection method is proposed that selects the modes for MPM by investigating the correlation between the neighboring blocks and the current block. Experimental results demonstrate that the average Bjøntegaard delta bit rate (BD-BR) saving of the proposed approach is -0.11%, and Bjøntegaard delta peak signal-to-noise ratio (BD-PSNR) is improved by 0.0065%.
Secondly, a hybrid approach for reducing intra coding complexity is proposed for HEVC codec. In this work, DC mode is declared as the optimal mode whenever the variance of available reference pixels is zero. After that, working of rough-mode-decision (RMD) is optimized by evaluating transform of fewer than 35 modes. Then, modes list to rate distortion optimization (RDO) is refined by using the neighboring modes correlation concept. Finally, an early prediction unit (PU) split termination technique is proposed which compares RD of available sub-PUs to the RD of 2N×2N PU. Experimental results demonstrate that the average time saving of the proposed approach is 40%, whilst the BD-BR increment is only 0.37%.
Thirdly, a quadratic approach for reducing the computational complexity of intra mode coding is proposed for HEVC encoder. In this work, the relationship between the RD-cost and the SAD is investigated. Then, a model is proposed to estimate the RD-cost of all 35 intra modes using the quadratic relation, thus avoiding the computation of entropy coding, Hadamard cost, distortion, and transform. Experimental results demonstrate that the average time saving of the proposed approach is 31-38%, while the BD-BR increment is only 0.62-1.37%, respectively.
Fourthly, a framework for the early decision of MERGE mode (EDM) is proposed to overcome the brute force inter mode decision for the coding unit (CU) in HEVC. In this work, the relationships between the prediction-results, i.e. RD-Cost/ SAD of CUs in previous intra/inter frame(s), and the prediction-results of merge candidates (MrgCands) for current CU is modeled for EDM. Then, the RD-cost based statistical model for EDM is proposed that is based on the observation that MERGE is selected 98.20% on average when 2N×2N produces similar prediction-results as of MERGE. Subsequently, two additional EDMs are proposed for 8×8 CUs because in a 64×64 CU there are 26 CUs of 8×8 that goes through the same brute force mode evaluation which causes the bottleneck in complexity reduction. The first additional algorithm models the motion similarity among spatial MrgCands of 8×8 CUs to identify uniform motion regions for EDM, because MERGE is selected 96% on average for regions having uniform motion. At last, a model is proposed that obtains the minimum SAD values for the prediction units (PU) of each inter mode using the reference block matching process in the motion-estimation (ME) of 2N×2N and performs EDM for 8×8 CUs based on the comparison of these SAD values. Experimental results demonstrate that an average 48.40% coding time can be saved, while the BDBR increase is only 1.83%. In addition, an average of 68.04% complexity reduction can be achieved with 1.80% BD-BR increase for conference video sequences.
Finally, fast intra mode prediction strategies are proposed to overcome the brute force method of mode selection for the coding unit (CU) in High Efficiency Video Coding (HEVC). In this chapter, spatial/ temporal correlations of intra frames are investigated and a new cost function is designed for shortlisting the intra modes. Firstly, the RMD module of HEVC is improved by incorporating the probabilistic model, which is based on spatial/ temporal knowledge. Secondly, a novel RD-cost prediction model is developed for early termination that is based on the RD-cost variation in the neighboring CUs with-respect-to their co-located CUs. Finally, an optimal stopping point is derived to early terminate the intra modes evaluation that is based on the classical secretary problem (CSP). Experimental results demonstrate that the RMD module of HEVC and the state-of-the-art fast intra mode prediction published method is outperformed by saving up to 0.61% and 0.91% BD-BR on average, respectively.