Image encoding by vector quantization of regions of an image and codebook updates

• US 5,822,465 A
• Filed: 06/07/1995
• Issued: 10/13/1998
• Est. Priority Date: 09/01/1992
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Normile, James Oliver, Wang, Katherine Shu-Wei
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Tadayon, Bijan
• Application Number:
  US08/486,828
• Time in Patent Office: 1,224 Days
• Field of Search: 382/232, 382/236, 382/238, 382/239, 382/240, 382/243, 382/253, 382/159, 382/160, 382/168, 382/170, 382/171, 382/172, 382/173, 382/175, 382/176, 382/180, 382/181, 382/190, 382/192, 382/195, 382/203, 382/209, 382/224, 382/235, 382/244, 382/248, 382/251, 382/252, 382/282, 382/286, 382/307, 382/308, 382/233, 382/234, 382/250, 382/274, 382/275, 358/425, 358/426, 358/427, 358/430, 358/433, 358/261.1, 358/261.2, 358/261.3, 375/241, 375/240, 341/65, 341/67, 341/106, 348/417, 348/422, 348/418
• US Class Current: 382/253
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/149 by estimating the code amount by means of a model, e.g. mathematical model or statistical model
• CPC Class Codes: H04N 19/152 by measuring the fullness of the transmission buffer
• CPC Class Codes: H04N 19/154 Measured or subjectively estimated visual quality after decoding, e.g. measurement of distortion use of rate-distortion criteria H04N19/147
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/192 the adaptation method, adaptation tool or adaptation type being iterative or recursive
• CPC Class Codes: H04N 19/196 being specially adapted for the computation of encoding parameters, e.g. by averaging previously computed encoding parameters processing of motion vectors H04N19/513
• CPC Class Codes: H04N 19/198 including smoothing of a sequence of encoding parameters, e.g. by averaging, by choice of the maximum, minimum or median value
• CPC Class Codes: H04N 19/507 using conditional replenishment
• CPC Class Codes: H04N 19/59 involving spatial sub-sampling or interpolation, e.g. alteration of picture size or resolution
• CPC Class Codes: H04N 19/94 Vector quantisation
• CPC Class Codes: H04N 19/96 Tree coding, e.g. quad-tree coding
• CPC Class Codes: H04N 7/54 the signals being synchronous H04N21/23602, H04N21/23614, H04N21/2365, H04N21/2368, H04N21/4341, H04N21/4342, H04N21/4347, H04N21/4348 take precedence

Abstract

Improved method and apparatus for vector quantization (VQ) to build a codebook for the compression of data. The codebook or "tree" is initialized by establishing N initial nodes and creating the remainder of the codebook as a binary codebook. Children entries are split upon determination of various attributes, such as maximum distortion, population, etc. Vectors obtained from the data are associated with the children nodes, and then representative children entries are recalculated. This splitting/reassociation continues iteratively until a difference in error associated with the previous children and current children becomes less than a threshold. This splitting and reassociating process continues until the maximum number of terminal nodes is created in the tree, a total error or distortion threshold has been reached or some other criterion. The data may then be transmitted as a compressed bitstream comprising a codebook and indices referencing the codebook.

Claims

1. An apparatus for encoding an image represented by a plurality of blocks of pixels, said apparatus comprising:

a preprocessor configured to select a portion of the plurality of blocks to subsample by calculating values indicative of distortion caused by subsampling the plurality of blocks;

the preprocessor being further configured to subsample the portion of the plurality of blocks into subsampled blocks to reduce the amount of data that must be encoded to encode the image; and

an encoder configured to receive the subsampled blocks from said preprocessor and non-subsampled blocks, said encoder being further configured to encode the subsampled blocks and the non-subsampled blocks with separate codebooks.

2. The apparatus of claim 1 wherein each of the values indicative of distortion is associated with a respective one of the plurality of blocks, and said preprocessor is configured to subsample blocks of the plurality of blocks having values indicative of small distortion relative to other of the plurality of blocks.

3. The apparatus of claim 1 wherein said encoder is further configured to indicate that the subsampled blocks have been encoded with a first codebook and that the non-subsampled blocks have been encoded with a second codebook.

5. The apparatus of claim 1 wherein the portion of the plurality of blocks subsampled into subsampled blocks is spatially smoother than the non-subsampled blocks.

6. The apparatus of claim 1 wherein said encoder comprises a vector quantizer.

7. The apparatus of claim 1 wherein at least one of the separate codebooks is used to encode a plurality of images.

4. An apparatus for encoding an image represented by a plurality of blocks of pixels, said apparatus comprising:

a preprocessor configured to subsample a portion of the plurality of blocks into subsampled blocks to reduce the amount of data that must be encoded to encode the image;

an encoder configured to receive the subsampled blocks from said preprocessor and non-subsampled blocks, said encoder being further configured to encode the subsampled blocks and the non-subsampled blocks with separate codebooks; and

a rate controller configured to limit the number of subsampled blocks according to a desired bit-rate.

8. An apparatus for encoding an image, said apparatus comprising:

means for encoding each of a plurality of regions of an image with a respective one of a first plurality of codebooks;

means for generating an error value indicating a measure of distortion resulting from encoding at least one of the plurality of regions with one of the first plurality of codebooks;

means for dividing the at least one of the plurality of regions into subregions based on the error value; and

means for encoding each of the subregions with a respective one of a second plurality of codebooks.

9. The apparatus of claim 8 wherein said error value is based on a difference between the magnitude of a codebook vector used to encode a first vector in the at least one of the plurality of regions and the magnitude of the first vector.

10. The apparatus of claim 8 wherein said means for dividing at least one of the plurality of regions into subregions comprises means for dividing at least one of the subregions into additional subregions based on an error value associated with encoding the at least one of the subregions.

11. The apparatus of claim 8 wherein said error value comprises a mean-squared error.

12. The apparatus of claim 8 wherein said means for dividing comprises means for recursively dividing the plurality of regions into subregions until a predetermined number of regions is reached.

13. The apparatus of claim 8 wherein two or more codebooks of the first plurality of codebooks contain different quantities of codebook vectors.

14. An apparatus for encoding a current image comprising:

means for using a previous codebook from a previous image to encode said current image as a first encoded image;

means for decoding said first encoded image to generate a first decoded image;

means for comparing said current image to said first decoded image to produce an error value;

means for updating said previous codebook to create a current codebook for said current image if said error value exceeds a threshold, said threshold being based on an error between a second decoded image generated from a previous encoded image and a previous unencoded image; and

means for encoding said current image as a second encoded image using said current codebook if said error value exceeds said threshold.

15. The apparatus of claim 14 wherein said threshold is based on an average of frame mean squared errors.

16. The apparatus of claim 14 wherein said updating means comprises a means for updating specific entries in said previous codebook to generate said current codebook if decoded vectors generated from said first encoded image have a large error in comparison with said current image.

17. The apparatus of claim 16 wherein said updating means further comprises a means for generating a new codebook to be used as said current codebook if said decoded vectors generated from said first encoded image have a large mean squared error in comparison with said current image and said means for updating entries in said previous codebook has already been operative.

19. The apparatus of claim 14 wherein said updating means comprises a means for traversing nodes in a tree representative of vectors for said previous codebook and determining best entries in said previous codebook to use in said current codebook.

20. The apparatus of claim 19 further comprising a means for removing entries in said tree which have a worst error compared with vectors in said current image.

21. The apparatus of claim 19 wherein said means for determining best entries in said tree comprises a means for determining the mean squared error between vectors in said current image and vectors in said tree.

22. The apparatus of claim 19 further comprising a means for creating additional entries in said tree to better represent said current image.

23. The apparatus of claim 22 wherein said means for creating additional entries comprises splitting nodes in said tree to create two new entries for said current codebook.

26. The apparatus of claim 20 further comprising a means for removing an entry in said tree which has no vectors from the current image associated with it.

18. An apparatus for encoding a current image comprising:

means for using a previous codebook from a previous image to encode said current image as a first encoded image;

means for decoding said first encoded image to generate a first decoded image;

means for comparing said current image to said first decoded image to produce an error value;

means for updating said previous codebook to create a current codebook for said current image if said error value exceeds a threshold; and

means for encoding said current image as a second encoded image using said current codebook if said error value exceeds said threshold

wherein said updating means comprises a means for updating specific entries in said previous codebook to generate said current codebook if decoded vectors generated from said first encoded image have a large error in comparison with said current image;

wherein said updating means further comprises a means for generating a new codebook to be used as said current codebook if said decoded vectors generated from said first encoded image have a large mean squared error in comparison with said current image and said means for updating entries in said previous codebook has already been operative; and

wherein said new codebook generation means is activated if said updating means has been operative for encoding at least N images sequentially.

24. An apparatus for encoding a current image comprising:

means for using a previous codebook from a previous image to encode said current image as a first encoded image;

means for decoding said first encoded image to generate a first decoded image;

means for comparing said current image to said first decoded image to produce an error value;

means for updating said previous codebook to create a current codebook for said current image if said error value exceeds a threshold; and

means for encoding said current image as a second encoded image using said current codebook if said error value exceeds said threshold;

wherein said updating means comprises a means for traversing nodes in a tree representative of vectors for said previous codebook and determining best entries in said previous codebook to use in said current codebook;

means for creating additional entries in said tree to better represent said current image;

wherein said means for creating additional entries comprises splitting nodes in said tree to create two new entries for said current codebook; and

wherein said means for splitting nodes in said tree is operative upon determining that said nodes have a greater population of vectors from the current image associated with them than a population threshold.

25. An apparatus for encoding a current image comprising:

means for using a previous codebook from a previous image to encode said current image as a first encoded image;

means for decoding said first encoded image to generate a first decoded image;

means for comparing said current image to said first decoded image to produce an error value;

means for updating said previous codebook to create a current codebook for said current image if said error value exceeds a threshold; and

means for encoding said current image as a second encoded image using said current codebook if said error value exceeds said threshold;

wherein said updating means comprises a means for traversing nodes in a tree representative of vectors for said previous codebook and determining best entries in said previous codebook to use in said current codebook;

means for creating additional entries in said tree to better represent said current image;

wherein said means for creating additional entries comprises splitting nodes in said tree to create two new entries for said current codebook; and

wherein said means for splitting nodes in said tree is operative upon determining that said nodes have a greater distortion of vectors than a distortion threshold.

27. An apparatus for encoding N images comprising:

means for encoding N images into N encoded images using a first codebook generated from n images, wherein n is greater than or equal to one and n is less than or equal to N;

means for determining based on an error between one of said N images and a decoded one of said N encoded images that a second codebook should be used by said means for encoding instead of said first codebook;

means for determining whether a first number of blocks for said N encoded images having an error greater than an average block error is greater than a threshold; and

means for generating a second codebook for encoding an image encoded subsequent to said N images.

28. The apparatus of claim 27 wherein said means for determining comprises means for replacing said first codebook with said second codebook.

29. The apparatus of claim 27 wherein said means for determining comprises means for updating said first codebook to generate said second codebook.

30. The apparatus of claim 27 wherein said determining means comprises a means for determining whether the error between said one of said N images and said decoded one of said N encoded images exceeds a threshold.

34. The apparatus of claim 27 further comprising means for updating said first codebook to create said second codebook, said means for updating comprising means for computing blocks from said N images to update entries in said first codebook.

35. The apparatus of claim 34 further comprising means for determining whether an image decoded with said second codebook has a frame error greater than a threshold.

36. The apparatus of claim 35 further comprising means for generating a replacement codebook if said image decoded with said second codebook has a frame error greater than said threshold.

31. An apparatus for encoding N images comprising:

means for encoding N images into N encoded images using a first codebook generated from n images, wherein n is greater than or equal to one and n is less than or equal to N;

means for determining based on an error between one of said N images and a decoded one of said N encoded images that a second codebook should be used by said means for encoding instead of said first codebook;

filtering means for filtering said N images prior to said encoding means encoding said N images; and

rate control means for controlling said filtering means to generate an encoded bitstream at a desired rate.

32. The apparatus of claim 31 wherein said rate control means determines a desired frame length for a current one of said N images based on the extent to which an actual frame length for a previous one of said N images differed from a desired frame length determined for the previous one of said N images.

33. The apparatus of claim 31 wherein said filtering means comprises a low pass filter.

37. A method of encoding a sequence of images comprising:

generating a first codebook based on vectors obtained from an initial image of said sequence of images;

encoding a subsequent image of said sequence of images into a subsequent encoded image using said first codebook;

decoding said subsequent encoded image into a subsequent decoded image using said first codebook;

determining whether a current frame error between said subsequent decoded image and said subsequent image is greater than a previous frame error between a decoded initial image and said initial image; and

if said current frame error is greater than said previous frame error, generating a second codebook based on said subsequent image and encoding said subsequent image using said second codebook.

38. The method of claim 37 further comprising the steps of:

determining that a number of decoded blocks in said subsequent decoded image differ from corresponding blocks in said subsequent image by at least a threshold amount;

determining whether said number of decoded blocks exceeds a threshold number; and

if said number of decoded blocks exceeds the threshold number, generating a third codebook based on said subsequent image and encoding said subsequent image using said second codebook.

39. The method of claim 37 wherein said step of generating a second codebook comprises:

identifying a first codebook vector in said first codebook which is least representative of said subsequent image;

removing said first codebook vector from said first codebook;

adding a second codebook vector to said first codebook to generate a second codebook, said second codebook vector being based on said subsequent image; and

encoding said subsequent image with said second codebook.

40. The method of claim 39 wherein said step of adding a second codebook vector to said first codebook to generate a second codebook comprises the step of associating said second codebook vector with a terminal node of a tree structure.

41. The method of claim 37 wherein said step of generating a second codebook comprises the step of associating vectors with terminal nodes of a tree structure, said vectors being based on said subsequent image.

42. The method of claim 41 further comprising the steps of:

determining that one of said terminal nodes of said tree structure has no vectors associated with it; and

removing said one of said terminal nodes from said tree structure.

43. The method of claim 41 further comprising the steps of:

determining one of said terminal nodes of said tree structure to have a distortion measure greater than distortion measures of other of said terminal nodes of said tree structure;

splitting said one of said terminal nodes into a parent node having child nodes;

associating vectors associated with said one of said terminal nodes with said child nodes.

44. The method of claim 39 wherein said step of adding a second codebook vector to said first codebook to generate a second codebook comprises the steps of:

transmitting said second codebook vector to a decoding means; and

updating a third codebook in said decoding means.

46. The method of claim 43 further comprising the step of subsampling the smooth regions prior to said step of encoding the smooth regions with the first codebook.

45. A method for transmitting an image, the method comprising:

separating the image into smooth regions and detailed regions based upon a comparison between pixels and neighboring pixels in the image;

encoding the smooth regions of the image with a first codebook;

encoding the detailed regions of the image with a second codebook; and

wherein said step of separating the image into smooth regions and detailed regions comprises the step of calculating, for each one of a plurality of blocks of pixels comprised by the image, an error value indicative of distortion that would result if the one of the plurality of pixel blocks was subsampled, the smooth regions being defined by pixel blocks having lower error values than pixel blocks defining the detailed regions.

47. A method for encoding images, the method comprising the steps of:

generating a first codebook based on a first input image;

encoding a second input image with the first codebook to generate a second encoded image;

decoding said second encoded image to generate a second decoded image;

determining whether a difference between the second decoded image and the second input image exceeds a threshold;

updating the first codebook to generate a second codebook if the difference exceeds the threshold; and

wherein said step of determining whether a difference between the second decoded image and the second input image exceeds a threshold comprises the step of determining a threshold based on a difference between a previous input image and a previous decoded image.

48. The method of claim 47 wherein said step of updating the first codebook to generate a second codebook comprises the step of removing a vector from said first codebook.

49. The method of claim 47 wherein said step of updating the first codebook to generate a second codebook comprises the step of adding a vector to said first codebook.

55. The method of claim 47 further comprising the step of encoding the second input image with the second codebook if the difference exceeds the threshold.

50. A method for encoding images, the method comprising the steps of:

generating a first codebook based on a first input image;

encoding a second input image with the first codebook to generate a second encoded image;

decoding said second encoded image to generate a second decoded image;

determining whether a difference between the second decoded image and the second input image exceeds a threshold;

updating the first codebook to generate a second codebook if the difference exceeds the threshold; and

wherein said step of updating the first codebook to generate a second codebook comprises the step of traversing nodes in a tree to locate a terminal node of the tree having a larger distortion measure than other terminal nodes of the tree.

51. The method of claim 50 further comprising the steps of:

converting the terminal node of the tree into a parent node having a plurality of child nodes; and

assigning a plurality of vectors to be representative vectors for the plurality of child nodes.

52. An apparatus for encoding an image comprising:

a preprocessor configured to receive the image and to indicate whether a difference between a first region of the image and a second region of the image exceeds a threshold;

a vector quantizer coupled to said preprocessor and receiving therefrom the first region, the second region and an indication whether the difference exceeds a threshold, said vector quantizer being configured to encode the first region of the image with a first codebook into a first data sequence and, if the difference exceeds the threshold, to encode the second region with a second codebook into a second data sequence;

a packer coupled to said vector quantizer and receiving the first data sequence and, if the difference exceeds a threshold, the second data sequence therefrom, said packer being configured to generate a datastream containing the first data sequence and, if the difference exceeds the threshold, the second data sequence; and

said packer being further configured to place information in the datastream indicating that the first data sequence is encoded with the first codebook and, if the difference exceeds the threshold, that the second data sequence is encoded with the second codebook.

53. An apparatus for decoding an encoded image, said apparatus comprising:

a receiving unit configured to receive a datastream including a first codebook index, a second codebook index and information indicating for each of the first codebook index and the second codebook index whether a subsampled block-type or a non-subsampled block-type is represented;

an unpacker coupled to said receiving unit and receiving the datastream therefrom, said unpacker being configured to detect the information indicating whether a subsampled block-type or a non-subsampled block-type is represented and to decode each one of the first codebook index and the second codebook index using either a first codebook or a second codebook according to whether the one of the first codebook index and the second codebook index represents a subsampled block-type or a non-subsampled block-type.

54. The apparatus of claim 53 wherein said receiving unit comprises a codebook regenerator and the datastream further includes codebook vectors, said codebook regenerator being configured to generate the first and second codebooks from the codebook vectors.

56. A method for encoding an image represented by a plurality of blocks of pixels, said method comprising:

subsampling a portion of the plurality of blocks into subsampled blocks to reduce the amount of data that must be encoded to encode the image;

encoding the subsampled blocks with a first codebook;

encoding non-subsampled blocks with a second codebook; and

wherein said step of subsampling a portion of the plurality of blocks includes the step of selecting the portion of the plurality of blocks to subsample by calculating values indicative of distortion expected from subsampling the plurality of blocks.

57. A method for encoding an image, said method comprising:

encoding each of a plurality of regions of an image with a respective one of a first plurality of codebooks;

dividing at least one of the plurality of regions into subregions based on an error value associated with encoding the at least one of the plurality of regions; and

encoding each of the subregions with a respective one of a second plurality of codebooks.

58. The method of claim 57 wherein said step of dividing at least one of the plurality of regions into subregions comprises the step of dividing at least one of the subregions into additional subregions based on an error value associated with encoding the at least one of the subregions.