Encounter CU Again: History-Based Complexity Reduction Strategy for VVC Intra-Frame Encoder

Due to the newly adopted Quad Tree with Nested Multi-Type Tree (QTMT) partitioning scheme in Versatile Video Coding (VVC), multiple partitioning combinations can lead to the same Coding Unit (CU) structure. In other words, a CU may be encoded more than once. Based on this feature, a history-based complexity reduction strategy is proposed to accelerate VVC intra-frame coding with extremely low coding losses. Firstly, analyses of the relationship between the 1st round CUs (encoded at the first time) and the following rounds CUs (encountered again and already analyzed in previous partitioning attempts) are provided. Correspondingly, some unnecessary partitioning types are identified and early terminated. Secondly, a hierarchical pruning algorithm is designed, where thresholds are adjusted adaptively in the 1st round and used for pruning in the following rounds. To our knowledge, it is the first attempt to apply this history-based feature to accelerate partitioning for VVC intra-frame coding. Results show that these strategies can achieve 20% encoding time saving (TS) with only 0.18% BDBR increase. In addition, there is a huge potential for High-Resolution videos (21% TS with only 0.1% BDBR increase for 4K sequences). Compared to other works, our method achieves a considerably high TS/BDBR ratio, which indicates a better tradeoff between coding efficiency and complexity.