JPH0113673B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to an image information encoding method for optimally encoding image information that is sampled in units of pixels and subjected to multilevel quantization.

In general, in image input/output devices such as facsimile machines, when transmitting the image information read by scanning and sampling the original image pixel by pixel on the input side to the output side, data compression is performed. How can we improve transmission efficiency through encoding, reduce storage capacity when it is necessary to store the data, and reproduce high-resolution, high-quality images on the output side? The big question is whether it can be done.
In this case, in order to improve the resolution of images such as characters and line diagrams that are reproduced by binary output, it is necessary to increase the sample rate on the input side or perform multi-value quantization of the read image information. In any case, the amount of information transmitted to the output side tends to increase, and there is a strong demand for improvement in data compression.

Conventionally, when encoding a document image consisting only of white and black levels, encoding is performed using the number of consecutive pixels of the same code (run length) in image information expressed in binary. Run-length encoding is widely used, but although this method has a good data compression rate, it cannot express halftones, so it is difficult to reproduce data based on the encoded data. The quality of the images, especially the resolution, has deteriorated. In other words, when reading the boundary between white and black, the white,
Since it is recognized as a halftone depending on the proportion of black, if you binarize it using a certain threshold and reproduce the image, information will be lost and unevenness will occur at the border. In addition, especially in a document image such as a handwritten character whose density changes rapidly, a low density part will be reproduced at a white level.

Furthermore, conventionally, in order to encode image information expressed in multi-values, a differential encoding method has been widely adopted in which, for example, the difference from the previous pixel is encoded according to each gradation level. In this case, it is possible to encode halftones, but since the state of change in the density level is simply expressed at each pixel, not only is the data compression rate poor, but also the sudden change in density level is The quality of the reproduced image deteriorates because it is unable to follow the fluctuations.

On the other hand, recently, in ^multi -value quantized image information, for ^example , as shown in ^FIG . use,
Focusing on the number of consecutive bits in the "1" or "0" state in the bit pattern when looking at each weight of 2 ⁰ , 2 ¹ , and 2 ² , we can calculate a run for each weighted bit pattern. An encoding method has been proposed that aims to improve data compression by length encoding (Japanese Patent Application Laid-open No. 1973-
58705).

However, such encoding methods are not only unsuitable for documents with sharp changes in shading, such as document images with handwritten characters, but also provide multivalued information to images that are mostly composed of white and black levels. Things have become wasteful.

The present invention has been made in consideration of the above points, and
When encoding image information read pixel by pixel at multi-tone density levels, it is necessary to encode original images with sharp density changes such as handwritten documents, especially images containing signatures or ink stamps. The purpose of the present invention is to provide an image information encoding method with excellent data compression rate, which is suitable for cases where it is desired to faithfully reproduce the characteristics of seals and seal impressions.

The image information encoding method according to the present invention uses the following two requirements as its basic encoding rules.

1. Continuous portions of the same density level in image information read at multiple gradation levels are subjected to run-length encoding. Note that for run length encoding, a general Modified Huffman method, Wye method, or the like can be used as is. At that time, the data compression rate can be improved by providing an optimal run-length code system for each level according to the continuous state of each concentration level, but the specific equipment required to achieve this is complicated. I'm getting used to it. Therefore, in the present invention, we focused on the fact that the run length distribution characteristics are significantly different between a series of white pixels with a density level of 0 and a series of pixels with other density levels. and a continuous portion of pixels having other density levels, and run-length encoding is performed by giving different codes to each of them. For example, in a continuous part of white pixels, the Weyl code (WYC) shown in Figure 2 is used.
For continuous parts of pixels with other density levels, a mix code (MXC) shown in FIG. 3 is used. Note that the x marks in FIGS. 2 and 3 represent binary codes.

2. The range in which the density level continuously increases or decreases every time one pixel advances in the main scanning line direction is encoded using a density transition form code (TFC).

Figure 4 shows all possible routes of density transition forms in the case of 8 gradations (density levels 0 to 7) according to the definition, and Figure 5 provides supplementary information for calculating the number of routes. It is a diagram. In Fig. 5, it forms a so-called Pascal's number triangle, and the summation N _o of its paths is given by the following equation.

N _o = _o 〓 ^r=1 nCr=2 ⁿ −1 ...(1) Here, n is the maximum concentration level difference.

Therefore, in the case of image information read at eight gradation levels, the total number of paths that the density transition form can take is N ₇ =2 ⁷ -1=127.

These concentration transition forms were coded according to the frequency of their appearance according to the rise or fall of the concentration level.
An example of TFC is shown in FIG. This is Huffman
The maximum efficiency coding method is applied as is, and the code length is determined so that the average code length M is given by the following equation.

M=min( _o 〓 ⁱ⁼¹ Li·Pi) ...(2) Here, Li is the code length and Pi is the probability of appearance of the density transition form.

Next, in the image information encoding method according to the present invention,
In addition to the basic requirements mentioned above, the following two requirements are used as ancillary encoding rules described below.

1. Run-length codes and density transition form codes are arranged alternately.

At that time, in principle, the entire run length may be encoded before the concentration transition form is encoded, or vice versa, but if such a method is adopted, The device becomes complicated.

2. Only when it cannot be determined whether the density transition type code is rising or falling during decoding, a 1-bit code for this determination is attached after the density transition type code.

In this case, the density transition form part of the density level difference, which may not be able to be determined as rising or falling at the time of decoding, is optimally encoded comprehensively, including both rising and falling. For example, in the case of 8 gradations, there are 7 different density level differences up to 3 that may not be distinguishable, so it may be possible to create a system of density transition form codes that also includes these. .

FIG. 7 shows an example of encoding image information read at eight gradation levels according to the encoding rule described above. The symbol (±) in the figure indicates a code for determining whether the density level is rising or falling; the code "0" is used when the density level is rising, and the code "1" is used when it is falling. Note that when encoding each scanning line, it is determined that the coding always starts from a white level pixel.

As described above, in the image information encoding method according to the present invention, different coding systems are used for a series of white level pixels and a series of pixels having other density levels, so that a rough image can be obtained for a continuous part of pixels of the same density level. In addition to performing run-length encoding according to the state, it is also possible to perform encoding according to the form of density transition over the details of an image, focusing on the range in which the density level of the image information continuously increases or decreases. This makes it possible to fully express changes in halftone levels in image information read at multiple density levels, making it especially suitable for images with rapid density changes or vermilion images showing halftones. encoding can be performed,
Moreover, the data compression will be effectively performed.

Note that when expanding to two-dimensional compression, this can be achieved by predicting the position of the boundary between white runs and other runs from the boundary one scanning line before, and encoding the amount of deviation. become. At that time, READ or
The CODIC method can be applied as is.

FIG. 8 shows an example of a configuration for concretely implementing the image information encoding method according to the present invention described above. The A/D converter 2 performs value quantization, and the A/D converted 3-bit output signals are sequentially shifted in accordance with the pixel clock sent from the clock oscillator 3, depending on the density level difference between 0 and 7. A shift register group 4 consisting of SR ₀ to _{SR 8} for calculating the density transition form distribution, a TFC encoder 5 for encoding the density transition form according to the contents read from each shift register SR ₁ to _{SR 8} , and a shift It constantly reads the contents of registers SR ₀ to SR ₂ to detect each information on the _rise and fall of the concentration level, and also detects the inflection point from rise to fall or from fall to rise _. A comparator 6 which compares the respective outputs of the pixel clock and generates a matching signal "1" if they match, and otherwise generates a "0" signal, a counter 7 which counts the pixel clock, and each shift register. Gives a reset command to SR ₀ to _{SR 8} , reads the contents of the counter 7 during the signal period in response to the "0" signal from the comparator 6, and then resets the counter 7.
Comparator 6, counter 7 and TFC encoder 5
It is composed of a CPU 8 that executes encoding according to each piece of information sent from the CPU 8 and sends the results to an external transmission device or memory 9.

The operation of the apparatus configured as described above will be described below, taking as an example the case of encoding the input image information shown in FIG.

The clock output from the clock oscillator 3 at the start is set so that it is not counted by the counter 7.

When the clock advances three clocks after the start, data for density level 3 will appear in SR ₀ , but at that point
Since the content of SR ₁ is 0, the comparator 6 outputs a "0" signal indicating a mismatch, and the CPU 8 reads the content 3 of the counter 7 up to that point and converts it into a run-length code using the Wild code WYC. 010. At the same time, the counter 7 is reset by a command from the CPU 8.

Furthermore, each time one clock advances, data for density levels 3, 5, 6, and 7 will appear in SR ₀ in sequence, but during that period, no data will match with SR ₁ , but the next SR ₀ and
Data of density level 7 will appear between SR ₁ and at that point, the coincidence output of comparator 6 will change from "0" to "1", which will be taken into CPU 8 and output to TFC encoder 5. The contents are read. At that time, the contents of the TFC encoder 5 are set to density levels 3, 5, and 5 from SR ₁ to _{SR 4} , respectively.
Since each data of 6 and 7 is led, the corresponding TFC is "011" (code No. 96 in FIG. 6).

Furthermore, when two clocks advance, the content of SR ₀ continues to be data of density level 7, and in the next clock, it changes to data of density level 5, and the coincidence output of comparator 6 changes from "1" to "0". Accordingly, the CPU 8 reads the count contents 3 of the counter 7 up to that point and sends it to the mix code MXC.
Run-length encoding is performed using (1100).

Thereafter, in the same way, CPU8 outputs TFC14 "1001", MXC4 "1101", and TFC6 according to the input image signal.
"010" is sequentially encoded, but this TFC 6 can take either a rising or falling form from the density level difference 3, so in this case, the falling information "1" output from the comparator 6 is encoded. and add it as a descending sign.

Furthermore, after that, WYC6 "1001", TFC2
"001", MXC2 "10" are encoded sequentially, and when the clock further advances to 25, 26, 27, SR ₀ , SR ₁ ,
Since the contents of SR ₂ are 2, 4, and 3, the inflection point signal output from the comparator 6 at that point is "1".
The CPU 8 accordingly reads the content TFC3 "1011" from the TFC encoder 5 and sends it as it is to the external transmission device or memory 9. In this case as well, the rising information "0" output from the comparator 6 is read and added to it for transmission. Also, when the inflection point output is “1”, MXC1 is “0” except when the minimum value is 0.
is output unconditionally (when the minimum value is 0,
output WYC1 “000”).

Furthermore, when the clock advances three clocks, the coincidence output of the comparator 6 changes to "1", and the CPU 8 changes accordingly.
The content TFC 14 "1001" of the TFC encoder 5 is read and sent to the outside as it is. In this case, since there is no possibility that it is a rise, no code is added based on the rise or fall information.

When encoding is performed sequentially in this manner and the encoding for one line is completed, an EOL (end of line) code is attached and the next line is encoded using the same procedure.

Further, in the image information encoding method according to the present invention, when the read image information has a density level of more than 8 gradations, for example, at 12 gradations, the total number of paths that the density transition form can take is N ₁₁ = 2 ¹¹ - 1 = 2047, which is too large, so the TFC in the TFC encoder 5
The storage capacity of will increase. Therefore, in such a case, as shown in Figure 9, note that the part A surrounded by the dashed line in the figure is the same as in Figure 4 for the case of 8 gradations, and adjust accordingly. It is possible to simplify the process by adding a TFC for cases where the density level difference between adjacent pixels is 8 to 11 to the TFC shown in FIG. It becomes possible.
FIG. 10 shows an example of encoding 12-gradation image information based on this concept.

In addition, by adding TFC132 or later to image information with high gradations such as 16 gradations and 32 gradations using the same concept as TFC, it is possible to encode without causing errors due to data compression. It is possible. In that case, it goes without saying that it is desirable to use Huffman's optimal coding method for TFC so as to be optimal according to the characteristics of each gradation image.

Further, FIG. 11 shows an example of encoding image information read at five gradation density levels.

In this case, there are 15 states in which the density level continues to rise each time one pixel advances in the main scanning line direction, as shown in FIG. 12. Further, the decrease in the concentration level can also be shared by taking the completely opposite route. however,
When the concentration level changes by one step (one way) and when it changes by two steps (two ways), it is difficult to distinguish between rising and falling, so we will include them here as shown in Fig. 13. A total of 18 TFCs are used to encode density transition forms.

In FIG. 13, the predicted frequency column is calculated from the statistics of a certain document image, and the column of code example 2 is an example of a coding system optimized for this. Code example 1 is an example in which images with other characteristics are treated on an average basis.

As described above, in the image information encoding method according to the present invention, in the method of compressing image data by encoding multi-value image data obtained by sampling and quantizing an image pixel by pixel, the density of the multi-value image data is Distinguish between sections where the level changes with each scanning step and sections where the same density level continues, and assign a predetermined code to the section where the density level changes with each scanning step according to the density transition form of the image density. By using the density transition form coding method, a run-length coding method is used for continuous sections of the same density level, or by using different codes for the white level and other levels in the continuous section of the same density level. By using run-length encoding, which consists of a system, multi-level image data is compressed, and it is possible to perform encoding with a good data compression rate and sufficient representation of halftones. It provides optimal encoding for images with large density changes, such as handwritten documents, and halftone images, such as ink stamps, and has the excellent advantage of being able to faithfully reproduce the original image during decoding. .

[Brief explanation of drawings]

FIG. 1 is a chart showing an example of a bit plane code, FIG. 2 is a chart showing a Weyl code, FIG. 3 is a chart showing a mix code, and FIG. 4 is a characteristic chart showing paths of density transition forms of eight gradations. Figure 5 is a diagram showing the count state of the number of paths, Figure 6 is a diagram showing physically an example of the density transition form code of 8 gradations, and Figure 7 is a diagram showing the density level of 8 gradations. FIG. 8 shows an example of encoding image information according to the present invention.
The figure is a block diagram showing an example of a configuration for concretely implementing the image information encoding method according to the present invention.
The figure is a characteristic diagram showing the path of the density transition form when expanding to 12 gradations, Figure 10 is a diagram showing an encoding example when expanding to 12 gradations, and Figure 11 is a diagram showing the density level of 5 gradations. A diagram showing an example of encoding of read image information,
FIG. 12 is a characteristic diagram showing paths of density transition forms for five gradations, and FIG. 13 is a chart showing an example of density transition form codes for five gradations. 2...A/D converter, 3...Clock oscillator, 4...Shift register group, 5...TFC encoder, 6...Comparator, 7...Counter, 8...
CPU, 9...transmission device or memory.

Claims (1)

[Claims] 1. A method for compressing image data by encoding multi-value image data obtained by sampling and quantizing an image pixel by pixel, wherein the density level of the multi-value image data changes with each scanning step. A density transition mode encoding method is used to distinguish between sections where the same density level continues and sections where the same density level continues, and to assign a predetermined code to sections where the density level changes for each scanning step according to the density transition form of the image density. . An image information encoding method characterized in that multivalued image data is compressed by using a run-length encoding method for sections where the same density level continues. 2. Claim 1, characterized in that only when it is difficult to determine whether the density transition is rising or falling during decoding of the density transition form code, a rising/falling discrimination code is attached after the density transition form code. image information encoding method. 3. For sections where the density level changes with each scanning step, by using a combination of codes in the density transition form coding system that corresponds to changes in low density levels,
2. The image information encoding method according to claim 1, wherein all density level changes are encoded. 4. A patent claim characterized in that multivalued image data is compressed by encoding using a density transition form coding system that encodes density transition forms including rising and falling density transition forms as a density transition form encoding method. The image information encoding method according to item 1. 5. In a method of compressing image data by encoding multivalued image data obtained by sampling and quantizing an image pixel by pixel, a section in which the density level of the multivalued image data changes with each scanning step and a period in which the density level is the same for each scanning step. A density transition type encoding method that distinguishes between continuous levels and assigns a predetermined code according to the density transition form of the image density to the areas where the density level changes for each scanning step is used. An image information encoding method characterized in that multivalued image data is compressed by using a run-length encoding method having different encoding systems for the white level and other levels within the interval.