Significance map encoding and decoding using partition selection

What is this patent about?

’486 is related to the field of video data compression, specifically the entropy encoding and decoding of significance maps within transform units. In modern codecs like HEVC, significance maps identify the locations of non-zero coefficients after spectral transformation and quantization. Because these maps account for a massive portion of the total bitstream, efficient context-adaptive coding is required to estimate the probability of each bit accurately without overwhelming the processor with an excessive number of distinct contexts to track.

The underlying idea behind ’486 is that the statistical importance of coefficient positions in a transform block is not uniform, and therefore the allocation of coding contexts should not be uniform either. Instead of assigning a unique context to every single position or using a rigid grid, the invention uses a non-spatially-uniform partitioning strategy. By clustering more contexts in the high-energy upper-left region and grouping multiple positions into shared contexts in the lower-right region, the system achieves a better balance between modeling accuracy and the speed of context adaptation.

The claims of ’486 focus on a specific context assignment pattern for 4×4 transform units that optimizes the use of context-adaptive binary arithmetic coding. The independent claims define a partition set where each position in the upper-left quadrant is granted its own unique context to capture high-frequency detail. In contrast, the upper-right and lower-left quadrants utilize shared contexts for groups of two positions, while the entire lower-right quadrant—where non-zero coefficients are rarest—shares a single, unified context.

In practice, this mechanism allows the encoder and decoder to maintain fewer total contexts while focusing their statistical tracking resources where they matter most. When processing a block, the system determines the context for a specific bit position based on this predefined map, performs the arithmetic coding, and then updates that specific context’s probability state. This approach ensures that contexts in the lower-energy areas of the block receive enough data samples to converge on an accurate probability estimate, rather than remaining under-trained due to the sparsity of data in those regions.

This invention differs from prior approaches, such as H.264 or early HEVC drafts, which typically employed either a unique context for every position or a uniform grid-based grouping. By moving away from spatially uniform distribution, the ’486 patent reduces the computational overhead of tracking nearly a hundred different contexts across various block sizes. It specifically addresses the problem of context dilution, where having too many contexts for rarely-used positions leads to poor probability estimation and reduced compression efficiency.