Rate-Distortion Optimized Quantization in AV1

Rate-distortion optimized quantization (RDOQ) in the AV1 video codec is an advanced decision-making process that optimizes transform coefficient levels to achieve the best possible balance between compression efficiency and visual quality. Rather than relying on static scalar rounding during quantization, RDOQ treats quantization as an optimization problem, testing multiple candidate values for each transform coefficient against a mathematical cost function. This overview explains how AV1 formulates rate-distortion costs, evaluates candidate levels, optimizes coefficient runs, and integrates entropy modeling to maximize coding performance.

The Objective: Minimizing Lagrangian Cost

Standard quantization scales transformed frequency coefficients by a quantization step size and rounds them to the nearest integer. While computationally fast, this scalar rounding ignores the exact bit cost required to signal the resulting value.

RDOQ overcomes this limitation by minimizing the Lagrangian cost function:

\[J = D + \lambda R\]

• \(J\) (Cost): The overall cost to be minimized.
• \(D\) (Distortion): The reconstruction error introduced by quantization, typically calculated as the Sum of Squared Errors (SSE) between the original and reconstructed coefficients in either the frequency or spatial domain.
• \(R\) (Rate): The exact number of bits required by the entropy coder to signal the quantized coefficient, sign, and structural flags.
• \(\lambda\) (Lambda): The Lagrange multiplier, which determines the trade-off between bitrate and distortion based on the frame's quantization parameter (QP).

Candidate Selection and Trellis Search

AV1 applies RDOQ across its diverse transform set, which includes traditional Discrete Cosine Transforms (DCT), Asymmetric Discrete Sine Transforms (ADST), and Identity transforms in block sizes ranging from 4x4 up to 64x64.

For each transform coefficient, RDOQ evaluates a small set of candidate integer levels rather than accepting a fixed rounded value:

1. The floor value \(\lfloor x \rfloor\)
2. The ceiling value \(\lceil x \rceil\)
3. Zero (testing whether completely dropping the coefficient reduces the bit cost enough to justify the added distortion)

Because the bit cost of a given coefficient depends on surrounding coefficients and the end-of-block (EOB) position, AV1 uses dynamic programming (trellis coding) or a reverse-scan search. The algorithm typically processes coefficients in reverse scan order (from high-frequency to low-frequency components). This reverse pass allows the encoder to accurately evaluate the impact of shifting the EOB marker earlier in the block, which can save substantial bit overhead by truncating trailing zeros.

Entropy Coding Integration

AV1 uses a multi-symbol arithmetic coding engine. The bit cost \(R\) cannot be accurately estimated using fixed-length tables; it depends heavily on context models. During RDOQ, the encoder tracks:

• EOB Position: The bit savings achieved if all subsequent coefficients in the scan order are set to zero.
• Coefficient Magnitude: The probabilities associated with specific syntax elements, including base_eob_extra, coeff_base, and coeff_br (base ranges for absolute values).
• Sign Bits: The cost of coding the sign of non-zero coefficients.
• Context Modeling: How choosing a specific level for one coefficient updates the context for neighboring and subsequent coefficients.

By evaluating the arithmetic coder's probabilities during the search, the algorithm calculates the exact bit penalty \(R\) for each candidate level.

Decision and Coefficient Updating

Once distortion \(D\) and rate \(R\) are computed for each candidate level, the encoder computes \(J\). The candidate that produces the lowest cost \(J\) is selected as the final quantized coefficient.

Common outcomes of this optimization include:

• Coefficient Dropping: High-frequency coefficients with high bit costs but minimal visual impact are rounded down to zero.
• Level Adjustment: Coefficients are shifted by \(\pm 1\) if the lower rate cost outweighs the minor increase in distortion.
• Early Truncation: Entire high-frequency tails of transform blocks are zeroed out, substantially lowering block overhead.

Complexity Management in AV1 Encoders

Full trellis-based RDOQ is computationally demanding. Production AV1 encoders, such as libaom and SVT-AV1, employ selective RDOQ strategies based on preset speeds:

• Full RDOQ: Evaluates all candidate levels and accurate entropy contexts across all transform blocks, typically reserved for slow, archival-quality presets.
• Fast/Pruned RDOQ: Skips candidates based on early-termination heuristics, limits RDOQ to luma channels or lower-frequency coefficients, or uses look-up tables to approximate bit costs instead of querying the arithmetic coder directly.