Opportunity
In video coding, achieving the optimal rate-distortion (R-D) trade-off is a fundamental challenge. The operational R-D bound, which defines the best achievable compression performance for a given encoding scheme, is continually pushed by introducing more efficient coding tools. However, in modern video standards like Versatile Video Coding (VVC), the encoder’s decision process—involving coding unit (CU) partitioning, prediction modes, and transform selections—is typically optimized independently for each CU using greedy, local rate-distortion optimization (RDO). This approach ignores the dependencies between neighboring CUs, which arise due to predictive and entropy coding techniques. Consequently, the encoder may settle for suboptimal solutions, leaving significant performance gains unexplored. While joint optimization methods that consider CU dependencies have been explored for earlier standards like H.264/AVC and H.265/HEVC, applying them directly to VVC intra coding is challenging due to its more flexible partition structures (e.g., quadtree with multi-type tree) and advanced coding tools. This creates an opportunity to develop a computationally feasible joint optimization algorithm that can harness these dependencies to push the operational R-D bound further for VVC, especially in intra coding scenarios where spatial correlations are critical.
Technology
The patent introduces a beam search-based joint rate-distortion optimization (BSJRDO) algorithm tailored for VVC intra coding. The core innovation lies in modeling the joint RDO problem as a multistage decision process, where each stage corresponds to a CU. Instead of independently optimizing each CU (greedy approach) or exhaustively searching all possible decision paths (Viterbi algorithm), the BSJRDO algorithm maintains a customized subset of promising decision paths at each stage. Specifically, for a given stage, a subspace of the full decision space—containing the b_i best paths (where b_i is the beam size) with the lowest accumulated Lagrangian cost—is selected for consideration in subsequent stages. This allows the encoder to incorporate dependencies between CUs while keeping computational complexity manageable. To further enhance practicality, the algorithm truncates dependencies between CUs at different partitioning depths, reducing memory and computational overhead. Additionally, the beam size can be flexibly adjusted based on CU characteristics (e.g., width and height), enabling fine-grained scalability to meet diverse computational constraints. The BSJRDO scheme is implemented within the VVC Test Model (VTM) framework and fully conforms to VVC decoding syntax, ensuring compatibility with existing standards.
Advantages
- Achieves significant bit-rate savings compared to conventional greedy RDO, with up to 1.30% BDBR-YUV reduction under common test conditions and 3.22% under low-bit-rate scenarios.
- Provides a scalable trade-off between computational complexity and coding performance through adjustable beam sizes and non-uniform configurations.
- Incorporates CU dependencies in a low-complexity manner, bridging the gap between independent optimization and exhaustive joint search.
- Implementation-friendly, with no changes required to VVC decoding syntax, facilitating easy deployment in existing encoders.
- Enables finer granularity in optimization by allowing beam size adaptation based on CU characteristics (e.g., size).
- Outperforms reduced-state Viterbi algorithms (RSVA) in coding gain under VVC intra coding configurations.
Applications
- Real-time video encoding applications requiring high compression efficiency, such as streaming services, video conferencing, and broadcast.
- Storage-constrained environments where reduced bit rates are critical, including cloud-based video storage and archival systems.
- Hardware-accelerated video encoders in consumer electronics (e.g., smartphones, cameras, and televisions).
- Research and development of next-generation video coding standards beyond VVC.
- Adaptive video delivery networks that optimize encoding parameters based on network conditions and device capabilities.
