Significance map encoding and decoding using partition selection

What is this patent about?

’801 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, and their efficient coding is critical because they represent a substantial portion of the total bitstream. Traditional approaches often use uniform context assignment, which can lead to inefficient probability estimation when data is sparse in certain regions of the transform block.

The underlying idea behind ’801 is that the statistical distribution of significant coefficients is not uniform across a transform block, and therefore the assignment of coding contexts should not be uniform either. By employing a non-spatially-uniform partitioning of the significance map, the invention ensures that high-frequency areas with sparse data share contexts to accelerate probability convergence, while low-frequency areas with dense data use more granular contexts. This balancing act optimizes the trade-off between the accuracy of the probability model and the speed at which the model adapts to local data statistics.

The claims of ’801 focus on a specific context-adaptive decoding method for 4×4 transform units where the significance map is divided into distinct zones of varying context density. The upper-left quadrant is assigned unique contexts for every bit position to capture high-detail variations, while the upper-right and lower-left quadrants use shared contexts for groups of two positions. Finally, the lower-right quadrant, which typically contains the least amount of significant data, collapses all bit positions into a single shared context to maximize the data available for updating that specific probability model.

In practice, the system determines the appropriate context for each bit position by looking up its location within a predefined partition set before performing binary arithmetic decoding. As each bit is reconstructed, the associated context is immediately updated, allowing the decoder to refine its probability estimates in real-time. The invention also contemplates dynamic partition switching, where the codec can transition from a coarse partition set to a more refined one mid-slice if the amount of encoded data exceeds a specific threshold, ensuring the model complexity matches the data volume.

This approach differs from prior solutions by moving away from rigid, uniform grids that often waste computational resources on tracking underutilized contexts in high-frequency regions. By grouping bit positions based on their likelihood of containing non-zero coefficients, the invention achieves higher compression efficiency with a reduced context memory footprint. Furthermore, the grouping of contexts allows for optimized hardware implementations where scan orders can be reconfigured to process multiple bits sharing the same context in a single clock cycle, significantly increasing throughput.