JPH0224432B2 - - Google Patents

Description

[Detailed Description of the Invention] [Field of Application of the Invention] The present invention relates to an image information compression method, and in particular to a pattern data compression method that allows easy encoding and decoding processing and reduces memory capacity. .

[Background of the invention]

Traditionally, the data compression method used in FAX, etc. is MH (Modified Huffman) or MR.
(Modified Read) This is data compression by encoding using a code, and although it has the advantage of increasing the compression rate, it requires complicated processing steps in the decoding process to return the encoded data to a dot pattern. In order to increase the speed, a large amount of dedicated hardware for encoding and decoding is required, which has the disadvantage of being expensive.

Furthermore, there are patterns that have no compression effect, and it is known that in the worst pattern, in the case of MH code, the data before encoding is increased by as much as 4.5 times after encoding. Therefore, the storage capacity of the storage device that stores pattern data must be determined by taking into account the frequency of occurrence of the worst pattern, and therefore, it is not possible to expect a significant reduction in capacity, even though the average compression rate is high.

In addition, when scanning and importing image data on paper sheets, there is a requirement that the scan data must be stored in the storage device within a certain period of time in order to maintain uniform scanning speed. However, there were problems such as having to ensure a throughput (storage speed) that matched the worst-case pattern.

Also, each line is divided into blocks of consecutive pixels, and if there is even one bit of information in each block, it is set as "1", and if there is no information at all, it is set as "0", and a table is created. A method has been proposed in which only the pixel information of a block is stored (see Japanese Patent Laid-Open No. 58-53272). However, with this method, it is not possible to compress all "1" data, and the compression effect is low, especially for devices that blacken the background of a form.

[Purpose of the invention]

The purpose of the present invention is to improve these conventional drawbacks, to realize encoding and decoding processing with a simple circuit, to compress even the worst patterns, and to reduce the capacity of pattern storage memory. The object of the present invention is to provide an image information compression method that enables image information to be compressed.

[Summary of the invention]

In order to achieve the above object, the image information compression method of the present invention divides a time-series binary image signal into word data in units of multiple bits and stores them in a memory. When all bits are white or black, it is stored in memory, but when all bits are white or black, it is decided whether to store it in memory or not based on the result of comparing the word data with the contents of the word data immediately before it. However, the present invention is characterized in that a flag bit indicating whether or not the word data is stored in the memory is generated for each word data, and the flag bit is also stored in the memory.

That is, the first point of the present invention is to scan image data on a sheet of paper using a raster scan method,
When importing into memory as binary data, the bit string of binary data is divided into multiple bit units (word units), and if the bits that make up a word are all white data or all black data, the word is transferred to memory. , and only other words of data are stored in memory. Therefore, by representing the blank space that occupies most of the paper sheet as white data and capturing the background of the paper sheet as black data, these data are not stored in memory, so the memory capacity for storing image data can be greatly reduced. can be reduced.

The second point of the present invention is to provide a flag bit corresponding to each word to indicate whether or not that word is stored in the memory, and to map this to an area separate from the pattern storage area of the memory. The point is that it is stored as . That is, at the first point, simply storing or not storing word by word depending on its contents is insufficient for decoding, so a flag is provided. In this way, when decoding, the map data is first read out, it is determined whether or not the word in question is stored in memory, and a flag bit is set to indicate that the word is stored. In this case, the corresponding word is read from the pattern storage area, and when the flag bit is not set, a word of all-bit white data or all-bit black data can be generated.

Next, the third point of the present invention is that as a condition for determining not to store it in memory, an initial value is determined to be either the result of comparison with the contents of the immediately previous word, or white or black when the word is at the beginning. At the point.

In other words, in the coding system using only the first and second points, each word has one flag bit, so there is only one meaning that indicates that the word is not stored in memory, and all bits are Only either white data or all-bit black data is subject to compression. Therefore, if most of the data is limited to either white data or black data, a great compression effect can be expected, but if both white data and black data are mixed, it is not possible to determine which data is the data. Therefore, if it is necessary to compress both white data and black data, set the flag bits to 2 bits for each word, so that it can be distinguished whether white data is black data or not when the word is not stored. There are possible ways. However, this reduces the compression effect by the increase in flag bits. Therefore, the third point is to use the comparison result with the previous word as a condition for determining not to store the word in the memory. For example, if the content is the same as the previous word, it is not stored and it is possible to compress both white data and black data without increasing the flag bits.

The comparison target as a judgment condition for omitting storage is:
Either all bits of the previous word, or as shown in the example below, the contents of the last bit of the previous word, or the content of the previous word with a larger number of white or black bits. Various methods can be considered, but in any case, when decoding indicates that the flag bit is not stored in memory, the contents of the immediately preceding word may be referred to. Note that in cases where the immediately preceding word cannot be defined, such as at the beginning of a scan, the initial value may be determined in advance as either white or black. According to the compression method of the present invention, if the number of bits constituting a word is 16 and the flag bit is 1 bit, even in the worst pattern where compression is not effective, the amount of data will only be 16 + 1/16 = 1.0625 times. This is a significant improvement compared to the 4.5 times the MH code, and can solve problems such as the need to increase throughput to capture worst-case patterns. On the other hand, if we look at the maximum compression rate, it is about 100 times with the MH code, but with this method, it is 16/1 = 16 times in the above example, and unless the number of bits that make up a word is increased, it will not be that large. Although the compression rate is not high, a reliable compression effect can be expected. Furthermore, considering that the memory capacity for pattern storage must be determined to cover the sheet of paper containing the expected maximum amount of data, the memory capacity that should be prepared even with this method is smaller than that of the conventional method. This is about the same as MH code, etc., and the actual memory reduction effect is almost the same.

In addition, when determining the number of bits of a word,
It is desirable to determine the optimum value according to the characteristics of the pattern to be compressed.

[Embodiments of the invention]

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

FIG. 1 is a block diagram of an optical character reading device to which the present invention is applied.

In FIG. 1, 1 is a paper slip, 2 is a sensor, 3 is a binarization circuit, 4 is an encoding circuit, 5 is a memory, 6 is a processor, 7 is a display device, 8 is an output device, and 9 is a paper feed mechanism. It is.

In response to instructions from the processor 6, the paper feed mechanism 9
Paper slip 1 is conveyed. The image data on the conveyed paper form 1 is photoelectrically converted by the sensor 2, binarized by the binarization circuit 3, data compressed by the encoding circuit 4, and stored in the memory 5. Ru. The processor 6 sequentially decodes the image data stored in the memory 5, cuts out character parts, performs recognition processing, and displays the recognition results on the display device 7 or outputs them to the output device 8.

FIG. 2 is a diagram showing a specific example of the encoding circuit shown in FIG. 1.

In FIG. 2, 401 is a D-type flip-flop, 402 is an exclusive OR gate, and 401 is a D-type flip-flop;
03 is JK type flip prop, 404,
405 is a shift register, 406 and 412 are multiplexers, 407 and 409 are counters, and 41
0, 411 is an address counter, 408 is a non-compression mode switch, and 413 is a write control circuit.

The data 421 binarized by the binarization circuit 3 is
The data is shifted by n bits in shift register 404 by clock 422 and converted into n-bit word data. On the other hand, the binary data 421 is compared with the output of the flip-flop 401, which stores the last bit of the word immediately before the word to be converted by the shift register 404, by the exclusive OR gate 402, and the word data is If there is a mismatch in even one bit, flip-flop 403 is set. With this set, the flag bit is set. In addition, flip flop 4
Since there is no immediately preceding data at the beginning of each scan, 01 is initialized in advance and supplies a set or reset output.

The counter 407 is a counter that counts the number of shifts of the shift register 404. When the shift register 404 is shifted by n bits, the output of the counter 407 becomes "1", and this output "1" is shifted. It is sent to terminal T of register 405 as a synchronization signal for shifting the contents of flip-flop 403 into shift register 405. When the contents of flip-flop 403 are shifted, for the next word data,
The contents of the second bit of the binarized data 421 are set in the flip-flop 401. shift·
When shifting the contents of the flip-flop 403 to the register 405, if the contents are "1", the preset address counter 4
At the same time, a write signal is sent to the memory write control circuit 413 in order to store data in the memory 5.

When the write control circuit 413 receives a write signal from the flip-flop 403, it controls the multiplexers 406 and 412 to send the contents of the counter 410 as an address and the contents of the shift register 404 as data to the memory 5. Store. Address counter 410 is triggered by a count-up signal received from flip-flop 403 after data storage is completed, and the address counter 410 increments the contents by one.

Note that if the content of the flip-flop 403 is "0", no write signal is output, so
Pattern data is not stored in memory 5.
Further, the counter 409 is connected to the shift register 40
This is a counter that counts the number of shifts of 5, and when the shift register 405 is shifted by n bits, the preset address counter 4
At the same time, a write signal is sent to the memory write control circuit 413 for storing in the memory 5. When the write control circuit 413 receives the write signal from the counter 409, it controls the multiplexers 406 and 412 to store the contents of the counter 411 as an address and the contents of the shift register 405 as data in the memory 5. As a result, n bits (1 word) of flag bits are stored in the memory 5. After the address counter 411 has finished storing data in the memory 5, it is triggered by a count-up signal sent from the counter 409 and increments its contents by one.

In FIG. 2, the flip-flop 403 is set at the beginning of each scan, but it may be reset in reverse, or it may be set or reset only at the first scan of encoding. You may also do so.

FIG. 3 and FIG. 4 are explanatory diagrams of encoded data stored in the memory, respectively.

In FIG. 3, shift registers 404, 405
4 bits each, address counter 410
The initial value of (00) ₁₆ , address counter 411
The initial value of (100) ₁₆ , the first 10 bits of each scan
(Initial value of each scan of the flip-flop 401) is set to "1", and data stored in the memory 5 for the binary input data 11A to 13A of each scan is shown. In the figure, 11B to 13B indicate flag bits for the binary input data 11A to 13A. The pattern data 14 stores only the data in which the flag bit is "1", and the map data 15 stores the flag bit. In other words, in the input data 11A, compared with the final bit 10 of the previous 4 bits, it is not stored because it is the same 4 bits.
The flag bit is “0” and the next 4-bit pattern “1010” is the address (00) of table 14 _.
Store in. Since the next data is all "0", it is not stored, and the next data pattern "0101" is stored at address (01) ₁₆ of the table 14. In input data 12A, the last of the previous 4 bits
Since it is a different 4 bits compared to 10, even if it is all “0”, the address of table 14 (03) ₁₆
Store in. In this way, table 1 in memory 5
Only pattern data corresponding to flag bit "1" is stored on table 15, and map data of flag bits is stored in table 15 divided into four bits.

In addition, in FIG. 3, pattern data 14
The capacity of the binary input data 421 is compressed or uncompressed and varies depending on the content of the binarized input data 421, so decoding from an arbitrary scan position is not possible. Therefore, as shown in FIG. 4, the contents of address counter 410 are transferred to multiplexer 40.
6, the address counter 411 is used as an address once for each scan, and the contents of the address counter 410 are stored as data in the memory 5, so that the pattern data storage address can be set to any scan position. This allows decoding to be performed from any scan position. FIG. 4 shows map data in the memory 5 in that case. In table 16 of Fig. 4,
The start address of the pattern data corresponding to the first four flag bits of the map data is stored at address “0000” = (00) ₁₆ , and the next four
It can be seen that the start address of the pattern data corresponding to the two flag bits is also stored at address "0000"=(00) ₁₆ . It can also be seen that the last 4-bit pattern of data 13A, which is an arbitrary scan position, is stored at address "0101"=(05) ₁₆ .

FIG. 5 is a diagram showing a compression target area in the present invention.

This indicates that only the area within the dotted line shown in FIG. 5 is stored in the memory 5, and the rest is compressed. That is, it is only necessary to store the frame lines, numbers, and alphanumeric characters on the paper slip, and the black background and blank spaces within the paper slip are not stored, so the memory capacity may be small.

In addition, in FIG. 2, a programmable mode switch 408 is provided and connected to the set terminal of the address counter 403 and the reset terminal of the counter 409, so that the map data is not stored in the memory 5 and the pattern Since data can be stored at all times, in a device where the capacity of the memory 5 is set for large paper sheets, if the amount of image data is small, such as for small paper sheets, the binarized input data 421 can be converted into word data as is. If only the conversion is performed and stored in the memory 5, the decoding process becomes unnecessary and the speed can be increased.

Note that the present invention is not limited in its application to pattern data from paper sheets, but can be used as a method for compressing a wide variety of general pattern data.

〔Effect of the invention〕

As explained above, according to the present invention, encoding and decoding processes can be configured with simple and inexpensive circuits, restoration is easy, and data does not increase contrary to the worst pattern. Therefore, the memory capacity for storing patterns can be reduced. Furthermore, since both the all-bit black pattern and the all-bit white pattern are compressed, even in a device where the background of a form is black, the black background and the white on the form can be compressed. Therefore, if applied to an image input device or an optical character reading device that handles pattern data on most or the entire surface of a sheet of paper, it will be very effective.

[Brief explanation of drawings]

FIG. 1 is a block diagram of an optical character reading device to which the present invention is applied, FIG. 2 is a specific example of the encoding circuit of FIG. 1, and FIGS. 3 and 4 are diagrams of encoded data stored in memory. The explanatory diagram, FIG. 5, is a diagram of a form showing the area to be compressed in the present invention. 1: Paper slip, 2: Sensor, 3: Binarization circuit, 4:
Encoding circuit, 5: memory, 6: processor, 7:
Display device, 8: Output device, 9: Paper feeding mechanism, 40
1: D type flip-flop, 402: exclusive OR gate, 403: JK type flip-flop, 404, 405: shift register, 406, 412: multiplexer, 407,
409: Counter, 410, 411: Address
Counter, 413: Write control circuit.

Claims (1)

[Claims] 1 When dividing a time-series binary image signal into word data in units of multiple bits and storing it in memory, the word data is stored in memory except when all bits are white or black, but when all bits are When the word data is white or black, it is determined whether or not to store it in memory based on the result of comparing the word data with the contents of the word data immediately before the word data, and each word data
An image information compression method characterized in that a flag bit indicating whether or not the word data is stored in a memory is generated for each data, and the flag bit is also stored in the memory.