JPH0650912B2 - 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. In this case, image data compression is widely applied for the purpose of efficiently recording an image signal on a recording medium. ing.

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. As the orthogonal transform, a Fourier transform,
Cosine transformation, Hadamard (Hada)
mard transform, Karhunen-Lewe (Karhune)
Although n-Love transformation, Haar transformation and the like are often used, the above method will be described in more detail by taking 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 (0) and x in this block
When (1) and (1) are shown in an orthogonal coordinate system, they have a high correlation as described above, and therefore x (1) = x as shown in FIG.
Many are distributed near the straight line (0). Therefore, this orthogonal coordinate system is converted by 45 ° as shown in FIG. 3 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), x
It takes a value slightly larger than (1) (about √2 times), while y (1) indicating the high-frequency component of the original image data is y.
It is distributed only in a very narrow range near the (0) axis. Therefore, for example, if it is assumed that a code length of 7 bits is required for encoding x (0) and x (1),
For y (0), about 7 bits or 8 bits are required, while on the other hand, y (1) can be coded with a code length of, for example, about 4 bits, which eventually reduces the code length per block and reduces the 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, although the code length (the number of bits) is assigned according to a predetermined pattern, the number of bits required to show the conversion data of a certain sequence is different for each image and for each block, and therefore is assigned in advance. In some cases, the converted data cannot be represented accurately due to insufficient number of bits. In that case, the maximum value or the minimum value that can be represented by the number of allocated bits is used as the encoded data, but of course, the quality of the reproduced image obtained by decoding and inverse conversion deteriorates.
In order to avoid such a shortage of the number of bits, it is sufficient to set the predetermined number of allocated bits to be 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 at the same time, on the other hand, does not cause deterioration of the image quality of a reproduced image due to the shortage of the number of bits as described above. The purpose of the present invention is to provide a conversion method.

(Structure of the Invention) An orthogonal transform coding method for image data according to the present invention is an image in which orthogonal transform is performed on image data to obtain converted data as described above, and these converted data are each encoded with a unique number of bits. In the orthogonal transform coding method for data, based on the coded data of a block that has already been coded and the bit number distribution, the optimum bit number distribution in the block adjacent to the block is predicted, and the predicted bit number is calculated. According to the distribution, each of the conversion data of the adjacent blocks is encoded.

(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. For example, as shown in FIG. 5, this two-dimensional orthogonal transformation is performed for each rectangular block B of the sample number (image number) M × N in the halftone image F indicated by the image data x.
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. That is, M × in the 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 M × N transformed data 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 orthogonal transformation in each block B as shown in FIG. 4 (for example, the Wash function in the Hadamard transform, the trigonometric function in the Fourier transform, etc.).
The sequence is arranged vertically and horizontally. As mentioned above, this sequence corresponds to the spatial frequency, so
The converted data y are arranged in the block B in the order of spatial frequency in the vertical and horizontal directions (that is, in the order of density of detail components of the image).
Will be lined up. 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, the conversion data y (1,1) is in the block B. Is the average image density.

The converted data y arranged in this way is sent to the encoding circuit 12 and encoded. The encoding of the converted data y in the encoding circuit 12 will be described below with reference to FIG. As shown by the arrow A in FIG. 5, this encoding is
The blocks B are sequentially performed in the order of arrangement. This encoding is n
The block to be performed next is denoted by B (n). The encoding circuit 12 stores a predetermined allocation bit allocation table T _{1 in,} for example, a ROM, and the conversion data y in the block B (1) in which encoding is performed first follows the allocation table T ₁ . Encoding is performed with the code length (the number of bits) (step P1). The bit allocation table T ₁ is, for example, as shown in FIG. 4, in which a unique number of bits is allocated to each sequence, and as described above, the converted data y has energy concentrated in the low frequency component. By giving a relatively long code length to the low-frequency component with high energy and a relatively short code length to the high-frequency component with low energy, the number of bits required per block B is reduced, and the image data Compression is achieved. As will be described later, another bit allocation table T ₂ is created later, but when the conversion data y in the first block B (1) is encoded, the bit allocation table T 2 stored in the ROM is stored. ₁ is selected in step P2 and used for encoding.

The data f (y) coded in this way is output from the coding circuit 12 as coded data for the block B (1). At the same time, the encoded data f (y)
Is sent to step P3 and is used to identify exactly what code length is required to encode each transformed data y. For example, it is assumed that the conversion data y of a certain sequence has the number of allocated bits defined by the bit allocation table T ₁ of 4 bits. Then, as shown in the table below, the conversion data y having 16 values from a minimum of -8 to a maximum of +7 is encoded by the 4-bit binary number.

As described above, the conversion data y of the sequence in which the above 4 bits are allocated in the block B (1) is
It may happen that the value is too large or too small to be represented by the code length of bits. So in the above example,
When the converted data y takes a value of -9 or less or 8 or more, the data y cannot be accurately represented by 4-bit data and is encoded as "1000" and "0111", respectively. Therefore, with respect to the sequence that has become such encoded data, for example, 1 bit is further expanded to 5 bits, and this is written in the bit allocation table T _{2 including} , for example, RAM (step P4). When the encoded data is “1000”, it is impossible to determine whether the value of the converted data y before encoding is −8 or −9 or less. Therefore, for safety, in this case Extend the length. The same applies when the encoded data is "0111". On the other hand, on the other hand, for example, the converted data y is 0,
When the value of 1 is taken, the data y can be represented by 2 bits, and the converted data y having the values of 2 and 3 can be represented by 3 bits. Therefore, with respect to the sequence of such encoded data, 2 bits and 1 bit are respectively shortened to 2 bits and 3 bits, which are written in the bit allocation table T ₂ in the same manner as described above.

Transformed data y of block B (2), which is the second in the encoding order
At the time of encoding, the bit allocation table T ₂ created as described above is switched so as to be used for encoding (step P2). This state is maintained until coding is completed for all blocks B. Further, since the code length identification in step P3 and the writing (rewriting) in step P4 are sequentially performed until the end,
Eventually, the conversion data y of the sequence k of the block B (n) to be encoded in the nth is the previous block B.
The coded data f (y) having the sequence (n-1) and the sequence k is encoded with the expected code length. Since the image data in the block B (n) and the image data in the block B (n-1) that are adjacent to each other have a strong correlation, the code length predicted as described above corresponds to each conversion data in the block B (n). There will be no significant excess or deficiency in encoding y. Note that FIG. 4 shows an example of changing the code length described above. The arrows a and b indicate the sequence in which the code length is extended and shortened, respectively.

Image data f (y) coded as described above
Is recorded in a recording medium (image file) such as an optical disk or a magnetic disk in the recording / reproducing device 13. 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, this image data f (y) is read from the recording medium and is combined in the decoding circuit 14 into the converted data y. The transformed data y thus decoded is sent to the inverse transformation circuit 15 and undergoes the inverse transformation of the two-dimensional orthogonal transformation. 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.

In the above embodiment, the optimum number of bits for each converted data y of the block B (n) is predicted from the coded data of the block B (n-1) which is one before in the coding order. However, the optimum number of bits can be predicted from the coded data of other blocks. For example, when each block B is encoded in the order of arrow A'as shown in FIG. 7, block B (n-m) [m Number of columns in block B]
, Block B (n-m-1), block B (n-m +)
The optimum number of bits can be predicted from the encoded data of 1).

(Effects of the Invention) As described in detail above, in the orthogonal transform coding method for image data of the present invention, when coding the orthogonal transform data, the number of bits relating to each data is used as the already obtained coded data. Then, it is possible to set the optimum length without excess or deficiency. Therefore, according to the method of the present invention, it is possible to prevent the quality of a reproduced image obtained by decoding and inverse conversion from being deteriorated due to a shortage of the number of bits, and reduce the amount of encoded data to the maximum. , The data compression rate can be greatly increased.

[Brief description of drawings]

FIG. 1 is a block diagram showing a schematic configuration of an apparatus for carrying out a method of an embodiment of the present invention, FIGS. 2 and 3 are explanatory diagrams for explaining orthogonal transformation according to the present invention, FIGS. 4 and 5 Is an explanatory view for explaining the method of the present invention, FIG. 6 is a flow chart showing a flow of an encoding process of orthogonal transform data in the apparatus of FIG. 1, and FIG. 7 is an explanation of the method of the present invention in another encoding order. FIG. 11 ... Orthogonal transformation circuit, 12 ... Encoding circuit B, B (n), B (n-1) ... Block of image data x ... Original image data, y ... Transformation data f (y). Encoded image data

Claims (1)

[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 an orthogonal transform coding method of image data to be coded with a unique number of bits, respectively, based on the coded data of the already coded block and the bit number distribution, the optimum bit in a block adjacent to the block A method for orthogonal transform coding of image data, which predicts a number distribution, and codes each transform data of the adjacent blocks according to the predicted bit number distribution.