JPS6340505B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a highly efficient vector quantizer that provides quantization characteristics with minimum distortion based on the amplitude probability density of an input signal.

Conventional quantizers of this type have used scalar quantization to convert an input signal into a corresponding output signal level sample by sample.

FIG. 1 shows a conventional scalar quantizer. In the figure, 1 indicates the sequentially input signal sequence x ₁ , x ₂ ..., x _K
(K is an integer), 2 is a scalar quantizer, and 3 is an output signal sequence y ₁ , y ₂ , . . . , x _K.

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, input signal sequence 1 is quantized into output signal sequence 2 for each sample. In the scalar quantization characteristic that provides the minimum distortion, 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 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 quantization, and is a simple method that blocks input signal sequences for each predetermined sample and converts them together into blocks of output signal sequences at high speed. The aim is to provide a highly efficient vector quantizer.

Here, the principle of vector quantization will be explained. Let the input vector X={x ₁ , x ₂ , . . . , x _K } be a block consisting of K samples of the input signal sequence. Let Y = {y ₁ , y ₂ , . . . , y _N } be representative points of a K-dimensional signal space R ^K including all input vectors X, that is, a set of output vectors y _i . The division of R ^K with each y _i as a representative point (e.g. center of gravity) is R ₁ ,
When R ₂ ,...R _N , vector quantization Q is defined by the following equation.

Q: R ^K →Y where 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) The above vector quantization Q can be regarded as a cascade connection of encoding C and decoding D. At this time, the encoding C is the index set J of Y of R ^K = {1, 2,
..., N}, and decoding D is a mapping from J to Y. That is, C: R ^K → J D: J → Y Q=D・C. The index set, which is the encoded output, may be transmitted or recorded.

The vector quantization described above can realize highly efficient encoding in the case of an image signal or the like in which the input signal sequence has a correlation. Output vector that minimizes distortion of input vector
Vector quantization to convert y to ₁ is the input vector
The division that minimizes the total distortion with respect to the amplitude probability density of , and the set of output vectors that are representative points Y
You need to find out. This can be seen, for example, in document Y.
Lind, A. Buzo, and RMGray “An algorithm
for vector quantizer design”, IEEE Trans.
Commun, Vol.COM―28, PP.84―95.Jan.1980
is shown. It is obtained by clustering using a model of the target image. Vector quantization can be said to be the search for the output vector y _i that is closest to the input vector K (resulting in the least distortion) from the set Y of output vectors. In this case, when the number of output vectors is large, the conversion speed of vector quantization becomes slow. This drawback can be overcome by dividing R ^K in advance by the average value of the blocks and vector quantizing each. That is, it is a mixed form with scalar quantization. FIG. 3 shows an array of average value division output vectors in a two-dimensional signal space.

Here, based on FIG. 3, the case where the two-dimensional input vector X is vector quantized by clustering will be further explained below. As shown in the above literature, clustering generally involves collecting similar objects to create clusters (groups), and then calculating the structure of the object based on the similarities within each cluster and the differences between each cluster. This is one operation in the method of describing .

In FIG. 3, an elliptical region R indicates the entire space in which the input vector X exists, and a straight line ₁₁ indicates the average value threshold E(x _k ) for space division.
The straight line 12 is a straight line indicating x ₁ =x ₂ , and of the two subspaces obtained by dividing the entire space R by the straight line 1 ₁ , the upper side is R ₁ and the lower side is R ₂ .

Since image signals have a high correlation between pixels, input vectors are generally distributed in a concentrated manner near x ₁ =x ₂ .
In the 2-bit vector quantizer, four output vectors y ₁ , y ₁ ′, y ₂ , y ₂ ′ are set in advance in the signal space R. The input vector X is vector quantized into the output vector located at the shortest distance in space among the four output vectors.

In mean value division vector quantization _, by comparing the mean value _{μ of} the input vector
Determine which of R ₂ it exists in. In the example of FIG. 3, μE(x _k )→X∈R ₁ μ<E(x _k )→X∈R ₂ .

Next, vector quantization is performed using the two output vectors in the subspace. In this case, the distance calculation for vector quantization is reduced to two.

In this way, in the example shown in Figure 3, there are four output vectors (y ₁ , y ₂ ,
y ₁ ′, y ₂ ′) to 2 (y ₁ , y ₂ ) or (y ₁ ′, y ₂ ′)
decreases to

A block diagram of an embodiment of the mean value division vector quantizer according to the present invention is shown in FIGS. 4 and 5. Here, FIG. 4 shows an encoding section, and FIG. 5 shows a decoding section.

In the figure, 4 is an input vector, 5 is an input vector register, 6 is an average value calculator, 7 is a code table switch, 8 is a code table address counter,
9 is a first output vector code table memory;
10 is a second output vector code table memory, 11 is an output vector register, 12 is a sequence subtractor, 13 is a parallel absolute value calculator, 14 is a maximum element distortion detector, 15 is a minimum distortion output vector detector, 1
6 is an index signal, 17 is a code table switching signal, 18 is an output device consisting of an index latch, 19 is an output device output signal, and 20 is an output vector. Reference numeral 21 denotes an elemental distortion calculator comprising a parallel subtracter 12 and a parallel absolute value calculator 13, and 22 represents a minimax calculator comprising a maximum elemental distortion detector 14 and a minimum distortion output vector detector 15.

First, the operation of the encoding section shown in FIG. 4 will be explained.

K input signal sequences of the encoding section are collectively converted into blocks and taken into the input vector register 5 as input vectors X={x ₁ , x ₂ , . . . , x _K }.
At this point, the average value calculator 6 calculates the average amplitude value of K blocks (K is an integer of 2 or more),
The average value is sent to the code table switch 7. The code table switch 7 sets a threshold on this average value and determines which output vector code table memory to refer to. Next, the code table address counter 8
Output vectors y i are sequentially read out from either the output vector code table memory 9 or the second output vector code table memory 10 up to _i =1, 2, . . . , N. This output vector y _i is compared with the input vector X and the element distortion D _il =|y _il −X _l | (where l=
1, 2, . Next, the maximum value of the element distortion D _i1 is detected by the maximum element distortion detector 14, and is set as the maximum element distortion D _i of the output vector y _i . The maximum elemental distortions are determined for each of the output vectors y _i that are sequentially read out, and the minimum value of each maximum elemental distortion is determined as the minimum distortion D by the minimum distortion output vector detector 15 . That is, the minimum distortion is D=Min i[Max l|y _il −X _l |]. This output vector resulting in the minimum distortion, that is, the minimum distortion output vector is the vector quantization output of the input vector X. Minimum distortion output vector detector 1
When the minimum distortion output vector is detected, the strobe signal is sent to the index latch or output device 18, and the code table switching signal 17 and the index signal 16 which is the code table address counter of the output vector are sent to the index latch or output device 18. be included. The index signal 16 and the code table switching signal 17 are transmitted, recorded and reproduced as an output signal 19, and are input to the decoding section.

Next, the operation of the decoding section shown in FIG. 5 will be explained.

An output signal 19 from an output device 18 sent from the encoding section is taken into an input device 23 consisting of an index latch of the decoding section. Above output signal 1
Reference numeral 9 indicates that the index signal 16 serves as an address signal for the first output vector code table memory 9 or the second output vector code table memory 10, and that the code table switching signal 17 serves as selection information for which output vector code table memory to refer to. Become. The output vector y _i selected and read at the above address is latched in the output vector register 11, and an output vector 20 is obtained as the output of the decoding section.

As described above, the average value dividing vector quantizer according to the present invention divides the signal space in advance according to the average value of the blocks and refers to the output vector code table, so even if the output vector is doubled, the reference time is Does not increase. The coding efficiency η is the number of samples in a block K, the number of output vectors in one output vector code table N=2 ^S , the number of output vector code tables (corresponding to the number of average threshold levels) T= 2 ^t , then η=s+t/K bits/sample. For example, if K, N, and T are selected to be s+tK, highly efficient encoding of 1 bit or less per sample can be performed.

In addition, although the code table of the output vector is switched based on the average value of the block in the above example, the medium value may be used instead of the average value. Furthermore, although minimax approximation is used to calculate distortion between input and output vectors, it goes without saying that Euclidean norm (squared error) or absolute value norm may also be used.

Furthermore, although the present invention aims to increase the speed by parallel processing of vector operations, it is of course possible to perform sequential processing using a microprocessor or the like if the data rate of the input signal is slow.

Further, in the present invention, two output code tables are switched, but the output code table may be divided into a larger number of tables.

As described above, in the mean-value dividing vector quantizer according to the present invention, high-speed and highly efficient encoding can be realized by dividing the signal space in advance by the average value within a block and vector-quantizing this. effective.

[Brief explanation of drawings]

Fig. 1 is an explanatory diagram of a conventional scalar quantizer, Fig. 2 is an explanatory diagram of quantization characteristics of conventional scalar quantization, and Fig. 3 is a two-dimensional signal of the mean value division vector quantizer according to the present invention. An explanatory diagram showing the arrangement of output vectors in space, FIG. 4 is a block diagram showing an embodiment of the encoding section of the mean value division vector quantizer according to the present invention, and FIG. 5 shows the mean value division according to the present invention. FIG. 2 is an explanatory diagram showing an example of a decoding section of a vector quantizer. In the figure, 1 is an input signal sequence, 2 is a scalar quantizer, 3 is an output signal sequence, 4 is an input vector, 5 is an input vector register, 6 is an average value calculator, 7 is a code table switch, and 8 is a code table address counter; 9 is a first output vector code table memory; 10 is a second output vector code table memory; 11 is an output vector register;
12 is a parallel subtracter, 13 is a parallel absolute value calculator, 1
4 is a maximum element distortion detector, 15 is a minimum distortion output vector detector, 16 is an index signal, 17 is a code table switching signal, 18 is an output device, 19 is an output device output signal, 20 is an output vector, and 21 is an element distortion The arithmetic unit 22 is a minimax arithmetic unit, and 23 is an input device. In the drawings, the same or corresponding parts are denoted by the same reference numerals.

Claims (1)

[Claims] 1 After dividing the K-dimensional signal space of the input vector, which is obtained by blocking a predetermined K samples of the input signal (K is an integer of 2 or more) into multiple blocks, by the average value of the blocks, the minimum a plurality of output vector code table memories that obtain and store a plurality of sets of output vectors that result in distortion; an average value calculator that calculates the average value of blocks of input signals; a code table switcher that selects one of a plurality of output vector code table memories; a code table address counter that sequentially reads out output vectors from the selected output vector code table memory; and an input vector and the output vector that is sequentially read out. an elemental distortion calculator that calculates elemental distortion by comparing the elements for each corresponding element; a minimax calculator that detects an output vector that results in the minimum distortion by minimax approximation based on the elemental distortion obtained by the elemental distortion calculator; an encoding unit comprising an output vector code table address of an output vector resulting in minimum distortion and an output device that outputs a signal corresponding to the selected output vector code table memory number as an output signal; and an output signal from the encoding unit. An average value division vector quantizer, comprising: a decoding unit that reads out an output vector corresponding to an input vector from a plurality of output vector code table memories based on the above.