JPH01879A - Image data compression device using vector quantization - 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] (Field of Industrial Application) The present invention provides a method for compressing image data, in particular, a method for compressing image data, in particular, a combination of vector quantization and orthogonal transform coding 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 vector quantization is known.

This vector quantization method divides two-dimensional image data into blocks each containing data related to pixels that are close to each other, and creates a codebook consisting of a plurality of t-th different vectors that are created by defining vector elements in advance. In this method, vectors corresponding to the set of image data in each of the blocks with minimum distortion are selected, and information indicating the selected vectors is encoded in correspondence with each block. It is.

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 64 = 512 bits.
If you create a codebook with 256 such vectors, the amount of data per block will be 8 bits, which is the amount of data for vector identification, and the amount of data will be compressed to 1/64. It becomes possible.

After the image data is compressed and recorded or transmitted as described above, the vector elements of the vector indicated by the vector identification information are used as reconstructed data for each block, and by using this reconstructed data, the original image is reproduced.

(Issue 8 to be solved by the invention) The image data compression method using vector quantization described above has been effective in, for example, transmitting TV signals, but recently it has been used for extremely high-gradation images such as medical radiation images. So-called electronic image files, which are recorded on the above-mentioned optical disk or the like, are attracting attention, and more efficient image data compression is desired in such fields.

SUMMARY OF THE INVENTION It is an object of the present invention to provide an image data compression method that uses the vector quantization technique described above and can further increase the compression rate than conventional techniques.

(Means and effects for solving the problem) The image data compression method according to the present invention aims to improve the data compression rate by combining the vector quantization described above with orthogonal transform coding. , the larger the distortion of each vector in the codebook with respect to a predetermined vector, the larger or smaller the distortion becomes. Adjacent blocks B1 are grouped together and divided into blocks B2 for each sample number J, orthogonal transformation is applied to the above set data for each block Bz, and the transformed data obtained by this transformation is converted to a unique code length. It is characterized by encoding.

Top GC! Orthogonal transform encoding is usually applied to original image data for data compression. In that case, orthogonal transform encoding divides the two-dimensional image data into blocks with an appropriate number of obstacles, and orthogonally transforms the numerical sequence consisting of sample values for each block.This transformation concentrates energy on specific components. Therefore, components with high energy are encoded (quantized) by assigning a long code length, while components with low energy are roughly encoded with a short code length, thereby reducing the number of codes per block. . The above-mentioned orthogonal transformation is Fourier (Fourier)
) transformation, Cosine transformation, Hadamard (
) (ad, amard) conversion, Karunen-Lebe (K
a rhunen-Lo? ve) conversion, Baal (Haa
r) transformation etc. are often used, and the above method will be explained in more detail using Hadamard transformation as an example. First, as shown in FIG. 2, digital two-dimensional image data is divided into two blocks in a predetermined one-dimensional direction to form the blocks. Two sample values x in this block
When (0) and
(1) -x (0) Most of them are distributed near the straight line. Therefore, the second orthogonal coordinate system is transformed by 45° as shown in Figure 3 to determine the new y (0) - y (1) locus (head thread). In this coordinate system, y (0) is the original original before transformation. It indicates the low frequency component of the image data, and the y
(0) takes a slightly larger value (approximately 71 times) than x (0) and x (1), but on the other hand, y (1), which indicates the high frequency component of the original image data, is close to the y (0) axis. It will be distributed only in a very narrow range. So, for example, the above x
If a code length of 7 bits is required to encode each of (0) and Encoding can be performed with a code length of about 4 bits, which ultimately reduces the code length per block.
Image data compression is achieved.

Above, we have explained the second-order orthogonal transformation that constitutes one block for each two pieces of image data, but as the order increases, the tendency for energy to concentrate on a specific component becomes stronger, increasing the effect of reducing the number of bits. Can be done. In general, the above transformation can be performed using an orthogonal function matrix, and in the extreme, if the eigenfunction of the target image is selected as the orthogonal function matrix, the transformed image becomes its eigenvalue matrix, and the pair of matrices This means that the original image can be expressed using only the angular components. Also, in the above example, the image data is grouped into a block in one dimension only, but this block may be composed of several pieces of image data spanning two dimensions; in that case, one dimension orthogonal A more remarkable effect of reducing the number of bits can be obtained than in the case of conversion.

The transformation data obtained by the above-mentioned two-dimensional orthogonal transformation is based on the sequence (0
(the number that crosses the line). Since this sequence corresponds to the spatial frequency, each converted data is arranged in frequency order in the vertical and horizontal directions, as shown in FIG. Therefore, a relatively long code length is assigned to the transformed data that carries the low frequency component (the data on the upper left side of Figure 4). ), a relatively short code length is assigned to the converted data that carries high frequency components (the data on the lower right side of Figure 4), or
Alternatively, the code length per block is reduced by truncating.

In the method of the present invention, the above-described orthogonal transform encoding is not applied to the original image data, but is applied to the data with the number indicating the vector selected by vector quantization. By defining the numbers as described above, data compression can be achieved. That is, if vector numbers are defined as described above, the numbers of vectors become closer as the distortions of the defined vectors become smaller. On the other hand, the original image data has a high correlation between nearby pixels within block Bl, but when considering the block 81,
In this case as well, blocks that are close to each other have a high correlation among the entire image data. Therefore, the vectors selected for each block B1 have a high correlation between blocks Bl that are close to each other, and eventually the correlation between the vector numbers becomes high, so which vector number should be orthogonally transformed encoded? The code length required to indicate this will be reduced.

(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 IO and converted into data X for each rectangular block consisting of MXN adjacent pixels. This block division is clearly shown in FIG. 5. In FIG. 5, F is the original image and B1 is the block. For ease of explanation, the following discussion will proceed on the assumption that the block B described above consists of data for 6×6 pixels.

The original image data X for each block B1 is then input to the vector quantizer 11. This vector quantizer 11
selects a vector corresponding to the set of input original image data X for each block (consisting of 36 pieces of data) with minimum distortion from among a plurality of vectors stored in advance in the memory 12 as a codebook. select. i.e. memory 1
2 has 36 vector elements (Xl, X2゜...X36) [n-1, 2, .
..., 256] as an example of specifying 256.
The vector ma(1), x(2), ? (3)...
. . . A code book indicating ma(25B>) is stored.

T(1)=(52++), 9T, 2L
: +++++ M (IA) Ma (2) - (shoulder゛, core゛,
・・・・・・・・・・・・9゛3′ima(3)−(father゛r°, Ωf%3.・・・・・・・・・・・・Ship 3wama(
25B) −('12':'ゝ, 9゛7ζ...
・・・・・・g(:′:).

Then, the vector quantizer 11 operates on a set of original image data X (X
l + X2 + x3・・・・・・X36
) and vector elements (=, +; 2+93...
- 936) determines the corresponding vector ma(m) with the minimum distortion, and outputs encoded data DIIl indicating the identification number m of the vector that defines this vector ma(m). As the above-mentioned distortion, for example, a mean squared error is used (in this example, it is -38). Which vector minimizes this kind of distortion? To find (m), for example, it is possible to calculate this distortion for all vectors and then find the vector ma(m) that minimizes the distortion (so-called exhaustive search vector quantization), or to shorten processing time. (although the distortion may not be completely minimized)2
An advanced tree search type vector quantization may also be performed.

In this example, vector f(2) less than or equal to vector ma(1)
, Ma(3) . . . Ma(25B) are arranged in descending order of distortion from vector Ma(1). In other words, for example, a vector with identification number m? The distortion of vector x(m+1) between vector x(m) and identification number (m+1) is smaller than the distortion of vector x(m+2) between vector x(m) and identification number (m+2). This distortion may be defined by, for example, the above-mentioned mean square error.

Note that each vector element (Xi, X2, X3...
The optimal codebook consisting of vectors that define the data compression method can be obtained by preparing in advance a training image of the same type as the image for which data compression is to be performed, and using a known method based on this training image.

In this example, the vector identification data Dm described above can be expressed in 8 bits as long as 256 vectors can be distinguished. Therefore, in this case, if the density scale of each pixel is 256 levels - 8 bits, then 8 bits x 36
Since the image data of (pixel) can be represented by 8 bits, the data compression ratio is 1/36.

Vector selection and vector identification data Dn+ described above
The output is performed for all blocks B1 in one image indicated by the original image data S.

The distribution state of vector identification numbers indicated by this vector identification data Dew is as shown in FIG. 6, for example, for one image. That is, in this example, one vector identification number is determined for every 6x6-36 pixels. As described above, these vector identification numbers have a high correlation among blocks BI that are close to each other. Data Dffl indicating such a vector identification number is input to the orthogonal transform circuit 13 as shown in FIG. This data Dl
In the orthogonal transformation circuit 13, u undergoes two-dimensional orthogonal transformation, for example. This two-dimensional orthogonal transformation transforms adjacent pXQ blocks B1 into one block B, as shown in FIG.
2, it is performed for each block B2. Note that FIG. 6 shows an example in which a 3×3-9 block B1 is used as one block B2.

As this orthogonal transformation, for example, the aforementioned Hadamard transformation is used. Since the Hadamard transform has a transform matrix consisting of only +1 and -1, it can be executed by a simpler transform circuit compared to other orthogonal transforms. Furthermore, as is well known, two-dimensional orthogonal transformation can be reduced to one-dimensional orthogonal transformation. In other words, PXQ in the above two-dimensional block B2
A one-dimensional orthogonal transformation is applied to the codebook identification data Dm in the vertical direction, and a two-dimensional orthogonal transformation is performed by applying a one-dimensional orthogonal transformation in the horizontal direction to the obtained PXQ transformed data. will be carried out. Note that the order of vertical and horizontal conversion may be reversed.

Transformed data Ym obtained by the above two-dimensional orthogonal transformation
In each block B2, the function that is the basis of the orthogonal transformation (for example, the Walsh function in the case of Hadamard transform,
In Fourier transform, they are arranged vertically and horizontally in the sequential order of trigonometric functions, etc.

The transformed data YIIl arranged in this way is sent to a known encoding circuit 14 and encoded (quantized) as shown in FIG. Since the energy components are concentrated, the necessary bits in block B2 are given relatively long code lengths to the components with high energy, while components with low energy are given relatively short code lengths or are truncated. number is reduced and data compression is achieved.

The data f (m) indicating the encoded vector identification number is stored in the recording/reproducing device 15 on a recording medium (image file) such as an optical disk or a magnetic disk.
recorded in As mentioned above, this data f (m) has been significantly compressed with respect to the original image data S by vector quantization and orthogonal transform encoding, so a large amount of images can be recorded on a recording medium such as an optical disk. It becomes wet.

During image reproduction, the data f(m) is read out from the recording medium, and converted into the converted data YII in the decoder 1B.
It is decoded to l. This conversion data Ym is supplied to the inverse conversion circuit 17
and undergoes an inverse transformation to the two-dimensional orthogonal transformation. As a result, data Dra indicating the vector identification number is restored. This vector identification data Dm, which indirectly indicates image data, is converted into reconstructed data X' in the decoder 18.

That is, the decoder 18 reads the vector indicated by the input vector identification data Da+ from the codebook stored in the memory 12, and calculates the vector elements (xl, X2 + X3... 36) as reconstructed data X° regarding one block B1.

This reconstructed data X° is sent to the synthesis circuit 19, where it is converted from data for each block 81 to data for one image. The image data S' after undergoing this conversion has only a slight distortion with respect to the original image data S,
are almost the same, and finally the image reproducing device 2
Sent to 0. In this image reproducing device 20, the above-mentioned image data S.

Based on this, an image substantially equivalent to the original image carried by the original image data S is reproduced.

In addition, in the embodiment described above, the vector quantity (1
) for the vectors arranged in descending order of distortion.
3.4... A vector identification number of 256 is set, but if a certain predetermined vector quantity is given an identification number of 256 and set to T (256), then the vector quantity (25B
) may be sequentially set with vector identification numbers of 255.254.253...3.2.1 for each vector arranged in descending order of distortion. Further, the predetermined vector that serves as a standard for assigning an identification number to each vector quantity and arranging them may be a vector that is not specified in the codebook.

Furthermore, in the above embodiment, when performing vector quantization, the two-dimensional image data is divided into blocks for each rectangular range of data consisting of adjacent MXN 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. 7 and 8, 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. As shown in Figures 7 and 8, if the ranges of block division are intertwined with each other, block distortion (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 i) making it less noticeable that density steps (occurrence) are 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 vector quantization.
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. You can get some effect.

[Brief explanation of the drawing]

Fig. 1 is a block diagram showing a schematic configuration of an apparatus for carrying out the method of the present invention, Figs. 2.3 and 4 are explanatory diagrams explaining orthogonal transformation according to the present invention, and Fig. 5 is an image data according to the present invention. FIG. 6 is an explanatory diagram illustrating the division of vector identification data into blocks according to the present invention, and FIGS. 7 and 8 each illustrate another example of the division of image data into blocks according to the present invention. FIG. DESCRIPTION OF SYMBOLS 10... Block transformation circuit 11... Vector quantizer 12... Memory (codebook) 13... Orthogonal transformation circuit 14... Encoding circuit 15...
Recording and reproducing device 16.18...Decoder 17.
... Inverse conversion circuit 19 ... Synthesis circuit 20.
...Image reproduction device Dm...Vector identification data f (m)...Orthogonal transform encoded vector identification data X...Original image data X゛...Reconstructed data Fig. 2 Fig. 3 x (1) Figure 4 yn M, Nl

Claims (1)

[Scope of Claims] Two-dimensional image data is divided into blocks B_1 each containing data related to K pixels that are close to each other, and in a codebook consisting of a plurality of different vectors created by defining K vector elements in advance. Then, a vector corresponding to the set of image data in each of the blocks B_1 with the minimum distortion is selected, and a number indicating the selected vector is encoded in correspondence with each block. Image data is obtained by vector quantization. In the compression method, the number is defined to be larger or smaller as the distortion of each vector in the codebook with respect to a predetermined vector is larger, and the aggregate data of the number selected for each block B_1 is Number of samples J for adjacent blocks B_1
Vector quantization characterized by dividing the set data into each block B_2, applying orthogonal transformation to the set data for each block B_2, and encoding the transformed data obtained by this transformation with each unique code length. Image data compression method.