Universal codebook vector quantization with constrained storage

• US 5,889,891 A
• Filed: 11/21/1995
• Issued: 03/30/1999
• Est. Priority Date: 11/21/1995
• Status: Expired due to Term

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Ramakrishnan, Sangeeta, Rose, Kenneth, Gersho, Allen
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): BRINICH, STEPHEN M
• Application Number:
  US08/561,251
• Time in Patent Office: 1,225 Days
• Field of Search: 382/239, 382/253, 348/414, 348/417-418
• US Class Current: 382/253
• CPC Class Codes: H04N 19/94 Vector quantisation

Abstract

Vectors associated with multiple sources are quantized with a codebook. A mapping function associates each source with a subset of codevectors in the codebook, each subset being defined prior to quantization. Each vector from a source is matched to a codevector in the subset corresponding to the source. The universal codebook is designed by first providing a codebook and a mapping function. Using the codebook, the mapping function is updated by identifying subsets that reduce distortion when vectors from a source are quantized using a corresponding subset.

Claims

1. A method for guantizing vectors associated with multiple sources, comprising:

providing a mapping function associating each source with a subset of codevectors in a codebook and forming subsets sharing a codevector; and

matching each vector from a source to a codevector in the subset corresponding to the source, each subset being defined prior to said matching.

2. A method for quantizing vectors associated with multiple sources, comprising:

providing a mapping function associating each source with a subset of codevectors in a codebook;

matching each vector from a source to a codevector in the subset corresponding to the source, each subset being defined prior to said matching; and

providing to a decoder an identification for the codevector matched to each vector.

3. The method of claim 2 further comprising providing to the decoder an identification of the source of each vector, the identification for the codevector distinguishing between different codevectors in the subset corresponding to the source.

4. A method for quantizing vectors associated with multiple sources, comprising:

providing a mapping function associating each source with a subset of codevectors in a codebook;

matching each vector from a source to a codevector in the subset corresponding to the source, each subset being defined prior to said matching; and

associating each state of an encoder with a source.

5. A method for quantizing vectors associated with multiple sources, comprising:

providing a mapping function associating each source with a subset of codevectors in a codebook;

matching each vector from a source to a codevector in the subset corresponding to the source, each subset being defined prior to said matching; and

associating each class of vectors with a source.

6. A method for quantizing vectors associated with multiple sources, comprising:

providing a mapping function associating each source with a subset of codevectors in a codebook;

matching each vector from a source to a codevector in the subset corresponding to the source, each subset being defined prior to said matching; and

associating groups of vectors arising from a given source with a different source name, the mapping function associating a subset of the codebook with each source name, each vector in a group being matched to a codevector in the subset associated with the source name corresponding to the group.

7. A method for designing a universal codebook for quantizing vectors associated with different sources, comprising:

providing a codebook and a mapping function, the mapping function identifying subsets of codevectors in the codebook corresponding to different sources;

updating the mapping function using the codebook, the mapping function being chosen to reduce distortion when the vectors from a source are quantized using a corresponding subset; and

updating the codevectors in the codebook using the mapping function to further reduce the distortion.

8. A method for designing a universal codebook for quantizing vectors associated with different sources, comprising:

providing a codebook and a mapping function, the mapping function identifying subsets of codevectors in the codebook corresponding to different sources;

updating the mapping function using the codebook, the mapping function being chosen to reduce distortion when the vectors from a source are quantized using a corresponding subset; and

repeating the steps of forming a mapping function and updating the codevectors until convergence.

9. A method for designing a universal codebook for quantizing vectors associated with different sources, comprising:

providing a codebook and a mapping function, the mapping function identifying subsets of codevectors in the codebook corresponding to different sources;

updating the mapping function using the codebook, the mapping function being chosen to reduce distortion when the vectors from a source are quantized using a corresponding subset;

forming the mapping function, including;

receiving a training set of vectors from each source;

determining a nearest neighbor partition cell for each codevector in each subset using the training set from the source corresponding to the subset, and

updating the codevector in each cell for each subset.

10. A method for designing a universal codebook for quantizing vectors associated with different sources, comprising:

providing a codebook and a mapping function, the mapping function identifying subsets of codevectors in the codebook corresponding to different sources;

updating the mapping function using the codebook, the mapping function being chosen to reduce distortion when the vectors from a source are quantized using a corresponding subset; and

updating the codevector comprises finding the codevector in the codebook that minimizes the distortion for the cell.

11. A method for designing a universal codebook for quantizing vectors associated with different sources, comprising:

providing a codebook and a mapping function, the mapping function identifying subsets of codevectors in the codebook corresponding to different sources;

updating the mapping function using the codebook, the mapping function being chosen to reduce distortion when the vectors from a source are quantized using a corresponding subset;

updating the codevector comprises finding the centroid of each cell, and quantizing that centroid using the codebook to produce the updated codevector.

12. A method for designing a universal codebook for quantizing vectors associated with different sources, comprising:

providing a codebook and a mapping function, the mapping function identifying subsets of codevectors in the codebook corresponding to different sources;

updating the mapping function using the codebook, the mapping function being chosen to reduce distortion when the vectors from a source are quantized using a corresponding subset; and

updating the codebook, including;

receiving a training set of vectors for each source,

for each codevector in a subset, finding from the mapping function a nearest neighbor partition cell associated with the codevector,

for each nearest neighbor partition cell in a subset, determining a centroid of the vectors that fall in the cell, the vectors arriving from a source associated with the subset, and

replacing the codevector in the cell with the centroid.

13. A method for designing a universal codebook for quantizing vectors associated with different sources, comprising:

providing a codebook and a mapping function, the mapping function identifying subsets of codevectors in the codebook corresponding to different sources;

updating the mapping function using the codebook, the mapping function being chosen to reduce distortion when the vectors from a source are quantized using a corresponding subset;

providing an initial codebook, comprising;

receiving a training set of vectors from each source, and

deriving the initial codebook from the training sets using a generalized Lloyd algorithm.

14. A method for designing a universal codebook for quantizing vectors associated with different sources, comprising:

providing a codebook and a mapping function, the mapping function identifying subsets of codevectors in the codebook corresponding to different sources;

updating the mapping function using the codebook, the mapping function being chosen to reduce distortion when the vectors from a source are quantized using a corresponding subset; and

providing an initial mapping function, comprising;

receiving a training set of vectors from each source; and

,

deriving the initial mapping function by performing a generalized Lloyd algorithm over a training set for each source.

15. A method for designing a universal codebook for quantizing vectors associated with different sources, comprising:

providing a codebook and a mapping function, the mapping function identifying subsets of codevectors in the codebook corresponding to different sources;

updating the mapping function using the codebook, the mapping function being chosen to reduce distortion when the vectors from a source are quantized using a corresponding subset; and

,

associating each state of an encoder with a source.

16. A method for designing a universal codebook for quantizing vectors associated with different sources, comprising:

providing a codebook and a mapping function, the mapping function identifying subsets of codevectors in the codebook corresponding to different sources;

updating the mapping function using the codebook, the mapping function being chosen to reduce distortion when the vectors from a source are quantized using a corresponding subset; and

,

associating each class of vectors with a source.

17. A method for designing a universal codebook for quantizing vectors associated with different sources, comprising:

providing a codebook and a mapping function, the mapping function identifying subsets of codevectors in the codebook corresponding to different sources;

updating the mapping function using the codebook, the mapping function being chosen to reduce distortion when the vectors from a source are quantized using a corresponding subset; and

associating groups of vectors arising from a given source with a different source name, the mapping function associating a subset of the codebook with each source name.