Multi-level significance map scanning
Methods of encoding and decoding for video data are described in which multi-level significance maps are used in the encoding and decoding processes. The significant-coefficient flags that form the significance map are grouped into contiguous groups, and a significant-coefficient-group flag signifies for each group whether that group contains no non-zero significant-coefficient flags. A multi-level scan order may be used in which significant-coefficient flags are scanned group-by-group. The group scan order specifies the order in which the groups are processed, and the scan order specifies the order in which individual significant-coefficient flags within the group are processed. The bitstream may interleave the significant-coefficient-group flags and their corresponding significant-coefficient flags, if any.
1. A method, at a decoder, of reconstructing significant-coefficient flags for a transform unit, wherein the transform unit comprises non-overlapping blocks of transform coefficients, each of the non-overlapping blocks corresponds to a respective group of significant-coefficient flags, each significant-coefficient flag corresponds to a respective transform coefficient, and each respective group corresponds to a respective significant-coefficient group flag, groups of significant-coefficient flags are reconstructed in a group scan order, and significant-coefficient flags are reconstructed in a scan order within their group, the method comprising:
decoding a position for a last-significant coefficient of the transform unit from a bitstream of encoded data;
in a first group corresponding to the position of the last-significant coefficient, decoding from the bitstream each significant-coefficient flag in the scan order from a position following the position of the last-significant coefficient in the scan order through position (0,0) of the first group;
for each group in the group scan order from a second group, which follows the first group in the group scan order, to a group preceding a DC group in the group scan order, wherein the DC group corresponds to a block containing a transform coefficient at the (0,0) position of the transform unit,
decoding a significant-coefficient-group flag from the bitstream for that group, and
reconstructing significant-coefficient flags in that group in a scan order within that group, by, for each significant-coefficient flag in that group,
if that significant-coefficient flag is at position (0,0) in its group, its corresponding significant-coefficient-group flag is decoded to be non-zero, and all of the significant-coefficient flags which precede that significant-coefficient flag in the scan order in that group are zero, then inferring, without decoding from the bitstream, that significant-coefficient flag to be 1, and
otherwise
decoding that significant-coefficient flag from the bitstream if that significant-coefficient flag is in a group that has corresponding significant-coefficient-group flag that is non-zero, and
inferring, without decoding from the bitstream, that significant-coefficient flag to zero, if that significant-coefficient flag is in a group that has corresponding significant-coefficient-group flag that is zero; and
in the DC group, decoding each corresponding significant-coefficient flag in the scan order.
2. The method claimed in claim 1 , wherein the group scan order is one of horizontal, vertical, or diagonal.
3. The method claimed in claim 1 , wherein the scan order is one of horizontal, vertical, or diagonal.
4. The method claimed in claim 1 , wherein the significant-coefficient flags of a next one of the respective groups are reconstructed only after all significant-coefficient flags of all groups earlier in the group scan order are reconstructed.
5. The method claimed in claim 1 , further comprising reconstructing a significant-coefficient-group flag for the first group by inferring, without decoding from the bitstream, the significant-coefficient group flag for the first group to be 1.
6. The method claimed in claim 1 , further comprising reconstructing a significant-coefficient-group flag for the DC group by inferring, without decoding from the bitstream, the significant-coefficient group flag for the DC group to be 1.
7. The method claimed in claim 1 , wherein the blocks are contiguous square blocks.
8. The method claimed in claim 1 , wherein decoding at least one of the significant-coefficient-group flags includes determining a context for that significant-coefficient-group flag based on significant-coefficient-group flags decoded for two neighbor groups.
9. A decoder which reconstructs significant-coefficient flags for a transform unit, wherein the transform unit comprises non-overlapping blocks of transform coefficients, each of the non-overlapping blocks corresponds to a respective group of significant-coefficient flags, each significant-coefficient flag corresponds to a respective transform coefficient, and each respective group corresponds to a respective significant-coefficient group flag, groups of significant-coefficient flags are reconstructed in a group scan order, and significant-coefficient flags are reconstructed in a scan order within their group, the decoder comprising:
a processor;
a memory; and
a decoding application stored in memory and containing instructions for configuring the processor to:
decode a position for a last-significant coefficient of the transform unit from a bitstream of encoded data;
in a first group corresponding to the position of the last-significant coefficient, decode from the bitstream each significant-coefficient flag in the scan order from a position following the position of the last-significant coefficient in the scan order through position (0,0) of the first group;
for each group in the group scan order from a second group, which follows the first group in the group scan order, to a group preceding a DC group in the group scan order, wherein the DC group corresponds to a block containing a transform coefficient at a (0,0) position of the transform unit,
decode a significant-coefficient-group flag from the bitstream for that group, and
reconstruct significant-coefficient flags in that group in a scan order within that group, by, for each significant-coefficient flag in that group,
if that significant-coefficient flag is at position (0,0) in its group, its corresponding significant-coefficient-group flag is decoded to be non-zero, and all of the significant-coefficient flags which precede that significant-coefficient flag in the scan order in that group are zero, then inferring, without decoding from the bitstream, that significant-coefficient flag to be 1, and
otherwise
decoding that significant-coefficient flag from the bitstream if that significant-coefficient flag is in a group that has corresponding significant-coefficient-group flag that is non-zero, and
inferring, without decoding from the bitstream, that significant-coefficient flag to zero, if that significant-coefficient flag is in a group that has corresponding significant-coefficient-group flag that is zero; and
in the DC group, decode each corresponding significant-coefficient flag in the scan order.
10. The decoder claimed in claim 9 , wherein the group scan order is one of horizontal, vertical, or diagonal.
11. The decoder claimed in claim 9 , wherein the scan order is one of horizontal, vertical, or diagonal.
12. The decoder claimed in claim 9 , wherein the processor is configured to reconstruct significant-coefficient flags of a next one of the respective groups only after all significant-coefficient flags of all groups earlier in the group scan order are reconstructed.
13. The decoder claimed in claim 9 , wherein the processor is further configured to reconstruct a significant-coefficient-group flag for the first group by inferring, without decoding from the bitstream, the significant-coefficient group flag for the first group to be 1.
14. The decoder claimed in claim 9 , wherein the processor is further configured to reconstruct a significant-coefficient-group flag for the DC group by inferring, without decoding from the bitstream, the significant-coefficient group flag for the DC group to be 1.
15. The decoder claimed in claim 9 , wherein the blocks are contiguous square blocks.
16. The decoder claimed in claim 9 , wherein the processor is configured to decode at least one of the significant-coefficient-group flags by determining a context for that significant-coefficient-group flag based on significant-coefficient-group flags decoded for two neighbor groups.
17. A non-transitory processor-readable medium storing processor-executable instructions for a decoder which reconstructs significant-coefficient flags for a transform unit, wherein the transform unit comprises non-overlapping blocks of transform coefficients, each of the non-overlapping blocks corresponds to a respective group of significant-coefficient flags, each significant-coefficient flag corresponds to a respective transform coefficient, and each respective group corresponds to a respective significant-coefficient group flag, groups of significant-coefficient flags are reconstructed in a group scan order, and significant-coefficient flags are reconstructed in a scan order within their group, the processor-executable instructions, when executed, configuring one or more processors to:
decode a position for a last-significant coefficient of the transform unit from a bitstream of encoded data;
in a first group corresponding to the position of the last-significant coefficient, decode from the bitstream each significant-coefficient flag in the scan order from a position following the position of the last-significant coefficient in the scan order through the (0,0) position;
for each group in the group scan order from a second group, which follows the first group in the group scan order, to a group preceding a DC group in the group scan order, wherein the DC group corresponds to a block containing a transform coefficient at the (0,0) position of the transform unit,
decode a significant-coefficient-group flag from the bitstream for that group, and
reconstruct significant-coefficient flags in that group in a scan order within that group, by, for each significant-coefficient flag in that group,
if that significant-coefficient flag is at position (0,0) in its group, its corresponding significant-coefficient-group flag is decoded to be non-zero, and all of the significant-coefficient flags which precede that significant-coefficient flag in the scan order in that group are zero, then inferring, without decoding from the bitstream, that significant-coefficient flag to be 1, and
otherwise
decoding that significant-coefficient flag from the bitstream if that significant-coefficient flag is in a group that has corresponding significant-coefficient-group flag that is non-zero, and
inferring, without decoding from the bitstream, that significant-coefficient flag to zero, if that significant-coefficient flag is in a group that has corresponding significant-coefficient-group flag that is zero; and
in the DC group, decode each corresponding significant-coefficient flag in the scan order.
18. The non-transitory processor-readable medium claimed in claim 17 , wherein the group scan order is one of horizontal, vertical, or diagonal.
19. The non-transitory processor-readable medium claimed in claim 17 , wherein the scan order is one of horizontal, vertical, or diagonal.
20. The non-transitory processor-readable medium claimed in claim 17 , wherein the processor-executable instructions configure the one or more processors to decode at least one of the significant-coefficient-group flags by determining a context for that significant-coefficient-group flag based on significant-coefficient-group flags reconstructed for two neighbor groups.