Rate-Distortion-Complexity Optimized Coding Mode Decision for HEVC

The newest generation of video coding standard, high efficiency video coding (HEVC), significantly improves the video compression efficiency by introducing more flexible block partitioning structures and richer coding modes than those of the previous coding standards; however, the encoders suffer from high-computational complexity, which greatly hinders their extensive application. Extensive studies on optimizing the complexity of the HEVC encoders have been conducted. However, most studies do not effectively achieve a trade-off between the rate-distortion (RD) performance loss and complexity during the rate-distortion optimization (RDO). In this paper, we mathematically define the complexity-constrained RDO problem as a constrained optimization problem of subset selection. Next, based on the classification methodology, the derivation process for this optimization problem is simplified to find the adaptive threshold function in the feature space with extremely low complexity. The proposed method is also highly general and is applicable to algorithm design for various coding mode decisions, such as coding unit splitting, prediction unit partitioning and transform unit tree decision, and the global optimum can be achieved. Compared with existing methods, the experimental results show that the proposed method can reduce the coding time by 2-16% with the same RD performance loss and can decrease the BD rate by 0.1-1.2% under the same complexity. In addition, this method is capable of flexibly adjusting the complexity under different rate-distortion complexity trade-off requirements.