AV1 16-Way Partitioning Rate-Distortion Optimization

This article examines how an AV1 video encoder evaluates rate-distortion (RD) curves across its 16-way block partitioning scheme. AV1 expands traditional quad-tree partitioning into a flexible recursive tree supporting square, rectangular, and non-symmetrical 1:4 and 4:1 aspect ratios. Encoders navigate this immense search space by computing Lagrangian cost functions across candidate splits, deploying variance and edge-detection heuristics, and using early termination strategies to select the optimal partition balance between compression efficiency and bit budget.

The 16-Way Partition Topology

AV1 extends the superblock architecture (typically 128x128 or 64x64 pixels) down to 4x4 blocks using 16 distinct partition configurations:

• None (PARTITION_NONE): The block remains undivided.
• Horizontal and Vertical Splits (PARTITION_HORZ, PARTITION_VERT): Divides the block into two equal 2:1 or 1:2 rectangles.
• Quad-Tree (PARTITION_SPLIT): Divides the block into four equal sub-quadrants.
• T-Shapes (HORZ_A, HORZ_B, VERT_A, VERT_B): Asymmetrical splits where one half is undivided and the other is split into two smaller blocks.
• Extended Aspect Ratios (HORZ_4, VERT_4): Divides the block into four 4:1 or 1:4 slivers, designed for fine horizontal or vertical textures.

Each split creates sub-blocks that can often be partitioned recursively, producing an exponential number of structural candidates for a single superblock.

The Rate-Distortion Optimization (RDO) Metric

To compare different partition options, the encoder projects candidate splits onto an RD curve using the Lagrangian formulation:

\[J = D + \lambda \cdot R\]

Where:

• \(J\) is the calculated RD cost.
• \(D\) represents distortion, typically measured as Sum of Squared Errors (SSE) between original and reconstructed pixels, or weighted by perceptual metrics.
• \(R\) represents the total rate, counting the bits required to signal partition metadata, prediction modes, motion vectors, and quantized transform coefficients.
• \(\lambda\) is the Lagrange multiplier derived from the frame's quantization parameter (QP). Higher \(\lambda\) values prioritize bit savings over fidelity (high-compression regimes), while lower values prioritize distortion reduction.

Bottom-Up vs. Top-Down RD Evaluation

Encoders evaluate RD curves across partition depths using recursive tree searches, typically functioning via a depth-first traversal:

1. Leaf Cost Evaluation: For any given partition candidate, the encoder tests candidate intra-prediction or inter-prediction modes, computes residual transforms, quantizes coefficients, and reconstructs the block to yield precise values for \(D\) and \(R\).
2. Aggregated Cost Summation: The cost of a partitioned block equals the sum of the RD costs of all its sub-blocks plus the bit cost needed to signal the partition syntax itself: \[J_{\text{split}} = \left( \sum_{i=1}^{N} J_{\text{sub\_block}_i} \right) + \lambda \cdot R_{\text{partition\_type}}\]
3. Direct Comparison: The aggregate cost \(J_{\text{split}}\) is compared against the undivided parent cost \(J_{\text{none}}\). If a split configuration yields a lower \(J\), the encoder adopts the split branch on the RD curve.

Pruning the 16-Way Search Space

An exhaustive evaluation of all 16 partition types across every depth level is computationally prohibitive for real-time and near-real-time encoding. Production encoders like SVT-AV1 and libaom implement aggressive pruning to evaluate only the most viable points on the RD curve:

• Spatial Variance and Edge Direction: If spatial gradient analysis reveals high horizontal variance and low vertical variance, the encoder prioritizes horizontal splits (HORZ, HORZ_4, HORZ_A/B) and prunes vertical candidates before running full transform and quantization pipelines.
• Early Termination via Split Cost Tracking: If the RD cost of an undivided block (PARTITION_NONE) falls below a dynamic threshold determined by neighboring blocks, the encoder skips evaluating deeper 4-way and 16-way splits. Conversely, if PARTITION_SPLIT yields an RD cost substantially lower than PARTITION_NONE, non-split branches at that depth are discarded immediately.
• Machine Learning Classifiers: Encoders deploy lightweight neural networks and decision trees trained on historical video datasets. These models predict the probability of 1:4, 4:1, and T-split utility based on motion vector consistency and residual energy, bypassing full RD loop calculations for low-probability topologies.
• Staged RDO: Instead of running full entropy coding on every partition candidate, encoders use fast estimators (such as Hadamard transform domain distortion and estimated bit-rates) in early stages. Only the top-ranking candidates proceed to the full, computationally expensive RD evaluation stage.