JPH0367375B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a vector quantization method suitable for cases where the amount of quantization information per vector is large.

<Prior art> In general, vector quantization converts multiple sample values into vectors E ₁ = (e ₁₁ e ₁₂ ... e _1p ), E ₂ = (e ₂₁ e ₂₂ ...
…e _2p )……E _o = (e _o1 e _o2 …e _op ), and the representative vector calculated in advance for each vector is
F ₁ = (f ₁₁ f ₁₂ ...f _1p ), F ₂ = (f ₂₁ f ₂₂ ... f _2p ) ......
From the dictionary of F _n =(f _n1 f _n2 . . . f _np ), the one with the minimum distortion, that is, the one closest to it, is selected, and that number is used as the code. In this way, one vector is encoded using one representative value, such as a number, so efficient encoding is possible even when the amount of encoded information (number of bits) B per one vector is small. . In addition, we created a dictionary (codebook) consisting of ^2B centroid vectors (representative vectors) and a dictionary consisting of learning samples (learning vectors) that are 10 times more than the number of centroid vectors to reflect the statistical distribution of data from the learning samples. If created in advance, even data with unusual or biased distributions can be encoded efficiently. The average distortion due to encoding can be reduced in proportion to 2 ^{- (2B/P)} , where P is the dimension of the vector.

However, for a given amount of information B, a dictionary of 2 ^B vectors and more than 10 times as many learning samples are required, and considering the storage capacity and calculation amount required for dictionary creation, the amount of information B should be less than 10. Be realistic. For example, if B≧20, it is impossible to create a dictionary using any existing electronic computer.
That is, in general vector quantization, there is a limit to reducing the average distortion associated with encoding due to the restriction on the amount of information B per vector. Also B
If the values of B were different, it was necessary to create a separate dictionary for each value of B.

On the other hand, scalar quantization is an independent quantization process for each sample, and processing is extremely simple. It becomes much larger than usual.

This invention utilizes the advantage of vector quantization that even data with a biased distribution can be efficiently quantized, and at the same time, vector quantization is capable of reducing distortion accordingly even when the amount of encoded information B is 20 or more. It provides law.

<Embodiment> FIG. 1 shows an example of an information transmission system to which the vector quantization method of the present invention is applied. Encoder 11 is communication path 1
2, and dictionaries 14 and 15 are connected to the encoder 11 and the decoder 13, respectively. The dictionary 14 includes a centroid vector section 16 in which centroid vectors representing representative values are stored, and a dispersion vector section 17 in which dispersion vectors indicating the spread of learning vectors belonging to each village (region) to which each centroid vector belongs are stored. Be equipped. The dictionary 15 on the decoder side has exactly the same configuration as the dictionary 14 on the encoder side, and includes a centroid vector section 18 and a dispersion vector section 19. The encoder 11 includes a vector quantizer 21 and a scalar quantizer 22, each using a centroid vector section 16 and a variance vector section 17.

The vector quantization method of the present invention will be explained by taking as an example the case where two-dimensional (P=2) data having the distribution shown in FIG. 2 is quantized with B=6 bits and B ₀ =2. It is assumed that data is distributed within a region surrounded by a closed curve 23 in FIG. normal
In quantization independent of X ₁ and X ₂ coordinates or quantization after coordinate transformation, as long as scalar quantization is used and quantization is performed for each data item, distortion for a certain amount of information will increase.

However, in this invention, vector quantization is performed in two stages. First, in the first quantization stage, the input data in which the sample value series is converted into a vector whose element is the sample value for each block is input to the vector quantization unit 21 from the input terminal 24, and is converted into a vector quantizer with B ₀ = 2. be converted into That is, the entire area is divided into 2 ^B0 areas 25a to 25d in accordance with the a priori distribution of the area 23, and each area, that is, each village 25a to 25d.
The center of gravity points C ₁ to _{C 4} are created as a dictionary.
In the vector quantization unit 21, the input vector is 2 ^B0
It is determined which of the villages 25a to 25d the person belongs to. For example, it is assumed that the input vector S belongs to the village 25a at the center of gravity _C1 .

Based on the results of the first vector quantization stage, the next second scalar quantization stage is performed.

The dispersion vector of the village 25a is represented by the center of gravity vector indicating its center of gravity _C1 . The one with the minimum distortion is selected from the coordinate-independent grid points 26 expressed by (B-B ₀ ) bits created using this dispersion vector. That is, in the example of the same figure, since B-B ₀ = 4 from the above assumption, each coordinate (X ₁ , X ₂ )
Thus, a total of 16 (2 ² × 2 ² ) grid points 26 are provided around the center of gravity C ₁ . In this way, the _B0 bit obtained in the first vector quantization stage is used to convey the number of region 25. Next, the number of the grid point 26 is transmitted to the decoder 13 from the terminals 27 and 28 as the output of the encoder 11 using the remaining (B-B ₀ ) bits.

In the decoder 13, the code of the sent B bits is
In this example, the vector S^ at the grid point 26a near the input vector S is decoded by referring to the center of gravity vector section 18 and the dispersion vector section 19 using the B0-bit village number and the B- _{B0 -} bit grid point number, respectively. and outputs to terminal 31.

During the first stage of vector quantization, multiple villages are selected as candidates, and for each candidate, the grid point with the minimum distortion is selected, and finally the combination of the ones with the minimum distortion is sent. In other words, the average distortion can be further reduced with the same amount of information.

In addition, the dispersion vector parts 17 and 19 have values for each coordinate for each center of gravity, but even if each is replaced with an average value, the overall distortion will not become very large, so a dictionary of dispersion vectors can be easily used as needed. It is possible to make it into something.

<Effects> As described above, according to the present invention, the two-stage quantization method using 2 ^B0 ×2 vector dictionaries allows the average distortion to be smaller than that of scalar quantization with the same amount of information. A comparative example in the case of audio sample values is shown in FIG. The horizontal axis is the number of bits per sample B
, the vertical axis shows the SN ratio, curve 32 is for one-dimensional optimal quantization (conventional case), curve 33 is for six-dimensional vector and Gaussian quantization, and curve 34 is 12
This is the case for dimensional vectors and Gaussian quantization. Vector quantization becomes difficult when the number of bits becomes larger than this, but vector quantization is possible with this invention, and the signal-to-noise ratio is also good. The difference becomes even larger for data with unique distributions.
According to the quantization method of this invention, it is expected that the distortion will be on the same level as the distortion of vector quantization using ^2B vector dictionaries. When the amount of encoded information B is 20 or more, a dictionary of 2 ^B is unrealistic, so B
The vector quantization method of the present invention is extremely effective for quantization when is 20 or more.

Furthermore, when B changes, the vector quantization method of this invention eliminates the need to change the dictionary as long as rules for setting grid points are established, and the amount of information per sample value (B/P) can be finely controlled. . In normal scalar quantization, the amount of information per sample value is basically limited to an integer value, and in normal vector quantization, a separate dictionary must be prepared for each change in B.

[Brief explanation of drawings]

Figure 1 is a block diagram showing an example of an information transmission system that encodes and transmits input data to which the vector quantization method of the present invention is applied, and Figure 2 is an example of quantization of data with a two-dimensional biased distribution. FIG. 3 is a diagram showing an example of comparison with a scalar quantization method using sample values in the audio frequency domain. 11: encoder, 12: communication path, 13: decoder,
14, 15: Dictionary, 16, 18: Centroid vector section, 17, 19: Dispersion vector section, 21: Vector quantization section, 22: Scalar quantization section.

Claims (1)

[Claims] 1. In a vector quantization method in which a series of sample values is quantized in batches, each input vector is quantized by the number of bits B (B is an integer).
When quantizing it, part of it B ₀ (B ₀ is 2 or more and
N (N is a positive integer greater than or equal to 2 and less than or equal to 2 ^B0 ) in descending order of quantization distortion between the input vector and the input vector from a dictionary consisting of 2 ^B0 centroid vectors. The first vector quantization stage selects candidate vectors, and the remaining (B-B ₀ ) is calculated based on a dictionary of variance vectors corresponding to each of the candidate vectors.
A second scalar quantization stage that uses bits to quantize the difference between the input vector and each of the candidate vectors for each coordinate axis, thereby determining the encoded information that minimizes distortion as a whole. Vector quantization method.