JPH0327670A - Vector quantizer for image data - Google Patents

Abstract

PURPOSE:To attain high speed vector quantization while the processing quantity is reduced by outputting index information after representative vector information is outputted. CONSTITUTION:An input picture data inputted from a terminal 21 is subject to original high speed code book production and high speed vector quantization coding, the result is outputted from a terminal 29 as output coded information comprising of code book information and index information. When the code book information and the index information are inputted from a terminal 30 as input coded information, a coded information input circuit 31 writes code book information into a memory 33 and the index information is given to a vector quantization decoding circuit 32 sequentially and a corresponding representative vector is read from the memory 33 as an output vector and reproduced in a picture data reproduction circuit 34 and outputted.

Description

Detailed Description of the Invention [Field of Industrial Application] The present invention relates to an image encoding device, and in particular to an image vector suitable for a IIIR image encoding recording/reproducing device intended for data recording media such as optical disks. Quantizer C is involved.

[Conventional technology]

Vector quantization refers to dividing a k-dimensional (k is a natural number) vector space into N subspaces (N is a natural number) according to the distribution of a k-dimensional training vector set. Set the representative vector of the subspace and N
After generating a codebook, which is a set of representative vectors, for the k-dimensional input vector, the subspace to which the input vector belongs is detected, and the representative vector of that subspace is read out from the codebook and used as an output vector. It is. However, the training vector set is a set of vectors for codebook generation that is prepared in advance assuming the distribution of input vectors in the vector space.

Normally, for this set of training vectors, a predetermined distortion (distortion in the distance between two vectors) that occurs when each training vector is replaced with a representative vector of the subspace to which the training vector belongs The division of the vector space into subspaces and the setting of representative vectors for each subspace are gradually modified from the initial determination so as to minimize the total distortion 8 while calculating the sum of the corresponding values. A vector quantizer extracts k from a sequence of input data.
Generate a k-dimensional input vector that summarizes the data of
After performing the above vector quantization process, the k-dimensional output vector is converted into a sequence of output data and output.0 Now, the vector quantization process consists of vector fit child encoding and vector quantization. It can be divided into two parts: decoding. Vector quantization coding refers to dividing a vector space into N subspaces according to the quotient of a k-dimensional vector set in a k-dimensional vector space, and setting a representative vector for each subspace. After generating a codebook that is a set of N-dimensional representative vectors, find out the subspace to which the input vector belongs for the k-dimensional input vector, and calculate the number of that subspace, that is, the number of the representative vector of that subspace. This is the process of outputting it as an index. In addition, vector quantization decoding means that a codebook that is the same as the codebook generated in the vector quantization encoding process described above is maintained in advance, and the corresponding representative vector is added to the codebook according to the input index value. This is the process of reading out the vector from the vector and using it as an output vector. When using a fixed codebook for any input vector, it is sufficient to maintain a pre-generated codebook in the vector quantization encoder and vector quantization decoding 1111, but When changing the codebook at an appropriate time in response to changes in the distribution of input vectors, it is necessary to send the codebook generated by the vector quantization encoder to the vector quantization decoder each time.

A vector quantization encoder generates an input vector from a sequence of input data, performs the vector quantization encoding process described above, and if necessary outputs codebook information and then sequentially outputs index information. It is. Also,
When codebook information is input, the vector quantization decoder changes the codebook accordingly, performs the above-mentioned vector quantization and decoding processing from the sequentially input indices, and generates an output vector. It converts into a series of output data and outputs it.

Vector quantization converts the input vector pattern into Na!, which is the number of representative vectors in the courtbook. Since the amount of information of the index, which is the output of the vector decoding encoder, is per input data (1ogtN)
/ k bits, and the amount of information is reduced by compressing the data through vector doji conversion. Therefore, it is used as one of the high-efficiency encoding techniques for the purpose of compressing image data. The vector quantization encoding process and the vector quantization decoding process are attracting attention because they are relatively simple except for the process of generating code blocks. In particular, the process of vector quantization and decoding is very simple because it is a process of simply selecting one of the representative vectors in the codebook according to the input index. Therefore, vector quantization is a suitable technique for an image encoding recording/reproducing system that compresses and records images on package media such as optical disks. This is because real-time decoding processing is necessary, but real-time encoding processing is not particularly necessary.

FIGS. 5 and 4 show block diagrams of an image encoding recording/reproducing system intended for optical discs.

FIG. 3 is a block diagram of an image encoding/recording system that encodes an image and records it on an optical disk, and FIG. 4 is a block diagram of an image decoding/reproducing system that decodes data read from the optical disk and reproduces an image.

In FIG. 5, 1 is an input video signal terminal, 2 is an image encoding device. 5 is an optical disc recording device, and 4 is an optical disc. Further, in the image encoding device 2, 5 is A/Di.
6 is a frame memory. 7 is an image encoding circuit, 8
is the backup memory. Terminal 1 to iI image encoding device 2
The input video signal inputted from the A/D conversion circuit 5 is converted from an analog video signal to digital image data and stored in the frame memory 6. The image data read from the frame memory 6 is compressed by the image encoding circuit 7 using a predetermined efficiency encoding method to generate encoded data. After being stored in the buffer memory 8, it is delivered to the optical disk recording paddle 3. The optical disc recording device 3 records the encoded data on the optical disc 4 according to a predetermined optical disc recording method and distribution data format.
to be recorded. However, in the case of a read-only optical disc such as a CD (compact disc) on which the user cannot directly write, the optical disc 4 is manufactured by pressing after the master disc is generated.

In FIG. 4, 4 is an optical disk. 9 is an optical disc playback device, 10 is an image gl. Decoding device. 11 is a terminal for an output video signal. In addition, the image decoding device [10f,
12 is a puffer memo IJ, and 13 is an image decoding device. 14
is frame memory. 15 is a D/A conversion circuit. The disc playback device t9 reads compressed encoded data from the optical disc 4. The encoded data passed to the image decoding device 10 is once stored in the buffer memory 12, and then decompressed by the image decoding circuit 15 through decoding I to reproduce the image data. The data 11# after data expansion is stored in the frame memory 14, converted into an analog video signal in the D/A conversion circuit 15, and then outputted from the terminal 11 as an output video signal. In an image encoding recording/reproducing system for optical discs, a vector quantization encoder is used as the image encoding circuit 7 in the image encoding device 2, and an image decoding device 15 in the image decoding device 10 is used. A vector quantization decoder can be used as a vector quantization decoder. At this time, real-time processing of the image decoding device if10 that decodes and reproduces the compressed image data can be realized relatively easily.

Now, when generating a codebook, it is common to divide the vector space into subspaces and gradually modify the settings of the representative vector of each subspace from the initial settings. It's very big so thlgJ! It was almost impossible to incorporate it into the vector doji coding encoder of the encoding circuit 7. Therefore, it has been common to use a fixed codebook that is generated in advance from a training vector set over time. In other words, the same codebook is set in advance for both the vector quantization encoder and the vector quantization decoder, and only the index information generated from the input image data is transferred from the vector quantization encoder to the vector quantization encoder. It was passed to the quantization decoder.

However, the distribution of input vectors generated from input image data in a vector space varies considerably due to the influence of image characteristics such as the fineness of the image. Therefore, when vector quantization is performed using a fixed codebook, distortion caused by vector quantization becomes large, and negative iji deterioration of the reproduced image may become a problem. In order to avoid this, it is necessary to generate a codebook at an appropriate time in the vector quantization encoder using the input vector as a training vector, and to pass the information of the codebook to the vector quantization decoder. To do this, it is necessary to generate a codebook at high speed and execute vector quantization encoding processing.

Regarding this successful vector quantization encoding method, please refer to the IEE Conference on ASSHE. Dallas (1987) Glossary pp. 725-728 (Procee
dings * Pagea 725-728,
IEEEConference on AS SP.
Discussed in Dallaa (1987).

The process of generating a codebook using this high-speed vector quantization encoding method is as follows. First, when dividing the vector space into subspaces according to the distribution of the training vector set in the vector space, a restriction is added to the division method to simplify the process. In other words, one coordinate axis is selected based on a predetermined standard from among the k coordinate axes of the k-dimensional vector space, and after determining the coordinate position on that coordinate axis based on the predetermined standard, First, the entire vector space is divided into two by a hyperplane, and two subspaces are generated. Then, hierarchically repeat the process of further dividing those partially empty buildings into two in the same way,
Continue partitioning until the valley subspace holds only one training vector. All boundary surfaces that divide vector space into subspaces are characterized by being hyperplanes perpendicular to one of the coordinate axes.

Since bipartition processing is performed hierarchically, the state of vector space partitioning is completely maintained by retaining information on the division base coordinate axes and division coordinate positions in a binary tree structure for each two-division processing. stipulated in For example, the root node of this space division tree structure holds information for dividing the entire vector space into two, and the leaf nodes hold information about input vectors belonging to the corresponding subspace.

Next, after grouping several subspaces that exist in the vicinity of each other and generating multiple subspace groups from the entire vector space, in each subspace group, two parts within that subspace group are generated. The bear of the subspace with the minimum total distortion (corresponding to the sum of the distances between each training vector and the representative vector of the subspace to which the training vector belongs) added when the spaces are integrated is determined.

Then, among the subspace bears that are candidates for integration in each of these subspace groups, for example, half of the subspace pairs that have a small increase in total strain when integrated are integrated. By repeating the process of gradually integrating each subspace as described above, N subspaces are finally determined and the representative vector of each subspace is used as an element of the codebook.

The process of vector quantization using the generated codebook is as follows. First, the subspace to which the input vector belongs is found by searching the space division tree structure.

Next, among the representative vectors of that subspace and the representative vectors of neighboring subspaces, a representative vector that is close in distance to the input vector is selected from the codebook and used as an output vector. Compared to selecting from among all representative vectors in the codebook, the process of determining the output vector is simplified.

[Wllil to be solved by the invention] In a vector quantizer that adopts the above-mentioned high-speed vector quantization encoding method, the total distortion that occurs when vector quantizing an input vector is close to an ideal minimum value. However, the amount of processing required to generate the codebook and the amount of processing required to vector quantize the input vector and determine the output vector are not small. In other words, when generating a codebook, it is necessary to first divide the subspace into fine subspaces and then gradually integrate the subspaces, and when performing vector quantization of the input vector, the input vector It is necessary to select an output vector from representative vectors of a plurality of subspaces in the vicinity of the subspace to which the subspace belongs.

Additionally, the above document does not describe the process of generating a codebook using an input vector as a training vector, and then regenerating the codebook at an appropriate time according to changes in image characteristics such as the fineness of the picture. do not have. For example, 1II
When vector quantizing a JijI image, it is necessary to change the codebook in response to changes in image characteristics due to changes in the scene, and instead of rewriting all representative vectors in the codebook, it is necessary to It is desirable to rewrite only the representative vector of the section.

[Means to solve the problem]

In order to solve the above problems, in the present invention, the vector quantization encoder is configured as follows. The vector space is divided into two sequentially according to the distribution of the input vector in the k-dimensional vector space to generate N subspaces, and the state of the division of the vector space is shown. A spatial division tree structure generation means for generating a spatial division tree structure that is a binary tree structure that retains information;
Generate representative vectors of the subspace from a plurality of input vectors belonging to the valley subspace corresponding to the leaf nodes of the space division tree structure, and generate a codebook that is a set of the N generated representative vectors. The codebook generation means searches the subspace function to which each input vector belongs by sequentially tracing the space division tree structure from the root node, selects a representative vector of that subspace from the codebook, and uses the number of the representative vector. A vector quantization encoder is constituted by vector quantization encoding means for determining a certain index, and encoded information output means for sequentially outputting index information corresponding to each input vector after outputting codebook information.

When targeting moving images, a predetermined number of frames and I
This input image data is divided into multiple groups, each group is vector quantized and encoded using the vector quantization encoder described above, and the information of the book and the index information corresponding to each input vector are output. do. Furthermore, for each representative vector that is an element of the codebook of the current group, the vector quantization encoder described above calculates the representative vector of the previous group with the closest distance, and calculates the representative vector of the previous group whose distance is closer than a predetermined threshold. If so, replace the representative vector of the current group with the representative vector of the previous group, and if not, add codebook partial amplification means that outputs information on the representative vector of the current group as update information. The output means is of a different codebook compared to the case of the previous group! ! ! After outputting information on prime substitute p vectors as codebook change information for each group, the coded information output means outputs information on indexes corresponding to each input vector.

[Effect]

First, the space division tree structure generation means divides the entire k-dimensional vector space into two according to a predetermined rule to generate subspaces, and then repeats the process of dividing each subspace into two in a similar manner step by step. , generate N subspaces. For example, the above rule selects one Zara axis from among k Zara axes in a vector space according to a predetermined criterion,
After determining the coordinate position on the coordinate axis based on a predetermined standard, the partial space is divided into two by a hyperplane passing through the coordinate position and perpendicular to the coordinate axis. However, at an intermediate stage, the subspace to be divided into two next is determined based on a predetermined criterion.

Here, the method for selecting the division reference ridge axis is to select the coordinate axis with the largest distribution width based on the distribution @ of the input vectors belonging to the subspace in each coordinate axis direction.

For example, the distribution width in a certain coordinate axis direction can be defined as the difference between the maximum and minimum values of each input vector on that coordinate axis. This is to find the center value of the distribution regarding the axis. For example, the center value of the distribution can be defined as the median value (media/) of the values of each input vector on the division reference coordinate axis.

In addition, the method for determining the subspace to be divided next is to select the subspace with the largest distribution spread among all subspaces based on the spread of the distribution of input vectors belonging to the subspace. . For example, the size of the division can be defined as the sum of the variance values of the input vectors for each coordinate axis (the square of the difference between the input vector's corollary value and its average value). In the intermediate stage of processing, the input vector is divided starting from the subspace where the spread of the distribution is the largest, so the distortion caused by vector quantization can be reduced without having to perform the process of gradually integrating the input vector after first dividing it finely. A good codebook can be generated. Furthermore, since the number of times the vector space is divided into two is reduced, speeding up is possible.

In addition, while generating N subspaces in the above manner, information on the division reference coordinate axes and division coordinate positions for each two-part division, and the spread of the distribution of input vectors in the subspaces is used to create a binary tree. IJ + structure and R define the partitioning state g of N subspaces '(-:%). In this space partitioning tree structure, the root node has the entire vector space divided into two. Information upon division is held, and leaf nodes hold information on input vectors that belong to corresponding subspace nodes.

Next, for each of the N subspaces, the codebook generation means generates a representative vector of the subspace from the input vectors belonging to each subspace according to a predetermined standard,
A set of N generated representative vectors is defined as a codebook. Here, the method for generating the representative vector of the subspace is
The central vector of the distribution of input vectors belonging to the subspace is taken as the representative vector. For example, the center vector of the distribution can be defined as the center of gravity vector whose value is the average value of the values of the input vectors for each coordinate axis.

Then, the vector quantization encoding means searches for the subspace to which each input vector belongs by sequentially tracing the space division tree structure from the root node. In other words, at each node of the space division tree structure, the division reference coordinate axis The value of the input vector is compared with the division coordinate position, and the process proceeds to the left or right branch of the binary tree depending on the magnitude of the value. After searching the space-division tree structure in this way, an index, which is the number of the representative vector of the subspace corresponding to the finally reached leaf point, is obtained. Unlike conventional methods, vector quantization encoding is performed using a codebook generated from the input vector itself, so vector quantization can be performed without the need to include the representative vectors of neighboring subspaces to find the nearest representative vector. The distortion generated by this method hardly increases, and good vector quantization can be performed. Furthermore, since the process of determining the nearest representative vector is not performed, the processing speed can be increased.

By operating each means of the vector quantization encoder as described above, the distortion generated when vector quantizing the input vector is suppressed to a sufficiently small level, and the amount of processing when generating the codebook is reduced. The amount of processing required when determining an output vector by vector quantizing an input vector is also reduced, and high-speed vector quantization is realized.

Furthermore, when the target is a moving image, in order to follow fluctuations in image characteristics due to changes in the scene, input 1 for every predetermined number of frames. The data may be divided into a plurality of groups, and the vector quantization encoder may be operated as described above for the input vectors of each group. Here, the second vector quantization encoder operates as follows.

In the codebook partial update means, for each representative vector in the codebook of the current group, if there is a representative vector close to the representative vector in the codebook of the previous group, it is replaced with that representative vector. That is, the representative vector of the current group is compared with each of the representative vectors of the previous group to find the representative vector of the previous group with the closest distance, and if the distance is smaller than a predetermined threshold, the representative vector of the current group is used. is replaced with the corresponding representative vector of the previous group, and if not, the representative vector of the current group is output as update information. However, after vector quantization is performed using the codebook of the current group using the representative vector of the previous group as an input vector, the representative vector in each subspace is compared with the representative vector of the previous group associated with that subspace. By doing this, the representative vectors of the previous group closest to each of the representative vectors of the current group are found, and the distances are compared with a predetermined threshold. This reduces the amount of processing required to partially update the codebook, making it possible to speed up the process.

By operating the second vector quantization encoder as described above, the video Il! When vector quantizing the input vector, the distortion that occurs when vector quantizing the input vector is suppressed to a sufficiently low level, and at the same time, the information in the output codebook is reduced, and the amount of processing required to generate the codebook is reduced. In addition, the amount of processing required when determining an output vector by vector quantizing an input vector is also reduced, and high-speed vector quantization is realized.

〔Example〕

Embodiments of the present invention will be described in detail with reference to the drawings.

FIG. 1 is a block diagram of a vector quantization encoder that is an example of the present invention. Moreover, FIG. 2 is a block diagram of the vector quantization encoder and the corresponding vector quantization post-coder.

In FIG. 1, 21 is a terminal for input image data, 22 is a vector generation circuit, 23 is a space division tree structure generation circuit, 24 is a codebook generation circuit, 25 is a vector quantization encoding circuit, and 26 is a space division tree structure , and 27 is a memory that holds the codebook. 28 is an encoded information output circuit, and 29 is a terminal for output encoded information.

Input image data input from a terminal 21 is divided into blocks for each k pixels by a vector generation circuit 22, and the k input image data are combined to generate a k-dimensional input vector. First, all input vectors to be vector quantized are passed to the space division tree structure generation circuit 25, and the k-dimensional pek}/l/space is divided into N subspaces according to the distribution of the input vectors, and the space division A space division tree structure indicating the state of is output and stored in the memory 26. Next, a representative vector is generated from the input vectors belonging to each subspace, and N
representative vectors are output and stored in the memory 27.

After the space division tree structure is stored in the memory 26 and the codebook is stored in the memory 271 in this way, each input vector is individually stored in the vector quantization encoding circuit 271.
is vector quantized encoded. That is, the subspace to which the input vector belongs is found by searching the space division tree structure held in the memory 26, and the index, which is the number of the representative vector of that subspace, is found from the codebook held in the memory 27 and output. . The encoded information output means outputs the information of the codebook held in the memory 274, and then outputs the index sequentially output from the vector spacing encoding circuit 25.

A method for dividing a k-dimensional vector space into N subspaces is to first divide the entire vector space into two, and then repeat the process of sequentially dividing each subspace into two to generate N subspaces. When dividing into two, select the division standard coordinate axis that lies on that coordinate axis and has the largest distribution width of the input vector among the k coordinate axes, set the center value of the distribution on that coordinate axis as the division coordinate position, and divide it into two parts. Divide into two by a hyperplane perpendicular to the division reference coordinate axis at the coordinate position. The boundary surface of each subspace is always a hyperplane perpendicular to a certain coordinate axis. However, at an intermediate stage of division, the subspace in which the distribution of input vectors of the subspace has the largest spread at that point is selected as the next subspace to be divided into two.

As the distribution width for each coordinate axis when selecting a division reference coordinate axis, the value of the difference between the maximum value and the minimum value of the input vector values for that coordinate axis is used. Alternatively, the sum of the absolute values of the differences between the value of the input vector on the coordinate axis and its average value or the sum of the squared values can also be used. As the division coordinate position regarding the division reference coordinate axis, the median of the values of the input vectors on the division reference coordinate axis is used. Further, it is also possible to use a slight average value of the input vectors on the 9-division base single coordinate axis or the center value of the difference between the maximum value and the minimum value.

The spread of the distribution of the input vector in the subspace, which is referred to in order to determine the subspace to be divided into two parts at an intermediate stage, is the variance a of the input vector on each coordinate axis (the value of the input vector and its average value). The squared difference of ) is used for all Zara axes. Alternatively, the sum of the absolute value of the difference between the maximum value and the minimum value of the input vector in each coordinate axis or the difference between the value of the input vector and its average value for the previous coordinate axis can also be used. Furthermore, instead of the total value of all the input vectors belonging to the subspace, it is also possible to use the average value of each input vector divided by the number of the input vectors.

FIG. 5 illustrates this vector space division for a two-dimensional vector space. In this figure, 24 x marks indicate a two-dimensional input vector 438 that exists in the vector space, and the class line represents a hyperplane "'(゜~qQ)" that divides the eight subspaces 42 into which the space has been divided. E7r
';Lte0゛ru・So1・The Δ mark located almost in the center of each subspace is the representative vector 44 of each subspace,
A total of eight representative vectors 41 (+aO to hidden 7) are used as 111 of the codebook. The super-flat plane 41 that divides the partially empty space indicated by the broken line is a hyperplane (Ill because it is two-dimensional) perpendicular to either the X axis or the Y axis, which are the two axis axes. . In this figure, the entire vector space is divided by seven hyperplanes a to g to generate eight draw spaces.

The state of the space division is a binary tree structure (
This is defined by a space division tree structure which is the information about the space division maintained. The root node holds information about the division reference coordinate axis and the division coordinate position on that coordinate axis when dividing the entire vector space into two, and the spread of the distribution of input vectors in the entire vector space. Nodes in the middle of the space division tree structure hold information on the division reference coordinate axis and division coordinate position in the corresponding subspace, and the spread of the distribution of the six input vectors in the subspace number. The nodes of the set hold information on the input vectors of the corresponding subspace, and the representative vectors of that subspace are used as elements of the codebook.

FIG. 6 illustrates the space division tree structure 45 and the information in the codebook 49 for a two-dimensional vector space. The ○ mark is the root node 46 corresponding to the subspace to be divided, or the intermediate node 47, and information on the division reference coordinate axis, the division coordinate position, and the spread of the distribution of input vectors to which the subspace belongs. is held. Also, ● marks are leaf nodes 48 corresponding to the finally obtained N subspace numbers, and hold information on input vectors (x marks) existing within the subspaces. Usually, the number of input vectors existing in each subspace is not the same. The representative vector (Δ mark) of the subspace which is the node 48 of the leaf is N (hidden 0) corresponding to the N subspaces.
.about.M7) are generated and become the information of the code block 49.

Here, in the examples shown in Figures 5 and 6, the depth of the node of the leaf of the space division tree structure (the binary tree is the same and has a balanced tree structure, but in the middle of the space division Since the subspace with the widest spread of the input vector distribution at that point is selected as the next subspace to be divided into two, a non-flat tree structure in which the depths of the leaf nodes are generally uneven is obtained.As a result, The sum of the distances between the input vectors and the representative vectors in the codebook, that is, the sum of the distortions that occur when vector quantizing each input vector, is quite close to the ideal value, and a good codebook is generated.

The method of vector quantization encoding each k-dimensional input vector in the vector quantization encoding circuit 25 is to trace the space division tree structure sequentially from the root node to the leaf nodes, thereby determining the subspace to which the input vector belongs. The goal is to explore In other words, by comparing the value of the input vector in the division reference coordinate axis maintained at each node of the space division tree structure with the division coordinate axis, the node connected to the left side of the binary tree or the right side is determined depending on the magnitude of the value. Select nodes connected to . Sob! , outputs index information, which is the number of the finally arrived representative vector of the subspace to which the person vector belongs.

As described above, the vector quantization encoder shown in FIG. 1 performs high-speed codebook generation and high-speed vector quantization encoding based on the input image data input from the terminal 21, and and the index information corresponding to each input vector as output encoded information at terminal 2.
Output from 9.

@2 In Figure C, 50 is a terminal for input encoded information. 5
1 is an encoded information input circuit. 32 is a vector quantization decoding circuit. 53 is a memory that holds the codebook,! +4 is an image data reproducing circuit, and 35 is a terminal for output image data.

First, codebook information and index information, which are the outputs of the vector quantization encoder shown in FIG. 1, are input from the terminal 50 as input encoded information. In the encoded information input circuit 31, the codebook information is first input to the memory 5.
5, and then the index information is sequentially written to the vector quantization/decoding circuit 9. In the vector quantization/decoding circuit 52, since the index information is the number of the representative vector, the corresponding representative vector is read from the memory 35 in which the code hook is held, and is used as an output vector. The image data reproducing circuit 54 reproduces the iii image data from the output vector and outputs it from the terminal 35. In this way, the operation of the vector quantization decoder is very simple. ○ Also, when working with moving images, for example, the input image data is divided into multiple groups for each predetermined number of frames, and each Vector quantization may be performed for each group using the vector quantization encoder and the vector dojikaization encoder.

That is, in order to follow changes in image characteristics due to changes in the scene, the codebook is updated by regenerating the codebook from the input vector every predetermined number of frames.

Next, a second embodiment of the present invention will be described in detail. FIG. 7 is a block diagram of a vector quantization encoder according to a second embodiment of the present invention. Moreover, FIG. 8 is a block diagram of the vector quantization encoder and its counterpart, the vector quantization post-coder. These are videos @! A vector quantization encoder and a vector quantization decoder for .

In FIG. 7, 51 is a terminal for input image data. 52
is a vector generation circuit. 53 is a space division tree structure generation circuit. 54 is the codebook life cycle circuit, and 55 is the codebook partial update circuit. 56 is a vector quantization encoding circuit, and 57 is a memory that holds a space division tree structure. 58
59 is an encoded information output circuit; and 60 is a terminal for output encoded information.

Vector generation circuit 52 and space division IJ structure generation circuit 55 in FIG. A codebook generation circuit 54, a vector quantization encoding circuit 56, a memory 57 for holding a space division tree structure. and memory 5 for storing the codebook.
The structure and operation of 8 are the same as those of the vector quantization encoder of FIG. 1, which is the first embodiment described above. first,
After the input image data is divided into a plurality of groups for each predetermined number of frames, the input image data for each group is vector quantized and encoded. That is, the codebook is updated every predetermined number of frames.

Input image data input from the terminal 51 is converted into a k-dimensional input vector by the vector generation circuit 52. From all the input vectors of the group, a space division tree structure generation circuit 53 executes space division according to the distribution of the input vectors, generates a space division tree structure, and stores it in the memory 5.
74 praises are received. A representative vector for each of the N subspaces is generated by a codebook generation circuit 54 and passed to a codebook partial aggregation circuit 55. The codebook partial update circuit 55 compares the information of the previous group's codebook currently held in the memory 58 with the information of the current group's codebook newly generated by the codebook generating circuit 54, and changes the information. The representative vectors in the memory 58 are rewritten only for necessary representative vectors. Then, the information on the codebook partial anobdate, which is the representative vector that needs to be changed,
The encoded information output circuit 59 outputs index information corresponding to each input vector as a result of vector quantization encoding in the vector quantization encoding circuit 56 from a terminal 60 as output encoded information.

The idea of detecting whether each representative vector kl in the codebook of the current group is close to the representative vector in the codebook of the previous group in the codebook partial update path 55 is as follows. In other words, the representative vector of the previous group that is closest to the representative vector of the current group is searched, and if the distance to the nearest representative vector found as a result is smaller than a predetermined threshold, the current group is searched for. The representative vector of the corresponding previous group is substituted for the substitute vector of the group, and the representative vector of the previous group held in the memory 58 is not rewritten. Although the two are close, they are not completely the same, and this process slightly increases distortion due to vector quantization, so the threshold value must be determined in such a way that the increase in distortion is not significant. In addition, when the representative vector of the previous group is used as the representative vector of the current group without changing it, the index value for that representative vector, that is, the number in the codebook of the representative vector, is the same. It is necessary to take this into account when numbering the representative vectors of the current group.

Figure 9 shows the actual codebook partial attach circuit 5.
FIG. 5 is a block diagram of No. 5. 71 is a representative vector reading circuit. 72 is a vector quantization encoding circuit, 75 is a memory that holds a space division tree structure, 74 is a memory that stores and holds a codebook, and 75 is a nearest neighbor vector detection circuit.
76 is an update determination circuit.

First, each representative vector in the codebook of the previous group stored in the memory 58 is read out by the representative vector reading circuit, and the vector quantization encoding circuit 72
passed to. The vector quantization encoding circuit 72 vector-retracts each representative vector of the previous group, which is an input vector, using the space-division tree structure of the current group generated by the space-division tree structure analysis means 55 and held in the memory 75. encode and output the index and its input vector. Then, the nearest vector detection circuit 75 calculates the index output from the vector quantization encoding circuit 72 for each representative vector of the codebook of the current group generated by the codebook generation circuit 54 and stored in the memory 74. The representative vectors of a plurality of previous codebooks corresponding to the original number are found, and the one with the closest distance is detected and selected.

After one representative vector of the previous codebook corresponding to each representative vector of the current codebook is selected in this way, the representative vector of the previous codebook is passed to the update determination means, and the representative vector of the current codebook is passed to the update determination means. It is determined whether the distance to the vector is smaller or larger than a predetermined threshold. As a result, if it is smaller than the threshold value, the representative vector of the previous codebook is used as is, and the update determination circuit 7
6 outputs nothing. However, if it is larger than the threshold, it is necessary to use the representative vector of the current codebook, so the new representative vector is output from the update determination circuit 76, and the previous codebook held in the memory 58 is partially At the same time as updating, it is passed to the encoded information output circuit 59. Note that if there is no corresponding representative vector of the previous codebook with respect to the representative vector of the current codebook, it is updated in the same way.

FIG. 10 is a conceptual diagram showing a method for determining whether to partially update the previous codebook. 81 is a subspace in the space division of the current group. 82 is a representative vector of the current group in that subspace, and 85 is a representative vector of the previous codebook associated with that subspace by the operation of the vector quantization encoding circuit 72 of the codebook partial update circuit 55. 84 is a hypersphere in the vector space whose radius is a predetermined threshold value.

In case (a), Yuko is the vector 8 of the current codebook.
Since the representative vector 85 of the previous codebook closest to 2 is inside the hypersphere 84 whose radius is a predetermined threshold value, we will use the representative vector of the previous codebook as is. , its representative vector is not updated. On the other hand, in the case of ω, there is no representative vector of the previous codebook that enters the hypersphere 84, so the representative vector of the current codebook 82
We will perform an attestation using this as a new representative vector. In this method, the process of comparing each representative vector of the current codebook with the representative vector of the previous codebook is simplified, so that the process of partially updating the codebook is sped up.

FIG. 11 is a conceptual diagram showing how codebook partial update information is generated by the above processing. The codebook information generated by the codebook generation circuit 54 is
Of course, in the first group, all information is output from the codebook partial update circuit 55 as codebook partial update information. However, in the intermediate group, the process described above searches to see if there is a representative vector close to the previous group's representative vector, and if a similar representative vector exists, the representative vector of the previous group is The vector replaces the current group's representative vector. As a result, the information output from the codebook partial update circuit 55 is only information related to representative vectors of a portion of the codebook. However, for each representative vector of the current group, it is necessary to add flag information indicating whether or not to output the representative vector by some method.

Now, the vector quantization decoder shown in FIG. 8, which is the counterpart of the vector quantization encoder shown in FIG. 7 explained above, will be explained. @8 In Figure 8, 61 is a terminal for input encoded information. 62 is an encoded information input circuit, and 65 is a vector quantization/decoding circuit. 64 is a memory that holds the codebook. 65
1 is an image data reproducing circuit, and 66 is a terminal for output logical image data.

A vector quantization decoding circuit 65, a memory 64 for storing a codebook, and an image data reproduction circuit 65 in FIG.
The structure and operation of the decoder are the same as those of the quantization decoder in FIG. 1, which is the first embodiment described above. The codebook is updated for each group, and the input index is vector quantized and decoded to reproduce output image data.

First, codebook partial aggregation information and index information, which are the outputs of the vector doji conversion encoder shown in FIG. 7, are inputted from the terminal 61 as input encoded information. In the encoding information input circuit 62, first, only the representative vector of a part of the codebook held in the memory 64 is omitted according to the information of the codebook partial update, and then the information of the sequential index is vector quantized and decoded. It is passed to circuit 65. The vector quantization/decoding circuit 63 reads out the representative hector corresponding to the index from the memory 64 in which the codebook is held, and uses it as an output vector. Then, in the image data reproducing circuit 54, output image data is reproduced from the output vector and outputted from the terminal 66.

In the embodiment of the present invention described in detail above, it is assumed that the code information and the index information are passed as they are from the vector t-child encoder to the vector quantization decoder.
By variable-length encoding the codebook information in the encoded information output circuit of the vector quantization encoder, the amount of information t to be transmitted can be reduced without increasing distortion due to vector t-childization. Information on the codebook to be transmitted￥IA4c
Regarding this, the k coordinate values of each representative vector can be dynamically encoded in variable length using a variable length encoding table generated in advance.Also, regarding the index information, similarly, variable length encoding can be performed. In some cases, the amount of information can be reduced by encoding.

In addition, when input image data is divided into groups for video gI, and the codebook is updated for each group and the input vector is vector quantized encoded, the index is partially updated for each frame of the video. It is also possible to do this. That is, each of the vector quantization encoder and the vector quantization decoder is provided with an index memory that holds an index regarding input vectors for one entire frame, and the vector quantization encoder converts each input vector into a vector. The index of the current frame output after quantization encoding is compared with the index of the previous frame at the corresponding screen position lt4. Then, if they do not match, G outputs the information of that index, or if they match, I does not output the information of that index. However, it is necessary to add flag information to indicate whether or not to send it in some way. Incorporating a partial update of the index in this way allows the amount of information to be further reduced without adding to the distortion of vector t-childization.

〔Effect of the invention〕

According to the present invention, there are the following effects. First of all, by simplifying the method of dividing the vector space, storing Wll information for that space in a binary tree structure, and generating a codebook from the representative vectors of each subspace, it is possible to The amount of processing and the amount of processing when vector quantizing and encoding input vectors can be significantly reduced, and high-speed vector quantization can be achieved. Also, in the middle of the process of dividing a subspace into two, the subspace with the widest distribution of input vectors is selected as the next subspace to be divided, so the final divided subspace The codebook made up of representative vectors is fairly close to optimal, and the distortion that occurs when vector quantizing input vectors can be sufficiently reduced.

Second, when performing vector quantization on IIfJ images, divide the input image data into 8 groups, vector quantize the input vectors for each group in the same manner as described in -E, and By sending only the information of the codebook partial update of the part that has changed compared to the codebook contents from the vector quantization encoder to the vector quantization decoder, the information amount of the result of vector quantization encoding is will be significantly reduced. Then, in 0), the representative vector of the previous codebook to be partially updated is determined by vector quantization of each representative vector of the previous codebook using the current codebook.
High-speed partial amplification of the codebook can be achieved.

[Brief explanation of drawings]

FIG. 1 is a block diagram of a vector quantization encoder according to the first embodiment of the present invention, and FIG. 2 is a block diagram of a vector quantization decoder corresponding to the vector quantization encoder of FIG. 1. , FIG. 5 is a block diagram of an image encoding recording system for an optical disc, FIG. 4 is a block diagram of an image postcoding and reproducing system corresponding to the image encoding recording system of FIG. 5,
Figure 5 is a conceptual diagram showing the state of vector space division;
The figure is a conceptual diagram of a space division tree structure corresponding to the space division state of FIG. 5, and FIG. 7 is a block diagram of a vector quantization encoder for moving images, which is a second embodiment of the present invention.
FIG. 8 is a block diagram of a vector quantization decoder corresponding to the vector quantization encoder in FIG.
Part 11 is a detailed block diagram of the codebook partial update circuit and a conceptual diagram of the determination process. 21.51... Input data 29.60... Output encoded information 30.61... Input encoded information 55.66... Output image data 25.5! S... Space division tree structure generation circuit 24.
54...Codebook generation circuit 26, 57. 75
... Space division tree structure memory 27, 55. 58
, 64. 74...Codebook memory 25.56
．． 72...Vector quantization encoding circuit 52.63...
- Vector quantization decoding circuit 55...Codebook partial update circuit 75...Nearest vector detection path 76...Update determination circuit 42...Draw space 45...Input vector 44... Representative vector tsu 1 Dark figure 5 man 2 figure 6 figure 46 Jaku no node code Fushiku 7th west figure 8 figure 9? (L) ″lP site F-■η｝re (b) ゛Information included-489 11 [ffi YO~Y7 1st page 5/) r Kutonore

Claims (1)

[Scope of Claims] 1) Vector generation means for generating a multidimensional input vector by dividing input image data into blocks each consisting of a plurality of pixels; Divide into multiple subspaces,
space division tree structure generation means for generating a space division tree structure indicating a state of division of the vector space, and a plurality of input vectors existing in each subspace corresponding to a leaf node of the space division tree structure; codebook generation means for generating a representative vector of the subspace to generate a codebook that is a set of representative vectors; Find the subspace to which
vector quantization encoding means for selecting a representative vector of the subspace from the codebook and generating an index that is a number of the representative vector; and after outputting the information of the codebook, the index corresponding to each input vector. 1. A vector quantization encoder for image data, comprising encoded information output means for sequentially outputting information. 2) Encoding information input means for sequentially inputting index information after inputting codebook information, and vector quantization decoding means for reading out and outputting a representative vector whose number is the value of the index from the codebook. ,
A vector quantization decoder for image data, comprising an image data reproduction means for synthesizing multidimensional output vectors that are outputs of the vector quantization decoding means and reproducing output image data. 3) Vector generation means for generating multidimensional input vectors by sequentially dividing input image data of a plurality of groups into blocks each consisting of a plurality of pixels for each group, and sequentially generating the input vectors in a multidimensional vector space for each group. space division tree structure generation means for dividing a vector space into a plurality of subspaces according to the distribution of the vector space, and generating a space division tree structure indicating the division state of the vector space; codebook generation means for generating a representative vector of a subspace from a plurality of input vectors existing in each subspace corresponding to a node of a leaf of the structure, and generating a codebook that is a collection of representative vectors; For each representative vector that is an element of the codebook of a group, find the representative vector that is an element of the codebook of the previous group that has the smallest distortion corresponding to the distance between two vectors in a predetermined distortion measure, and a codebook partial update means that replaces the representative vector of the current group with a corresponding representative vector of the previous group if it is smaller than a threshold; and traversing the space division tree structure in order from the root node for each group. vector quantization encoding means for detecting a subspace to which the input vector belongs for each input vector, selecting a representative vector of the subspace from the codebook, and generating an index that is a number of the representative vector; , for each group, among the representative vectors that are elements of the codebook of the current group, information about representative vectors that are different from any of the representative vectors that are elements of the codebook of the previous group is output as codebook change information, and then each input vector is 1. A vector quantization encoder for image data, comprising encoded information output means for sequentially outputting information of the index corresponding to the index. 4) Encoding information that inputs codebook change information for each group and generates a codebook by comparing it with the codebook of the previous group and rewriting only the changed representative vectors, and then sequentially inputting index information an input means, a vector quantization/decoding means for reading and outputting a representative vector whose number is the value of the index for each group from the codebook, and an output of the vector quantization/decoding means for each group. 1. A vector quantization decoder for image data, comprising an image data reproducing means for synthesizing multidimensional output vectors and reproducing output image data.