Multi-level significance maps for encoding and decoding

1. A method for use in an encoder of an image to produce a bitstream of compressed image data, the encoder generating a transform unit from the image, the transform unit including transform coefficients, wherein the transform unit is represented by a significance map containing a significant-coefficient flag for each transform coefficient, and wherein the significance map is partitioned into a plurality of coefficient groups, each coefficient group having an associated significant-coefficient-group flag indicating whether its coefficient group contains at least one non-zero significant-coefficient flag, the method comprising:

for one of the coefficient groups containing at least one non-zero significant-coefficient flag,

determining, using rate-distortion optimized quantization, that said one of the coefficient groups is to be modified to contain all zero significant-coefficient flags, wherein determining includes determining a rate cost associated with encoding the significant-coefficient-group flags, the significant-coefficient flags, and remaining level information for the transform unit and a distortion based on modifying at least one transform coefficient in said one of the coefficient groups to be zero;

based on that determination, setting all significant-coefficient flags in that coefficient group to zero and setting its significant-coefficient-group flag to zero; and

entropy encoding the significant-coefficient-group flags and, for any coefficient groups having an associated significant-coefficient group flag that is non-zero, entropy encoding the significant-coefficient flags for those groups.

2. The method claimed in claim 1 , further including, prior to determining that said one of the coefficient groups is to be modified to contain all zero significant-coefficient flags,

applying a rate distortion optimization to the transform unit; and

adjusting a level of one or more transform coefficients based on the rate distortion optimization to produce a rate-distortion optimized transform unit, wherein the significant-coefficients of the significance map represent the locations of non-zero coefficients in the rate-distortion optimized transform unit.

3. The method claimed in claim 1 , further including first fixing the location of the last significant coefficient in a scan order in the transform unit, and excluding a last coefficient group containing the last significant coefficient from the rate-distortion optimized quantization.

4. The method claimed in claim 3 , further including testing, in a reverse scan order, each of the coefficient groups other than the last coefficient group and a first coefficient group in the scan order.

5. The method claimed in claim 1 , further including repeating the method, for the transform unit, using a different coefficient group size and selecting a coefficient group size that results in the most rate-distortion efficient bitstream.

6. The method claimed in claim 5 , further including inserting information in the bitstream indicating the selected coefficient group size.

7. An encoder for encoding an image to produce a bitstream of compressed image data, the encoder generating a transform unit from the image, the transform unit including transform coefficients, wherein the transform unit is represented by a significance map containing a significant-coefficient flag for each transform coefficient, and wherein the significance map is partitioned into a plurality of coefficient groups, each coefficient group having an associated significant-coefficient-group flag indicating whether its coefficient group contains at least one non-zero significant-coefficient flag, the encoder comprising:

a processor;

a memory; and

an encoding application stored in memory and containing instructions, which when executed, cause the processor to,

for one of the coefficient groups containing at least one non-zero significant-coefficient flag,

determine, using rate-distortion optimized quantization, that said one of the coefficient groups is to be modified to contain all zero significant-coefficient flags, wherein determining includes determining a rate cost associated with encoding the significant-coefficient-group flags, the significant-coefficient flags, and remaining level information for the transform unit and a distortion based on modifying at least one transform coefficient in said one of the coefficient groups to be zero;

based on that determination, set all significant-coefficient flags in that coefficient group to zero and setting its significant-coefficient-group flag to zero; and

entropy encode the significant-coefficient-group flags and, for any coefficient groups having an associated significant-coefficient group flag that is non-zero, entropy encode the significant-coefficient flags for those groups.

8. The encoder claimed in claim 7 , wherein the instructions, when executed, further cause the processor to, prior to determining that said one of the coefficient groups is to be modified to contain all zero significant-coefficient flags,

apply a rate distortion optimization to the transform unit; and

adjust a level of one or more transform coefficients based on the rate distortion optimization to produce a rate-distortion optimized transform unit, wherein the significant-coefficients of the significance map represent the locations of non-zero coefficients in the rate-distortion optimized transform unit.

9. The encoder claimed in claim 7 , wherein the instructions, when executed, further cause the processor to first fix the location of the last significant coefficient in a scan order in the transform unit, and exclude a last coefficient group containing the last significant coefficient from the rate-distortion optimized quantization.

10. The encoder claimed in claim 9 , wherein the instructions, when executed, further cause the processor to test, in a reverse scan order, each of the coefficient groups other than the last coefficient group and a first coefficient group in the scan order.

11. The encoder claimed in claim 7 , wherein the instructions, when executed, further cause the processor to repeat the method, for the transform unit, using a different coefficient group size and selecting a coefficient group size that results in the most rate-distortion efficient bitstream.

12. The encoder claimed in claim 11 wherein the instructions, when executed, further cause the processor to insert information in the bitstream indicating the selected coefficient group size.

13. A non-transitory processor-readable medium storing processor-executable instructions which, when executed, configures one or more processors to encode an image in an encoder to produce a bitstream of compressed image data, the encoder generating a transform unit from the image, the transform unit including transform coefficients, wherein the transform unit is represented by a significance map containing a significant-coefficient flag for each transform coefficient, and wherein the significance map is partitioned into a plurality of coefficient groups, each coefficient group having an associated significant-coefficient-group flag indicating whether its coefficient group contains at least one non-zero significant-coefficient flag, wherein the instructions comprise:

instructions to, for one of the coefficient groups containing at least one non-zero significant-coefficient flag,

determine, using rate-distortion optimized quantization, that said one of the coefficient groups is to be modified to contain all zero significant-coefficient flags, wherein determining includes determining a rate cost associated with encoding the significant-coefficient-group flags, the significant-coefficient flags, and remaining level information for the transform unit and a distortion based on modifying at least one transform coefficient in said one of the coefficient groups to be zero;

based on that determination, set all significant-coefficient flags in that coefficient group to zero and setting its significant-coefficient-group flag to zero; and

entropy encode the significant-coefficient-group flags and, for any coefficient groups having an associated significant-coefficient group flag that is non-zero, entropy encode the significant-coefficient flags for those groups.

14. The non-transitory processor-readable medium claimed in claim 13 , wherein the instructions, when executed, further cause the one or more processors to, prior to determining that said one of the coefficient groups is to be modified to contain all zero significant-coefficient flags,

apply a rate distortion optimization to the transform unit; and

adjust a level of one or more transform coefficients based on the rate distortion optimization to produce a rate-distortion optimized transform unit, wherein the significant-coefficients of the significance map represent the locations of non-zero coefficients in the rate-distortion optimized transform unit.

15. The non-transitory processor-readable medium claimed in claim 13 , wherein the instructions, when executed, further cause the one or more processors to first fix the location of the last significant coefficient in a scan order in the transform unit, and exclude a last coefficient group containing the last significant coefficient from the rate-distortion optimized quantization.

16. The non-transitory processor-readable medium claimed in claim 15 , wherein the instructions, when executed, further cause the one or more processors to test, in a reverse scan order, each of the coefficient groups other than the last coefficient group and a first coefficient group in the scan order.

17. The non-transitory processor-readable medium claimed in claim 13 , wherein the instructions, when executed, further cause the one or more processors to repeat the method, for the transform unit, using a different coefficient group size and selecting a coefficient group size that results in the most rate-distortion efficient bitstream.

18. The non-transitory processor-readable medium claimed in claim 17 , wherein the instructions, when executed, further cause the one or more processors to insert information in the bitstream indicating the selected coefficient group size.

19. A method for use in an encoder of an image to produce a bitstream of compressed image data, the encoder generating a transform unit from the image, the transform unit including transform coefficients, wherein the transform unit is represented by a significance map containing a significant-coefficient flag for each transform coefficient, and wherein the significance map is partitioned into a plurality of coefficient groups, each coefficient group having an associated significant-coefficient-group flag indicating whether its coefficient group contains at least one non-zero significant-coefficient flag, the method comprising:

for one of the coefficient groups containing at least one non-zero significant-coefficient flag,

determining, using rate-distortion optimized quantization, that said one of the coefficient groups is to be modified to contain all zero significant-coefficient flags, wherein the determining includes first fixing the location of the last significant coefficient in a scan order in the transform unit, and excluding a last coefficient group containing the last significant coefficient from the rate-distortion optimized quantization and wherein the determining further includes testing, in a reverse scan order, each of the coefficient groups other than the last coefficient group and a first coefficient group in the scan order;

based on that determination, setting all significant-coefficient flags in that coefficient group to zero and setting its significant-coefficient-group flag to zero; and

entropy encoding the significant-coefficient-group flags and, for any coefficient groups having an associated significant-coefficient group flag that is non-zero, entropy encoding the significant-coefficient flags for those groups.

20. An encoder for encoding an image to produce a bitstream of compressed image data, the encoder generating a transform unit from the image, the transform unit including transform coefficients, wherein the transform unit is represented by a significance map containing a significant-coefficient flag for each transform coefficient, and wherein the significance map is partitioned into a plurality of coefficient groups, each coefficient group having an associated significant-coefficient-group flag indicating whether its coefficient group contains at least one non-zero significant-coefficient flag, the encoder comprising:

a processor;

a memory; and

an encoding application stored in memory and containing instructions, which when executed, cause the processor to,

for one of the coefficient groups containing at least one non-zero significant-coefficient flag,

determine, using rate-distortion optimized quantization, that said one of the coefficient groups is to be modified to contain all zero significant-coefficient flags, wherein the determining includes first fixing the location of the last significant coefficient in a scan order in the transform unit, and excluding a last coefficient group containing the last significant coefficient from the rate-distortion optimized quantization and wherein the determining further includes testing, in a reverse scan order, each of the coefficient groups other than the last coefficient group and a first coefficient group in the scan order;

based on that determination, set all significant-coefficient flags in that coefficient group to zero and setting its significant-coefficient-group flag to zero; and

entropy encode the significant-coefficient-group flags and, for any coefficient groups having an associated significant-coefficient group flag that is non-zero, entropy encode the significant-coefficient flags for those groups.