Vector quantization using thresholds

• US 5,481,739 A
• Filed: 06/23/1993
• Issued: 01/02/1996
• Est. Priority Date: 06/23/1993
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Staats, Erik
• Primary Examiner(s): Coleman, Eric
• Application Number:
  US08/082,022
• Time in Patent Office: 923 Days
• Field of Search: 395/800, 348/405, 381/30, 381/35
• US Class Current: 712/222
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: G10L 2019/0013 Codebook search algorithms
• CPC Class Codes: G10L 25/48 specially adapted for particular use
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94

Abstract

Methods and apparatus for vector quantization. A threshold generator generates an i threshold (Threshold_i) to be associated with each i quantized vector of n quantized vectors in a vector quantization codebook. The vector quantization codebook and the thresholds are used by a vector quantizer to encode a set of input vectors (V₁ -V_TOT). The determination that a distance between a vector to be encoded and a quantized vector in a codebook is less than the associated threshold causes a search for the closest vector to terminate for a nearest neighbor vector quantizer. In some embodiments, the vectors comprise samples of continuous signals for sound containing speech, or display signals. In other embodiments, codebook vectors are arranged from most frequently encoded vectors to least frequently encoded vectors.

Claims

1. In a computer system, a method of vector quantization, comprising the following steps:

a. from a training set of vectors, creating a vector quantization codebook representative of a set of training vectors, said codebook comprising a representative set of n quantized vectors from said training vectors;

b. for each i quantized vector (VQ_i) of said n quantized vectors, determining an i threshold (Threshold_i) to be associated with said i quantized vector, wherein said i threshold comprises half a distance between said i quantized vector and a k quantized vector (VQ_k) of said n quantized vectors, wherein i<

k≦

n, and said k quantized vector is the closest quantized vector to said i quantized vectors of a set of quantized vectors having an index k wherein i<

k≦

n;

c. for each i quantized vector of said n quantized vectors, associating in said vector quantization codebook said i threshold with said i quantized vector; and

d. using said vector quantization codebook to encode a set of input vectors (V₁ -V_TOT).

2. The method of claim 1 wherein said step of using said codebook to encode said set of input vectors comprises for each input vector being coded in said set of input vectors sequencing using an index j through said codebook and determining for each j quantized vector in said codebook, if the distance between said input vector being coded and said j quantized vector is less than said j threshold associated with said j quantized vector, then encoding said vector and terminating sequencing through said codebook.

3. The method of claim 1 wherein said codebook comprises a tree-searched vector quantized codebook.

4. The method of claim 1 wherein said codebook comprises a standard vector quantized codebook.

5. The method of claim 1 wherein said n quantized vectors in said codebook are ordered from a most frequently encoded vector (VQ₁) to a least frequently encoded vector (VQ_N).

6. The method of claim 1 wherein said n quantized vectors and said set of input vectors comprise samples from a continuous audio signal including speech.

7. The method of claim 1 wherein said n quantized vectors and said set of input vectors comprise graphical display signals.

8. The method of claim 7 wherein said graphical display signals comprise red-green-blue color values.

9. The method of claim 7 wherein said graphical display signals comprise intensity values.

10. An apparatus for vector quantization comprising:

a. a vector quantization codebook generator for generating a representative set of n quantized vectors operative upon receiving a set of training vectors;

b. a threshold generator operative for generating a threshold (Threshold_i) for each i quantized vector (VQ_i) of said n quantized vectors, said i threshold comprising half a distance between said i quantized vector and a k quantized vector (VQ_k) of said n quantized vectors, wherein i<

k≦

n, and said k quantized vector is the closest quantized vector to said i quantized vector of a set of quantized vectors having an index k wherein i<

k≦

n; and

c. an encoder for encoding a set of input vectors (V₁ -V_TOT) using said n quantized vectors and said threshold for said each of said n quantized vectors.