JPS6340507B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a quantizer that quantizes a signal sequence to minimize distortion according to the amplitude probability density function of an input signal.

Conventional quantizers of this type have been based on scalar quantization, in which the input signal is quantized sample by sample to the corresponding output signal level.

FIG. 1 shows a conventional scalar quantizer. In the figure, 1 indicates a signal sequence x ₁ , x ₂ ,..., which is input sequentially.
x _K (K is an integer), 2 is a scalar quantizer, and 3 is an output signal sequence y ₁ , y ₂ , . . . y _K converted into a quantization level corresponding to each sample of input signal sequence 1.

Now, it is assumed that the amplitude probability density of input signal sequence 1 takes a Gaussian distribution centered on the origin. In this case, in the conventional scalar quantization characteristic that minimizes the distortion of input signal sequence 1 and output signal sequence 2, as shown in FIG. 2, the quantization level becomes coarser as the distance from the origin increases. However, if there is a correlation between each sample of the input signal sequence 1, the output signal sequence 2 will not be optimally quantized even if quantization is performed to minimize distortion for each sample as in the conventional method.

This invention was made in order to eliminate the quantization loss caused by conventional scalar quantizers. Vector quantization involves dividing an input signal sequence into blocks for each predetermined sample and converting them into blocks of an output signal sequence at high speed. The purpose is to provide equipment.

Next, the principle of vector quantization will be explained. For a block consisting of K correlated input signal sequences (K is an integer of 2 or more), that is, input vector X = {x ₁ , x ₂ , ..., x _K }, K corresponding output signal sequences Let y _i ={y _i1 , y _i2 , . . . , y _iK } be one block, that is, the output vector.

Now assume a K-dimensional Euclidean signal space R ^K containing all input vectors X. In this case, vector quantization is a finite set of output vectors Y
= defined as the mapping of R ^K to {y ₁ , y ₂ ,...y _N }. Letting N divisions of R ^K be each R ₁ , R ₂ , . . . _RN , vector quantization Q is expressed as follows.

Q: R ^K →Y Here, R _i =Q ^-1 (y _i )={X∈R ^K :Q(X)=y _i } _N U ⁱ⁼¹ R _i =R ^K , R _i ∩R _j = 0 (i≠j) In the end, vector quantization Q is equal to encoding C and decoding D
It can be considered as a continuous connection. At this time, the encoding ^C is the index set J={1,
2,...N}, and the decoding D is mapping to J
This is mapping from to Y.

C: R ^K → J D: J → Y Q=D·C The vector quantization described above can achieve efficient quantization when there is a correlation between the input vectors X. FIG. 3 shows the signal space and output vector arrangement in two-dimensional vector quantization. Input signal x ₁
When there is a correlation between x 2 and x ₂ , the amplitude distribution concentrates near x ₁ = x ₂ . Therefore, the division R _i and its representative point (for example, the center of gravity) y _i where the sum of the error vectors of the input vector and the output vector is the minimum are optimized by clustering as in the example shown in FIG. 3. At this time, split
The input vector contained in R _i is vector quantized into an output vector y _i . In Figure 3, x ₁ , x ₂ >0
It is said that

FIG. 4 shows a block diagram of an encoding section of a vector quantizer according to the present invention, and FIG. 5 shows a block diagram of an embodiment of a decoding section.

In the figure, 4 is the input vector X, 5 is the input vector register, 6 is the output vector code table address counter, 7 is the output vector code table, 8 is the output vector register, 9 is the subtracter, 1
0 is the absolute value corrector, 11 is the maximum element distortion detector, 1
2 is a minimum distortion output vector detector; 13 is an output circuit 14 consisting of an index latch for an output vector resulting in minimum distortion; 15 is an output vector;

Next, the operation of the vector quantizer according to the present invention will be explained.

In the encoding section shown in Fig. 3, the signal sequence input from the signal source is blocked every K and K-dimensional input vector X = {x ₁ , x ₂ , ..., x _K } (each element corresponds to a sample value). ) is latched into the input vector register 5. At this point, from the probabilistic model of the input signal or the standard image data, for example, Y. Linde, A. Buzo, and
RMGray “An algorithm for vector quantizer
design”IEEE Trans.Commun., vol.COM―28,
Output vector with minimum distortion obtained using clustering shown in PP.84-95.Jan.1980
The output vectors y _i are sequentially read out from the output vector code table 7 in which the set Y={y ₁ , y ₂ , . . . y _N } of y _i is written. Note that clustering is generally an operation in a method that collects similar objects to create clusters (groups) and describes the structure of the object based on the similarities within each cluster and the differences between each cluster. be. output vector y _i
is sent to the output vector register 8 in the order of i=1, 2,...N, and is sent to the input vector X and the subtracter 9 for each element.
and the absolute value of the difference (hereinafter defined as element distortion D _il ) is calculated through the absolute value corrector 10. Maximum element distortion detector 1 of this element distortion D _il = {D _i1 , D _i2 ,...D _iK }
Detected at 1. The maximum element distortion detection calculation is the element distortion
It is sufficient to compare each element of D _il in a tournament format. Next, the minimum distortion output vector detector 12 calculates D _i =
The minimum distortion D is detected among {D ₁ , D ₂ ,...D _N }. This means that code table address counter 6 is i=
Comparative detection is performed while replacing the past minimum distortion at timings that sequentially change from 1, 2, . . . N.

That _is , _{the minimum} distortion D _of the input vector The index i at this time is taken in by the code output circuit 13 and outputted from the encoding section as an index signal i14.

Next, in the decoding section shown in FIG. 5, the index signal i14 is taken into the code input circuit 16 consisting of an index latch, and this is used as an address signal to refer to the output vector code table 7 in which the output vector y _i is stored. Then, the output vector y _i corresponding to the index signal i becomes the output signal 15
obtained as.

Here, if the index signal 14 of the encoding section in the vector quantizer according to the present invention is used for transmission or recording in memory, highly efficient encoding can be realized.

The coding ^efficiency η of the vector quantizer according to the invention becomes η=M/ _K bits/sample when input signal sequences x ₁ , x ₂ , . . . Therefore, the present vector quantizer can be used for highly efficient encoding of data such as images and audio by blocking and encoding correlated sample sequences.

Further, in the present invention, a high-speed vector quantizer can be realized because the output vector code table reference method, parallelization of vector operations, and minimax approximate distortion detection method are adopted for minimum distortion calculation.

Furthermore, by introducing a microprocessor, it is of course possible to sequentially process this vector operation for each element.

Alternatively, the output vector code table may have this structure and the minimax comparison with the input vector may be performed using a tree search method.

Furthermore, when there is a three-channel parallel signal sequence such as a color image signal, it is of course possible to block the signal sequence across the channels and use it as an input vector.

As described above, according to the present invention, the input signal sequence is divided into blocks, vectorized all at once, and vectorized as a continuous connection of the encoder and decoder so that the input signal sequence is converted into a block of the output signal sequence that has the minimum distortion by minimax approximation. Since the quantizer is configured, there is an advantage that highly efficient encoding of the input signal can be realized.

[Brief explanation of the drawing]

FIG. 1 is an explanatory diagram of a conventional scalar quantizer, FIG. 2 is an explanatory diagram of quantization characteristics of a conventional scalar quantizer, and FIG. 3 is an explanatory diagram of quantization characteristics of a vector quantizer according to the present invention. , FIG. 4 is a block diagram showing an embodiment of the encoding section of the vector quantizer according to the present invention, and FIG. 5 is a block diagram showing an embodiment of the decoding section of the vector quantizer according to the present invention. . In the figure, 2 is a scalar quantizer, 5 is an input vector register, 6 is a code table address counter, 7 is an output vector code table, 8 is an output vector register, 9 is a subtracter, 10 is an absolute value corrector, and 11 is a A maximum element distortion detector, 12 a minimum distortion output vector detector, and 13 a code output circuit.
In the figures, the same reference numerals indicate the same or corresponding parts.

Claims (1)

[Claims] 1 Divide the signal space into K-dimensional Euclidean signal space distribution of input vectors obtained by dividing the input signal sequence into K blocks (where K is an integer greater than or equal to 2), and divide the signal space into multiple representative points so as to minimize distortion. an output vector code table that stores output vectors; a subtracter that calculates the difference between each element of the output vector and the input vector that are sequentially read from the output vector code table; and an output vector code table that stores output vectors; an absolute value corrector that calculates the distortion for each element by converting it into a value, a maximum element distortion detector that calculates the maximum value of the distortion compared for each element, and an output vector that is sequentially compared with the input vector. A minimum distortion output vector detector that detects the output vector with the minimum maximum distortion value for each element, and a code output that encodes and outputs the address of the output vector code table corresponding to the output vector with the minimum distortion. and a decoding unit that decodes the encoded output of the output vector code table address and reads out an output vector corresponding to the input vector so as to cause minimum distortion. Vector quantizer.