JPH01878A - How to compress image data - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed Description of the Invention] (Industrial Field of Application) The present invention provides a method for compressing image data, and more specifically, a method for compressing image data, in particular, a combination of block coding and vector quantization to achieve a high data compression rate. The present invention relates to a method for compressing image data.

(Prior Art) An image signal carrying a halftone image, such as a TV signal, has a huge amount of information, so a broadband transmission path is required for its transmission. Conventionally, attention has been paid to the fact that such image signals have large redundancy, and various attempts have been made to compress image data by suppressing this redundancy. Recently, it has become common practice to record halftone images on optical disks, magnetic disks, etc., and in this case, image data compression is widely applied to efficiently record image signals on the recording medium. ing.

As one of such image data compression methods, a method using so-called block encoding is known. This image data compression method using block encoding divides the original image data carrying a two-dimensional image into blocks consisting of multiple samples, and converts the original image data regarding each pixel into n-values in each block (n is 2 or more). ), the average value m1, mz...rrBl of the original image data for each pixel in the common block from this n-valued data is calculated,
These average values ml, mz, . . . rJ and the above n-valued data are encoded.

According to this method, for example, the density scale of one pixel is 25
If we divide the original image data into 6 levels (=8 bits) every 4x4-18 pixels and then binarize the original image data, the amount of image data per block is 16x.
1 bit plus data indicating the average value m1 + mz (both may be about 8 bits), and is sufficiently compressed compared to the data ff1 (-16×8 bits) before compression.

Normally, the image data in the blocks have a high correlation with each other, so even if the above average values are applied to pixels whose n-valued data are equal to each other, the average values correspond to the original image data with low distortion. Therefore, when reconstructing an image, by applying the above average value to each pixel based on the n1ii data and reproducing the image based on this data, a reconstructed image that is not much different from the original image can be obtained. become.

(Problem to be Solved by the Invention) The image data compression method using block encoding described above does not cause much deterioration in image quality when the image has many low frequency components, so it is particularly useful for radiographic images with many low frequency components. However, it is desired to further improve the data compression rate.

SUMMARY OF THE INVENTION Therefore, an object of the present invention is to provide an image data compression method that utilizes block coding and can further increase the data compression rate than conventional techniques.

(Means and Effects for Solving the Problems) The image data compression method of the present invention is an image data compression method using block coding, in which the above-mentioned average values ml, mz... - It is characterized by vector quantizing mn and/or n-valued data.

The above vector quantization is generally applied to original image data carrying a two-dimensional image, and in that case, the two-dimensional image data is usually divided into blocks with a sample number of PXQ, and pXQ blocks are From a codebook made up of a plurality of different vectors created by specifying vector elements, select a vector that corresponds with the set of image data in each of the blocks with minimum distortion, and use this selected codebook. The information indicating the vectors in the block is encoded in correspondence with each block.

Since the image data in blocks as described above have a high correlation with each other, it is possible to represent the image data in each block fairly accurately using one of a relatively small number of prepared vectors. It becomes possible. Therefore, image data can be transmitted or recorded by transmitting or recording a code indicating this vector instead of actual data, thereby achieving data compression.

For example, the amount of image data for 64 pixels in a halftone image with a density scale of 256 levels (=8 bits) is 8 x 84"512 bits.
If a pixel is one block and each image data in the block is represented by a vector consisting of 64 elements, and a codebook is created with 258 such vectors, the amount of data per block is equal to the amount of vector identification. In other words, the data amount becomes 8 bits, and the data amount can be compressed to 1/64.

In the method of the present invention, instead of applying vector quantization as described above to original image data, the average values ml, IJ...mQ obtained by block coding are
, or applied to n-valued data. Although such average values and n-ary data are obtained through block coding, they still have a correlation with each other (that is, they have redundancy), so these data cannot be used. Data compression is achieved by further vector quantization.

As described above, in the method of the present invention, since the two techniques of block encoding and vector quantization are used together, the data compression rate can be further increased than when only block encoding is performed.

(Example) Hereinafter, the present invention will be described in detail based on an example shown in the drawings.

FIG. 1 schematically shows an apparatus for carrying out the method of the invention. Original image data S representing one continuous tone image is first passed through a block conversion circuit 9 and converted into data Sb for each rectangular block consisting of PXQ pixels. This block division is clearly shown in FIG. 2. In FIG. 2, F is the original image, and B is the block.

For ease of explanation, the density scale of each pixel is 256 levels (-8 bits), and the block B is 6 levels.
The discussion will proceed assuming that the data consists of data for X6 pixels.

The original image data sb for each block B is then input to the block encoding circuit 10J and block encoded. That is, this block encoding circuit 10 first calculates the average value So of 36 pieces of input original image data sb.
Find the average value S. The original image data sb larger than is 1
In addition, the original image data sb below the average value So is converted to O and binarized.

The resulting binary data is, for example, as shown in FIG. Next, the block encoding circuit 10 calculates the average value m1 of the original image data sb for pixels given a 0 value and the average value m2 of the original image data sb for pixels given a 1 value, respectively. The block encoding circuit IO receives the data M indicating the average value m1 + mZ obtained in this way and the binarized data X for the 36 pixels.
Output.

As mentioned earlier, such binary data X and average value m
1 + "Z represents the original image with little distortion.The amount of data of the original image data sb for 36 pixels is 5exsbit, while the above average value ml + mZ is expressed in 8bits. If expressed as follows, the binary data X and the average value m1 + mZ are 36X
It can be expressed by the amount of data of 1bit+2X8bit. In other words, by performing the above block encoding, the amount of data is 36X1b i t+2X8b i
It will be compressed to t36x8bit"!115.5.

This binary data X and average value data M are then input to the vector quantizer 11. This vector quantizer 11
corresponds to the input set of binary data X for each block (consisting of 36 pieces of data) from among the multiple vectors stored in advance as a codebook in Memo January 2 with the minimum distortion. Select the vector to In other words, memo January 2 has 36 vector elements (Xl + XZ +...X36) [n
-1, 2, ..., 16] is defined as 16 vectors 7(1), T(2), x(3)・
. . . Codebooks each indicating Y(16) are stored.

Ma(1)” (x't' + XZ + x3...
...X36), (2) = ('x+, 2), father'z
' r ”' ・・・・・・” Q 13”6) Ma(
3)-(History 7), binding) , ,,, ,,, ・,
, ,, father゛6) ma (1B) = (xl,
XZ......X36) and the vector quantizer 11 generates a set of binary data X (Xi
xZ + x3......X, 6) and vector elements (Father 1 + Q2. Father 3...... Father, 6)
The vector quantity (1) corresponding to the vector quantity <1> is determined with the minimum distortion, and encoded data Dt indicating the identification number t of the vector that defines this vector quantity <1> is output. As the above distortion, for example, is used (in this example, it is -36). To find the vector x (t) with the minimum distortion, for example, it is possible to calculate the distortion for all vectors and then find the vector x (t) with the minimum distortion. quantization) or to shorten processing time (although distortion may not be completely minimized)
Binary tree search type vector quantization may be performed.

Note that each vector element (x1 + x2 + '3...
...936) can be obtained by preparing in advance a training image of the same type as the image to be data compressed, and using a known method based on this training image.

The vector quantizer 11 also performs vector quantization on the two average values ml + mz indicated by the data M in the same manner as described above. For this purpose, in addition to the codebook mentioned above, the memory 12 contains two vector elements (ml, mz) [n-1, 2°...] as shown below.
, as an example of specifying 64 vectors, 64 vectors (1)
, m(2), m(3)---m (84)
:+ )'Hook is memorized.

ii (1) - Sieve; ゛, field ゛;
-(mx, mz) The vector quantizer 11 generates a set of mean values (ml 1 mz ) and a vector element (mt l
mz ) with the minimum distortion is found, and encoded data Du indicating the identification number U of the vector that defines this vector city (u) is output. As the above-mentioned distortion, for example, the above-mentioned mean square error is used. Further, the search for vector m(u) and the setting of the optimal codebook can be performed in the same manner as in the above case.

Here, the data compression effect obtained by implementing vector quantization as described above will be explained in detail. In this example, the identification data Dt of the vector indicating the binarized data X is 1.
It suffices if the vectors of 6 can be distinguished, so 4b
It can be expressed as it. On the other hand, the identification data DU of the vector indicating the average value m11 mz can be expressed in 6 bits as long as it can distinguish 64 vectors. On the other hand, as mentioned above, in order to directly indicate these average values "1 r mz, 2X8bit and binarized data X
Since 38X1 bit data is required to directly represent, the data compression rate by vector quantization is 4b it+6b it 2X8b it+36X1b it'! 115
．． It becomes 2. Also, the total compression rate (combining block encoding and vector quantization) is (115, 5) 15
．． It becomes 2-1/28.6.

The above-described selection of the codebook and output of the codebook identification data Dt, Du are performed for all blocks B in one image indicated by the original image data S. In this example, these vector identification data Dt and Du are recorded in the recording/reproducing device 13 on a recording medium (image file) such as an optical disk or a magnetic disk. Note that if the entire original image data S is divided into blocks in a predetermined order, the recording/reproducing device 13
Each of the identification data Dt and Du sent one after another can be recorded in correspondence with each block B. Further, in order to establish a correspondence between each identification data Dt, Du and each block B in this way, identification data Dt.

Block identification data may be added to Du and recorded. As mentioned above, these vector identification data D
Since t and Du can be expressed with an extremely smaller amount of data than the original image data X, a large amount of images can be recorded on a recording medium such as the optical disk.

During image reproduction, vector identification data Dt and Du that indirectly indicate image data are read from the recording medium and converted into reconstructed data X° and Mo in the decoder 14. That is, the decoder 14 reads the vector indicated by the input vector identification data Dt from the codebook stored in the memo 2, and calculates the vector element (=, l x., 23 ""'
436) are output as reconstructed binary data X' for one block B. Further, the decoder 14 reads the vector indicated by the input vector identification data Du from the memory 12, and converts each of the vector elements (ml + "2) defined in the vector into 1
The reconstructed average value data M for each block B is output.

These reconstructed data x', M' are used in the inverse transform circuit 15 to reconstruct image data for each block. In other words, the inverse conversion circuit 15 applies the average value m1 to pixels having a 0 value indicated by the reconstructed data X', and applies the average value m2 to pixels having a 1 value, thereby generating a reconstructed image for one block. Data Sb° is formed. As described above, such reconstructed image data Sb' corresponds to the original image data sb with only a slight distortion. This reconstructed image data Sb' is then sent to the synthesis circuit 1B, where it is converted from data in units of blocks to data for one image. The image data S° after undergoing this conversion is approximately equal to the original image data S with only a slight distortion, and is finally sent to the image reproduction device 17. In this image reproducing device 17, an image substantially equivalent to the original image carried by the original image data S is reproduced based on the image data S°.

In the embodiments described above, the original image data of each block B is binarized, but the original image data may be classified into ternary or higher classes.

Further, in the above embodiment, both the average value ml r m2 obtained by block encoding and the binary data X are vector quantized, but the n-ary data and the n average values Only one of them may be vector quantized. However, in order to increase the data compression rate, n
It is more preferable to vector quantize both the value data and the n average values.

Furthermore, in the above embodiment, when performing block encoding, two-dimensional image data is divided into blocks for each data about a rectangular range consisting of adjacent pXQ pixels, but the shape of the pixel range extracted for this block division is The shape is not limited to a rectangle, but may be shaped as shown in FIGS. 4.5 and 6, for example. In these figures, each square represents one pixel, and the portion surrounded by solid lines represents the pixel range extracted for block division. In the example of FIG. 6, small blocks Z1, Z2, Z3, and z4 that are separated from each other are combined into one block.

In this way, in the present invention, the pixels extracted as one block do not necessarily have to be all adjacent, but only as long as they are close to each other. It shall be called. Section 4.5 above
As shown in Figure 6, if the ranges of block division are intertwined with each other, block distortion (differences in density at block boundaries) will occur in the reconstructed image, compared to the case where pixels in a rectangular range are extracted and divided into blocks. This has the effect of making it less noticeable.

(Effects of the Invention) As explained in detail above, according to the image data compression method of the present invention, even more data compression is achieved compared to the conventional image data compression method using block encoding.
In particular, when recording high-gradation medical images, etc., the amount of images that can be recorded on a recording medium is greatly increased, and when applied to image transmission, it is possible to significantly reduce the data transmission path and shorten the transmission time. Effects can be obtained.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing a schematic configuration of an apparatus that implements the method of the present invention, FIG. 2 is an explanatory diagram illustrating the division of image data into blocks according to the present invention, and FIG. 3 is a block diagram showing the block coding according to the present invention. Schematic diagram showing an example of binarized data. Figures 4.5 and 6 are explanatory diagrams each showing another example of dividing image data into blocks in the present invention. 9...Block conversion circuit lO...Block encoding circuit 11...Vector quantizer 12...Memory (codebook) 13...Recording/reproducing device 14...Decoder 15...Reverse Conversion circuit 1B...Composition circuit 17...Image reproduction device Di, Du...Vector identification data M...Average value data M'...Reconstruction average value data sb...Original image for each block Data Sb°...Reconstructed data for each block X...Binarized data Xo...Reconstructed binary data

Claims (1)

[Claims] Original image data carrying a two-dimensional image is divided into blocks each consisting of a plurality of samples, and in each block, the original image data regarding each pixel is converted into n-values (n is an integer of 2 or more), and this n Average values m_1, m_2...m of original image data for each pixel in a block that has common value data
Find _n, and calculate these average values m_1, m_2...m_n,
In the image data compression method for encoding the n-ary data, the average values m_1, m_2, etc. for each block are provided.
An image data compression method characterized by vector quantizing m_n and/or n-valued data.