AV1 Palette Index Encoding with Multi-Symbol Entropy

The AV1 video codec utilizes palette prediction mode to efficiently compress screen content, computer graphics, and synthetic video blocks featuring sharp edges and low color variance. Rather than transmitting discrete transform coefficients or standard intra prediction modes, palette mode represents a block using a localized color lookup table paired with a 2D map of color indices. To maximize compression efficiency on this index map, AV1 deploys a multi-symbol entropy coder that leverages spatial neighborhood contexts and adaptive cumulative distribution functions (CDFs) to encode non-binary index values in single operations.

Palette Construction and Index Representation

When palette mode is selected for an intra-coded block, the encoder identifies up to eight dominant colors for the luma and chroma planes. Each color is placed in an ordered array known as the palette, with sizes ranging from 2 to 8 entries.

Once the palette is constructed, every pixel inside the block is assigned an integer index pointing to its corresponding palette color. Instead of treating these indices as independent values or splitting them across color planes, the indices form an index map representing the spatial geometry of the block. Compressing this index map requires signaling which index appears at each \((x, y)\) coordinate without transmitting excessive residual data.

Context Modeling via Spatial Neighbors

Neighboring pixels in natural and synthetic images exhibit high spatial correlation. In AV1, the color index of the current pixel is predicted using causal neighbors—specifically, the pixel immediately to the left (\(L\)) and the pixel immediately above (\(A\)).

The encoder evaluates the relationship between these neighbors to determine the context index for entropy coding:

• Neighbor Matching: The context model evaluates whether the top and left neighbors share the same palette index, whether they differ, or if one or both neighbors fall outside the block boundaries.
• Dominance Context: The system checks if the current candidate symbol matches the left neighbor's index, the top neighbor's index, or represents a distinct color index.

This context design groups pixels with similar local characteristics, ensuring that the probability distribution heavily skews toward the colors already established by adjacent pixels.

The Multi-Symbol Arithmetic Coding Engine

Unlike legacy codecs (such as H.264 or early HEVC implementations) that rely heavily on binary arithmetic coding engines requiring non-binary symbols to be decomposed into binary decision trees (binarization), AV1 uses an entropy coding engine derived from the Daala project. This engine processes \(N\)-ary alphabets directly.

Because a palette can contain up to eight colors, the alphabet size \(N\) for a palette index is between 2 and 8. The multi-symbol coder accepts an entire \(N\)-ary symbol directly alongside a corresponding 16-bit Cumulative Distribution Function (CDF). The CDF array represents the cumulative probabilities for each potential index:

\[\text{CDF}[i] = \sum_{j=0}^{i} P(\text{Index} = j)\]

By executing range updates against an \(N\)-ary CDF rather than cycling through multiple binary states, the decoder reduces computational dependencies and processes color indices with higher throughput.

Index Remapping and Transmission

To maximize the skew of the probability distributions in the multi-symbol engine, AV1 dynamically remaps the palette indices before entropy coding:

1. Neighbor-Based Ordering: Lower symbol values are prioritized for indices that match the causal neighbors. If the left and top neighbors have distinct indices, they are prioritized as the first candidates in the symbol alphabet.
2. Remaining Palette Indices: The remaining available indices from the palette are ordered systematically, usually in ascending order of their original palette placement.

Once the index is remapped to a localized symbol, the corresponding context model supplies an adaptive CDF configured for the current alphabet size. The multi-symbol arithmetic coder then reads or writes the symbol in a single arithmetic step.

Dynamic CDF Adaptation

AV1 maintains adaptation across the block to reflect changing local color statistics. After an index symbol is coded using a given context:

• The probability weights inside the associated CDF are updated using an adaptation factor (learning rate).
• Frequently occurring colors in the block gradually gain higher probability mass in the CDF, narrowing the bit interval allocated to them in the arithmetic coder.
• This continuous adaptation allows the engine to adjust dynamically when transitioning across different color regions within the same block, ensuring high coding efficiency without the need for manual distribution resets.