Balancing Compression Efficiency and Computational Complexity

This direction is split into other directions: real-time encoding constraints, speed-quality tradeoff in video compression. Its last version stays readable and citable here.

Version 1 of 183 papers98 conceptsfrozen 2026-10-04

In the world of video engineering, there is no such thing as a free lunch. Every leap in compression efficiency—the ability to squeeze high-definition video into smaller bitrates—has historically come at the cost of a staggering increase in computational complexity.

As standards evolved from H.264/AVC to HEVC (H.265) and finally to VVC (H.266), the research community shifted its focus. It was no longer enough to simply reduce file sizes; the new challenge was making these "efficiency kings" actually runnable on consumer hardware without draining batteries or causing hour-long latencies for a single frame.

The Complexity Paradox

The fundamental mechanism of modern video coding is a massive search problem. To find the most efficient way to represent a frame, an encoder must test thousands of combinations of block sizes, prediction directions, and transform types.

As Jar‐Ferr Yang, Hsueh‐Ming Hang, and Ming–Ting Sun noted in Advanced Video Technologies and Applications for H.264/AVC and Beyond, features like variable block sizes and exhaustive rate-distortion optimization (RDO) create a significant barrier for real-time deployment. By the time the industry reached VVC, the encoding process had become up to 31 times more complex than its predecessors, as detailed by Jizheng Xu and colleagues in Intra Encoding Complexity Control with a Time-Cost Model for Versatile Video Coding.

This creates a "complexity paradox": we save energy on data transmission (bandwidth), but we spend it—often in greater quantities—on the local processor. Dmitriy S. Vatolin and Roman Kazantsev quantified this in Power Consumption of Video-Decoders on Various Android Devices, showing that the battery drain of newer codecs can offset their storage benefits on mobile platforms.

Pruning the Search Space

To make high-efficiency coding practical, researchers focus on "fast mode decision" algorithms. The goal is to predict the best way to compress a block of pixels without actually trying every possible option.

  1. Heuristic Pruning: Yu Liu and Junjuan Li demonstrated in DCT Based Fast INTRA Mode Decision Method for HEVC Coding that by analyzing the texture direction of an image using Discrete Cosine Transform (DCT) coefficients, an encoder can narrow down 35 possible prediction modes to just a few likely candidates, slashing encoding time by over 40%.
  2. Learning-Based Prediction: Instead of manual heuristics, newer methods use neural networks to "look" at a frame and decide how to partition it. Liulin Chen proposed a deep learning approach in Fast Learning-Based Split Type Prediction Algorithm for VVC that achieves a 67% reduction in encoding time by predicting block partitions before the heavy computation begins.

Parallelism and Architectural Efficiency

When algorithmic pruning isn't enough, researchers turn to structural changes that allow hardware to process video more effectively.

  • Hybrid Parallelization: Younhee Kim and Jinwuk Seok explored combining frame-level and tile-level processing in Tile-level and Frame-level Parallel Encoding for HEVC. By breaking a frame into independent "tiles," multiple CPU cores can work on the same image simultaneously.
  • Selective State Spaces: In the realm of learned (neural) compression, Jinpeng Wang introduced MambaVC: Learned Visual Compression with Selective State Spaces. This approach replaces heavy Transformer or CNN blocks with Selective State Space Models (SSMs), which scale linearly with image resolution rather than quadratically, significantly reducing the memory and compute footprint for high-resolution 4K and 8K video.

From R-D to R-D-C Optimization

The traditional gold standard for video coding was Rate-Distortion (R-D) optimization: finding the lowest bitrate for a given level of quality. However, the modern research direction has evolved toward Rate-Distortion-Complexity (R-D-C) optimization.

As Chenhao Zhang and Wei Gao argue in Adaptive Rate Control and Rate-Distortion-Complexity Optimization for Dynamic Point Cloud Compression, we must treat computational cost as a primary constraint. This means building "slimmable" encoders that can automatically dial back their search depth when running on a smartphone versus a high-end server.

By treating complexity not as a fixed byproduct of a standard, but as a controllable variable, researchers like Frank Bossen and Karsten Sühring have shown in VVC Complexity and Software Implementation Analysis that even the most "expensive" standards can eventually achieve real-time performance through a combination of clever algorithmic shortcuts and hardware-aware design.

Papers in this version

Showing 60 of 83 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_balancing_compression_efficiency_and_com_bba5f1ad,
  title = {Balancing Compression Efficiency and Computational Complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/balancing-compression-efficiency-and-computational-complexity/rdr_bba5f1ade1dc4ec49b8a2b303183ff58},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_balancing_compression_efficiency_and_com_bba5f1ad_v1,
  title = {Balancing Compression Efficiency and Computational Complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/balancing-compression-efficiency-and-computational-complexity/rdr_bba5f1ade1dc4ec49b8a2b303183ff58/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}