Run-length encoding/decoding video signals using scan patterns explicitly encoded into bitstreams

• US 5,721,822 A
• Filed: 09/29/1995
• Issued: 02/24/1998
• Est. Priority Date: 07/21/1995
• Status: Expired due to Term

• Current Assignee: Intel Corporation, Tamarack Products Incorporated
• Original Assignee: Intel Corporation
• Inventors: Agarwal, Rohit
• Primary Examiner(s): Ramirez, Ellis B.
• Application Number:
  US08/537,246
• Time in Patent Office: 879 Days
• Field of Search: 395/200.18, 364/514 R, 364/715.02, 382/233, 382/240, 382/245, 382/246, 382/248, 348/403, 348/407, 358/432
• US Class Current: 710/68
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/126 Details of normalisation or weighting functions, e.g. normalisation matrices or variable uniform quantisers
• CPC Class Codes: H04N 19/129 Scanning of coding units, e.g. zig-zag scan of transform coefficients or flexible macroblock ordering [FMO]
• 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/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/18 the unit being a set of transform coefficients
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/619 the transform being operated outside the prediction loop
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/70 characterised by syntax aspects related to video coding, e.g. related to compression standards
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
• CPC Class Codes: H04N 7/24 Systems for the transmission of television signals using pulse code modulation H04N21/00 takes precedence

Abstract

Video signals are run-length encoded using a scan pattern and encoded video signals are run-length decoded using the scan pattern, where the scan pattern is explicitly encoded into the encoded bitstream. In a preferred embodiment, the scan pattern is generated by applying a constrained sorting rule to energy measures corresponding to the video signals to be encoded. The scan pattern used for encoding can be changed as often as needed where each new scan pattern is explicitly encoded into the bitstream for use in decoding.

Claims

1. A computer-implemented process for processing video signals, comprising the steps of:

(a) generating energy measures for coefficients of a plurality of blocks of video signals; and

(b) applying a constrained sorting rule to the energy measures to generate a scan pattern for run-length encoding.

2. The process of claim 1, further comprising the step of:

(c) decoding a block of encoded video signals of an encoded bitstream using run-length decoding based on the scan pattern to generate decoded video signals.

3. The process of claim 2, wherein step (c) comprises the step of decoding the encoded bitstream to determine the scan pattern, wherein the scan pattern is explicitly encoded in the encoded bitstream.

4. The process of claim 2, wherein step (c) comprises the step of run-length decoding the block of encoded video signals using the scan pattern to generate quantized coefficients, wherein the quantized coefficients correspond to one of pixels and pixel differences.

5. The process of claim 1, further comprising the step of:

(c) encoding a block of video signals using run-length encoding based on the scan pattern to generate an encoded bitstream.

6. The process of claim 5, wherein step (c) comprises the step of explicitly encoding the scan pattern into the encoded bitstream.

7. The process of claim 5, wherein step (c) comprises the step of run-length encoding quantized coefficients using the scan pattern, wherein the quantized coefficients correspond to one of pixels and pixel differences.

8. The process of claim 1, wherein the energy measures are sums of absolute values of the coefficients.

9. The process of claim 1, wherein step (b) comprises the step of generating the scan pattern according to the relative magnitudes of the energy measures, except, if three or more of the energy measures are within a specified threshold value of each other, then ordering the corresponding three or more coefficients within the scan pattern to minimize distances between subsequent scan points.

10. The process of claim 9, further comprising the step of:

(c) encoding a block of video signals using run-length encoding based on the scan pattern to generate an encoded bitstream, wherein;

the energy measures are sums of absolute values of the coefficients;

the block of step (c) is one of the plurality of blocks of step (a); and

step (c) comprises the steps of;

(1) run-length encoding quantized coefficients using the scan pattern, the quantized coefficients corresponding to one of pixels and pixel differences; and

(2) explicitly encoding the scan pattern into the encoded bitstream.

11. The process of claim 9, further comprising the step of:

(c) decoding a block of encoded video signals of an encoded bitstream using run-length decoding based on the scan pattern to generate decoded video signals, wherein;

the energy measures are sums of absolute values of the coefficients;

the block of step (c) corresponds to one of the plurality of blocks of step (a); and

step (c) comprises the steps of;

(1) decoding the encoded bitstream to determine the scan pattern, wherein the scan pattern is explicitly encoded in the encoded bitstream; and

(2) run-length decoding the block of encoded video signals using the scan pattern to generate quantized coefficients, the quantized coefficients corresponding to one of pixels and pixel differences.

12. An apparatus for processing video signals, comprising:

means for generating energy measures for coefficients of a plurality of blocks of video signals; and

(b) means for applying a constrained sorting rule to the energy measures to generate a scan pattern for run-length encoding.

13. The apparatus of claim 12, further comprising:

(c) means for decoding a block of encoded video signals of an encoded bitstream using run-length decoding based on the scan pattern to generate decoded video signals.

14. The apparatus of claim 13, wherein means (c) decodes the encoded bitstream to determine the scan pattern, wherein the scan pattern is explicitly encoded in the encoded bitstream.

15. The apparatus of claim 13, wherein means (c) run-length decodes the block of encoded video signals using the scan pattern to generate quantized coefficients, wherein the quantized coefficients correspond to one of pixels and pixel differences.

16. The apparatus of claim 12, further comprising:

(c) means for encoding a block of video signals using run-length encoding based on the scan pattern to generate an encoded bitstream.

17. The apparatus of claim 16, wherein means (c) explicitly encodes the scan pattern into the encoded bitstream.

18. The apparatus of claim 16, wherein means (c) run-length encodes quantized coefficients using the scan pattern, wherein the quantized coefficients correspond to one of pixels and pixel differences.

19. The apparatus of claim 12, wherein the energy measures are sums of absolute values of the coefficients.

20. The apparatus of claim 12, wherein means (b) generates the scan pattern according to the relative magnitudes of the energy measures, except, if three or more of the energy measures are within a specified threshold value of each other, then ordering the corresponding three or more coefficients within the scan pattern to minimize distances between subsequent scan points.

21. The apparatus of claim 20, further comprising:

(c) means for encoding a block of video signals using run-length encoding based on the scan pattern to generate an encoded bitstream, wherein;

the energy measures are sums of absolute values of the coefficients;

the block of means (c) is one of the plurality of blocks of means (a); and

means (c);

(1) run-length encodes quantized coefficients using the scan pattern, the quantized coefficients corresponding to one of pixels and pixel differences; and

(2) explicitly encodes the scan pattern into the encoded bitstream.

22. The apparatus of claim 20, further comprising:

(c) means for decoding a block of encoded video signals of an encoded bitstream using run-length decoding based on the scan pattern to generate decoded video signals, wherein;

the energy measures are sums of absolute values of the coefficients;

the block of means (c) corresponds to one of the plurality of blocks of means (a); and

means (c);

(1) decodes the encoded bitstream to determine the scan pattern, wherein the scan pattern is explicitly encoded in the encoded bitstream; and

(2) run-length decodes the block of encoded video signals using the scan pattern to generate quantized coefficients, the quantized coefficients corresponding to one of pixels and pixel differences.

23. A storage medium encoded with machine-readable computer program code for processing video signals, comprising:

(a) means for causing a computer to generate energy measures for coefficients of a plurality of blocks of video signals; and

(b) means for causing the computer to apply a constrained sorting rule to the energy measures to generate a scan pattern for run-length encoding.

24. The storage medium of claim 23, further comprising:

(c) means for causing the computer to decode a block of encoded video signals of an encoded bitstream using run-length decoding based on the scan pattern to generate decoded video signals.

25. The storage medium of claim 24, wherein means (c) causes the computer to decode the encoded bitstream to determine the scan pattern, wherein the scan pattern is explicitly encoded in the encoded bitstream.

26. The storage medium of claim 24, wherein means (c) causes the computer to run-length decode the block of encoded video signals using the scan pattern to generate quantized coefficients, wherein the quantized coefficients correspond to one of pixels and pixel differences.

27. The storage medium of claim 23, further comprising:

(c) means for causing the computer to encode a block of video signals using run-length encoding based on the scan pattern to generate an encoded bitstream.

28. The storage medium of claim 27, wherein means (c) causes the computer to explicitly encode the scan pattern into the encoded bitstream.

29. The storage medium of claim 27, wherein means (c) causes the computer to run-length encode quantized coefficients using the scan pattern, wherein the quantized coefficients correspond to one of pixels and pixel differences.

30. The storage medium of claim 23, wherein the energy measures are sums of absolute values of the coefficients.

31. The storage medium of claim 23, wherein means (b) causes the computer to generate the scan pattern according to the relative magnitudes of the energy measures, except, if three or more of the energy measures are within a specified threshold value of each other, then ordering the corresponding three or more coefficients within the scan pattern to minimize distances between subsequent scan points.

32. The storage medium of claim 31, further comprising:

(c) means for causing the computer to encode a block of video signals using run-length encoding based on the scan pattern to generate an encoded bitstream, wherein;

the energy measures are sums of absolute values of the coefficients;

the block of means (c) is one of the plurality of blocks of means (a); and

means (c) causes the computer to;

(1) run-length encode quantized coefficients using the scan pattern, the quantized coefficients corresponding to one of pixels and pixel differences; and

(2) explicitly encode the scan pattern into the encoded bitstream.

33. The storage medium of claim 31, further comprising:

(c) means for causing the computer to decode a block of encoded video signals of an encoded bitstream using run-length decoding based on the scan pattern to generate decoded video signals, wherein;

the energy measures are sums of absolute values of the coefficients;

the block of means (c) corresponds to one of the plurality of blocks of means (a); and

means (c) causes the computer to;

(1) decode the encoded bitstream to determine the scan pattern, wherein the scan pattern is explicitly encoded in the encoded bitstream; and

(2) run-length decode the block of encoded video signals using the scan pattern to generate quantized coefficients, the quantized coefficients corresponding to one of pixels and pixel differences.

34. A computer-implemented process for encoding video signals, comprising the steps of:

(a) encoding a first set of video signals of a video sequence using run-length encoding based on a first scan pattern to generate a first set of encoded video signals of an encoded bitstream; and

(b) explicitly encoding the first scan pattern into the encoded bitstream.

35. The process of claim 34, further comprising the step of:

(c) encoding a second set of video signals of the video sequence using run-length encoding based on a second scan pattern, different from the first scan pattern, to generate a second set of encoded video signals of the encoded bitstream, wherein;

step (c) comprises the step of explicitly encoding the second scan pattern into the encoded bitstream; and

the first set of video signals corresponds to a first band of a video frame of the video sequence and the second set of video signals corresponds to a second band of the video frame.

36. The process of claim 34, wherein step (a) comprises the step of run-length encoding quantized coefficients using the first scan pattern, wherein the quantized coefficients correspond to one of pixels and pixel differences.

37. The process of claim 34, wherein:

the first set of video signals correspond to a plurality of blocks of video signals; and

step (a) comprises the steps of;

(1) generating energy measures for coefficients of the blocks; and

(2) applying a constrained sorting rule to the energy measures to generate the first scan pattern.

38. The process of claim 37, wherein step (a)(2) comprises the step of generating the first scan pattern according to the relative magnitudes of the energy measures, except, if three or more of the energy measures are within a specified threshold value of each other, then ordering the corresponding three or more coefficients within the first scan pattern to minimize distances between subsequent scan points.

39. The process of claim 38, further comprising the step of:

(c) encoding a second set of video signals of the video sequence using run-length encoding based on a second scan pattern, different from the first scan pattern, to generate a second set of encoded video signals of the encoded bitstream, wherein;

step (c) comprises the step of explicitly encoding the second scan pattern into the encoded bitstream;

the first set of video signals corresponds to a first band of a video frame of the video sequence and the second set of video signals corresponds to a second band of the video frame;

the energy measures are sums of absolute values of the coefficients; and

step (a) comprises the steps of;

(1) generating the first scan pattern to optimize the run-length encoding of the first set of video signals; and

(2) run-length encoding quantized coefficients using the first scan pattern, the quantized coefficients corresponding to one of pixels and pixel differences.

40. An apparatus for encoding video signals, comprising:

(a) means for encoding a first set of video signals of a video sequence using run-length encoding based on a first scan pattern to generate a first set of encoded video signals of an encoded bitstream; and

(b) means for explicitly encoding the first scan pattern into the encoded bitstream.

41. The apparatus of claim 40, further comprising:

(c) means for encoding a second set of video signals of the video sequence using run-length encoding based on a second scan pattern, different from the first scan pattern, to generate a second set of encoded video signals of the encoded bitstream, wherein;

means (c) explicitly encodes the second scan pattern into the encoded bitstream; and

the first set of video signals corresponds to a first band of a video frame of the video sequence and the second set of video signals corresponds to a second band of the video frame.

42. The apparatus of claim 40, wherein means (a) run-length encodes quantized coefficients using the first scan pattern, wherein the quantized coefficients correspond to one of pixels and pixel differences.

43. The apparatus of claim 40, wherein:

the first set of video signals correspond to a plurality of blocks of video signals; and

means (a);

(1) generates energy measures for coefficients of the blocks; and

(2) applies a constrained sorting rule to the energy measures to generate the first scan pattern.

44. The apparatus of claim 43, wherein means (a) generates the first scan pattern according to the relative magnitudes of the energy measures, except, if three or more of the energy measures are within a specified threshold value of each other, then ordering the corresponding three or more coefficients within the first scan pattern to minimize distances between subsequent scan points.

45. The apparatus of claim 44, further comprising:

(c) means for encoding a second set of video signals of the video sequence using run-length encoding based on a second scan pattern, different from the first scan pattern, to generate a second set of encoded video signals of the encoded bitstream, wherein;

means (c) explicitly encodes the second scan pattern into the encoded bitstream;

the first set of video signals corresponds to a first band of a video frame of the video sequence and the second set of video signals corresponds to a second band of the video frame;

the energy measures are sums of absolute values of the coefficients; and

means (a);

(1) generates the first scan pattern to optimize the run-length encoding of the first set of video signals; and

(2) run-length encodes quantized coefficients using the first scan pattern, the quantized coefficients corresponding to one of pixels and pixel differences.

46. A storage medium encoded with machine-readable computer program code for encoding video signals, comprising:

(a) means for causing a computer to encode a first set of video signals of a video sequence using run-length encoding based on a first scan pattern to generate a first set of encoded video signals of an encoded bitstream; and

(b) means for causing the computer to explicitly encode the first scan pattern into the encoded bitstream.

47. The storage medium of claim 46, further comprising:

(c) means for causing the computer to encode a second set of video signals of the video sequence using run-length encoding based on a second scan pattern, different from the first scan pattern, to generate a second set of encoded video signals of the encoded bitstream, wherein;

means (c) causes the computer to explicitly encode the second scan pattern into the encoded bitstream; and

the first set of video signals corresponds to a first band of a video frame of the video sequence and the second set of video signals corresponds to a second band of the video frame.

48. The storage medium of claim 46, wherein means (a) causes the computer to run-length encode quantized coefficients using the first scan pattern, wherein the quantized coefficients correspond to one of pixels and pixel differences.

49. The storage medium of claim 46, wherein:

the first set of video signals correspond to a plurality of blocks of video signals; and

means (a) causes the computer to;

(1) generate energy measures for coefficients of the blocks; and

(2) apply a constrained sorting rule to the energy measures to generate the first scan pattern.

50. The storage medium of claim 49, wherein means (a) causes the computer to generate the first scan pattern according to the relative magnitudes of the energy measures, except, if three or more of the energy measures are within a specified threshold value of each other, then ordering the corresponding three or more coefficients within the first scan pattern to minimize distances between subsequent scan points.

51. The storage medium of claim 50, further comprising:

(c) means for causing the computer to encode a second set of video signals of the video sequence using run-length encoding based on a second scan pattern, different from the first scan pattern, to generate a second set of encoded video signals of the encoded bitstream, wherein;

means (c) causes the computer to explicitly encode the second scan pattern into the encoded bitstream;

the first set of video signals corresponds to a first band of a video frame of the video sequence and the second set of video signals corresponds to a second band of the video frame;

the energy measures are sums of absolute values of the coefficients; and

means (a) causes the computer to;

(1) generate the first scan pattern to optimize the run-length encoding of the first set of video signals; and

(2) run-length encode quantized coefficients using the first scan pattern, the quantized coefficients corresponding to one of pixels and pixel differences.

52. A computer-implemented process for decoding encoded video signals, comprising the steps of:

(a) decoding an encoded bitstream corresponding to a video sequence to determine a first scan pattern, wherein the first scan pattern is explicitly encoded in the encoded bitstream; and

(b) decoding a first set of encoded video signals of the encoded bitstream using run-length decoding based on the first scan pattern to generate a first set of decoded video signals of the video sequence.

53. The process of claim 52, further comprising the step of:

(c) decoding the encoded bitstream to determine a second scan pattern different from the first scan pattern; and

(d) decoding a second set of encoded video signals of the encoded bitstream using run-length decoding based on the second scan pattern to generate a second set of decoded video signals of the video sequence, wherein the first set of encoded video signals corresponds to a first band of a video frame of the video sequence and the second set of video signals corresponds to a second band of the video frame.

54. The process of claim 52, wherein step (b) comprises the step of run-length decoding the first set of encoded video signals using the first scan pattern to generate quantized coefficients, wherein the quantized coefficients correspond to one of pixels and pixel differences.

55. The process of claim 52, wherein:

the first set of encoded video signals correspond to a plurality of blocks of video signals; and

the first scan pattern was generated by;

(1) generating energy measures for coefficients of the blocks; and

(2) applying a constrained sorting rule to the energy measures to generate the first scan pattern.

56. The process of claim 55, wherein the first scan pattern has been generated according to the relative magnitudes of the energy measures, except, if three or more of the energy measures were within a specified threshold value of each other, then the corresponding three or more coefficients have been ordered within the first scan pattern to minimize distances between subsequent scan points.

57. The process of claim 56, further comprising the step of:

(c) decoding the encoded bitstream to determine a second scan pattern different from the first scan pattern; and

(d) decoding a second set of encoded video signals of the encoded bitstream using run-length decoding based on the second scan pattern to generate a second set of decoded video signals of the video sequence, wherein;

the first set of encoded video signals corresponds to a first band of a video frame of the video sequence and the second set of video signals corresponds to a second band of the video frame;

step (b) comprises the step of run-length decoding the first set of encoded video signals using the first scan pattern to generate quantized coefficients, the quantized coefficients corresponding to one of pixels and pixel differences;

the first scan pattern has been generated to optimize the run-length encoding of the first set of encoded video signals; and

the energy measures are sums of absolute values of the coefficients.

58. An apparatus for decoding encoded video signals, comprising:

(a) means for decoding an encoded bitstream corresponding to a video sequence to determine a first scan pattern, wherein the first scan pattern is explicitly encoded in the encoded bitstream; and

(b) means for decoding a first set of encoded video signals of the encoded bitstream using run-length decoding based on the first scan pattern to generate a first set of decoded video signals of the video sequence.

59. The apparatus of claim 58, further comprising:

(c) means for decoding the encoded bitstream to determine a second scan pattern different from the first scan pattern; and

(d) means for decoding a second set of encoded video signals of the encoded bitstream using run-length decoding based on the second scan pattern to generate a second set of decoded video signals of the video sequence, wherein the first set of encoded video signals corresponds to a first band of a video frame of the video sequence and the second set of video signals corresponds to a second band of the video frame.

60. The apparatus of claim 58, wherein means (b) run-length decodes the first set of encoded video signals using the first scan pattern to generate quantized coefficients, wherein the quantized coefficients correspond to one of pixels and pixel differences.

61. The apparatus of claim 58, wherein:

the first set of encoded video signals correspond to a plurality of blocks of video signals; and

the first scan pattern was generated by;

(1) generating energy measures for coefficients of the blocks; and

(2) applying a constrained sorting rule to the energy measures to generate the first scan pattern.

62. The apparatus of claim 61, wherein the first scan pattern has been generated according to the relative magnitudes of the energy measures, except, if three or more of the energy measures were within a specified threshold value of each other, then the corresponding three or more coefficients have been ordered within the first scan pattern to minimize distances between subsequent scan points.

63. The apparatus of claim 62, further comprising:

(c) means for decoding the encoded bitstream to determine a second scan pattern different from the first scan pattern; and

(d) means for decoding a second set of encoded video signals of the encoded bitstream using run-length decoding based on the second scan pattern to generate a second set of decoded video signals of the video sequence, wherein;

the first set of encoded video signals corresponds to a first band of a video frame of the video sequence and the second set of video signals corresponds to a second band of the video frame;

means (b) run-length decodes the first set of encoded video signals using the first scan pattern to generate quantized coefficients, the quantized coefficients corresponding to one of pixels and pixel differences;

the first scan pattern has been generated to optimize the run-length encoding of the first set of encoded video signals; and

the energy measures are sums of absolute values of the coefficients.

64. A storage medium encoded with machine-readable computer program code for decoding encoded video signals, comprising:

(a) means for causing a computer to decode an encoded bitstream corresponding to a video sequence to determine a first scan pattern, wherein the first scan pattern is explicitly encoded in the encoded bitstream; and

(b) means for causing the computer to decode a first set of encoded video signals of the encoded bitstream using run-length decoding based on the first scan pattern to generate a first set of decoded video signals of the video sequence.

65. The storage medium of claim 64, further comprising:

(c) means for causing the computer to decode the encoded bitstream to determine a second scan pattern different from the first scan pattern; and

(d) means for causing the computer to decode a second set of encoded video signals of the encoded bitstream using run-length decoding based on the second scan pattern to generate a second set of decoded video signals of the video sequence, wherein the first set of encoded video signals corresponds to a first band of a video frame of the video sequence and the second set of video signals corresponds to a second band of the video frame.

66. The storage medium of claim 64, wherein means (b) causes the computer to run-length decode the first set of encoded video signals using the first scan pattern to generate quantized coefficients, wherein the quantized coefficients correspond to one of pixels and pixel differences.

67. The storage medium of claim 64, wherein:

the first set of encoded video signals correspond to a plurality of blocks of video signals; and

the first scan pattern was generated by;

(1) generating energy measures for coefficients of the blocks; and

(2) applying a constrained sorting rule to the energy measures to generate the first scan pattern.

68. The storage medium of claim 67, wherein the first scan pattern has been generated according to the relative magnitudes of the energy measures, except, if three or more of the energy measures were within a specified threshold value of each other, then the corresponding three or more coefficients have been ordered within the first scan pattern to minimize distances between subsequent scan points.

69. The storage medium of claim 68, further comprising:

(c) means for causing the computer to decode the encoded bitstream to determine a second scan pattern different from the first scan pattern; and

(d) means for causing the computer to decode a second set of encoded video signals of the encoded bitstream using run-length decoding based on the second scan pattern to generate a second set of decoded video signals of the video sequence, wherein;

the first set of encoded video signals corresponds to a first band of a video frame of the video sequence and the second set of video signals corresponds to a second band of the video frame;

means (b) causes the computer to run-length decode the first set of encoded video signals using the first scan pattern to generate quantized coefficients, the quantized coefficients corresponding to one of pixels and pixel differences;

the first scan pattern has been generated to optimize the run-length encoding of the first set of encoded video signals; and

the energy measures are sums of absolute values of the coefficients.