METHOD AND DEVICE FOR VECTOR QUANTIZATION

• US 20090074076A1
• Filed: 11/18/2008
• Published: 03/19/2009
• 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: Guo, Libin, Wu, Wehai, Wang, Tinghong, Li, Lixiong, Zhang, Liang, Zhang, Dejun
• Granted Patent: US 8,335,260 B2
• Time in Patent Office: Days
• US Class Current: 375/240.220
• 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 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; and

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

wherein

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

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 claims 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;

$A<br><br><br><br>V<br><br>\left(i\right)=\frac{\underset{j=1}{\overset{N}{\sum <br><br>}}<br><br>Y_j<br><br>\left(i\right)}{N},i=1,2,\mathrm{\dots <br><br>}<br><br>,a;<br><br>$

and

obtaining the average vector from a formula;

AV(a)={AV(i),i=1, 2, . . , a}.

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

$A<br><br><br><br>V<br><br><br><br>S<br><br>\left(j\right)=\sqrt{\frac{\underset{i=1}{\overset{a}{\sum <br><br>}}<br><br><br><br>{\left[Y_j<br><br>\left(i\right)-A<br><br><br><br>V<br><br>\left(i\right)\right]}^2}{a}},j=1,2,\mathrm{\dots <br><br>}<br><br>,N,$

wherein AVS(j) is the distance from the basic codebook vector j to the average vector.

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

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

10. The method according to claim 9, 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.

11. The method according to claim 10, 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 codebooks by use of the adjustment vectors of each of the codebooks.

12. The method according to claim 11, wherein the number of the adjustment vectors corresponding to the component of each dimension of the codebooks is one or more, and performing the quantization process on the residual vector between the vectors to be quantized and codebooks by use of the adjustment vectors of each of the codebooks 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.

13. The method according to claim 12, 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.

14. The method according to claim 13, 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.

15. The method according to claim 13, 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.

16. The method according to claim 15, 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.

17. A method for generating adjustment vector of codebook, comprising:

calculating an average vector of N codebooks, wherein N is a positive integer larger than or equal to 1;

calculating a distance from each of the codebooks to the average vector; and

generating an adjustment vector of the codebooks according to the distance from the codebooks to the average vector.

18. The method according to claim 17, wherein generating an adjustment vector of each of the codebooks comprises:

generating an adjustment vector of the component on each dimension of each of the codebooks.

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

generating an index of the adjustment vectors.

20. The method according to claim 19, wherein generating an index of each of the adjustment vectors comprises:

ordering the products corresponding to the component of the current dimension of the codebooks, and using the sequence numbers obtained by the product as the indexes of the adjustment vector corresponding to the product.

21. A device for quantizing vector comprising:

a codebook providing unit that is adapted to transfer N codebooks corresponding to a vector to be quantized to the quantizing unit, and N is a positive integer larger than or equal to 1;

an adjustment vector providing unit that is adapted to transfer adjustment vectors of the N codebooks to the quantizing unit; and

a quantizing unit that is adapted to receive the adjustment vectors of the N codebooks 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 codebooks and the adjustment vectors of each codebooks, and obtain codebooks and adjustment vectors for quantizing the vector to be quantized.

23. The device according to claim 21, wherein the device further comprises a residual vector calculating unit that calculates the residual vectors between the codebooks among the vector to be quantized and the N codebooks, and transferring the residual vectors to the quantizing unit.

24. The device according to claim 23, wherein the device further comprises a quantizing sub-unit, a calculating sub-unit, and a selecting sub-unit, wherein

the quantizing sub-unit is adapted to receive the adjustment vector of the N codebooks 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;

the calculating sub-unit is adapted 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

the selecting sub-unit is adapted to receive N distortions from the calculating sub-unit, select a minimum distortion, and the codebooks and the adjustment vectors corresponding to the minimum distortion, and output the codebooks and the adjustment vectors corresponding to the minimum distortion.

25. The device according to claim 24, wherein the device further comprises an output unit for receiving the codebooks 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.

22. The device according to claim 22, wherein the device further comprises an adjustment vector generating unit for calculating the average vector of N codebooks, calculating a distance from the N codebooks to the average vector, generating one or more adjustment vectors of the N codebooks according to the distance from the N codebooks to the average vector, and transferring the generated adjustment vectors of the N codebooks to the adjustment vector providing unit.

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

27. The method according to claim 26, 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.

28. The method according to claim 26, 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.

29. The method according to claim 26, 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.

30. The method according to claim 26, 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 an 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.

31. The method according to claim 30, 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.

32. The method according to claim 26, 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

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

33. The method according to claim 32, wherein judging 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

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

34. A device for quantizing vector, comprising:

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

a basic codebook unit, adapted 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, adapted to provide an adjustment vector corresponding to the one or more basic sub-vectors; and

a quantizing unit, adapted 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.

35. The device according to claim 34, wherein the device further comprises:

a scale factor unit, adapted 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.

36. The device according to claim 34, wherein the quantizing unit comprises:

a residual calculating unit, adapted 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, adapted 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, adapted 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, adapted to compare the deviation of the joint codebook vector corresponding to each basic codebook vector, and select a joint codebook vector for quantization.

37. The device according to claim 34, wherein the quantizing unit comprises:

a joint vector unit, adapted 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, adapted 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, adapted 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.

38. The device according to claim 34, wherein the quantizing unit comprises:

a collection providing unit, adapted 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, adapted 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.

39. The device according to claim 34, wherein the quantizing unit comprises:

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

a vector selecting unit, adapted to judge 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.