Variable dimension vector quantization

A variable dimension vector quantization method that uses a single "universal" codebook. The method can be given the interpretation of sampling full-dimensioned codevectors in the universal codebook and generating subcodevectors of the same dimension as input data subvector, which dimension may vary in time. A subcodevector is selected from the codebook to have minimum distortion between it and the input data subvector. The subcodevector with minimum distortion corresponds to the representative, full-dimensioned codevector in the codebook. The codebook is designed by inverse sampling of training subvectors to obtain full-dimension vectors, then iteratively clustering the training set until a stable centroid vector is obtained.

We claim:

1. A method for digital signal compression for use with means for acquiring an input subvector which from time to time may have any one of a plurality of different dimensions with any particular occurrence of said subvector containing L sub-samples of a K-dimensional data vector with L<K, and means for producing an ordered set of L index values that identifies which ordered subset of components of said data vector yields the elements of said subvector, said method digitally compressing the subvector and comprising the steps of:

receiving a signal and computing a K-dimensional data vector representing the signal;

from a predetermined codebook containing a plurality of codevectors of fixed dimension K, extracting from each of said codevectors a subiodevector of dimension L by selecting components of said codevector in accordance with said ordered set of index values;

computing for each said subcodevector in said codebook a measure of distortion between said input subvector and said subcodevector; and

comparing the distortion values so computed to find the substantially minimum distortion value and the corresponding optimal subcodevector that yields the substantially minimum distortion.

2. The method of claim 1 wherein the codebook contains N codevectors denoted Y.sub.i, where the subscript i is an index for each stored codevector, and wherein said codebook is designed by the method of using an arbitrary initial codebook and a set of m pairs of training vectors, where m>N, with each such pair consisting of a selector vector Q that specifies said ordered index set and an associated variable dimension subvector S, comprising the steps of:

clustering said m pairs into N clusters wherein each individual pair is assigned to a particular cluster C.sub.i labeled with index i if the distortion between each variable dimension subvector S, of said individual pair and a subcodevector selected from each codevector Y.sub.i is minimized over all possible assignments of said individual pair to a cluster;

computing N centroid vectors from said N clusters of pairs wherein the centroid vector G.sub.i for cluster C.sub.i is chosen to be that vector which substantially minimizes the sum of the distortions between each pair (S, Q) in the cluster C.sub.i and the corresponding codevector Y.sub.i ;

updating said codebook by replacing each codevector Y.sub.i by the corresponding centroid vector G.sub.i ; and

testing for convergence of the updated codebook, and if convergence has not been achieved, repeating the process of clustering, computing centroids, and testing for convergence, until convergence has been achieved.

3. The method of claim 1 wherein said data vector consists of samples representative of the spectral magnitude of a frame of speech, and said ordered set of index values is responsive to the pitch frequency of the speech frame.

4. The method of claim 1 in which said K-dimensional data vector consists of short-term Fourier transform coefficients representing said signal.

5. The method of claim 1 wherein said data vector consists of samples representative of the spectral magnitude of a portion of a signal.

6. The method of claim 1 including the step of identifying the codevector in said codebook from which said optimal subcodevector was extracted.

7. A method for classifying a pattern for use with means for acquiring an input subvector containing features representative of a particular one of J classes, said subvector having from time to time any one of a plurality of different dimensions, with any particular occurrence of said subvector containing L sub-samples of a K-dimensional data vector with L<K, and means for acquiring an ordered set of L index values that identifies which ordered subset of components of said data vector yields the elements of said subvector, and including a method for classification of the input subvector into one of J classes, and having a predetermined codebook containing a plurality of codevectors of fixed dimension K and an associated class index for each codevector, said method for classification of the input subvector comprising the steps of:

receiving a signal and computing said K-dimensional vector representing the signal;

extracting from each of s aid codevectors a subcodevector of dimension L by selecting components of said codevector in accordance with said ordered set of index values;

computing for each said subcodevector in said codebook a measure of distortion between said input subvector and said subcodevector;

comparing the distortion values so computed to fin d the substantially minimum value; and

reading out the class index associated with the codevector in said codebook from which said distortion minimizing subcodevector was extracted.

8. The method of claim 7 wherein the codebook contains N codevectors denoted Y.sub.i, where the subscript i is an index for each stored codevector, and wherein said codebook is designed by the method of using an arbitrary initial codebook and a set of m pairs of training vectors, where m>N, with each such pair consisting of a selector vector Q that specifies said ordered index set and an associated variable dimension subvector S, said step of using an arbitrary initial codebook comprising the steps of:

clustering said m pairs into N clusters wherein each individual pair is assigned to a particular cluster with label index i if the distortion between each variable dimension subvector S of said individual pair and a subcodevector selected from each codevector Y.sub.i is minimized over all possible assignments of said individual pair to a cluster;

computing N centroid vectors from said N clusters of pairs wherein the centroid vector C.sub.i for that cluster with label index i is chosen to be that vector which substantially minimizes the sum of the distortions between each pair in the cluster and the corresponding codevector Y.sub.i ;

updating said codebook by replacing N codevectors Y.sub.i by the said centroid vectors C.sub.i ; and

testing for convergence of the updated codebook, and if convergence has not been achieved, repeating the process of clustering, computing centroids, and testing for convergence, until convergence has been achieved.

9. The method of claim 7 wherein said data vector consists of samples representative of the spectral magnitude of a frame of speech, and said ordered set of index values is responsive to the pitch frequency of the speech frame.