JPH0681307B2 - Orthogonal transform coding method for image data - Google Patents

Description

Description: FIELD OF THE INVENTION The present invention relates to an image data encoding method for data compression, and more particularly to an image data encoding method using orthogonal transformation.

(Technical Background of the Invention and Prior Art) Since an image signal carrying a halftone image, such as a TV signal, has an enormous amount of information, its transmission requires a wide band transmission line. Therefore, conventionally, attention has been paid to the fact that such an image signal has large redundancy, and various attempts have been made to compress the image data by suppressing this redundancy. Recently, it has been widely practiced to record a halftone image on, for example, an optical disk or a magnetic disk, and in this case, image data compression is widely applied for the purpose of efficiently recording an image signal on a recording medium. There is.

As one of such image data compression methods, a method using orthogonal transformation of image data is well known. In this method, the digital two-dimensional image data is divided into blocks each having an appropriate number of samples, and a numerical sequence consisting of sample values is orthogonally transformed for each block, and energy is concentrated on a specific component by this transformation. The large component of is encoded (quantized) by assigning a long code length, while the low energy component is roughly encoded with a short code length,
The number of codes per block is reduced. The orthogonal transform may be a Fourier transform, a cosine transform, a Hadamard transform, a Karhunen-Loeve transform, or a Haa transform.
Although r) transformation and the like are often used, the above method will be described in more detail here by taking the Hadamard transformation as an example. First, as shown in FIG. 2, the block is formed by dividing digital two-dimensional image data into two pieces in a predetermined one-dimensional direction. Two sample values x in this block
When (0) and x (1) are shown in an orthogonal coordinate system, they have a high correlation as described above, and therefore x as shown in FIG.
There are many distributions near the straight line (1) = x (0). Therefore, this Cartesian coordinate system is set to 45 ° as shown in Fig. 3.
Transform to define a new y (0) -y (1) coordinate system.
In this coordinate system, y (0) represents the low frequency component of the original image data before conversion, and y (0) is x
(0), a value slightly larger than x (1) However, on the other hand, y indicating the high frequency component of the original image data
(1) is distributed only in a very narrow range near the y (0) axis. So, for example, x (0), x (1) above
If a code length of 7 bits is required for each encoding of y, 0 or 7 bits are required for y (0), while y (1) has a code length of, for example, 4 bits. As a result, the code length per block is reduced, and image data compression is realized.

The quadratic orthogonal transformation that forms one block for each two image data has been described above. However, as the order is increased, the energy tends to concentrate on a specific component, and the effect of reducing the number of bits is increased. You can Generally, the above transformation can be performed by using an orthogonal function matrix. In the limit, if the eigenfunction of the target image is selected as the orthogonal function matrix, the transformed image becomes the eigenvalue matrix, and the matrix pair The original image can be represented only by the corner components. Further, in the above example, the image data is grouped into blocks only in the one-dimensional direction, but this block may be composed of several image data in the two-dimensional direction. A more significant bit number reduction effect can be obtained than in the case.

The transformation data obtained by the above-mentioned two-dimensional orthogonal transformation is the sequence (0) of the orthogonal functions used for transformation in each block.
(Number crossing) is arranged in order. Since this sequence corresponds to the spatial frequency, each conversion data is arranged in the order of frequency in the vertical and horizontal directions as shown in FIG. Therefore, a relatively long code length is assigned to the transform data (data on the upper left side in FIG. 4) that bears the low-frequency component (a long code length was assigned to y (0) in the above-described one-dimensional second-order orthogonal transform). The corresponding code length per block is reduced by assigning or truncating a relatively short code length to the converted data (data on the lower right side in FIG. 4) that carries the high frequency component.

By the way, conventionally, the code length is assigned according to a predetermined pattern, but since the code length required to show conversion data of a certain sequence is different for each image and for each block, it is assigned in advance. In some cases, the code length is insufficient and the converted data cannot be represented accurately. In that case, the maximum value or the minimum value that can be represented by the assigned code length is used as the encoded data, but of course, the quality of the reproduced image obtained by decoding and inverse conversion will deteriorate. In order to prevent such a shortage of code length, it is sufficient to make the predetermined assigned code lengths sufficiently long, but if this is done, the image data cannot be compressed sufficiently.

(Object of the invention) Therefore, the present invention is capable of sufficiently increasing the data compression rate, and on the other hand, it is possible to minimize the deterioration of the image quality of the reproduced image due to the insufficient code length as described above. An object is to provide an encoding method.

(Structure of the Invention) As described above, the orthogonal transform coding method for image data according to the present invention obtains transform data by subjecting image data of each block to orthogonal transform, and codes these transform data with a unique code length. In the orthogonal transform encoding method of image data to be converted, the transform data regarding the same sequence is extracted from each block, the average value of the absolute value of the transform data is obtained for each sequence, and the code length for the transform data of each sequence is calculated. It is characterized in that each is determined based on the average value.

(Embodiment) Hereinafter, the present invention will be described in detail based on an embodiment shown in the drawings.

FIG. 1 schematically shows an apparatus for carrying out the orthogonal transform coding method for image data according to the present invention. The image data (original image data) x indicating the halftone image is first obtained by the preprocessing circuit 10.
And undergoes preprocessing such as smoothing for noise removal to improve data compression efficiency. The image data x subjected to this pre-processing is passed through the orthogonal transformation circuit 11 and first subjected to two-dimensional orthogonal transformation. This two-dimensional orthogonal transformation is performed for each rectangular block B of the number of samples (number of pixels) MXN in the halftone image F indicated by the image data x, as shown in FIG. 5, for example.
As the orthogonal transform, for example, the Hadamard transform described above is used. This Hadamard transform can be executed by a simpler transform circuit than other orthogonal transforms because its transform matrix consists of only +1 and -1. Further, as is well known, the two-dimensional orthogonal transform can be degenerated into the one-dimensional orthogonal transform. In other words, the MX in the above two-dimensional block B
Two-dimensional orthogonal transformation is performed by subjecting image data relating to N pixels to one-dimensional orthogonal transformation in the vertical direction and further subjecting the obtained transformed data of MXN to one-dimensional orthogonal transformation in the horizontal direction. The order of conversion in the vertical direction and the conversion in the horizontal direction may be reversed.

Transformation data y obtained by the above two-dimensional orthogonal transformation
Is the function that is the basis of the above orthogonal transformation in each block B as shown in FIG. 4 (for example, in the Hadamard transformation,
Walsh function, in the Fourier transform, trigonometric functions, etc.) are arranged in the vertical and horizontal directions in the order of sequence. As described above, since this sequence corresponds to the spatial frequency, the converted data y is arranged in the block B in the order of spatial frequency in the vertical and horizontal directions (that is, in the order of the density of detail components of the image). In FIG. 4, the conversion data y (1,1) in the leftmost column of the top row corresponds to the sequence 0 (zero), and as is well known, this conversion data y (1,1)
1) shows the average image density in the block B.

The converted data y arranged in this way is sent to the encoding circuit 12 and encoded as shown in FIG. The encoding circuit 12 encodes each conversion data y in the block B with a code length (the number of bits) according to the allocation bit allocation table created as described later. For example, as shown in FIG. 6, the bit allocation table is one in which a unique number of bits is allocated for each sequence, and as described above, the conversion data y has energy concentrated in the low frequency component. A relatively long code length is given to low-frequency components with high energy,
On the other hand, by giving a relatively short code length to the high-frequency component having low energy, the number of bits required per block B is reduced and image data compression is achieved.

Here, in the above bit allocation table, if the number of allocated bits for each converted data y is short, the quality of the reproduced image is impaired as described above. Conversely, if the number of allocated bits is too long, a sufficient data compression effect is obtained. I can't. Hereinafter, a characteristic part of the method of the present invention which solves such a problem will be described. The encoding circuit 12 extracts the conversion data y having the same sequence from all the blocks B (seventh).
The figure shows how the conversion data y of sequence 0 is extracted). This data extraction is done for all sequences. Then, the encoding circuit 12 obtains the average value m of the absolute values of the extracted converted data y, obtains the code length (the number of bits) based on the average value m of the absolute values, and relates the number of bits to the sequence. The code length. That is, the code length obtained based on the average value mn of the conversion data y of the sequence n extracted from each block B is set as the code length regarding the sequence n (note that the value of mn may be obtained for each image. , May be obtained from some predetermined standard images). In this way, the number of bits Db based on the average value m of absolute values is obtained as, for example, Db = [log ₂ (2m + 1)] (however, the fractional part is rounded off). Conversion data y with the same sequence
Are often close to each other, their distribution is as shown in FIG. In FIG. 8, σ is a standard deviation, and the average value m of the absolute values is empirically close to the standard deviation σ. Therefore, there is no deficiency in the value twice this average value m (in the above formula, if the value of m is less than 0.5, the Db value becomes negative, so 1 is added to 2m to prevent it). The code length is long enough for most of the conversion data y of the sequence n. By performing the above operation for all the sequences, the bit allocation table as shown in FIG. 6 can be obtained.

It should be noted that, of the conversion data y of the sequence n, the one having a particularly large value or the one having a small value cannot be accurately encoded with the above-mentioned number of bits Db, but with respect to the conversion data y clipped at the time of encoding. It is also possible to eliminate this inconvenience by appropriately expanding the code length by a predetermined length.

Note that, especially when such code length extension is not performed, it is desired to avoid that the converted data y in the low frequency region including important image information is clipped and coded, so that the sequence is equal to or less than a predetermined value. The code length of the converted data y may not be determined by the above method, but may be encoded by a predetermined code length having a sufficient margin.

The image data f (y) coded according to the bit allocation table determined as described above is recorded in a recording medium (image file) such as an optical disk or a magnetic disk in the recording / reproducing apparatus 13 as shown in FIG. Will be recorded. As described above, since the image data f (y) is significantly compressed with respect to the original image data x, a large amount of images can be recorded on the recording medium such as an optical disk. At the time of image reproduction, the image data f (y) is read from the recording medium and is decoded by the decoding circuit 14 into the converted data y. The transformed data y thus decoded is sent to the inverse transform circuit 15 and subjected to the inverse transform of the two-dimensional orthogonal transform. As a result, the original image data x is restored, the original image data x is sent to the image reproducing device 16, and the image carried by the data x is reproduced.

As is well known, the conversion data y of the sequence corresponding to the low spatial frequency (the sequence in the upper left of FIG. 6) y, especially the conversion data y (1,1) of the sequence 0 (zero) is used for reproducing the original image. Since it is particularly important, it is desired to avoid clipping of these converted data y during encoding as much as possible. Therefore, as described above, the process of determining the code length for the converted data y based on the average value of the absolute values of the data y is performed only for the sequence corresponding to the spatial frequency equal to or higher than a predetermined value, and the processing of the low value less than the predetermined value is performed. Regarding the sequence corresponding to the spatial frequency, the converted data y
May be set to a length required to represent the maximum value of the data y that can be taken in each sequence. The conversion data y that can be taken in each sequence
The maximum value of can be obtained experimentally and empirically,
It can also be obtained from the dynamic range of pixel values and the block size.

(Effects of the Invention) As described in detail above, in the orthogonal transform coding method for image data of the present invention, when the orthogonal transform data is coded, the code length relating to each data is not unnecessarily too long, and on the other hand, it is largely insufficient. It is possible to set the optimum length that does not occur. Therefore, according to the method of the present invention, while preventing the image quality of the reproduced image obtained by decoding and inverse conversion from deteriorating due to insufficient code length,
The amount of encoded data can be reduced to the utmost and the data compression rate can be greatly improved.

[Brief description of drawings]

FIG. 1 is a block diagram showing a schematic configuration of an apparatus for carrying out a method according to an embodiment of the present invention, FIGS. 2 and 3 are explanatory diagrams for explaining orthogonal transform according to the present invention, and FIGS. 7 and 8 are explanatory views for explaining the method of the present invention. 11 ... Orthogonal transform circuit, 12 ... Encoding circuit B ... Image data block, x ... Original image data y ... Transformed data f (y) ... Encoded image data

Claims (3)

[Claims] 1. Two-dimensional image data is subjected to orthogonal transformation for each block based on a predetermined orthogonal function, and after this transformation, the transformed data arranged in the sequence of the orthogonal functions in the block is received. In the orthogonal transform coding method of image data to be coded with each unique code length, the above-mentioned transform data regarding the same sequence is extracted from each block, and the average value of the absolute values of the transform data is obtained for each sequence. An orthogonal transform coding method for image data, characterized in that the code lengths of the sequence transform data are determined based on the average values, respectively. 2. The process of determining the code length based on the average value is performed in a sequence corresponding to a spatial frequency equal to or higher than a predetermined value, and the code length is determined in a sequence corresponding to a spatial frequency lower than a predetermined value. The orthogonal transform coding method for image data according to claim 1, wherein the length is set to represent a maximum transform data value that can be taken in each sequence. 3. The orthogonality of the image data according to claim 1 or 2, wherein the code length is substantially equal to a value twice the average value. Transform coding method.