JPS6167370A - Gradation picture coding and decoding method - Google Patents

Abstract

PURPOSE:To attain reproduction with good picture quality by sampling density information, coding it, interpolating it into information with higher picture element density than a sampled picture element density and then applying dither so as to encode a gradation picture efficiently. CONSTITUTION:When input density information IN is inputted to a coding section 100, the input density of each picture element of the gradation picture is sampled with a low resolution at coding and the result is outputted to a decoding section 200 as a code string C. A controller B201 in a decoding section 200 uses an identification code discriminating circuit 202 to discriminate a received code and then uses an interpolation circuit 207 to apply interpolation based on the regenerated density and uses a dither circuit 208 to apply binary- coding top interpolated density information.

Description

Detailed Description of the Invention (Industrial Field of Application) The present invention efficiently encodes a gradation image by suppressing redundancy, and further converts this code into a binary image using a dither method to reproduce the gradation image. Regarding encoding/decoding methods.

(Prior Art) A dither method is conventionally known as a method for pseudo-expressing an image having gradation with two types of density, white and black. As a document describing this disa method, International
onal Conference on Commun
cation.

Conference Record volume
1 + 1973 P, 26 el 1- P, 26・
15, but as described in this document, the dithering method involves binarizing the original image using different threshold values depending on the pixel position, and creating a pseudo intermediate image by using the density ratio of black pixels and white pixels. It expresses the tone. Next, the dither method will be further explained using FIGS. 2, 3, and 4. FIG. 2 shows the position of each pixel in the original image and its density information. For example, one pixel block consists of 4 rows x 4 columns, and the main scanning direction position within one pixel block is h=o,
The positions in the sub-scanning direction of 1, 2, and 3 are v=o, 1°2.3, and the density of each pixel is represented by 16 levels of gradation from 0 to 15. Figure 3 shows a 4x4 dither threshold matrix, and when the original image shown in Figure 2 is binarized using the threshold matrix in Figure 3, it is binarized as shown in Figure 4. An image is obtained. Here, Figures 2 and 3
In the figure, O is the whitest level, 15 is the blackest level, and in FIG. 4, 0 is white and ■ is black.

By the way, Modified Huffman (hereinafter abbreviated as Ding), which is one of the run-length encoding methods, has been proposed by the CCITT (Consultative Committee for International Telegraph and Telephone) as an encoding method for suppressing redundancy for binary images of black and white. ) The specific content of the recommended encoding method is, for example, published by the Institute of Electronics and Communication Engineers.
Basics and Applications of New Edition Facsimile” (September 10, 1972)
) Written in IEICE P, 390-393. This method utilizes the statistical properties of document images in which white pixels are relatively long and black pixels are relatively short, resulting in highly efficient encoding.

The MH encoding method is a run-length encoding method for binary images such as characters, but the bit interleaving method is a method devised for efficiently encoding dithered images. A document describing this bit interleaving method is Proceeding of
the S, 1. D, + 17 [2] 5econ
dQuarter (1976) (US) P, 92-
As described in this document, the bit interleaving method is a method of rearranging pixels so that pixels with similar threshold values are continuous and performing run-length encoding such as MH encoding.

(Problem to be solved by the invention) However, as shown in FIG.
Since a value image has a high probability of generating short white runs or long black runs, high efficiency cannot be obtained even if the value image is encoded using the MH method. For example, in an image with gradation, the third
Dithered image (main scan 1) using IJ
When MH encoding is used for 728 pixels and 2290 sub-scan lines), a code of 6.277,409 bits is generated, and the original image 1728 x 2290 = 3,957,12
This has the disadvantage that it is approximately 1.6 times as large as a 0 bit, making the encoding meaningless.

By the way, the above gradation image is bit-interleaved every four pixels by the bit-interleaving method, and M
When H-encoded, it was 1,316,897 bits, which was about 033 times the original image.

However, the data transfer rate in a facsimile that uses a normal telephone line is about 9,600 bits per second, and even if the above-mentioned bit interleaving encoding is performed at this speed, the transmission time will be about 137 seconds. There was a need for efficient compression and encoding to enable high-speed transfer. Therefore, the present invention provides a gradation image encoding/decoding method that enables high-speed transmission by efficiently compressing during encoding, and enables high-quality reproduction by performing decoding, interpolation, and dithering during decoding. It is about providing.

(Means for Solving the Problems) The present invention provides that, at the time of encoding, the density information of each pixel of a gradation image is encoded and transmitted at a first pixel density lower than the original pixel density, and then decoded. Sometimes, after decoding the code and reproducing density information, the density information is interpolated to a second pixel density that is higher than the first pixel density, and binarized by dithering at the second pixel density. It is.

(Operation) According to the present invention, since the input density information of each pixel of a gradation image is sampled and encoded at a low resolution during encoding, high-speed transmission is possible, and during decoding, the input density information is decoded. Then, after interpolating to a high resolution, the image is binarized by dithering and then reproduced, making it possible to reproduce the image with high quality.

(Embodiment) FIG. 1 shows a gradation image code, which is a first embodiment of the present invention.
This figure shows a block diagram of a decoding device, and will be explained in detail below based on FIG. 1.

In FIG. 1, 100 is an encoding section, and 200 is a decoding section. This encoding unit 100 is a controller A
101, memory AlO2, address counter A703,
MH encoding circuit 104, memory B105, address counter B106, counter 107, identification code generation circuit 10
8. Consists of selector A109. The decoding unit 200 also includes a controller 8201, an identification code discrimination circuit 202, a decoding circuit 203, a selector B2θ4, and a memory C205.
, an address counter C206, an interpolation circuit 207, and a dither circuit 20EI.

The operation of this embodiment will be explained next. First, image reading information detected by an image reading means (not shown), that is, input density information IN quantized to 4 bits for each image, is input to the encoding section 100.

For example, if the number of pixels per line to be read is 1728 pixels, the input density information IN for 1728 pixels/1 line is 4 each.
Bits are input sequentially. Here controller Al0I
Under the control of, from among these pixels, pixels corresponding to every row, for example, the row at the position f v = 0 in FIG. 2, and pixels every fourth column in the corresponding row, for example h=
Only the input density information IN of 432 pixels/row corresponding to the column at position o is sampled and stored up to 4 bits of 1 in the memory AlO2. Next, only the bit with the largest weight is extracted from the input density information of each pixel in the first row stored in the memo IJ AZ 02. For example, if the input density information of v=O, h=O is extracted from the input density information of FIG. 2, it becomes 1.10.15... If this is expressed in binary numbers, it will be as shown in Figure 5. Among these bits, the bits with the highest weight are 0.1, 1, etc., as shown by the MSB in FIG. ...
becomes. For this bit string, M H encoding circuit 104
MH encoding is performed using This MH encoding circuit 104
The Ml'i code generated in is stored in memory B105. At this time, the number of bits of the MH code is counted by the color/reader 107, and when the encoding of one row of original information, that is, 432 bits, is completed, the count value for one row is output to the controller A101. The controller 8 101 compares this value with the 432 bits of the original information to see if it is a dog, and if it is a dog, it causes the identification code generation circuit 108 to generate an identification code B that sends the original information as it is, and then outputs the memo IJA 102.
The original information of 432 bits is sent to the decoding section 200 via the selector A109. When the count value of the counter 107 is smaller than 432 bits, after the identification code generation circuit generates the identification code A which sends the MH code,
The MH code in memory B105 is sent to decoding section 200 via selector A109.

In FIG. 5, the above encoding is performed in the bit, g, and g rows 0, 0, one position to the right of MGB. The same process is performed for L, . . . , and then the bit strings 0, 1, 1, . . . 'The same process is performed, and finally the bit string with the smallest weight, that is, the bit string l, 0° 1, . . . indicated as LSB in FIG. 5, is encoded. In this way, the topmost v=
0. When the encoding of the row h=0, 1, 10° 15, . O
, . . . are encoded in the same way. Repeat this below,
Finish encoding all pages.

FIG. 6 illustrates the order of the code string C (output of the encoding unit 100) obtained by the above operation.

In the example shown in FIG. 6, it is assumed that the number of bits of the MH code is smaller than 432 in the upper two bit strings of the four weighted bit strings, and it is assumed that the number of bits of the MH code is smaller than 432 in the lower two bit strings. A is an identification code indicating that it is an MH code,
C, , C2 are code strings obtained by MH encoding the bit strings of the most significant and one digit below the most significant bit string, respectively. Still, B is an identification code indicating that it is original information, and D3+D4 are the bit strings one above the lowest and the lowest, respectively, extracted as they are. This code string C is transmitted to the decoding unit 20θ
is input.

In the decoding unit 200, the controller B 201 does not select the received code using the identification code discriminating circuit 202.
It is determined whether the MH code string shown by A and B in the figure is the original information or the original information. As a result, if MH code string, MH
The decoding circuit 203 is used to reproduce 432 bits of the original bit string information. At this time, the controller B201 instructs the selector B204 to select this playback information as memory input. If the discrimination result of the identification code discrimination circuit is still the original information, the controller 820 selector B2
04 to select this raw information as memory input. The information selected by selector B204 in this manner is sequentially stored in memory C205 according to address counter C2θ6. Similar to the above-mentioned encoding, the above operation is performed four times for one row from the bit string with the highest weight to the bit string with the lowest weight. Repeat this for the corresponding digits and when all pages have been decoded, the memo IJC
Input density information of pixels at positions v=o, h=o in every fourth row and every fourth column as shown in FIG. 5 is stored in 205.

Next, the controller B 201 uses the interpolation circuit 207 to
Interpolation is performed based on the density reproduced every ×4 period. The interpolation function is written by William K. Pratt,
”Digital Image Process
ng'+ (1978) John Wi Iey &
As described in pages 113 to 114 published by 5ons, there are 0-order interpolation, 1-order interpolation, 2-order interpolation, etc., but here we will discuss the case where 1-order interpolation is performed in the main scanning direction and 0-order interpolation is performed in the sub-scanning direction. explain. The memo IJC 205 stores input density information 1°10.15 for pixels at positions y=Q, h=o in every fourth row and every fourth column. For this information, it is assumed that the densities correspond to the positions v=o and h=o in FIG. performs zero-order interpolation, that is, interpolation using the same values in four rows. The result is as shown in Figure 7. This interpolated density information is binarized using a dither circuit 20B. The dither circuit 20g performs binarization using the threshold matrix shown in FIG. 3, and the result of this binarization is shown in FIG. The reproduction output OUT of the binary image reproduced in this way does not necessarily match the image shown in FIG. 4, but since images with gradation generally have little sudden change in density, Even when encoding is performed using the above-mentioned method, practically necessary information can be preserved with a resolution of about 8 pixels/III+I+ used in facsimile, for example.

Note that the results of performing the above-mentioned high-speed encoding according to this embodiment on the gradation image used in the description of the conventional technique are as follows. First, 572 rows are extracted every fourth row out of 2290 rows and encoded for each weight bit string. First, 563 out of 572 rows of the bit string with the highest weight were MH encoded, 496 rows of the next bit string, 116 rows of the next bit string, and 27 rows of the bit string with the lowest weight were MH coded. As a result, the total code length is 666,310 bits, which is about 0.51 times that of the bit interleaving method. Therefore, at a data transfer rate of 9600 bits per second, it is possible to transmit data in approximately 69 seconds.

In this embodiment, the encoding unit 100 and the decoding unit 200 are shown as separate blocks, and the case where they are directly connected is shown, but the encoding unit ZOO and the decoding unit 200 are This also includes cases where connections are made via transmission paths such as lines. Furthermore, when the encoding section 100 and the decoding section 200 are provided in the same housing, it is also possible to share one controller, the controller 820 and the controller B20Z. Furthermore, as a second embodiment of the present invention, the encoding unit 100 may sample in a staggered manner, and the decoding unit 2θ0 may also perform interpolation and desaturation in a staggered manner. In this case, as shown in FIG. 9, since the sampling points of the density information are staggered, the effect of improving visual naturalness and intelligibility can be obtained.

Furthermore, as a third embodiment, the upper specific number of digits (for example, 2 digits) of the weight of the input density information is MH encoded, and the lower specific number of digits (for example, 2 digits) uses the original bit string as its IT code. It is also possible to set it fixedly like this. In this case, the counter 107 of the encoding section 100 becomes unnecessary. The reason for doing this is that, according to our experimental results, it has been found that the MH code of a bit string with a large weight has a short code length.

By the way, in the above, by sampling the input density information of each pixel, the positions of v=o and h=O in each pixel block are also sampled.
Although we have explained the case where the input density information is extracted and encoded/decoded, it is also possible to extract the input density information of a pixel at any other position in each pixel block, or It is also possible to calculate the average of the input density information of a predetermined number of pixels or all pixels and use it as an extraction target. The sampling period for the input density information to be encoded may be short if high image quality is desired, or long if low image quality is acceptable. Therefore, it is also possible to prepare a plurality of sampling periods in advance and select the sampling period according to the required image quality.

(Effects of the Invention) As explained above, in this invention, density information is sampled and encoded, and after decoding, it is interpolated to a pixel density higher than the original sampling pixel density, and then desaturation is performed. It has the advantage of being able to efficiently encode gradation images and reproduce them with very good image quality, and can be used as a gradation image encoding/decoding device in facsimiles, still image transmission devices, innotal image file devices, etc.

[Brief explanation of the drawing]

Figure 1 is a block diagram of the first embodiment of the present invention, Figure 2 is a diagram showing the density information of each pixel of the original image, and Figure 3 is a 4x4
Figure 4 is a diagram showing an image binarized by the dither method, Figure 5 is a diagram showing the dither threshold matrix of v=o,
Figure 6 is a diagram showing the code string C in binary representation of the density information at the position h=o, Figure 7 is a diagram for explaining interpolation during decoding, and Figure 8 is a diagram showing the dithering during decoding FIG. 9 is a diagram for explaining the dither period in the second embodiment of the present invention. 100... Encoding unit, 10... Controller A11
02...Memory A, 103...Address counter A
1104...MH encoding circuit, 105...Memo'JB
%106...Address counter B, 107...Counter, 108...Identification code generation circuit, 109...Selector A1200...Decoding unit, 20 control port 7B
z2θ2...Identification code discrimination circuit, 2θ3...MH
Decoding circuit, 204...Selector f3, 20.5...
・Memory C120T6...Address counter C, 20
7...Interpolation circuit, 208...Dither circuit. Patent Applicant: Oki Electric Industry Co., Ltd. Procedural Amendment 60.3.27 Showa Year, Month, Day

Claims (2)

[Claims] (1) In a gradation image encoding/decoding method that binarizes and reproduces a gradation image by dithering, during encoding, the density information of each pixel of the gradation image is sampled at a first pixel density and encoded. At the time of decoding, the code is decoded to reproduce the density information, and then the density information is interpolated to a second pixel density that is higher than the first pixel density, and binarized by dithering at the second pixel density. A gradation image encoding/decoding method characterized by: (2) Encoding is performed by constructing a bit string for each bit at the same position in the bit information representing the density information of each pixel for the density information of each pixel sampled in a predetermined unit, and creating a run length for each bit string. The bit length of the encoded run-length code is compared with the bit length of the original bit string, and the shorter one is selected as the code to be transmitted.Decoding of the code and reproduction of the density information are transmitted. It is characterized by determining whether the code is a run-length code or an original bit string, decoding only if it is a run-length code, and reproducing the density information of each pixel from the decoded run-length code or original bit string. do. A gradation image encoding/decoding method according to claim 1.