Method and device for vector quantization

• US 8,335,260 B2
• Filed: 11/18/2008
• Issued: 12/18/2012
• Est. Priority Date: 12/05/2006
• Status: Active Grant

• Current Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: Li, Lixiong, Guo, Libin, Zhang, Liang, Zhang, Dejun, Wu, Wehai, Wang, Tinghong
• Primary Examiner(s): Shiferaw, Eleni
• Assistant Examiner(s): FIELDS, COURTNEY D
• Application Number:
  US12/273,201
• Publication Number:
  US 20090074076A1
• Time in Patent Office: 1,491 Days
• Field of Search: 375/240.22, 375/240.01
• US Class Current: 375/240.22
• CPC Class Codes: G10L 2019/0005 Multi-stage vector quantisation
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94
• CPC Class Codes: H04N 19/94 Vector quantisation

Abstract

A method for quantizing vector. The method includes: performing a quantization process on a vector to be quantized by use of N basic codebook vectors and the adjustment vectors of each of the basic codebook vectors, generating a basic codebook vector and an adjustment vector used for quantizing the vectors to be quantized, N being a positive integer larger than or equal to 1. According to the present invention, based on the method a device for quantizing vector is disclosed. According to embodiments of the present invention, the quantization of an input vector is done by introducing the modification vectors for the base codebook vectors, therefore the memory amount of the base codebook vectors is reduced effectively, and the calculation amount is merely the calculation amount required for going through N codebooks. Therefore, the complexity of the vector quantization could be decreased effectively.

Claims

1. A method for vector quantization comprising:

performing, by a hardware processor, a quantization process on a vector to be quantized by use of N basic codebook vectors and adjustment vectors of the N basic codebook vectors;

generating a basic codebook vector and an adjustment vector used for quantizing the vectors to be quantized;

combining the basic codebook vector and the adjustment vector to different basic sub-vectors as a joint codebook vector; and

selecting a joint codebook vector for quantization among possible joint codebook vectors according to the deviation between the joint codebook vector and the vector to be quantized;

wherein;

N is a positive integer larger than or equal to 1;

each basic codebook vector and each adjustment vector have same dimensions; and

selecting the joint codebook vector for quantization among possible joint codebook vectors according to the deviation between the joint codebook vector and the vector to be quantized comprises;

calculating a residual vector between the vector to be quantized and the current basic codebook vector obtained from the basic codebook unit;

wherein the residual vector has one or more residual sub-vectors, and the way of dividing into residual sub-vectors is the same as the way of dividing into basic sub-vectors;

for a basic sub-vector corresponding to an adjustment vector collection, selecting a best adjustment vector of the current basic sub-vector according to the deviation between the adjustment vector in the adjustment vector collection provided by the adjustment vector unit and the corresponding residual sub-vector;

accumulating a deviation of best adjustment vectors, and the deviation between the basic sub-vector not corresponding to the adjustment vector collection and the vector to be quantized, and using such a deviation as the deviation of the best joint codebook vector corresponding to the current basic codebook vector; and

comparing the deviation of the best joint codebook vector corresponding to each basic codebook vector, and selecting a joint codebook vector for quantization.

2. The method according to claim 1, wherein the adjustment vector is generated before the quantization process is performed on said vector, comprising:

calculating an average vector of the N basic codebook vectors;

calculating a distance from the N basic codebook vectors to the average vector; and

generating the adjustment vector the N basic codebook vectors according to the distance from the N basic codebook vectors to the average vector.

3. The method according to claim 2, wherein the adjustment vector of the basic codebook vectors is generated by generating the adjustment vector of the component of each dimension of the N basic codebook vectors.

4. The method according to claim 3, wherein generating the adjustment vector of the component of each dimension of the N basic codebook vectors comprises:

setting one or more scale factors corresponding to the adjustment vector of the component of each dimension of the N basic codebook vectors;

multiplying the distance from the basic codebook vectors to the average vector with the scale factors corresponding to the adjustment vector of a component of a current dimension,

obtaining a plurality of products corresponding to the component of the current dimension of the N basic codebook vectors, and

using the plurality of obtained products as an adjustment vector corresponding to the component of the current dimension of the N basic codebook vectors.

5. The method according to claim 2, wherein the method further comprises:

generating an index of the adjustment vectors.

6. The method according to claim 5, wherein generating the index number of the adjustment vectors comprises:

ordering the products corresponding to the component of the current dimension of the N basic codebook vector, and

using the sequence numbers obtained by the product as an indexes of the adjustment vector corresponding to the product.

7. The method according to claim 2, wherein the average vector is an a-dimension vector, where a is a positive integer larger than or equal to 1, and calculating the average vector of the N basic codebook vectors comprises:

setting a component of dimension i of basic codebook vector j be Y_j(i);

setting a component of dimension i of the average vector be AV(i) from a formula;

8. The method according to claim 7, wherein the distance from the basic codebook vectors to the average vector is calculated from the formula:

9. The method according to claim 1, wherein calculating the residual vector between the basic codebook vectors and the adjustment vector of the codebook vectors among the vector to be quantized and the N basic codebook vectors comprises:

calculating a residual vector between the basic codebook vectors among the vector to be quantized and the N basic codebook vectors.

10. The method according to claim 9, wherein performing a quantization process on a vectors to be quantized by use of N basic codebook vectors and the adjustment vectors of the basic codebook vectors comprises:

performing the quantization process on the residual vector between the vectors to be quantized and codebook vectors by use of the adjustment vectors of each of the codebook vectors.

11. The method according to claim 10, wherein the number of the adjustment vectors corresponding to the component of each dimension of the codebook vectors is one or more, and performing the quantization process on the residual vector between the vectors to be quantized and codebook vectors by use of the adjustment vectors of each of the codebook vectors comprises:

calculating an absolute residual between the component on each dimension of the residual vector and each adjustment vector of the component on the same dimension of the codebook vector; and

selecting a minimum absolute residual corresponding to the component of each dimension of the residual vector and the corresponding adjustment vector corresponding to the minimum absolute residual.

12. The method according to claim 11, wherein after selecting the minimum absolute residual corresponding to the component of each dimension of the residual vector and the corresponding adjustment vector corresponding to the minimum absolute residual, the method further comprises:

calculating the distortion between each residual vectors and the adjustment vector corresponding to the minimum absolute residual, including;

working out a square value of the minimum absolute residual corresponding to the component on each dimension of the residual vector, summing up the square values of the minimum absolute residues corresponding to the components on each dimension, and then using the sum as distortion between the residual vector and the adjustment vector corresponding to the same codebook vector.

13. The method according to claim 12, wherein after working out the square value of the minimum absolute residual corresponding to the component on each dimension of the residual vector, the method further comprises:

multiplying the square value with one or more corresponding weight coefficients, wherein said corresponding weight coefficients are real numbers.

14. The method according to claim 12, wherein each of the residual vector corresponds to a distortion, the number of the distortion is N, and the method further comprises:

selecting the minimum distortion from the N distortions, and using the codebook and the adjustment vector corresponding to the minimum distortion as a codebook and an adjustment vector for quantizing the vector to be quantized.

15. The method according to claim 14, wherein the method further comprises:

outputting the index of the codebook corresponding to the minimum distortion, and the index of the adjustment vector corresponding to the minimum distortion.

16. A device for quantizing vector comprising:

a codebook providing unit configured to transfer N codebook vectors corresponding to a vector to be quantized to a quantizing unit, and N is a positive integer larger than or equal to 1;

an adjustment vector providing unit configured to transfer adjustment vectors of the N codebook vectors to the quantizing unit; and

the quantizing unit configured to receive the adjustment vectors of the N codebook vectors from the adjustment vector providing unit, and from the codebook providing unit, perform a quantization process on a vector to be quantized by use of N codebook vectors and the adjustment vectors of each codebook vectors, and obtain codebook vectors and adjustment vectors for quantizing the vector to be quantized;

a residual vector calculating unit that calculates the residual vectors between the codebook vectors among the vector to be quantized and the N codebook vectors, and transferring the residual vectors to the quantizing unit;

a quantizing sub-unit configured to receive the adjustment vector of the N codebook vectors from the adjustment vector providing unit, and the residual vector from residual vector calculating unit, calculate the absolute residual between a component on each dimension of the each residual vector and each adjustment vector of the component on the same dimension of the corresponding codebook, select a minimum absolute residual corresponding to the component on each dimension of the residual vector, and transfer the calculation result of the minimum absolute residual corresponding to the component on each dimension of the residual vector to the calculating sub-unit;

a calculating sub-unit configured to receive the calculation result of the minimum absolute residual corresponding to the component on each dimension of each residual vector from the quantizing sub-unit, calculate a square value of the minimum absolute residual corresponding to the component on each dimension of the residual vector, sum the square values of the minimum absolute residues corresponding to the components on each dimension, calculate N distortions of N residual vectors using the sum as distortion between the residual vector and the adjustment vector, and transfer N distortions to the selecting sub-unit; and

a selecting sub-unit configured to receive N distortions from the calculating sub-unit, select a minimum distortion, and the codebook vectors and the adjustment vectors corresponding to the minimum distortion, and output the codebook vectors and the adjustment vectors corresponding to the minimum distortion,

wherein each basic codebook vector and each adjustment vector have same dimensions.

17. The device according to claim 16, wherein the device further comprises an adjustment vector generating unit configured to calculate the average vector of N codebook vectors, calculating a distance from the N codebook vectors to the average vector, generating one or more adjustment vectors of the N codebook vectors according to the distance from the N codebook vectors to the average vector, and transferring the generated adjustment vectors of the N codebook vectors to the adjustment vector providing unit.

18. The device according to claim 16, wherein the device further comprises an output unit for receiving the codebook vectors and the adjustment vectors corresponding to the minimum distortion from the selecting sub-unit, and outputting an index of the codebook corresponding to the minimum distortion and the index of the adjustment vector corresponding to the minimum distortion.

19. A method for vector quantization, comprising:

obtaining a vector to be quantized;

obtaining a basic codebook vector, wherein the basic codebook vector includes one or more basic sub-vectors, in the several basic sub-vectors;

at least one K-dimension (K≧

2) basic sub-vector corresponds to an adjustment vector collection which includes N adjustment vectors corresponding to the K-dimension basic sub-vectors;

at least one adjustment vector collection meets the requirement that N is less than the quantity of all possible combinations of different values of each dimension of any dimension of all adjustment vectors in the collection;

obtaining an adjustment vector corresponding to the basic sub-vector;

wherein the combination of the basic codebook vector and the adjustment vector correspond to different basic sub-vectors as a joint codebook vector, and selecting a joint codebook vector for quantization among possible joint codebook vectors according to the deviation between the joint codebook vector and the vector to be quantized; and

obtaining an index of the basic codebook vector corresponding to the selected joint codebook vector and an index of the adjustment vector,

wherein the K-dimension basic codebook vector and the corresponding adjustment vector have same dimensions;

wherein selecting a joint codebook vector for quantization among possible joint codebook vectors according to the deviation between the joint codebook vector and the vector to be quantized comprises;

calculating a residual vector between the vector to be quantized and the current basic codebook vector obtained from the basic codebook unit;

wherein the residual vector has one or more residual sub-vectors, and the way of dividing into residual sub-vectors is the same as the way of dividing into basic sub-vectors;

for a basic sub-vector corresponding to an adjustment vector collection, selecting a best adjustment vector of the current basic sub-vector according to the deviation between the adjustment vector in the adjustment vector collection provided by the adjustment vector unit and the corresponding residual sub-vector;

accumulating a deviation of best adjustment vectors, and the deviation between the basic sub-vector not corresponding to the adjustment vector collection and the vector to be quantized, and using such a deviation as the deviation of the best joint codebook vector corresponding to the current basic codebook vector; and

comparing the deviation of the best joint codebook vector corresponding to each basic codebook vector, and selecting a joint codebook vector for quantization.

20. The method according to claim 19, wherein the method further comprises:

obtaining a scale factor corresponding to the basic codebook vector;

wherein the adjustment vector collection corresponding to one of the basic sub-vectors of the current basic vectors is a product of the adjustment coefficient vector corresponding to the basic sub-vector and the scale factor.

21. The method according to claim 19, wherein the act of selecting a joint codebook vector for quantization among possible joint codebook vectors according to the deviation between the joint codebook vector and the vector to be quantized comprises:

adding the current basic codebook vector and optional adjustment vectors to form a joint codebook vector;

calculating the deviation between the joint codebook vector currently and the vector to be quantized; and

comparing the deviation between each different joint codebook vector and the vector to be quantized, and selecting a joint codebook vector for quantization.

22. The method according to claim 19, wherein obtaining the adjustment vector corresponding to the basic sub-vector comprises:

searching for the relation vector collection corresponding to the basic sub-vectors, wherein the relation vector collection is a n adjustment vector collection or is in a function relation with the adjustment vector collection; and

obtaining the corresponding adjustment vector according to the relation vector obtained from the relation vector collection; and

wherein the index of the adjustment vector is a sequence number of the relation vector corresponding to the adjustment vector in the relation vector collection.

23. The method according to claim 22, wherein searching for the relation vector collection corresponding to the basic sub-vectors comprises:

searching several sub-collections in the relation vector collection, the quantity of relation vectors contained in each sub-collection being equal to the quantity of all possible combinations of different values of each dimension of all relation vectors in the sub-collection;

searching for different values of each dimension of the corresponding relation vector in each sub-collection; and

wherein

the index of the adjustment vector is a sequence number be expressed as the serial number of the relation vector sub-collection that has the relation vector, and the sequence number of the relation vector in the relation vector sub-collection.

24. The method according to claim 19, wherein obtaining the adjustment vector corresponding to the basic sub-vector comprises:

searching for different values on each dimension of a relation vector corresponding to the basic sub-vector; and

determining whether the combination of values on each dimension currently is a selectable valid relation vector;

if so, obtaining the adjustment vector according to the currently obtained valid relation vector;

if not, going on searching until the search succeeds;

wherein the adjustment vector collection is the valid relation vector collection or is in a function relation with the valid relation vector collection, the index of the adjustment vector is a sequence number of the valid relation vector corresponding to the adjustment vector in the valid relation vector collection.

25. The method according to claim 24, wherein determining whether the combination of values on each dimension currently is a selectable valid relation vector comprises:

calculating a sequence number of the combination of the currently obtained values of each dimension in possible combinations; and

determining whether the value combination is a selectable valid relation vector according to a serial number.

26. A device for quantizing vector, comprising:

a vector input unit, configured to obtain the vector to be quantized;

a basic codebook unit, configured to provide a basic codebook vector, wherein the basic codebook vector includes one or more basic sub-vectors, in the several basic sub-vectors;

at least one K-dimension (where K≧

2) basic sub-vector corresponds to an adjustment vector collection which includes N adjustment vectors corresponding to the K-dimension basic sub-vectors;

at least one adjustment vector collection meets the requirement that N is less than a quantity of all possible combinations of different values of each dimension of any dimension of all adjustment vectors in the collection;

an adjustment vector unit, configured to provide an adjustment vector corresponding to the one or more basic sub-vectors; and

a quantizing unit, configured to obtain the basic codebook vector and the adjustment vector from the basic codebook unit and the adjustment vector unit, the combination of the basic codebook vector and one or more adjustment vectors corresponding to different basic sub-sectors as a joint codebook vector, and select a joint codebook vector for quantization among the possible joint codebook vectors according to a deviation between the joint codebook vector and the vector obtained by the vector input unit,

wherein the basic codebook vector and the corresponding adjustment vector have same dimensions;

wherein the quantizing unit comprises;

a residual calculating unit, configured to calculate the residual vector between the vector to be quantized and the basic codebook vector obtained from the basic codebook unit;

wherein the residual vector has one or more residual sub-vectors, and the way of dividing into residual sub-vectors is the same as the way of dividing into basic sub-vectors;

a residual quantizing unit, for a basic sub-vector corresponding to an adjustment vector collection, configured to select a best adjustment vector of the current basic sub-vector according to the deviation between the adjustment vector in the adjustment vector collection provided by the adjustment vector unit and the corresponding residual sub-vector; and

a deviation accumulating unit, configured to accumulate a deviation of the best adjustment vectors, and the deviation between the basic sub-vector not corresponding to the adjustment vector collection and the vector to be quantized, and use such a deviation as the deviation of a joint codebook vector corresponding to the basic codebook vector; and

a quantization selecting unit, configured to compare the deviation of the joint codebook vector corresponding to each basic codebook vector, and select a joint codebook vector for quantization.

27. The device according to claim 26, wherein the device further comprises:

a scale factor unit, configured to provide a scale factor corresponding to the basic codebook vector currently provided by the basic codebook unit;

wherein the adjustment vector provided by the adjustment vector is a product of the adjustment coefficient vector corresponding to the basic sub-vector and the scale factor provided by the scale factor unit.

28. The device according to claim 26, wherein the quantizing unit comprises:

a joint vector unit, configured to add up the current basic codebook vector obtained from the basic codebook unit and the adjustment vector obtained from the adjustment vector unit to form a joint codebook vector;

a deviation calculating unit, configured to calculate the deviation between the joint codebook vector currently generated by the joint vector unit and the vector to be quantized; and

a comparing and selecting unit, configured to compare the deviation between each different joint codebook vector obtained by the deviation calculating unit and the vector to be quantized, and select a joint codebook vector for quantization.

29. The device according to claim 26, wherein the quantizing unit comprises:

a collection providing unit, configured to provide a relation vector collection corresponding to the basic sub-vector, the relation vector collection being an adjustment vector collection or in a function relation with the adjustment vector collection; and

an adjustment generating unit, configured to search for the relation vector collection, and obtain the corresponding adjustment vector according to the relation vector obtained from the relation vector collection;

wherein the index of the adjustment vector obtained by the quantizing output unit is a sequence number of the relation vector corresponding to the adjustment vector in the relation vector collection.

30. The device according to claim 26, wherein the quantizing unit comprises:

a surplus searching unit, configured to search for different values on each dimension of the relation vector corresponding to the basic sub-vector; and

a vector selecting unit, configured to determine whether the combination of values on each dimension currently obtained by the surplus searching unit is a selectable valid relation vector;

if so, obtaining the adjustment vector according to the currently obtained valid relation vector;

if not, controlling the surplus searching unit to go on searching until the search succeeds;

wherein the index of the adjustment vector obtained by the quantizing output unit is a sequence number of the relation vector corresponding to the adjustment vector in the relation vector collection.