Variable length coding of coefficient clusters for image and video compression

• US 8,041,131 B2
• Filed: 02/13/2008
• Issued: 10/18/2011
• Est. Priority Date: 10/02/2007
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.), Georgia Tech Research Corporation (University System of Georgia)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: AlRegib, Ghassan, Chen, Wen-hsiung, Li, Junlin, Chang, Pi Sheng, Tian, Dihong
• Primary Examiner(s): Le; Brian Q
• Assistant Examiner(s): BEKELE, MEKONEN T
• Application Number:
  US12/030,821
• Publication Number:
  US 20090087113A1
• Time in Patent Office: 1,343 Days
• Field of Search: 382/245, 382/146, 382/232
• US Class Current: 382/232
• CPC Class Codes: H04N 19/136 Incoming video signal characteristics or properties
• CPC Class Codes: H04N 19/18 the unit being a set of transform coefficients
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/62 by frequency transforming in three dimensions H04N19/63 takes precedence
• CPC Class Codes: H04N 19/649 the transform being applied to non rectangular image segments
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

A coding method, apparatus, and medium with software encoded thereon to implement a coding method. The coding method includes encoding cluster of consecutive non-zero-valued coefficients, the encoding of a cluster including jointly encoding joint events that each are defined by at least two parameters: the number of zero-valued coefficients preceding the cluster, and the number of non-zero-valued coefficients in the cluster. The encoding of the cluster also includes encoding a parameter indicative of the number of amplitude-1 trailing non-zero-valued coefficients in the cluster, in one version with the parameter indicative of the number of trailing amplitude-1 coefficients part of the joint events such that the coding is according to a 3-dimensional joint variable length coding table. The method further includes encoding the amplitudes of the non-zero-valued coefficients that are not encoded by the joint encoding, e.g., encoding the amplitudes of the other than the trailing amplitude-1 coefficients.

Claims

1. A method of operating an encoding apparatus to compress image data, the method comprising:

accepting quantized transform coefficients of one or more blocks of image data into the encoding apparatus;

for a first region of an ordered series of quantized transform coefficients of a block of image data, the first region possibly including the whole series, the series having a most likely-to-occur amplitude, and at least one other amplitude including a next-to-most likely-to-occur amplitude, the encoding apparatus encoding the position and amplitude of each cluster of consecutive coefficients having amplitude other than the most likely-to-occur amplitude, the encoding of each cluster including the encoding apparatus encoding one or more events for the cluster, including encoding a joint event defined by at least two parameters;

the number of coefficients having the most likely-to-occur amplitude preceding the cluster, and the number of coefficients in the cluster, and encoding an indication of the number of trailing coefficients having the next-to-most likely-to-occur amplitude in the cluster, the encoding of the events by the encoding apparatus forming event codewords, with the encoding of each cluster according to at least one multi-dimensional joint encoding mapping such that for at least some events, encoding the events by the joint encoding mapping is such that on average, the more likely an event is to occur, the shorter the event codeword formed to encode the event; and

the encoding apparatus encoding the amplitude of the coefficients that have amplitude other than the most likely-to-occur amplitude and that are not jointly encoded by the encoding of the indication of the number of trailing coefficients in the cluster, the encoding of the amplitude by the encoding apparatus forming amplitude codewords.

2. A method as recited in claim 1, wherein the encoding of each cluster includes jointly encoding an event defined by three parameters:

the number of coefficients having the most likely-to-occur amplitude preceding the cluster, the number of coefficients in the cluster, and a third parameter that includes an indication of the number of trailing coefficients having the next-to-most likely-to-occur amplitude in the cluster, with the jointly encoding being according a three-dimensional joint encoding mapping such that for at least some events, encoding the events by the joint encoding mapping is such that on average, the more likely an event is to occur, the shorter the codeword used to encode the event.

3. A method as recited in claim 2, wherein the third parameter is the number of trailing coefficients in the cluster that have the next-to-most likely-to-occur amplitude.

4. A method as recited in claim 2, wherein, for at least one cluster length, the third parameter includes an indication of which of the coefficients in the cluster have the next-to-most likely-to-occur amplitude.

5. A method as recited in claim 1, wherein the encoding of each cluster includes jointly encoding an event defined by two parameters:

the number of coefficients having the most likely-to-occur amplitude preceding the cluster, and the number of coefficients in the cluster, and further encoding a second event for the cluster defined by the number of trailing coefficients having the next-to-most likely-to-occur amplitude in the cluster, with the jointly encoding being according a first two-dimensional joint encoding mapping such that for at least some events, encoding the events by the joint encoding mapping is such that on average, the more likely an event is to occur, the shorter the codeword used to encode the event.

6. A method as recited in claim 5, wherein the second event for each cluster is a one dimensional event defined by the number of trailing coefficients having the next-to-most likely-to-occur amplitude in the cluster, with the encoding of the second event being according to a one-dimensional encoding mapping such that for at least some events, encoding the second events by the one-dimensional encoding mapping is such that on average, the more likely an event is to occur, the shorter the codeword used to encode the event.

7. A method as recited in claim 5, wherein the second event for each cluster is defined by two parameters:

the number of consecutive trailing coefficients having the next-to-most likely-to-occur amplitude in the cluster, the amplitude of the coefficient immediately preceding the consecutive trailing coefficients having the next-to-most likely-to-occur amplitude in the cluster with the encoding of the second event for the cluster being according a second two-dimensional joint encoding mapping such that for at least some events, encoding the events by the joint encoding mapping is such that on average, the more likely an event is to occur, the shorter the codeword used to encode the event.

8. A method as recited in claim 1, wherein encoding the amplitude of the coefficients that have amplitude other than the most likely-to-occur amplitude includes encoding the coefficients other than the coefficient adjacent to the trailing coefficients of the cluster, and further encoding a value equal to one less than the amplitude of the coefficient immediately preceding the trailing coefficients in that cluster that have the next-to-most likely-to-occur amplitude value.

9. A method as recited in claim 1, wherein 0 is the most-likely-to-occur amplitude and 1 is the next-to-most likely-to-occur amplitude.

10. A method as recited in claim 9, further comprising:

encoding the signs of the non-zero-valued coefficients in the cluster.

11. A method as recited in claim 9, wherein the first region is one of a plurality of regions, the first region being one wherein clusters of non-zero-valued coefficients are likely to occur, the method further comprising:

encoding the coefficients in the remaining region(s).

12. A computer-readable hardware storage medium encoded with computer-executable instructions that when executed by one or more processors of a processing system implement a coding method comprising:

for a first region of an ordered series of quantized transform coefficients of a block of image data, the first region possibly the whole series, the series having a most likely-to-occur amplitude, and at least one other amplitude including a next-to-most likely-to-occur amplitude, encoding the position and amplitude of each cluster of consecutive coefficients having amplitude other than the most likely-to-occur amplitude, the encoding of each cluster including encoding one or more events for the cluster, including encoding a joint event defined by at least two parameters;

the number of coefficients having the most likely-to-occur amplitude preceding the cluster, and the number of coefficients in the cluster, and encoding an indication of the number of trailing coefficients having the next-to-most likely-to-occur amplitude in the cluster, with the coding of each cluster according to at least one multi-dimensional joint encoding mapping such that for at least some events, encoding the events by the joint encoding mapping is such that on average, the more likely an event is to occur, the shorter the codeword used to encode the event; and

encoding the amplitude of the coefficients that have amplitude other than the most likely-to-occur amplitude and that are not jointly encoded by the encoding of the indication of the number of trailing coefficients in the cluster.

13. A computer-readable hardware storage medium as recited in claim 12, wherein in the method, the encoding of each cluster includes jointly encoding an event defined by three parameters:

the number of coefficients having the most likely-to-occur amplitude preceding the cluster, the number of coefficients in the cluster, and a third parameter that include an indication of the number of trailing coefficients having the next-to-most likely-to-occur amplitude in the cluster, with the jointly encoding being according a three-dimensional joint encoding mapping such that for at least some events, encoding the events by the joint encoding mapping is such that on average, the more likely an event is to occur, the shorter the codeword used to encode the event.

14. A computer-readable hardware storage medium as recited in claim 12, wherein in the method, the coding of each cluster includes jointly encoding an event defined by two parameters:

the number of coefficients having the most likely-to-occur amplitude preceding the cluster, and the number of coefficients in the cluster, and further encoding a second event for the cluster defined by the number of trailing coefficients having the next-to-most likely-to-occur amplitude in the cluster, with the jointly encoding being according a first two-dimensional joint encoding mapping such that for at least some events, encoding the events by the joint encoding mapping is such that on average, the more likely an event is to occur, the shorter the codeword used to encode the event.

15. A computer-readable hardware storage medium as recited in claim 14, wherein in the method, the second event for each cluster is a one dimensional event defined by the number of trailing coefficients having the next-to-most likely-to-occur amplitude in the cluster, with the encoding of the second event being according to a one-dimensional encoding mapping such that for at least some events, encoding the second events by the one-dimensional encoding mapping is such that on average, the more likely an event is to occur, the shorter the codeword used to encode the event.

16. A computer-readable hardware storage medium as recited in claim 14, wherein in the method, the second event for each cluster is defined by two parameters:

the number of consecutive trailing coefficients having the next-to-most likely-to-occur amplitude in the cluster, the amplitude of the coefficient immediately preceding the consecutive trailing coefficients having the next-to-most likely-to-occur amplitude in the cluster with the encoding of the second event for the cluster being according a second two-dimensional joint encoding mapping such that for at least some events, encoding the events by the joint encoding mapping is such that on average, the more likely an event is to occur, the shorter the codeword used to encode the event.

17. A computer-readable hardware storage medium as recited in claim 12, wherein 0 is the most likely-to-occur amplitude and 1 is next-to-most likely-to-occur amplitude.

18. A computer-readable hardware storage medium as recited in claim 17, wherein the method further includes:

encoding the signs of the non-zero-valued coefficients in the cluster.

19. A computer-readable hardware storage medium in claim 17, wherein the first region is one of a plurality of regions, the first region being one wherein clusters of non-zero-valued coefficients are likely to occur, and wherein the method further comprises:

encoding the coefficients in the remaining region(s).

20. An apparatus to accept image data and transform the image data to event codewords and amplitude codewords, the apparatus comprising:

a first region encoder operative to accept an ordered series of quantized transform coefficients of a block of the image data and to form one or more event codewords by encoding the position and amplitude of each cluster of consecutive coefficients having amplitude other than the most likely-to-occur amplitude in a first region of an ordered series of quantized transform coefficients of a block of the image data, the first region possibly the whole series, the series having a most likely-to-occur amplitude, and at least one other amplitude including a next-to-most likely-to-occur amplitude, the encoding of each cluster including encoding one or more events for the cluster, including encoding a joint event defined by at least two parameters;

the number of coefficients having the most likely-to-occur amplitude preceding the cluster, and the number of coefficients in the cluster, and encoding an indication of the number of trailing coefficients having the next-to-most likely-to-occur amplitude in the cluster, with the encoding of each cluster according to at least one multi-dimensional joint encoding mapping such that for at least some events, encoding the events by the joint encoding mapping is such that on average, the more likely an event is to occur, the shorter the event codeword used to encode the event; and

an amplitude encoder coupled to the first region encoder and operative to encode the amplitude of the coefficients that have amplitude other than the most likely-to-occur amplitude and that are not jointly encoded by the encoding of the indication of the number of trailing coefficients in the cluster.

21. An apparatus as recited in claim 20, wherein the first region encoder is operative such that the encoding of each cluster includes jointly encoding an event defined by three parameters:

the number of coefficients having the most likely-to-occur amplitude preceding the cluster, the number of coefficients in the cluster, and a third parameter indicative of the number of trailing coefficients having the next-to-most likely-to-occur amplitude in the cluster, with the jointly encoding being according a three-dimensional joint encoding mapping such that for at least some events, encoding the events by the joint encoding mapping is such that on average, the more likely an event is to occur, the shorter the codeword used to encode the event.

22. An apparatus as recited in claim 20, wherein the first region encoder is operative such that the encoding of each cluster includes jointly encoding an event defined by two parameters:

the number of coefficients having the most likely-to-occur amplitude preceding the cluster, and the number of coefficients in the cluster, and further encoding a second event for the cluster defined by the number of trailing coefficients having the next-to-most likely-to-occur amplitude in the cluster, with the jointly encoding being according a first two-dimensional joint encoding mapping such that for at least some events, encoding the events by the joint encoding mapping is such that on average, the more likely an event is to occur, the shorter the codeword used to encode the event.

23. An apparatus as recited in claim 20, wherein 0 is the most-likely-to-occur amplitude and 1 is the next most-likely to occur amplitude.

24. A method of operating a decoding apparatus to decompress image data, the method comprising:

the decoding apparatus recognizing codewords in a set of concatenated codewords, the codewords formed by a coding method comprising;

for a first region of an ordered series of quantized transform coefficients of a block of image data, the first region possibly the whole series, the series having a most likely-to-occur amplitude, and at least one other amplitude including a next-to-most likely-to-occur amplitude, encoding the position and amplitude of each cluster of consecutive coefficients having amplitude other than the most likely-to-occur amplitude, the encoding of each cluster including encoding one or more events for the cluster, including encoding a joint event defined by at least two parameters;

the number of coefficients having the most likely-to-occur amplitude preceding the cluster, and the number of coefficients in the cluster, and encoding an indication of the number of trailing coefficients having the next-to-most likely-to-occur amplitude in the cluster, with the coding of each cluster according to at least one multi-dimensional joint encoding mapping such that for at least some events, encoding the events by the joint encoding mapping is such that on average, the more likely an event is to occur, the shorter the codeword used to encode the event; and

encoding the amplitude of the coefficients that have amplitude other than the most likely-to-occur amplitude and that are not jointly encoded by the encoding of the indication of the number of trailing coefficients in the cluster; and

the decoding apparatus decoding the recognized codewords using a plurality of code mappings.

25. A computer-readable hardware storage medium storing computer-executable instructions that when executed by one or more processors of a processing system implement a decoding method comprising:

recognizing codewords in a set of concatenated codewords, the codewords formed by a coding method comprising;

for a first region of an ordered series of quantized transform coefficients of a block of image data, the first region possibly the whole series, the series having a most likely-to-occur amplitude, and at least one other amplitude including a next-to-most likely-to-occur amplitude, encoding the position and amplitude of each cluster of consecutive coefficients having amplitude other than the most likely-to-occur amplitude, the encoding of each cluster including encoding one or more events for the cluster, including encoding a joint event defined by at least two parameters;

the number of coefficients having the most likely-to-occur amplitude preceding the cluster, and the number of coefficients in the cluster, and encoding an indication of the number of trailing coefficients having the next-to-most likely-to-occur amplitude in the cluster, with the coding of each cluster according to at least one multi-dimensional joint encoding mapping such that for at least some events, encoding the events by the joint encoding mapping is such that on average, the more likely an event is to occur, the shorter the codeword used to encode the event; and

encoding the amplitude of the coefficients that have amplitude other than the most likely-to-occur amplitude and that are not jointly encoded by the encoding of the indication of the number of trailing coefficients in the cluster; and

decoding the recognized codewords using a plurality of code mappings.