Multi-level significance maps for encoding and decoding

What is this patent about?

’849 is related to the field of video data compression, specifically focusing on the efficient entropy coding of significance maps within large transform units. In modern video standards like HEVC, significance maps identify the locations of non-zero coefficients, but as transform blocks grow to 16x16 or 32x32, the computational cost of determining contexts for every individual flag becomes a significant bottleneck for memory bandwidth and processing speed.

The underlying idea behind ’849 is to implement a multi-level hierarchy for significance maps by partitioning a large transform unit into smaller, non-overlapping blocks or groups. By first signaling a high-level flag for each group to indicate whether it contains any non-zero data, the system can bypass the processing of entire clusters of zero-value coefficients. This hierarchical approach reduces the total number of flags that must be entropy-encoded and allows the decoder to skip memory-intensive context lookups for empty regions of the transform unit.

The claims of ’849 focus on a method and apparatus for reconstructing these flags using a specific inference logic to further save bits. The system decodes a group-level flag and, if non-zero, proceeds to decode individual coefficient flags within that group; however, it includes a mechanism to infer the value of the final flag in a group. Specifically, if a group is known to be non-empty but all previously scanned flags in that group are zero, the decoder automatically infers that the remaining flag at the group's starting position must be one, thereby omitting it from the bitstream.

In practice, the invention operates by scanning the transform unit in a prescribed order, such as a reverse diagonal scan, to identify the last significant coefficient. The encoder uses rate-distortion optimized quantization to decide if certain groups should be entirely zeroed out to improve compression efficiency. During decoding, the system utilizes neighbor-based context modeling—looking at the status of groups to the right and below—to predict the probability of the current group containing non-zero coefficients, which streamlines the arithmetic coding process.

This approach differs from prior methods by moving away from a flat, single-level significance map where every coefficient position requires a dedicated context and bit. By introducing the significant-coefficient-group flag, the invention effectively compresses the map itself. The specific inference rule for the (0,0) position within a group ensures that the bitstream never carries redundant information for groups already proven to be non-zero, providing a leaner data structure for high-resolution video streams.