JPH0577232B2 - - Google Patents

Description

[Detailed description of the invention]

-Field of Industrial Application- The present invention relates to a tone image compression method for compressing halftone image data. -Background of the Invention- A predictive coding method is known as a compression method for image data having halftones such as a film image.
In this method, a pixel value at the current point is predicted from pixel values that appeared in the past, and compression is performed by encoding a prediction error that is the difference between this predicted value and the pixel value at the current point. Taking into consideration that the distribution of prediction errors follows the Laplace distribution, we assign short codes to frequently occurring prediction errors and long codes to infrequently occur prediction errors. It is known to perform highly efficient encoding. Compression by predictive coding is reversible compression that can completely restore the original image as long as it is used alone, and the reproduced image quality does not deteriorate due to compression. However, according to statistics regarding various images, the entropy of the prediction error is about 4 bits for an 8-bit image, and even if optimal encoding is performed, it can only be compressed to about 1/2. This compression rate is hardly improved even if the prediction method is devised, and is considered to be the limit value of the predictive encoding method. On the other hand, as another encoding method, there is block encoding that utilizes human visual characteristics and the high correlation between adjacent pixels. The simplest block encoding method uses the average value of each block of n×n pixels as block information. First, as something a little more sophisticated, take the average value X _ab of the pixel density of an n×n block, take as 1-bit data whether each pixel density in the block is above or below the average value X _ab , and calculate the average value X ab. There is an encoding method that takes the average value X _ab1 of the pixel group above ab and the average value X _ABO of the pixel group below ab, and performs compression using these average values _{X ab1} and X _ab0 . In this case, the required number of bits is 8n ² →n ² +16 for an 8-bit image,
When n=4, it can be compressed to 32/128=1/4. However, in this block encoding method, since the block size is constant, the compression effect is insufficient in areas with small density changes, and conversely, in areas with large density changes, boundaries between blocks may be formed due to coding errors. This results in a decrease in image quality. Regarding this point, there is a contradictory tendency that the larger the block size is, the more the former improves and the latter becomes worse, and the smaller the block size is, the latter is improved and the former becomes worse. You won't be able to find anything that will satisfy you both. -Object of the Invention- The object of the present invention is to make it possible to achieve a high compression rate while maintaining high quality of image data having arbitrary density regions and density changes, and to make the distribution of prediction errors in predictive coding concentrate in the center. The purpose of the present invention is to provide a compression method that can improve encoding efficiency. -Structure of the Invention- The present invention collects a plurality of pixel data of image data having halftones into a block, and classifies these blocks into a plurality of modes according to the magnitude of the difference between the pixel data within the block. In a gradation image compression method that processes pixel data according to parameters specified by a mode, blocks with a small difference have a small gradation quantity and a large amount of thinning, and blocks with a large difference have a large gradation reduction amount. This paper proposes a method for compressing gradation images that is large and reduces thinning. -Embodiment- The figure is a block diagram showing an embodiment of the present invention. Image memory 1 stores images (original images) on film, etc.
Halftone image data represented by multivalued gradation of each pixel read from the image data is stored. 1 block memory 2
One block of data D cut out from the image data in the image memory 1 is stored. Block representative value memory 3 is 1 transferred to block memory 2.
The representative value D _a 1 of the block data D is stored.
The difference calculation circuit 4 calculates the difference S _a between each pixel data D _b sequentially read out from the block data D stored in the one block memory 2 and the adjacent pixel. The mode determining circuit 5 determines the mode M from the maximum value of the difference S _a determined by the difference calculating circuit 4. The gradation information reduction circuit 6 changes the gradation of the block data _Db in the 1-block memory 2 according to the mode M, and writes the changed block data _Dc into the 1-block memory 2 again. The difference calculation circuit 4 again calculates the difference S _a between the block data D _b rewritten in the one block memory 2 and the adjacent pixel. The thinning circuit 7 thins out the difference S _a from the difference calculating circuit 4 according to the degree of mode M of the mode determining circuit 5. The encoder 8 performs variable length encoding on the thinned out difference data S _b . The predictive encoding circuit 9 predictively encodes the representative value data D _a 2 stored in the block representative value memory 3.
The encoded block representative value data C _a obtained in the predictive encoding circuit 9, the encoded difference data C _b obtained in the encoder 8, and the mode M obtained in the mode determination circuit 5 are combined as compressed image data 10. taken out. Processing operations for actual image data in this configuration will be described in detail below. The image data collected in the image memory 1 is divided into one block memory 2, and one block worth of data is transferred. Here, the number of block divisions will be explained. When decomposing an image into N×N minute blocks, if N is too small or too large, the properties of the blocks cannot be accurately grasped. However, it is very difficult to accurately determine the size of N because it largely depends on the individual characteristics of the target image. Therefore, in this embodiment, N=8 is used as a number with good separation and a number that can be easily converted into hardware. By setting N=8, the block data can be further divided into 4×4 and 2×2 blocks, which has the advantage of facilitating transition to more detailed processing. Now, with N=8 set, 1 block memory 2
64 pixel data are transferred. At the same time, one pixel data is stored in the block representative value memory 3 as a representative value. This representative value may be any of the 64 pixel data, but in this embodiment, the pixel data at the upper left corner of the block data (8 x 8) is set as the block representative value, and the pixel data is stored in the block representative value memory 3. . This set of representative values is stored in the memory 3 as one file, and the size of this file is 1/64th of the original image data.
It's getting old. Additionally, this file can be made even smaller by lossless compression, and ultimately less than 1%. For block data D _b consisting of 64 pixel data transferred to block memory 2, if each pixel is named as follows: X11 X12 X13 ... X1N X21 X22 ... X31 ...・ ・ ・ ・ ・ ・ XN1 XN2 ・ ... XNN The difference calculation circuit 4 calculates the difference S _a between adjacent pixels according to the following rules. (a) Ignore the difference dX11 with respect to X11. (b) Let dXi1=Xi1-X(i-1)1. however,
2<=i<=8 (c) Let dXij=Xij−Xi(j−1). However, j
<>1 The mode determining circuit 5 that receives the set S _a of the differences dX obtained in this way selects the one with the largest absolute value of S _a , compares it with three preset thresholds, and selects the block data. Classified and stored in four modes. The correspondence between this threshold value and mode M is set, for example, as follows.

[Table] For this mode classification, classification numbers 0 to 3 are also stored in a file for each block, and this file is hereinafter referred to as a mode selection file. This mode selection file requires 2 bits for each block, so the size of the file is (1/64) x (2/8) = 1/256, and together with the representative value file, it is approximately the size of the image data. It will be 1.5%. Next, in the gradation information reduction circuit 6, the mode data of the mode M from the mode determination circuit 5 as described above.
The gradation of block data D _b in the mode M is reduced according to M0 to M3. Care must be taken in this gradation reduction to avoid creating false contours. False contours tend to occur in areas where temperature changes are gentle. Therefore, in this embodiment, the degree of gradation reduction is changed for each block while referring to the mode data M0 to M3 in the mode selection file. That is, for a small block with a mode data value of 0 to 3, it is determined that the density change is gradual, and the gradation reduction amount of the block data D _b is reduced.
Blocks with large numerical values from 0 to 3 are determined to be areas with large density changes, and the gradation reduction amount of the block data _Db is increased to increase the compression ratio while suppressing the occurrence of false contours. Specifically, in the gradation reduction process by the gradation information reduction circuit 6, the difference between adjacent pixels is a multiple of the mode data M0 to M3 numerical value 0 to 3 (gradation reduction variable) as the processed data D _c Thereafter, the value obtained by dividing the difference value between adjacent pixels by a numerical value of 0 to 3 is stored in one block memory 2 as gradation-reduced data _Dc . For example, assume that the numerical values of 4*4 block D _b are in the array as shown below. 5 6 8 10 7 7 8 10 7 9 9 12 10 13 9 3 For this data D _b , the difference from the block representative value in the upper left corner is 0 1 3 5 2 2 3 5 2 4 4 7 5 8 4 -2 . Here, if we assume gradation reduction variable 3 (M3),
This difference is changed to 0 0 3 6 3 3 3 6 3 3 3 6 6 9 3 -3. Therefore, the image data is 5 5 8 11 8 8 8 11 8 8 8 11 11 14 8 2. If you calculate the difference using the same procedure as when creating the mode selection file, the upper left corner will be 0 0 3 3 3 0 0 3 0 0 0 6 3 3 -6 -6, and this will be the gradation reduction variable 3 When divided by , the data 0 0 1 1 1 0 0 1 0 0 0 1 1 1 -2 -2 is obtained. As is clear from this data, the distribution of prediction errors (differences with adjacent pixels) is concentrated at the center (0), which increases the subsequent encoding efficiency and allows a high compression rate to be obtained. Next, the compression ratio of the gradation-reduced and difference-calculated data S _a is further improved by thinning the data by the thinning circuit 7, that is, by reducing the pixel density. If this data is thinned out using a simple method such as simply thinning out every other pixel, the reproduced image will become blurred, and the image quality will deteriorate, although not as much as the pseudo-contour. In this embodiment, thinning is performed in consideration of image characteristics, and the thinning circuit 7 performs thinning processing with varying degrees of thinning in accordance with mode data M0 to M3 from the mode determining circuit 5. In other words, when pixels are thinned out, the effect is greatest in areas where the image changes minutely, and in this case, the data difference between pixels within the block is considered to be large. , when the numerical value of mode data M0 to M3 obtained from the mode selection file is large, the thinning is reduced, and when the numerical value is small, the thinning is increased, thereby reducing the occurrence of blurring and improving the compression ratio. In addition, for thinning processing, the processing target block is
The thinning effect is further ensured by dividing the pixel data into 2, 4×4 small blocks and starting from the mode data with the representative value of the pixel data at the upper left corner or the like. In addition, pixels thinned out in the thinning process are interpolated during reproduction from compressed image data. The thinning process and interpolation method will be specifically explained below using 8×8 blocks to 4×4 blocks. First, when the 8×8 block data has the following coordinate array, X11 X12 X13 X14 X15...X15 X21...X25...X28 X31...・・・・・・X35 ・ X41・・・・・・・・・X45 ・ X51・・・・・・・・・X55 ・ ・ ・ ・ ・ ・ ・X85...X88 This block is divided into four 4x4 blocks, and the pixels X11, X51, X15,
The thinning process is performed using the value of X55 as a representative value and from the mode data of each block. Next, a method of interpolation from compressed image data that has been subjected to thinning processing will be explained. When the representative values of the above 8×8 block are extracted as compressed image data as Y11, Y21, Y12, and Y22, respectively, X11...Y12.........AIJ・・・・・・ ・・・・・・・・・・・・ X21・・・・Y22・・・ ・・・・・・・・・・ ・・・・・・・・・・ ・・・・・・... To interpolate the thinned out pixels AIJ, use the representative value
The weights of Y11, Y12, Y21, and Y22 are the reciprocal of the distance from pixel AIJ, and the distance is the sum of the difference between pixel AIJ and each representative value on the horizontal axis and the difference on the vertical axis. In other words, let the coordinates of the representative value Y11 be (N1, M2), and the pixel
If the coordinates of AIJ are (N2, M2), the distance between the two is
D11 becomes D11=(N1-N2)+(M-M2), and the weight of representative value Y11 with respect to pixel AIJ becomes 1/D11. Similarly, typical values Y12, Y21,
Find the distances D12, D21, and D22 of Y22, and use all these distances DIJ to calculate the interpolated value of pixel AIJ: AIJ = (Y11/D11+Y12/D12+Y21
/D21+Y22/D22)/(1/D11+1/D12+1/D21+1
/D22). Note that interpolation for 2×2 blocks is similarly performed, but if 4×4 blocks are adjacent, no reference data exists. To prevent this, first interpolate the 4x4 block, then
×2 block interpolation is performed. Next, the encoder 8 performs variable length encoding on the data S _b thinned out by the thinning circuit 7 according to the coding pattern. The encoding pattern at this time is shown in the table below as an example of variable length code bits for data S _b thinned out based on the difference value from the representative value after gradation reduction processing.

[Table] In this table, the F(N-2) part divides N-2 into the following ranges and encodes them.

[Table] The data C _b encoded in this way is used as a compressed data file, the data C _a from the predictive encoding circuit 9 is used as a representative value file, and the mode data M from the mode determining circuit 5 is used as a compressed data file. The selected files become compressed image data 10 as three independent files or one combined file. For example, if the above-mentioned 4*4 difference data S _b is 0 0 1 1 1 0 0 1 0 0 0 1 1 1 -2 -2 and the mode M is 1, this compressed image data 10 is as follows. It becomes a data group like this.

[Table] Based on the examples described above, compression of test images and evaluation of reproduced images were performed. Note that for the thinned out blocks, focusing only on the extracted data, and assuming that they are 2x2 or 4x4 blocks, the same gradation reduction process as in the gradation information reduction circuit 6 is performed. The resulting encoded difference between adjacent pixels was used as compressed data. At this time, the difference corresponding to the block representative value is undefined, and since this value can be reproduced from the representative value file, it is removed from the compressed data file. Then, to facilitate playback, the difference values are written to the compressed image data file in the same order as when creating the mode selection file. The following table shows the thinning conditions for performing such gradation reduction.

[Table] The compression ratio in this example is 14% in example 1 and 20% in example 2.
It became %. - Effects of the Invention - As described above, according to the present invention, the gradation information reduction process and the pixel density reduction (thinning) process of each pixel data are performed from the mode data determined according to the size of the difference between the blocked pixel data. Since compressed data is obtained by performing the above steps, efficient compression can be performed for arbitrary images while minimizing deterioration in reproduced image quality, and the encoding efficiency can also be improved.

[Brief explanation of drawings]

The drawing is a block diagram showing one embodiment of the present invention. 1... Image memory, 2... 1 block memory,
3... Block representative value memory, 4... Difference calculation circuit, 5... Mode determining circuit, 6... Gradation information reduction circuit, 7... Thinning circuit, 8... Encoder, 9...
...Predictive encoding circuit, 10...Compressed image data.

Claims (1)

[Claims] 1 Each pixel data of image data with halftones is grouped together into a block, these blocks are classified into multiple modes according to the size of the difference between the pixel data within the block, and the pixel data is specified by the mode. In a gradation image compression method that processes pixel data according to parameters, blocks with small differences have a small gradation reduction amount and large thinning, and blocks with large differences have a large gradation reduction amount and small thinning. A gradation image compression method characterized by: