JPH0541805A - Image data compression method and apparatus thereof - Google Patents

Abstract

(57) [Abstract] [PROBLEMS] To provide an image data compression method and apparatus for halving the code table for compressing binary image data. [Structure] Divide white and black image data into blocks,
A pattern that makes all black when added is represented by one label, and a flag of 0 is added to one and a flag of 1 is added to the other.
This label is used as a code table. [Effect] A high compression rate can be achieved by shortening the code to be assigned to the control code and the code table which are fixed bits. Also, the process of changing the code table for each image is simplified and high-speed processing can be performed.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method and apparatus for compressing binary image data obtained by scanning an image and sampling in pixel units.

[0002]

2. Description of the Related Art As a method of obtaining compressed data of a binary image, a two-dimensional block coding method disclosed in Japanese Patent Laid-Open No. 54-2619 is known. In the two-dimensional block coding method, the coding unit is a fixed-sized two-dimensional block, and
Data compression is performed by aggregating according to the frequency of appearance of patterns that can express a dimensional block and assigning a variable-length code to each pattern for pattern coding.

[0003]

The conventional two-dimensional block coding method has a problem that the compression efficiency of the entire image cannot be improved because the code table showing the correspondence between the pattern and the code is large. It was In particular, it was remarkable when the data amount of the original image was not large as compared with the coding table.

Further, when the code table is large, there is a problem in that the calculation for assigning the code by the Huffman method or the like becomes more complicated and the time required for data compression increases.

The present invention has been made in view of the above problems, and an object of the present invention is to provide a novel image data compression method and apparatus capable of reducing the code table and the data compression time.

[0006]

In order to solve the above problems, the image data compression method and apparatus of the present invention are characterized by the following points.

(1) An image data compression method according to the present invention is a method of compressing binary image data in which a density value is 0 or 1 obtained by scanning an image and sampling in pixel units. Of the patterns expressed in rows × M columns, the value obtained by adding the density values of the pixels at the positions in the same row and the same column to a certain two patterns is 1 at all positions in the N rows × M columns. When it becomes (high), the two patterns
Each row is given the same label, and one pattern is given a flag of 0 and the other is given a flag of 1 so that N rows × M in advance.
Patterns expressed by pixels in columns are classified, (b) image data is divided into pixel blocks of N rows x M columns, and (c)
The pixel block of N rows × M columns is checked to see which of the patterns classified in (a) matches, and the label and flag given to the matched pattern are given to the pixel block. , (D) the appearance frequency of the label is measured for a plurality of image blocks, and a short code is assigned in order from the label with the highest appearance frequency, and (e) each pixel block corresponds to the label to which it is attached. A code is added, and the flag given in (f) and (c) and the code given in (e) are used as compression results.

(2) The image data compression method of the present invention is a method for compressing binary image data having a density value of 0 or 1 obtained by scanning an image and sampling in pixel units.
(A) Among patterns expressed in N rows × M columns, some 2
For each of the two patterns, if the value obtained by adding the density values of the pixels in the same row and the same column is 1 (high) in all the positions of N rows × M columns, the two patterns are respectively added. , The same label is given, and a flag of 0 is given to one pattern and a flag of 1 is given to the other pattern to classify the patterns expressed in pixels of N rows × M columns in advance, (b) The image data is divided into pixel blocks of N rows × M columns, and (c) the pixel block of N rows × M columns is examined to see which of the patterns classified in (a) matches, and they match. Pattern
A label and a flag assigned to each pixel block are assigned to the pixel block, (d) the appearance frequency of the label is measured for a plurality of image blocks, and a short code is assigned in order from the label with the highest appearance frequency, (e) For each of the pixel blocks,
Give the code corresponding to the label that has been given,
(F) The flag given in (c) and the code given in (e) are compression results, and (g) the flag is
Recompressing is performed by the processes of (a) to (f).

(3) The image data compression apparatus of the present invention comprises an information input section for scanning an image to obtain a binary digital signal having a density value of 0 or 1, an encoding section for encoding the digital signal, and An image data compression device comprising a compressed data holding unit for storing a code, the information input unit, the encoding unit, and a control unit for controlling the compressed data holding unit. A value obtained by adding the density values of pixels located at the same row and the same column for a certain two patterns among (b) the pattern expressed by N rows × M columns Is 1 (high) at all positions of N rows × M columns, the same label is given to each of the two patterns, and 0 is assigned to one pattern and 1 is assigned to the other pattern. By adding a flag, N
Patterns expressed by pixels of rows x M columns are classified,
A block information conversion circuit for checking which of the patterns the pixel block made into a block in (a) matches and adding the label and the flag given to the matched pattern to the pixel block. c) The appearance frequency of the label is measured for a plurality of image blocks, a short code is assigned in order from the label with the highest appearance frequency, and a code corresponding to the label to which the label is attached is assigned to each pixel block, It is characterized by comprising the above-mentioned code and an encoding circuit which makes the flag given in (b) a compression result.

[0010]

A code table showing the correspondence between the pattern used in the method of the present invention and the code for compression is disclosed in Japanese Patent Laid-Open No. 54-261.
It is less than half the size of the code table for all possible patterns as used in FIG.
When the code table becomes half or less, the control code is
Since the code assigned to the code table and the code table becomes shorter, the total compressed data including the code table can be made smaller than the conventional technique.

[0011]

(Embodiment 1) An embodiment of the present invention will be described with reference to the drawings.

FIG. 1 is a flow chart showing the flow of the image data compression method of the present invention.

The outline of the flow will be described below.

First, a binary image is prepared. (S10
1) The processing unit is N rows × M columns. (S102) N rows x
For all patterns that can express the pixel block of M columns,
Assign labels and flags. Details of the operation of assigning labels and flags to patterns will be described later. (S10
3) The number Z of blocks to be scanned is set to 0. (S104) While scanning the input image line by line from the left, it is divided into pixels of N rows × M columns. (S105) N rows × M
The pattern of the block of column pixels is the pattern of S103.
The block is given the label and flag assigned to the pattern. On the way, if N scanning is completed, an EOL (End of Line) code is output. Z is
Although the maximum number of all blocks of the image is the maximum, when the input image is large or when plural types of images are included and divided and compressed, an appropriate value smaller than the total number of blocks may be provided.
(S106, S107, S108, S109, S11
0) The cumulative occurrence frequency of labels is totaled, and a short code is given to a label having a high cumulative occurrence frequency. (S111) Determine the end of all blocks. (S112) If all blocks have ended, the RTC (Return to Control) code indicating the end of all data is added to the code, the flag, and the EOL code and saved. (S112) The details of the process will be described below.

FIG. 2 shows the pattern used in the step (S103) of assigning labels and flags to all patterns represented by a pixel block of N × M pixels, where one pixel is represented by a binary value. It is a figure for demonstrating using the example of the pattern of the 2x2 pixel which exists. No. As shown in FIG. 1, the positions of 4 pixels of the pattern of 2 × 2 pixels are A, B, C and D, respectively.

No. 1 shown in FIG. 1 to No. Reference numeral 16 denotes all the patterns that can be represented by the white pixels 21 shown in solid white and the black pixels 22 shown in diagonal lines.

The pattern state is 0 for white pixels and 1 for black pixels.
This pattern is a 2-gradation pattern from 0 to 1. No. The pattern of 1 is 0 in the order of ABCD
000, No. Similarly, the pattern of 9 becomes 1111. Therefore, No. No. 1 pattern and No. 1 pattern. Bits representing the state of the 9 patterns are added at each position to obtain 1111. Similarly, No. The pattern of No. 2 is 1001, No.
The pattern of 10 is 0110, and the added value for each position is 1111.

Similarly, No. 1 to No. For all 16 patterns up to 16, two patterns in which the added value of the bits indicating the state are all 1 in ABCD are put together,
When expressed by one label, label 1 (No. 1
And No. 9 pattern), label 2 (No. 2 and No. 2).
No. 10 pattern), label 3 (No. 3 and No. 11 pattern), label 4 (No. 4 and No. 12 pattern)
Label), label 5 (patterns of No. 5 and No. 13),
Label 6 (No. 6 and No. 14 patterns), Label 7 (No. 7 and No. 15 patterns), Label 8 (N
o. 8 and No. It is possible to classify the patterns by expressing them with 8 labels of 16 patterns). Next, changing the viewpoint, No. When the white and black of the pixels of the pattern 1 (the pattern in which all the pixels of A, B, C, and D are composed of the white pixels 21) are reversed, No. 9 patterns (patterns in which all pixels A, B, C, and D are composed of black pixels 22). Similarly, No. White pixel 2 of pattern 2 (pattern in which A and C pixels are black pixels 22 and B and D pixels are white pixels 21)
No. 1 when the black pixel 22 and the black pixel 22 are reversed. 10 patterns (patterns in which A and C pixels are white pixels 21 and B and D pixels are black pixels 22). The combination of such patterns and the method of generating two original patterns from the label are fixed to the processing system and are known in advance.

A flag indicates which of the two patterns grouped by one label is shown. If the flag 0 is set to No. 1 to No. 8 pattern, 1 for N
o. 9 to No. Assign to patterns up to 16.

For example, if label 1 and flag 0, then N
o. No. 1 pattern, and if the label is 1 and the flag is 1, 9 shows a pattern of 9.

It has been described above that all 16 patterns of a binary 2 × 2 pixel block can be represented by 8 labels and 0 and 1 flags.

In the case of the conventional block coding method, the above 1
Since a different code is assigned to each of the 6 patterns, it is necessary to describe the correspondence between the 16 patterns and the codes in the code table. However, according to the method of the present invention,
By using a code table that describes the correspondence between the eight labels and the code, the size of the code table is half that of the conventional one.

Next, the method of creating the code table and the effect of the present invention will be described using an example in which actual image data is compressed.

3 (a), (b), (c) and (d) are diagrams showing an example when the character font data is compressed.

In FIG. 3A, the input binary image is a font "love" of 48 × 48 pixels. Black squares represent black pixels, and white squares represent white pixels.
When this image is scanned from the upper left and divided into blocks of 2 × 2 pixels, 24 × 24 blocks are formed. The pattern represented by this block is searched for a match from the pattern of 2 × 2 pixels shown in FIG. 2, and the flag and label assigned to this pattern are given to the block. After processing all blocks, the cumulative occurrence frequencies of the labels given to the blocks are aggregated, and the labels 1 to 8 have the occurrence frequencies shown in FIG. 4B. Further, the pattern No. shown in FIG. 1 to No. The frequency of occurrence up to 16 is
It becomes like FIG.3 (c).

A code table in which codes are assigned to such labels by the known Huffman method is shown in FIG. 4 (a).

In this way, each of the 24 × 24 blocks is represented by the code corresponding to each label shown in FIG. 4A and the flag 1 bit described above. The number of bits of the compressed image is 385 x 2 bits + 12 x 7 bits + 88 x 3 bits + 30 x 5 bits +
15 x 6 bits + 21 x 5 bits + 25 x 5 bits + 0
X8 bits + 23 x 9 bits (EOL) + 10 bits (RTC) = 1705 bits. Since the total number of bits of the code assigned to each label is 33 bits and 32 bits (8 × 4 bits) are required to indicate 8 patterns, the code table itself needs 65 bits. The total number including 1 is 1770 bits. 48 x 4
When the character font of 8 is expressed in binary as a simple bitmap, since it is 2304 (48 × 48) bits,
The compression rate is 1770/2304 (compression bit number / binary expression bit number) = 0.77.

On the other hand, FIG. 4B shows a code table assigned by the known Huffman method based on the cumulative occurrence frequency of FIG. 3C, as in the conventional block coding.

When compressed with this code table, 293 ×
1 bit + 6 x 6 bits + 45 x 3 bits + 15 x 5 bits + 7 x 7 bits + 9 x 6 bits + 16 x 6 bits +
0 x 8 bits + 92 x 3 bits + 6 x 7 bits + 43 x
4 bits + 15 x 5 bits + 8 x 8 bits + 12 x 5 bits + 9 x 6 bits + 0 x 9 bits + 23 x 10 bits (EOL) + 11 bits (RTC) = 1722 bits. Since it is necessary to distinguish all labels from EOL and RTC, EOL has 10 bits and RTC has 11 bits. Since the code table itself has 150 bits, the compressed data has a total of 1872 bits. The compression ratio according to the conventional method is 0.81, and the compression ratio according to the present method is 0.77. The compression ratio according to the method of the present invention is better.

As for the combination of the patterns, any other method can be considered, but in the present method of combining the patterns which are in the inversion relation to each other, the frequency of occurrence of the patterns as shown in FIG. 3 (c). This is a method of combining patterns close to each other. Therefore, the total number of bits not including the control code and the code table is suppressed to 1481 bits by the pattern compression and 1488 bits and 7 bits by the label compression of the present method. With any other arbitrary combination, the ones that have similar occurrence frequencies are not combined, so the number of bits increases compared to the compression by this method.

This method using the pattern inversion relation is as follows.
This is excellent because the frequency of occurrence of 16 patterns can be closely approximated by the frequency of occurrence of 8 labels.

The method according to the present invention has a total of 1 including the code table as compared with the method by the ordinary block coding.
02 bits, compression ratio 0.04 is good. The reason is that the number of bits in the code table is 65 bits in the method of the present invention.
This is because the conventional method has 150 bits, and the code table according to the method of the present invention is less than half the size of that of the conventional method.

Further, according to the method of the present invention, even if a code is assigned differently depending on the image and the code is determined, since the number of labels is half, all the possible patterns are assigned to the code. Compared to, there are few calculations and the compression time is short. Further, since the code table for associating the label with the code is less than half of the conventional one, the image communication time can be shortened even when the code table is transmitted when used for communication such as facsimile. Also, for the original pattern of FIG. 3A, in which the black pixel and the white pixel are inverted,
The label converted by the method of the present invention is shown in FIG.
There is no change compared to. That is, the compression processing can be performed with the same code table regardless of whether the pattern has many black pixels or the pattern has many white pixels. However, in the conventional method, the code table is determined by the frequency of appearance of black pixels and white pixels.
It is necessary to change the bull. In the reproduction of inverting black and white by the method of the present invention, an image in which white pixels and black pixels are inverted can be obtained only by inverting a flag which is information of 1/4 of the original image data.

In the above, the embodiment in which the character font data is compressed in FIGS. 3 (a) (b) (c) (d) has been described.

In this embodiment, the correlation with the horizontal block is not used, but it is easily conceivable to consider one block as one pixel and apply the run length method for compression.

FIG. 5A shows a label, a flag and a control code.
(EOL, RTC), the storage order of the code table.

The storage order is the code table, flag 1, label 1, ..., Flag n1, label n1, EOL, flag n2, label n2, ..., Flag n3, label n.
3, RTC order.

FIG. 5B shows the storage order of another label, flag, control code (EOL, RTC), and code table.

The storage order is the code table, flag 1, ...
..Flag n1, label 1, ... Label n1, EO
The order is L, label n2, ... Flag n3, RTC. In FIG. 5B, the storage order is such that labels and flags up to EOL are separated.

It goes without saying that the method of the present invention can be easily applied to the case of a block size other than 2 × 2 pixels.

(Embodiment 2) In this embodiment, an image is hierarchically encoded by compressing by using a flag as raw data before compression.

An embodiment of the present invention will be described in detail with reference to the drawings.

In FIG. 2, the pattern of 2 × 2 pixels is 1
In order to reduce it to 1 pixel which is / 4, it can be represented by associating 0 of the flag with a white pixel and 1 with a black pixel. This will be described in detail below.

No. 1, No. 4, No. 5, No.
6, No. In the pattern of 7, the black pixel 22 is 0 pixel or 1 pixel among the 4 pixels, and when it is reduced to ¼, it is converted as one white pixel. In addition, No.
9, No. 12, No. 13, No. 14, No. 1
In the pattern of 5, the black pixels are 4 pixels or 3 pixels, and thus are converted into one black pixel when reduced to ¼. No. 2, No. 3, No. 4, No.
8, No. 11, No. The 16 patterns have 2 black pixels and 2 white pixels out of 4 pixels.

In the case of reducing to 1/4, the conventional method is to reduce the density by providing a threshold value. No. 2, N
o. 3, No. 4, No. 8, No. 11, No. 16
When the threshold value is 2 or more black pixels, all the patterns are 1 black pixel, and when the threshold is 3 or more pixels, 1 white pixel.

However, when the flag used in the image data compression method of the present invention is used, No. 2, No.
3, No. The pattern of No. 8 is converted into white pixels, and No.
10, No. 11, No. The 16 patterns are converted to black pixels. No. 2, No. 3, No. No. 8 pattern and No. 8 pattern. 10, No. 11, No. When 16 patterns appear with equal probability, a 1/4 reduced image using the flag is an image in which the ratio of black pixels and white pixels of the input image is accurately reduced.

FIG. 3 (d) shows the pattern of which the flag is 0 by black pixels and the pattern of which the flag is 1 by white pixels. The character of 48 × 48 pixels of FIG. 3 (a) is shown. It can be seen that the font has been converted into a 24 × 24 pixel font. In other words, by using the font as new font data, 48 × 48 pixels and 24 × 24 pixels can be obtained.
The character font data of pixels can be expressed by the data amount of one font. 24 × 2
576 bits (24
X24) and 2304 bits of the binary representation of 48 × 48 pixels are added, and 2880 bits is the number of bits before compression,
The compression rate for font data is 1770/2880 =
It can be said that it is 0.61.

The compression rate can be increased by recompressing the flag that becomes an image obtained by reducing the image data to 1/4. In this embodiment, an example of recompressing the flag will be described.

FIG. 6 is a flow chart showing the flow of the image data compression method of the present invention.

The outline of the flow will be described below.

First, a binary image composed of pixels is prepared. (S1001) N pixels by M columns. (S
1002) Labels and flags are assigned to all patterns that can be represented by a pixel block of N rows x M columns. Pattern
The details of the operation of assigning the label and the flag to the user are the same as those described in the first embodiment. (S1003) The number Z of blocks to be scanned is set to 0. (S1004) While scanning the input image line by line from the left, it is divided into pixels of N rows × M columns. (S1005) It is checked which pattern of the block of N rows × M columns of pixels matches the pattern of S1003, and the label and flag assigned to the pattern are given to the block. On the way, if N scanning is completed, an EOL (End of Line) code is output. Z is the maximum number of all blocks of the image, but when the input image is large or when plural types of images are included and divided and compressed, an appropriate value smaller than the total number of blocks may be provided. (S100
6, S1007, S1008, S1009, S110
0) If an appropriate number of blocks are biased, the cumulative occurrence frequency of labels is aggregated, and a short code is given to a label having a large cumulative occurrence frequency. (S1011) Determine the end of all blocks. (S1012) Code and EO if all blocks are finished
The L code and the RTC (Return to Control) code are saved.
(S1013) The number of times of repeated coding is designated in advance as the number of layers. If the number of times H is less than the number of layers, the flag and N and M are newly sent to S1003. (S10
14, S1015) If H is equal to or larger than the number of layers, the RTC is added to the code, the flag, and the EOL and stored. (S101
6) (Embodiment 3) FIG. 7 shows an image data compression apparatus 1 according to the present invention.
It is a block diagram which shows an Example.

The image data compression apparatus of the present invention comprises an information input section 71, an encoding section 72, a compressed data holding section 73, and a control section 74 for controlling these, and the encoding section 72.
Is composed of a blocking circuit 75, a block information conversion circuit 76, and an encoding circuit 77.

In the information input section 71, an analog signal obtained by scanning an image, a character font or the like and sampling in pixel units is converted into a digital signal by an A / D converter (not shown) in the information input section 71. After the conversion, it is input to the encoding unit 72. Details of the encoding unit 72 will be described later. The digital signal input to the encoding unit 72 has the code 3
00 is output to the compressed data holding unit 73.

The control section 74 receives a signal of the end of N scanning from the information input section 71 and outputs an N scanning end signal EOL (End of Line) to the encoding section 72. Furthermore, the control unit 7
4 receives a signal indicating the end of image data from the information input unit 71, and the data end signal RTC (Return to
Control) is output.

The compressed data holding unit 73 has the code 300.
Is to hold.

The process in which the input digital signal becomes the code 300 in the encoder 72 will be described in detail below.

The digital signal input to the encoding unit 72 is input to the blocking circuit 75 in the encoding unit 72,
It is divided into blocks for each N × M pixels, input to the block information conversion circuit 76, and converted into a flag 100 and a label 200. The details of the blocking circuit 75 and the block information conversion circuit 76 will be described later.

The flag 100 and the label 200 are
It is input to the encoding circuit 77. Details of the encoding circuit 77 will be described later. The flag 100 and the label 200 are coded as a code 201 in the coding circuit 77 by a known entropy coding method such as Huffman method or arithmetic coding method.

The coding circuit 77 in the coding unit 72 is
The EOL received from the control unit 4 is converted into a code and added to the code 201 for every N scans, the RTC is converted into a code and added to the end of the code 201 of the end of all image data,
The reference numeral 300 is used.

FIG. 8 shows an example in which the block forming circuit 75 and the block information converting circuit 76 are formed by using a gate circuit when one pixel is binary and one block is 2 × 2 pixels. It is a thing.

The blocking circuit 75 is composed of a line buffer 81 for one line, a line buffer 82 for two lines, and latches 83, 84, 85 and 86. The block information conversion circuit 76 is an AND gate. 87a to 87
p and OR gates 88a to 88i.

The digital signal output from the information input unit 1 is input from the input terminal 80 to the line buffer 81 of the blocking circuit and accumulated as data for one line. A digital signal represents a black pixel when it is high and a white pixel when it is low. Hereinafter, high is indicated by 1 and low is indicated by 0. The digital signals are input to the line buffer 82 line by line, and digital signals for a total of two lines are accumulated. The data of 4 pixels, A, B, C and D are latched by 8
Latched by 3, 84, 85, 86. At this time, if the input digital signal does not have the data for two lines, the data for one line is copied and
It is accumulated in the line buffer 82 as data for a line.

While the data for two lines is being processed, the next data is input to the line buffer 81.

The data of 4 pixels, A, B, C, D are 8 from the 16 AND gates 87a of the block information conversion circuit.
It is input to 7p and becomes 16 pieces of pattern information. For example, the pattern No. 1 shown in FIG. In the AND gate 87a, 1 is the AND circuit 67 when 0000 is input.
One is output as output 1 from a. Similarly, the pattern No. 1 in FIG. 9 is 111 in the AND gate 87b
Output 1 from AND Gate 87b when 1 is input
Is output. AND gate 87a to 87p
The inputs and outputs up to are shown in FIG. 9 (a) using the corresponding pattern numbers in FIG.

The outputs of the AND gates 87a and 87b are O
It is input to the R gate 88a, and the No. in FIG. 1 and N
o. The same label 1 is output for 9. Similarly,
The outputs of the AND gates 87c and 87d are the OR gates 88.
2 is input to No. b in FIG. 2 and No. The same label 2 is output for 10. Similarly, the OR gates 88c, 88d, 88e, 88f, 88g, 88h are
The labels 3, 8, 4, 5, 7, 6 are output to the bus 89.
The relationship between the inputs and outputs of the OR gates 88a to 88h is shown in FIG. 7 (b) using the corresponding label numbers in FIG.

The OR gate 88i is the AND gate 87.
b, 87d, 87f, 87h, 87j, 87l, 87
The outputs of n and 87p are input and the flag 100 is output. The relationship between the pattern input of 2 × 2 pixels and the output of the OR gate 88i is shown in FIG. 9 (c) using the corresponding pattern numbers in FIG.

AND gates 87b, 87d, 87f, 8
When the processing of the data A, B, C, D in 7h, 87j, 87l, 87n, 87p is completed, the latches 83, 8
4, 85 and 86 latch the next data E, F, G and H, and a flag and label are generated by the same processing as A, B, C and D. In the last block of the line buffer 82, if there is no 4-pixel data, the latch 83,
84, 85, 86 convert data i, j to i, i, j, j
Latch like. When the processing of all the data in the line buffer 82 is completed, the line buffer 82 accumulates digital signals for one line from the line buffer 81 for two lines in total. When a new digital signal for two lines is accumulated in the line buffer 82, it is converted into a flag and a label by the same processing as above.

In the above embodiment, the input image information is binarized and divided into blocks of 2 × 2 pixels, and the block information is converted into labels and flags. However, it is possible to divide the block size by changing the circuit slightly.
Needless to say.

FIG. 10 shows an example in which the encoding circuit is composed of a general-purpose processor. The encoding circuit
The CPU 101 is a general-purpose processor, the RAM 102, the code memory 103, and the ROM 104. The CPU 101 is connected to the bus 89, the bus 105, and the output bus 108. The RAM 102 is the bus 106
Is connected to the CPU 101 via the bus 105. The code memory is connected to the CPU 101 via the bus 107 via the bus 107.

The label output from the block information conversion circuit is input to the CPU 101 via the bus 89, and the cumulative appearance frequency for each label up to the number of blocks Z is measured. The cumulative appearance frequency and the flag and label output on the bus 89 are output from the CPU 101 to the RAM 102 and stored therein. The number of blocks Z is the number of blocks generated from all the pixels of a normal image, but may be small. CPU 101
Assigns fewer codes to the label with the higher appearance frequency. The code is assigned by a known entropy coding method such as Huffman method or arithmetic coding method. The assigned label code is stored in the code memory 103.

Upon receiving the EOL signal, the CPU 101 sets 1
RAM of EOL signal at the end of line flag and label
It is stored in 102. CPU 101 receives RTC signal
R flag the EOL signal at the end of the flag and label for all images.
It is stored in the AM 102.

The codes of EOL and RTC are code memory 10
3 is stored in advance.

The CPU 101 stores the label, the EOL signal and the RTC signal stored in the RAM 102 in the code memory 1
The reference numeral 03 is referred to, and encoding is performed to obtain the reference numeral 300. The flag and the code 300 are output to the bus 108 by the CPU 101 and output to the compressed data holding unit via the bus 108.

The operation of the CPU 101 described above is based on the RO
It is stored in M104 as a program.

The operation when the encoding circuit is configured by using a general-purpose processor has been described above. However, the encoding circuit may be composed of dedicated hardware.

[0076]

As described above, the present invention provides a code table.
By halving the number of bits, it is possible to provide an image data compression method and apparatus capable of achieving high compression efficiency by reducing the number of bits assigned to the control code and the code table itself. Further, the time required for the compression processing can be shortened by reducing the code table.

Furthermore, in the invention of claim 2, when applied to an image such as character font data, the flag is used as character font data having the same type but different resolution, so that images having different resolutions in the same compressed file are used. A high compression rate can be obtained because a plurality of data will be stored.

[Brief description of drawings]

FIG. 1 is a flowchart showing a processing flow of an image data compression method of the present invention.

FIG. 2 shows the operation of converting a pattern into a label and a flag.
The figure for demonstrating using the example of the block of 2x2 pixel by which the value was input.

3A to 3D are diagrams showing a case where the method of the present invention is applied to a character font image.

4A is a diagram showing an example of correspondence between labels and codes in FIG. FIG. 6B is a diagram showing an example of correspondence between patterns and symbols in FIG.

5A and 5B are diagrams showing an example of a storage order of a code table, a label, a flag, and a control code.

FIG. 6 is a flowchart showing a processing flow showing an example in which the flag is compressed again using the image data compression method of the present invention.

FIG. 7 is a block diagram showing an embodiment of an image data compression device of the present invention.

FIG. 8 is a diagram showing an example of a block formation circuit and a block information conversion circuit.

9A is a diagram showing the relationship between the input and output of the AND gate shown in FIG. FIG. 9B is a diagram showing the relationship between the input and output of the OR gate shown in FIG. (C) is an O that outputs the flag of FIG.
The figure which showed the relationship of the input and output of R gate.

FIG. 10 is a diagram showing an example of an encoding circuit.

[Explanation of symbols]

 71 Information Input Unit 72 Encoding Unit 73 Compressed Data Holding Unit 74 Control Unit 75 Blocking Circuit 76 Block Information Conversion Circuit 77 Encoding Circuit 81 Line Buffer 82 Line Buffer 83, 84, 85, 86 Latch 87 AND Gate 88 OR Gate 101 CPU 102 RAM 103 Code memory 104 ROM

Claims (3)

[Claims] 1. A method for compressing binary image data having a density value of 0 or 1 obtained by scanning an image and sampling in pixel units, wherein (a) a pattern represented by N rows × M columns. 2 out of
For each of the two patterns, if the value obtained by adding the density values of the pixels in the same row and the same column is 1 (high) in all the positions of N rows × M columns, the two patterns are respectively added. , Give the same label and 0 to one pattern
(Low) and the other one is assigned a flag of 1 (high) to classify patterns represented in advance in pixels of N rows × M columns, and (b) image data to pixels of N rows × M columns. It is divided into blocks, and (c) the pixel block of N rows × M columns is checked to see which pattern classified in (a) matches, and the label and flag given to the matched pattern. Is assigned to the pixel block, (d) the appearance frequency of the label is measured for a plurality of image blocks, and a short code is assigned in order from the label with the highest appearance frequency. (E) It is assigned to each of the pixel blocks. An image data compression method, characterized in that a code corresponding to a given label is added, and the flag given in (f) and (c) and the code given in (e) are used as compression results. 2. The image compression method according to claim 1, wherein a flag which is a compression result is recompressed by the processing of (a) to (f) according to claim 1. Item 1. The image data compression method according to Item 1. 3. An information input section for scanning an image to obtain a binary digital signal having a density value of 0 or 1, an encoding section for encoding the digital signal, a compressed data holding section for storing the code, and In a device including an information input unit, the encoding unit, and a control unit that controls the compressed data holding unit, (a) a block circuit that divides image data into pixel blocks of N rows × M columns, and (b) N Some 2 of the patterns expressed in rows x M columns
For each of the two patterns, if the value obtained by adding the density values of the pixels in the same row and the same column is 1 (high) in all the positions of N rows × M columns, the two patterns are respectively added. , The same label is given, and a flag of 0 is given to one pattern and a flag of 1 is given to the other pattern to classify the patterns expressed in pixels of N rows × M columns in advance, (a) A block information conversion circuit that checks which of the patterns the pixel block that has been divided into blocks matches, and adds the label and the flag given to the matched pattern to the pixel block; The frequency of appearance of the label is measured for each image block, a short code is assigned in order from the label with the highest appearance frequency, a code corresponding to the label to which it is given is given to each pixel block, and (B)
An image data compression device, comprising: an encoding circuit that uses the flag added in step 1 as a compression result.