JPH02237270A - encoding device - Google Patents

Abstract

PURPOSE:To solve the problems of a conventional computing element system or LUT system such as calculating speed, coding efficiency and circuit scale by constituting vector quantization processing in multi-stage. CONSTITUTION:Scalar quantizers 12a-12d, LUT memories 13a-13d storing codes of vectors apart by the shortest distance from inputted vectors, and LUT memories 13e-13g storing the codes of vectors apart by the shortest distance from vectors represented by inputted vector codes are provided on the subject device. An inputted n-dimensional vector is split into plural vector spaces in p-dimension (p>n) and each vector is subjected to vector quantization by using a code book having the same space. Then the result of each quantization is combined into q-dimensional (q<=n) vector and the result is subjected to vector quantization by using a code book having the constitution of vector space represented by each vector. Thus, problems such as calculating speed, coding efficiency and cost are solved.

Description

DETAILED DESCRIPTION OF THE INVENTION [Industrial Field of Application] The present invention relates to an encoding device for encoding signals such as image information using a vector quantization technique.

[Prior Art] Conventionally, an encoder using vector quantization calculates the distance between a human vector and a reproduced vector in a codebook stored in a memory 1 using a calculator 2, as shown in FIG. 13A. Based on the results of these calculations, the comparator 3 selects the reproduction vector with the shortest distance and outputs its code. In addition, as shown in FIG. 13B, the vectors at the shortest distance to the input vector are calculated in advance and stored in the memory 4, so that when a human vector is given, the code of the reproduced vector is calculated. It was constructed using a lookup table (hereinafter abbreviated as LUT) method.

[Problems to be Solved by the Invention] However, in the former configuration using arithmetic units (Figure 13A), the higher the dimensionality of the human vector, the larger the scale of the arithmetic circuits and comparators, resulting in lower cost and speed. There is a problem in terms of

Further, although the LUT method (FIG. 13B) solves the problems in terms of speed and cost, it has the following drawbacks when the dimension of the input vector increases.

(i): When performing an exhaustive search on the LUT of a multidimensional vector quantizer, a huge amount of calculation time and hardware are required, which poses problems in terms of coding efficiency and cost.

(ii): The capacity of the memory is limited by the size of the element, making it difficult to configure it with a ROM or the like.

(iii): If only a scalar quantizer is set before the LUT, the correlation between vector elements cannot be utilized, resulting in a decrease in efficiency and image quality.

That is, even though the LUT method is said to be superior to the arithmetic unit method in terms of speed, there are still problems such as a decrease in calculation speed and deterioration of encoding efficiency and image quality depending on the input signal.

[Means for Solving the Problems] Therefore, the present invention solves the problems of the conventional arithmetic unit system and LUT system, such as the calculation speed, coding efficiency, and circuit size.
This problem was solved by configuring vector quantization in multiple stages.

The configuration of the encoding method of the present invention for achieving this task is to use a codebook created from training data in advance to perform vector quantization of a signal. A first step of dividing into a plurality of vector spaces, each of which has p dimensions (p<n), and a second step of vector quantizing these divided individual vectors using a codebook having the same space. and a third step of composing the individual quantization results vector quantized in the above steps into a q-dimensional (q≦n) vector, and composing this q-dimensional vector with the configuration of the vector space they represent. It is characterized by comprising a fourth step of vector quantization using a codebook, and a fifth step of repeating the third and fourth steps until q=n.

Further, in the configuration of the encoding device of the present invention, in the encoding device that performs vector quantization of a signal using a codebook created in advance from 1. training data, each n-dimensional vector representing an input signal vector is p dimension (p
<n); a first vector quantization means for vector quantizing these divided individual vectors using a codebook having the same space; The individual quantization results vector-quantized by the quantization means are q-dimensional (q≦n)
and a second vector quantization means that vector quantizes this q-dimensional vector using a codebook having a configuration of a vector space that these q-dimensional vectors represent. until the above 1st
The vector quantization means, the synthesis means, and the second vector quantization means are linearly arranged in multiple stages.

Further, the configuration related to the codebook creation method of the present invention is as follows:
Each of the p-dimensional input signal vector and the q-dimensional input signal vector is vector quantized using the first and second codebooks, and the vector obtained by combining these two quantization results is The method for creating the third codebook, which involves further quantization using the codebook, wherein the quantization using the first and second codebooks is used in the third codebook. The present invention is characterized in that it includes a first step of extracting a reproduced vector without a code, and a second step of deleting the extracted reproduced vector from a third codebook.

[Embodiments] Three embodiments in which the tree invention is applied to image signal encoding will be described below with reference to the accompanying drawings, including a first embodiment to a third embodiment.

<First Example> FIG. 1 is a configuration diagram showing an encoding device according to a first example. In the figure, reference numeral 10 denotes an input terminal for inputting an image signal of the present device in the form of a vector.

This vector as image data is obtained by applying Hadamard transformation to a 4×4 image block.

Further, 11 is a distributor that subdivides the input vector into subspaces. Reference numerals 12a to 12d are scalar quantizers that scalar quantize a manually input sequence for each sequence, and are abbreviated as SQ in the figure. 13a to 13g are vector quantizers, of which 13a to 13d are LUT memories that store the code of the vector closest to the input vector, and 13e to 13g are the input vector codes. It consists of an LUT memory that stores the code of the vector that is the shortest distance from the vector represented by . That is, four vector quantizers 13a to 13d are arranged in parallel, and vector quantizers 13e. 13f two quantizers (13e, 1
3f are in a parallel relationship with each other) and 13g quantizers are arranged. Further, 14 is an output terminal of a code as an output result of vector quantization.

Image encoding in this example involves cutting out 4x4 blocks, applying preprocessing to each block (in this example, Hadamard transform as an example), and vector quantizing the results. Determine the mapping vector for vector quantization during encoding. The concept of vector quantization is common to all embodiments described below. Hex-le quantization is a type of encoding that is superior in terms of wood quality, and can significantly improve quantization distortion compared to scalar quantization.

The concept of vector quantization will be briefly described according to FIG. The input signals are divided into K blocks, and each block is represented by a K-dimensional vector X for convenience of explanation in FIG. Vector quantization can be seen as mapping from this X to a set of N vectors prepared in advance. These N vectors are called output vectors, and this set is called a coat book (or output vector set).
It is called. FIG. 2 shows the basic configuration of vector quantization.

Now, we will block K samples of the input signal system and create a human vector. Let X = (X+ ,X2 .X3."'. subspace P
Assume that it is divided into I. It is assumed that the vectors forming P1 are known. Using this subspace as a constituent vector, a representative vector R of the subspace R+ is selected. Therefore, if XεR, then its index (index number) i
can represent the input vector X.

That is, by transmitting or storing this i, compression/encoding becomes possible. Then, on the decoding side, the K-dimensional vector stored at the same i address in the codebook on the decoding side, R + "" (r+, r2, r3."'+ r
Output J as a reproduction vector of input vector X. Such a mapping F F :Rl = f (X) such as X→R1 is called vector quantization. This mapping is done so that the distortion caused by mapping X to RI is minimized. That is, the codebook is generated according to a certain predetermined training sequence so as to minimize the average distortion. Vector quantization is a method of quantizing in units of blocks, and it is known that increasing the number of dimensions, that is, the size of the block, approaches the theoretical data compression limit. Furthermore, since the quantization error is randomized, when an image signal is targeted, a high reproduction quality can be obtained in relation to the S/N ratio.

Next, the Hadamard transform used in this embodiment will be explained. This Hadamard transform is a form of orthogonal transform, but this orthogonal transform requires vector quantization preprocessing and L,
This is because it is particularly suitable.

This Hadamard transform is common to the first to third embodiments. As an example, it is assumed that the image to be encoded is a monochrome multivalued image, and each pixel has an information amount of 8 bits.

Hadamard transform is, for example, 4× as shown in Figure 3A.
This is applied to a block of 4 pixels.

xl,1 (i.1..4, j-1..4) represents a pixel of the image.

When this XIJ is expressed using a matrix X, X − [X11, X12, X13, X14, X21.
X22, X23, X24, X31, X32, . X33.
X34. X41. L2. X43. X44]T-(1
). However, T in the above formula represents a transposed matrix. The result of applying Hadamard transformation to this X is the y-th (J-1
・・４． j- 1...4), the matrix Y represented by yIJ is Y = [yI+1yI2・y13・yl41y2
1・V22 +y231y24Y311y32・V33
1y34・y41. y42・y43, Y<41"...
・(2) It is. Then, the conversion from matrix X to matrix Y is as follows (
3) It is expressed by the formula.

Here, I{+a is a 16-line Hadamard matrix and is expressed by the following equation.

[Margin below] The coefficients obtained by applying Hadamard transform to a 4×4 pixel block are called a sequence. That is, for a 4×4 pixel block, 16 sequences are obtained. Among these, y++ is a DC component, and the remaining 15 AC components are to be quantized.

Now, when quantizing 15 sequences, assuming that the amount of information per sequence is 10 bits, in the conventional LUT method, a memory whose address is the amount of information of 10 (bits) Xi 5 = 1 50 (bits) is As mentioned above, it was necessary to use it as an LUT, and this was not suitable for increasing the scale of the circuit. Therefore, in the first embodiment, the input vector space is divided into subspaces. This is due to the following reason. The sequence indicates the power of the frequency, and whether orthogonal transform or Hadamard transform is used as preprocessing, a 4×4 sequence generally shows a tendency for the upper left to be a low frequency and the lower right to be a high frequency. Further, since the variances tend to be equal in areas where the frequencies of each sequence are close, it is suitable to perform vector quantization by forming a new vector and quantizing in such areas. In other words, if we construct a new vector by dividing it into a low frequency part and a high frequency part, the dynamic range of this new vector is close, so even if we vector quantize this vector, there will be little quantization distortion. Become.

FIG. 3A is a diagram showing the 4×4 vector space division applied to the distributor 11 of this first embodiment. The sequence 20a is a DC component, and as described above, is excluded from vector quantization. The other 15 alternating current component sequences 20b to 20p are inputted from the terminal 10 of the present encoding device. Distributor 11 serves to distribute sequences 20b-20p to the following scalar quantizers as shown in FIG. 3A. That is, the distributor 11 divides the human vector space into subspaces. Specifically, the sequences 20b, 20e, 20f are sent to the scalar quantizer 12a, and the sequences 20c, 20g, 20i, 20j are sent to the scalar quantizer 12a. to vessel 12b, sequence 2Qd 20h. 20
m, 20n to scalar quantizer 12c, sequence 2C
lk, 201, 20o, 2Qp by scalar quantizer 12d
distribute to. Each scalar quantizer quantizes each sequence to the number of bits that can be configured by the next vector quantizers 13a to +36 with the minimum number of ROMs.

It should be noted that these scalar quantizers 12a to 12d can be configured with a number of ROMs equal to the number of sequences, or can be configured with a small number of ROMs using latches.

From the scalar quantizer 12a, the sequences 20b and 20e are
, 20f is output, and the scalar quantizer 12b outputs a three-dimensional vector after scalar quantization by the sequences 20c, 20f.
20g, 20i, and 20j are output, and the scalar quantizer 12c outputs a four-dimensional vector after scalar quantization by the sequences 20d. A four-dimensional vector after scalar quantization using 20h, 20m, and 20n is output, and the scalar quantizer 1
From 2d, the sequence is 20k, 201, 20o, 20p.
A four-dimensional vector after scalar quantization is output.

Each of the vector quantizers 13a to 13d quantizes the three-dimensional or four-dimensional vector given from these scalar quantizers, obtains the code of the reproduced vector, and then outputs the code to the vector quantizer 13e, Output to 13f. That is, the vector quantizer 13e is the vector quantizer 1 at the previous stage.
The codes of reproduction vectors 3a and 13b are input, and the vector quantizer 13f is connected to the previous stage vector quantizer 13c,
Input the reproduction vector code of 13d.

A method for determining the contents of the LUTs constituting the vector quantizers 13e and 13f will be described. First, the code of the input reproduced vector is decoded once into a vector, and then the entire vector space is divided into two as shown in FIG. 3B to create a new vector. Vector quantization is applied to this to obtain a reproduction vector code, which becomes the contents of the LUTs 13e and 13f.

Thus, the vector quantizer 13e converts the original sequence 2
0b, 20c, 20d, 20e, 20f, 20g, 20
Vector quantization is performed for i, 20j. Further, the vector quantizer 13f has sequences 20d, 20h. 20
Vector quantization is performed for k, 201, 20i, and 20j.

The vector quantizer 13g is the vector quantizer 13 in the previous stage.
Input the reproduction vector code of e and 13f. That is, similarly to the vector quantizers 13e and 13f in the previous stage, the input reproduced vector code is decoded and the vector space is
A reproduced vector code is obtained as a result of returning to the dimension and applying vector quantization.

By adopting such a configuration, a reproduced vector code is obtained by inputting a 15-dimensional human input through a multi-stage vector quantizer.

Next, we will describe the creation of a codebook for each vector quantization. The codebook is generally created using the LBG method. This is a well-known method for calculating a playback vector from training data serving as a population. Therefore, this embodiment uses this LBG method. This will be explained using the aforementioned 4×4 vector space as an example.

One way to create training data is to collect vectors obtained by actually applying Hadamard transform to images. In this way, training data consisting of 16-dimensional vectors is created. From there, the sequence required for each vector quantizer is extracted using Hadamard transform, and a training table consisting of vectors of the required dimensions is created. Then, the LBG method is applied to obtain the necessary reproduction vector code from these. The reason for doing this is that by directly designing each vector quantizer from the 1-learning data, a codebook without distortion caused by the previous stage quantization can be obtained.

According to the above codebook creation method, a codebook that is optimal in all stages in terms of no distortion can be obtained. However, due to the quantization in the first stage, the reconstruction vector in the second stage may not be used, resulting in a problem that it is not efficient.

FIGS. 4 and 5 are diagrams illustrating the generation of unused reproduction vectors. FIG. 4 is a diagram for explaining the entire generation of unused reproduction vectors for 2×2 blocks, and FIGS. 5A to 5D explain the individual processes in FIG. 4. The size of the vector is 2X2=4, which means 4X4
This is because the explanation is simpler than in the case of =16, and there is no difference in terms of wood quality between the two. Therefore, the 2 x 2 word direction made in FIGS. 4 and 5 is directly applied to the 4 x 4 word direction. Now, the processing shown in FIG. 4 is as follows. 4-dimensional human power Hek1・ru, Y4°{'! + + y2+ 'I3+ "Is)", and this vector Y4 is divided into country; 2ji::be{ as shown in FIG. Further, returning to FIG. 4, vector quantization is performed on each divided vector Y I + Y 2, and the results are combined to obtain a vector Y.

Vector quantize again. This is the process shown in FIG. Here, each y1 to y4 is 2-bit data, 0, 1
, 2.3.

Now, the reproduction vector X of the codebook CI for vector quantizing Y+={y+, y2} into 2-bit information
1. ~Xl4 is determined as follows, as also shown in FIG. 5A.

C, E {x++} H=i ~4) Also, Y2
= (Y3.'I4'j is vector quantized, and the reproduced vectors X2, to X24 of codebook C2 for vector quantization into 2-bit information are as follows, as shown in FIG. 5B. stipulated in

C2 ε {X21} (i=1 to 4) Furthermore, the reproduction vector obtained as a result of vector quantization of Yl and Y2 is as follows, and the vector that combines these is Yo ``''{y+'+'l2'' + y3' + y
4'). The reproduction vector of the codebook co that vector quantizes this is X. 1 to XO8 are determined as follows.

Co E {xo+} (i=1~a)Xo6=
{3, 2, 1. 1 } In this way,
After defining vectors and codebooks, the generation of unused reproduction vectors will be explained.

For example, Y. Consider the case where a hectare with components such as = {2.1} is manually constructed. Codebook C1
By vector quantization of , Y1 becomes Y"l==Xl3=
Quantized to {3.1}. This Y1゛ is combined with Y2゜, resulting in a composite vector Y. Codebook C. is vector quantized by Here, {21} is quantized to (3.1) by vector quantization of C1, so vector Y. When quantizing, this Y. Codebook C. Only input vectors with {3.1} components of are quantized. In other words, the vector Yo has {2
,t} component does not appear, therefore, {2.1
} component of the reproduction vector X. 5. XOII is not used at all. Such unused vectors can be
Call the unused reproduction vector J. Storing vectors that are never used in this way in the codebook reduces efficiency. Therefore, the efficiency is improved by removing the unused reproduction vector XOS and adding a new reproduction vector in its place.

FIG. 6 is a flowchart showing the procedure for removing unused reproduction vectors and replacing them with new reproduction vectors. As an example, this flowchart shows 2×
2 input vectors into two vectors and each
,,C2, vector quantization is performed, the result is combined into a 2×2 vector, and again, coatbook C. Codebook C for vector quantization. This is the procedure for deleting unused vectors inside. First, step S2,
In S4, it is checked whether there is an unused reproduction vector in the codebook C2. This check is performed as follows. That is, vector quantization of C or C2 is performed on human vectors of any pattern, and the resulting reproduced vector is C. Perform hexle quantization.

And C, which was never used as a reproduction vector for all the above manual patterns. The contents inside are picked out as unused reproduction vectors xN.

In addition, the pattern of the human power vector is ``'' in the example of Figure 4.
It is an arbitrary pattern from 0000°' to "1 1 1 1".

In step S6, unused vectors XN are removed from codebook C2. At the same time, step S8
Now, vector quantization is performed on all of the training data T using C, , C2 to obtain new training data T°. Here, the operation of dividing the 2×2 vector T1 into two vectors and performing vector quantization of C,,C2 on each of them to obtain a new vector T° is expressed as T + '-V QCIC2 (T +). Here, {+:・doujiji;jiH. At this time, the dimension of the training data is codebook C. is the dimension of the vector space represented by . Next, in step 510, the codebook C is selected from among the vectors T,° of the new training data T°. The vector X that is the farthest from the playback vector xI is determined. That is, MAX (djs {X I, T J
')). Then, in step S12, the codebook C is stored with this distant vector xF as a new reproduction vector. Add to. That is, it is set as co4-co+xF. In this case, XF is C, which is a LUT. , said x
N is stored in the deleted part. This is also done because unused vectors occur in areas with high density, so by adding new reproduction vectors to areas with low density, Codebook C as a table is created. This achieves both uniform density and efficiency.

Codebook C for the above operations. Repeat until there are no unused vectors within.

<Second Embodiment> FIG. 7 is a configuration diagram showing another embodiment of the present invention. The second embodiment is similar in that vector quantization is performed in a multi-stage configuration. However, whereas the first embodiment deletes unused reproduction vectors and further extracts and adds new reproduction vectors from the training data, in the second embodiment, the input images are line drawings and halftone images. The difference is that when a mixture of vectors is included, unused reproduction vectors are deleted and reproduction vectors suitable for line drawing vector quantization are added.

In order to simplify the explanation, in this second embodiment as well, a 4×4 sequence obtained by Hadamard transformation is taken as an example, as in the first embodiment. In Figure 7, 110 is 15
This is an input terminal for manually inputting sequences. As in the first embodiment, the DC component is excluded from quantization. 111
is a distributor that subdivides the input vector, and 11
2a to 112d are scalar quantizers that scalar quantize the input sequence. 113a to 113g are quantizers for vector quantizing input vectors or vectors represented by vector coats, and LUs 113a to 113g are quantizers for vector quantizing input vectors or vectors represented by vector coats;
There is a memory of T. 114 is an output terminal. Terminal 11
Reference numeral 5 denotes a human input terminal for manually inputting a selection signal for selecting whether the sequence image input from the terminal 110 is a line drawing or a halftone image.

Fifteen sequences are input from the input terminal 110, and these sequences are distributed by the distributor 111 to the scalar quantizers that follow. The distribution method is the same as in the first embodiment. Vector quantizers 113a to 113f following the scalar quantizers 112a to 112d function in the same manner as in the first embodiment. Input terminal 115 inputs a select signal.

This select signal is transmitted to the final stage vector quantizer 113g.
The codebook inside is being switched. This time, for the sake of explanation, the human-generated image is a natural image such as a photograph (halftone image).
113g for single cases and cases of letters and fine line drawings.
Switch the codebook. Note that this codebook switching does not mean switching everything between the two codebooks, but rather one codebook for line drawings and one for natural drawings, which is effective for preserving edge information, although it is a small number that occurs in character images. Two small, special codebooks are prepared, and a select signal is used to switch which one to use.

The reason for doing this is as follows. When quantizing Hadamard transform sequences, high frequency sequences are generally roughly quantized. Furthermore, if the training data is a natural image, sharp edges will not be reproduced using the codebook obtained by this 1-learning sequence. That is, 4 as shown in FIG. 8A.
When diagonal line data with a large density difference of 5° is input, the edge portion is surrounded by the thick line in the figure, blocks 1218 to 1218.
121k, and the distribution shape within that block is the 8th B.
Either (a) or (b) shown in the figure. FIG. 9A shows an example of vector quantization after Hadamard transformation. Block (a) of FIG. 8B mentioned above
) or (b) becomes smooth and becomes a block shape (a”) or (b°) as shown in Fig. 9B. Therefore,
One black pixel in block (a) becomes extremely dull because there is a lot of white surrounding it, and becomes almost a flat white block like block (a°). Furthermore, in block (b), the two pixels near the black edges are very close to black because there is a lot of black surrounding them, and the remaining pixels in the lower right corner also have a black tinge, as shown in block (b°). For this reason, in FIG. 9A, the texture of the 4×4 blocks stands out on the diagonal edges, which has a negative effect on the image quality. This is because low-frequency edges are preserved even in natural images.

Therefore, the configuration of codebook A of the vector quantizer 113g is made as shown in FIG.

Codebook A has (n-α
) reproduction vectors, a codebook N for natural pictures consisting of α reproduction vectors, and a codebook C for character images consisting of α reproduction vectors. Here, it can be considered that α corresponds to the number of unused vectors as in the first embodiment.

That is, codebook B is a codebook from which unused vectors have been removed. The codebook N is composed of reproduction vectors created from training data as in the first embodiment. For example, blocks (a) and (b) as shown in FIG. 8B are registered in court book C as playback vectors.

FIG. 11 shows an example of actual Keiko conversion.

In the figure, the input hector XN is a vector of a natural image. Also, human power vector X. is the edge portion of the character image, which is a vector input by Hadamard transformation of a block such as block (a) in FIG. 8B. These human vectors are not manually input at the same time, but when both are input, they are divided by a distributor 111, passed through scalar quantizers 112a to 112d, and then quantized via vector quantizers 113a to 113f. Ru. The quantization result is designated as xp in FIG. Here, the vector quantization on the right side of FIG. 11 is performed by the vector quantizer 113g in FIG.
represents the vector quantization to be performed. This vector quantization is to calculate a reproduction vector xn calculated from the codebook NIJ by calculating the distance at+, and a reproduction vector X,' calculated from the codebook C by distance calculation.

Here, the selection signal manually input from the human input terminal 115 in FIG. 7 is input to the selector in FIG. If the input is the vector xN in Figure 11), select the code of the reproduction vector is the reproduction vector X.

Select the code for ゜. This helps maintain edge sharpness.

Thus, according to the second embodiment, when an image containing a mixture of halftone images such as natural images and line drawing images is input, encoding with good reproducibility can be performed without deteriorating the image quality of the original image. be able to. In addition, by sharing the parts of the codebook that can be shared between the halftone image and the line drawing image, it is possible to reduce the overall codebook capacity.

<Third Embodiment> In this third embodiment, the form of the codebook in the vector quantizer 113g of the second embodiment shown in FIG. 7 is changed to the form shown in FIG. 12. In FIG. 12, codebook C is a codebook corresponding to edges of character information, etc., as described above, that is, it contains reproduction vectors of a pattern as shown in FIG. 9B. This can also be obtained by generating a binary pattern on a computer. Such a reproduced vector for edges is added as codebook C to the part of the codebook B of the final stage quantizer from which unused vectors have been deleted.

The reproduction vector in the codebook C of this third embodiment is
This is not just a simple distance calculation, but a distance calculation that takes into account the phase information of ``10''゜' and the absolute value of each coefficient. That is, if the sign of each sequence of the quantization result vector xp in FIG. It is determined that the original block has a shape such as block (a) in FIG. 8B, and the call 1 of the reproduction vector xc° in FIG. 11 is output.

In this case, the selector shown in FIG. 11 is unnecessary and no selector signal exists.

<Effects of Examples> As explained in the three examples above, vector quantization is configured in multiple stages, and inefficient unused vectors are deleted along with the optimal reproduction vectors obtained by the LBG method etc. of each codebook. By configuring reproduction vectors obtained from training data (first embodiment) or artificial data (second embodiment), the dimension of the vector space and the number of occurrences of input vectors can be reduced. This has the effect of realizing vector quantization that can be realized with hardware. At the same time, when creating an LUT, by reducing the number of dimensions, the calculation time can be significantly reduced when the calculation is performed on a computer, etc., and even multidimensional vectors can have the same performance as a full search vector quantizer. Obtainable.

<Other Examples> The present invention can be modified in various ways without changing the gist thereof.

In the above description of the first to third embodiments, a 4×4 Hadamard transform sequence or a four-dimensional vector was used, but the present invention is not limited to this, and the n-dimensional (n≧3) vector is used. It is clear that it can be applied to everything.

Furthermore, although the image type selection signal is manually input only to the final stage vector quantizer, it may be modified so that it is input to other vector quantizers, scalar quantizers, and distributors.

Furthermore, the method of adding new reproduced vectors to the codebook after deleting unused vectors is not limited to this, it is also possible to add an arbitrary vector from the training data that is farthest from each reproduced vector, and the training data It is compatible with all methods that add vectors extracted from . Furthermore, the reproduction vectors to be added to the codebook can be generated by generating binary patterns on the computer, or can be ternary patterns without being limited to this, or if the number is particularly small, you can input the patterns manually. I don't mind.

[Effects of the Invention] As explained below, according to the tree invention, by configuring vector quantization in multiple stages, it is possible to reduce the dimensionality of the vector space.

That is, it is possible to provide a coding method and a coding device that can reduce the dimensions of a vector space, and to create an efficient codebook that can be applied to these methods.

Further, by deleting inefficient and unused vectors that appear as a result of the multi-stage configuration, it is possible to downsize the vector quantization configuration.

In addition, by adding the deleted portion to the male vector obtained from training data or artificial data, it is possible to prevent deterioration of the reproduced signal and to create a high-speed vector quantizer that can perform a full search for multidimensional vectors. It is possible to obtain the same performance as .

[Brief explanation of drawings]

FIG. 1 is an overall diagram of the encoding device of the first embodiment according to the present invention, FIG. 2 is a diagram explaining the concept of vector quantization used in the first to third embodiments, and FIG. 3A , 3B are diagrams explaining the concept of space division applied to the first to third embodiments, and FIG. Figure 5A~
FIG. 5D is a diagram explaining how unused reproduction vectors are generated, FIG. 6 is a flowchart showing a procedure for replacing unused vectors from training data, and FIG. 7 is a code according to a second embodiment of the present invention. Block diagram of the conversion device, Figures 8A and 8B. 9A and 9B are diagrams explaining how the edge portion deteriorates if the method of the second embodiment is not used. FIG. 10 is a structural diagram of the vector quantization codebook of the second embodiment. 12 is a diagram explaining the operation of the second embodiment using an actual example, FIG. 12 is a diagram showing the configuration of a codebook used in the third embodiment, and FIG. 13A. FIG. 13B is a diagram illustrating the configuration of a conventional technique. a to d...scalar quantizer, 13a to 13g, 113
a~113g...vector quantizer, 14.114.
...Output terminal, 115...Select signal input terminal, 2
0a to 20p...Sequence, 120...Pixel, 1
21a to 121k...blocks. Patent applicant: Canon Inc. In the figure, 1...Memory, 2...Distance calculator, 3...Comparator, 4...LUT table memory, 10.110...
Manual terminal, 11, 111-...Distributor, 12a to d,
112 inch Σ く圃美澱-510１〈Procedure Nefushojt and (Method) Indication Patent No. 1-56321 of the June 22, 1999 case of the Director General of the License Agency 2. Relationship with the Case of Person Who Amends the Method of Encoding Names of Inventions and Encoding Devices and the Method of Preparing Codebooks Used Therewith Patent Canon Co., Ltd. Applicant's Agent 2-5 Toranomon, Minato-ku, Tokyo 105 May 1999 Month 30th (Shipping)

Claims (6)

[Claims] (1) In a coding method that performs vector quantization of a signal using a codebook previously created from training data, an n-dimensional vector representing an input signal vector is The first step is to divide these divided individual vectors into vector spaces, the second step is to vector quantize these divided individual vectors using a codebook with the same space, and the individual quanta vector quantized by the above step. The third step is to combine the quantization results into a q-dimensional vector (q≦n), and the fourth step is to vector quantize this q-dimensional vector using a codebook that has the configuration of the vector space that these q-dimensional vectors represent.
and a fifth step of repeating the third and fourth steps until q=n. (2) In an encoding device that performs vector quantization of a signal using a codebook previously created from training data, a plurality of n-dimensional vectors representing an input signal vector are each generated with p dimensions (p<n). a first vector quantization means for vector quantizing these divided individual vectors using a codebook having the same space; a synthesis means for synthesizing individual quantization results into a q-dimensional vector (q≦n); 2
vector quantization means, and the first vector quantization means, the combining means, and the second vector quantization means are linearly arranged in multiple stages until at least q=n. An encoding device characterized by: (3) Vector quantize each of the p-dimensional input signal vector and the q-dimensional input signal vector using the first and second codebooks, and combine these two quantization results to obtain a vector. A method for creating the third codebook in an encoding system that further quantizes using a third codebook, wherein the third codebook is used in the third codebook depending on the quantization using the first and second codebooks. A method for creating a codebook, comprising: a first step of extracting a reproduction vector that will never be reproduced; and a second step of deleting the extracted reproduction vector from a third codebook. (4) A third step of extracting new reproduction vectors from the training data, and a fourth step of adding the extracted new reproduction vectors to the third codebook by the number deleted in the second step. 4. The method of creating a codebook according to claim 3, further comprising: (5) A third step of extracting new reproduction vectors that are not based on the training data, and a fourth step of adding the extracted new reproduction vectors to the third codebook by the number deleted in the second step. 4. The method for creating a codebook according to claim 3, further comprising the step of: (6) Creating a codebook according to claim 5, wherein the input signal is an image signal, and the new reproduction vector that is not based on the training data is a reproduction vector representing an engine part of the line drawing. Method.