Multi-level significance maps for encoding and decoding

What is this patent about?

’597 is related to the field of video data compression, specifically focusing on the efficient entropy encoding and decoding of significance maps within large transform units. In modern codecs like HEVC, significance maps identify the positions of non-zero coefficients, but as transform units scale to 16x16 or 32x32, the computational cost of determining contexts for individual flags and the bitstream overhead for sparse data become significant bottlenecks.

The underlying idea behind ’597 is the implementation of a multi-level hierarchy for significance maps that allows the decoder to skip entire regions of zero-value coefficients. By partitioning a transform unit into smaller, non-overlapping sub-blocks and assigning a significant-coefficient-group flag to each, the system can signal the presence or absence of data at a macro level. This hierarchical approach reduces memory bandwidth requirements and improves throughput by avoiding the bit-by-bit processing of empty regions.

The claims of ’597 focus on a specific decoding mechanism that utilizes spatial dependencies to determine the context for these group flags. The decoder evaluates the flags of blocks immediately to the right and below the current block to select a context model, switching between a first and second context based on whether those neighbors are zero. Furthermore, the claims specify a logic gate where, if a group is flagged as containing non-zero data but all other flags in that group have been decoded as zero, the final flag is inferred to be one without being explicitly read from the bitstream.

In practice, the invention works by first decoding the position of the last significant coefficient and then scanning the higher-level group flags in a prescribed order. If a group flag is zero, the decoder automatically fills the corresponding coefficient positions with zeros. If the flag is one, the decoder proceeds to decode individual coefficient flags, utilizing a rate-distortion optimized quantization (RDOQ) process at the encoder to ensure that the decision to signal a group as significant is mathematically justified by the balance of bit-rate and visual fidelity.

This approach differs from prior methods that relied on computationally expensive neighbor-based context derivation for every single coefficient flag in a large block. By shifting the context dependency to the group level and allowing for inferred flag values, the invention reduces the number of costly memory access operations. It effectively streamlines the processing of sparse high-frequency data, which is common in high-definition video residuals, leading to more efficient hardware and software decoder implementations.