JP2000040966A - Device and method for data compression, device and method for data expansion, data compression and expansion system, and recording medium - Google Patents

Abstract

PROBLEM TO BE SOLVED: To obtain a reproduced image of high quality by surely retrieving a pattern image which matches human visual sensation characteristics. SOLUTION: When vector quantization is performed, the pattern of a block cut out of a source image is detected by a pixel arithmetic part 2, and one of code books 5a and 5b is used for the vector quantization according to the detected pattern to select an optimum pattern image from the code book matching, for example, a solid image for a solid part and an optimum pattern image from the code book matching an edge for an edge part, thereby obtaining a natural reproduced image matching human visual sensation characteristics, when the image is reproduced by using a selected code vector.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a data compression apparatus and method, a data expansion apparatus and method, a data compression / expansion system, and a recording medium storing a program for executing these processes. It is suitable for use in apparatuses, methods and systems that use vector quantization as one of the above.

[0002]

2. Description of the Related Art Conventionally, various data compression techniques have been proposed. Among them, a technique called “vector quantization” is well known as one of data compression algorithms that can very easily perform decompression processing of compressed data. This algorithm has been known for a long time in the field of signal processing, especially for data compression of image signals and audio signals,
Or it has been applied to pattern recognition.

In this vector quantization, several pixel patterns of a certain size (for example, a block of 4 × 4 pixels) are prepared, and a unique number or the like is given to each of them (this set is called a “codebook”). ). Then, for example, blocks of the same size (for example, 4 × 4 pixels) are sequentially extracted from the image data of the two-dimensional array, a pattern most similar to the block is found in the codebook, and the pattern number is assigned to the block. Perform data compression. In vector quantization, a data sequence in one block corresponds to one vector.

FIG. 10 is a diagram showing a schematic configuration example of a conventional vector quantization apparatus. In FIG. 10, an original image input by an image input device 101 is supplied to a compression device 102 based on a codebook method. The code book compression device 102 includes a code book storage device 103
A vector quantization process described below is performed on an input original image using a pattern image (for example, an image of a block composed of 4 × 4 pixels) registered in advance as a code book.

[0005] Codebook-based compression apparatus 102
When the input original image is a still image, the following processing is performed on the single still image. When the input original image is a moving image, the following processing is sequentially performed on each frame image. That is, starting from the upper left of the original image, blocks of 4 × 4 pixels are sequentially extracted rightward from there. When the block is taken out to the right end, the take-out position is shifted down by one block, taken out again from the left end, and by repeating this, blocks for the entire screen are taken out.

Then, for each block taken out,
A code vector having the most similar pattern is selected from a large number of code vectors registered in the code book storage device 103, and a corresponding code number is output. For example, 6
When processing an image of 40 × 480 pixels, 19200 blocks are extracted and processed, so that the output code number is also 19200.

On the receiving side or the decompressing side of the coded compressed data, the original image can be reproduced only by extracting the pattern corresponding to the code number for each block from the code book. Therefore, on the decompression side, if the code book is received or stored in advance, no special operation is required, and the original image can be reproduced with very simple hardware.

[0008]

In the above-described vector quantization, for example, when performing image data compression,
The challenge is how to obtain a high-quality reproduced image while maintaining a high compression ratio, and how to create a high-performance codebook that is always required for performing vector quantization.

When performing vector quantization, it is necessary to perform a search process for finding a code vector of a pattern similar to vector data of an original image from a code book as described above. Conventionally, as means for determining whether two vector data are similar, conventionally, two vector data are input to a predetermined function and operated to convert the degree of similarity into a numerical value, and a determination is made based on the magnitude of this numerical value. Was.

As the predetermined function, a function for obtaining a Manhattan distance or a Euclidean distance between two input vector data has been used. The Manhattan distance is obtained by calculating the absolute value of the difference between the individual elements constituting the two input vector data, and adding all the absolute values of the differences calculated for each element. Further, the Euclidean distance is obtained by calculating the sum of squares of the absolute value of the difference as described above.

FIG. 11 is a diagram for explaining a problem of a conventional example in which a similarity is obtained by such a method to search for a code vector. FIGS. 11A and 11B show a part of a reproduced image reproduced by embedding a plurality of code vectors (pattern images for each block) obtained by vector quantization for each block. A plurality of squares shown in FIG. 11 correspond to individual blocks.

FIG. 11A shows that the original image (not shown) before compression is an image in which the overall luminance gradually changes in the direction from the lower left block to the upper right block (large arrow). Regardless, the reproduced image shows that a pattern block whose luminance changes in the opposite direction (small arrow) is included. FIG. 11 (b) is a reproduction of a portion corresponding to an edge in the original image, but shows that this edge portion is not reproduced well.

As described above, according to the conventional vector quantization technique, for each of the image in which the luminance value changes gradually and the image in which the luminance value changes rapidly, humans feel uncomfortable with the embedded pattern. However, there is a problem that an unnatural reproduced image that makes the user remember the image.

One of the causes is that the conventional codebook is not created in consideration of the pattern in which the luminance value changes gradually or the pattern in which the luminance value changes rapidly as described above. This is because a pattern image suitable for each is not necessarily included in the created codebook.

As another cause, in the conventional vector quantization, the similarity is calculated independently for each block, and the similarity is calculated by using the information of all the pixels in the block. It is also possible that they are seeking. That is, although the codebook contains code vectors of various patterns, the similarity with the input vector extracted from the original image is based on the sum of the absolute values of the differences for each pixel for each block. Given.

[0016] Therefore, even if a pattern is opposite to the direction of the luminance as a whole, if the calculated similarity is larger than other patterns, the pattern is selected. In other words, even if a codebook of a more natural pattern image is included in the codebook as a whole, it may not be selected, and an unnatural pattern image may be selected. If such blocks of the pattern image are included in various places in the reproduced image, the viewer will feel uncomfortable.

The present invention has been made to solve such a problem, and a high-quality reproduced image can be obtained by reliably searching for a pattern image suitable for human visual characteristics. The purpose is to be able to.

[0018]

According to the data compression apparatus of the present invention, a data sequence having at least one or more data is divided into blocks and extracted as vectors from a code book prepared in advance. In a data compression device that searches for a code vector similar to a vector and outputs a code corresponding to the code vector, code book storage means for storing code books prepared for different types of patterns, and information in the block to be compressed Based on the above, a discriminating means for discriminating what kind of pattern the data of the block is, and a vector quantization process using the codebook prepared for each pattern in accordance with the discrimination result by the discriminating means. And a vector quantization means for performing the following.

Here, the discriminating means includes, for example, a first pattern in which the data value gradually changes in a certain direction in the block based on the data value of each element in the block to be compressed; The second where the data value changes rapidly
Is determined. For example, when the difference between the maximum value and the minimum value among the elements in the block is less than a predetermined threshold, the block is determined to be the first pattern, and the difference between the maximum value and the minimum value in the block is determined. If the difference is larger than a predetermined threshold, the block is determined to be the second pattern.

Further, the vector quantizing means may determine the similarity of the blocks of the different types of patterns by different processes. In this case, the vector quantization means may, for example, perform a first quantization in which the data value of each element in the block to be compressed gradually changes.
The similarity is calculated using the data values of the elements at the four corners in the rectangular block. Further, the direction of the data value change in the block may be detected from the data values at the four corners in the block, and the similar code vector may be searched for in consideration of this direction. When the vector quantization is performed with the information on the four corners as described above, the first
Each of the code vectors constituting the code book for the pattern may be constituted only by information of the elements at the four corners in the block.

Further, the data decompression device of the present invention uses a data string having at least one or more data as a vector and searches for a code vector corresponding to a compressed code from a code book having at least one or more code vectors. In a data decompression device that reproduces original data by allocating it to a corresponding block position, codebook storage means for storing codebooks prepared for different types of patterns, Decoding means for searching for a code vector corresponding to the compressed code from the code book prepared for each pattern based on the compressed code generated separately for each pattern.

Here, the different types of patterns are, for example, a first pattern in which the data value of each element in the block to be compressed gradually changes in a certain direction in the block, and a data value in the block in which the data value is changed. The rapidly changing second
And the pattern. Further, each code vector constituting the codebook for the first pattern may be constituted only by information of elements at four corners in a rectangular block. In this case, there may be provided a calculating means for calculating information on other elements by calculation based on information on elements at the four corners in the block.

In the data compression method of the present invention, a data sequence having at least one or more data is divided into blocks to form a vector, and a vector similar to a vector extracted from a compression target from a codebook prepared in advance. In a data compression method of searching for a code vector and outputting a code corresponding to the code vector, a type of data of the block is determined based on information in the block to be compressed, and according to a result of the determination. , The vector quantization process is performed using a codebook prepared for each pattern.

In another aspect of the present invention, when performing the above-described vector quantization processing, the similarity between vectors is obtained by different processing for the blocks of the different types of patterns, and the first similarity is obtained. For the pattern (1), the similarity may be obtained using only the data values of the elements at the four corners in the rectangular block. Further, the direction of the data value change in the block may be detected from the data values at the four corners in the block, and the similar code vector may be searched for in consideration of this direction.

Further, in the data decompression method of the present invention, a data string having at least one or more data is set as a vector, and a code vector corresponding to a compressed code is searched for from a code book having at least one or more code vectors. In the data decompression method of reproducing the original data by assigning it to the corresponding block position, a code prepared for each pattern is generated based on the compression code generated by dividing the compression side into different types of patterns. A code vector corresponding to the compressed code is searched for from a book.

In another aspect of the present invention, each of the code vectors constituting the code book for the first pattern has only information of elements at four corners in a rectangular block, and a code corresponding to the compressed code is provided. When searching for a vector and assigning it to a corresponding block position, information on other elements may be calculated by calculation based on information on elements at the four corners in the block.

Further, the data compression / decompression system of the present invention blocks a data string having at least one or more data into a vector, and resembles a vector extracted from a compression target from a codebook prepared in advance. A data compression device that searches for a code vector corresponding to the code and outputs a code corresponding to the code vector, and a code vector corresponding to the code is searched from the code book and the original data is reproduced by assigning the code vector to a corresponding block position. In the data compression / expansion system provided with a data decompression device, the data compression device includes: first codebook storage means for storing codebooks prepared for different types of patterns; Based on the information, the data of the block Discriminating means for discriminating whether or not, and according to the discrimination result by the discriminating means, vector quantization means for performing a vector quantization process using the codebook prepared for each pattern, The decompression device includes a second codebook storage unit that stores a codebook prepared for each of different types of patterns, and a compression code generated for the different types on the compression side. And decoding means for searching for a code vector corresponding to the compressed code from the code book prepared in (1).

Here, the first and second codebook storage means may store codebooks of different types of patterns in one storage device. Further, the first and second codebook storage means store codebooks of different types separately in a plurality of storage devices, and determine which pattern together with the code generated by the data compression device. Information for identification may be supplied to the data decompression device.

Further, a computer-readable recording medium of the present invention is characterized in that a program for causing a computer to function as the above-described units or a program for causing a computer to realize the above-described functions is recorded. Another embodiment of the present invention is characterized in that a program for causing a computer to execute the processing procedure of the above-described data compression method or data decompression method is recorded.

[0030]

DESCRIPTION OF THE PREFERRED EMBODIMENTS One embodiment of the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram showing a configuration example of a data compression / decompression system according to the first embodiment of the present invention, and FIG. 2 is a diagram for explaining the principle of operation according to the first embodiment. is there. First, the principle will be described with reference to FIG.

As shown in FIG. 2, in the present embodiment, a plurality of blocks (for example, one block is 4 × 4 pixels) extracted from an original image when performing vector quantization are divided into pixel values within the block. A block of a pattern that gradually changes in a certain direction (hereinafter referred to as a low-frequency pattern or a solid pattern) and a pattern in which the pixel value changes rapidly in the block (hereinafter referred to as a high-frequency pattern or an edge pattern) ) Block.

For each block of the solid pattern and the edge pattern, vector quantization (V) is performed independently using a low frequency codebook and a high frequency codebook prepared in advance for each pattern.
The processing of Q) is performed, and the results obtained for each are combined into compressed data. Although individual blocks are not shown in FIG. 2, only a solid pattern block is included in a low-frequency pattern image, and only an edge pattern block is included in a high-frequency pattern image.

FIG. 1 shows a configuration for realizing such an operation. In FIG. 1, reference numeral 1 denotes an image input unit for inputting image data to be compressed. The image input unit 1 has a function of dividing an entire input image into blocks of, for example, 4 × 4 pixels, and outputting an image for each block. The image data to be compressed may be a still image or a moving image. Further, the image may be a monochrome image or a color image.

Reference numeral 2 denotes a pixel operation unit, which executes an operation necessary to determine whether the input block image corresponds to a solid pattern or an edge pattern. For example, here, the minimum luminance value and the maximum luminance value are detected from each pixel in the block, and the difference is calculated. When the difference is small, it corresponds to a solid pattern in which the luminance value changes gradually. When the difference is large, it corresponds to an edge pattern in which the luminance value changes rapidly.

Reference numeral 3 denotes a search threshold input unit for inputting a threshold necessary for performing pattern determination based on the difference between the minimum luminance value and the maximum luminance value in the block calculated by the pixel operation unit 2. Reference numeral 4 denotes a codebook compression unit.
Based on the operation result input from the pixel operation unit 2 and the threshold value input from the search threshold input unit 3, it is determined whether the block is a solid pattern or an edge pattern, and an appropriate codebook is used in accordance with each of them. Execute the vector quantization process.

That is, when the block is a solid pattern, vector quantization is performed using a solid pattern codebook 5a stored in the codebook storage unit 5 in advance. On the other hand, when the block is an edge pattern, vector quantization is performed using the edge pattern codebook 5b stored in the codebook storage unit 5 in advance. The codebook storage unit 5 previously stores a plurality of pixel patterns having the same size (block of 4 × 4 pixels) as blocks extracted from an original image as code vectors.

The solid pattern code book 5a is, for example, as shown in FIG. 3 (a), in which a plurality of code vectors of a pattern which monotonously changes in eight directions are registered.
That is, a set of patterns whose pixel values (for example, luminance values) gradually change starting from any one of the edge portions (upper, lower, left, right sides, and four corners) of a block composed of 4 × 4 pixels. It is. Although only eight patterns are shown here, a large number of solid patterns are actually registered with variations in the luminance value of the starting point and the degree of luminance change.

The edge pattern code book 5b
In FIG. 3, for example, as shown in FIG. 3B, a plurality of code vectors of a pattern whose luminance value changes rapidly is registered. Note that only 12 patterns are shown here, but with variations similar to solid patterns,
Alternatively, many edge patterns including patterns other than those shown here are registered.

Returning to FIG. 1, a code number output unit 6 outputs a code number sequence obtained as a result of performing vector quantization for each block by the code book system compression unit 4. In the case of the present embodiment, a series of code numbers (such as addresses of a storage device) are assigned to each code vector constituting the solid pattern codebook 5a and the edge pattern codebook 5b, and the similarity is assumed to be large for each block. A code number sequence corresponding to each searched code vector is output. The above is the configuration on the compression side.

A code number input unit 7 inputs a code number sequence of each block output from the code number output unit 6 on the compression side. The code number output unit 6 and the code number input unit 7 are connected by a communication path such as a network,
The code number may be transferred via this network, or the code number sequence output from the code number output unit 6 may be temporarily stored in a storage medium such as a floppy disk and input to the decompression side via this. You may do it.

Reference numeral 8 denotes a code book type decompression unit, based on the code number sequence input from the code number input unit 7,
The corresponding pattern image of the code vector is read from the code book storage unit 9 and embedded in the corresponding block position, thereby performing a process of generating a reproduced image.
At this time, if the input code number corresponds to the solid pattern, the corresponding code vector is read from the solid pattern code book 9a. If the code number corresponds to the edge pattern, the corresponding code vector is read from the edge pattern code book 9b.

Similarly to the codebook storage unit 5 on the compression side, the codebook storage unit 9 also uses a plurality of pixel patterns having the same size (blocks of 4 × 4 pixels) as blocks extracted from the original image as code vectors. It is something that I remember. This code book may be transmitted and stored before the decompression processing of the code book on the compression side, or the same code book may be stored from the beginning.

The reproduced image generated by the codebook expansion unit 8 is provided to the image display device or the storage device 10 and is displayed as an image or stored as image data. The above is the configuration on the extension side.

Next, a specific operation of the data compression / decompression system according to the present embodiment configured as described above will be described.
This will be described with reference to the flowcharts of FIGS. FIG. 4 shows the operation on the compression side. In FIG. 4, first, a processing process is performed in step S1. here,
A process for clearing a block counter for counting processed blocks is performed.

Next, after giving threshold T _H of the search in step S2, enter one of the image blocks in step S3. Then, in step S4, the image blocks the input to calculate the difference between the maximum luminance value and minimum luminance value in the block, it is determined whether the calculation result is larger than the search threshold T _H.

[0046] Here, when the calculated difference value is greater than the search threshold T _H, since the block will be referred to as an image edge pattern, vector quantization using the edge pattern codebook 5b proceeds to step S5 To find the code vector of the edge pattern most similar to the input image block.

Meanwhile, if the calculated difference value is not greater than the search threshold T _H, since the block will be referred to as an image of the solid pattern, vector quantized using a solid pattern codebook 5a proceeds to step S6 To find a code vector of a solid pattern most similar to the input image block.

When the vector quantization process is completed in step S5 or step S6, the process proceeds to step S7, where the image of the input block is encoded by replacing it with a code number corresponding to the found code vector. Thereafter, in step S8, the replaced code number is output.

Then, the process proceeds to a step S9, and it is determined whether or not the above-described processing has been completed for all the blocks in the image. If not completed, the value of the block counter is increased by 1 in step S10, and the process returns to step S3 to repeat the same processing. In this way, the original image is compressed by finding the optimum codes for all the blocks in the image. It should be noted that the processing of steps S8 and S9 may be interchanged to output the code number sequence of one image collectively.

FIG. 5 shows the operation on the extension side. In FIG. 5, processing processing is first performed in step S11. Here, a process of clearing a block counter for counting processed blocks is performed. Next, in step S12, the code number specified on the compression side is set to 1
Enter one.

In the next step S13, a pattern image of a code vector corresponding to the code number is searched from the solid pattern code book 9a or the edge pattern code book 9b based on the input code number. Then, it is read out and embedded in the corresponding block position (specifically, it is stored at a predetermined position in the reproduction image buffer).

Next, after the generated reproduced image is displayed on a display or the like or stored in a storage medium in step S14, the flow advances to step S15 to determine whether or not the above processing has been completed for all blocks in the image. to decide. If the processing has not been completed, the value of the block counter is increased by 1 in step S16, and the process returns to step S12 to repeat the same processing.

By reproducing the pattern image for all the blocks in the image in this way, the original image is reproduced. Note that the processing of steps S14 and S15 may be interchanged, and processing such as image display and storage may be performed after all one reproduced image is generated.

In the above example, an example is shown in which a solid pattern portion and an edge pattern portion are provided in one codebook. However, as shown in FIG. 6, a codebook for a solid pattern and an edge pattern portion are provided. And two codebooks may be prepared separately.
That is, solid pattern codebook storage units 11 and 13 for storing a solid pattern codebook,
This is an example in which edge pattern codebook storage units 12 and 14 for storing an edge pattern codebook are separately provided.

In the case of such a configuration, since the code numbers (addresses and the like) are independently assigned to the respective codebook storage sections, the same code numbers are assigned to the solid pattern and the edge pattern. There is also. Therefore, at the time of the decompression process, the input code number is a solid pattern,
In order to identify which of the edge patterns corresponds, flag information is transmitted together with the code number. The operation in this case is shown in the flowcharts of FIGS.

In the operation on the compression side shown in FIG.
Steps S5, S6, and S8 are replaced with steps S21, S22, and S23, respectively. In step S21, when the calculated difference value for the maximum luminance value and minimum luminance value in the block is greater than the search threshold T _H, the processing of vector quantization using a code book edge pattern codebook storage unit 12 And sets the flag to “1”.

[0057] In step S22, when the calculated difference value is not greater than the search threshold T _H, performs processing of vector quantization using a code book in the solid pattern codebook storage unit 11, a flag To “0”
Set to. In step S23, the flag information set as described above is output in addition to the replaced code number.

In the operation on the decompression side shown in FIG.
Is replaced by the process of step S24, and the process of step S13 is replaced by the processes of steps S25, S26, and S27. In step S24, the above flag information is input in addition to the code number specified on the compression side. In step S25,
Determine whether the input flag is "1",
If so, proceed to step S26; otherwise, proceed to step S27.

In step S26, based on the input code number, a pattern image of the corresponding code vector is read from the edge pattern code book storage unit 14 and embedded in a corresponding block position. In step S27, the pattern image of the corresponding code vector is read from the solid pattern code book storage unit 13 based on the input code number, and is embedded in the corresponding block position.

In FIG. 6, components denoted by the same reference numerals as those shown in FIG. 1 have the same functions, and in FIGS. 7 and 8, FIGS.
Steps denoted by the same reference numerals as those described in (1) perform the same processing, and a detailed description thereof will be omitted.

As described above, in the present embodiment, when vector quantization is performed, blocks are not cut out sequentially from one image and vector quantization is performed using one codebook. Detects what kind of luminance distribution is inside the block cut out from the image,
It is determined whether the block is a solid pattern or an edge pattern of the image.

If the cut-out block is a solid pattern, a code vector having a high degree of similarity is selected from a solid pattern portion in the code book or an independently prepared solid pattern code book. On the other hand, if the cut-out block is an edge pattern, a code vector having a high degree of similarity is selected from an edge pattern portion in the codebook or an independently prepared edge pattern codebook.

As described above, in the present embodiment, each block is given a meaning in forming one image, and vector quantization is performed in accordance with the meaning. , And an optimal pattern image can be selected from the codebook corresponding to the edge at the edge portion. Therefore, when an image is reproduced using the pattern image determined in this way, a higher-quality reproduced image can be obtained.

Next, a second embodiment of the present invention will be described. As described in the background of the related art, in order to obtain a natural reproduced image suitable for human visual characteristics, especially for solid patterns, the direction of change in the luminance value of each pixel in a block is an important factor. . Then, in the case of a solid pattern, the direction of this luminance change can be predicted by looking at the pixel values at the four corners in the block.

For example, in the block shown in FIG. 9, the luminance value gradually increases from the upper right pixel to the lower left pixel in the block, or the luminance value gradually increases from the lower left pixel to the upper right pixel. Is a block of a solid pattern that becomes smaller. In this case, if only the pixel values at the four corners are known, it is possible to know in which direction the luminance value changes in the block.

Therefore, in the second embodiment, when calculating the similarity between the input vector of the block extracted from the original image and each code vector in the codebook, all the pixels ( Instead of using information of 16 dimensions), pixels at four corners (4 dimensions)
The calculation is performed using only the information of.

The configuration for realizing the data compression / decompression system according to the second embodiment is the same as the configuration shown in FIG. 1 or FIG. However, the contents of the vector quantization process performed by the codebook compression unit 4 are different from those of the first embodiment. The flowchart showing the operation is almost the same as that of the first embodiment, but the contents of the search processing in step S6 of FIG. 4 and step S22 of FIG. 7 are different from those of the first embodiment.

That is, in the first embodiment, the similarity between two vectors is obtained by calculating, for example, the Manhattan distance and the Euclidean distance using all 16 pixels in the block. On the other hand, in the second embodiment, for the solid pattern, the similarity such as the Manhattan distance is calculated using only the pixels at the four corners, and the direction of the luminance change in the block is detected. Then, a code vector having a high degree of similarity with the input vector of the original image and having the same luminance change direction is selected from the code book.

By doing so, it is possible to reliably prevent the inconvenience of selecting an unnatural pattern image whose luminance changes in the opposite direction in the block against the flow of luminance change of the entire image. Thus, it is possible to reliably select a more natural pattern image suitable for human visual characteristics. As a result, a higher-quality reproduced image can be obtained. Further, since the operation is performed only in four dimensions, the processing speed can be increased.

In the second embodiment, when performing vector quantization, an operation is performed using only information of pixels at four corners in a block, and information of other pixels is not used. Therefore, each code vector in the codebook may not be composed of 16-dimensional information as in the first embodiment, but may be composed of only 4-dimensional information corresponding to pixels at four corners. By doing so, the storage capacity of the codebook storage unit can be reduced. Further, it is possible to register more types of code vectors without changing the storage capacity, and it is possible to further improve the image quality of a reproduced image.

However, in such a case, the original image cannot be reproduced only by the pixel information at the four corners during the decompression process. Therefore, for example, for the solid pattern codebook 5a in the codebook storage unit 5 of FIG. 1, a code vector is composed of only four-dimensional information, and for the solid pattern codebook 9a in the codebook storage unit 9, 1 is set.
What is necessary is just to comprise a code vector by six-dimensional information.

The solid pattern code books 5a, 9
In both cases, the code vector may be configured using only four-dimensional information, and the information on the pixels other than the four corners may be generated from the information on the pixels at the four corners, for example, by an operation using linear interpolation. In this case, for example, an operation unit for performing the above-described operations such as the linear interpolation is provided at the subsequent stage of the codebook expansion unit 8 in FIG.

A code vector having the same luminance value at the start point and the end point but different directions of the luminance change,
For code vectors and the like in which the brightness change mode is the same but the brightness value of each pixel is different, only the representative code vector is stored in advance, and based on this, the block rotation operation and brightness inversion of the brightness value are performed. Another code vector may be generated by performing an operation (a process of turning a luminance value back at an intermediate value).

In each of the above embodiments, the size of the block is 4 × 4 pixels. However, the present invention is not limited to this. Further, in each of the above embodiments, in order to determine whether the pattern is a solid pattern or an edge pattern, whether or not the difference between the maximum luminance value and the minimum luminance value in the block is larger than a predetermined threshold value is checked. The method is not limited as long as it can be distinguished.

Further, each block may be classified into a different pattern using other information (for example, color information) instead of the luminance value, and the vector quantization may be independently performed on each block. Further, the patterns to be classified are not limited to the two types described above, and may be classified into more patterns.

Each of the functional blocks shown in FIG. 1 or FIG. 6 may be constituted by hardware in this embodiment, or may be constituted by a CPU or MPU, ROM and R
It may be constituted by a microcomputer system composed of an AM or the like, and its operation may be realized according to a work program stored in a ROM or a RAM. The present invention also includes a software program for realizing the functions described above, which is provided to a RAM so as to realize the functions of the respective functional blocks, and which is executed by operating the functional blocks according to the programs. include.

In this case, the software program itself implements the functions of the above-described embodiment.
The program itself and means for supplying the program to a computer, for example, a recording medium storing such a program constitute the present invention. As a recording medium for storing such a program, in addition to the ROM and RAM, for example, a floppy disk, hard disk, optical disk, magneto-optical disk, CD-ROM, CD-I,
CD-R, CD-RW, DVD, zip, magnetic tape,
Alternatively, a nonvolatile memory card or the like can be used.

Further, when the computer executes the supplied program, not only the functions of the above-described embodiment are realized, but also the OS (operating system) or other application software running on the computer. Needless to say, such a program is also included in the embodiment of the present invention when the functions of the above-described embodiment are realized in cooperation with the above.

Further, after the supplied program is stored in the memory provided in the function expansion board of the computer or the function expansion unit connected to the computer, the program is provided in the function expansion board or the function expansion unit based on the instruction of the program. It is needless to say that the present invention also includes a case where the CPU or the like performs part or all of the actual processing, and the processing realizes the functions of the above-described embodiments.

[0080]

As described above, according to the present invention, when performing vector quantization, a pattern is determined based on information in a block cut out from a compression target, and each pattern is determined according to the determined pattern. Vector quantization is performed using the appropriate codebook prepared in the above.For example, when compression is performed on an image, when the image is reproduced using the selected code vector, A more natural reproduced image matching the characteristics can be obtained.

According to another feature of the present invention, for a solid pattern, similarity is calculated using only information on four corners in a block, and the direction of change in the block is detected. The code vector is selected on the basis of, so that it is possible to reliably prevent the inconvenience of selecting an unnatural code vector whose data value changes in the opposite direction in the block against the flow of change of the entire image And a higher quality reproduced image can be obtained.

[Brief description of the drawings]

FIG. 1 is a block diagram illustrating a configuration example of a data compression / decompression system according to an embodiment.

FIG. 2 is a diagram for explaining an operation principle of vector quantization according to the embodiment;

FIG. 3 is a diagram showing an example of each code vector (pattern image) constituting a code book according to the embodiment;

FIG. 4 is a flowchart illustrating an example of a data compression operation according to the embodiment;

FIG. 5 is a flowchart illustrating an example of a data decompression operation according to the embodiment.

FIG. 6 is a block diagram illustrating another configuration example of the data compression / decompression system according to the present embodiment.

FIG. 7 is a flowchart illustrating another example of the data compression operation according to the present embodiment.

FIG. 8 is a flowchart illustrating another example of the data decompression operation according to the present embodiment.

FIG. 9 is a diagram for explaining a second embodiment of the present invention.

FIG. 10 is a block diagram illustrating a configuration of a conventional vector quantization device.

FIG. 11 is a diagram for explaining a conventional problem.

[Explanation of symbols]

 2 Pixel operation unit 3 Search threshold value input unit 4 Codebook compression unit 5 Codebook storage unit 5a Solid pattern codebook 5b Edge pattern codebook 8 Codebook expansion unit 9 Codebook storage unit 9a Solid pattern codebook 9b Edge pattern code Book 11 Solid pattern codebook storage unit 12 Edge pattern codebook storage unit 13 Solid pattern codebook storage unit 14 Edge pattern codebook storage unit

Continuation of the front page (72) Inventor Tatsuro Morimoto Aoba, Aramaki-ku, Aoba-ku, Sendai-shi, Miyagi (No address) Inside Tohoku University (72) Inventor Tadahiro Omi Yonegabukuro 2-1-1-17, Aoba-ku, Aoba-ku, Sendai, Miyagi 301 (72) Inventor Yuhisa Nitta 4-1-1 Hongo, Bunkyo-ku, Tokyo F-term (reference) 5C059 KK02 MD08 SS20 TA55 TC43 TD12 UA02 UA05 UA38 UA39 5J064 AA01 BA13 BC01 BC14 BC16 BC25 BD03 CA02 CB12

Claims (26)

[Claims] 1. A data sequence having at least one or more pieces of data is divided into vectors, and a code vector similar to a vector extracted from a compression target is searched from a code book prepared in advance, and a corresponding code vector is searched for. A data compression device that outputs a code to be compressed; code book storage means for storing a code book prepared for each of different types of patterns; and A discriminating means for discriminating whether the pattern is a pattern, and a vector quantizing means for executing a vector quantization process using the codebook prepared for each pattern in accordance with a discrimination result by the discriminating means. A data compression device characterized by the above-mentioned. 2. A first pattern in which a data value gradually changes in a certain direction in a block, based on a data value of each element in the block to be compressed, and a data value in the block. 2. The data compression apparatus according to claim 1, wherein the data compression apparatus determines a second pattern that rapidly changes. 3. The method according to claim 1, wherein the determining unit determines that the block is the first pattern when a difference between a maximum value and a minimum value among the elements in the block is less than a predetermined threshold.
The data compression apparatus according to claim 2, wherein the block is determined as the second pattern when a difference between a maximum value and a minimum value in the block is larger than a predetermined threshold. 4. The data compression method according to claim 1, wherein said vector quantization means obtains a similarity between the blocks of the different types of patterns by different processes. apparatus. 5. The vector quantization means according to claim 1, wherein the first pattern in which the data value of each element in the block to be compressed gradually changes is only the data value of the elements at the four corners in the rectangular block. 5. The data compression apparatus according to claim 4, wherein the similarity is obtained using the following. 6. The vector quantization means detects a direction of a data value change in a block from data values at four corners in the block, and searches for the similar code vector in consideration of this direction. The data compression apparatus according to claim 5, wherein 7. The code vector constituting the code book for the first pattern has only information of elements at four corners in the block.
A data compression device according to claim 1. 8. A data string having at least one or more data is defined as a vector, and a code vector corresponding to a compressed code is searched from a code book having at least one or more code vectors, and the code vector is searched for a corresponding block position. In a data decompression device that reproduces original data by assigning to a codebook, codebook storage means for storing a codebook prepared for each of different types of patterns, and a compression code generated by being divided into the different types of patterns on the compression side. Decoding means for searching for a code vector corresponding to the compressed code from the code book prepared for each pattern based on the data pattern. 9. The different type of pattern includes a first pattern in which the data value of each element in the block to be compressed gradually changes in a certain direction in the block, and a data pattern in which the data value changes rapidly in the block. 9. The data decompression device according to claim 8, further comprising a second pattern. 10. The code vector constituting the code book for the first pattern has only information of elements at four corners in a rectangular block.
A data decompression device according to claim 1. 11. The data decompressing apparatus according to claim 10, further comprising an operation unit for calculating information on other elements by operation based on information on elements at four corners in the block. 12. A data sequence having at least one or more data is divided into blocks to obtain a vector, and a code vector similar to a vector extracted from a compression target is searched from a code book prepared in advance, and a corresponding code vector is searched for. In the data compression method of outputting a code to be compressed, a type of data of the block is determined based on information in the block to be compressed, and a pattern is prepared for each pattern according to the determination result. A data compression method, wherein a vector quantization process is executed using a codebook. 13. The different types of patterns include a first pattern in which the data value of each element in the block to be compressed gradually changes in a certain direction in the block, and a data pattern in which the data value changes rapidly in the block. 13. The data compression method according to claim 12, further comprising: 14. When performing the vector quantization process, vector similarities are obtained by different processes for the blocks of the different types of patterns, and the block similarity is calculated for the first pattern. 14. The data compression method according to claim 13, wherein the similarity is obtained using only the data values of the four corner elements in the rectangular block. 15. The method according to claim 1, wherein a direction of a data value change in the block is detected from data values at four corners in the block, and the similar code vector is searched for in consideration of this direction. 15. The data compression method according to 14. 16. A data string having at least one or more data is defined as a vector, a code vector corresponding to a compressed code is searched from a code book having at least one or more code vectors, and the code vector is searched for a corresponding block position. In the data decompression method that reproduces the original data by assigning to the compression code, based on the compression codes generated by dividing the compression side into different types of patterns, the compression code is prepared from the codebook prepared for each pattern. A data decompression method characterized by searching for a corresponding code vector. 17. The different type of pattern includes a first pattern in which the data value of each element in the block to be compressed gradually changes in a certain direction in the block, and a data value in which the data value changes rapidly in the block. 17. The data decompression method according to claim 16, further comprising a second pattern. 18. Each code vector constituting the code book for the first pattern has only information of elements at four corners in a rectangular block, and finds a code vector corresponding to the compressed code and corresponds to the code vector. 18. The data decompression method according to claim 17, wherein, when assigning to the block position, information of other elements is calculated by calculation based on information of elements at four corners in the block. 19. A data sequence having at least one or more pieces of data is divided into a vector, and a code vector similar to a vector extracted from a compression target is searched from a prepared code book, and a corresponding code vector is searched for. And a data decompression device that retrieves a code vector corresponding to the code from the code book and assigns it to a corresponding block position to reproduce the original data. In the compression / decompression system, the data compression device includes: first codebook storage means for storing codebooks prepared for different types of patterns; and data of the block based on information in the block to be compressed. Determining means for determining which type of pattern is used, Vector quantization means for performing a vector quantization process using the codebook prepared for each pattern in accordance with the determination result by the stage, wherein the data decompression device is provided for each of different types of patterns. A second codebook storing means for storing the prepared codebook; and a codebook prepared for each pattern based on a compressed code generated by dividing the pattern into different types on the compression side. Decoding means for searching for a code vector corresponding to the compressed code. 20. The apparatus according to claim 1, wherein said first and second codebook storage means store codebooks of different types of patterns in one storage device.
10. The data compression / decompression system according to 9. 21. The first and second codebook storage means store codebooks of different types separately in a plurality of storage devices, and store the codebook in any pattern together with the code generated by the data compression device. 20. The data compression / decompression system according to claim 19, wherein information for identifying whether there is a data is supplied to said data decompression device. 22. A computer-readable recording medium on which a program for causing a computer to function as each of the means according to claim 1 is recorded. 23. A computer-readable recording medium having recorded thereon a program for causing a computer to realize the functions according to claim 2. Description: 24. A computer-readable recording medium on which a program for causing a computer to function as each of the means according to claim 8 or 11 is recorded. 25. A computer-readable recording medium storing a program for causing a computer to execute the processing procedure of the data compression method according to claim 12. 26. A computer-readable recording medium on which a program for causing a computer to execute the processing procedure of the data decompression method according to claim 16 is recorded.