AV1 Coefficient Scan Orders for Non-Square Blocks

In the AV1 video codec, coefficient scan orders for non-square transform blocks map two-dimensional quantized transform coefficients into a one-dimensional array for entropy coding. Rather than relying solely on traditional diagonal zigzag scanning, AV1 determines scan paths using pre-computed lookup tables optimized for specific aspect ratios, transform types, and sub-block groupings. This article explains how AV1 structures non-square transform sizes, organizes hierarchical sub-blocks, and applies pre-calculated scan tables to maximize compression efficiency.

Non-Square Block Dimensions in AV1

AV1 expands on previous standards by supporting extended non-square partition shapes and transform sizes. Non-square blocks exist in both 2:1 / 1:2 ratios (e.g., 4x8, 8x4, 8x16, 16x8, 16x32, 32x16, 32x64, 64x32) and 4:1 / 1:4 ratios (e.g., 4x16, 16x4, 8x32, 32x8, 16x64, 64x16).

Because non-square blocks exhibit asymmetric spatial correlations, residual energy is distributed unevenly between the horizontal and vertical frequency axes. High spatial frequency along the shorter dimension tends to have lower correlation, requiring specialized scan orders to group high-energy low-frequency coefficients together at the beginning of the entropy coding stage.

Sub-Block Hierarchical Scanning

To maintain hardware parsing throughput and minimize memory access overhead, AV1 processes transform blocks using a hierarchical sub-block scanning structure.

1. Sub-Unit Grouping: Blocks are divided into small, fixed-size coefficient clusters—predominantly 4x4 sub-blocks (or 2x2 and 4x2/2x4 groupings for blocks containing 2- or 4-pixel dimensions).
2. Inter-Sub-Block Scanning: The codec traverses across the sub-blocks in a defined sequence based on the dominant dimension of the block. For example, a wide horizontal block (such as 16x4) traverses sub-blocks along the horizontal axis differently than a tall vertical block (such as 4x16).
3. Intra-Sub-Block Scanning: Within each 4x4 sub-block, individual frequency bins are scanned using a localized pattern that mirrors the local energy concentration.

Role of Transform Type Combinations

Scan orders are coupled with the two-dimensional separable transform types applied to the block. AV1 pairs independent 1D horizontal and vertical transforms, which include:

• Discrete Cosine Transform (DCT)
• Asymmetric Discrete Sine Transform (ADST)
• Flipped ADST (FLIPADST)
• Identity Transform (IDTX)

The specific combination of horizontal and vertical transforms influences where the energy resides. For instance, pairing a 1D DCT horizontally with an Identity transform vertically creates strong directional clustering along the vertical axis. The scan order adapts to ensure that coefficients with the highest probability of non-zero values are evaluated first.

Static Pre-Computed Tables

Unlike codecs that dynamically derive scan orders at runtime through complex heuristics, AV1 uses static scan tables defined directly in the codec specification.

• Look-up Parameters: The scan table is indexed using two primary parameters: the transform block size (TxSize) and the transform kernel combination (TxType).
• Statistical Derivation: During the development of the AV1 format, these tables were derived offline using empirical training data. The probabilities of non-zero coefficients across millions of sample video frames were sorted by descending likelihood to establish an optimal traversal sequence for every supported non-square size and transform combination.

Reverse Direction Processing

Entropy coding in AV1 operates in reverse order. After identifying the End of Block (EOB) position—the index of the highest-frequency non-zero coefficient—the parser processes coefficients from the EOB backward toward the DC coefficient located at (0, 0). The predetermined scan order provides the exact coordinates for this reverse traversal, allowing the context modeling engine to efficiently track non-zero coefficient counts and zero-run lengths.