Method and apparatus for real time compression and decompression of a digital motion video signal using a fixed Huffman table

• US 5,329,313 A
• Filed: 10/01/1993
• Issued: 07/12/1994
• Est. Priority Date: 04/01/1992
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Keith, Michael
• Primary Examiner(s): Chin, Tommy P.
• Assistant Examiner(s): LIN, BRYAN T
• Application Number:
  US08/131,017
• Time in Patent Office: 284 Days
• Field of Search: 358/133, 358/135, 358/136, 358/105, 348/384, 348/390, 348/422
• US Class Current: 375/240.22
• CPC Class Codes: H04N 19/00 Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
• 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/503 involving temporal prediction adaptive coding with adaptive selection between spatial and temporal predictive coding H04N19/107; adaptive coding with adaptive selection among a plurality of temporal predictive coding modes H04N19/109
• CPC Class Codes: H04N 19/507 using conditional replenishment
• CPC Class Codes: H04N 19/60 using transform coding
• 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
• CPC Class Codes: H04N 19/94 Vector quantisation

Abstract

A bitstream representative of at least one digital video image is decoded in real time by providing a code-book index from the bitstream, applying the code-book index to an index table to determine an index value, and comparing the index value to a first predetermined threshold. A single fixed statistical table is used for a plurality of images. If the index value is greater than the predetermined threshold, then at least one current pixel is determined by copying a corresponding previous pixel into the location of at least one current pixel; otherwise the index value is applied to a vector table to determine at least one vector value and a current pixel is determined from the vector value and a corresponding previous pixel. A digital video image is encoded in real time by selecting at least one pixel for encoding and determining at least one difference value between the selected pixel and at least one corresponding previous pixel. An index value corresponding to the location in a table of the difference value is calculated. If the index value is equal to a first predetermined value then a run-length counter is incremented by a second predetermined value and the process is repeated until the index value is not equal to the first predetermined value. The run-length counter is then encoded. If the index value is not equal to the first predetermined value then the index value is encoded.

Claims

1. A method for forming in real time a compressed digital video signal representative of a plurality of compressed digital video images from an analog video signal representative of a plurality of uncompressed digital video images, said compressed digital signal being formed from a bitstream representing a plurality of encoded digital video images, said plurality of uncompressed digital video images being formed from arrays of pixels representing a plurality of motion video images, comprising the steps of:

(a) selecting a training set formed of a plurality of video training images;

(b) determining a set of variable-length codes in accordance with said training set and forming a single fixed lookup table in accordance with said set of variable-length codes;

(c) converting said analog video signal to said plurality of uncompressed digital video images;

(d) selecting a plurality of pixels from said plurality of uncompressed digital video images for compression;

(e) determining a plurality of locations within said single fixed lookup table by applying information representative of said plurality of pixels to said single fixed lookup table; and

(f) converting information representative of said plurality of locations into said bitstream and forming said compressed digital video signal representative of said plurality of compressed digital video images from said bitstream.

2. The method of claim 1, wherein step (e) further comprises the steps of:

(1) determining at least one difference value between a pixel from said plurality of pixels and at least one corresponding previous pixel;

(2) calculating an index value corresponding to said at least one difference value;

(3) if said index value is equal to a first predetermined value then

(i) incrementing a run-length counter by a second predetermined value;

(ii) repeating steps (1)-(2)(i) until said index value is not equal to said predetermined value;

(iii) incrementing said run-length counter by a third predetermined value;

(iv) encoding said run-length counter by determining a corresponding location in said single fixed lookup table; and

(4) if said index value is not equal to said first predetermined value then encoding said index value by determining a corresponding location in said single fixed lookup table.

3. The method of claim 2, wherein said first predetermined value is zero.

4. The method of claim 2, wherein step (e) comprises the steps of:

(i) determining a first difference value between a first pixel from said plurality of pixels and a first corresponding previous pixel;

(ii) determining a second difference value between a second pixel from said plurality of pixels and a second corresponding previous pixel; and

step (e2) comprises quantizing said first and second difference values into an index value corresponding to the location of said first difference value in a first table, wherein said first and second difference values are adjacent to each other in said first table.

5. The method of claim 1, in a processing system for receiving and processing input video data wherein steps (a) and (b) are preformed independently of said processing system prior to said receiving of said input video data and steps (c)-(f) are performed upon said input video data by said processing system after said receiving of said input video data.

6. The method of claim 1, wherein step (b) comprises providing a table representative of statistical information about said video images of said training set.

7. The method of claim 1, wherein said plurality of uncompressed digital video images differ from said training images.

8. The method of claim 1, wherein said plurality of pixels resides in memory.

9. A method for forming an analog motion video signal representative of a plurality of decompressed digital video images from a compressed digital video signal formed from a bitstream representing a plurality of encoded digital video images, said plurality of decompressed digital video images being formed from arrays of pixels representing a plurality of motion video images, comprising the steps of:

(a) determining a set of variable-length codes in accordance with a training set formed of a plurality of video training images and forming a single fixed lookup table in accordance with said set of variable-length codes;

(b) applying bits from said bitstream to said single fixed lookup table until a code-book index is recognized;

(c) determining the value of at least one decompressed pixel in accordance with said code-book index;

(d) forming said plurality of decompressed digital video images by repeating steps (b)-(c); and

(e) converting said plurality of decompressed digital video images into said analog motion video signal.

10. The method of claim 9, wherein step (c) comprises the steps of:

(i) obtaining an index value by applying said code-book index to an index table;

(ii) comparing said index value to a predetermined threshold;

(iii) determining at least one current pixel by copying a corresponding previous pixel into the location of said at least one current pixel if said index value is greater than said a predetermined threshold; and

(iv) obtaining at least one vector value by applying said index value to a vector table and determining said at least one current pixel from said at least one vector value and said corresponding previous pixel if said index value is not greater than said predetermined threshold.

11. The method of claim 10, wherein said corresponding previous pixel is positioned directly above said at least one current pixel.

12. The method of claim 10, wherein said corresponding previous pixel is in a frame preceding said at least one current pixel.

13. The method of claim 10, wherein step (f) further comprises the steps of:

(a) selecting a vector table from a plurality of vector tables; and

(b) applying said index value to said selected vector table to determine said at least one vector value.

14. The method of claim 9, in a processing system for receiving and processing input video data wherein step (a) is preformed independently of said processing system prior to said receiving of said input digital video data and steps (b)-(e) are performed upon said input digital video data by said processing system after said receiving of said input digital video data.

15. The method of claim 9, wherein said single fixed lookup table is representative of statistical information about said video images of said training set.

16. The method of claim 9, wherein said one or more uncompressed digital video images differ from said training images.

17. The method of claim 10, wherein said at least one current pixel resides in memory.

18. An apparatus for forming in real time a compressed digital video signal representative of a plurality of compressed digital video images from an analog video signal representative of a plurality of uncompressed digital video images, said compressed digital signal being formed from a bitstream representing a plurality of encoded digital video images, said plurality of uncompressed digital video images being formed from arrays of pixels representing a plurality of motion video images, comprising:

a digital processor, said digital processor being adapted for coupling to a converter for converting said analog motion video signal into said plurality of uncompressed digital video images, said digital processor including;

(a) means for selecting a training set formed of a plurality of video training images;

(b) means for determining a set of variable-length codes in accordance with said training set and means for forming a single fixed lookup table in accordance with said set of variable-length codes;

(c) means for selecting a plurality of pixels from said plurality of uncompressed digital video images for compression;

(d) means for determining a plurality of locations within said single fixed lookup table by applying information representative of said plurality of pixels to said single fixed lookup table; and

;

(e) means for converting information representative of said plurality of locations into said bitstream and means for forming said compressed digital video signal representative of said plurality of compressed digital video images from said bitstream.

19. The apparatus of claim 18, further comprising;

(f) means for determining at least one difference value between a pixel from said plurality of pixels and at least one corresponding previous pixel;

(g) means for calculating an index value corresponding to said at leas tone difference value;

(h) means for incrementing a run-length counter by a second predetermined value if said index value is equal to a first predetermined value;

(i) means for encoding said run-length counter if said index value is equal to a first predetermined value by determining a corresponding location in said single fixed lookup table; and

(j) means for encoding said index value if said index value is not equal to said first predetermined value by determining a corresponding location in said single fixed lookup table.

20. The apparatus of claim 19, wherein said first predetermined value is zero.

21. The apparatus of claim 19, wherein said means for selecting a plurality of pixels comprises means for selecting first and second pixels from said plurality of uncompressed digital video images for compression, said means for determining at least one difference value comprises:

(1) means for determining a first difference value between said first pixel and a first corresponding previous pixel;

(2) means for determining a second difference value between said second pixel and a second corresponding previous pixel; and

said means for calculating said index value comprises means for quantizing said first and second difference values into an index value corresponding to the location of said first difference value in a first table, wherein said first and second difference values are adjacent to each other in said first table.

22. The apparatus of claim 18, wherein said single fixed lookup table is representative of statistical information about said video images of said training set.

23. The apparatus of claim 18, wherein said plurality of uncompressed digital video images differ from said training images.

24. The apparatus of claim 18, wherein said digital processor has memory associated therewith, said plurality of pixels from said plurality of uncompressed digital video images residing in said memory.

25. An apparatus for forming an analog video signal representative of a plurality of decompressed digital video images from a compressed digital video signal formed from a bitstream representing a plurality of encoded digital video images, said plurality of decompressed digital video images being formed from arrays of pixels representing a plurality of motion video images, comprising:

a digital processor, said digital processor including;

(a) means for determining a set of variable-length codes in accordance with a training set formed of a plurality of video training images and means for forming a single fixed lookup table in accordance with said set of variable-length codes;

(b) means for applying bits from said bitstream to said single fixed lookup table until a code-book index is recognized;

(c) means, coupled to said means for applying, for determining the values of a plurality of decompressed pixels in accordance with a plurality of code-book index values; and

(d) means for forming said plurality of decompressed digital video images from said decompressed pixels, wherein said digital processor is adapted for coupling to a converter for converting said plurality of decompressed digital video images into said analog motion video signal.

26. The apparatus of claim 25, wherein said means for determining further comprises:

(i) means for obtaining an index value by looking up said code-book index in an index table;

(ii) means for determining at least one current pixel by copying a corresponding previous pixel into the location of said at least one current pixel if said index value is greater than a predetermined threshold; and

(iii) means for obtaining at least one vector value by looking up said index value in a vector table and determining said at least one current pixel from said at least one vector value and said corresponding previous pixel if said index value is not greater than said predetermined threshold.

27. The apparatus of claim 26, wherein said corresponding previous pixel is positioned directly above said at least one current pixel.

28. The apparatus of claim 26, wherein said corresponding previous pixel is in a frame preceding said at least one current pixel.

29. The apparatus of claim 26, wherein said means for obtaining at least one vector value further comprises:

(a) means for selecting a vector table from a plurality of vector tables; and

(b) means for applying said index value to said selected vector table to determine said at least one vector value.

30. The apparatus of claim 25, wherein said digital processor has memory associated therewith, said plurality of decompressed pixels residing in said memory.

31. The apparatus of claim 25, wherein said single fixed lookup table is representative of statistical information about said video images of said training set.

32. The apparatus of claim 25, wherein said plurality of decompressed digital video images differ from said training images.

33. A system for forming an output digital video signal representative of one or more decompressed digital video images for an input digital video signal representative of one or more compressed digital video images comprising:

(a) means for providing a single fixed lookup table in accordance with a training set formed of a plurality of video training images, said single fixed lookup table being representative of the video training images of said training set;

(b) input means for receiving said input digital video signal;

(c) a digital processor coupled to said input means, said digital processor having decompressing means for forming said one or more decompressed digital video images from said one or more compressed digital video images, said decompressing means including;

(1) means for acquiring a code-book index from said input digital video signal in accordance with said single fixed lookup table;

(2) means for obtaining an index value by looking up said code-book index in an index table;

(3) means for determining one or more current pixels by copying one or more corresponding previous pixels into the location of said one or more current pixels if said index value is greater than a predetermined threshold;

(4) means for obtaining at least one vector value by looking up said index value in a first table if said index value is not greater than said predetermined threshold; and

(5) means for forming one or more current pixels from said at least one vector value and one or more corresponding previous pixels if said index value is not greater than said predetermined threshold;

(6) means for forming said one or more decompressed digital video images from said one or more current pixels; and

(C) output means, coupled to said processor, for forming said output digital video signal in accordance with said one or more decompressed digital video images.

34. The system of claim 33, wherein said one or more compressed digital video images comprise a plurality of compressed digital video images, said system further comprising synchronization means, coupled to said digital processor, for selectively invoking said digital processor to decompress selected ones of said plurality of compressed digital video images.

35. The system of claim 34, wherein said digital processor further comprises means for detecting at least one sync frame.

36. The system of claim 35, further comprising memory coupled to said output means, for sequentially storing ones of said plurality of decompressed digital video images.

37. The system of claim 36, further comprising display means, coupled to said memory, for sequentially displaying said stored images and said at least one sync frame.

38. The system of claim 33, wherein said means providing a single fixed lookup table comprises means for providing a table representative of statistical information about said video images of said training set.

39. The system of claim 33, wherein said one or more decompressed digital video images differ from said training images.

40. A system for forming an output digital video signal representative of one or more decompressed digital video images in real time from an input digital video signal representative of one or more decompressed digital video images comprising:

(a) means for providing a single fixed lookup table in accordance with a training set formed of a plurality of video training images, said single fixed lookup table being representative of the video training images of said training set;

(b) input means for receiving said input digital video signal;

(c) a digital processor coupled to said input means, said digital processor having decompressing means for forming said one or more decompressed digital video images in real time from said one or more decompressed digital video images, said compressing means including;

(1) means for selecting from said one or more decompressed digital video images at least one pixel for compression;

(2) means for determining at least one difference value between said at least one selected pixel and at least one corresponding previous pixel;

(3) means for determining an index value corresponding to the location in a first table of said at least one difference value;

(4) means for comparing said index value to a first predetermined value;

(5) means for incrementing a run-length counter by a second predetermined value if said index value is equal to said first predetermined value;

(6) means for encoding said run-length counter in accordance with said single fixed lookup table;

(7) means for encoding said index value in accordance with said single fixed lookup table if said index value is not equal to said first predetermined value;

(8) means for forming a compressed digital video image from said encoded run-length counter and said encoded index value;

(d) output means, coupled to said digital processor, for forming said output digital video signal from said one or more compressed digital video images.

41. The system of claim 40, wherein said input means comprises:

(1) a video digitizer for forming said one or more decompressed digital video images from said input digital video signal; and

(2) memory, coupled to said video digitizer, for storing said one or more decompressed digital video images.

42. The system of claim 40, wherein said one or more decompressed digital video images comprise a plurality of decompressed digital video images.

43. The system of claim 42, further comprising synchronization means, coupled to said digital processor, for selectively invoking said digital processor to compress selected ones of said plurality of decompressed digital video images.

44. The system of claim 43, wherein said synchronization means further comprises means for invoking said digital processor to from at least one sync frame.

45. The system of claim 40, wherein said means for providing a single fixed lookup table comprises means for providing a table representative of statistical information about said video images of said training set.

46. The system of claim 40, wherein said one or more decompressed digital video images differ from said training images.