Early Termination for Integer Motion Estimation via Multi-Level Successive Elimination in Versatile Video Coding
Tan-Phat Dang, Nhu-Hoang Nguyen, Tuan-Kiet Tran, Anh Tuan Hoang, Huu-Thuan Huynh, Cong‐Kha Pham · IEEE Access · 2025
Integer motion estimation (IME) dominates the computational budget of Versatile Video Coding (VVC) encoders, creating a bottleneck for high-resolution and low-delay applications. Prior fast full-search (FS) methods (e.g., multi-level successive elimination algorithm (MSEA)) reduce runtime via lower-bound pruning but rely only on local per-candidate information, and are primarily tailored to square blocks, hindering direct use in VVC’s non-square partitions. To address these issues, we propose a VVC-compatible method with three components. First, an MSEA-based early-termination scheme (MSEA-ET) with coarse and refined stages leverages spatial correlation in rate-distortion (RD) cost and the elimination level to raise the rejection rate beyond baseline MSEA. Second, we integrate a rate-cost-based search order (RCSO) that visits candidates at ascending rate costs, which is implemented within VVC for the first time. Third, a unified square partition (USP) decomposes non-square blocks into square subblocks, enabling efficient reuse of intermediate sums and practical integration of MSEA within VVC. On the VVC test model (VTM) 15.0, experimental results show that our method reduces encoding time by 76.19% compared with FS while preserving encoding efficiency. Additionally, the proposed approach achieves average early-termination rates up to 21.88% across sequences and notably higher rates for larger blocks (e.g., up to 40% for 128×128). Compared with other fast FS methods, our approach delivers substantial improvements, with average encoding-time savings up to 67.38 %. Our contributions are cross-candidate information reuse for tighter early termination, the first VVC integration of RCSO, and USP for non-square partitions; together, these contributions enhance encoding performance, aiming for real-time applications. Moreover, a hybrid strategy that combines our method with a pattern-based search method to coarsely localize promising regions, followed by local fast FS refinement, is a promising direction for future work.