Multi-level significance maps for encoding and decoding

What is this patent about?

’945 is related to the field of video data compression, specifically the entropy encoding and decoding of transform coefficients. In modern video standards like HEVC, residual data is converted into spectral coefficients and represented by a significance map, which indicates the locations of non-zero values. As transform units grow to sizes like 16x16 or 32x32, the computational overhead of managing individual coefficient contexts and the bit-rate cost of signaling sparse maps become significant bottlenecks for efficient processing.

The underlying idea behind ’945 is the implementation of a multi-level significance map that groups individual coefficient flags into larger contiguous blocks. By creating a higher-level hierarchy, the system can use a single flag to signal whether an entire group of coefficients contains any non-zero values. This allows the encoder to skip the signaling of individual flags for empty regions of a transform unit, drastically reducing the number of memory accesses required for context modeling and improving the overall compression ratio for sparse high-frequency data.

The claims of ’945 focus on a method for optimizing the encoding process using rate-distortion optimized quantization (RDOQ) applied at the group level. The encoder evaluates the cost-benefit of zeroing out an entire coefficient group by comparing the bit-rate savings against the resulting image distortion. The independent claims specifically protect the mechanism of fixing the last significant coefficient's position and then iteratively testing whether modifying a group to be entirely zero improves the rate-distortion cost, subsequently updating the group-level flags accordingly.

In practice, the invention partitions a large transform unit into smaller sub-blocks, such as 4x4 groups. During the encoding pass, the system generates a significant-coefficient-group flag for each sub-block. If a group is determined to be empty—either because it contains no data or because the RDOQ process decided zeroing it was more efficient—the encoder simply writes a '0' for that group. The decoder then reads this high-level flag and, seeing a zero, automatically fills the corresponding area with zeros without needing to parse individual coefficient bits from the stream.

This approach differs from prior methods that relied on complex, computationally expensive context derivations based on the immediate neighbors of every single coefficient. By shifting the focus to a hierarchical signaling structure, the invention reduces the dependency on local memory lookups and provides a more flexible way to handle large transform blocks. Furthermore, the integration of RDOQ at the group level allows the encoder to make smarter decisions about which data is visually essential, rather than treating every non-zero coefficient as equally necessary to transmit.