JPS6337777A - Compression system for image data - Google Patents

Abstract

PURPOSE:To enable fast processing by making classifications by clusters indicated by representative gradations at the shortest distance from representative gradations, and representing image information in a block with a representative gradation which is determined finally and a cluster number where each picture element data belongs. CONSTITUTION:A representative gradation selecting means 5 reads picture element data out of a buffer memory 2 and classifies respective picture element data by clusters indicated by representative gradations at the shortest distance. A representative gradation updating means 8 reads the classification results out of a resolution component memory 6 to find the mean value of each classified cluster, and the mean value is set as a new representative gradation in a representative gradation sending means 4. A convergence deciding means 7 checks the coincidence between a resolution component which is generated nearly and the last resolution component and decides that operation for finding representative gradations is converged when coincidence is obtained to output the found representative gradation to a terminal 9 by a representative gradation sensing means 4 and also output in-block arrangement information on the representative gradation to a terminal 10 from the resolution component memory 6. Consequently, the fast processing becomes possible.

Description

[Detailed Description of the Invention] [Table of Contents] Overview Industrial Field of Application Prior Art (Figure 7.8.9) Problems to be Solved by the Invention Means for Solving the Problems Examples of Actions Present Invention Explanation of the principle (Figure 1.2) Creation of initial value of representative gradation (Figure 3.4) Selection of output 1 of representative gradation and convergence judgment (Figure 5) Update page of representative gradation (Figure 6) Effects of the Modified Example Invention [1 Already Required] The present invention, in data compression of a multi-level halftone image, divides the image into blocks each consisting of a predetermined plurality of pixels, and divides the image into blocks each consisting of a predetermined plurality of pixels, and also divides the image into blocks each consisting of a predetermined plurality of pixels, and divides the image into blocks each consisting of a predetermined plurality of pixels. The number of representative gradations to display the block and the initial value of the representative gradation are calculated, and from these initial values, the representative gradation is updated using an averaging algorithm, and the final representative gradation and its representative gradation are calculated. The arrangement within the block is determined, and these representative gradations and the arrangement within the block are encoded.

[Industrial application field]

The present invention relates to an image data compression method, and more particularly to an improvement in a data compression method for multi-level halftone images.

[Conventional technology]

The amount of information required to represent image data increases by an order of magnitude compared to numerical data. This increase in the amount of information is remarkable among image data, especially in multi-value halftone images and color images.

Accumulate such image data or fast.

In order to transmit with high quality, it is necessary to encode tone information for each image with high efficiency.

As a highly efficient compression method for image data, for example, differential adaptive block coding (IEEJ Study Group Proceedings 85-07-
04) and a method devised by the applicant of the present application in which each block is expressed using a plurality of representative gradations.Next, these two methods will be explained.

(1) The former method divides an image into predetermined blocks of multiple pixels, then quantizes the maximum and minimum gradation levels within the block into 2'' gradations, and encodes this into bit-plane encoding. It is characterized by dividing image information into three components: median value, difference value, and bit plane information.

Considering the case where the gray scale image has 256 tones (θ~256) and n=2, the maximum value of the tones within the block (L ma
When the difference between x) and the minimum value (L ll1in) is uniformly quantized as shown in FIG. 7, the median value LA.

The difference value LD and the representative floor jPIPi, Q are determined as shown in the following equation.

Median value: LA − (Lmax + Lmin) /
2 difference value: L, -(Lmax -Lmin)
/222 gradation indication: P, -ri, + -LD (i 1 )L.

When expressing a grayscale image, the larger the density change in a block, the smaller the number of gradation levels can be used to approximate the block without degrading the image quality. Therefore, as shown in FIG. 8, LI is compared with threshold values T I and T z, and depending on the magnitude thereof, the block is approximated with 1, 2, and 4 gradations, respectively. max 4
Since gradation (gradation component) is used, to specify the placement of this gradation within a block, a maximum of 2 bits of information (
resolution component) is required. 2 bits φ1 of resolution component
．． Each of φ2 is bit-plane encoded.

(2) The latter method divides an image into predetermined blocks of multiple pixels, and then divides the image into blocks of predetermined multiple pixels, and then divides the image into
The number of gradations is 1.2, 3, 4. ..., and is characterized in that the representative gradation and the arrangement of the representative gradation are determined, for example, by an averaging algorithm.

A block diagram of a circuit for extracting encoded information using this method is shown in FIG.

In this method, an image signal is input, stored in a buffer memory, read out block by block, and encoded information is created as follows. First, the average value of a block is determined as a representative gradation, and the block is represented by the average value to check whether sufficient approximation can be achieved.

The degree of approximation uses the root mean square error from the actual value when each pixel in the block is represented by a representative gradation.

If the degree of approximation is insufficient, the representative gradation with a large error among the representative gradations is divided into two to create two representative gradations, and two initial values of the representative gradation are created. Next, using this representative gradation, the pixels of the block are classified into the nearest representative gradation, and the average value (centroid) for each group of classified pixels is determined and used as a new representative gradation. In this way, the number of representative gradations is increased according to the degree of approximation of the blocks, and the representative gradation (gradation component) and the arrangement of the representative gradation within the block (resolution component) are determined.

[Problem that the invention seeks to solve]

In the conventional technology, in the former type of differential adaptive block coding, when a block is approximated by multiple pixels, the average density of the block is not preserved, so in order to reproduce the image naturally, the number of tones representing each block must be This method had the disadvantage that the compression ratio had to be increased compared to the latter method, and the compression ratio could not be increased. On the other hand, in the latter method of determining the representative gradation using an averaging algorithm without increasing the number of gradations, it is possible to optimally select the number of representative gradations and the representative gradation, but it requires repeated calculations. However, the disadvantage is that it takes time to encode.

[Means for solving problems]

The present invention divides a multilevel halftone image into blocks each consisting of a predetermined number of pixels, compares the tone changes within this block with a plurality of predetermined darkness values, and creates clusters according to the tone changes. and the initial value of the representative gradation for displaying each cluster.

Next, each pixel is classified into the determined number of clusters by selecting and assigning the one closest to each pixel from among the representative gradations described above, and the classification results are recorded.

Next, a centroid (center of gravity) is determined for each cluster, and this is set as a new representative gradation.

In this representative gradation updating operation, if the newly obtained classification result matches the previous classification result, it is determined that the representative gradation updating operation has converged.

When the representative gradation updating operation converges, or after repeating the same operation a certain number of times, the obtained representative gradation and classification result are output as the gradation component and resolution component of the block.

[For production]

In the present invention, the number of clusters is selected according to the degree of gradation change in image data, and the average value of pixel data is saved for each cluster, so it is possible to determine a representative gradation that is close to the optimum. Moreover, since the calculation used to update the representative gradation is extremely simple, it can be executed at high speed.

〔Example〕

FIG. 1 is a diagram explaining the principle of an encoded information extraction circuit in an image data compression method according to the present invention.

In the figure, 1 is an input terminal for image data, 2 is a buffer memory, 3 is representative gradation initial value creation means, 4 is representative gradation sending means for sequentially sending out representative gradations, and 5 is representative gradation selection means. , 6 is a resolution component memory, 7 is a convergence determining means, 8 is a representative gradation updating means, 9 is an output terminal of a gradation component, and IO is an output terminal of a resolution component.

The buffer memory 2 of the present invention receives an image signal in units of pixels from a terminal 1, stores 1 block of 947 worth of image data, and outputs pixel data one block at a time. The pixel data stored in this buffer memo 2 is read out block by block and subjected to necessary processing.

The following description will be made assuming that the image data has 256 gradations (0 to 256), the block size is 4×4 pixels, and one block is approximated by a maximum of 4 gradations.

Encoding information for each block is created as follows. First, the initial value creation means 3 reads one block of pixel data from the buffer memory 2, and reads the maximum value (
Lmax) and the minimum value (Lm1n) are determined, and the difference value Lo=Lmax-L+nin is determined from these values.

Next, the above difference value is set as the threshold value T l + T z, T
s, and determine the number of gradations to display the block from 1 to 4 depending on the size of LD (see Figure 2), and calculate the initial values of representative gradations LA, Pk, Qk, Ri= using the following formula. Find from.

Median value: Lx −1−+++; n ” Lo (k
= 1) Two-gradation display: Pk=L,,linshi□LD (k=1.2)
3-gradation display: k Qk= L+++i+s ” Ln (k
=1.2.3) 4-gradation display: Rk -Lath + -Lt+ (k =1.2
, 314) Then, the initial values of these representative gradations are set in the representative gradation sending means 4.

Next, the representative gradation selection means 5 uses these representative gradations to classify the pixels of the block into the closest representative value, and writes the result (gradation arrangement) into the resolution component memory 6.

Next, the representative gradation selection means 5 reads out the pixel data from the buffer memory 2 again, and classifies each pixel data into clusters in which the closest among the representative gradations is displayed. Then, this classification result is stored in the resolution component memory 6.

The representative gradation updating means 8 reads the classification results from the resolution component memory 6, finds the average value (centroid) for each classified cluster, and sets this as a new representative gradation to the representative gradation sending means 4. .

The operation of obtaining a new representative gradation using the representative gradation sending means 41, representative gradation selecting means 52, resolution component memory 6, and representative gradation updating means 8 is repeated as necessary.

The convergence determining means 7 repeats this operation, checks whether the newly created resolution component matches the previous resolution component, and if they match, determines that the operation for determining the representative gradation has converged. Then, the one representative gradation sending means 4 is caused to output the determined representative gradation to the terminal 9, and the in-block arrangement information of the representative gradation is output from the resolution component memory 6 to the terminal 10.

The encoding of the gradation component and the resolution component is the same as in the prior art, so a description thereof will be omitted.

A specific example for realizing the encoded information extraction circuit described above will be described below.

3, 5, and 6 are detailed diagrams of each part of the encoded information extraction circuit of the present invention shown in FIG. 1.

FIG. 3 is a detailed diagram of the initial value generating means 3, in which pixel data is input block by block from the buffer memory 2 to the terminal 3-1.

L+++ax detector 3-2 and Lwin detector 3-3
inputs the pixel data read out for each block,
Maximum value (L, , ) and minimum value (L
,,,) is output.

This maximum value and minimum value detection circuit can be configured using a ROM 3-2-1 and a register 3-2-2, for example, as shown in FIG. The register 3-2-2 is first cleared.Pixel data Xij of the block is input from the terminal 3-1,
It is added as part of the address (for example, upper n bits) of the ROM 3-2-1. Also, the value of register 3-2-2 is stored in ROM3-2-1.
is added as part of the address (for example, the lower n bits). This ROM 3-2-1 has written therein a table that outputs the larger of the two values input as addresses, as shown in FIG. 3(b). By doing this, each time pixel data is input, ROM3-2 to
If the output of 1 is set in register 3-2-2, the maximum value of the block is finally obtained in registers 3-2-2.

On the other hand, if you want to find the minimum value, register 3-2-
2, all bits are initially preset to 1, and a table that outputs the smaller of the two values input to the address may be written in the ROM 3-2-1. As mentioned above, when the number of gradations of image data is 256, the capacity of ROM3-24 is 64-ord
It becomes t.

Now, let's return to the explanation of FIG. The subtracter 3-4 is L max
From detector 3-2 and i, i was determined as described above from detector 3-3, and 08. is input, and its difference value (1, +>) is output. In addition, the number of gradations calculation RO
Similarly, M3-5 inputs L MIIX 0.7 to its address and outputs the number m of gradations to display that block.0 Since the maximum value of the number of gradations is 4, the number of gradations is 1. ~4
corresponds to 0 to 3, and m is represented by 2 bits.

The input difference value and threshold value T are stored in the ROM 3-5.

A table for determining the number of gradations, ie, the number of clusters m mentioned above, is written in advance from the comparison results with "rz and T" (see FIG. 2).

Next, the obtained difference (J L o and the number of gradations m are determined by the increment R
Added to part of address of OM3-6. Furthermore, 2 bits of output from the gradation magnetic counter 3-7 are added to the address of the incremental ROM 3-6.

The gradation light counter 3-7 is initially cleared, and counts up by one each time a control order signal (not shown) is applied. The incremental ROM 3-6 inputs these values and outputs the incremental LD (j!+1)/(m+2). Adder 3-8 inputs L sin and the increment, and outputs L sin and the increment. Every time a B order signal (not shown) is added, the initial values of the representative gradations are output one by one to the terminals 3-9 in increments.

FIG. 5 shows representative gradation sending means 49 representative gradation selecting means 5.
and a detailed diagram of the convergence determination means 7.

In FIG. 5, first, the operation of the representative gradation sending means 4 is as follows.
It will look like this: In the same figure, from terminals 4-1 and 4-2, initial value creation means 3 and representative gradation updating means 8 are provided, respectively.
Therefore, the representative tone LA (k=1).

Alternatively, Pk (k=1.2), Qk (k=1°2.3), or Rk (k=1.2, 3.4) is input. The multiplexer 4-3 is switched to the input side and outputs these representative gradations.

The demultiplexer 4-4 inputs these representative gradations,
Depending on the value of k of 1, 2, or 3.4, the output is switched to the register 4-5.4-6.4-7.4-8 side and set in each register. The multiplexer 4-9 sequentially selects each register and outputs a representative gradation.

Next, the operation of the representative gradation selection means 5 will be explained. Pixel data Xij for each block is input from the buffer memory 2 through the terminal 5-1 to the subtracter 5-2. Then, for the data of each pixel, representative gradations are selected one by one through the multiplexer 4-9, and the subtracter 5
-2 is added. The subtracter 5-2 outputs the absolute value of the difference d'1j-l X=J-(REG)'l from these values. (REG) k (k-1, 2, 3, 4) are registers 4-5, 4-6, respectively. The contents shall be as per 4-7.4-8.

The detector 5-3 inputs d kij and outputs k (index of representative gradation) for which this value is the minimum.

The detector 5-3 has almost the same configuration as the minimum value detection circuit shown in FIG. If this value is larger, a signal that latches and outputs the value of k at this time may be added.

Next, the index (number) k4 of the representative gradation obtained for each pixel of the pro-tsuku manually inputted to the terminal 5-1,
are stored in the shift register 6-1 while being shifted one by one. Here, a shift register 6-1 is used as the memory 6 for storing the index of the representative gradation as a resolution component.

The configuration of this shift register 6-1 is 16 words
It is 2 bits.

The convergence determination means 7 includes a mismatch detection circuit 7-1. It is composed of a flip-flop 7-2. The convergence determination operation is performed as follows. The mismatch detection circuit 7-1 is the detector 5-3
The index of the newly classified representative gradation from the shift register and the index of the previously classified representative gradation from the shift register are input, and their coincidence is checked. If there is a pixel whose newly determined representative gradation index does not match the previous representative gradation index, a signal to this effect is set in the flip-flop 7-2. This makes it possible to determine whether the averaging algorithm has converged to find the representative gradation.

If there is a mismatched pixel in the block, the representative gradation is updated again using a signal from the printer 7-2.

FIG. 6 is a detailed diagram of the representative gradation updating means 8.

In FIG. 6, pixel data XiJ for each block is input from the buffer memory to the adder 8-2, and the contents of the register 8-3 are added to the other input. And, this adder 8-2 is a negative number construction circuit 8.
Accumulation is performed according to the addition command from -6.

The match detection circuit 8-6 receives input from the counter 8-5 of the index of the representative gradation read out from the resolution component memory 6 and the number of the currently required representative gradation based on the order control signal. be done. When these two values match, the minus number construction circuit 8-6 outputs the above-mentioned addition command.

At the same time, the counter 8-7 outputs a -number output circuit 8.
The number of addition commands from -6 is counted.

When these two values match, the minus number construction circuit 8-6 outputs the above-mentioned addition command.

At the same time, the counter 8-7 outputs a -number output circuit 8.
The number of addition commands from -6 is counted.

Then, for each representative gradation, the accumulated value is stored in the register 8-3.
Then, the number in the block is determined by the counter 8-7, and these two values are input to the divider 8-4. As a result, a new representative gradation is obtained as the average value (centroid) of pixels belonging to the previous representative gradation.

The new representative gradation is set in the register 8-8 and sent to the representative gradation sending means 4.

In this embodiment, the convergence judgment was made based on whether the arrangement of the representative gradations in the block matched the previous one and the newly obtained one. The difference between the approximation error and the approximation error based on the newly determined representative gradation may be calculated, and the determination may be made based on the rate of decrease in this difference.

Further, in FIG. 1, the convergence determining means 7 is used to update the representative gradation until it converges, but this can also be implemented with various modifications.

That is, if processing speed is more important than accurate selection of the representative gradation, the convergence determining means 7 may be omitted and the representative gradation updating operation may be performed only once from the initial value.

Furthermore, in the above embodiment, the block size is 4×4 pixels, and the maximum number of gradations constituting the block is 4. However, the block size and the number of display gradations may vary depending on the type of image and It may be selected arbitrarily, taking into consideration the processing conditions.

Further, in the above embodiment, a case was described in which data compression is performed on a monochrome multi-value halftone, but it is clear that the present method can also be applied to a color multi-value image.

When applying the present invention to an RGB color multilevel image,
Instead of monochrome gradation, it has 3 elements of R, G, and B.
It is sufficient to consider dimensional vectors, and the proximity of representative gradations (representative colors) may be measured by the distance between vectors. Therefore,
When this method is applied to a color multivalued image, one block is approximated by a plurality of representative colors.

〔Effect of the invention〕

According to the present invention, the average value of the gradations in each block obtained by subdividing an image is saved, and the representative gradation that is close to the optimum is selected. , a large compression ratio can be obtained.Also, since the number of display gradations (number of clusters) and the initial value of the representative gradation (cluster center) are determined according to the gradation changes of each block, an averaging algorithm is used. , calculation time can be shortened and high-speed processing becomes possible.

[Brief explanation of drawings]

Fig. 1 is an explanatory diagram of the encoded information extraction circuit of the present invention, Fig. 2 is a diagram for explaining the number of display gradations of blocks and initial values, Fig. 3 is a detailed explanatory diagram of the initial value creation circuit, Fig. 4 (a) and (b) are explanatory diagrams of the maximum value/minimum value detector, and FIG. 5 is representative gradation sending means 1 representative gradation selection means. Fig. 6 is an explanatory diagram of the convergence determining means, Fig. 6 is an explanatory diagram of the representative gradation updating means, Fig. 7 is an explanatory diagram of conventional quantization of image signals, and Fig. 8 is an explanatory diagram of the conventional block display gradation number and encoding information. , FIG. 9 is an explanatory diagram of a conventional image data compression method. In the figure, 2 is a buffer memory, 3 is an initial value creation means, 4 is a representative tone sending means, 5 is a representative tone selecting means, 6 is a resolution component memory, 7 is a convergence determining means, and 8 is a representative tone updating means. , xtJ is pixel data, La , Ph , Qk,
R represents the initial value of the representative gradation, and φ represents the resolution component. Figure 1 is an explanatory diagram of the encoded information extraction circuit of the present invention. Initial values of gradations La P-Q-Rk
Number of display gradations and initial values of Pro 7ri Figure 2 Detailed explanation of the initial value creation circuit! @3 Diagram ROM configuration example explanatory diagram Maximum value/minimum value detection S! ! Figure 4: Representative gradation exit means 1: Representative gradation selection means, and convergence determining means: Figure 5: 6: Conventional quantization of image signal Encoding information explanation box
8 Figure

Claims (1)

[Claims] An image is divided into blocks consisting of a predetermined number of pixels, and the number of clusters is set in advance according to the magnitude of gradation change within the block. From the pixel data, find the minimum value and maximum value of the pixel data and the difference between the two, select the corresponding number of clusters based on the size of the difference, and calculate the initial value of the representative gradation for displaying each cluster. Then, each pixel data is classified into clusters in which the nearest representative gradation is displayed, the centroid of the pixel data classified into the same cluster is calculated to create a new representative gradation, and each pixel data is The operation of reclassifying the newly created representative gradations into a cluster in which the closest representative gradation is displayed is performed at least once, and the finally determined at least one representative gradation and each An image data compression method characterized in that image information of a block is expressed by a cluster number to which pixel data belongs.