Preprocessing and postprocessing for vector quantization

• US 5,596,659 A
• Filed: 09/01/1992
• Issued: 01/21/1997
• Est. Priority Date: 09/01/1992
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Wu, Hsi-Jung, Normile, James O., Wang, Katherine S.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Tran, Phuoc
• Application Number:
  US07/938,942
• Time in Patent Office: 1,603 Days
• Field of Search: 382/56, 382/36, 382/30, 382/31, 382/50, 382/253, 382/249, 382/236, 382/240, 382/299, 358/136, 358/135, 358/133, 348/417, 348/418, 348/422
• US Class Current: 382/253
• CPC Class Codes: G06T 9/008 Vector quantisation

Abstract

Improved proprecessing and postprocessing for vector quantization, for example, for encoding an image. In one embodiment, the luminosity of the vectors in an image are used to determine the codes for vector quantization. In another embodiment, a median filter is performed to eliminate motion artifacts. In another embodiment, temporal filtering is applied once the difference between an earlier frame and a current frame exceeds a threshold. Embodiments are also provided for adaptive temporal filtering based on temporal "no change" blocks and their errors. Embodiments are provided for different regions of images which reference different codebooks, and regions of variable size. Embodiments are also provided for shared and variable size codebooks for different images or other data.

Claims

1. A method of encoding an image comprising the following steps:

a. adaptively preprocessing a first bitstream representative of said image in order to eliminate spatial redundancy by selectively subsampling individual vectors in said image based upon luminance of said individual vectors, reduce noise and control data rate, and generate a second bitstream on which to perform vector quantization, wherein said individual vectors include a block of adjacent pixels in said image;

b. applying vector quantization to said second bitstream in order to create a third bitstream comprising a codebook and indices referencing said codebook; and

c. performing index packing on said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a single base address into said codebook for a plurality of said indices in said third bitstream and an associated offset value each for each of said plurality of indices from said single base address to reference entries in said codebook.

2. The method of claim 1 wherein said selective subsampling is performed according to a different weight assigned to different positions of the subsampled individual vectors in said image.

3. The method of claim 2 wherein said weight assigned to central regions of said image is less than said weight assigned to border regions of said image such that said border regions of said image are subsampled prior to said central regions of said image given similar characteristics of said central border regions of said image.

4. The method of claim 1 wherein said selective subsampling is performed according to a different weight assigned to different magnitudes of luminance of the subsampled individual vectors in said image.

5. The method of claim 4 wherein said weight increases as the magnitude of luminance of the individual subsampled vectors in said image increases.

6. The method of claim 5 wherein said different weight is generated by a rate control mechanism.

7. The method of claim 4 wherein said different weight is generated by a rate control mechanism.

8. The method of claim 1 wherein said selective subsampling is performed on individual vectors having edge transitions less than a first luminance threshold to preserve edge detail in said image.

9. The method of claim 8 wherein the first threshold is generated by a rate control mechanism.

10. The method of claim 1 further comprising the step of limiting the number of vectors chosen for subsampling in said image to a first number of vectors.

11. The method of claim 10 wherein the first number of vectors may be a value ranging from zero to the number of vectors in said image.

12. A method of encoding an image comprising the following steps:

a. adaptively preprocessing a first bitstream representative of said image in order to eliminate temporal redundancy by adaptively adjusting a difference threshold to determine whether blocks in said bitstream should be encoded according to rate control demands, and generate a second bitstream on which to perform vector quantization;

b. applying vector quantization to said second bitstream in order to create a third bitstream comprising a codebook and indices referencing said codebook; and

c. performing index packing on said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a single base address into said codebook for a plurality of said indices in said third bitstream and an associated offset value each for each of said plurality of indices from said single base address to reference entries in said codebook.

13. The method of claim 12 wherein said preprocessing step comprises determining whether a difference between a first vector in said image and a second vector in a previous image at a same spatial position as said first vector is less than a first threshold, then tagging said first vector as a no-change block, said tagging indicating that said vector quantization should not be performed on said first vector, said first threshold being adaptively adjusted based upon rate control demands determined by examining said fourth bitstream and errors in encoding previous vectors in said first bitstream.

14. The method of claim 13 wherein said preprocessing step further includes the step of determining whether said first vector in said image has been tagged as a no-change block for a first interval of time from previous images, and if so, then determining whether said difference is less than a second threshold, said second threshold being less than said first threshold, and if so, then tagging said fast vector as a no-change block.

15. The method of claim 14 wherein the first interval of time comprises a number of frames that said first vector has been tagged as a no-change block from previous images.

16. The method of claim 14 wherein the fast interval of time is determined based upon a fast age associated with the fast vector, said first age having an initial value which is pseudo-randomly generated and associated with said first vector upon an initial determination in a previous image that said vector should be tagged as a no-change block.

17. A method of encoding an image comprising the following steps:

a. based upon local image characteristics of said image, adaptively determining which filtering method in a first set of filtering methods best preserves detail in said image given rate control demands and which eliminates spatial redundancy in said image to generate a first bitstream on which to perform vector quantization;

b. preprocessing said first bitstream using said filtering method in order to generate a second bitstream which is free of said spatial redundancy;

c. applying vector quantization to said second bitstream in order to create a third bitstream comprising a codebook and indices referencing said codebook; and

d. performing index packing on said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a single base address into said codebook for a plurality of said indices in said third bitstream and an associated offset value each for each of said plurality of indices from said single base address to reference entries in said codebook.

18. The method of claim 17 wherein said first set of filtering methods comprises a horizontal filtering method.

19. The method of claim 17 wherein said first set of filtering methods comprises a vertical filtering method.

20. The method of claim 17 wherein said first set of filtering methods comprises a upward diagonal filtering method.

21. The method of claim 17 wherein said first set of filtering methods comprises a downward diagonal filtering method.

22. An apparatus for encoding an image comprising:

a. means for adaptively preprocessing a first bitstream representative of said image in order to eliminate spatial redundancy, reduce noise and control data rate and generate a second bitstream on which to perform vector quantization;

b. means for applying vector quantization to said second bitstream in order to create a third bitstream comprising a codebook and indices referencing said codebook; and

c. means for performing index packing on said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a single base address into said codebook for a plurality of said indices in said third bitstream and an associated offset value each for each of said plurality of indices from said single base address to reference entries in said codebook.

23. An apparatus for encoding an image comprising:

a. means for adaptively preprocessing a first bitstream representative of said image in order to eliminate temporal redundancy reduce noise and control data rate, and generate a second bitstream on which to perform vector quantization;

b. means for applying vector quantization to said second bitstream in order to create a third bitstream comprising a codebook and indices referencing said codebook; and

c. means for performing index packing on said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a Single base address into said codebook for a plurality of said packed indices in said third bitstream and an associated offset value each for each packed index from said single base address to reference entries in said codebook.

24. An apparatus for encoding an image comprising:

a. means for adaptively determining based upon local image characteristics of said image a filter in a first set of filters which yields a minimum absolute error compared to vectors in a first bitstream representative of said image in order to eliminate spatial redundancy to generate a first bitstream on which to perform vector quantization;

b. means for preprocessing said first bitstream using said filter in order to generate a second bitstream which is free of said spatial redundancy;

c. means for applying vector quantization to said second bitstream in order to create a third bitstream comprising a codebook and indices referencing said codebook; and

d. means for performing index packing on said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a single base address into said codebook for a plurality of said indices in said third bitstream and an associated offset value each for each of said plurality of indices from said single base address to reference entries in said codebook.

25. An apparatus for decoding an image comprising:

a. means for creating a current codebook from a previous codebook including;

i. means for detecting a reference to a first codebook entry which should be updated in a previous codebook;

ii. means for updating said first codebook entry in said previous codebook from a received codebook entry to transform said previous codebook into said current codebook;

b. means for receiving a coded bitstream including block header identifiers in said coded bitstream, each said block header identifier including one of the following;

i. a first value indicating that subsequent blocks in said coded bitstream have not changed from a previous image;

ii. a second value indicating that subsequent blocks in said coded bitstream have been subsampled and been vector quantized;

or

iii. a third value indicating that subsequent blocks in said coded bitstream have been vector quantized;

c. means for receiving codebook indices in said coded bitstream, said codebook indices referencing entries in said current codebook;

d. means for retrieving entries from said current codebook based upon said codebook indices received by said codebook receiving means;

e. means for determining whether said codebook indices refer to vectors which have been subsampled according to said block header identifiers;

f. means for upsampling said retrieved codebook entries for said vectors determined to be subsampled by said subsampling determining means; and

g. means for displaying each of the vectors contained in said codebook entries retrieved by said retrieving means on a display means.

26. The apparatus of claim 25 wherein the means for detecting the reference to the first codebook entry in the previous codebook includes means for detecting a bitmap referencing said first codebook entry in said previous codebook.

27. The apparatus of claim 25 wherein the means for upsampling codebook entries comprises means for replicating pixels from a codebook entry.

28. The apparatus of claim 25 wherein the means for upsampling codebook entries comprises means for interpolating pixels from a codebook entry.

29. The apparatus of claim 25 wherein the means for retrieving entries from said current codebook comprises means for using one index of said indices to reference said current codebook.

30. The apparatus of claim 29 wherein the means for using the index to reference said current codebook comprises means for adding said one index to a base address to calculate an actual index and using said actual index to reference said entry in said current codebook.

31. An apparatus for decoding an image comprising:

a. means for creating a current codebook from codebook entries transmitted by an encoding means;

b. means for receiving a ceded bitstream including block header identifiers in said coded bitstream each said block head identifier including one of the following;

i. a first value indicating that subsequent blocks in said coded bitstream have not changed from a previous image;

ii. a second value indicating that subsequent blocks in said coded bitstream have been subsampled and been vector quantized;

or

iii. a third value indicating that subsequent block in said coded bitstream have been only vector quantized with no subsampling;

c. means for receiving codebook indices in said coded bitstream, said codebook indices referencing entries in said current codebook;

d. means for retrieving entries from said current codebook based upon said codebook indices received by said codebook receiving means;

e. means for determining whether said codebook indices refer to vectors which have been subsampled according to said block header identifiers; and

f. means for upsampling said retrieved codebook entries for said vectors determined to be subsampled by said subsampling determining means.

32. The apparatus of claim 31 further comprising means for displaying vectors comprising an image based upon entries retrieved from said current codebook.

33. The apparatus of claim 31 wherein said upsampling means comprises means for interpolating pixel values from said entries received from said current codebook.

34. The apparatus of claim 31 wherein said upsampling means comprises means for replicating pixel values from said entries received from said current codebook.

35. The apparatus of claim 31 wherein said vector is represented using luminance and chrominance information.

36. The apparatus of claim 31 wherein said vector is represented using a block of luminance and a single chrominance value.

37. An apparatus for decoding an image comprising:

a. means for receiving a reference to a previous codebook, wherein said reference to a previous codebook refers to one of a plurality of codebooks in said apparatus and each of said plurality of codebooks is used for decoding different spatial regions of said image;

b. means for creating a current codebook from said previous codebook including;

i. means for detecting a reference to a first codebook entry which should be updated in a previous codebook;

ii. means for updating said first codebook entry in said previous codebook from a received codebook entry to transform said previous codebook into said current codebook;

c. means for receiving codebook indices, said codebook indices referencing entries in said current codebook; and

d. means for retrieving entries from said current codebook based upon said codebook indices received by said codebook receiving means.

38. A method of encoding an image comprising the following steps:

a. adaptively preprocessing a first bitstream representative of said image in order to eliminate redundancy by selectively subsampling individual vectors in said image based upon data rate demands and the luminance of each of said vectors, and generate a second bitstream on which to perform vector quantization, wherein said individual vectors include a block of adjacent pixels in said image;

b. applying vector quantization to said second bitstream in order to create a third bitstream comprising indices referencing a codebook; and

c. performing index packing on said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a single base address into said codebook for a plurality of said indices in said third bitstream and an associated offset value each for each of said plurality of indices from said single base address to reference entries in said codebook.

39. The method of claim 38 wherein said selective subsampling is performed according to a different weight assigned to different positions of the subsampled individual vectors in said image.

40. The method of claim 39 wherein said weight assigned to central regions of said image is less than said weight assigned to border regions of said image such that said border regions of said image are subsampled prior to said central regions of said image given similar characteristics of said central and border regions of said image.

41. The method of claim 38 wherein said selective subsampling is performed according to a different weight assigned to different magnitudes of luminanee of the subsampled individual vectors in said image.

42. The method of claim 41 wherein said weight increases as the magnitude of luminanee of the individual subsampled vectors in said image increases.

43. The method of claim 38 wherein said selective subsampling is performed on individual vectors having edge transitions less than a first threshold to preserve edge detail in said image.

44. The method of claim 43 wherein the first threshold is generated by a rate control mechanism.

45. The method of claim 38 further comprising the step of limiting the numbers of vectors chosen for subsampling in said image is limited to a first number of vectors.

46. The method of claim 45 wherein the first number of vectors may be a value ranging from zero to the number of vectors in said image.

47. An apparatus for encoding an image comprising:

a. preprocessing circuitry for adaptively preprocessing a first bitstream representative of said image in order to eliminate redundancy based upon data rate demands, and generate a second bitstream on which to perform vector quantization;

b. vector quantization circuitry for encoding said second bitstream in order to create a third bitstream comprising indices referencing a codebook; and

c. index packing circuitry for processing said indices in said third bitstream in order to generate a fourth bitstream, said fourth bitstream including a single base address into said codebook for a plurality said indices in said third bitstream and a plurality of associated offset values from said single base address to reference entries in said codebook.