Vector quantization

• US 5,649,030 A
• Filed: 03/15/1995
• Issued: 07/15/1997
• 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
• Assistant Examiner(s): KELLEY, CHRISTOPHER S
• Application Number:
  US08/405,448
• Time in Patent Office: 853 Days
• Field of Search: 382/251, 382/253, 348/414, 348/417, 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 automatic method in an encoding device of vector quantization of an image comprising the following steps:

a. initializing N initial nodes in a vector quantizer tree in a dynamic storage device of said encoding device;

b. sampling a vector from said image;

c. determining a node in said vector quantizer tree which is a best representative sample of the vector sampled from said image;

d. associating the vector with said node in said vector quantizer tree in said dynamic storage device;

e. sampling a next vector from said image;

f. repeating steps c-f until there are no more vectors to be sampled from said image, said next vector becoming said vector;

g. determining which of the nodes in said tree is the most distorted node in said tree;

h. splitting said most distorted node into two children nodes in said dynamic storage device;

i. associating a first portion of the vectors associated with said most distorted node with a first of said children nodes in said dynamic storage device, and a second portion of the vectors associated with said most distorted node with a second of said children nodes in said dynamic storage device;

j. determining a current error of the two children nodes compared to the first and second portions of the vectors;

k. if the change in error between the current error and a previous error is less than an error threshold then proceeding to step l otherwise determining new values of said first and second children, and proceeding to step i, said current error becoming said previous error;

l. repeating steps g through l until the number of terminal nodes in said vector quantizer tree has reached a desired population; and

m. associating indices with each of the terminal nodes in said vector quantizer tree in said dynamic storage device.

2. The method of claim 1 further comprising the step of transmitting a sequence of indices from said vector quantizer tree representative of an index of a terminal node in said vector quantizer tree associated with each said sampled vector in said input image.

3. The method of claim 1 wherein the step of determining the most distorted node comprises determining whether the average distortion of the node compared to each of vectors sampled from said input image associated with the node has exceeded a threshold.

4. The method of claim 1 wherein the step of determining the most distorted node comprises determining whether the total distortion of the node compared to each of the vectors sampled from said input image associated with the node has exceeded a threshold.

5. The method of claim 1 wherein the step of determining the most distorted node comprises determining whether the total population of sampled vectors from said input image associated with said node has exceeded a threshold.

6. The method of claim 1 wherein the step of determining the most distorted node comprises determining whether the percentage distortion of the node compared to each of the vectors sampled from said input image associated with the node has exceeded a threshold.

7. The method of claim 1 wherein the step of determining the most distorted node comprises determining whether the maximum distortion of the node compared to each of the vectors sampled from said input image associated with the node has exceeded a threshold.

8. The method of claim 1 wherein the step of determining the most distorted node comprises determining whether the ratio of maximum to minimum distortion of the node compared to each of the vectors sampled from said input image associated with the node has exceeded a threshold.

9. The method of claim 1 wherein the step of determining the node which is the best representative sample of the vector sampled from said image comprises determining the mean squared error between the sampled vector and the node.

10. The method of claim 9 wherein the step of determining the mean squared error is weighed more heavily towards large errors during an early portion of said vector quantization, and weighed less heavily towards large errors during a latter portion of said vector quantization.

11. The method of claim 1 wherein the step of creating N initial nodes comprises using N initial nodes from a previous vector quantization which has been performed on a previous image.

12. The method of claim 1 wherein further comprising the additional step of adding a pseudo-randomly generated value to the vector sample from said input image prior to splitting said most distorted node.

13. The method of claim 1 wherein the step of determining the node which is the best representative sample of the vector sampled from said image comprises determining the node which has luminance and chrominance (YUV) values closest to the sampled vector from the image.

14. The method of claim 1 further comprising the step of generating a separate vector quantizer tree for different zones in said image.

15. The method of claim 14 further comprising a step of determining different zones in said image which have variable sizes.

16. The method of claim 1 which is applied to a sequence of images, the creation of a new vector quantizer tree being performed when a scene change is detected in said sequence of images.

17. An automatic apparatus for vector quantization of an image comprising:

a. means for initializing N initial nodes in a vector quantizer tree in a dynamic storage device of said encoding device;

b. means for sampling a vector from said image;

c. means for determining a node in said vector quantizer tree which is a best representative sample of the vector sampled from said image;

d. means for associating the vector with said node in said vector quantizer tree in said dynamic storage device;

e. means for sampling a next vector from said image;

f. means for activating components c-e until there are no more vectors remain to be sampled from said image, said next vector becoming said vector;

g. means for determining which of the nodes in said tree is the most distorted node in said tree;

h. means for splitting said most distorted node into two children nodes in said dynamic storage device;

i. means for associating a first portion of the vectors associated with said most distorted node with a first of said children nodes in said dynamic storage device, and a second portion of the vectors associated with said most distorted node with a second of said children nodes in said dynamic storage device;

j. means for determining a current error of the two children nodes relative to the first and second portions of the vectors;

k. means for determining new values of said first and second children nodes and continuously activating components i-j if the change in error between the current error and a previous error is greater than an error threshold said current error becoming said previous error;

l. means for continuously activating components g through l until the number of terminal nodes in said vector quantizer tree has reached a desired population; and

m. means for associating indices with each of the terminal nodes in said vector quantizer tree in said dynamic storage device.

18. An automatic apparatus in an encoding device for vector quantization of an image comprising:

a. means for initializing N initial nodes in a vector quantizer tree in a dynamic storage device of said encoding device wherein N is greater than 2;

b. means for sampling non-overlapping fixed-size vectors from said image;

c. means for determining nodes in said vector quantizer tree which are best representative samples of the vectors sampled from said image;

d. means for associating said vectors with said nodes in said vector quantizer tree in said dynamic storage device;

e. means for iterating and creating new nodes in the vector quantizer tree in said dynamic storage device by determining worst nodes in said tree, splitting said nodes into more than two children nodes and reassociating said vectors with said children nodes in said vector quantizer tree until a number of terminal nodes in said tree reaches a desired population.

19. A tree-searched vector quantizer for encoding an image, said tree-searched vector quantizer for generating a codebook from first signals received from said image, said first signals representative of vectors sampled from said image, and terminal nodes in a tree created by said tree-searched vector quantizer are used for said codebook, wherein second signals are transmitted from said vector quantizer, said second signals including indices referencing said terminal nodes in said tree, said tree-searched vector quantizer comprising:

a processor; and

a storage device coupled to said processor;

said storage device having stored therein executable code which, when executed by said processor, causes said processor to perform the steps of;

a. determining which of the nodes in said tree is a most distorted node in said tree based on error criteria;

b. splitting said most distorted node into children nodes by performing the following steps;

sampling K representative vectors for said children nodes;

perturbing vectors for said most distorted node in order to create said children nodes if said step of sampling K representative vectors fails to split said most distorted node;

re-associating vectors from said most distorted node with said children nodes; and

tagging said most distorted node as a terminal node if said children nodes are unable to be created;

c. repeating steps a and b until a desired population of said terminal nodes in said tree are created.

20. The tree-searched vector quantizer of claim 19 wherein said step of determining which of the nodes in said tree is the most distorted based on error criteria comprises the step of determining which of the nodes in said tree is the most distorted based on a total distortion of each of the nodes.

21. The tree-searched vector quantizer of claim 19 wherein said step of determining which of the nodes in said tree is the most distorted based on error criteria comprises the step of determining which of the nodes in said tree is the most distorted based on average distortion of each of the nodes.

22. The tree-searched vector quantizer of claim 19 wherein said step of determining which of the nodes in said tree is the most distorted based on error criteria comprises the step of determining which of the nodes in said tree is the most distorted based on vector populations associated with each of the nodes.

23. The tree-searched vector quantizer of claim 19 wherein said step of determining which of the nodes in said tree is the most distorted based on error criteria comprises the step of determining which of the nodes in said tree is the most distorted based on distortion percentages associated with each of the nodes.

24. The tree-searched vector quantizer of claim 19 wherein said step of determining which of the nodes in said tree is the most distorted based on error criteria comprises the step of determining which of the nodes in said tree is the most distorted based on a maximum distortion of the nodes.

25. The tree-searched vector quantizer of claim 19 wherein said step of determining which of the nodes in said tree is the most distorted based on error criteria comprises the step of determining which of the nodes in said tree is the most distorted based on a ratio of distortions of the nodes.

26. An encoding apparatus for compressing an image by performing vector quantization on said image, said apparatus comprising:

a processor; and

a storage device coupled to said processor;

said storage device having stored therein executable code which, when executed by said processor, causes said processor to perform the steps of;

a. initializing N initial nodes in a vector quantizer tree;

b. sampling a vector from said image;

c. determining a node in said vector quantizer tree which is a best representative sample of the vector sampled from said image;

d. associating the vector with said node in said vector quantizer tree;

e. sampling a next vector from said image;

f. repeating steps c-f until there are no more vectors to be sampled from said image, said next vector becoming said vector;

g. determining which of the nodes in said tree is the most distorted node in said tree;

h. splitting said most distorted node into two children nodes;

i. associating a first portion of the vectors associated with said most distorted node with a first of said children nodes, and a second portion of the vectors associated with said most distorted node with a second of said children nodes;

j. determining a current error of the two children nodes compared to the first and second portions of the vectors;

k. if the change in error between the current error and a previous error is less than an error threshold then proceeding to step 1 otherwise determining new values of said first and second children, and proceeding to step i, said current error becoming said previous error;

l. repeating steps g through k until the number of terminal nodes in said vector quantizer tree has reached a desired population; and

m. associating indices with each of the terminal nodes in said vector quantizer tree.

27. The encoding apparatus of claim 26 wherein the step of determining the most distorted node comprises determining whether the average distortion of the node compared to each of vectors sampled from said image associated with the node has exceeded a threshold.

28. The encoding apparatus of claim 26 wherein the step of determining the most distorted node comprises determining whether the total distortion of the node compared to each of the vectors sampled from said image associated with the node has exceeded a threshold.

29. The encoding apparatus of claim 26 wherein the step of determining the most distorted node comprises determining whether the total population of sampled vectors from said image associated with said node has exceeded a threshold.

30. The encoding apparatus of claim 26 wherein the step of determining the most distorted node comprises determining whether the percentage distortion of the node compared to each of the vectors sampled from said image associated with the node has exceeded a threshold.

31. The encoding apparatus of claim 26 wherein the step of determining the most distorted node comprises determining whether the maximum distortion of the node compared to each of the vectors sampled from said image associated with the node has exceeded a threshold.

32. The encoding apparatus of claim 26 wherein the step of determining the most distorted node comprises determining whether the ratio of maximum to minimum distortion of the node compared to each of the vectors sampled from said image associated with the node has exceeded a threshold.

33. The encoding apparatus of claim 26 wherein the step of determining the most distorted node comprises determining whether multiple error criteria compared to each of the vectors sampled from said image associated with the node has exceeded a threshold.

34. The encoding apparatus of claim 26 wherein the step of determining the node which is the best representative sample of the vector sampled from said image comprises determining the mean squared error between the sampled vector and the node.

35. The encoding apparatus of claim 34 wherein the step of determining the mean squared error is weighed more heavily towards large errors during an early portion of said vector quantization, and weighed less heavily towards large errors during a latter portion of said vector quantization.

36. The encoding apparatus of claim 26 wherein the step of creating N initial nodes comprises using N initial nodes from a previous vector quantization which has been performed on a previous image.

37. The encoding apparatus of claim 28 wherein the vector quantization further comprises the additional step of adding a pseudo-randomly generated value to the vector sample from said image prior to splitting said most distorted node.

38. The encoding apparatus of claim 26 wherein the step of determining the node which is the best representative sample of the vector sampled from said image comprises determining the node which has luminance and chrominance (YUV) values closest to the sampled vector from the image.

39. The encoding apparatus of claim 26 wherein the vector quantization further comprises the step of generating a separate vector quantizer tree for different zones in said image.

40. The encoding apparatus of claim 39 wherein the vector quantization further comprises a step of determining different zones in said image which have variable sizes.

41. The encoding apparatus of claim 26 wherein the vector quantization further comprises is applied to a sequence of images, the creation of a new vector quantizer tree being performed when a scene change is detected in said sequence of images.