Significance map encoding and decoding using partition selection

What is this patent about?

’885 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 compression is vital as they represent a substantial portion of the total bitstream. Traditional methods often utilize uniform context modeling, which may not optimally account for the statistical distribution of coefficients across a block.

The underlying idea behind ’885 is that the probability distribution of significant coefficients is not spatially uniform, and therefore, the assignment of contexts should be non-uniform to balance accuracy with adaptivity. By using a non-spatially-uniform partitioning of the significance map, the invention ensures that high-frequency areas with sparse data share contexts to speed up probability convergence, while low-frequency areas with dense data use more granular contexts. This approach prevents the “dilution” of context statistics in regions where non-zero coefficients are rarely encountered.

The claims of ’885 focus on a decoding method and apparatus that reconstructs a significance map by assigning contexts based on a specific quadrant-based partition set. The independent claims require that the upper-left quadrant of the map assigns unique contexts to each bit position, while the upper-right and lower-left quadrants utilize shared contexts among groups of bits. Finally, the lower-right quadrant, where coefficients are least likely to be significant, assigns a single shared context to the majority of its bit positions.

In practice, the system determines the appropriate context for each bit position by looking up its coordinates within a predefined partition map, such as a 4x4 or 8x8 grid. As the decoder processes each significant coefficient flag, it uses the assigned context to interpret the bitstream and then immediately updates that context’s state to reflect the observed data. This allows the probability models to evolve dynamically during the decoding of a single slice, improving the compression ratio for both luma and chroma components.

This invention differs from prior approaches by moving away from rigid, one-to-one context mapping or perfectly symmetrical sub-block partitioning. By clustering bit positions in the bottom-right high-frequency region into a single context, the invention reduces the total number of contexts the hardware must track and update. This reduction in context overhead, combined with the ability to switch between coarse and fine partition sets based on slice size or quantization parameters, results in a more efficient and hardware-friendly entropy coding engine.