Vector quantization using thresholds

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 1 -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.

What is claimed is: 
     
       1. In a computer system, a method of vector quantization, comprising the following steps: a) creating a vector quantization codebook comprising n quantized 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;   c) for each i quantized vector of said n quantized vectors, associating said i threshold with said i quantized vector in said vector quantization codebook; and   d) using said vector quantization codebook to encode a set of input vectors (V 1  -V TOT ), wherein for each input vector being coded, sequencing using an index j through said vector quantization codebook and determining for each j quantized vector in said vector quantization 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 input vector and terminating sequencing through said vector quantization codebook.   
     
     
       2. The method of claim 1, wherein during said step of using said vector quantization codebook to encode a set of input vectors if it is determined that 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, said input vector is encoded as said j index. 
     
     
       3. The method of claim 1 wherein said input vectors are video graphic data. 
     
     
       4. A data compression system comprising: an encoder, said encoder receiving an input data stream comprising a set of input vectors to be compressed, said encoder comprising a vector quantization codebook of n quantized vectors and n thresholds, wherein for each i quantized vector of said n quantized vectors there is an i th  threshold of said n thresholds associated with said i quantized vector, wherein said encoder encodes said input vectors by sequencing through said vector quantization codebook using an index j and determining for each j quantized vector in said vector quantization codebook if the distance between said input vector being coded and said j quantized vector is less than said j threshold then encoding said input vector as an encoded vector and terminating sequencing through said vector quantization codebook, and wherein said encoder outputs said encoded vector.   
     
     
       5. A data compression system as in claim 4 further comprising storage means, said storage means coupled to said encoder and receiving said encoded vectors, said encoded vectors being stored in said storage means. 
     
     
       6. A data compression system as in claim 4 further comprising a decoder coupled to said encoder, said decoder receiving said encoded vectors and reconstructing said encoded vectors as decoded vectors. 
     
     
       7. A data compression system as in claim 6 further comprising display means coupled to said decoder, wherein said input vectors are video graphic data, and wherein said decoded vectors are displayed on said display means. 
     
     
       8. An apparatus for decoding encoded input vectors comprising: a decoder for reconstructing said encoded input vectors as decoded vectors wherein said encoded input vectors are encoded using a method of vector quantization, said method comprising the steps of:   a) creating a vector quantization codebook comprising n quantized 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;   c) for each i quantized vector of said n quantized vectors, associating said i threshold with said i quantized vector in said vector quantization codebook; and   d) using said vector quantization codebook to encode a set of input vectors (V 1  -V TOT ), wherein for each input vector being coded, sequencing using an index j through said vector quantization codebook and determining for each j quantized vector in said vector quantization 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 input vector and terminating sequencing through said vector quantization codebook.   
     
     
       9. The apparatus of claim 8, wherein during said step of using said vector quantization codebook to encode a set of input vectors if it is determined that 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, said input vector is encoded as said j index. 
     
     
       10. The apparatus of claim 9 further comprising a display device coupled to said decoder, and wherein said decoded vectors are video graphic data.