To compress an image or a video frame, an encoder must answer a fundamental question: How should this image be broken down into smaller pieces to describe it most efficiently?
Modern video coding standards like HEVC, VP9, and VVC achieve state-of-the-art compression by recursively partitioning frames into hierarchical blocks. For example, VVC introduces the Quadtree with Multi-Type Tree (QTMT) structure, which allows blocks to be split not just into four squares, but vertically or horizontally into halves (binary splits) or thirds (ternary splits).
To find the absolute best way to partition a frame, traditional encoders rely on a brute-force approach called Rate-Distortion Optimization (RDO). For every single possible block split and prediction mode, the encoder compresses the pixels, calculates the distortion ($D$), measures the generated bitrate ($R$), and evaluates the Lagrangian cost:
$$J = D + \lambda R$$
The encoder then selects the configuration that minimizes $J$. As noted by Jar‐Ferr Yang et al., this exhaustive search creates a massive computational bottleneck. The combinatorial explosion of testing every possible sub-block shape and prediction direction makes real-time encoding on standard hardware virtually impossible.
The Diminishing Returns of Brute Force
Why is the exhaustive search space so inefficient? If a block can be split in multiple ways, and each sub-block can be recursively split further, the number of combinations grows exponentially. Compounding this, for each potential partition, the encoder must evaluate dozens of prediction modes (such as the 65+ directional intra-prediction modes in VVC).
Yiqun Liu demonstrated the sheer scale of this inefficiency by disabling early-exit heuristics in the VVC Test Model to measure the maximum search space. The results revealed that exploring every single combination increased computational complexity by over 130%, yet improved the final rate-distortion trade-off by less than 1%.
Exhaustive RDO Search Space:
[Root Block]
├── No Split ──> Evaluate Modes (Cost J1)
├── Quad Split ──> [4 Sub-blocks] ──> Recursive Search...
├── Horizontal Binary Split ──> [2 Sub-blocks] ──> Recursive Search...
└── Vertical Ternary Split ──> [3 Sub-blocks] ──> Recursive Search...
(Repeated for billions of combinations per frame)
This insight forms the foundation of modern fast-encoding research: the vast majority of the RDO search space consists of low-yield configurations that are rarely chosen as optimal. If an encoder can predict which block structures are unlikely to be chosen, it can prune those paths entirely, bypassing the expensive reconstruction and entropy coding loops.
Statistical and Analytical Pruning
The earliest and most hardware-friendly solutions to this bottleneck rely on extracting lightweight mathematical properties from the raw pixels before running RDO. If the encoder can deduce the texture or complexity of a block upfront, it can terminate the recursive search tree early.
For instance, Yunyu Shi et al. introduced a "Quasi-Zero-Block" detection method for HEVC. By identifying blocks with negligible high-frequency information early in the pipeline, their algorithm skips redundant recursive transform unit (TU) searches, cutting processing time by over 50% with an imperceptible loss in video quality.
Texture orientation can also be mapped directly to prediction modes without testing each one. Encoders can use discrete cosine transforms (DCT) or directional gradients to narrow down dozens of spatial prediction modes to a small handful of likely candidates. Similarly, Junan Chen et al. utilized pixel variance and Sobel gradients to analyze texture complexity in VVC. If a region is highly uniform, it is mathematically highly unlikely to benefit from complex ternary or binary splits. By using a multi-step decision logic to prune these uniform regions, the authors bypassed exhaustive brute-force searches and cut encoding time by nearly half.
Deep Learning as a Direct Mapping Function
While hand-crafted statistical heuristics work well for simple block structures, they struggle to scale to the highly flexible, non-square partitioning schemes of newer codecs. The modern frontier of compression research replaces these heuristics with deep learning models that treat partition selection as a direct classification or segmentation task.
Instead of iteratively calculating the RDO cost at every single level of a partition tree, a neural network can look at the pixel intensities of a large block once and output its predicted final structure.
Predictive Pipeline:
[Raw Pixels] ──> [Lightweight CNN / U-Net] ──> [Predicted Partition Map] ──> Targeted RDO (Save >50% Time)
Hierarchical and Structural Predictions
To accelerate VP9 and HEVC encoders, early deep learning approaches used convolutional neural networks (CNNs) to predict whether a coding unit should split or merge. Tianyi Li et al. extended this to VVC with DeepQTMT, a multi-stage deep learning framework that predicts complex square and rectangular block partitions, reducing intra-mode encoding time by up to 67%. Rather than making a sequence of binary decisions at each level of the partition tree, Yixiao Li et al. framed the block partition problem as a single multi-class classification task, using a combination of a bagged tree and a ResNet to predict the final structure of a block in one step.
Integrating Quantization Context
A major challenge in using neural networks for video encoding is that the optimal partition structure is not purely a function of the input pixels; it also depends heavily on the target bitrate. When the Quantization Parameter (QP) is high, the encoder smooths out fine details to save bits, meaning larger block sizes become optimal.
To bridge this gap, Zhao Zan et al. integrated a "QP fusion network" into a U-Net framework. By feeding the quantization level alongside the visual features into the network, the model dynamically adjusts its partition predictions based on the compression constraints, achieving a 68.76% encoding speedup.
Why It Works: The Pareto Frontier
Predictive RDO works because video texture, motion, and residual data exhibit massive spatial and temporal correlations. A brute-force encoder spends the majority of its time confirming what basic statistics or a trained neural network can infer instantly: smooth skies do not need intricate sub-block partitions, and sharp edges follow predictable geometric lines.
The success of these methods is evaluated using the Bjontegaard Delta Bitrate (BD-rate), which measures the percentage of extra bitrate required to maintain the same subjective visual quality. Across the literature, substituting exhaustive RDO with predictive models consistently demonstrates that encoders can eliminate 50% to 75% of their computational overhead while incurring a BD-rate penalty of less than 1%. By trading an imperceptible fraction of compression efficiency for orders-of-magnitude faster processing, predictive partitioning transforms advanced video codecs from theoretical standards into deployable, real-time technologies.
Key Foundational Work
Advanced Video Technologies and Applications for H.264/AVC and Beyond (2006) — contributed 2 concept elements to this direction.
Low-Complexity Adaptive Block-Size Transform Based on Extended Transforms (2006) — contributed 1 concept elements to this direction.