Adaptive multi-stage vector quantization
First Claim
1. In a multi-stage vector quantization encoder comprising a plurality of consecutive vector quantization stages wherein each stage comprises a vector quantizer and an associated codebook containing a plurality of codevectors, there being a unique address associated with each codevector in the codebook of each stage, a method comprising the steps of:
- p1 (a) receiving a data vector indicative of a block of data to be compressed;
(b) selecting a codevector from the codebook at an initial stage that most closely resembles the data vector, generating a residual vector, and proceeding directly to step (e) if a measure of quantization error at that stage satisfies a threshold value, but otherwise first performing the following steps (c) and (d);
(c) at a next succeeding stage, selecting a codevector from the codebook at that stage that most closely resembles the residual vector from the immediately preceding stage, and generating another residual vector;
(d) repeating said step (c) until a measure of quantization error at a particular stage satisfies the threshold value; and
then(e) transmitting addresses of each codevector selected in said steps (b) and (c) to a remote location.
3 Assignments
0 Petitions
Accused Products
Abstract
Vector quantization of a data vector proceeds through successive stages of a multi-stage vector quantization encoder until either (i) a measure of distortion between the vector input to a given stage and the codevector selected at that stage satisfies a threshold value or (ii) the last stage of the encoder is reached. The threshold value varies according to the fullness of a buffer which stores vector quantized data to be transmitted. Consequently, the last stage reached may differ from data vector to data vector. Compression efficiency therefore improves. Preferably, the mean value of each data vector is removed prior to vector quantization.
82 Citations
40 Claims
-
1. In a multi-stage vector quantization encoder comprising a plurality of consecutive vector quantization stages wherein each stage comprises a vector quantizer and an associated codebook containing a plurality of codevectors, there being a unique address associated with each codevector in the codebook of each stage, a method comprising the steps of:
- p1 (a) receiving a data vector indicative of a block of data to be compressed;
(b) selecting a codevector from the codebook at an initial stage that most closely resembles the data vector, generating a residual vector, and proceeding directly to step (e) if a measure of quantization error at that stage satisfies a threshold value, but otherwise first performing the following steps (c) and (d); (c) at a next succeeding stage, selecting a codevector from the codebook at that stage that most closely resembles the residual vector from the immediately preceding stage, and generating another residual vector; (d) repeating said step (c) until a measure of quantization error at a particular stage satisfies the threshold value; and
then(e) transmitting addresses of each codevector selected in said steps (b) and (c) to a remote location. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
- p1 (a) receiving a data vector indicative of a block of data to be compressed;
-
11. In a multi-stage vector quantization encoder comprising a plurality of consecutive vector quantization stages wherein each stage comprises a vector quantizer and an associated codebook containing a plurality of codevectors, there being a unique address associated with each codevector in the codebook of each stage, a method comprising the steps of:
-
(a) receiving a data vector indicative of a block of data to be compressed; (b) providing the data vector to an initial stage of the multi-stage vector quantization encoder, said data vector defining an input vector for the initial stage, said initial stage defining a current stage; (c) selecting a codevector from the codebook at the current stage that most closely resembles the input vector and generating a residual vector based on the input vector and the selected codevector; (d) determining a measure of distortion between the input vector and the selected codevector; (e) performing the following additional steps if the measure of distortion exceeds a threshold value, but otherwise proceeding to step (f); (i) passing the residual vector to a next succeeding stage as an input vector to that stage, said next succeeding stage becoming the current stage; and (ii) repeating said steps (c) through (e) until the measure of distortion calculated in step (d) at a particular stage does not exceed the threshold value; and
then,(f) transmitting the address of any codevectors selected in said steps (c) and (e) to a remote location, and repeating said steps (a) through (f) for a different data vector. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. In a multi-stage vector quantization encoder comprising a plurality of consecutive vector quantization stages wherein each stage comprises a vector quantizer and associated codebook containing a plurality of codevectors, there being a unique address associated with each codevector in the codebook of each stage, a method comprising the steps of:
-
(a) receiving a data vector indicative of a block of data to be compressed; (b) providing the data vector to an initial stage of the multi-stage vector quantization encoder, said data vector defining an input vector for the initial stage, said initial stage defining a current stage; (c) selecting a codevector from the codebook at the current stage that most closely resembles the input vector and generating a residual vector based on the input vector and the selected codevector; (d) determining a measure of distortion between the input vector and the selected codevector; (e) performing the following additional steps if the measure of distortion exceeds a threshold value, but otherwise proceeding to step (f); (i) passing the residual vector to a next stage of the encoder as an input vector to that stage, said next stage becoming the current stage; and (ii) repeating said steps (c) through (e) until the measure of distortion calculated in step (d) at a particular stage does not exceed the threshold value; and
then,(f) inserting the address of any codevectors selected in said step (c) into a buffer, and repeating said steps (a) through (f) for a different data vector; and (g) transmitting the addresses from the buffer at a fixed data rate, periodically obtaining a measure of unused capacity of the buffer, and automatically adjusting the threshold value based upon the measure of unused buffer capacity. - View Dependent Claims (22, 23, 24, 25, 26)
-
-
27. In a data compression system employing a multi-stage vector quantization encoder comprising a plurality of vector quantization stages coupled consecutively for compressing each of a plurality of data vectors wherein each stage has a codebook containing a plurality of codevectors and each codevector has a unique address, and wherein the number of stages through which vector quantization proceeds in the multi-stage vector quantization encoder is controlled by obtaining a measure of quantization error at each successive stage and proceeding through the successive stages only until the measure of quantization error at a particular stage satisfies a threshold value, and wherein the addresses of codevectors selected from the codebooks at each stage reached during compression of a particular data vector are transmitted to a remote location, and further wherein the codebooks of each stage of the multi-stage vector quantization encoder are reproduced at the remote location, a method for substantially reproducing the data vector at the remote location comprising the steps of:
-
a'"'"') receiving the codevector addresses transmitted by the multi-stage vector quantization encoder for that data vector; b'"'"') for each received address, retrieving the codevector associated with that address from a respective one of the codebooks at the remote location; and c'"'"') summing the retrieved codevectors to obtain a substantial reproduction of the data vector. - View Dependent Claims (28)
-
-
29. In a data compression system employing a multi-stage vector quantization encoder comprising a plurality of vector quantization stages coupled consecutively for compressing each of a plurality of data vectors wherein each stage has a codebook containing a plurality of codevectors and each codevector has a unique address, and wherein the number of stages through which vector quantization proceeds in the multi-stage vector quantization encoder is controlled by obtaining a measure of quantization error at each successive stage and proceeding through the successive stages only until the measure of quantization error at a particular stage satisfies a threshold value, and wherein the addresses of codevectors selected from the codebooks at each stage reached during compression of a particular data vector are transmitted to a remote location, and further wherein the codebooks of each stage of the multi-stage vector quantization encoder are reproduced at the remote location, a method for substantially reproducing the data vector at the remote location comprising the steps of:
-
a'"'"') receiving the codevector addresses transmitted by the multi-stage vector quantization encoder for that data vector; b'"'"') for each received address, retrieving the codevector associated with that address from a respective one of the codebooks at the remote location; and c'"'"') summing the retrieved codevectors to obtain a substantial reproduction of the data vector.
-
-
30. A multi-stage vector quantization encoder comprising:
a plurality N of vector quantization stages arranged consecutively and each having a vector input, a residual vector output and a codevector address output, the residual vector output of each stage being coupled to the vector input of a succeeding stage, the vector input of an initial stage being coupled to receive a data vector indicative of a block of data to be compressed, each stage comprising; a vector quantizer having an associated codebook containing a plurality of codevectors, each codevector having an address associated therewith, said vector quantizer performing vector quantization on an input vector to said stage; a vector subtractor coupled to said vector quantizer for generating a residual vector based on a codevector selected by the vector quantizer and the input vector; a distortion calculator for determining a measure of distortion between the input vector and the selected codevector; a comparator for comparing the measure of distortion to a threshold value; and a gating device responsive to the comparator for allowing the residual vector to pass from the residual vector output of the stage to the vector input of a next succeeding stage only when the measure of distortion exceeds the threshold value, said encoder further comprising a transmitter for transmitting the addresses of codevectors selected at each stage to a remote location. - View Dependent Claims (31, 32, 33, 34, 35, 36, 37, 38, 39, 40)
Specification