JPS61136378A - Encoding system - Google Patents

Abstract

PURPOSE:To execute effectively the redundancy compression of the analog value of the data, etc. of an image density by converting each the difference of a prescribed analog value data obtained continuously, to a code which is assigned in advance in accordance with a probability distribution. CONSTITUTION:The analog value of density, etc. of a picture element is converted to the digital density signal of plural levels by an A/D converter 21. For instance, the inputted gradation level of a prescribed range is divided into eight levels of '0'-7 and outputted to an encoding device 22. In the encoding device 22, this inputted signal is converted to a difference data. Subsequently, with respect to this difference data, the first encoding is executed in accordance with an encoding table (A) prescribed in advance, and the continuous length of a code train is counted. Next, with respect to the continuous length of the gradation difference data, the second encoding is executed in the same way as a run-length. This second encoding is executed by an encoding table which is assigned in advance in accordance with the appearance probability of the continuous length of the gradation difference data as shown in (B).

Description

DETAILED DESCRIPTION OF THE INVENTION [Technical Field] The present invention relates to an encoding system, and more particularly to an encoding system for encoding analog quantities such as image density data.

[Prior Art] Currently, in image processing in facsimile machines, electronic file machines, etc., a method is adopted in which a document image is divided into pixels of a constant density, and the density of the pixels is converted into black and white z-values and transmitted or recorded. As is well known, this method does not handle density data, so when attempting to process a halftone image, pseudo halftone image processing such as a dither method is used.

The method currently commonly used in facsimile machines and the like is to first convert the original image into black-and-white z-value halftone data using the dithering method described above, and then convert it to the appearance probability of black-and-white data obtained by normal black-and-white binarization. Redundancy compression is performed by performing coding conversion to a code determined accordingly. However, according to this method, after conversion to halftone dots, the halftone data has many points of change between black and white, and the probability distribution of the black and white data is different from the probability of appearance of normal black and white data, so compression efficiency is reduced. The disadvantage is that it is bad.

[Objective] The present invention has been made in view of the above problems, and an object of the present invention is to provide an encoding method that can effectively compress the redundancy of analog quantities such as image density data.

[Structure of the Invention] In order to achieve the above object, the present invention includes a means for converting each difference in predetermined analog quantity data obtained continuously into a code assigned in advance according to the probability distribution of the difference. , a configuration is adopted in which means is provided for converting the continuous length of the analog quantity data into a code assigned in advance according to its probability distribution.

[Example] Hereinafter, the present invention will be described in detail based on the example shown in the drawings.

Here, as an example of codes used for analog quantity encoding in the present invention, a method of assigning Huffman codes according to probability will be described.

Currently, various encoding and compression methods are used in various image processing apparatuses such as facsimile machines and electronic file apparatuses for the purpose of shortening transmission time or reducing the information capacity occupied by recording media. Among them, the MH (Modified Huffman) encoding method is widely used in facsimile machines and the like as a one-dimensional encoding method.

A Huffman code expresses a certain event using an O or l code, and the number of bits decreases according to the probability of the event occurring. Determined with respect to the events treated by statistical properties. FIG. 1 shows a code assignment method when converting a certain event into a Huffman code.

Here, as an example, encoding of run-length information in image processing such as facsimile is exemplified. As is well known, the run length is the number of consecutive white or black pixels of image information. Here, for the sake of simplicity, it is assumed that only 1 to 7 consecutive pixels are generated due to processing such as image reading.

The center column of the table in Figure 1 shows run lengths 1 to 7 arranged in descending order of probability, and the leftmost column shows the probability of each run length occurring, and the total of these is l,00. There is. Further, the leftmost column of the table shows an example of Huffman codes assigned to each of the run lengths 1 to 7 as shown below.

The right half of FIG. 1 shows the code assignment method for each run length. This processing will be shown in bullet points below.If you want to consider it in terms of a film, the following "r run length" can be read as "event".

(1) Arrange the ten lengths in order of appearance probability.

The table portion of FIG. 1 shows the state in which this process has been completed.

(2) Calculate the probability sum of the two run lengths with the smallest probability. At the same time, 0 is assigned to the run length with a greater probability, and 1 is assigned to the run length with a smaller probability. In the case of Figure 1, first, the probability of run lengths 7 and 6 is 0. O
This means adding l, o, and io. This process is coded P
It is indicated by i.

(3) Rearrange the probability sums obtained in (2) as substitutes for the two processed probabilities.

(4) Repeat (2) and (3) above until the probability sum becomes 1. In Figure 1, the second process of repetition is coded P2.
It is shown in In process P2, the probability sum is larger than the probability of ten length 2 which has the maximum probability, so
New probabilities are rearranged above that.

(5) A Huffman code representing each run length is obtained by tracing the codes of 0 and 1 assigned at each stage from the front side and rearranging them in reverse. In Figure 1, the run length is 7.
．． The Huffman codes of 3 and 2 are coded C7, C3 and C
2 are shown respectively.

As described above, run lengths that appear frequently according to probability can be expressed with a small amount of information, so the encoded run length information is compressed rather than representing each run length with a predetermined number of bits. Expression becomes possible with a small amount of information.

In the MH code used in facsimile machines and the like, a ten-length code is determined for black-and-white binary information obtained by reading a standard original image at 8 pels (8 dots per lam). It is well known that in character manuscripts, which are most often used in facsimiles, white run lengths and black run lengths have different frequencies of appearance, so codes are assigned to black and white separately. In the MH code commonly used in facsimile, codes are assigned to run lengths from 1 to 1728 according to probability distribution as described above. As is well known, the run length of 0 to 63 is expressed by a code called a terminating code. The subsequent run lengths of 64 to 1728 are divided into blocks of 64 each. A code called a make-up code (not shown) is defined for these, and a run length of 64 to 1728 is expressed by the combination of this make-up code and the terminating code.

Here, FIG. 2 shows a block diagram of the encoding device according to the present invention.
For example, in an image processing apparatus such as a facsimile machine, an analog quantity such as the density (gradation) of a certain pixel is inputted to a /D converter.

Hereinafter, halftone image processing in a facsimile machine or the like will be explained as an example.

The A/D converter 21 converts this analog quantity into a multi-level digital density signal. For example, the input gradation level in a predetermined range is divided into eight levels from O to 7 and output to the encoding device 22.

A differentiation circuit including a unit delay unit, an adder, etc. is provided at the first stage of the encoding device 22, and converts a signal corresponding to the input gradation level into difference data. When eight gradation levels from θ to 7 are converted into differential signals, differential data from -7 to +7 is obtained, as shown in FIG.

This difference data is treated as an "event" in the code assignment method shown in Fig. 3, and an eight-man code as shown on the right side of Fig. 3 is determined according to the appearance probability distribution of density levels.

According to the first encoding table shown in FIG.
counts the continuous length of the same differential data or the continuous length of the code string obtained by the first encoding. Here, the continuous time or the number of continuous data of the same code may be measured using a counter or the like.

Next is the encoding table! i22 handles the continuous length of gradation difference data in the same way as the run length described above, and performs the second encoding. A coding table determined separately from the one shown in the figure is assigned in advance.

As described above, the gradation value difference code and the continuous length code of the difference are obtained by the two encodings, and redundancy compression can be performed by transmitting or recording these.

The encoding device 22 performs two-stage encoding using a code table determined according to the appearance probability distribution of consecutive gradation lengths as shown above, thereby converting conventional halftone dot data into black and white binary. It is possible to perform redundancy compression of halftone data more effectively than a compression method using a ready-made encoding table determined according to the frequency of appearance.

The encoding operation of the encoding table W22 is not limited to gradation levels,
When extended to other analog quantity processing.

The steps will be as follows:

l) Converting a certain continuous input analog quantity into n-level digital values.

2) Forming difference data between the obtained adjacent level values.

3) Convert the difference data into a code whose information amount is determined in advance according to the probability of appearance of the difference data obtained above.

4) Next, measure the continuous length of the same differential data.

5) Convert the above continuous length into a second code whose information amount is determined in advance according to the probability of occurrence of the obtained continuous length.

6) Repeat the above and output the obtained differentially encoded data and its continuous length encoded data.

In this way, any analog quantity can be effectively compressed in redundancy.

Returning now to the halftone image encoding processing apparatus shown in FIG. 2, its operation will be explained in detail.

Now, suppose that the gradation value shown on the left side of FIG. 5 is obtained as the input signal of the encoding device 22 at the output of the A/D converter 21. Encoding system! The i22 converts this data into the difference data shown in the center of FIG. 5 using a differentiating circuit, measures the continuous length of the difference data, and forms a continuous length value as shown in the right side of FIG.

Subsequently, the third difference data and its continuous length value are
By performing encoding using the encoding table shown in FIG. 4, a differential code and a continuous length code as shown in FIG. 6 can be obtained for each pixel. If we arrange these i one-dimensionally, the 7th
Serial data as shown in the figure is obtained. Of course, the differential code and its continuous length code can be not only output as serial data, but also transmitted in parallel using separate signal lines.

In particular, in the case of encoding the difference data shown above, the difference level does not become a large number of bits even if it is encoded, and in continuous tone images, the tone difference does not change drastically and the probability of continuity is low. Therefore, the compression effect is much higher than that of the conventional method.

During decoding, each code is determined according to a specific probability distribution for the gradation difference value or its continuous length, so a specific gradation and continuous length can be reached by sequentially examining the code bit string.

[Effect] As is clear from the above explanation, according to the present invention, individual differences in predetermined analog quantity data obtained continuously can be
This is because the configuration includes a means for converting into a pre-assigned code according to the probability distribution of the difference, and a means for converting the continuous length of the analog quantity data into a pre-assigned code according to the probability distribution. , it is possible to provide an excellent encoding method that can effectively compress the redundancy of analog quantities such as image density data with a simple configuration.

[Brief explanation of the drawing]

FIG. 1 is an explanatory diagram showing how to determine the MH code as an example of the encoding method, FIG. 2 is a block diagram showing the configuration of the encoding device according to the present invention, and FIG. 3 is an explanatory diagram showing how to determine the MH code as an example of the encoding method. 4 is a table explaining the code assignment of continuous length of gradation difference, and FIG. 5 is a table showing gradation difference values and their continuous length values processed by the apparatus of FIG. 2. 6 is a table showing encoded gradation difference values and continuous length values, and FIG. 7 is an explanatory diagram in which gradation difference codes and their continuous length codes are arranged one-dimensionally. Pi, P2...Processing C2, C3, C7...Huffman code 21...A/D converter 22...Encoding device Fig. 3 Fig. 4A Fig. 5 Fig. 6 Fig. 7

Claims (1)

[Claims] Means for converting each difference in predetermined analog quantity data obtained continuously into a code assigned in advance according to the probability distribution of the difference, and a continuous length of the analog quantity data previously assigned according to the probability distribution. An encoding method characterized by providing means for converting into a code.