Variable length coding for clustered transform coefficients in video compression

• US 20070019877A1
• Filed: 03/20/2006
• Published: 01/25/2007
• Est. Priority Date: 08/18/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Chen, Wen-hsiung, Wu, Fang, Toebes, John, Rosenfeld, Dov, Pelton, Gregory
• Granted Patent: US 7,680,349 B2
• Time in Patent Office: Days
• US Class Current: 382/245
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/14 Coding unit complexity, e.g. amount of activity or edge presence estimation H04N19/146 takes precedence
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/159 Prediction type, e.g. intra-frame, inter-frame or bidirectional frame prediction
• CPC Class Codes: H04N 19/17 the unit being an image region, e.g. an object
• CPC Class Codes: H04N 19/18 the unit being a set of transform coefficients
• CPC Class Codes: H04N 19/48 using compressed domain processing techniques other than decoding, e.g. modification of transform coefficients, variable length coding [VLC] data or run-length data motion estimation in a transform domain H04N19/547; processing of decoded motion vectors H04N19/513
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
• CPC Class Codes: H04N 19/93 Run-length coding

Abstract

Coding quantized transform coefficients as occur in image compression combines a position identifying method to identify the relative position of clusters of consecutive non-zero-valued coefficients, an amplitude event identifying method to identify amplitude events in the clusters of non-zero-valued coefficients, and a coding method to code the position events, amplitude events, and signs of the amplitudes in the clusters. The method is particularly applicable to a series of quantized transform coefficients where clusters are likely to occur.

Claims

1. A method for processing an ordered series of digital signals that each have an amplitude from a finite set of amplitudes consisting of the most likely-to-occur amplitude and at least one other amplitude, the at least one other amplitude including a next most likely-to-occur amplitude to the most likely-to-occur amplitude, the processing to reduce the amount of data used to represent the digital signals and to form codewords such that the relatively more likely-to-occur values or sequences of values of digital signals are represented by relatively short codewords and the relatively less likely-to-occur values or sequences of values of digital signals are represented by relatively long codewords, the method comprising:

(a) using a position event identifying method to identify position events that each include a cluster of at least one consecutive signal having any amplitude other than the most likely-to-occur amplitude, such that the position events define the relative positions and runlengths of the clusters and of any intervening runs of consecutive coefficients having the most likely-to-occur amplitude;

(b) using an amplitude event identifying method to identify the amplitudes of the signals having amplitudes other than the most likely-to-occur amplitude; and

(c) encoding the identified position events, encoding the identified amplitude events, and encoding the signs of the amplitudes other than the most likely-to-occur amplitude in the identified amplitude events, such that for at least some of the signals having amplitudes other than the most likely-to-occur amplitude, clusters of signals having relatively more likely-to-occur signal amplitudes are encoded on average by shorter codeword(s) than are clusters of signals having relatively less likely-to-occur signal amplitudes,

wherein the position event identifying method uses Cluster Runlength Identifying and the amplitude event identifying method uses Multi-Dimensional Amplitude Event Identifying.

2. A method as recited in claim 1, wherein the series of digital signals is a series of quantized coefficients of a transformed block of image data, the transform such that the most likely-to-occur amplitude is 0, and the next most likely-to-occur amplitude is 1, such that the identifying of position events identifies events that include a cluster of one or more non-zero-valued coefficients.

3. A method as recited in claim 2, wherein the transformed block of image data includes a DC term, and wherein the DC term is separately encoded, such that the series of digital signals is a set of non-DC quantized coefficients of a transformed block of image data.

4. A method as recited in claim 2, wherein (c) includes separately encoding the signs of the amplitudes.

5. A method as recited in claim 2, wherein the encoding of the amplitude events and of the position events uses coding tables.

6. A method as recited in claim 5, wherein each of the respective coding tables is constructed by assigning a variable length code to at least some of the respective events being coded by the coding table according to measured or assumed statistics of the respective event being coded by the coding table.

7. A method as recited in claim 2, wherein the encoding of the identified position and amplitude events includes encoding the identified position events jointly with the identified amplitude events.

8. A method as recited in claim 2, wherein the encoding of the identified position and amplitude events includes separately encoding the identified position events and the identified amplitude events.

9. A method for processing an ordered series of digital signals that each have an amplitude from a finite set of amplitudes consisting of the most likely-to-occur amplitude and at least one other amplitude, the at least one other amplitude including a next most likely-to-occur amplitude to the most likely-to-occur amplitude, the processing to reduce the amount of data used to represent the digital signals and to form codewords such that the relatively more likely-to-occur values or sequences of values of digital signals are represented by relatively short codewords and the relatively less likely-to-occur values or sequences of values of digital signals are represented by relatively long codewords, the method comprising:

(a) using a position event identifying method to identify position events that each include a cluster of at least one consecutive signal having any amplitude other than the most likely-to-occur amplitude, such that the position events define the relative positions and runlengths of the clusters and of any intervening runs of consecutive coefficients having the most likely-to-occur amplitude;

(b) using an amplitude event identifying method to identify the amplitudes of the signals having amplitudes other than the most likely-to-occur amplitude; and

(c) encoding the identified position events, encoding the identified amplitude events, and encoding the signs of the amplitudes other than the most likely-to-occur amplitude in the identified amplitude events, such that for at least some of the signals having amplitudes other than the most likely-to-occur amplitude, clusters of signals having relatively more likely-to-occur signal amplitudes are encoded on average by shorter codeword(s) than are clusters of signals having relatively less likely-to-occur signal amplitudes,

wherein the position event identifying method uses Cluster Runlength Identifying and the amplitude event identifying method uses Multi-Table Amplitude Event Identifying.

10. A method as recited in claim 9, wherein the series of digital signals is a series of quantized coefficients of a transformed block of image data, the transform such that the most likely-to-occur amplitude is 0, and the next most likely-to-occur amplitude is 1, such that the identifying of position events identifies events that include a cluster of one or more non-zero-valued coefficients.

11. A method as recited in claim 10, wherein the transformed block of image data includes a DC term, and wherein the DC term is separately encoded, such that the series of digital signals is a set of non-DC quantized coefficients of a transformed block of image data.

12. A method as recited in claim 10, wherein (c) includes separately encoding the signs of the amplitudes.

13. A method as recited in claim 10, wherein the encoding of the amplitude events and of the position events uses coding tables.

14. A method as recited in claim 13, wherein each of the respective coding tables is constructed by assigning a variable length code to at least some of the respective events being coded by the coding table according to measured or assumed statistics of the respective event being coded by the coding table.

15. A method as recited in claim 10, wherein the encoding of the identified position and amplitude events includes encoding the identified position events jointly with the identified amplitude events.

16. A method as recited in claim 10, wherein the encoding of the identified position and amplitude events includes separately encoding the identified position events and the identified amplitude events.

17. A method for processing an ordered series of digital signals that each have an amplitude from a finite set of amplitudes consisting of the most likely-to-occur amplitude and at least one other amplitude, the at least one other amplitude including a next most likely-to-occur amplitude to the most likely-to-occur amplitude, the processing to reduce the amount of data used to represent the digital signals and to form codewords such that the relatively more likely-to-occur values or sequences of values of digital signals are represented by relatively short codewords and the relatively less likely-to-occur values or sequences of values of digital signals are represented by relatively long codewords, the method comprising:

(a) using a position event identifying method to identify position events that each include a cluster of at least one consecutive signal having any amplitude other than the most likely-to-occur amplitude, such that the position events define the relative positions and runlengths of the clusters and of any intervening runs of consecutive coefficients having the most likely-to-occur amplitude;

(b) using an amplitude event identifying method to identify the amplitudes of the signals having amplitudes other than the most likely-to-occur amplitude; and

(c) encoding the identified position events, encoding the identified amplitude events, and encoding the signs of the amplitudes other than the most likely-to-occur amplitude in the identified amplitude events, such that for at least some of the signals having amplitudes other than the most likely-to-occur amplitude, clusters of signals having relatively more likely-to-occur signal amplitudes are encoded on average by shorter codeword(s) than are clusters of signals having relatively less likely-to-occur signal amplitudes,

wherein the position event identifying method uses 2-D Cluster Length and Position Identifying.

18. A method as recited in claim 17, wherein the series of digital signals is a series of quantized coefficients of a transformed block of image data, the transform such that the most likely-to-occur amplitude is 0, and the next most likely-to-occur amplitude is 1, such that the identifying of position events identifies events that include a cluster of one or more non-zero-valued coefficients.

19. A method as recited in claim 18, wherein the transformed block of image data includes a DC term, and wherein the DC term is separately encoded, such that the series of digital signals is a set of non-DC quantized coefficients of a transformed block of image data.

20. A method as recited in claim 18, wherein (c) includes separately encoding the signs of the amplitudes.

21. A method as recited in claim 18, wherein the encoding of the amplitude events and of the position events uses coding tables.

22. A method as recited in claim 21, wherein each of the respective coding tables is constructed by assigning a variable length code to at least some of the respective events being coded by the coding table according to measured or assumed statistics of the respective event being coded by the coding table.

23. A method as recited in claim 18, wherein the amplitude event identifying method uses Multi-Dimensional Amplitude Event Identifying.

24. A method as recited in claim 18, wherein the amplitude event identifying method uses Multi-Table Amplitude Event Identifying.

25. A method as recited in claim 18, wherein the amplitude event identifying method identifies individual amplitudes in the clusters.

26. A method as recited in claim 18, wherein the encoding of the identified position and amplitude events includes encoding the identified position events jointly with the identified amplitude events.

27. A method as recited in claim 18, wherein the encoding of the identified position and amplitude events includes separately encoding the identified position events and the identified amplitude events.

28. A carrier medium carrying computer readable instructions that when executed by at least one processor of a processing system cause the processing system to carry out a method for processing an ordered series of digital signals that each have an amplitude from a finite set of amplitudes consisting of the most likely-to-occur amplitude and at least one other amplitude, the at least one other amplitude including a next most likely-to-occur amplitude to the most likely-to-occur amplitude, the processing to reduce the amount of data used to represent the digital signals and to form codewords such that the relatively more likely-to-occur values or sequences of values of digital signals are represented by relatively short codewords and the relatively less likely-to-occur values or sequences of values of digital signals are represented by relatively long codewords, the method comprising:

(a) using a position event identifying method to identify position events that each include a cluster of at least one consecutive signal having any amplitude other than the most likely-to-occur amplitude, such that the position events define the relative positions and runlengths of the clusters and of any intervening runs of consecutive coefficients having the most likely-to-occur amplitude;

(b) using an amplitude event identifying method to identify the amplitudes of the signals having amplitudes other than the most likely-to-occur amplitude; and

(c) encoding the identified position events, encoding the identified amplitude events, and encoding the signs of the amplitudes other than the most likely-to-occur amplitude in the identified amplitude events, such that for at least some of the signals having amplitudes other than the most likely-to-occur amplitude, clusters of signals having relatively more likely-to-occur signal amplitudes are encoded on average by shorter codeword(s) than are clusters of signals having relatively less likely-to-occur signal amplitudes,

wherein the position event identifying method uses Cluster Runlength Identifying and the amplitude event identifying method uses Multi-Dimensional Amplitude Event Identifying.

29. A carrier medium as recited in claim 28, wherein the series of digital signals is a series of quantized coefficients of a transformed block of image data, the transform such that the most likely-to-occur amplitude is 0, and the next most likely-to-occur amplitude is 1, such that the identifying of position events identifies events that include a cluster of one or more non-zero-valued coefficients.

30. A carrier medium as recited in claim 29, wherein the encoding of the identified position and amplitude events includes encoding the identified position events jointly with the identified amplitude events.

31. A carrier medium as recited in claim 29, wherein the encoding of the identified position and amplitude events includes separately encoding the identified position events and the identified amplitude events.

32. A carrier medium for processing an ordered series of digital signals that each have an amplitude from a finite set of amplitudes consisting of the most likely-to-occur amplitude and at least one other amplitude, the at least one other amplitude including a next most likely-to-occur amplitude to the most likely-to-occur amplitude, the processing to reduce the amount of data used to represent the digital signals and to form codewords such that the relatively more likely-to-occur values or sequences of values of digital signals are represented by relatively short codewords and the relatively less likely-to-occur values or sequences of values of digital signals are represented by relatively long codewords, the method comprising:

(a) using a position event identifying method to identify position events that each include a cluster of at least one consecutive signal having any amplitude other than the most likely-to-occur amplitude, such that the position events define the relative positions and runlengths of the clusters and of any intervening runs of consecutive coefficients having the most likely-to-occur amplitude;

(b) using an amplitude event identifying method to identify the amplitudes of the signals having amplitudes other than the most likely-to-occur amplitude; and

(c) encoding the identified position events, encoding the identified amplitude events, and encoding the signs of the amplitudes other than the most likely-to-occur amplitude in the identified amplitude events, such that for at least some of the signals having amplitudes other than the most likely-to-occur amplitude, clusters of signals having relatively more likely-to-occur signal amplitudes are encoded on average by shorter codeword(s) than are clusters of signals having relatively less likely-to-occur signal amplitudes,

wherein the position event identifying method uses Cluster Runlength Identifying and the amplitude event identifying method uses Multi-Table Amplitude Event Identifying.

33. A carrier medium as recited in claim 32, wherein the series of digital signals is a series of quantized coefficients of a transformed block of image data, the transform such that the most likely-to-occur amplitude is 0, and the next most likely-to-occur amplitude is 1, such that the identifying of position events identifies events that include a cluster of one or more non-zero-valued coefficients.

34. A carrier medium as recited in claim 33, wherein the encoding of the identified position and amplitude events includes encoding the identified position events jointly with the identified amplitude events.

35. A carrier medium as recited in claim 33, wherein the encoding of the identified position and amplitude events includes separately encoding the identified position events and the identified amplitude events.

36. A carrier medium for processing an ordered series of digital signals that each have an amplitude from a finite set of amplitudes consisting of the most likely-to-occur amplitude and at least one other amplitude, the at least one other amplitude including a next most likely-to-occur amplitude to the most likely-to-occur amplitude, the processing to reduce the amount of data used to represent the digital signals and to form codewords such that the relatively more likely-to-occur values or sequences of values of digital signals are represented by relatively short codewords and the relatively less likely-to-occur values or sequences of values of digital signals are represented by relatively long codewords, the method comprising:

(a) using a position event identifying method to identify position events that each include a cluster of at least one consecutive signal having any amplitude other than the most likely-to-occur amplitude, such that the position events define the relative positions and runlengths of the clusters and of any intervening runs of consecutive coefficients having the most likely-to-occur amplitude;

(b) using an amplitude event identifying method to identify the amplitudes of the signals having amplitudes other than the most likely-to-occur amplitude; and

(c) encoding the identified position events, encoding the identified amplitude events, and encoding the signs of the amplitudes other than the most likely-to-occur amplitude in the identified amplitude events, such that for at least some of the signals having amplitudes other than the most likely-to-occur amplitude, clusters of signals having relatively more likely-to-occur signal amplitudes are encoded on average by shorter codeword(s) than are clusters of signals having relatively less likely-to-occur signal amplitudes,

wherein the position event identifying method uses 2-D Cluster Length and Position Identifying.

37. A carrier medium as recited in claim 36, wherein the series of digital signals is a series of quantized coefficients of a transformed block of image data, the transform such that the most likely-to-occur amplitude is 0, and the next most likely-to-occur amplitude is 1, such that the identifying of position events identifies events that include a cluster of one or more non-zero-valued coefficients.

38. A carrier medium as recited in claim 37, wherein the amplitude event identifying method uses Multi-Dimensional Amplitude Event Identifying.

39. A carrier medium as recited in claim 37, wherein the amplitude event identifying method uses Multi-Table Amplitude Event Identifying.

40. A carrier medium as recited in claim 37, wherein the amplitude event identifying method identifies individual amplitudes in the clusters.

41. A carrier medium as recited in claim 37, wherein the encoding of the identified position and amplitude events includes encoding the identified position events jointly with the identified amplitude events.

42. A carrier medium as recited in claim 37, wherein the encoding of the identified position and amplitude events includes separately encoding the identified position events and the identified amplitude events.

43. An apparatus for processing an ordered series of digital signals that each have an amplitude from a finite set of amplitudes consisting of the most likely-to-occur amplitude and at least one other amplitude, the at least one other amplitude including a next most likely-to-occur amplitude to the most likely-to-occur amplitude, the processing to reduce the amount of data used to represent the digital signals and to form codewords such that the relatively more likely-to-occur values or sequences of values of digital signals are represented by relatively short codewords and the relatively less likely-to-occur values or sequences of values of digital signals are represented by relatively long codewords, the apparatus comprising:

(a) means for using a position event identifying method to identify position events that each include a cluster of at least one consecutive signal having any amplitude other than the most likely-to-occur amplitude, such that the position events define the relative positions and runlengths of the clusters and of any intervening runs of consecutive coefficients having the most likely-to-occur amplitude;

(b) means for using an amplitude event identifying method to identify the amplitudes of the signals having amplitudes other than the most likely-to-occur amplitude; and

(c) means for encoding the identified position events, for encoding the identified amplitude events, and for encoding the signs of the amplitudes other than the most likely-to-occur amplitude in the identified amplitude events, such that for at least some of the signals having amplitudes other than the most likely-to-occur amplitude, clusters of signals having relatively more likely-to-occur signal amplitudes are encoded on average by shorter codeword(s) than are clusters of signals having relatively less likely-to-occur signal amplitudes,

wherein the position event identifying method uses Cluster Runlength Identifying and the amplitude event identifying method uses Multi-Dimensional Amplitude Event Identifying.

44. An apparatus as recited in claim 43, wherein the series of digital signals is a series of quantized coefficients of a transformed block of image data, the transform such that the most likely-to-occur amplitude is 0, and the next most likely-to-occur amplitude is 1, such that the identifying of position events identifies events that include a cluster of one or more non-zero-valued coefficients.

45. An apparatus for processing an ordered series of digital signals that each have an amplitude from a finite set of amplitudes consisting of the most likely-to-occur amplitude and at least one other amplitude, the at least one other amplitude including a next most likely-to-occur amplitude to the most likely-to-occur amplitude, the processing to reduce the amount of data used to represent the digital signals and to form codewords such that the relatively more likely-to-occur values or sequences of values of digital signals are represented by relatively short codewords and the relatively less likely-to-occur values or sequences of values of digital signals are represented by relatively long codewords, the apparatus comprising:

(a) means for using a position event identifying method to identify position events that each include a cluster of at least one consecutive signal having any amplitude other than the most likely-to-occur amplitude, such that the position events define the relative positions and runlengths of the clusters and of any intervening runs of consecutive coefficients having the most likely-to-occur amplitude;

(b) means for using an amplitude event identifying method to identify the amplitudes of the signals having amplitudes other than the most likely-to-occur amplitude; and

(c) means for encoding the identified position events, for encoding the identified amplitude events, and for encoding the signs of the amplitudes other than the most likely-to-occur amplitude in the identified amplitude events, such that for at least some of the signals having amplitudes other than the most likely-to-occur amplitude, clusters of signals having relatively more likely-to-occur signal amplitudes are encoded on average by shorter codeword(s) than are clusters of signals having relatively less likely-to-occur signal amplitudes,

wherein the position event identifying method uses Cluster Runlength Identifying and the amplitude event identifying method uses Multi-Table Amplitude Event Identifying.

46. An apparatus as recited in claim 45, wherein the series of digital signals is a series of quantized coefficients of a transformed block of image data, the transform such that the most likely-to-occur amplitude is 0, and the next most likely-to-occur amplitude is 1, such that the identifying of position events identifies events that include a cluster of one or more non-zero-valued coefficients.

47. An apparatus for processing an ordered series of digital signals that each have an amplitude from a finite set of amplitudes consisting of the most likely-to-occur amplitude and at least one other amplitude, the at least one other amplitude including a next most likely-to-occur amplitude to the most likely-to-occur amplitude, the processing to reduce the amount of data used to represent the digital signals and to form codewords such that the relatively more likely-to-occur values or sequences of values of digital signals are represented by relatively short codewords and the relatively less likely-to-occur values or sequences of values of digital signals are represented by relatively long codewords, the apparatus comprising:

(a) means for using a position event identifying method to identify position events that each include a cluster of at least one consecutive signal having any amplitude other than the most likely-to-occur amplitude, such that the position events define the relative positions and runlengths of the clusters and of any intervening runs of consecutive coefficients having the most likely-to-occur amplitude;

(b) means for using an amplitude event identifying method to identify the amplitudes of the signals having amplitudes other than the most likely-to-occur amplitude; and

(c) means for encoding the identified position events, for encoding the identified amplitude events, and for encoding the signs of the amplitudes other than the most likely-to-occur amplitude in the identified amplitude events, such that for at least some of the signals having amplitudes other than the most likely-to-occur amplitude, clusters of signals having relatively more likely-to-occur signal amplitudes are encoded on average by shorter codeword(s) than are clusters of signals having relatively less likely-to-occur signal amplitudes,

wherein the position event identifying method uses 2-D Cluster Length and Position Identifying.

48. An apparatus as recited in claim 47, wherein the series of digital signals is a series of quantized coefficients of a transformed block of image data, the transform such that the most likely-to-occur amplitude is 0, and the next most likely-to-occur amplitude is 1, such that the identifying of position events identifies events that include a cluster of one or more non-zero-valued coefficients.