Trellis Quantization in AV1 Video Encoding

Trellis quantization is an optimization technique that improves video compression efficiency by evaluating the trade-off between visual distortion and bit consumption at the transform coefficient level. This article explains the core principles of Trellis quantization—commonly known as Rate-Distortion Optimized Quantization (RDOQ)—and details how it is specifically tailored to complement the multi-symbol entropy coding engine used in the AV1 video standard.

Fundamentals of Trellis Quantization

Standard scalar quantization divides transformed frequency coefficients by a step size and rounds them to the nearest integer. While computationally inexpensive, simple rounding ignores whether transmitting an altered coefficient value might save a significant number of bits at the cost of minimal reconstructed distortion.

Trellis quantization frames the quantization process as a graph-search problem solved using the Viterbi algorithm. Coefficients in a transformed block are ordered according to their scan sequence. For each coefficient, the algorithm evaluates multiple candidate quantization states (typically the floor and ceiling rounding values, or zero).

The optimal sequence of quantized levels is determined by minimizing a Lagrangian rate-distortion cost function:

\[J = D + \lambda R\]

Here, \(D\) represents the distortion (squared error between the original and reconstructed transform coefficients), \(R\) represents the rate (the number of bits required to signal that level in the bitstream), and \(\lambda\) is a Lagrange multiplier derived from the frame's quantization parameter (QP). The Trellis algorithm traverses the graph to find the minimum-cost path through the block.

AV1 Entropy Coding Architecture

To understand how Trellis quantization is customized for AV1, one must consider how AV1 signals transform coefficients. Unlike H.264 or HEVC, which rely heavily on binary arithmetic coding (CABAC), AV1 uses a non-binary, multi-symbol arithmetic coder derived from the Daala project. It leverages context-dependent Cumulative Distribution Functions (CDFs) that adapt dynamically as symbols are processed.

AV1 serializes transform blocks through a multi-layered syntax:

  1. End-of-Block (EOB): The index of the last non-zero coefficient in scan order.
  2. Base Levels: Binary flags indicating whether a coefficient is non-zero (base_eob or base_flag), and whether it exceeds lower magnitude thresholds.
  3. Levels and Signs: Intermediate magnitude flags followed by an Exp-Golomb remainder for large values, alongside sign bits.
  4. Context Dependency: The probability distribution of each flag depends on the position of the coefficient, the transform type, and the magnitudes of previously decoded neighboring coefficients.

Customizing Trellis Quantization for AV1

Because AV1’s entropy coder evaluates probabilities using multi-symbol CDFs and strict structural layers, Trellis quantization cannot use a generic bit-cost estimation. Encoders such as libaom and SVT-AV1 customize the algorithm in several critical ways:

1. Context-Accurate Rate Estimation

The rate term (\(R\)) in the cost function must match the true cost of AV1’s entropy engine. For every candidate level at every node in the trellis, the algorithm queries the active CDF context tables. This includes estimating the cost of the base-level flags, intermediate level flags, sign bits, and potential Golomb-coded tails. Because neighboring reconstructed coefficients define the context for subsequent coefficients, the Trellis graph tracks context transitions accurately across the scan path.

2. EOB Position Optimization

In AV1, signaling the EOB token incurs a distinct bit cost, but it eliminates the need to signal any subsequent coefficients. AV1-tailored Trellis algorithms explicitly evaluate candidate EOB positions. The encoder tests whether truncating trailing high-frequency coefficients to zero reduces the overall cost \(J\), balancing the increased distortion of dropping those coefficients against the substantial rate reduction of an earlier EOB.

3. Handling Non-Binary Transitions

Traditional Trellis implementations designed for binary coders evaluate simple transitions. For AV1, candidate states must model the multi-symbol nature of the syntax. The search space is structured around AV1's specific magnitude thresholds (e.g., levels 0, 1, 2, and beyond), ensuring that probabilities assigned to compound multi-symbol tokens reflect actual syntax generation rather than generic approximations.

4. Transform-Specific Scan Orders

AV1 supports a wide variety of transform kernels (DCT, Asymmetric Discrete Sine Transforms, and Identity transforms) across rectangular and square block sizes ranging from 4x4 to 64x64. Trellis quantization paths are aligned with the custom scan patterns of each transform type, ensuring that the dependency chain used for neighbor context modeling matches the exact traversal order of the decoder.