JPH0423990B2 - - Google Patents

Description

[Detailed Description of the Invention] [Technical Field of the Invention] The present invention blocks a plurality of input signal sequences in, for example, an imaging device to form an input signal vector, and quantizes this input signal vector in a multidimensional signal space. This invention relates to a vector quantization device. [Prior Art] First, tree search vector quantization will be explained. Considering a binary tree with two branches branching from each branch point R as shown in Figure 4, the root of the tree is a K-dimensional signal space R ^K , and each branch point divides the space R ^K in stages. It corresponds to each space. A representative point (for example, the center of gravity) is determined in each space, and the representative point becomes a k-dimensional output vector. The output vector of each stage is determined based on the distribution of the input vectors so that the sum of distortions between the input and output vectors is minimized. When an input vector is given, compare the distortion with the output vector corresponding to the two branch points that branch from the first stage to the final stage, and select the branch with the smaller distortion, which corresponds to the final branch point. The output vector is selected. If the final stage is the n-th stage, there are 2 ⁿ terminal branch points. The above is Tree Search Vector Quantization (TSVQ)
This is an explanation. In FIG. 4, an example where n=3 is shown. FIG. 5 shows an example of the configuration of a conventional tree search vector quantizer when n=3. In Fig. 5, 1 is the input signal vector that is blocked every K pieces, and 2 is the input signal vector that is input.
The first stage of the TSVQ encoder, 3 is the first stage output vector index output from the first stage of the TSVQ encoder, and 4 is the second stage of the conventional TSVQ encoder into which the first stage output vector index is input. Step 5 is
2nd stage output vector index output from the 2nd stage of the TSVQ encoder, 6 is the 3rd stage of the TSVQ encoder into which the 2nd stage output vector index is input, 7 is from the 3rd stage of the TSVQ encoder This is the third stage output vector index to be output. FIG. 6 also shows the second stage 4 of the conventional TSVQ encoder.
This shows an example of the configuration in more detail. 6th
In the figure, 8 is an input vector register into which input signal vector 1 is input, and 9 is into which first stage output vector index 3 is input. 2nd stage output vector code table; 10 is a distortion calculation circuit that calculates the distortion between the input signal vector output from the input vector register and the output vector output from the 2nd stage output vector code table 9; 11 is a distortion calculation circuit; 10 is a distortion comparison circuit that calculates the minimum value of the distortion calculated; 12 is a distortion comparison result signal output from the distortion comparison circuit 11; 13 is a distortion comparison result signal 12 and the first stage output vector index signal 3; This is an index register that outputs a second stage output vector index 5 based on the index. Next, the operation will be explained. Tree search vector quantization is a repetition of performing distortion comparisons between two paired output vectors and an input signal vector in each stage, and determining the paired output vectors to be compared in the next stage. The three-stage distortion calculation of the tree shown in FIG. 4 corresponds to the first stage 2 of the TSVQ encoder, the second stage 4 of the TSVQ encoder, and the third stage 6 of the TSVQ encoder in FIG. In each stage, a distortion operation is performed between the pair of output vectors specified by the distortion comparison results up to the previous stage and the input vector, the one with the smaller distortion is determined, and that information is added to the comparison results up to the previous stage. Send to the next stage. Since there is only one pair of output vectors in the first stage, the comparison results from the previous stages are not necessary or exist. If the output vector index 3 output as a result of the distortion comparison in the first stage is _i1 , then in the second stage a distortion operation is performed between the pair of output vectors determined by _i1 and the input vector, and the comparison is performed. Add the result to i ₁ to form i ₂ 5. In the third stage, by i ₂ and the input signal vector,
Outputs i ₃ 7. In Figure 4, if the left branch is selected, 0 is assigned, and the right branch is assigned 1, then the indices i ₁ , i ₂ , and i ₃ are 1-digit, 2-digit, and 3-digit binary strings, respectively. The index _i3 of this binary number string becomes the output vector index of the final stage. The above is an explanation of the operation of the tree search vector quantizer. Here, the output vector code table in each stage is a pair of output vectors specified from the results of the previous stage, as shown in FIG .
₀ , y ₁ , in the second stage y ₀₀ , y ₀₁ , y ₁₀ , y ₁₁ , in the third stage
In the rows, y ₀₀₀ , y ₀₀₁ , y ₀₁₀ , y ₀₁₁ , y ₁₀₀ , y ₁₀₁ ,
y ₁₁₀ and y ₁₁₁ must be stored as respective output vectors. [Problems to be Solved by the Invention] Since the conventional tree search vector quantizer is configured as described above, the contents of the output vector code table differ depending on the encoder corresponding to each stage. Even if you try to share the memory contents that make up the output vector code table of the encoder corresponding to each stage, the addresses accessed in the memory that makes up the output vector code table will be duplicated in the encoder corresponding to each stage. Therefore, it became impossible, and there were drawbacks such as the need for a wide variety of memory contents (at least as many as the number of stages). [Means for Solving the Problems] Therefore, the present invention provides an encoder constituting this kind of vector quantization device for each of the plurality of branch points, and that The output vector index, which has a different value for each branch point, and the output signal vector corresponding to the tree-like branch point in the above vector space are stored in advance as a set, and the output vector index corresponds to the output vector index. a vector code table that outputs output signal vectors as a set; a comparison means that compares each of the output signal vectors constituting the set of output signal vectors from the vector code table with an input signal vector; Vector index output means for selecting the output signal vector having a smaller comparison difference with the input signal vector from among the output signal vectors included in the set, and outputting respective output vector indices corresponding to the plurality of branch points. It has been established that [Operation] The encoder of the vector quantization device of the present invention stores in advance output signal vectors as sets corresponding to tree-like branch points in the vector space, and The output signal vectors are selected as a set based on the output vector index which is given to each of the plurality of branch points and has a different value to each of the plurality of branch points, and each of the output signal vectors and the input signal vector are selected as a set. compare. Based on this comparison result, the output signal vector with the smaller comparison difference with the input signal vector is selected, and based on this selected output signal vector, each output vector index corresponding to the plurality of branch points is determined. This outputs the following. [Embodiment of the Invention] An embodiment of the invention will be described. The vector quantization device of the present invention has encoders connected in multiple stages that determine an output vector based on an input signal vector and output an output vector index corresponding to the determined output vector. The input signal vector is previously blocked in a multi-dimensional signal space, and the output vector has a relationship in the vector space such that a plurality of branches from a plurality of branch points correspond to connection stages of the encoder. The output signal vector is configured to form a tree-like structure that branches into (n stages), and outputs an output vector index based on the determined output signal vector. The output vector index is assigned to each of the plurality of branch points, and has a different value for each of the plurality of branch points. Hereinafter, as an embodiment of the present invention, the case where the input vector index input to the first-stage encoder in the third-stage search is "001" (BIN) will be explained based on FIGS. 1 to 3. explain. FIG. 1 is a block diagram of a tree search vector quantization encoder which is an embodiment of the present invention when the number of search stages is three. The same parts as in FIG. 5 are indicated using the same or corresponding symbols. are doing. In Figure 1, 1
4 is an input vector index input to the first stage encoder, and 15 is a TSVQ according to the present invention to which the input vector index 14 and input signal vector are input to the first stage encoder.
In the first stage of the encoder, 16 is the first stage pseudo output vector index output from the first stage 15 of the TSVQ encoder, and 17 is input with the input signal vector 1 and the first stage pseudo output vector index 16.
In the second stage of the TSVQ encoder, 18 is the second stage pseudo output vector index output from the second stage 17 of the TSVQ encoder, and 19 is the second stage pseudo output vector index 18 to which the input signal vector 1 and the second stage pseudo output vector index 18 are input. This is the third stage of the TSVQ encoder. Figure 2 is based on this invention in Figure 1.
FIG. 2 is a block diagram showing the second stage of the TSVQ encoder in more detail; In FIG. 2, the output vector code table 17 of the second stage 17 of the TSVQ encoder
A is the second stage output vector code table #0,
It has a second stage output vector code table #1. The input signal vector 1 is input to the distortion calculation circuit 10 via the input signal vector register 8 which is an input means, and this distortion calculation circuit 10 inputs the second stage output vector code table #0 and the second stage output vector code. The distortion between the output signal vectors a and b stored in table #1 and the input signal vector 1 is calculated, and the calculation result is output to the second stage distortion comparison circuit 11. The second stage distortion comparison circuit 11 selects the output signal vector a and b that has a smaller comparison difference with the input signal vector based on the calculation result, and outputs a distortion comparison result signal 12 of 0 or 1. This distortion comparison result signal 12 and the first stage pseudo output vector index 16 input to the output vector code table 17 are input to a pseudo index shift register 22 which is a vector index output means. . This pseudo index shift register 22 outputs a second stage pseudo output vector index 18. Here, TSVQ encoder first stage 15, TSVQ encoder second stage 17, TSVQ encoder third stage 19
constitutes a vector quantization device 20 as a whole. Next, the operation of the embodiment of the present invention described above is explained by converting the initial pseudo index to binary "001" (BIN: 2).
The explanation will be based on the case where it is a base number). First, output vector code table #0 common to each search stage,
The address map when the #1 search is in three stages is shown in the table of FIG. Now, input signal vector 1 input to the first stage of TSVQ and input vector index 14 “001” input to the first stage encoder.
(BIN) output signal vector y ₀ output from output vector code table #0, #1,
The distortion with respect to y ₁ is calculated by the distortion calculation circuit 10.
The distortion comparator circuit 11 selects one of the output vectors resulting in the minimum distortion based on the calculation result of the distortion calculation circuit 10,
Based on this selected result, the distortion comparison result signal 12
Output. Pseudo index shift register 2
In step 2, the distortion comparison result signal 12 is added to the least significant LSB of the first stage pseudo output vector index 16, the most significant MSB is discarded, and the second stage pseudo output vector index is sent to the next stage. When such an operation is performed in the second and third stages, the lowest digit LSB of the initial pseudo output vector index is stored in the third stage pseudo index shift register.
All “1”s are truncated and the third value to be found is
A stage output vector index 7 can be obtained. To illustrate this with a concrete example, in the first stage of the TSVQ encoder, for an input vector, the output signal vector y is output from the output vector code table #0 using the initial pseudo output vector index “001” (BIN) .
₀ , output signal vector y ₁ is output from output vector code table #1, and output signal vector y ₀ of output vector code table #0 is selected, the distortion comparison result signal 12 becomes “0” (BIN) and a pseudo In the index shift register 21, the lowest digit LBS of the input vector index 14 "001" (BIN) input to the first stage encoder is input.
Add “0” (BIN) and add the most significant MSB
``0'' (BIN) is truncated. This can be expressed as a formula as follows. 001 (BIN) → 0010 (BIN) → 010 (BIN) In the second stage of the TSVQ encoder, the first stage pseudo output vector index 16 “010” (BIN) is the output vector y ₀₀ from the output vector code table #0. , output signal vector y ₀₁ is output from output vector code table #1. If vector y ₀₁ of output vector code table #1 is selected, second stage pseudo output vector index 1
8 becomes 010 (BIN) → 0101 (BIN) → 101 (BIN). Furthermore, in the third stage of the TSVQ encoder, the second
Stage pseudo output vector index 18 “101”
(BIN) outputs the output vectors y ₀₁₀ and y ₀₁₁ from the output vector code tables #0 and #1, respectively, and when the output signal vector y ₀₁₁ of the output vector code table #1 is selected, 101 (BIN)
→ 1011 (BIN) → 011 (BIN), the input vector index input to the first stage encoder disappears, and the index “011” (BIN) of the output signal vector y ₀₁₁ to be obtained is changed to the third stage encoder. It is obtained as an output vector index (encoded output) 7. This search process corresponds to the route in FIG. [Effects of the Invention] Based on the above configuration, the present invention can share the memory contents constituting the output vector code table of the encoder corresponding to each stage, and can reduce the memory contents.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing an embodiment of a tree search vector quantization encoder according to the present invention, and FIG. 2 is a block diagram showing an embodiment of the second stage of the tree search vector quantization encoder according to the present invention. , FIG. 3 is a table showing address maps of output vector code tables #0 and #1 according to the present invention, FIG. 4 is an explanatory diagram of the search in tree search vector quantization, and FIG. 5 is a diagram showing the conventional tree search vector quantization. FIG. 6 is a block diagram showing an embodiment of a conventional tree search vector quantization encoder at the second stage. In the figure, 1... input signal sequence (input signal vector), 2... first stage of conventional TSVQ encoder,
3...1st stage output vector index, 4...
Conventional TSVQ encoder second stage, 5...Second stage output vector index, 6...Conventional TSVQ
Encoder third stage, 7...Third stage output vector index, 8...Input vector register, 9...
Conventional output vector code table, 10...distortion calculation circuit, 11...distortion comparison circuit, 12...distortion comparison result signal, 13...index register, 14
... Input vector index input to the first stage encoder, 15 ... TSVQ according to the present invention
Encoder first stage, 16...First stage pseudo output vector index, 17... According to this invention
TSVQ encoder second stage, 18... Second stage pseudo output vector index, 19... TSVQ encoder third stage according to the present invention, #0, #1... Second stage output vector code according to the present invention table,
20...Vector quantizer, 22...Pseudo index shift register. In addition, in each figure,
The same reference numerals indicate the same or equivalent parts.

Claims (1)

[Scope of Claims] 1. An encoder that receives an input signal vector, determines an output vector based on the input signal vector, and outputs an output vector index corresponding to the determined output vector, which is connected in multiple stages, The input signal vector is previously blocked in a multi-dimensional signal space, and the output vector has a relationship in the vector space such that a plurality of branches from a plurality of branch points correspond to connection stages of the encoder. (n
In the vector quantization device, the encoder receives an input signal vector and outputs an output vector index based on the determined output signal vector. an input means; an output vector index assigned to each of the plurality of branch points and set to a different value for each of the plurality of branch points; and a tree-like branch in the vector space in advance. a vector code table that stores output signal vectors as sets corresponding to points, and outputs output signal vectors corresponding to the output vector index as a set based on the input output vector index; Comparison means for inputting a set of output signal vectors from the code table and an input signal vector from the input means, and comparing each of the output signal vectors constituting the input set of output signal vectors with the input signal vector. Based on the comparison result of this comparison means, the output signal vector that has a smaller comparison difference with the input signal vector is selected from among the output signal vectors included in the set of output signal vectors, and this selected output signal vector is selected. A vector quantization device comprising vector index output means for outputting respective output vector indices corresponding to the plurality of branch points based on the signal vector. 2 In a multi-disconnected encoder, the input vector index input to the first stage encoder is set to “1” (BIN) only at the lowest order, and all the required number of upper bits are “0” (BIN). A vector quantization device according to claim 1, characterized in that: