JPS6341253B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to vector quantization that blocks a plurality of input signal sequences and quantizes the blocks.

Let us briefly explain the raw materials for vector quantization. K input signal sequences are combined into an input vector X={x ₁ ,
x ₂ , ..., x _K }. At this time, the predetermined divisions of the K-dimensional signal space ^RK are R ₁ , R ₂ , ..., R _N , and the set of representative points (for example, the center of gravity) of each division is Y = {y ₁ ,
y ₂ , ..., y _N }. The process of using this representative point y _i as an output vector corresponding to the input vector X included in division R _i is called vector quantization. Vector quantization Q is defined by the following equation.

Q: R ^K →Y Here, R _i =Q ^-1 (yi)={X∈R ^K :Q(X)=y _i } _N U ⁱ⁼¹ Ri=R ^K , R _i ∩R _j =0 (i≠J) Above, the vector quantization Q is the encoding C and the decoding D
Represented as a continuation of the connection. The encoding C is a set of output vectors in R _K Y = {y ₁ , y ₂ , ...,
y _N } index set J = {1, 2, ...,
N}, and the decoding D is mapping from J to Y
This is mapping to. That is, C: R ^K → J D: J → Y Q=D・C. In vector quantization, the encoded output J is transmitted or recorded.

Vector quantization can achieve particularly efficient quantization when a signal sequence such as an image or audio signal has a predetermined correlation or when the amplitude probability density is biased. Furthermore, by reducing the number of sets of output vectors of vector quantization, data compression can be achieved when transmitting or storing the encoded output.

Input vector X in conventional vector quantization
The relationship between Y and the output vector set Y is shown in FIG. 1 on a two-dimensional signal space ^R2 . x ₁ = x ₂
indicates a DC component, and if there is a correlation between the two samples, the signal will be concentrated and distributed around x ₁ = x ₂ . For such a model of the amplitude distribution of a predetermined input signal source, a clustering algorithm is used to perform division and extraction of a set Y of output vectors that minimizes the sum of distortions of input vectors and output vectors.

However, when considering an image signal as an actual input signal source, specific model fitting such as an AR model is possible for AC signal components, but model fitting is difficult for DC components. Furthermore, the amplitude value of the alternating current component varies greatly depending on the screen, making it difficult to model them. That is, in image signals, it is difficult to model the brightness and contrast of the screen, and the efficiency of a fixed vector quantizer deteriorates.

This invention was made to eliminate these drawbacks. It normalizes and vector quantizes only the AC signal component obtained by subtracting the average value of the block from the input signal sequence, and adaptively performs vector quantization using the intra-block variance. The present invention aims to provide an adaptive vector quantizer that optimally vector quantizes all input signal sequences by controlling the amplitude of the output vector.

Now, the output vector y _i corresponding to the input vector
The intra-block average value m _A = E _A (xl) (A represents the intra-block operation) is removed from , and the normalization constant, for example, the standard deviation σ _A = [E _A {(x _l − m _A ) ² }] ¹ A set of normalized output vectors y′ _i normalized by ^/2 Y′={y′ ₁ ,
y′ ₂ , ..., y′ _N }. At this time, the normalized output vector is
Output vector y′ _i obtained by adaptively controlling y′ _i
The relationship is shown in Figure 2.

Next, FIGS. 3 and 4 show block diagrams of an embodiment of a vector quantizer according to the present invention. Here, FIG. 3 shows an encoding section, and FIG. 4 shows a decoding section.

In the figure, 1 is an input vector, 2 is an input vector register, 3 is an average value calculator, 4 is a standard deviation calculator, 5 and 10 are parallel subtracters, 6 is a code table address counter, and 7 is a normalized output vector code. Table memory, 8 normalized output vector register, 9 parallel multiplier, 11 parallel absolute value calculator, 12 maximum element distortion detector, 13 minimum distortion normalized output vector detector, 14 output vector index , 15 is the block average value, 16 is the block standard deviation, 17 is the index latch, 18
is an encoded output circuit, 19 is an encoded output signal, and 20
is a decoding input circuit, 21 is a parallel adder, 22 is a decoding output circuit, and 23 is an output vector.

Next, the operation will be explained.

First, in the encoding section shown in FIG. 3, a plurality of input signal sequences are collectively blocked and latched into the input vector register 2 as input vectors X={x ₁ , x ₂ , . . . , x _K }. At this point, the average value calculator 3 and the standard deviation calculator 4 simultaneously calculate the scalar average value of one block of the input vector
m _A and standard deviation σ _A are calculated. Here, m _A = E _A (x _l ) = 1/K _k 〓 ^I=1 x _l σ _A = [E _A {(x _l − m _A ) ² }] ^1/2 = [1/K _k 〓 ^{I =1} (x _l −m _A ) ² 〕 ^1/2 .

_{Next , the input vector K} −
m _A }. This DC separated input vector
Execute a procedure to find a normalized output vector y′ _i that matches X′. Therefore, the code table address counter 6 sequentially counts up from i=1 to N and converts the normalized output vector to y' ₁ , y' ₂ , . . .
Read up to y′ _N from the normalized output vector code table 7. The set Y' of normalized output vectors _y'i is modeled on the set of input vectors Normalized input vector X″={(x ₁ −
m _A )/σ _A , (x ₂ − m _A )/σ _A , ..., (x _K −
It is determined in advance by cluttering, which involves dividing the K-dimensional signal space formed by the set of m _A )/σ _A } and selecting a representative point (normalized output vector). In this case, the division of the signal space and the selection of the representative point (e.g. center of gravity) that results in the minimum distortion are described in, for example, Document Y.
Linde, A. Buzo, and RMGray “An algorithm
for vector quantizer design,” IEEE Trans.
Commun., vol.COM−28, pp.84−95, Jan.
It is recommended to use the Euclidean norm or minimax approximation as a definition of distortion for convergence by repeated clustering as shown in 1980.

Here, clustering is an operation in a method that generally collects similar items in terms of correspondence to create clusters (groups) and describes the structure of the target based on the similarities within each cluster and the differences between each cluster. It is.

Normalized output vector y′ _i sequentially read out from the normalized output vector code table memory 7
₌ {y _i1 , y _{i2 ,} . The outputs of the parallel multiplier 9 and parallel subtracter 5 are passed through a parallel subtracter 10 and a parallel absolute value calculator 11 to K.
The following calculation is performed for each element of the dimensional vector to obtain element distortion D _l (l=1, 2, . . . , K).

D _il = |σ _A ·y′ _il −(x _l −m _A )| Here, y _il =σ _A ·y′ _il +m _A is the element of the output vector corresponding to x _l . The maximum element distortion detector 12 detects the maximum element distortion D _i at l=1, 2, . . . , K and sends it to the minimum distortion normalized output vector detector 13 . The minimum distortion normalized output vector detector 13 is i
= 1, 2, ..., Detect the minimum distortion D _i among N, and calculate the index i, block average value m _A , and block standard deviation σ _A corresponding to the minimum distortion normalized output vector at that time. Load it into index latch 17. Here, the minimum distortion D is calculated by the following calculation: D=MinDi ⁱ =Min ⁱ [Max ^l Dil].

The index 14, block average value 15, and block standard deviation 16 of the normalized output vector resulting in the minimum distortion are collectively encoded by an encoding output circuit 18 and outputted as an encoded output signal 19.

In the decoding section shown in FIG. 4, the encoded output signal 1
After decoding 9 through the decoding input circuit 20, the index latch 17 receives the output vector index 14, the block mean value 15, and the block standard deviation 16. The decoded output vector index 14 is given as an address signal to the normalized output vector code table memory 7, and the corresponding normalized output vector _y'i is read out. The normalized output vector y′ _i is latched in the normalized output vector register 8, then multiplied by the block standard deviation 16 for each element in the parallel multiplier 9, and then multiplied by the block standard deviation 16 for each element in the parallel adder 21. A block average value of 17 is added.

The output signal of this parallel adder 21 is processed by a limiter for each element in a decoding output circuit 22, where overflow and underflow are removed from the input vector 1.
The result is an output vector 23 with minimum distortion.

That is, the minimum distortion output vector y _i is reproduced by the calculation y _i =σ _A ·y' _i +m _A.

As described above, the adaptive vector quantizer according to the present invention separates and normalizes the components that are difficult to model, which correspond to the amplitudes of the DC and AC components of the input signal. Since the sequence is vector quantized, efficient vector quantization that matches all signals can be realized.

The adaptive vector quantization processing according to the present invention can also be performed sequentially using a microprocessor or the like.

Note that although the block average value and block standard deviation are used as the DC component and amplitude gain component to be separated from the input signal sequence in the above, the speed of the circuit can be increased by using the intra-block medium (median value) and the intra-block deviation medium, respectively. Good too. Furthermore, it goes without saying that instead of the average value within a block, the average value spanning several blocks may be separated as a DC component.

Furthermore, it is also possible to separate only the MSB of the DC component and vector quantize the remaining components without requiring the same number of significant digits in the above numerical calculations.

As described above, in the adaptive vector quantizer according to the present invention, only the component corresponding to the basic structure of the input signal is vector quantized, and the other components are adapted to follow the input signal adaptively. It is possible to realize efficient vector quantization that is compatible with the following.

[Brief explanation of drawings]

FIG. 1 is an explanatory diagram of the relationship between input and output vectors in conventional vector quantization, FIG. 2 is an explanatory diagram of the adaptively controlled relationship between input and output vectors of the adaptive vector quantizer in the present invention, and FIG. FIG. 4 is a block diagram showing an embodiment of the encoding section of the adaptive vector quantizer according to the present invention. FIG. 4 is a block diagram showing an embodiment of the decoding section of the adaptive vector quantizer according to the present invention. In the figure, 1 is an input vector, 2 is an input vector register, 3 is an average value calculator, 4 is a standard deviation calculator, 5 and 10 are parallel subtracters, 6 is a code table address counter, and 7 is a normalized output vector code. Table memory, 8 normalized output vector register, 9 parallel multiplier, 11 parallel absolute value calculator, 12 maximum element distortion detector, 13 minimum distortion normalized output vector detector, 14 output vector index , 15 is the block average value, 16 is the block standard deviation, 17 is the index latch, 18
is an encoded output circuit, 19 is an encoded output signal, and 20
is a decoding input circuit, 21 is a parallel adder, 22 is a decoding output circuit, and 23 is an output vector. In addition, in the figures, the same reference numerals indicate the same or corresponding parts.

Claims (1)

[Claims] 1 For a normalized input vector obtained by dividing the input signal sequence into blocks of K (K is plural) samples, separating the DC component from the input vector, and normalizing the amplitude, the probability density in the K-dimensional signal space of the normalized input vector is A normalized output vector code table memory that stores a plurality of sets of normalized output vectors determined to have minimum distortion based on the distribution, and sequential reading from the normalized input vector and the normalized output vector code table memory. a minimum distortion output vector detector that detects a minimum distortion normalized output vector that minimizes distortion with respect to the normalized input vector by comparing the normalized output vector with the normalized output vector, and an encoding unit consisting of an encoding output circuit that encodes an index corresponding to the distortion normalized output vector, and a DC component obtained by decoding the encoded output signal from the encoding output circuit, a normalization constant, and a minimum An adaptive vector quantizer comprising: a decoding unit that reproduces an output vector that causes minimum distortion in the input vector based on the distortion-normalized output vector.