VARIABLE LENGTH CODING OF COEFFICIENT CLUSTERS FOR IMAGE AND VIDEO COMPRESSION

• US 20090087113A1
• Filed: 02/13/2008
• Published: 04/02/2009
• 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: Georgia Tech Research Corporation (University System of Georgia)
• Inventors: Chen, Wen-hsiung, Li, Junlin, Chang, Pi Sheng, Tian, Dihong, AlRegib, Ghassan
• Granted Patent: US 8,041,131 B2
• Time in Patent Office: Days
• US Class Current: 382/246
• 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, the method comprising:

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, 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-dimensional joint encoding mapping such that for at least some events, on average, 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.

2. A method as recited in claim 1, wherein the coding 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-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 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-dimensional joint encoding mapping such that for at least some events, on average, 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, on average, 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-dimensional joint encoding mapping such that for at least some events, on average, 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 than 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 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 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-dimensional joint encoding mapping such that for at least some events, on average, 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 medium as recited in claim 12, wherein in the method, the coding 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-dimensional joint encoding mapping such that for at least some events, on average, 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 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-dimensional joint encoding mapping such that for at least some events, on average, 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 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, on average, 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 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-dimensional joint encoding mapping such that for at least some events, on average, 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 medium as recited in claim 12, wherein 0 is the most-likely-to-occur amplitude and 1 is the next most-likely to occur amplitude.

18. A computer-readable 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 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 comprising:

a first region encoder in 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, the first region encoder operative to encode 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-dimensional joint encoding mapping such that for at least some events, on average, 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

an amplitude encoder 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 coding 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-dimensional joint encoding mapping such that for at least some events, on average, 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 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 farther 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-dimensional joint encoding mapping such that for at least some events, on average, 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, the 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-dimensional joint encoding mapping such that for at least some events, on average, 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.

25. A computer-readable medium encoded with 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-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.