JPH0578230B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION (Field of Industrial Application) The present invention relates to an image data compression method for reducing the amount of image information by compressing image data having gradations for each pixel block.

(Prior Art) Generally, in an image processing apparatus such as a plate-making scanner, image data is obtained for each pixel, which is a certain minute area, by reading an original image. The amount of image data in the printing field is larger than that of television, and each image has a large amount of data.
The amount of information reaches from MB to several tens of MB. Storing such a large amount of data as it is as a database requires a huge amount of memory, and the cost of data transmission is also large.

To deal with this, encoding techniques that reduce the amount of information in images, ie, image data compression techniques, are generally used.

(Problem to be Solved by the Invention) Various image data compression techniques are known, such as those using orthogonal transformation, but most of them are aimed at images with coarse image quality for television etc. It was. Therefore, there is a problem in that if the quality of the reproduced image is improved, the compression ratio cannot be increased.

(Purpose of the Invention) The present invention was made to solve the above-mentioned problems in the prior art, and its purpose is to provide an image data compression method that can increase the compression rate without impairing image quality. do.

(Means for Achieving the Object) In order to achieve the above object, the present invention provides an image data compression method for obtaining compressed image data for each of a plurality of pixel blocks that divide an image. By orthogonally transforming the image data obtained in advance for each pixel block, a transform coefficient table consisting of a plurality of transform coefficients representing the image data in the pixel block is obtained, and (b)
A plurality of different code tables are prepared in advance that designate part of the conversion coefficients of the conversion coefficient table as valid, and each coefficient value and each code of the conversion coefficient table corresponding to the pixel block are prepared in advance. Based on the result of calculation using the table values, one code table suitable for the conversion coefficient table of the pixel block is selected as the optimal code table, and (c) the conversion is performed while referring to the optimal code table. Compressed image data is obtained by extracting the coefficient values.

In order to achieve the above objective, the plurality of code tables are classified into a plurality of code table groups, and the plurality of code tables are divided into groups based on statistics representing the distribution state of image data within the pixel block. Depending on the situation, a selection is made from among a plurality of code table groups.

(Operation) Among the transform coefficients representing the image data in the pixel block, only the transform coefficients designated by the selected optimal code table are extracted, and the other transform coefficients are ignored. Therefore, the number of transform coefficients that are the basis for obtaining compressed image data is reduced.

In addition, multiple code tables are classified into code table groups, and the code table group is limited to one based on the image data statistics (standard deviation, etc.), which is the basis for selecting the optimal code table. , a code table group having a configuration corresponding to the above-mentioned statistics can be selected as appropriate.

(Example) A. Basic Concept FIG. 7 is a conceptual diagram showing an example of blocking an image. Image 1 is composed of (X×Y) pixels P, and is divided into (V×H) pixel blocks _Bvh each having a plurality of pixels. FIG. 8 is a conceptual diagram showing the structure of one pixel block _Bvh . Pixel block B _vh is (M×N) pixels
P _ij , and image data f _ij for each pixel
is obtained. In the example in Figure 8, the pixel block
B _vh is composed of (8×8) pixels, but (4
×4) pixels or (16×16) pixels may be used.

When compressing data, first, orthogonal transformation is performed on the image data for each pixel block _Bvh in image 1. Various methods such as discrete Fourier transform and Hadamard transform can be used as the orthogonal transform, but here, the discrete cosine transform (hereinafter referred to as "DCT transform") shown by the following equation is used.

F _no = 4/M×NC _noM-1 〓 ⁱ⁼⁰ _N-1 〓 〓 ^j=0 f _ij ×cos (2i+1) mπ/2Mcos (2j+1) nπ/2N…
...(1) However, C _no = 1/4: m = n = 0 1/2: m・n = 0 (excluding the case where m = n = 0) 1: m・n≠0 In Figure 9, FIG. 2 is an explanatory diagram showing image data f _ij within one pixel block and a conversion coefficient F _no obtained by equation (1). Hereinafter, the table indicating the conversion coefficient F _no will be referred to as a "transformation coefficient table FT." The conversion coefficient F ₀₀ indicates the average value of the image data f _ij (hereinafter referred to as "DC component"), and the other conversion coefficients F _no
(hereinafter referred to as "AC component") indicates the distribution state of image data, and each is a value expressed by, for example, an 8-bit binary number. However, in FIG. 9, the numbers are shown in decimal numbers for convenience.

Image data f _ij in Figures 9 (a-1) and (b-1)
and the corresponding figures (a-1) and (b-
As can be seen from the transformation coefficient F _no in 1), the transformation coefficient F _no may change to 0 depending on the distribution of the image data f _ij .
The positions (m, n) with values that are different from each other and the magnitudes of those values are quite different. Here, the conversion coefficient F _no with a large absolute value is a component that best represents the characteristics of the distribution state of the original image data f _ij , and the number of conversion coefficients F _no with a large absolute value is the component that represents the characteristic of the distribution state of the original image data f _ij It tends to increase as the spatial variation of is large.

In this invention, attention is paid to the bias in the distribution of the conversion coefficient F _no as described above, and a code table is used that specifies only a part of the AC component as valid. FIG. 10 is an explanatory diagram showing an example of a code table. The coordinates (m, n) for which the effective number of bits I _no is given in the code table CT are the corresponding positions (m,
Indicates that the conversion coefficient F _no of n) is designated as valid. Further, each effective bit number I _no is the maximum number of bits when representing the conversion coefficient F _no . In other words, the conversion coefficient up to the maximum effective value F _nax (=(2 to the power of I _no ) - 1)
The value of F _no is considered valid as is. In the figure, "-" indicates that the number of effective bits is "0". This effective number of bits I _no may all be the same value (e.g. 8 bits), but it is smaller than the number of bits (8 bits) of the original conversion coefficient F _no and may be a different value for each coordinate (m, n). value (e.g. 6 bits,
3 bits, etc.) has the advantage of increasing the compression ratio when compressed image data is obtained later. Note that the value of the conversion coefficient F _no is the maximum effective value F _nax
, then the conversion coefficient F _no is considered to be equal to the maximum effective value F _nax . Effective number of bits I _no
is determined empirically to prevent this from happening, and if the conversion coefficient F _no is the maximum effective value
Even if it is equal to F _nax , its effect can be ignored.

A plurality of such code tables CT having different positions and value patterns of the effective bit number I _no are prepared in advance. These patterns of the effective number of bits I _no of the code table CT are empirically determined so that higher quality images can be reproduced with fewer conversion coefficients. For example, the pattern is set based on a pattern that appears frequently from among typical patterns such as people, landscapes, and still lifes.

Next, for the transform coefficient table FT obtained for each pixel block _Bvh , the optimum code table is selected from among the plurality of code tables CT. For this selection, the sum of effective conversion coefficients (hereinafter also referred to as "effective sum") S _F is calculated using the following equation.

S _F = _M-1 〓 ^m=0 _N-1 〓 ⁿ⁼⁰ C _no | F _no | ...(2) However, C _no = 1: I _no ≠ 0 0: I _no = 0 And each code table Effective sum S _F for each CT
The code table CT for which this value is the largest is determined to be the optimal code table.

Note that if the number of effective conversion coefficients F _no (hereinafter referred to as the "number of effective AC components") N _c is the same for each code table CT, the optimal code table can be selected using the above effective sum S _F. becomes more reliable.

Compressed image data is created based on the average value of the original image data f _ij , the table number of the selected optimal code table CT, and the value of the conversion coefficient F _no specified as valid in the code table CT. be done. The number of effective AC components N _c is much smaller than the total number (M x N) of conversion coefficients F _no in the original conversion coefficient table, and the value of each conversion coefficient F _no has fewer effective bits. Since it is expressed by the number I _no , the compression ratio is extremely large. In addition,
Compressed image data is the well-known Huffman
The compression rate can be further increased by encoding with a code or the like.

Next, in order to further increase the compression rate according to the characteristics of the image, we adopt a method of dividing the code table CT into multiple groups. For this purpose, first, the standard deviation σ of the image data f _ij is determined for each pixel block B _vh . Then, the code table is divided into a plurality of groups (code table groups) as shown below according to the size of the standard deviation σ.

Group 1: CT ₁₁ to CT ₁₁ when σ<σ ₁ Group 2: CT ₂₁ to CT ₂₁ when σ ₁ ≦σ<σ ₂ Group 3: CT ₃₁ to CT _3L when σ ₂ =≦σ<σ ₃ 4: When σ ₃ ≦ σ, CT ₄₁ to CT _4L (However, σ ₁ , σ ₂ , and σ ₃ are predetermined threshold values.) Note that the number L of code tables in each group 1 to 4 is a different value. Needless to say, it's a good thing.

FIG. 11 is a diagram showing the distribution G of the number of appearances A in the entire image 1 with respect to the standard deviation σ determined for each pixel block B _vh of the image 1. In the figure, the number of occurrences A on the vertical axis is shown on a logarithmic scale.

The first threshold σ ₁ is determined as a value below which the change in the image within the pixel block is small when the standard deviation σ is smaller. Since the value of the alternating current component of the conversion coefficient of such a pixel block is small, even if a code table having a small number of effective alternating current components N _c is used, the image quality will not be degraded. Also,
As can be seen from Figure 11, the standard deviation σ
The appearance rate A of pixel blocks with extremely _small
If expressed as a code table, the effect of increasing the compression ratio is significant.

When the standard deviation σ is between the first threshold σ ₁ and the second threshold σ ₂ , it indicates that the image changes gradually within that pixel block. In this case, in order to maintain good image quality, it is better to use a code table having a larger number of effective AC components N _c than Group 1. Since this group 2 also has a relatively high appearance rate A, the effect of improving the compression ratio is also high.

The appearance rate A is relatively low for a standard deviation σ greater than or equal to the second threshold σ ₂ , but if all of these are processed using a code table with a large number of effective AC components N _c , this will cause a decrease in the compression ratio. becomes. Therefore, a third threshold value σ ₃ is determined as an intermediate value.

Code table CT for each group 1 to 4 _1k ~
The number of effective AC components N _c1 to N _c4 of CT _4k (k=1 to L) has the following relationship.

0≦N _c1 ≦N _c2 ≦N _c3 ≦N _c4 ≦M×N−1 (3) Note that within each group, the number of effective AC components of the code table is constant. Also, when N _c1 = 0, the pixel block that belongs to group 1
The compressed image data of B _vh is represented only by the average value of the pixel data f _ij .

The threshold values σ ₁ to σ ₃ and the grouped code table groups CT _1h to CT _4k are prepared in advance, and the code of the corresponding group is determined based on the value of the standard deviation σ of the pixel block B _vh . By selecting the optimal code table from a group of tables, the compression ratio can be greatly increased.

B. Schematic Configuration and Operation of Apparatus FIG. 1 is a schematic configuration diagram showing an image data compression apparatus that compresses image data by applying an embodiment of the present invention. In the figure, the image data compression device
The AP includes an image memory 5, a pixel block readout controller 6, a buffer memory 7, a two-dimensional DCT converter 8, a linear quantizer 9, an encoder 10, an encoded data recording controller 11, and a standard deviation calculator 14. , a threshold comparator 15, a ROM 17, and a controller 13. The operation of this image data compression apparatus AP will be explained below with reference to the flowchart shown in FIG.

In step S1, the standard deviation thresholds σ ₁ to _{σ 3} are inputted from the parameter input terminal 16 and applied to the threshold comparator 15. Steps S2 to S4 and S11
-S13 are steps for sequentially selecting pixel blocks _Bvh to be processed.

In step S5, the image data _fij in one pixel block _Bvh is read out by the pixel block readout controller 6.
The image data is read out from the image memory 5 and stored in the buffer memory 7. In step S6,
The image data f _ij is provided from the buffer memory 7 to the standard deviation calculator 14 to calculate the standard deviation σ,
At the same time, it is transmitted to the two-dimensional DCT converter 8 and subjected to DCT conversion (step S7). In step S8, the transform coefficient F _no is linearly quantized. Linear quantization, as is generally known, is when the transformation coefficient F _no is divided by a predetermined value α (this is called the "quantum width"), and the value F _no /α is a decimal number. This means converting this into an integer. The value of the quantum width α is the standard deviation σ
The details will be omitted. In step S9, linearly quantized transform coefficients are
For the transform coefficient table FT ^* with F _no ^* , the optimal code table is selected.

FIG. 3 is a flowchart showing a method for selecting an optimal code table. The meaning of each symbol in the diagram is as follows.

max: Parameter for finding the maximum value of the effective sum S _F Max: Parameter indicating the number of the code table that is the maximum of the effective sum S _F l: Parameter indicating the code table number L: Number of code tables c: Effective AC Parameter N _c indicating the number of components: number of effective AC components First, in step S21, it is determined which of groups 1 to 4 the standard deviation σ corresponds to. Steps S22 to S30 are steps for selecting the one with the largest effective sum S _F (see equation (2)) among the L code tables of the group.

In steps S23 to S26 for calculating the effective sum S _F ,
A sub-table T as shown in FIG. 4 stored in the ROM 17 is used. Sub table T
is the code table CT _gl in one group g
~CT For each _gL , the coordinate values of the coordinate positions where the value of the effective bit number I _no is not “0” (m _lc , n _lc )
Only shown. Here, l=0~(L-1),
c=0 to (N _c -1). For one code table CT _gl , the coordinates (m _lc , n _lc ) are called one after another from the sub-table T, and the conversion coefficient table is
Of the conversion coefficients F _no ^* of FT ^* , only the absolute values of those at the above coordinates are added up in step S24.

The code table with the maximum effective sum S _F is selected as the optimal code table. Step S31
Then, the table number Max of the optimal code table is
Conversion coefficients specified as valid in the optimal code table
F _no ^* is converted into a Huffman code string to obtain compressed image data (steps S31 and S10). Note that the average value of the original image data f _ij may be Huffman encoded at the same time, but apart from step S31, only the average value may be encoded by a method such as so-called predictive encoding. .

The compressed image data (encoded data) thus obtained is transmitted to the encoded data recording controller 11 and further output to the image memory 5 or a transmission line 12 to an external circuit (not shown). This output selection command is input to the parameter input terminal 16 by the operator prior to compressing the image data, and is initialized in the encoded data recording controller 11.

FIG. 5 shows encoded compressed image data D _f
FIG. 2 is a conceptual diagram showing the file structure of . The header 18 in FIG. 5a includes threshold values σ ₁ , σ ₂ , σ _{3 ,} etc. Following the header 18, code strings of each pixel block are sequentially arranged. Moreover, FIG. 5b shows the internal structure of the code string 19 of each pixel block,
It consists of the table number Max of the optimal code table and the code string of the conversion coefficient F _no ^* .

FIG. 6 is a schematic configuration diagram showing an image data decoding device that decodes encoded compressed image data D _f . The image data decoding device IAP includes an image memory 20, a readout controller 22, a buffer memory 23, a decoder 24, a ROM 25, an inverse quantizer 26, a two-dimensional DCT inverse transformer 27, and a recording controller 28. has been done. Compressed image data
D _f is read out from the image memory 20 or the transmitter 21 by the readout controller 22, and the buffer
The signal is applied to a memory 23 and further transmitted to a decoder 24. The ROM 25 stores the same code table used for encoding image data, a Huffman code table for decoding Huffman code strings, and the like. Compressed image data D _f is sent to decoder 2
4 to transform coefficient F _no ^* . The transform coefficient F _no ^* is dequantized by a dequantizer 26 . That is, the transformation coefficient linearly quantized with quantum width α
F _no ^* (=F _no /α) is multiplied by the quantum width α. The transformation coefficient F _no obtained in this way is the two-dimensional DCT
The data is inversely transformed by an inverse transformer 27, and image data f _ij for each pixel within the pixel block is obtained. image data
f _ij is recorded in the image memory 20 by the recording controller 28. If the above decoding process is performed for all pixel blocks, image data f _ij of the entire image will be obtained.

C. Modification In the above embodiment, the code table is classified into a plurality of code table groups based on the standard deviation of image data within a pixel block, but the code table is not limited to the standard deviation.
Classification may be performed using other statistics indicating the distribution state of image data.

Further, although the above embodiment has described a method of compressing image data for one image, it goes without saying that the present invention may be applied to each color-separated image in the case of a color image. For example, YMCK print images, RGB signal images, _Ys・
For _Is / _Qs signal (chroma signal) images, image data can be compressed for each color separation image. In this case, for each color separation image, the number of standard deviation thresholds and their values, the number of code tables in each code table group, the number of effective AC components of the code table, the pattern of the effective number of bits of the code table, etc. By changing , compression suitable for each color separated image is possible.

(Effects of the Invention) As explained above, according to the present invention, image data is compressed using only some of the transform coefficients that represent the characteristics of the image data, out of a plurality of transform coefficients obtained by orthogonally transforming the image data. Since converted image data is obtained, there is an effect that the compression rate can be increased without deteriorating the image quality.

Also, JP-A-62-216484 and JP-A-63-
109663, in which transform coefficients for all pixel blocks obtained after orthogonal transformation are classified by frequency component, and data encoding rules are determined for each frequency component. In the invention, data compression rules can be appropriately selected for each image block. For this reason,
Optimum and efficient data compression has become possible for each part of the original image individually.

Furthermore, the present invention is configured to prepare a plurality of code tables in advance and select and use an appropriate one from among them, so there is no need to construct compression rules from the beginning for each original image.

Therefore, in the present invention, the processing efficiency of data compression is high.

Furthermore, since there is no need to prepare multiple types of tables as in the technique disclosed in Japanese Patent Application Laid-Open No. 63-103583, the required capacity of memory for holding tables can be small.

In addition, multiple tables that are candidates for the code table that will actually be used are identified in the first stage, and the second
At this stage, a two-step selection process is performed in which the code table to be actually used is selected from among the candidate tables, so there is no need to perform calculations between all code tables and the orthogonal transformation coefficients of pixel blocks. It is only necessary to perform calculations between the table and the orthogonal transformation coefficients of the pixel block.

Therefore, there is an advantage that the number of calculations is small and the selection processing speed is fast.

[Brief explanation of the drawing]

FIG. 1 is a schematic configuration diagram of an apparatus to which an embodiment of the present invention is applied, FIGS. 2 and 3 are flowcharts showing an embodiment of the present invention, and FIG. 4 is an example of a sub-table. FIG. 5 is a conceptual diagram showing the structure of compressed image data. FIG. 6 is a schematic diagram showing the decoding device. FIG. 7 is an explanatory diagram showing image blocking. The figure is an explanatory diagram showing a pixel arrangement within a pixel block, FIG. 9 is an explanatory diagram showing an example of image data and conversion coefficients, FIG. 10 is a conceptual diagram showing an example of a code table, and FIG. 11 is an explanatory diagram showing an example of a code table. FIG. 2 is an explanatory diagram showing an example of the relationship between the standard deviation of image data and the number of occurrences thereof. AP...Image data compression device, B _vh ...Pixel block, CT...Code table, I _no ...Number of effective bits, F _no ...Conversion coefficient, f _ij ...Image data,
D _f ...Compressed image data, P...Pixel, σ...
standard deviation.

Claims (1)

[Scope of Claims] 1. An image data compression method for obtaining compressed image data for each of a plurality of pixel blocks into which an image is divided, comprising: (a) image data obtained in advance for each pixel for each pixel block; (b) a code for designating some of the transform coefficients in the transform coefficient table as valid; A plurality of code tables that are tables and are different from each other are prepared in advance, and based on the result of calculation using each coefficient value of the conversion coefficient table and the value of each code table corresponding to the relevant pixel block, the relevant pixel is (c) extracting the values of the conversion coefficients while referring to the optimum code table to obtain compressed image data; In the step (b), the plurality of code tables are selected from a plurality of code table groups according to the size of a statistic representing a distribution state of image data within the pixel block. An image data compression method characterized by: