JPH09289591A - Image encoding device, image decoding device, and their method - Google Patents

Abstract

PROBLEM TO BE SOLVED: To perform encoding corresponding to the correlation of binary image data, and improve the compressibility. SOLUTION: The two-dimensional correlation of the binary image data is detected by checking whether or not pixel data in an encoding line and its precedent line match each other (S101), whether or not all the pixel data in the encoding line are the same (S103), whether the pixel data in the encoding line are in pairs (S105), whether the pixel data in the encoding line have intense correlation at intervals of 8 pixels (S107), and the encoding is performed (S102, S104, S106, S108, and S109).

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an image encoding device for encoding and decoding a digital image, an image decoding device and their methods.

[0002]

2. Description of the Related Art The well-known PackBits method is a simple data compression method that encodes run lenses in byte units. FIG. 1 is a diagram for explaining the simple principle of the PackBits method. In this method, if a plurality of byte data with the same value continues, a tag (Ta
g) and its value form a code. This is called a repeat mode. Further, when the value of each byte data is different, a code is created with a tag indicating each different byte number and each value. This is called a copy mode (Copy).

FIG. 2 is a diagram showing the correspondence between the tag value and each mode. As shown, when the tag value is 0 to 127, the copy mode and its run length (byte number) are assigned, and when the tag value is 129 to 255, the repeat mode and its run length (byte number) are assigned. If the number of bytes in the copy mode exceeds 128, or if the number of bytes in the repeat mode exceeds 127, it is divided into two or more codes. A tag value of 128 is not normally used as a NOP.

On the other hand, on the decoding side, the value of the tag is checked, and when the value N is 129 to 255, the byte data following the tag is repeated (256-N) times. The tag value N is 0 to 1
When it is 27, the byte data of N bytes following the tag is copied.

As described above, the above-described method has a feature that it is possible to compress data obtained by byte-packing (8 pixels / 1 byte) a binary image. This is because many target binary images have a white background. Moreover, since the decoding process is very simple, it is suitable for applications requiring high speed.

[0006]

SUMMARY OF THE INVENTION
The PackBits method does not use the peculiar characteristics of the image such as the two-dimensional correlation of the image, so the compression rate is low compared to other image encoding methods, and it is applied to applications that require a high compression rate. There was a problem that it was difficult.

The present invention has been made to solve the above problems, and an image coding apparatus, an image decoding apparatus, and an image decoding apparatus that perform coding according to the correlation of binary image data and further improve the compression rate. The purpose is to provide a method.

[0008]

In order to achieve the above object, the image coding apparatus of the present invention has the following configuration. That is, a detection unit that detects the correlation of the binary image data, a determination unit that determines the encoding according to the detection result of the detection unit, and an encoding unit that performs the encoding determined by the determination unit. Prepare

In such a configuration, the correlation between the binary image data is detected, the coding is determined according to the detection result, and the determined coding is performed.

The image decoding apparatus according to the present invention has the following configuration.

That is, it is provided with a judging means for judging the code coded based on the correlation of the binary image data, and a decoding means for carrying out decoding according to the judgment result of the judging means.

In such a configuration, the coded code is judged based on the correlation of the binary image data, and the decoding is performed according to the judgment result.

Further, the image coding method according to the present invention has the following steps.

That is, a detection step of detecting the correlation of the binary image data, a determination step of determining the encoding according to the detection result of the detection step, and an encoding step of performing the encoding determined by the determination step. And the process.

The image decoding method according to the present invention has the following steps.

That is, there is a determining step of determining a coded code based on the correlation of binary image data, and a decoding step of performing decoding according to the determination result in the determining step.

[0017]

Embodiments of the present invention will be described below in detail with reference to the drawings.

In the embodiment, the following features of the binary image are used. (1) Two-dimensional correlation: It tends to occur when the coded line has the same value as the data of the previous line. This is set to line copy mode (LCP), a special code is sent, and PackBits processing is not performed. (2) There are many all-white lines and all-black lines: In most cases, it is detected as (1) above, but if the previous line is not all-white or all-black lines, a special code is sent and PackBits processing is not performed. . Particularly, in the case of a document image in which a document is written in a large number of lines, this corresponds to the highest line between lines (the line next to the lowest line of characters). (3) Utilizing a pair of two pixels: There are cases where the value of a binary pixel takes the same value in a pair of two pixels, and this is detected, and the thinning (subsampling) processing is performed every other pixel on the code side.
Halves the number of encoded bytes. Next, this is PackBits encoded. On the decoding side, the original data is completely restored by decoding the data of half the original number of bytes and repeating each bit data twice.

FIG. 3 is a diagram for explaining a pair of two pixels and a thinning process. The two-pixel pair means a case where the data of all lines have the same value every two pixels. In the example shown in FIG. 3, since white, black 2, white 4, black 2, white 2, and black 4 are established, this is determined as a 2-pixel pair.

Next, when this is sampled for each pixel, white 1, black 1, white 2, black 1, white 1, black 2 are obtained, and this line data is encoded by PackBits. On the decoding side, the original data can be completely restored by decoding half the data of all the lines and then repeating the bit data. (4) Use correlation every 8 pixels: When the binary image is subjected to pseudo halftone processing such as the systematic dither method, it can be determined by observing the bit correlation.

FIG. 4 is a diagram for explaining the correlation every 8 pixels and the bit interleaving process. Each 1-byte data is composed of 8 pixels (up to). Whether the one byte of interest has a strong correlation with the next one byte can be examined by an exclusive OR (EXOR) for each bit. In the embodiment, EXNOR is taken for convenience of processing. That is, when the value of each bit of the two bytes is the same, the value is "1". If all 8 bits are "1", it is assumed that the correlation is strong. However, in the above process, the value of 1 byte is "0".
Alternatively, when the value is “255”, the strength becomes stronger, and a judgment formula for excluding these cases is required.

As described above, as a method of detecting the bit correlation, "when the EXNOR of each bit at 8-pixel intervals is all" 1 "and the data is neither" 0 "nor" 255 "" is effective. However, it is not limited to this.

When the bit correlation is strong, the PackBits process is performed on the data bit-interleaved on the code side. Here, the bit interleaving is to collect the bits at the position of each byte and encode first, collect the bits at the next position and encode, and encode the bit at the final position.

On the other hand, on the decoding side, the process of returning the bit position is performed based on the decoding result to completely restore the original data. The above-mentioned processing is effective for an image binarized by 8 × 8 dither or the like.

The NOP code 128 is used as an escape code (ESC), 1-byte data is added after this code, and special processing is instructed according to the value of this data.

[First Embodiment] FIG. 5 is a flow chart showing an encoding process according to the first embodiment. First, in step S101, the matching between the encoded line and the previous line is determined. If they match, the process proceeds to step S102 to output the previous line copy code.

FIG. 6 is a flowchart showing details of step S101. First, in step S201, the data of the encoded line and the data of the previous line are read, and step S2
In 02, the pointer i indicating the data position is initialized.
Then, in step S203, it is determined whether or not it is the same as the previous line. If not, the process proceeds to step S204, the determination flag (LCP_flg) is set to "0", and the process ends. However, if they are the same, the process proceeds to step S205, the pointer i is updated, and it is checked in step S206 whether the data determination for one line is completed. here,
If it has not been completed, the process returns to step S203, and the above processing is repeated. After that, when the processing is completed, the process proceeds to step S207, the determination flag (LCP_flg) is set to "1", and the processing is completed. Here, max is the number of data in one line.

Returning to FIG. 5, in the determination of step S101,
If they do not match, the process proceeds to step S103, and it is determined whether the coding lines are all the same data. If the data is the same, the process proceeds to step S104, and the same code and a code indicating the value of the data are output.

FIG. 7 is a flowchart showing details of step S103. First, in step S301,
The data of the encoded line is read and the first data is stored in the register Ref. Then, in step S302,
A pointer i indicating a data position is initialized. Next, in step S303, it is determined whether or not the data pointed to by the pointer is the same as Ref.
Then, the determination flag (Same_flg) is set to "0", and the process ends. However, if they are the same, step S
The process proceeds to 305, the pointer i is updated, and step S306
Check if the data judgment for one line is completed.
If not finished, the process returns to step S303,
The above processing is repeated. After that, when finished, step S
Proceeding to 307, the determination flag (Same_flg) is set to "1" and the processing is terminated. Here, max is the number of data in one line.

Returning to FIG. 5, in the determination of step S103,
If the data is not the same for all lines, the process proceeds to step S105, and it is determined whether two pixel pairs are established. If the condition is satisfied, the process proceeds to step S106, the two-pixel pair code is output, and the overlapping pixels are thinned (subsampling) to halve the number of pixels, and then step S109.
Proceed to and perform PackBits encoding.

If the pair of two pixels is not established in step S105, the process proceeds to step S107 to calculate the correlation strength every eight pixels, and if the correlation is strong, step S1.
Proceed to 08. In step S108, the bit interleave code is output to rearrange the bits, and in step S109, PackBits encoding is performed.

If the correlation is not strong in step S107, the process proceeds to step S109 to perform PackBits encoding. As a result, the processing for one line is completed, and if this is performed for all lines, the processing for the entire image is completed.

FIG. 8 is a flow chart showing the decoding process according to the first embodiment. First, in step S401, it is determined whether the tag is the front line copy code, and Yes
In the case of s, it progresses to step S402 and outputs the previous line data. However, if No in step S401, the process proceeds to step S403 to determine whether the tags are the same data code on all lines, and if Yes, the process proceeds to step S404 to output the data understood from the code for all lines. If No in step S403, step S405
Then, it is determined whether the tag is a two-pixel pair code. If Yes, the process proceeds to step S406 to perform PackBits decoding, and then the original data is restored by the process of repeating 1 bit in step S410.

On the other hand, if the code is not a two-pixel pair code in step S405, the flow advances to step S407 to determine whether the tag is a bit interleave code. Here, in the case of Yes, the processing proceeds to step S408, PackBits decoding is performed,
Then, in step S411, a process of returning the bit interleave for every 8 pixels to the decoded data is performed to restore the original data. If No in step S407, the process proceeds to step S409 to perform normal PackBits decoding processing. As a result, when the processing for one line is completed and the above-described processing is performed for all the lines, the processing for the entire image is completed.

[Second Embodiment] Next, the second embodiment according to the present invention will be described in detail. In the second embodiment,
When the number of tags is large, the processing in byte units is given up and switched to bit processing. With any of the methods of the first embodiment, it may be difficult to compress with PackBits. In that case, the method of switching to bit-unit processing is effective.

FIG. 9 is a flowchart in which a process for switching from the byte unit process to the bit unit process is added. The processing from step S501 to step S509 shown in FIG. 9 is performed by step S shown in FIG. 5 in the first embodiment.
101 to step S109.

In step S510 shown in FIG. 9, Pa
The number of tags in the ckBits process is compared with the set threshold value, and if it is equal to or larger than the set threshold value, the process proceeds to step S511 to switch to the bit unit process. That is, the number of PackBits tags is counted, and if the number is larger than the set threshold value, it is determined that compression with PackBits is difficult. As an example of the bit unit processing, it is possible to use MH (Modified Huffman) which is used in facsimile encoding.

Since it is possible that the speed of the encoding process becomes slower by performing this switching, it is necessary to determine the set threshold value, the switching timing, etc. by the trade-off between the compression rate and the speed.

[Third Embodiment] Next, a third embodiment of the present invention will be described in detail. In the third embodiment,
Data is reduced by changing the method of creating tags.

The code in the repeat mode of PackBits described above is composed of a run length and 2 bytes of its value. However, when it is applied to the coding of a binary image, this value often takes 0 (white) and 255 (black).
In addition, there is a feature that the appearance frequency of black run length is long, but it is low. In consideration of this, it is possible to determine a new tag table defining the run length and its value as shown in FIG.

As shown in the figure, the tag value is 255 to 19
Up to 2, the number of bytes of the white run, from 191 to 160, the number of bytes of 1 to 32 of the black run, and 159 to 1
Up to 29, the number of bytes from 1 to 32 of other runs is shown. That is, if the tag value is 255 to 160, the value is associated with the run length of white or black, and is represented by only 1 byte of the tag. For 159 to 129, 1 byte data indicating the value next to the tag is displayed. wear.

As a result, the code length in the repeat mode is shortened, and the compression rate can be improved by 20 to 30%.

[Fourth Embodiment] The fourth embodiment according to the present invention will be described in detail below. In the fourth embodiment,
The table is switched after the repeat mode or the copy mode.

Examination of the PackBits type tag generation method described above reveals that the following rules exist. (1) Consideration when the second repeat mode follows after the first repeat mode When the byte length of the first repeat mode is other than the maximum value,
The second repeat mode has a value different from the first value. For example, when the data of the first repeat mode is “0”,
The data in the second repeat mode is a value other than "0". (2) Consideration of the next tag of the first copy mode When the second copy mode follows after the first copy mode, there is nothing except when the number of bytes of the first copy mode is the maximum value. Therefore, when the number of bytes in the first copy mode is other than the maximum value, the subsequent mode is only the repeat mode. Considering this, the tag table can be dynamically switched according to the previous mode and the number of data. This shows that the table can be used efficiently (that is, there are no unused table values).

FIG. 11 is a diagram showing a table for realizing the above (1). The first value, the second value, and the third value in the figure are dynamically switched. That is, when the previous is repeat mode and the value is "0" and the length is other than the maximum value, the first value is "25".
5 ", the second value is a value that has appeared a lot until then, and the third value is a value other than that, and a tag is generated.

FIG. 12 is an example of a table for realizing the above (2). When the previous is the copy mode and the length is other than the maximum value, the length of the data "0" is set for the tag value of 0 to 127, the length of the data "255" is set for 255 to 192, and the length of 191 to 191 is set. Up to 129, tag data is generated so as to indicate the length of other data.

As described above, according to the embodiment, the 2
Image-specific properties such as dimensional correlation are detected, and PackBits
By applying a special process to the process, it is possible to improve the compression rate.

The present invention can be applied to a system including a plurality of devices (for example, a host computer, an interface device, a reader, a printer, etc.), but can be applied to a single device (for example, a copier, a facsimile). Device).

Further, an object of the present invention is to supply a storage medium having a program code of software for realizing the functions of the above-described embodiments to a system or an apparatus, and to supply a computer (CPU or MP) of the system or the apparatus.
It goes without saying that U) is also achieved by reading and executing the program code stored in the storage medium.

In this case, the program code itself read from the storage medium realizes the functions of the above-described embodiment, and the storage medium storing the program code constitutes the present invention.

As a storage medium for supplying the program code, for example, a floppy disk, a hard disk, an optical disk, a magneto-optical disk, a CD-ROM, a CD
-R, a magnetic tape, a nonvolatile memory card, a ROM, or the like can be used.

Further, by executing the program code read by the computer, not only the functions of the above-described embodiments are realized, but also the OS (operating system) running on the computer based on the instructions of the program code. It is needless to say that this also includes a case where the above) performs a part or all of the actual processing and the processing realizes the functions of the above-described embodiments.

Further, after the program code read from the storage medium is written in the memory provided in the function expansion board inserted in the computer or the function expansion unit connected to the computer, based on the instruction of the program code, It goes without saying that a case where the CPU provided in the function expansion board or the function expansion unit performs a part or all of the actual processing and the processing realizes the functions of the above-described embodiments is also included.

[0054]

As described above, according to the present invention,
It is possible to perform encoding according to the correlation of binary image data and further improve the compression rate.

[0055]

[Brief description of drawings]

FIG. 1 is a diagram for explaining a simple principle of the PackBits method.

FIG. 2 is a diagram showing correspondence between tag values and respective modes.

FIG. 3 is a diagram for explaining a pair of two pixels and thinning processing.

FIG. 4 is a diagram for explaining correlation and bit interleaving processing every 8 pixels.

FIG. 5 is a flowchart showing an encoding process according to the first embodiment.

FIG. 6 is a flowchart showing details of step S101 shown in FIG.

FIG. 7 is a flowchart showing details of step S103 shown in FIG.

FIG. 8 is a flowchart showing a decoding process according to the first embodiment.

FIG. 9 is a flowchart showing an encoding process according to the second embodiment.

FIG. 10 is a diagram showing a correspondence between a tag value and each mode according to the third embodiment.

FIG. 11 is a diagram showing a correspondence between tag values and each mode according to the fourth embodiment.

FIG. 12 is a diagram showing correspondence between tag values and repeat modes according to the fourth embodiment.

Claims (14)

[Claims] 1. A detecting means for detecting a correlation between binary image data, a judging means for judging an encoding according to a detection result of the detecting means, and an encoding for performing the encoding judged by the judging means. An image coding apparatus comprising: 2. The detection means is configured such that the pixel data of the encoded line and the preceding line are the same, all the pixel data of the encoded line are the same, or the pixel data of the encoded line is a pair of two pixels. 2. The image code according to claim 1, wherein it is detected whether or not the pixel data of the coding line has a strong correlation at every 8 pixels, and the judging means judges the coding according to the detection result. Device. 3. The encoding means encodes into a predetermined code when it is detected that the pixel data of the encoding line and the previous line are the same or all the pixel data of the encoding line are the same. The image coding apparatus according to claim 1, wherein: 4. The image coding apparatus according to claim 1, further comprising means for switching from byte-unit coding to bit-unit coding in accordance with the number of tags resulting from the coding. 5. The image coding apparatus according to claim 1, wherein the 1-byte code of the tag of the coding means corresponds to the run length in the repeat mode. 6. The image coding apparatus according to claim 1, wherein the run length data corresponding to the tag value is changed according to the preceding mode. 7. A determination means for determining a coded code based on a correlation of binary image data, and a decoding means for performing decoding according to a determination result of the determination means are provided. Image decoding device. 8. A detection step of detecting a correlation between binary image data, a determination step of determining encoding according to a detection result in the detection step, and an encoding step of performing the encoding determined in the determination step. An image coding method comprising the steps of: 9. The detecting step is performed by matching pixel data between a coded line and a preceding line, all pixel data of a coded line are the same, or pixel data of a coded line is a pair of two pixels. 9. The image code according to claim 8, wherein it is detected whether or not the pixel data of the encoding line has a strong correlation at every 8 pixels, and the determination unit determines the encoding according to the detection result. Method. 10. The encoding step encodes into a predetermined code when it is detected that the pixel data of the encoding line and the previous line match or all pixel data of the encoding line are the same. The image coding method according to claim 8, wherein: 11. The image coding method according to claim 8, further comprising a step of switching coding in byte unit to coding in bit unit according to the number of tags of a coding result. 12. The image encoding method according to claim 8, wherein the 1-byte code of the tag in the encoding step corresponds to the run length in the repeat mode. 13. The image coding method according to claim 8, wherein the run length data corresponding to the tag value is changed according to the preceding mode. 14. A determination step of determining a coded code based on a correlation of binary image data, and a decoding step of performing decoding according to a determination result in the determination step. Image decoding method.