AV1 Palette Map Run-Length Coding Explained

This article provides an overview of the run-length coding (RLC) mechanism utilized in the AV1 video codec for palette map transmission. When encoding screen content or computer-generated graphics, AV1 uses palette mode to represent pixel blocks using a small set of representative colors. To minimize the bitstream overhead of transmitting pixel-by-pixel color assignments, AV1 applies a specialized, context-adaptive run-length coding scheme along a directional scan path.

Palette Mode and Scan Direction

In AV1, palette mode is an intra-prediction tool applied to blocks with a limited number of unique colors (up to eight colors per plane). Once a palette table containing these base colors is signaled, each pixel in the block is mapped to a palette index.

Instead of transmitting the map in standard two-dimensional coordinates, the encoder serializes the block into a one-dimensional sequence. The scanning order is chosen dynamically—either horizontal or vertical raster scan—depending on the block's aspect ratio and intra-prediction characteristics, ensuring maximum continuity among identical indices.

The Run-Length Mechanism

AV1 reduces index redundancy by grouping consecutive identical palette indices into "runs." The map transmission proceeds as follows:

1. Index Signaling: The encoder transmits the palette index for the current pixel position.
2. Run Value Signaling: Following the index, a run-length value is transmitted. This value specifies how many subsequent consecutive pixels along the scan path share the exact same palette index.
3. Implicit Transitions: Once the decoded run of identical pixels concludes, the decoder expects a new palette index for the next pixel, which cannot be identical to the index of the run that just finished.

Dynamic Range and Context Modeling

To achieve high compression efficiency, the run-length representation is tightly constrained and entropy-coded:

• Dynamic Alphabets: The maximum possible run length is dynamically bounded by the number of remaining unprocessed pixels in the coding block. The entropy coder adapts to this maximum, eliminating the signaling of impossible run values.
• Context-Adaptive Arithmetic Coding: Run lengths are coded using AV1's multi-symbol arithmetic coder. Probability models (CDFs) are selected using contexts derived from the palette size, the position within the block, and the index being repeated. Lower indices, which correspond to more frequent colors, typically feature different statistical run profiles than higher indices.

By transmitting index-run pairs rather than individual sample values, AV1 drastically reduces the bitrate required for text, user interfaces, and flat graphic content.