Method and apparatus for compression and decompression of still and motion video data based on adaptive pixel-by-pixel processing and adaptive variable length coding

• US 6,339,616 B1
• Filed: 05/30/1997
• Issued: 01/15/2002
• Est. Priority Date: 05/30/1997
• Status: Expired due to Term

• Current Assignee: XVD Technology Holdings Ltd.
• Original Assignee: Alaris, Inc., GT Technologies
• Inventors: Kovalev, Sergey I.
• Primary Examiner(s): Le, Vu
• Application Number:
  US08/866,193
• Time in Patent Office: 1,691 Days
• Field of Search: H04/N.730, H04/N.732, 348/400-467, 348/407-413, 348/415-416, 348/384, 348/390, 348/699, 348/700, 348/571, 382/237, 382/246, 382/248, 386/109, 386/111-112, 375/240.16, 375/240.17
• US Class Current: 375/240.16
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation

Abstract

A method and apparatus for pixel-by-pixel motion and/or still video data compression and decompression. Each pixel may be encoded as static, new, or direcionally estimated. Directionally estimated pixels are encoded with a value corresponding to a direction in a reduced set of substantially unique directions, wherein each direction may correspond to one or a combination of pixels. Directionally estimated pixels are further encoded using an adaptive variable length code (VLC), while static pixels and new pixels are encoded using run-lenth (RL) coding and delta coding techniques, respectively. Performance parameters, such as compression ratio, quality, etc., may be monitored to dynamically and adaptively update compression thresholds. Pixel processing may be performed in a plurality of directions to improve performance.

Claims

1. A computer implemented data compression method comprising:

determining a direction from a plurality of directions for encoding a single pixel in a current frame of a motion video sequence, said plurality of directions identifying pixels in a previously processed frame and previously processed pixels of said current frame, wherein the determining of the direction from the plurality of directions for encoding the single pixel is independent of determinations of directions for encoding other pixels in the current frame of the motion video sequence;

encoding said single pixel based on said direction, where the encoding of the single pixel is independent of encoding of other pixels in the current frame of the motion video sequence.

2. The method of claim 1 further comprising:

selecting a reduced set of directions from said plurality of directions, wherein all pixels identified by directions included in said reduced set of directions are unique relative to each other according to a predetermined threshold.

3. The method of claim 2, wherein said encoding further includes:

selecting a first of a set of variable length codes (VLCs) each having a different number of states, wherein the number of states in the first of said set of VLCs equals the number of directions in said reduced set of directions; and

encoding said single pixel with said first of said set of variable length codes.

4. The method of claim 1, wherein pixels in said current frame are processed in a first direction, and pixels in another frame in said sequence of motion video frames are processed in a second direction, said second direction being different from said first direction.

5. The method of claim 1, wherein said determining and said encoding is performed according to a pixel-by-pixel compression technique.

6. A machine-implemented pixel-by-pixel data compression method for encoding data representing a single pixel in an image, said method comprising:

reducing a plurality of directions into a reduced set of directions, said plurality of directions identifying pixels, wherein all pixels identified by directions included in said reduced set of directions are unique relative to each other according to a predetermined threshold;

determining a direction in said reduced set of directions that sufficiently approximates said single pixel, wherein the determining of the direction in said reduced set of directions that sufficiently approximates said single pixel is independent of determinations of directions for other pixels in the current frame of the motion video sequence; and

encoding said single pixel based on said direction, where the encoding of the single pixel is independent of encoding of other pixels in the current frame of the motion video sequence.

7. The method of claim 6, wherein said image represents either a still or motion image frame.

8. The method of claim 6, wherein said image represents a current frame in a sequence of motion video frames.

9. The method of claim 8, wherein the pixels identified by said plurality of directions belong to at least one of said current frame and another frame in said sequence of motion video frames.

10. The method of claim 6, wherein said encoding includes:

selecting a first variable length code for encoding said single pixel based on said reduced set of directions, said first variable length code having a first number of states that is equal to the number of directions in said reduced set of directions; and

encoding said single pixel using said first variable length code.

11. The method of claim 10, further comprising:

generating a second variable length code for encoding another pixel in said image, said second variable length code having a second number of states, said second number of states being unequal to said first number of states in said first variable length code and being based on another set of directions.

12. An apparatus for performing data compression comprising:

a first means for determining a direction from a plurality of directions for encoding a single pixel in a current frame of a motion video sequence, said plurality of directions identifying at least one pixel in a previously processed frame and at least one previously processed pixel of said current frame, wherein the determining of the direction from the plurality of directions for encoding the single pixel is independent of determinations of directions for encoding other pixels in the current frame of the motion video sequence;

a second means for encoding said single pixel based on said direction, where the encoding of the single pixel is independent of encoding of other pixels in the current frame of the motion video sequence.

13. The apparatus of claim 12, further comprising:

a selection means for selecting a reduced set of directions from said plurality of directions, wherein all pixels identified by directions in said reduced set of directions are unique relative to each other according to a predefined threshold.

14. The apparatus of claim 13, further comprising:

a third means for selecting a first of a set of variable length codes (VLCs) each having a different number of states, wherein the number of states in said first of said set of VLCs equals the number of directions in said reduced set of directions.

15. The apparatus of claim 12, further comprising:

a third means for processing said current frame in a first pixel processing direction and another frame in a second pixel processing direction, wherein said first and second pixel processing directions are different.

16. The apparatus of claim 12, wherein said first and second means perform a pixel-by-pixel compression technique.

17. A machine-readable medium having stored thereon executable data that cause a machine to perform a method comprising:

determining a direction from a plurality of directions for encoding a single pixel in a current frame of a motion video sequence, said plurality of directions identifying at least one pixel in a previously processed frame and at least one previously processed pixel of said current frame, wherein the determining of the direction from the plurality of directions for encoding the single pixel is independent of determinations of directions for encoding other pixels in the current frame of the motion video sequence;

encoding said single pixel based on said direction, where the encoding of the single pixel is independent of encoding of other pixels in the current frame of the motion video sequence.

18. The machine-readable medium of claim 17, said method further comprising:

selecting a reduced set of directions from said plurality of directions, wherein pixels identified by directions in said reduced set of directions are unique relative to each other according to a predefined threshold.

19. The machine-readable medium of claim 18, said method further comprising:

selecting a first of a set of variable length codes (VLCs) each having a different number of states, wherein the number of states in said first of said set of VLCs equals the number of directions in said reduced set of directions.

20. The machine-readable medium of claim 17, said method further comprising:

processing said current frame in a first pixel processing direction and another frame in a second pixel processing direction, wherein said first and second pixel processing directions are different.

21. The machine-readable medium of claim 17, wherein said encoding is performed according to a pixel-by-pixel compression technique.

22. An apparatus for pixel-by-pixel encoding of data representing a single pixel in an image, said apparatus comprising:

a first means for reducing a plurality of directions into a reduced set of directions, said plurality of directions identifying pixels, wherein all pixels identified by directions included in said reduced set of directions are unique relative to each other according to a predefined threshold;

a second means for determining a direction in said reduced set of directions that sufficiently approximates said single pixel, wherein the second means for determining of the direction in said reduced set of directions that sufficiently approximates said single pixel is independent of determinations of directions for other pixels in the current frame of the motion video sequence; and

a third means for encoding said single pixel based on said direction, where the third means for encoding of the single pixel is independent of encoding of other pixels in the current frame of the motion video sequence.

23. The apparatus of claim 22, wherein said image represents one of a still image frame and a motion image frame.

24. The apparatus of claim 22, wherein at least one of said pixels identified by said plurality of directions is derived from said image, said image being a first frame in a motion image sequence, and at least another of said pixels identified by said plurality of directions is derived from a second frame in said motion video sequence.

25. The apparatus of claim 24, further comprising:

a fourth means for processing said first frame in a first pixel processing direction and said second frame in a second pixel processing direction, wherein said first and second pixel processing directions are different.

26. The apparatus of claim 22, further comprising:

a code selection means for selecting one of a plurality of variable length codes (VLCs) for encoding pixels of said image, wherein each selected one of said plurality of VLCs has a number of states equal to the number of directions used to encode a particular one of said pixels.

27. A machine-readable medium having stored thereon executable data that cause a machine to perform a method comprising:

reducing a plurality of directions into a reduced set of directions, said plurality of directions identifying pixels, wherein all pixels identified by directions included in said reduced set of directions are unique relative to each other according to a predefined threshold;

determining a direction in said reduced set of directions that sufficiently approximates a single pixel, wherein the determining of the direction in said reduced set of directions that sufficiently approximates the single pixel is independent of determinations of directions for other pixels in the current frame of the motion video sequence; and

encoding said single pixel based on said direction, where the encoding of the single pixel is independent of encoding of other pixels in the current frame of the motion video sequence.

28. A machine-implemented decompression method comprising:

receiving an indication indicating a direction of a plurality of directions for decoding a single pixel in a current frame of a motion video sequence, said plurality of directions identifying pixels in a previously processed frame and previously processed pixels of said current frame, wherein the direction of said plurality of directions is determined independent of determinations of directions for other pixels in the current frame of the motion video sequence; and

decoding said single pixel based on said direction.

29. The method of claim 28, wherein pixels identified by directions in said plurality of directions are unique relative to each other according to a predefined threshold.

30. The method of claim 29, further comprising:

decoding said pixel according to a first of a set of variable length codes (VLCs) each having a different number of states, wherein the number of states in said first of said set of VLCs equals the number of directions in said plurality of directions.

31. The method of claim 28, further comprising:

processing said current frame in a first pixel processing direction and another frame in a second pixel processing direction, wherein said first and second pixel processing directions are different.

32. The method of claim 28, wherein said receiving and decoding is performed according to a pixel-by-pixel compression technique.

33. An apparatus for decoding encoded data comprising:

a first means for receiving an indication indicating a direction of a plurality of directions for decoding a single pixel in a current frame of a motion video sequence, said plurality of directions identifying pixels in a previously processed frame and previously processed pixels of said current frame, wherein the direction of said plurality of directions is determined independent of determinations of directions for other pixels in the current frame of the motion video sequence; and

a second means for decoding said single pixel based on said direction.

34. The apparatus of claim 33, wherein pixels identified by directions in said plurality of directions are unique relative to each other according to a predefined threshold.

35. The apparatus of claim 34, further comprising:

a decoding means for decoding said single pixel according to a first of a set of variable length codes (VLCs) each having a different number of states, wherein the number of states in said first of said set of VLCs equals the number of directions in said reduced set of directions.

36. The apparatus of claim 33, further comprising:

a third means for processing said current frame in a first pixel processing direction and another frame in a second pixel processing direction, wherein said first and second pixel processing directions are different.

37. The apparatus of claim 33, wherein said first and second means perform a pixel-by-pixel compression technique.

38. An image data compression method comprising:

receiving information representing a single pixel in a current frame of a motion video sequence;

selecting a direction from plurality of directions to encode said single pixel in said current frame, said plurality of directions specifying a set of encoding pixels, said set of encoding pixels being individual ones and/or combinations of a set of actual pixels, said set of actual pixels including at least one pixel in a previously processed frame and at least one previously processed pixel of said current frame, wherein the selecting of the direction from the plurality of directions to encode said single pixel in said current frame is independent of selections of directions to encode other pixels in the current frame; and

encoding said single pixel with an indication identifying said direction, where the encoding of said single pixel is independent of encoding of other pixels in the current frame.

39. The method of claim 38, further comprising:

outputting said indication.

40. The method of claim 38, further comprising:

storing said indication.

41. The method of claim 38, further comprising:

determining a reduced set of directions from said plurality of directions, wherein encoding pixels identified by directions in said reduced set of directions are unique relative to each other according to a predefined threshold.

42. The method of claim 38, further comprising:

selecting a first of a set of variable length codes (VLCs) each having a different number of states, where in the number of states in said first of said set of VLCs equals the number of directions in said reduced set of directions.

43. The method of claim 38, further comprising:

processing said cur rent frame in a first pixel processing direction; and

processing another frame in said motion video sequence in a second pixel processing direction, wherein said first and second pixel processing directions are different.

44. A data compression method for pixel-by-pixel encoding data representing a single pixel in an image, said method comprising:

determining a plurality of directions to encode said single pixel, wherein at least one of said plurality of directions corresponds to another pixel in said image;

reducing said plurality of directions into a reduced set of directions, wherein data corresponding to each direction included in said reduced set of directions is unique relative to each other according to a predefined threshold, wherein the determining of the direction of the plurality of directions to encode said single pixel is independent of determinations of directions to encode other pixels in said image;

selecting a direction in said reduced set of directions that sufficiently approximates said single pixel; and

encoding said single pixel based on said direction, where the encoding of said single pixel is independent of encoding of other pixels in said image.

45. The method of claim 44, further comprising:

including in said plurality of directions at least one direction that represents a combination of two pixels.

46. The method of claim 45, wherein a first of said combination of two pixels is contained in a current frame representing said image, and a second of said combination of two pixels is contained in another frame.

47. The method of claim 45, wherein both of said combination of two pixels are contained in said image.

48. The method of claim 44, wherein said image represents one of a still image frame and a motion image frame.

49. The method of claim 44, wherein said image is a first frame in a motion image sequence, and at least another of said pixels identified by said plurality of directions is derived from a second frame in said motion video sequence.

50. The method of claim 49, further comprising:

processing said first frame in a first pixel processing direction and said second frame in a second pixel processing direction, wherein said first and second pixel processing directions are different.

51. The method of claim 44, further comprising:

selecting a code from a plurality of codes to encode said single pixel, said code including a number of states corresponding to a number of directions in said reduced set of directions.

52. A computer-implemented method comprising:

selecting as part of a pixel-by-pixel compression technique a direction for encoding a single pixel in an image being compressed, wherein part of said image has already been encoded, and wherein said direction identifies a previously encoded pixel of said image or a combination of pixels that includes said previously encoded pixel of said image, wherein said selecting includes selecting said direction from a plurality of directions, said plurality of directions specifying a set of encoding pixels, said set of encoding pixels being individual ones and/or combinations of a set of actual pixels, said set of actual pixels including at least one pixel in a previously processed frame and at least one previously processed pixel of said current frame, wherein the selecting of the direction for encoding the single pixel is independent of selecting directions for encoding other pixels in said image; and

encoding said single pixel based on said direction, where the encoding of said single pixel is independent of encoding of other pixels in said image.

53. The computer-implemented method of claim 52, wherein said selecting includes:

selecting said direction from a plurality of directions, wherein each of said plurality of directions identifies a different pixel or combination of pixels.

54. The computer implemented method of claim 52, wherein said image is a still image.

55. The computer implemented method of claim 52, wherein said image is a current frame in a motion video sequence.

56. The computer-implemented method of claim 55, wherein said selecting said direction includes:

selecting a reduced set of directions from said plurality of directions, wherein all encoding pixels identified by directions included in said reduced set of directions are unique relative to each other according to a predetermined threshold.

57. The computer-implemented method of claim 56 further comprising:

selecting a first of a set of variable length codes (VLCs) each having a different number of states, wherein the number of states in the first of said set of VLCs equals the number of directions in said reduced set of directions; and

wherein said encoding is performed with said first variable length codes.

58. The computer-implemented method of claim 52, wherein said selecting includes:

selecting said direction from a plurality of directions, wherein at least one of said plurality of directions identifies a combination of actual pixels.

59. A machine-readable medium having stored therein executable data that cause a machine to perform a method comprising:

selecting as part of a pixel-by-pixel compression technique a direction for encoding a single pixel in an image being compressed, wherein part of said image has already been encoded, and wherein said direction identifies a previously encoded pixel of said image or a combination of pixels that includes said previously encoded pixel of said image, wherein said selecting includes selecting said direction from a plurality of direction, said plurality of directions specifying a set of encoding pixels, said set of encoding pixels being individual ones and/or combinations of a set of actual pixels, said set of actual pixels including at least one pixel in a previous frame and at least one previously processed pixel of said current frame, wherein the selecting of the direction for encoding the single pixel in the image is independent of selecting directions for encoding other pixels in said image; and

encoding said single pixel based on said direction, where the encoding of said single pixel is independent of encoding of other pixels in said image.

60. The machine readable medium of claim 59, wherein said selecting includes:

selecting said direction from a plurality of directions, wherein each of said plurality of directions identifies a different pixel or combination of pixels.

61. The machine-readable medium of claim 60, wherein said image is a current frame in a motion video sequence.

62. The machine readable medium of claim 59, wherein said image is a still image.

63. The machine-readable medium of claim 62, wherein said selecting said direction includes:

selecting a reduced set of directions from said plurality of directions, wherein all pixels identified by directions included in said reduced set of directions are unique relative to each other according to a predetermined threshold.

64. The machine-readable medium of claim 63 further comprising:

selecting a first of a set of variable length codes (VLCs) each having a different number of states, wherein the number of states in the first of said set of VLCs equals the number of directions in said reduced set of directions; and

wherein said encoding is performed with said first variable length code.

65. The machine-readable medium of claim 59, wherein said image is a current frame in a motion video sequence.

66. The machine-readable medium of claim 59, wherein said selecting includes:

selecting said direction from a plurality of directions, wherein at least one of said plurality of directions identifies a combination of actual pixels.

67. A method comprising:

accessing pixel data at a current single pixel location in a current frame of a motion video sequence as part of a pixel-by-pixel compression technique, wherein there is a pixel location in a composite frame that is in the same spatial location as said current single pixel location in said current frame, said composite frame comprising a processed pixel region and a base pixel region, said processed pixel region surrounding part of said current single pixel location and including the result of decoding previously encoded pixels from said current frame, said base pixel region surrounding part of said current pixel location and including the result of decoding previously encoded pixels from a previous frame;

selecting an indication that identifies pixel data in said composite frame that best matches the pixel data at said current single pixel location in said current frame, wherein the selecting of the indication is independent of selecting the indications for pixel data at other pixel locations in said current frame; and

encoding said indication, where the encoding of said indication is independent of encoding of other indications for in said current frame.

68. The method of claim 67, wherein said selecting includes:

comparing said pixel data accessed from said current frame to pixels and/or combinations of pixels surrounding said current pixel location in said composite frame.

69. The method of claim 67, wherein said selecting includes:

comparing said pixel data accessed from said current frame to at least one piece of pixel data generated from combining pixel data from two different pixel locations in said composite frame surrounding said current pixel location.

70. An apparatus comprising:

a set of one or more frame buffers;

a pixel classification unit coupled to said set of frame buffers to separately classify individual pixels of a current frame as static, new, or directionally estimated in relation to a composite frame, said composite frame formed by starting with a base frame and overwriting pixels with the result of decoding previously encoded pixels from the current frame on the fly;

a encoding unit coupled to said pixel classification unit to separately encode individual pixels of said current frame according to said classifications in relation to said composite frame, wherein the encoding unit is to separately encode each pixel of the individual pixels independent of other individual pixels in said current frame; and

a multiplexing unit coupled to said encoding unit.

71. The apparatus of claim 70, said set of frame buffers to store said composite base frame and said current frame.

72. The apparatus of claim 70, wherein said encoding unit includes:

a run-length encoder to encode pixels classified as static;

a variable length encoder to encode pixels classified as directionally estimated; and

a delta value encoder to encode pixels classified as new.

73. An apparatus comprising:

a set of one or more frame buffers to store a current frame and a composite base frame, said composite base frame starting as the result of decoding an encoded previous frame and being updated on the fly with the result of decoding encoded pixels of the current frame;

a pixel classification unit coupled to said set of frame buffers to individually select on a pixel-by-pixel basis a direction from a plurality of directions for encoding pixels in said current frame, said plurality of directions identifying pixel data that is based on pixels at pixel locations in said composite base frame at and surrounding the current pixel location in said current frame being encoded;

a encoding unit coupled to said pixel classification unit to separately encode individual pixels of said current frame according to said directions, wherein the encoding unit is to separately encode each pixel of the individual pixels independent of other individual pixels in said current frame; and

a multiplexing unit coupled to said encoding unit.

74. The apparatus of claim 73, wherein said plurality of directions can identify at least one pixel location in said composite frame storing a decoded version of a previously encoded pixel from said current frame.

75. The apparatus of claim 73, said pixel classification unit to reduce the plurality of directions to include only directions that identify pixels unique relative to each other according to a predetermined threshold.

76. The apparatus of claim 73, wherein said encoding unit includes:

a run-length encoder to encode pixels whose direction indicates those pixels are static;

a variable length encoder to encode pixels whose direction indicates those pixels best match one or more pixels at different spatial locations in said composite base frame; and

a delta value encoder to encode pixels whose direction indicates those pixels are sufficiently different from the pixel values identified by the plurality of directions.