Abstract
In this paper, a fast inter mode decision algorithm, called the unimodal model-based inter mode decision (UMIMD), is proposed for the latest video coding standard, the high-efficiency video coding (HEVC). Through extensive simulations, it has been observed that a unimodal model (i.e., with only one global minimum value) can be established among the size of different prediction unit (PU) modes and their resulted rate-distortion (RD) costs for each quad-tree partitioned coding tree unit (CTU). To guarantee the unimodality and further search the optimal operating point over this function for each CTU, all the PU modes need to be first classified into 11 mode classes according to their sizes. These classes are then properly ordered and sequentially checked according to the class index, from small to large so that the optimal mode can be early identified by checking when the RD cost starts to arise. In addition, an effective instant SKIP mode termination scheme is developed by simply checking the SKIP mode against a pre-determined threshold to further reduce the computational complexity. The extensive simulation results have shown that the proposed UMIMD algorithm is able to individually achieve a significant reduction on computational complexity at the encoder by 61.9% and 64.2% on average while incurring only 1.7% and 2.1% increment on the total Bjontegaard delta bit rate (BDBR) for the low delay and random access test conditions, compared with the exhaustive mode decision in the HEVC. Moreover, the experimental results have further demonstrated that the proposed UMIMD algorithm outperforms multiple state-of-the-art methods.
Introduction
The High Efficiency Video Coding (HEVC/H.265) standard provides approximately 50% better compression efficiency than its predecessor, H.264/AVC. However, this improvement comes at the cost of significantly increased computational complexity. A primary source of this complexity is the exhaustive search for the optimal block partitioning. HEVC uses a quad-tree structure where Coding Tree Units (CTUs) are recursively split into smaller Coding Units (CUs), and each CU is further divided into Prediction Units (PUs) and Transform Units (TUs). Finding the best combination of these units requires calculating the Rate-Distortion (RD) cost for every possible configuration, which is a major bottleneck for real-time and low-power encoding applications.
Methods
The proposed Unimodal Model-based Inter Mode Decision (UMIMD) algorithm optimizes this process by exploiting the mathematical properties of the RD cost function.
Unimodal Search Strategy
The researchers observed that when prediction modes are ordered by size, the resulting RD cost function typically exhibits unimodality—meaning it has a single global minimum. To leverage this, the algorithm classifies PU modes into 11 distinct classes based on their dimensions and checks them in a specific sequence.
By searching from larger to smaller block sizes, the encoder can identify the "sweet spot" where the reduction in prediction residual bits no longer outweighs the increase in header bits. As soon as the RD cost begins to rise, the algorithm terminates the search, assuming the optimal mode has been found.
Instant SKIP Termination
For video regions with low motion or smooth textures, the "SKIP" mode is often the most efficient. UMIMD incorporates an early termination scheme that compares the SKIP mode's RD cost against a threshold. This threshold is dynamically calculated as an exponential function of the Quantization Parameter (QP). If the cost is below the threshold, the search is terminated immediately, bypassing further partitioning checks.
Experimental Results
The UMIMD algorithm was benchmarked using the HEVC reference software (HM 16.7) across standard test sequences ranging from 240p to 1080p (Classes A through E).
- Complexity Reduction: The algorithm achieved an average reduction in encoding time of 61.9% for low-delay (LD) configurations and 64.2% for random-access (RA) configurations.
- Coding Efficiency: This significant speedup was achieved with a minimal impact on video quality, resulting in a Bjontegaard delta bit rate (BDBR) increase of only 1.7% (LD) and 2.1% (RA).
- Comparative Performance: UMIMD demonstrated superior performance compared to several state-of-the-art fast-mode decision algorithms, providing a more favorable trade-off between complexity and compression efficiency.
Conclusion
The UMIMD algorithm provides a robust solution for accelerating HEVC encoding by utilizing the unimodal nature of RD costs in block partitioning. By combining a sequential search strategy with early SKIP termination, it achieves over 60% reduction in computational complexity with negligible quality loss. Future research may explore applying these unimodal modeling principles to the more complex partitioning structures of the Versatile Video Coding (VVC/H.266) standard.
Summary updated