JPH03240173A - Image data compressing system - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed Description of the Invention] [Summary] Regarding an image data compression method that compresses binary image data obtained by scanning a reading line, the present invention relates to an image data compression method that compresses binary image data obtained by scanning a reading line. When compressing binary image data with the aim of reducing image data, multiple vertical lines of the image data are converted at once into a fixed-length intermediate code consisting of a pair of the bit pattern and the length of the pattern. After performing preprocessing, a histogram of the appearance frequency (rank) of pattern transitions between adjacent codes of the intermediate code string is created, and only intermediate codes with transition patterns that are likely to appear (for example, the one with the highest frequency) are
(not limited to one pattern) (for example, the pattern of the intermediate code with the lowest frequency of appearance), intermediate codes with pattern transitions that are difficult to appear are output as they are, and finally the converted code string to be encoded at the current time is The configuration is such that compression encoding (universal encoding) is performed as a copy of an already encoded transform code string.

[Industrial Application Field] The present invention relates to an image data compression method for compressing binary image data obtained by reading line scanning.

In recent years, with the development of OA, mixed information such as character codes and black-and-white binary images in documents has come to be handled together with layout information in 64 facsimiles, optical disk file systems, and the like. When document information is used as digital data, the amount of image information is extremely large compared to character code information, several tens to several tens of times larger. Therefore, in order to efficiently handle image information during storage and transmission, data compression is required. It is essential to reduce the amount of data by adding .

[Prior Art] Conventionally, data compression methods can be roughly divided into image data compression and character code compression.

First, as conventional image data compression methods, the MH method, the MMR method, and the predictive encoding method are known as typical compression methods for black-and-white binary images.

■MH method (Modified Hulfman Co.
ding) The MH method is an international standard one-dimensional compression method for binary images. This method compresses data by variable-length encoding a continuous length of white or black (Run Length) along the main scanning direction using a Huffman code. In order to reduce the number of code words, the Huffman code is composed of a terminating code representing a length of 64 or less and a make-up code representing a multiple of 64. With this MH method, a normal document image can be compressed to a fraction of the original size.

■MMR (Modified Modified RE
AD(REIative＾ddress Design
ate coding)) method 2 of the international standard for binary images
There is an MMR method as a dimension compression method. In this method, a pixel that changes from white to black or from black to white in the main scanning direction is called a changed pixel, and the black and white pattern boundary shift represented by the changed pixel between adjacent scanning lines (changed pixel relative address)
Data compression is performed by focusing on the connection relationship of pixels with a small change. By using this MMR method, a normal document image can be compressed to one-tenth to one-tenth.

On the other hand, as an efficient data compression method for character codes, there is a universal encoding method represented by 2iv-Lempel encoding.

2iv-Lempel encoding (hereinafter abbreviated as rZL encoding) will be briefly explained (for details, see, for example, Munakata's "ziy-Lempel data compression method", information processing.

vat, 26. No. 1.1985).

The ziv-Lempel code has two types: ■Universal type and ■Incremental parsin type.
Two algorithms have been proposed: g).

■Universal algorithm This algorithm requires a large amount of calculations, but provides a high compression ratio. This is a method in which encoded data is segmented (subsequences) of the maximum length from an arbitrary position in a past data sequence and encoded as a copy of the past sequence.

FIG. 9 shows a principle diagram of a universal ZL code encoder. First, encoded input data is stored in the P buffer 30, and data to be encoded is input to the Q buffer 32.

The sequence in the P buffer 30 is searched with the sequence in the Q buffer 32 to find a matching partial sequence in the P buffer 30 that has the maximum length. The next set of information is then encoded in P-buffer 30 to specify this maximum length subsequence.

Next, the encoded sequence in the Q buffer 32 is transferred to the P buffer 3.
0 to obtain new data. Thereafter, similar operations are repeated to decompose the data into subsequences and encode them.

■Incremental decomposition algorithm This algorithm has a lower compression rate than the universal type, but it is known to be simple and easy to calculate. In the incrementally decomposed ZL code, if the input symbol sequence is X=aabababaa@*@, then the incremental decomposition into the component series x=XOXI X2*#- is performed as follows.

Let Xi be the longest sequence with one symbol added to the right end of the existing part, and then X = a11abIIabaIIbaaa...

Therefore, XO=λ (all columns), XI=XOa.

X2 = XI b, X3 = X2 a.

It can be decomposed as X4=XOb X5=X1a...

Each incrementally decomposed component sequence is encoded as the following set using the existing component sequence.

The incremental decomposition algorithm uses the encoding pattern to
Among the subsequences decomposed in the past, the one with the maximum length matching is found and encoded as a copy of the subsequence decomposed in the past.

That is, in the ZL code, the current character code sequence is encoded as a copy of the encoded past sequence. When this ZL code is used, character code document information can be compressed to about 1/2.

[Problems to be solved by the invention] Among the conventional digital data of documents, image information is processed using the MH method, which uses the length of consecutive pixels of the same color, and the MM method.
Compression is performed by a method using a relative address of a changed pixel, typified by the R method.

Further, character code information can be compressed using a universal encoding method such as ZL encoding.

The name of the universal encoding method is "universal encoding method"
means. However, when the ZL encoding method is applied to image data, it can be compressed to about 1/2, but the compression rate is very low compared to the MMR method or the predictive encoding method.

For this reason, at present, character codes and binary image data have very different statistical properties, so it is disadvantageous to cover both with a single encoding method. A method of switching the encoding method is adopted.

The present invention was developed in view of the above situation, and is capable of efficiently compressing and reducing the amount of data even when image data with different statistical properties such as halftone dots, line drawings, character images, and their images are mixed. The purpose is to provide an image data compression method.

[Means to solve the problem] FIG. 1 is a diagram explaining the principle of the present invention.

First, the present invention is directed to an image data compression method for compressing a binary image obtained by scanning a reading line.

In the present invention for such an image data compression method, first, image data is input to the preprocessing means 10, a plurality of vertical lines (N lines) of the input image data are grouped, and the bit pattern (2N lines) is grouped. type) and the length of the pattern (RL
) into a fixed-length intermediate code.

Next, in the conversion means 12, a histogram 16 indicating the appearance frequency of pattern transitions between adjacent intermediate codes is created for the intermediate code string obtained from the preprocessing means 0, and based on this histogram 16, the current processing is If a pattern transition from the previous intermediate code 18 to the intermediate code 20 is likely to occur, the pattern of the intermediate code 20 is replaced with another specific pattern, such as A;
Outputs 0 as is.

Finally, in the compression encoding means 14, the conversion code string obtained by the conversion means 12 is encoded by the compression encoding means (universal encoding means) 14 as a copy of the conversion code string that has already been compressed and encoded. Configure it so that it becomes

Here, the converting means 12 replaces the intermediate code pattern in which pattern transitions occur frequently with an intermediate code pattern in which pattern transitions occur less frequently.

The compression encoding means 14 may be a universal ZL encoding method that changes the transform code string to be encoded at the present time into a set of a copy position and a copy length of a transform code string that has already been encoded; An incremental decomposition type ZL encoding method is used in which the commonly encoded transform code string is expressed by the number of the subsequence when an already encoded transform code string is divided into different subsequences.

[Operations] According to the image data compression method of the present invention having such a configuration, even if image data contains a mixture of images with different statistical properties, it is possible to perform preprocessing that incorporates the statistical properties unique to the images. Universal encoding is performed after the differences in statistical properties are matched, and one encoding method can effectively handle data with widely different statistical properties.

To explain in more detail, universal encoding was originally
This is an information preservation type data compression method that does not pre-assume the statistical properties of the information source when compressing data, so it can be applied to various types of data (character code, object code, etc.).

However, while character codes and symbols have boundaries in 8-bit and 16-bit units, image pigs do not have boundaries like characters and symbols. Even if there is a boundary, it is a line unit that has nothing to do with the image itself.

For this reason, for example, even if image data is compressed using a universal encoding method that processes character codes in bytes, various patterns that are far apart from each other may appear evenly when viewed as bytes due to the statistical properties of the image. , and an effective compression ratio cannot be obtained.

In addition, while the MMR method compresses images by using two-dimensional correlation, existing universal encoding methods only use one-dimensional correlation, and their compression performance is lower than that of two-dimensional image encoding methods. is inferior.

In order to effectively compress image data, universal encoding, which processes it bit by bit, may be considered, but in this case, compressing the character code in bytes would take more time due to bit processing, and The disadvantage is that learning efficiency is reduced because it is decomposed into different sequences.

On the other hand, in the present invention, as preprocessing when encoding image data, two-dimensional correlation is used to collectively convert multiple lines of an image into a fixed-length intermediate code of, for example, 8 bits. Apply processing. Next, for the intermediate code string obtained in the preprocessing, a histogram showing the frequency of appearance of pattern transitions between adjacent intermediate codes is created, and the intermediate code is further converted according to this histogram.

As an intermediate code conversion method using a histogram, the inventor of the present invention has proposed a method for calculating and replacing the appearance frequency (rank) of pattern transitions from the previous intermediate code from the histogram for all intermediate codes. According to this method, by increasing the bias of the frequency distribution of intermediate codes,
This makes it easier to compress the data in the final universal encoding.

However, for patterns in which the intermediate code itself does not have a certain degree of statistical bias, even if the pattern of the intermediate code sequence is replaced by the frequency of occurrence, the frequency distribution becomes smooth and the regularity of the intermediate code sequence is lost, and on the contrary, This causes a problem in which the compression rate in universal encoding decreases.

Therefore, in the present invention, based on the created histogram, only a specific pattern, for example, a pattern of an intermediate code with a low pattern transition, is applied to an intermediate code having a pattern with a large bias in appearance frequency, that is, an intermediate code with a pattern transition with a high frequency of appearance. Replaced and expressed.

As a result, even a series with a small average bias will be converted into a series with several peak distributions,
By using the peak value, the number of states can be reduced, making it easier to perform universal encoding.

[Embodiment] FIG. 2 is a block diagram of an embodiment of the data compression method of the present invention.

In FIG. 2, image data in 1-bit units obtained by reading line scanning by a reading device or the like is inputted to a preprocessing circuit 10 from a terminal 22. The image data input from the preprocessing circuit 10 is subjected to preprocessing to extract statistical features from the binary image, and then converted into a fixed length code in 8-bit units as an intermediate code.

Intermediate code converter 1 provided following preprocessing circuit 10
2 converts the intermediate code obtained from the preprocessing circuit 10 into a code sequence with a small number of states by taking statistical properties, and outputs the conversion result to the universal encoder 14. The universal encoder 14 encodes the input transform code while learning the statistical properties thereof, and outputs the compressed code to the terminal 24.

The universal encoder 14 executes the aforementioned universal type or incremental decomposition type compression algorithm,
Its configuration is known. Therefore, the processing of the preprocessing circuit 10 and intermediate code converter 12 in the embodiment shown in FIG. 2 will be explained in detail below.

FIG. 3 shows the processing contents of the preprocessing circuit 10, which processes multiple lines of an image at once, divided into (a), (b), and (c).

First, as shown in FIG. 3(a), the input binary image is divided into, for example, every four lines in the vertical direction.

Next, the 4-line bit pattern and the continuous length RL of the pattern are encoded while being shifted one bit at a time to the right from the left end. By this encoding, an intermediate code consisting of a pattern shown in FIG. 3(b) and a length RL in which the same pattern continues is obtained.

Here, the type of bit pattern of 4 lines is 2'=16
The type of pattern can be expressed by a 4-bit code. Generally speaking, the number of types of patterns is 2N for the number of lines to be grouped N, and therefore the proportion of the pattern code in 8 bits is N bits.

The data structure of the intermediate code in Figure 3(b) is as shown in Figure 3(c).
It is converted into a fixed length code in 8-bit units as shown in the following. That is,
The upper 4 bits store a code indicating the bit pattern in units of 4 lines as is, and the lower 4 bits store the length RL of the same bit pattern. However, the maximum length is up to 16 that can be represented by 4 bits, and any longer than that requires a new code.

This process is repeated every four lines until there are no vertical pixels left.

FIG. 4 is a processing flow of the preprocessing circuit 10 shown in FIGS. 2 and 3.

First, step 81 (hereinafter "step" is omitted) to 8
Proceed to step 2 and read bits for four vertical lines of the image into the buffer. Next, change the pattern of the first 4 lines to 83.
-Store as pat. Next, shift one pixel to the right in S4, and By-pat the pixel pattern of the next four lines in S5.
be memorized as

Next, in S6, compare the old-pat and new-pat, and if they are the same, in S7, proceed to 88 on the condition that RL<16 is satisfied, increase RL by 1, return to S4 again, and add the next vertical 4. Read pixels.

Even if old-pat and new-pal match in S6, if it is determined in S7 that RL exceeds 16, or if it is determined in S6 that old-pal and new-pal do not match, the process advances to S9 and the current old - Create and output a result code (intermediate code) that combines pal and RL.

Next, in S10, new-pat is substituted into old-pal, and if horizontal pixels continue in Sll, the process returns to S3 and continues the process of newly encoding the continuation of the pattern.

When the number of horizontal pixels runs out, it is transferred from Sll to S2 via 31.
Return to , read the next four lines into the buffer, and perform the same process. When the above processing is completed for all vertical lines, it is determined at SL that the number of remaining vertical lines has become zero, and the series of preprocessing is completed.

In this embodiment, the number of lines bracketed by - is set to four, but the number is not limited to this. For example, if the number of lines to be grouped is three, the upper three bits of the preprocessing result code will be allocated to the pattern, and the lower five bits will be allocated to the RL.

Next, the configuration and operation of the intermediate code converter 12 provided subsequent to the preprocessing circuit 10 will be explained.

First, the intermediate code converter 2 obtains the frequency distribution (histogram) of transition states of the intermediate code pattern obtained from the preprocessing circuit 10, as shown in FIG.

In Figure 5, the horizontal axis shows the current pattern, the vertical axis shows the previous prefix pattern, and the frequency of transition from a certain prefix pattern to a certain current pattern, that is, the appearance frequency, is shown numerically. The larger the value, the higher the frequency of appearance (rank).

Next, based on the frequency distribution of transition states in FIG.
FIG. 6 shows the state in which .

In another intermediate code conversion method using a histogram proposed by the inventor of the present application, all intermediate code patterns obtained from the preprocessing circuit 10 are re-converted to the order of appearance frequency according to FIG. and then universal encoding.

However, when the bias of the intermediate code is small, the compression ratio does not necessarily increase.

Therefore, in the intermediate code converter 12 of the present invention, among the frequencies of pattern transition states shown in FIG. 5, only those in which pattern transitions are likely to occur, that is, portions with high frequency of appearance are summarized.

Specifically, for each of the prefix patterns 1 to F in Fig. 5, the current pattern in the circled part that appears most frequently is the pattern rAJ of the current pattern row that is the least likely to appear in the rectangle.
Replace it with that.

Also, the current pattern in the part surrounded by a triangle that is the second most likely to appear is replaced with pattern "5" in the current pattern row that is the second least likely to appear in the part surrounded by a rectangle.

As a result, the histogram used by the intermediate code converter 12 for replacing pattern rAJ and pattern "5" is only the pattern rAJ enclosed in a circle and the pattern "5" enclosed in a triangle in FIG. .

Next, code conversion by the intermediate code converter 12 will be specifically explained with reference to FIG.

In FIG. 8, if six result codes are obtained from the preprocessing circuit 10 as shown in FIG. 8(a), they are converted as shown in FIG. 8(b).

First, focusing on the first two result codes in FIG. 8(a), 1st code; pattern 1. RL=2 Second code; pattern O, RL=3. The current code to be processed here is the second code. Therefore, since the prefix pattern = 1 and the current pattern - 〇, the conversion pattern rAJ is found from Fig. 7, and as shown in Fig. 8 (b), the current code pattern is the code indicating the previous pattern type. =: Conversion is performed to replace 0 with code =A, which indicates the pattern that is least likely to appear.

Focusing on the next second pattern transition, since the prefix pattern = 0 and the current pattern = 1, the conversion pattern "5" is found from Figure 7, and as shown in Figure 8 (b), the current code is The pattern is converted so that the code = 1 indicating the pattern type up to that point is replaced with the code = "5" indicating the pattern that is the second least likely to appear.

The next 3rd and subsequent pattern transitions are 1-8. 8-E.

E-3, and it does not correspond to the replacement pattern with the highest frequency of occurrence and the replacement pattern with the second highest frequency of occurrence circled in Figure 7, so the input pattern is left as is without performing the replacement operation. Output.

By converting the upper 4 bits of the code obtained in the intermediate stage into a code that takes into account the transition probability of the bit pattern, even if the bias in the intermediate code string due to preprocessing is small, it is possible to maintain sufficient bias in the statistical properties. It can be converted into a code string that is easy to compress, and the compression rate in the final universal encoding is greatly improved. Although the case where there are two patterns to be replaced is shown here, the number of patterns to be replaced is not limited to two.

[Effects of the Invention] As explained above, according to the present invention, by performing preprocessing on image data with different statistical properties, predetermined bit units with uniform statistical properties similar to characters and codes can be obtained. Can be converted to fixed length data.

In addition, by converting the data into a biased data sequence that is easy to compress based on the transition probability of the intermediate data after preprocessing, the data after universal encoding can achieve a high compression rate close to that of vector encoding. .

[Brief explanation of drawings]

FIG. 1 is a diagram explaining the principle of the present invention; FIG. 2 is a configuration diagram of an embodiment of the present invention; FIG. 3 is a diagram explaining the processing of the preprocessing circuit of the present invention; FIG. 4 is a diagram explaining the processing of the preprocessing circuit of the present invention Flow diagram; Fig. 5 is a frequency explanatory diagram of pattern transition states used in the present invention; Fig. 6 is an explanatory diagram of the pattern transition order obtained from Fig. 5; Fig. 7 is an appearance frequency code from the pattern code of the present invention. FIG. 8 is an explanatory diagram of the pattern transition state used for reconversion of the intermediate code of the present invention; FIG. 9 is an explanatory diagram of universal encoding used in the present invention. In the figure, 10: 12: 14: 16: 22° 30: 32: Preprocessing means (preprocessing circuit) Conversion means (intermediate code converter) Compression encoding means (universal encoder) Histogram 24: Terminal P buffer Q buffer Patent applicant Fujitsu Limited

Claims (4)

[Claims] (1) In an image data compression method that compresses binary image data obtained by reading line scanning, multiple vertical lines of input image data are collectively compressed, and a set of the bit pattern and the length of the pattern is preprocessing means (10) for converting into a fixed length intermediate code consisting of;
For the intermediate code string obtained from 10), a histogram (1
6) and calculates the previous intermediate code (1) for the intermediate code (20) currently being processed based on the histogram (16).
8) converting means that replaces the pattern of the intermediate code (20) with another specific pattern (A) when the pattern transition from 8) is likely to appear, and outputs the intermediate code (20) as is when it is unlikely to appear; (12); Compression encoding means (14) for encoding the transform code string obtained from the transform means (12) as a copy of a transform code string that has already been compressed and encoded; Characteristic image data compression method. (2) The image data compression according to claim 1, wherein the converting means (12) replaces an intermediate code pattern with a high frequency of pattern transitions with an intermediate code pattern with a low frequency of pattern transitions. method. (3) The compression encoding means (14) converts the transform code string to be encoded at the present time into a set of a copy position and a copy length of the already encoded transform code string. Image data compression method according to item 1. (4) The compression encoding means (14) is characterized in that the conversion code string to be encoded at the present time is represented by the number of a subsequence when an already encoded conversion code string is divided into different subsequences. The image data compression method according to claim 1.