JP2583089B2 - Adaptive vector quantization - Google Patents

Description

Description: BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an adaptive vector quantization method for encoding and transmitting digital signals such as images and sounds with high efficiency.

[Prior art] In the conventional adaptive vector quantization schemes ^{(1) and (2)} , after normalizing the amplitude of the input vector, the codebook size is switched according to the normalization coefficient (for example, the standard deviation) to change the code. The transmission method used for transmission has been used. In this method, when the amplitude of the input vector is large, a slight vector quantization error is decoded as a large quantization error on the receiving side, and is used for vector quantization for an input vector having a large amplitude. A process for reducing a quantization error by setting a large codebook size is performed. Conversely, when the amplitude of the input vector is small, even if the codebook size is set to a small value, the vector quantization error does not increase so much, and the amount of information necessary for coding the code vector can be reduced. Conversion efficiency can be improved. The normalization coefficient is quantized and transmitted with the vector index. Therefore, by determining the codebook size according to the normalization coefficient of the quantized input vector, the vector quantization error in a state where the quantized normalization coefficient is multiplied is controlled, and the encoding efficiency is reduced. It can be improved. This is because the codebook size can be known before the vector quantization decoding by decoding the normalization coefficient before the vector index.

However, the pattern of the normalized input vector and the pattern in the codebook are significantly different,
When the input vector and the quantization vector are almost orthogonal, there is a disadvantage that the vector quantization error increases as compared with the case where no encoding is performed. As an example, an input vector is X, a quantization vector is Y, a distance between the vectors X and Y is represented by d (X, Y), and a distance scale is defined by a Euclidean distance. If X⊥Y (⊥: orthogonal), the quantization error due to performing vector quantization is d (X, Y) = (XY-XY) = (XX) −2 ( XY) + (YY) = (XX) + (YY) (1) The reason is that (X · Y) = 0. However, (·) represents the inner product of the vectors. On the other hand, if no quantization is performed, the quantization error is d (X, 0) = (X−0 · X−0) = ( XX) (2) Comparing the expressions (1) and (2), d (X, Y) ≧ d (X, 0) (3), and the error increases due to the vector quantization.

As a solution to this error increase, gain / shape (Gain
/ Shape) There is vector quantization ⁽³⁾ . Gain / Shape vector quantization is a method that uses a square error criterion to simultaneously select a quantized representative vector from normalized code vectors and calculate its amplitude value. When the Euclidean distance is defined as a distance measure between vectors, it is not always necessary to perform vector quantization after normalizing an input vector with a standard deviation. That is, as shown in FIG. 5, the principle is based on the principle that the optimal quantization vector according to the square error criterion of the input vector is orthogonal projection. In FIG. 5, X is an input vector, and Y is a normalized code vector (Shape vector). After performing the inner product operation of X and Y, the value, that is, the Shape vector that gives the maximum value of the projection amount from the input vector to the quantization vector is set as the quantization representative vector, and the maximum value of the inner product is quantized as the gain. , The vector index and the quantized Gain may be encoded and transmitted.

FIG. 6 shows a relationship between an input vector and a quantization vector in conventional normalization vector quantization. In the vector quantization shown in FIG. 6, an input vector is normalized by a normalization coefficient such as a standard deviation, and then compared with a code vector having a unit norm, and a code vector having the smallest error vector is selected. As a result, the finally obtained quantization vector is a vector obtained by multiplying the code vector by the normalization coefficient n. If the distance measure used for the code vector search is the L1 norm (average absolute value), the orthogonality between the quantization vector and the error vector cannot be established. That is, the square error between the input vector and the quantization vector is not minimized. Even if the L2 norm (the Euclidean distance and the search result are equivalent) is used for the search, the orthogonality is not guaranteed at the time of multiplication by the normalization coefficient. From FIG. 6, it can be seen that it is difficult to perform optimal quantization in the sense of a square error, that is, S / N.

In the Gain / Shape vector quantization, the finally obtained quantization vector Q (X) is given by Q (X) = Q (g) Y (4) where Q (g) is the quantization Gain.

By the way, when trying to adaptively determine the codebook size according to the size of Gain in the Gain / Shape vector quantization, the shape vector must be determined prior to the calculation of Gain. It is impossible to determine after the calculation. Also,
Gain obtained with quantized shape vector even if codebook size is determined by standard deviation of input vector
Does not always coincide with the standard deviation, and takes a value equal to or smaller than the standard deviation. Therefore, the receiving side cannot know the codebook size from the value of Gain. Therefore, there is a disadvantage that the adaptation of the codebook size cannot be directly introduced to the Gain / Shape vector quantization. Also, when attempting to transmit codebook size information as additional information independently of Gain and vector index when performing Gain / Shape vector quantization of each vector, a sudden increase in the amount of encoded information is caused. There was a disadvantage that the efficiency was reduced.

References (1) Murakami et al .: "Adaptive Tree Search Vector Quantization Encoder", JP-A-60-191566. (2) Watanabe, Kuroda, Hashimoto: "Study on Adaptation of Vector Quantization", Showa 61 1165. (3) A.Buzo, AHGray, Jr., RMGray and JDMarkel:
“Speech coding based upon vector quantization”, IE
EE Trans. ASSP-28, No. 5, pp. 562-574 (Oct. 1980). [Means for Solving the Problems] According to the present invention, the type of codebook size to which a code vector belongs is limited by the amplitude of the input vector, that is, the standard deviation or variance, and the gain / shape vector quantum Then, an optimum one is selected from a combination of the plurality of gains and the shape vector, and the codebook size is encoded as additional information together with the gain and the shape vector index.

[Operation] In this way, the type of codebook size is limited in accordance with the amplitude of the input vector, and gain / shape vector quantization is performed using the limited codebook, and the optimal one is selected from among them. The encoding efficiency of the additional information indicating the codebook size can be improved.

FIG. 1 shows an embodiment of the present invention.

The input vector is input from a terminal 1 and a standard deviation calculation circuit 2 calculates a standard deviation of a signal included in the vector. According to the obtained standard deviation, the codebook size is limited to several types in the circuit 3 for limiting the type of codebook size. For example, the obtained standard deviation σ is compared with an appropriate threshold value Th, and the type of codebook size is limited in the following procedure.

If σ <Th, a set of an optimal quantized Shape vector and Gain is obtained for three types of codebooks of size I ₁ bit, I ₂ bits, and I ₃ bits. If σ ≧ Th, size I ₂ bits, For the three types of codebooks of I ₃ bits and I ₄ bits, a set of the optimal quantized Shape vector and Gain is obtained.

FIG. 2 shows a detailed embodiment of the circuit 3 for determining the type of codebook size shown in FIG.
The minimum codebook size determination circuit 102 determines the minimum codebook size 104 and the maximum codebook size determination circuit 103 determines the maximum codebook size 105 according to the standard deviation of the elements of the input vector from 1. The information on the lower and upper limits of the codebook size is given to the codebook sequential selection circuit 106, and each codebook in the codebook group 4 is delivered to the inner product operation circuit 5.

Codebook 41 of I ₁ bit for different codebook set 4 sizes, I _2-bit codebook 42, I ₃ bits of codebook 43, ... N species codebooks to the codebook 44 of I _N bits are available You. Here, N is an arbitrary natural number.
In order to find the optimal quantized shape vector, the inner product operation circuit 5 compares the input vector with the Shap in the codebook.
The dot product with the e-vector is calculated. For each codebook, the Shape vector that gives the inner product maximum is found,
That is the optimal Shape vector according to the codebook. The inner product value at this time is Gain. If sigma <should been limited to I _1, I ₂ and I ₃ bits of codebook types when Th, 3 sets of (codebook number below, Sha
pe vector index, Gain) is output.

These three sets of information are input to the codebook number, Shape vector index, and Gain selection determination circuit 6, and one set of information to be transmitted is determined. For this determination method, for example, the method described below can be used.

 First, the quantization error Ei of each set is obtained.

Ei = σ ² −Gi ² (i = 1,2,3) (5) If the value of Ei is less than a certain suitable threshold Te, the information of the smallest set of codebook size shall be transmitted. If the value of Ei is equal to or larger than Te, information of a set of code vectors that gives the minimum value of the quantization error within the codebook size specified by the standard deviation is transmitted. That is, if Ei <Te, the codebook number Ma to which the vector to be sent belongs is Ma = arg (min.I _K ) (k = 1,2,3), and the set of information to be sent is (Ma, S _Ma , G _Ma ).

If Ei ≧ Te, the codebook number Mb to which the vector to be sent belongs is Mb = arg (min.E _K ) (k = 1,2,3), and the set of information to be sent is (Mb, S _Mb , G _Mb ).

The set of information to be sent, ie (codebook number, Shape
The vector index (Gain) is input to the variable-length encoding circuit 7, subjected to variable-length encoding collectively, and then output from the data output terminal 8. This batch variable-length coding can greatly reduce coding information for redundant combinations, and is very effective in improving coding efficiency. Here, Gain is scalar-quantized, and a quantization number is assigned. For simplicity,
Now, consider a case where the Gain quantization number is 1 if Gain is equal to or greater than the threshold Th, and the Gain quantization number is 2 if Gain is less than Th, and a codebook number and a Gain quantization number are collectively encoded. If the standard deviation σ of the input vector is less than Th,
The codebook number is 1 or 2 or 3, and σ
Is greater than or equal to Th, the codebook number is 2 or 3 or 4, and the portion marked with a circle in FIG. 3 is a possible combination. The number of states is seven, and since the number of states when codebook numbers and gain quantization numbers are separately encoded and transmitted is eight, the number of states to be encoded is reduced. If the number of states to be encoded is reduced, the amount of information to be allocated can be small, and the information to be transmitted can be reduced.
In the example of FIG. 5, the codebook type is 4 and the number of gain quantization numbers is 2. However, in practice, the type and the number of quantization numbers are often large. For example, codebook type is 8, Gain
In an example in which the number of quantization numbers is four, the number of states as shown in FIG. 4 can be created by the way of determining the threshold value Th (a circle indicates a possible state).

In the example of FIG. 4, first, vector quantization is performed on an input vector having a standard deviation less than the threshold value between the gain quantization numbers 1 and 2 using the codebook of codebook number 1 or 2 or 3. , And then gain quantization number 2
If the input vector has a standard deviation smaller than a threshold value between the codebook numbers 3 and 4, the quantization is performed using the codebook of the codebook number 4 or 5 or 6. If the input vector has a standard deviation less than the threshold value, vector quantization is performed using the codebook of the Corso book number 7, and finally, the gain quantization number 3
For an input vector having a standard deviation equal to or larger than a threshold value between と and ４, a vector quantization is performed using a codebook of codebook number 8. In the example of FIG.
There are 16 possible states, codebook number and Ga
The number of states when the in-quantization numbers are separately encoded and transmitted is 32
As a result, the number of states to be coded is reduced by half. That is, it is possible to reduce the number of bits required from 5 bits to 4 bits for identification of the number of states. In the examples of FIGS. 3 and 4, Shap is used for simplicity.
Although the case where the e-vector index is not included in the batch coding is shown, the coding efficiency can be improved only by the batch coding of the codebook number and the gain quantization number as in the examples of FIGS. 3 and 4. It is.

In the embodiment described above, the N types of codebooks prepared in the vector quantizer are not switched and used, but the types of additional information to be transmitted by switching among the limited types are reduced. A major feature is that the coding efficiency is thereby improved. In the above example, N =
If the number is 10, the three types clearly have a small number of states, so that the identification information can be reduced by simply using a fixed-length code.

Although the data input to the circuit 3 for determining the type of the codebook size is the standard deviation, there is no problem even if the variance of the input vector is used. In addition, the codebook groups 4 having different sizes are arbitrarily set to N types, but a tree search codebook does not pose a problem. When a tree search codebook is used, changing the search step corresponds to changing the codebook size. Further, even if codebooks of the same codebook size and different contents exist in any of the N types, there is no problem if an algorithm that can determine the superiority and deterrence by the selection determination circuit 6 is used. Also, the standard deviation σ
Is compared with the threshold value Th in the above example, but there is no problem in dividing it into any number of cases. Also, an example has been shown in which the types of codebooks specified by the standard deviation σ are limited to three types, but any type from one type to N types can be independently selected. However, specifying N codebook sizes for all the standard deviations σ is not very advantageous because the effect of reducing the amount of additional information is weakened.
If one type of codebook size is specified for all the standard deviations σ and the sizes are equal, this corresponds to stopping the adaptive switching capability of the codebook. Therefore, the circuit 3 for determining the type of codebook size needs to be carefully designed so as to achieve both the codebook switching capability and the reduction of the amount of additional information. An example of an algorithm for determining a set of information to be transmitted (codebook number, shape vector index, gain) has been described above, but a method of always selecting a minimum set of codebook size without using a threshold Te. It is clear that any other method is acceptable as long as it is an algorithm that can be limited to one set of information, such as a method that always selects a set that gives the minimum value of quantization error, or a method that appropriately combines them. It is.

[Effects of the Invention] As described above, by performing the Gain / Shape vector quantization by designating the codebook size to which the codebook vector belongs by the amplitude of the input vector, it has the ability to adaptively switch the codebook size. In addition, there is an advantage that the encoding efficiency of the additional information indicating the codebook size can be improved.

[Brief description of the drawings]

FIG. 1 is a block diagram showing an embodiment of the present invention, and FIG. 2 is a circuit 3 for determining the type of codebook size in FIG.
FIG. 3 is a diagram showing an example of the number of states between a codebook number and a gain quantization number, and FIG. 4 is another example of the number of states between a codebook number and a gain quantization number. FIG. 5 is a diagram for explaining gain / shape vector quantization, and FIG. 6 is a diagram for explaining normalized vector quantization.

Claims (1)

(57) [Claims] An input vector formed by blocking an input signal sequence for every predetermined number is given by a code vector (Shape vector) normalized with respect to a standard deviation and an inner product value of the input vector and the code vector. In the gain / shape vector quantization method for performing quantization separately for gain and shape, the type of codebook size to which the code vector belongs is limited by the amplitude of the input vector, and the gain / shape is calculated using a plurality of codebooks. Adaptive vector quantization that performs vector quantization, selects the best combination of these multiple gains and shape vectors, and codes the codebook size as additional information together with the gain and shape vector index Law.