JP2561292B2 - Image data compression device - Google Patents

Description

DETAILED DESCRIPTION [Table of Contents] Outline Industrial field of application Conventional technology (Fig. 4 (a) Fig. 4 (b)) Problems to be solved by the invention Means for solving problems Example Description of coding circuit (Fig. 1 (a)) Description of decoding circuit (Fig. 1 (b)) Description of gradation / resolution component separation circuit (Fig. 2) Description of vector quantization encoder ( FIG. 3) Modification Example Effect of the invention [Overview] A compressor for image data, and more particularly, a compressor for image data of a multi-value halftone image. Control and circuit configuration can be simplified and the image can be efficiently processed. For the purpose of enabling compression of data, the image is divided into blocks of a predetermined number of pixels, and the number of gradations according to the magnitude of gradation change in the block is preset. Every other block, the pixel data The maximum value and the minimum value of the pixel data and the difference between the two, and select the corresponding number of gradations from the magnitude of the difference. A gradation number is assigned to each pixel, and a gradation number indicating which gradation value each pixel belongs to is given to each pixel. An output vector having a gradation number sequence closest to the vector of the block is selected from the set of vector vectors, and the average gradation of the pixels of the block is calculated by using the gradation number sequence of the selected output vector. Then, the image information of the block is represented by the average gradation and the index designating the output vector.

[Industrial applications]

The present invention relates to an image data compression apparatus, and more particularly to an image data compression apparatus for a multi-value halftone image.

[Conventional technology]

The amount of information required to represent image data is orders of magnitude greater than that of numerical data. This information amount becomes extremely large especially in multi-value halftone images and color images among image data.

In order to store such image data or to transmit at high speed and high quality, it is necessary to highly efficiently compress and encode the gradation information for each image.

Thus, for example, a block coding method has been proposed as a compression method of image data for compressing image data with high efficiency. In this block coding method, an image is divided into blocks each including a plurality of predetermined pixels, and image information in the blocks is divided into two gradation components and how the gradations are arranged in the blocks. It is represented by a resolution component indicating whether or not there is an error (see, for example, the Journal of the Institute of Electronics and Communication, January 1979, Vol. J62-B, No. 1, "Block Coding Method for Still Images").

However, in this block coding method, since the image information is approximated by two gradations for each block, the quality of the restored image is greatly deteriorated. Therefore, the following improved block coding scheme has been proposed. This improved block coding method divides an image into N × N blocks, and divides the block into 1 to 4 gradation components according to the degree of gradation change in the blocks, and Is displayed separately from the resolution component that indicates how to arrange in the block and is encoded (for example, 1986 Proceedings of the Institute of Image Electronics, 1986, 86-02-05, "Multi-gradation of grayscale image". Type block coding ").

The following devices are available as devices that employ such a block coding method. FIG. 4 (a) shows an encoding circuit of an apparatus adopting this block encoding method. In this example, the processing is performed by using pixels of 4 × 4 pixels as one block. In the figure, 1 is a first block line buffer for storing one block line (4 lines) of image data input from the input terminal 2, and 3 is one block of image data input from the block line buffer 1. A gradation determining circuit for determining gradation and a gradation determining circuit 4 for separating image data into gradation components and decomposition components based on the gradation number determined by the gradation number determining circuit.
Resolution component separation circuit, 5 is DPCM for encoding gradation components
(Differential Pulse Code Modulation) encoder, 6 is a second block line buffer that stores resolution components one block line (4 lines) at a time, and 7 is MR (Modified REA) that stores the resolution components stored in this block line buffer.
D) An MR encoder for encoding and transmitting, and 8 denotes a multiplexer for switching the DPCM-encoded gradation component and MR-encoded resolution component for each block line and outputting from the output terminal 9.

In such an encoding circuit, the gradation determining circuit 3 described above is used.
Then, the maximum gradation L _Max and the minimum gradation L _Min are obtained, gradation change L _d = L _Max −L _Min is calculated based on these values, and the preset thresholds T ₁ , T ₂ , T ₃ are calculated. (T ₁ <T ₂ <T ₃ ) and the number of gradations displayed by the block is determined. For example, 1 gradation when L _d <T ₁ 2 gradations when T ₁ ≦ L _d <T ₂ 3 gradations when T ₂ ≦ L _d <T ₃ 4 gradations when T ₃ ≦ L _d I am trying to. Further, the gradation / resolution component separation circuit 4 equally divides the gradation change according to the number of gradations determined by the gradation determination circuit 3, and the average gradation of the pixels falling within this divided section.
L _i (k) is obtained and this is the gradation to be displayed. Here, the subscript k indicates that it relates to the kth block, and the maximum number of gradations displayed in the Kth block is 4
Since it is a gradation, a maximum of L ₁ (k) to L ₄ (k) is output, and this is output as a gradation component. Then, a signal indicating which pixel in the block has which gray scale is output as a signal of maximum 2 bits per pixel as a resolution component.

Then, the above-mentioned gradation component is encoded in the DPCM encoder 5, and this encoding calculates the following difference and the difference value
It is performed by encoding D ₁ , D ₂ , D ₃ , D ₄ .

D ₁ = L ₁ (K-1) -L ₁ (K) D ₂ = L ₂ (K) -L ₁ (K) D ₃ = L ₃ (K) -L ₂ (K) D ₄ = L ₄ ( K) −L ₃ (K) Further, since the resolution component can be processed for each line, one block line is stored in the block line buffer 6 and is read out for each line, and the natural binarization indicating the gradation number is performed. After converting the number into a Gray code so that it can be easily encoded, it is bit-plate encoded by the MR encoding method by dividing it into upper bits and lower bits. The DPCM code and MR code are switched by the multiplexer 8 for each block line and output.

Next, a decoding circuit for decoding the encoded image data will be described. In FIG. 4 (b), 11 is a demultiplexer for separating the resolution component and the gradation component of each block of the compressed image data input from the input terminal 12, and 13 is the decoding of the MR encoded resolution component. MR decoder, 14 is a first block line buffer that stores the decoded resolution component for one block line, 15 is a DPCM decoder that decodes the DPCM-encoded gradation component, and 16 is each block from the resolution component Gradation number detection circuit that reads the gradation number of
Is a gradation / resolution component synthesizing circuit for synthesizing the gradation component and the resolution component to create image data, and 18 is storing the signals from the gradation / resolution component synthesizing circuit one block at a time and storing one block line The second block line buffer for outputting to the output terminal 19 is shown.

Here, since the gradation component is encoded and decoded in units of one block and the resolution component in units of line, the gradation component is temporarily stored in the first block line buffer 14 so that it can be handled in units of blocks. After that, the gradation / resolution component synthesizing circuit 17 takes in the gradation component and the resolution component for each block, and controls so that both components can be accurately synthesized.

[Problems to be solved by the invention]

By the way, in the above-described conventional image data compression method, the resolution component is encoded by the MR method, so the resolution component is processed line by line,
The gradation component is processed for each block. Therefore, in order to match these, a block line buffer for accumulating image data is provided in the encoding circuit and the decoding circuit so that image data in block units can be processed line by line and information in line units can be processed block by block. However, there is a problem in that the circuit configuration becomes complicated and the image data processing procedure and control become complicated.

Therefore, it is an object of the present invention to provide an image data compression method capable of simplifying control and circuit configuration and highly efficiently compressing image data.

[Means for solving problems]

In the present invention, a means for solving the above-mentioned problem is to divide an image into blocks each having a predetermined number of pixels, and preset the number of gradations according to the magnitude of gradation change in each block. For each block, means for obtaining the maximum value and the minimum value of the pixel data and the difference between the two from the pixel data in the block, and means 23 for selecting the corresponding number of gradations from the magnitude of the difference. , The maximum value and the minimum value are equally divided by the number of gradations, and each pixel is given a gradation number indicating which gradation value each pixel belongs to, the gradation number for one block. Means for obtaining the average gradation of pixels corresponding to the gradation number of the block by using the arrangement of gradation numbers of the output vector obtained by approximating the vector Vector of a sequence of tone numbers that appear frequently Means for selecting an output vector having a sequence of gradation numbers closest to the vector of the block from the set of.

[Action]

In the present invention, the gradation components and the arrangement of the gradation components within the block (resolution component) are processed in units of blocks, so that the configuration of the processing system is simple and the control is easy. Further, since the resolution component is non-conservatively encoded by vector quantum encoding, the information compression rate is improved. [Embodiment] FIG. 1 is an image data encoding of an image data compression apparatus according to the present invention. It is a principle explanatory view of a circuit. In the figure, 21
Is an image data input terminal, 22 is a block line buffer, 23 is a gradation number determination circuit, 24 is a gradation / resolution component separation circuit, 25 is a DPCM encoder, 26 is a vector quantization encoder, 27 is a multiplexer, 28 Indicates an output terminal of compressed data.

The block line buffer 22 of this encoding circuit stores image data in pixel units input from the input terminal 21,
The image data for one block line is stored. The image data stored in the block buffer memory is read block by block and subjected to necessary processing.

In this example, the image data has 256 gradations (0 to 255),
It is assumed that one block is displayed with 4 × 4 pixels and one block is displayed with a maximum of 4 gradations. First, the gradation number determination circuit 23 is 1
The image data for a block is read from the block line buffer 22, and the number of gradations (1 to 4) is determined by the same method as described above. Then, the image data is separated into a gradation component and a resolution component by the gradation / resolution component separation circuit 24, and the resolution component is vector-quantized and variable-length coded by the vector quantization encoder 26.

Since the vector-quantized resolution component is not the same as the resolution component of the original image data and the number of gradations and the distribution of gradations are different, the resolution component after vector quantization is again the gradation resolution / component. Using the arrangement of the gradation numbers of the block after being input to the separation device and having been vector-encoded, the average gradation of the pixels of the block is obtained. The calculated average gradation is output to the DPCM encoder 25 as a gradation component. The DPCM encoder 25 performs encoding in the same procedure as shown in the related art and outputs it to the multiplexer 27. The multiplexer 27 uses the vector quantized resolution component and DP
The CM-encoded gradation component is switched for each block one by one and is output to the output terminal 28 as compressed data.

FIG. 1 (b) is a diagram showing the principle of the decoding circuit of the image data compression apparatus according to the present invention.

In the figure, 31 is an input terminal for inputting compressed data,
32 is a demultiplexer, 33 is a vector quantization decoder, 34
Is a DPCM decoder, 35 is a gradation / resolution component synthesis circuit, 36 is a block line buffer, and 37 is an output terminal.

In this decoding circuit, the demultiplexer 32 divides the compressed data input from the input terminal 31 into one block of grayscale components and resolution components, the resolution components to the vector quantization decoder 33, and the grayscale components to DPCM decoding. Output to the container 34. The vector quantization decoder 33 decodes the vector-quantized resolution component, and the resolution component of the image data indicating which pixel in one block has which gradation exists in the gradation / resolution component combining circuit 35. Further, the number of gray levels used in the one block found by this decoding is output to the DPCM decoder 34 and the gray level / resolution component synthesizing circuit 35. The DPCM decoder 34 combines the DPCM-encoded gradation components and sequentially decodes the gradations used in one block, and outputs them to the gradation / resolution component synthesizing circuit 35. Then, the gradation / resolution component synthesizing circuit 35 receives the resolution component of one block, the number of gradations, and the contents of the gradations used in the block, and synthesizes the image data of each block to synthesize the block line buffer 36. The block line buffer 36 stores this image data for one block line,
The decoded image data is output to the output terminal 36.

Next, the gradation / resolution component separation circuit of the above-mentioned encoding circuit
The detailed structures of 24 and the vector quantization encoder 26 will be described. FIG. 2 shows the gradation / resolution component separation circuit of the above-mentioned encoding circuit. In the figure, 41 is an interval dividing circuit, 42, 43 and 44 are first, second and third registers, 45 is a pipeline register, 46, 47 and 48 are first,
Second and third comparators, 49 is a gradation number conversion circuit, 50 is a multiplexer, and 51, 52, 53 and 54 are first, second, third and fourth average value circuits. In this gradation / resolution component separating circuit, when the minimum gradation L _Min , gradation change L _d and gradation number m in one block are inputted from the gradation number determining circuit 23 to the interval dividing circuit 41, the interval dividing circuit 41 Determines the boundary values S ₁ , S ₂ , S ₃ of the gradation section used in the block and holds them in the first to third registers 42, 43, 44. This boundary value
S ₁ , S ₂ , and S ₃ are calculated according to the following formula.

When _{S 1 = S 2 = S 3} = 255 When the gray scale number _{m = 2 S 1 = L Min} + L d / 2 S 2 = S 3 = 255 gradation number m = 3 when the gray scale number m = 1 S ₁ ＝ L _Min ＋ L _d / 3 S ₂ ＝ L _Min ＋ 2 × L _d / 3 S ₃ ＝ 255 When the number of gradations m = 4 S ₁ ＝ L _Min ＋ L _d / 4 S ₂ ＝ L _Min ＋ 2 × L _d / 4 S ₃ = L _Min + 3 × L _d / 4 Then, the values of the boundary values S ₁ , S ₂ and S ₃ are output to the first to third comparators 46, 47 and 48. On the other hand, the pipeline register 45 stores the image data for one block from the block line buffer 22.
Are output one after another. The image data for one pixel is compared with the respective boundary values S ₁ , S ₂ , S ₃ by the comparators 46, 47, 48. If it is smaller than the boundary values S ₁ , S ₂ , S ₃ , it is "0". 1 ”is output, and this information is input to the gradation number conversion circuit 49.
In this embodiment, the comparators 46, 47 and 48 and the gradation number conversion circuit output the gradation numbers according to the following table.

Then, the gradation numbers n _{1 to} n _{16 for} one block obtained
Is input to the vector quantization encoder.

FIG. 3 shows the vector quantization encoder 26.
In the figure, 61 is a first register, 62-1 to 62-16.
Are first to sixteenth subtractors, 63-1 to 63-16 are first to sixteenth absolute value circuits, 64 is an adder, 65 is a minimum value detection circuit,
66 is the second register, 67 is the output vector code table
ROM, 68 is an index counter, and 69 is a variable length encoder.

In this vector quantization encoder 26, the gradation /
The resolution components b _{1 to} b ₁₆ of each pixel for one block from the resolution component separation circuit 24 are stored in the first register 61.
In the present embodiment, the output vector code table ROM stores a set (vector) of a series of gradation numbers having a high appearance frequency set in advance, for example, 256 sets of vectors to which index numbers 0 to 255 are attached. Has been done. When the index counter 68 counts up the index number from 0 to 255, the vectors corresponding to the index number are sequentially output to the second register 66. First to sixteenth subtracters 62-1 to 62
-16 is the resolution components b _{1 to} b ₁₆ of the image data stored in the first register 61 and 1 from the output vector code table ROM 67 sequentially stored in the second register 66.
A set of values b _{i1 to} b _i16 (i is an index number) is input, and the difference is calculated and output. Then, the absolute value of the difference is calculated by the absolute value circuits 63-1 to 63-16 and added by the adder 64.

with this, Is calculated for all index number vector sets.

Then, the minimum value detection circuit 65 detects the minimum of these values, holds this index number, and outputs the index number having the minimum value to the index counter 68 after this search is completed, The vector of the set of index numbers is stored in the second register 66. Further, this index number is input to and encoded by a variable length encoder that allocates shorter codes to index numbers that are used more frequently, and this becomes the compressed resolution component of the image data of the block.

Here, although the value of this vector is the vector closest to the resolution component of the image data input to this vector quantization encoder, these two values do not necessarily match. Therefore, the value of the second register 66 is again sent to the gradation / resolution component separation circuit 24 to calculate the average value of the gradation components to be output.

In FIG. 2, a sequence of gradation numbers of each pixel after the vector quantization from the vector quantization encoder 26 (gradation number 0
Combinations of 3 to 3) are input to the multiplexer 50. Then, the multiplexer 50 sequentially processes the image data of one block stored in the pipeline register 45 before the vector quantization is performed, in order, according to the tone number after the vector quantization, the tone of the pixel corresponding to the position. (0 to 255) is the average value circuit 51,52,53,54 corresponding to the gradation number 0,1,2,3
To enter.

The average value circuits 51, 52, 53, 54 calculate the average value of the input gradation values and display the average gradation value corresponding to each gradation number as a representative gradation Is output to the DPCM encoder 25 and is DPCM encoded. This is the gradation component of the compressed image data of the block.

This completes the compression and encoding of the image data for one block together with the above resolution component.

In the above-described embodiment, in the vector quantization encoder shown in FIG. 3, the comparison between the resolution component from the image data and the vector from the output vector code table ROM is the absolute difference absolute value of the two values. However, other methods such as square error can be adopted. Similarly, for the search of the output vector, the full search method (full searc
Although the case of using the h) method has been described, it goes without saying that a high-speed search method such as a tree search method can be used for this search.

〔The invention's effect〕

As described above, according to the image compression apparatus of the present invention, both the gradation component and the resolution component of image data can be processed in block units, so that encoding and decoding can be performed with a simpler circuit. can do. Therefore, there is an effect that the control of the device can be simplified. Further, according to the present invention, since the encoding of the resolution component is also the information non-preserving type encoding, there is an effect that the compression rate is improved and the processing can be executed at high speed.

[Brief description of drawings]

FIG. 1 (a) is a block diagram of an encoding circuit of the present invention.
FIG. 2B is a block diagram of the decoding / encoding circuit of the present invention,
1 is a block diagram showing a gradation / resolution component separating circuit of the encoding circuit shown in FIG. 1, FIG. 3 is a block diagram showing a vector quantization encoder of the encoding circuit shown in FIG. Four
FIG. 4A is a block diagram showing a conventional encoding circuit, FIG.
FIG. 1B is a block diagram showing a conventional decoding circuit. 22 …… Block line buffer 23 …… Gradation number determination circuit 24 …… Gradation / resolution component separation circuit 25 …… DPCM encoder 26 …… Vector quantization encoder

Claims (1)

(57) [Claims] 1. An image is divided into blocks composed of a predetermined number of pixels, and the number of gradations is preset according to the magnitude of gradation change in each block. Between the pixel data, a maximum value and a minimum value of the pixel data and a difference between them, a means for selecting a gradation number corresponding to the magnitude of the difference; The number of gradations is equally divided, each pixel is given a gradation number indicating which gradation value each pixel belongs to, and the arrangement of the gradation numbers for one block is made into a vector, and the vector is approximated. Means for obtaining the average gradation of the pixels corresponding to the gradation numbers of the block using the arrangement of the gradation numbers of the output vector obtained by To the floor closest to the vector of the block And a unit for selecting an output vector having a sequence of key numbers.