JPH031849B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to an image data compression device for improving data communication efficiency and storage efficiency when communicating and storing digital image data.

[Conventional technology]

With recent advances in digital image processing technology,
In the printing industry, total scanners, which convert images into digital data and perform plate collection and retouching work, have been introduced and are now in use. Here, it is necessary to communicate and store digital data of images.
Various methods have been tried, but the best method has not yet been announced. This is because the amount of image digital data is enormous compared to normal digital data. As an example, in order to express one A4 size print image with four color components at a resolution of 15 lines/mm, 56MByte of data is required, as shown by the following equation. Here, 1 pixel is 4Byte (= 8bit (1Byte) x 4 (color))
Suppose that it is expressed by the data of .

210mm x 297mm x (15 lines/mm) ² x 4Byte/point ≒ 56MByte...(1) Therefore, when communicating data for one A4 size print image, a normal public line (9600bit/sec) is required. It takes up to 13 hours to use a high-speed digital line (64Kbit/
sec), it takes just under 2 hours.

In addition, even when accumulating image data to construct a database, optical disks (1 to
Even if 2GByte) is used, the aforementioned A4 size image data can only be stored for 18 to 36 images, which is insufficient to build an image database.

Therefore, various methods regarding compression of image data have been proposed in order to improve communication efficiency and storage efficiency of image data. Among these, image data compression using orthogonal transformation is said to be the most superior in terms of its high compression rate. Here, there are three points to evaluate the image data compression method: little deterioration in image quality, high compression ratio, and calculation speed. Among various orthogonal transformations from this point of view, two have yielded good results: Hadamard transformation and two-dimensional discrete cosine transformation. The former is superior in calculation speed because it is easy to implement in hardware, and the latter is said to be advantageous in that it can suppress image quality deterioration and increase the compression rate.

The basic idea of image data compression using orthogonal transformation is to orthogonally transform the data matrix of the original image data, and then assign a predetermined bit allocation (LSB) to each data in the transformed data matrix according to the image characteristics. 4 bits that are unnecessary for restoring the original image are discarded, and then encoding is performed to create a compressed encoded data string. . At this time, the compression ratio and image quality reproducibility are determined by how optimal bit allocation is performed.

In addition, when restoring image data, the original image is restored by reproducing matrix data from the encoded data string according to the bit assignments made during encoding and inversely transforming the matrix data. Restore.

If bits are allocated so as to leave all valid bit data in the image data when compressing the image data, the original image data will be completely restored except for the quantization errors caused by digitization, but this will require high compression. I can't get the rate. Therefore, it is absolutely necessary to truncate some bit data of the image data while suppressing the deterioration of the image quality. The key point of image compression using orthogonal transformation is to quickly optimize this bit allocation.

As a conventional example, NEC Corporation's
Medifile1000 uses two-dimensional cosine transformation on X-ray images and obtains excellent results. However, X-ray images are monochrome images, have lower resolution than printed images, and handle an extremely smaller amount of data than color printed images.

Thus, until now, no device has been announced that efficiently compresses a large amount of image data such as a color image for printing, and its announcement has been awaited.

[Problem that the invention seeks to solve]

This invention was made to deal with the above-mentioned circumstances, and in order to enable efficient and high-speed compression of a large amount of digital image data such as printed matter, in image compression using orthogonal transformation,
The object of the present invention is to provide an image data compression device that can perform optimal bit allocation at high speed.

[Means for solving problems]

The image data compression device according to the present invention includes a bit allocation pattern memory storing a plurality of bit allocation patterns representing the bit length allocated to each pixel, and a differential memory for performing a difference between image data after orthogonal transformation and each bit allocation pattern. Circuit 11-
1 to 11-k, comparison circuits 14-1 to 14-k that determine whether the difference value for each bit allocation pattern is within an allowable range, and an optimal bit allocation pattern is selected based on the comparison results. The bit allocation pattern selector 17 is provided.

[Effect]

According to the image data compression device according to the present invention,
It is possible to select the optimal bit allocation pattern for the image data matrix after orthogonal transformation by a combination of simple operations, resulting in a high compression ratio.
Furthermore, image data can be compressed in a short time with little deterioration in image quality.

[Embodiment] An embodiment of the image data compression device according to the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram showing the schematic structure of this embodiment. FIG. 2 is a block diagram showing the configuration of a circuit for selecting the optimum bit allocation pattern, which is a feature of this embodiment. FIG. 3 is a block diagram showing the configuration of a circuit that cuts off unnecessary bits of data after orthogonal transformation based on a selected bit allocation pattern, and adds a pattern code of the bit allocation pattern to perform encoding. .

As shown in FIG. 1, this embodiment comprises a data normalization circuit 2, an orthogonal transformation circuit 4, a bit allocation pattern selection circuit 6, and a compression encoding circuit 8. Original image data ID in which an image is represented by an M×N image matrix, and each image is represented by data of a predetermined bit.
(x, y) are sequentially input to the data normalization circuit 2 for each pixel (x, y). Here, to simplify the explanation, only one original image data is shown as monochrome data in Figure 1, but the original image data ID
If it is a color image, each color component, for example IDr,
There are three data such as IDg and IDb indicating the brightness of each of the red R, green G, and blue B components, and each circuit in FIG. 1 processes each color component.

The data normalization circuit 2 divides (normalizes) the M×N matrix original image data ID (x, y) into data for each block consisting of n×n pixels, and creates block data ID′ (i, j). do. This is because performing orthogonal transformation on the entire original image data ID (x, y) would take too much calculation time, so it is more efficient to perform orthogonal transformation on each block of n×n pixels. . Here, n=8 to 64 is appropriate, and generally 16 or 32 is often used.

FIG. 4 shows an example of the relationship between original image data ID (x, y) and block data ID' (i, j). Fourth
The figure shows the case where M=32, N=48, n=8, and the original image data ID (x, y) is 24 block data.
ID'(i, j). The following processing is sequentially performed on each block data ID' (i, j) to perform data compression for each block.

Block data ID' (i, j) is orthogonal transform circuit 4
supplied to Orthogonal transform circuit 4 is block data
Perform orthogonal transformation on ID′ (i, j) and obtain orthogonal transformation data
Generate AD(i,j). Generally, orthogonal transforms include discrete Fourier transform, discrete cosine transform, Hadamard transform, Haar transform, Slant transform, K-
There are L conversions, etc. K-L transform and discrete cosine transform are superior in terms of less deterioration in image quality due to image compression, but the Hadamard transform is superior in terms of computational load and increase in computational speed.
Here, Hadamard transform will be explained as an example of orthogonal transform.

Assuming that the data matrix to be subjected to Hadamard transformation is ID′, and the data matrix after conversion is AD, the relationship between the two is given by the following equation.

AD=(1/n)・C・ID′・C ^T …(2) Here, C is Hadamard matrix, and Hadamard matrix is a diagonal matrix composed of +1 and −1 components, so Hadamard matrix The transposed matrix C ^T =C. Note that the inverse transformation is expressed by the following equation.

ID'=(1/n)・C・AD・C (3) An example of Hadamard matrix C is shown below. Example is 8
It is a ×8 Hadamard matrix.

The converted data AD(i, g) is transferred to the bit allocation pattern selection circuit 6, and the data AD(i, g) is transferred to the bit allocation pattern selection circuit 6.
j) The optimum bit allocation pattern is selected.

FIG. 2 shows a block diagram of the bit allocation pattern selection circuit 6. The bit allocation pattern selection circuit 6 includes a first-in first-out memory (FIFO) 10 as an input buffer. As an example, AD(i,
j) is a 16×16 data array, the orthogonal transformation data AD(i, j) input to FIFO 10 is (1, 1), (1, 2), ..., according to the transfer clock CK.
256 pieces of data with a mixture of (16, 16) components are sequentially transferred to the difference circuit 11-k (k=1 to K). Here, the number K of differential circuits 11-k is equal to the number K of bit allocation patterns prepared in advance. For example, if there are 16 bit assignment patterns, 16 differential circuits 11 are required, and if there are 32 bit assignment patterns, 32 differential circuits 11 are also required.

K bit allocation patterns BPk (i, j) are stored in the bit allocation pattern memory 16, and the 1st to Kth bit allocation patterns BPk
(i, j) are differential circuits 11-1 to 11-, respectively.
k. Bit allocation pattern memory 1
The read address ADR of 6 is generated by the memory controller 15. Memory controller 15
The transfer clock CK is also input to FIFO10.
By controlling the readout address ADR in synchronization with the data readout from the differential circuit 11-k, each component of the orthogonal transformation data and the corresponding bit allocation pattern component can be simultaneously supplied to the difference circuit 11-k.

FIG. 5 shows an example of a bit allocation pattern.
The illustrated bit allocation pattern is a pattern for 8.times.8 orthogonal transformation data, and although three types of patterns are shown here, it is usually preferable to prepare about 16 to 256 patterns. Here, the blank space is 0. The matrix data constituting the bit allocation pattern indicates a threshold value for cutting off the upper bits of each image data (8-bit data) in order to compress the image data. For example, if the threshold is 8, all 8 bits are valid, if it is 6, only the 6 bits from the LSB are valid (the 7th and 8th bits are invalidated and are not used for encoding), and if it is 0, all bits are valid. means unnecessary. Specifically, 8 means that all 8 bits are “1”, “11111111” is stored as pattern data, and 6 means that all 8 bits are “1” from the LSB to the 6th bit. , “00111111” is stored as the pattern data. The sum total of the matrix data of the bit allocation pattern indicates the total bit length of the image data after compression, and the smaller the sum, the higher the compression ratio.

The difference circuit 11-k is BPk(i,j)-AD(i,
j) is calculated. Here, data AD(i,j)
If is positive and negative signed data, BPk
Compute (i, j)−|AD(i, j)|. This difference value corresponds to the extent (degree of mismatch) in which the data amount (bit length) of each image data after orthogonal transformation exceeds the allocation amount (bit length) of the bit allocation pattern, and is herein referred to as an overflow value.

The overflow values output from the difference circuit 11-k are each supplied to a weighting circuit 12-k. This is a weight W(i,
j) and consists of a multiplier. This is because, as described later, the overflow value for each pixel is totaled for the entire matrix, the overflow value for each image data matrix is determined, and it is determined whether or not the bit allocation pattern is appropriate. This is to ensure that components (higher-order components) are discarded, and is not necessarily required. In the Hadamard transform, the data after transformation has the lowest frequency (spatial frequency) component in the upper left component ((1, 1) component) in the matrix, and the higher the frequency as it goes to the lower right component ((n, n) component). Therefore, when aggregating overflow values, it is possible to accurately determine the degree of mismatch between each image data matrix and the bit allocation pattern by increasing the weight of the low frequency component and decreasing the weight of the low frequency component. can.

The weighted overflow values output from the weighting circuit 12-k are each supplied to an overflow counter 13-k and are totaled. As a result, the overflow counter 13-k detects the degree of mismatch between the allocation amount given by each bit allocation pattern BPk and the data amount of each image data AD as an overflow counter value OCk.

It is determined by the comparison circuit 14-k whether the overflow counter value OCk of the overflow counter 13-k is within the range of appropriate threshold values TH ₁ and TH ₂ . Then, when the following equation is satisfied, a signal CPk indicating that data compression using the bit allocation pattern is appropriate is supplied to the bit allocation pattern selector 17.

TH ₁ ≦OCk≦TH ₂ …(5) Here, if OCk < TH ₁ , there is still redundancy in the data after compression, and conversely, if TH ₂ < OCk, it is overcompressed. Show that. Note that the threshold values TH ₁ and TH ₂ may be fixed values or may be different values for each comparison circuit 14-k.

When the bit allocation pattern selector 17 receives the signal CPk from the comparison circuit 14-k, the bit allocation pattern selector 17 selects a bit allocation pattern BPk for which the corresponding data compression is appropriate.
Determine the bit allocation pattern that maximizes the compression rate among
The PC is supplied to the compression encoding circuit 8. When determining the bit allocation pattern with the maximum compression ratio, if the bit allocation patterns BP1 to BPK are determined in advance so that the compression ratio increases (or decreases) in this order, the condition of TH ₁ ≦OCk≦TH ₂ can be satisfied. The maximum value (or minimum value) of k among k that satisfies the pattern code PC may be used, and selection is easy. As a result, the orthogonal transformation data AD(i,j)
and the pattern code of the optimal bit allocation pattern.
PC is supplied to the compression encoding circuit 8.

FIG. 3 is a block diagram of the compression encoding circuit 8. Data AD (i, j) and pattern code PC
are transferred to the delay circuit 20 and buffer 21, respectively. Data AD(i,j) is delayed by the delay circuit 20 by a time corresponding to the data length of the pattern code PC (8 bits if the bit allocation pattern is 256 bits), and then transferred to the data selector 22. On the other hand, the pattern code PC is Batsuhua 21
is transferred from the data selector 22 to the data selector 22, and
It is also transferred to the memory controller 23. As a result, the data selector 22 first selects the pattern code.
The PC then outputs data AD(i,j).
Since the data length of pattern code PC is fixed,
By switching the output, the data selector 22 continuously outputs data AD(i,
j) to the shift register 26. Shift register 26 is parallel input/serial output.

On the other hand, the memory controller 23 reads the corresponding data length pattern from the data length storage memory 24 based on the pattern code PC, and sets it in the transfer clock generator 25. Like the bit allocation pattern memory 16, the data length storage memory 24 stores a bit allocation pattern BPk (i, j), and outputs the bit allocation pattern BP _PC (i, j) specified by the pattern code PC.

The transfer clock generator 25 generates the transfer clock based on the bit allocation pattern BP _PC (i, j).
Generates CK′. Since the shift register 26 shifts data and transfers it to the buffer 27 only when the transfer clock CK' is input, the transfer clock generator 25 first generates the transfer clock CK' for the bit length of the pattern code PC. After that, for each pixel data, image data AD (i, j)
The transfer clock CK' is generated only for a period corresponding to the bit length necessary for encoding among the 8-bit data. As a result, following the pattern code PC, only valid bit data of each image data according to the bit allocation pattern is transferred to the buffer 27, and a compressed image data string CD for each block is generated.

The structure of the compressed data string CD is shown in FIG.
As shown in Figure 6, the pattern code PC is placed at the beginning.
is written, and the bit length of the PC is fixed.

For example, if the prepared bit allocation pattern is
If there are 256 types, the pattern code PC will be 8 bits long. Image data AD(i,j) follows the pattern code PC. Here, the data length of the entire image data is variable, and the pattern code PC
This is a data length that corresponds one-to-one with , and is determined in advance. As an example, in pattern 2 shown in Figure 5, the bit length (sum of bit lengths of each data) is
It is 37 bits. Immediately after the pattern code PC, the (1,1) component of the image data AD(i,j) is written. In the example of pattern 2 described above, this corresponds to a length of 8 bits. Next, the (1,2) component is written with a length of 4 bits. Similarly, image data
Compression encoding of image data is achieved by successively writing components of AD(i,j) having an effective bit length specified by the bit allocation pattern. In the case of the bit allocation pattern of pattern 2, the pattern code is 8 bits long for the PC and the data array is 37 bits long, so that the block data of the original image is compressed to a total length of 45 bits. This means that the total data length of the original image is 8×8×
Since 8 bits = 512 bits, 37/512 =
This means that the data has been compressed to 7.2%.

By repeating the above processing for each block ^twice (M×N)/n times, all the original image data is converted into compressed data.

Conversely, in order to restore a compressed data string, the bit allocation pattern is called according to the first pattern code PC, and the subsequent data string is allocated to the image data matrix according to the data length of the bit allocation pattern. The original image data for each block is obtained by performing inverse transformation. This operation may be repeated (M×N)/n ^times in the same manner.

As described above, according to this embodiment, by calculating the overflow amount of the current image data in each bit allocation pattern, the compression ratio can be maximized based on this, and the optimal compression ratio can be calculated without losing any necessary data. A suitable bit allocation pattern can be selected in a short time.

Note that in the Hadamard transform, since components other than the (1,1) component have positive and negative signs in the data array after the transform, data to which one sign bit has been added may be used as the original image data AD.

Although one embodiment of the present invention has been described above, the present invention is not limited to the above-described embodiment and can be modified in various ways. for example,
Although a shift register is used to discard unnecessary bits, gates operating in parallel on all bits of converted data may also be used. Further, the orthogonal transformation is not limited to Hadamard transformation, and other types may be used. Furthermore, the above-mentioned functions may be implemented in software using a programmed microcomputer.

〔Effect of the invention〕

As explained above, according to the present invention, it is possible to provide an image data compression device that can quickly perform optimal bit allocation for a data array after orthogonal transformation by simply combining simple operations. .

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing a schematic configuration of an embodiment of an image data compression device according to the present invention, FIG. 2 is a block diagram of a bit allocation pattern selection circuit, FIG. 3 is a block diagram of a compression encoding circuit, and FIG. 5 shows an example of normalization of image data, FIG. 5 shows an example of a bit allocation pattern, and FIG. 6 shows a data structure after compression. 2...Data normalization circuit, 4...Orthogonal transformation circuit, 6...Bit allocation pattern selection circuit, 8...
...Compression encoding circuit, 11-1 to 11-k...Differential circuit, 12-1 to 12-k...Weighting circuit, 1
3-1 to 13-k...overflow counter, 1
4-1 to 14-k... Comparison circuit, 16... Bit assignment pattern memory, 17... Bit assignment pattern selector, 20... Delay circuit, 22... Data selector, 24... Data length storage memory, 2
6...Shift register.

Claims (1)

[Scope of Claims] 1. An image data compression device using orthogonal transformation, comprising: a storage means in which a plurality of bit allocation patterns representing the bit length allocated to each pixel are registered; and a data amount of image data after orthogonal transformation. computing means for calculating the difference between the bit allocation pattern and the allocation amount of each of the bit allocation patterns; a comparison means for determining whether the difference value for each bit allocation pattern is within an allowable range; An image data compression apparatus comprising selection means for selecting an optimal bit allocation pattern from among bit allocation patterns determined to be within an allowable range. 2. The image data compression apparatus according to claim 1, wherein the comparing means has a tolerance range specific to each bit allocation pattern. 3. The calculation means includes a difference means for performing a difference between the image data after orthogonal transformation and each bit allocation pattern for each pixel, and a difference means for multiplying the difference value for each pixel by a weighting coefficient according to the position in the matrix. 2. The image data compression apparatus according to claim 1, further comprising weighting means and means for totalizing the output of the weighting means for all matrices.