JPS63102559A - Image processing device - Google Patents

Abstract

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

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to an image processing apparatus, and more particularly to an image processing apparatus that performs preprocessing to improve the data compression rate of dithered image data.

[Prior Art] Conventionally, the encoding methods used in facsimile machines and the like include the modified Huffman method (MH method), which is a one-dimensional encoding method, the modified read method (MR method), which is a two-dimensional encoding method, and the modified modified method. There are read methods (MMR methods), etc. However, since these encoding methods are basically run-length encoding methods, high data compression rates cannot be obtained for dithered images in which black pixels are almost randomly distributed, and in some cases, the amount of code is larger than the original image data. will increase. In addition, various dithered image encoding methods that do not rely on the run-length method have been proposed, but because they cannot be expected to be compatible with the international standard MH method and MR method, they have not become established as encoding methods for facsimile machines, etc. was not reached.

[Problems to be Solved by the Invention] The present invention has been made against the background of the above-mentioned prior art, and its purpose is to solve the problem of code used in conventional facsimile machines such as the MH system and the MR system. An object of the present invention is to provide an image processing device that maintains compatibility with the digitizing method and that significantly improves the data compression rate of dithered image data.

Another object of the present invention is to provide an image processing apparatus that can be easily applied to existing facsimile machines and the like to realize high-quality and high-speed image transmission of dithered image data.

[Means for Solving the Problem] As a means for solving this problem, for example, the image processing apparatus of the embodiment shown in FIGS. A dither conversion section 2 that dither-converts the converted image data VD using a dither matrix of a predetermined size, and a pre-processing section that performs a first-stage encoding process for obtaining a high data compression rate according to the present invention on the converted dithered image data DD. 3, and an MH that encodes the encoded image data ID subjected to the encoding process using the run-length method.
It includes an encoder 4 and a data transmitter 5 that transmits run-length encoded image data MD.

Here, the preprocessing section 3 processes the dithered image data D
An image blocking means 61 distributes and stores data D for each scanning line and blocks it in a predetermined length in the column direction, and a histogram ( hi+1
); a code assigning means 63 that assigns a code LD to each bit pattern of the image data block DB in a predetermined manner according to the histogram (hi) obtained for the previous block row; an image encoding means 64 for encoding an image data block DDB having the same bit pattern as the bit pattern to which a code LD has already been assigned to the data block DDB, with the assigned code LD; It includes an encoding means 7 that performs interleaving processing on the mixed image data blocks DDB' and LD of the encoded image data blocks LD for each number of columns of the dither matrix size.

[Operation] In the configurations shown in FIGS. 1 and 2, the code allocating means 63 allocates codes LD having fewer "1" bits, for example, in order of the bit pattern occurrence frequency of the image data block DB. The image encoding means 64 encodes the image data block DDB in accordance with this so that its apparent black area is reduced. However, the image data block DDB' to which no code has been assigned yet passes through as is. Next, the encoding means 7 encodes the image data block D which has not yet been encoded.
Interleaving processing is performed on the mixed image data blocks DDB' and LD of DB' and the encoded image data block LD for each number of columns of the dither matrix. As a result, the apparent black pixels, which are periodically arranged in each block, are gathered in one place. Next, the MH encoder 4 performs run-length encoding on this.

[Embodiments] Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings.

FIG. 1 is a block diagram of an image processing apparatus according to an embodiment. In the figure, an image reading unit 1 reads a halftone image, such as a photograph, and performs sampling and quantization. The multi-gradation digital image data VD obtained as a result is sent to the dither converter 2 and is binarized using a dither matrix of a predetermined size (for example, 4×4). In the preprocessing section 3, the pattern converting means 6 first encodes the dithered image data DD by a method described later so as to reduce its apparent black area. Generally, in a halftone image, pixels of similar density tend to be continuous, so the apparent pixels after encoding are also arranged periodically. Therefore, the encoding means 7 utilizes this property to further perform interleaving processing for each number of columns of the dither matrix on the encoded image data. As a result, the apparent black pixels that were periodically arranged in each image block are gathered in one place, and the white and black run lengths become relatively long. MH encoder 4 encodes this run length information, and data transmitter 5 sends MH encoded data MD to line 8.

The second section is a block diagram of the pattern conversion means 6 of FIG. 1, and FIGS. 3(a) to 3(c) are graph diagrams for explaining the operation of FIG. 2. In FIG. 2, in the image blocking means 61, line buffers 621 to 624 store dithered image data DD for each scanning line, and store the dithered image data DD in a predetermined length in the column direction, for example, in one dimension by 4), which is the number of rows of the dither matrix. block. In order to realize this control, the EOL detection unit 625 detects the delimitation EOL of each line, and the counter 626 counts, for example, four delimitation EOLs.

When the counter 626 counts 4'', the histogram creation means 62 converts the image data block DB into blocks.
A histogram is created and updated for each block row for each bit pattern. The creation and updating of this histogram is performed, for example, according to equation (1).

h i +1 = C + α・hi ... (1)
However, ho=0 0<αku1 Here, h i + 1 is the value of the histogram created and updated up to the i+1th block row, and hi is the value of the histogram created and updated up to the previous nth block row. The value C is the frequency of occurrence of each bit pattern included only in the i+1th block row, and α is a weighting coefficient for past histograms.

When α=1, all past histograms are added, so the occurrence frequency information of the latest block row does not have a large effect on the entire histogram. Therefore, it is suitable for encoding images with uniform density or image blocks with few types of density patterns, such as character images. Also, when α=0, the corresponding 1
Since it is created using only the histogram of block rows, the occurrence frequency information of the latest block row determines the coding efficiency of the next block row. Therefore, it is possible to encode an image in which the density of block rows changes randomly.

In general, the density distribution of a gradation image changes gradually for each block row, so by appropriately weighting 0, α, and 1, the followability changes, and encoding can be performed according to the nature of the image. The value of α is determined manually or by a microprocessor (not shown).

FIG. 3(a) shows a histogram table Hn created and updated up to the n-th block row. A logic "0" in the bit pattern corresponds to a white pixel, and a logic "1" corresponds to a black pixel. Further, in the embodiment, the block size is set to "4°" for ease of explanation, but this value can be appropriately windowed depending on, for example, the number of rows M of the size (MXN) of the dither matrix.

According to FIG. 3(a), the bit pattern P of all white pixels
The frequency of occurrence of o is 842, and the frequency of occurrence of bit pattern P1 in which black pixels are present in the first row is 29. Below, the bit patterns of table Hn are arranged in order so that the number of black pixels increases, and finally the bit pattern P of all black pixels is
The frequency of occurrence of z is shown as 199.

FIG. 3(b) is a diagram showing the contents of the intermediate table Mn. The code assignment means 63 first uses a histogram table Hn.
Sort in descending (or ascending) order of frequency, and each bit pattern after sorting has a binary code of “0”, for example.
Assign codes in ascending order starting from (all white code blocks). Alternatively, codes having a large number of 1 bits may be assigned in descending order of the bit patterns that occur more frequently in the histogram Hn. This can conversely increase the run length of black pixels.

FIG. 3(C) is a diagram showing the contents of the encoding table hn. Next, the code assignment means 63 rearranges the bit patterns of the intermediate table Mn, for example, in ascending order. This is for the convenience of image encoding processing, which will be described later. As a result, the image encoding means 64 selects an image block D having the same bit pattern as the bit pattern to which the code is assigned among the following image blocks DDB.
DB is encoded with the assigned code LD. The block delay means 66 is provided to match the timing of image encoding with the image block DDB.

FIG. 4 is a diagram showing an example of dithered image data, and FIG. 5 (a
) to (C) are diagrams showing changes in the encoding table hn, No. 6
The figure shows an arrangement of encoded image data. In FIG. 4, the dithered image data in the first block row is in blocks 1.2. ... Histogram creation means 6 in the order of 9 columns
2 is input.

Therefore, the bit pattern generation order is po, po.

・, P5. P2. P5. PO, P5. -, and so on. In this way, since the first block row is at the stage of creating a histogram, no code (label) LD is assigned to it. That is, the state is ho=o in FIG. 5(a). Further, for the sake of simplicity of explanation, it is assumed that α=1. Therefore, since there is no corresponding code, the image encoding means 64 passes the image block DDB of the block row as it is. This is the image data DDB' of the first block row in FIG.

In this respect, the decoding means on the receiving side (not shown) works in the same way,
You can take this image data DDB' as it is and create your own histogram. Therefore, the receiving side creates and updates the same histogram as the transmitting side with a delay of one block.

Now, when the transmission of the first block row is completed, the encoding table becomes hl as shown in FIG. 5(b). Bit pattern Po, P5
．． P2 has symbols Lo, Ll, and P2 according to the frequency of occurrence, respectively.
L2 is assigned. Further, since no other bit patterns were generated, there is no corresponding code. Next, the image encoding means 64 uses the encoding table h1 of FIG. 5(b) when transmitting the image block of the second block row of FIG. 4. In this example, the bit pattern PO is encoded as the code LO, the bit pattern P5 as the code L1, and the bit pattern P2 as the code L2.

It can be seen here that the bit pattern P5 is converted to the code L1 to subtract black pixels. Similarly, when transmitting the image block of the third block row, the encoding table h3 of FIG. 5(C) is used. In this way, high encoding efficiency can be expected in areas where many bit patterns with many black pixels occur.

In this respect, the decoding means on the receiving side works similarly. That is, the encoded image block LD is converted into the original bit patterns PO, P5 . Restore to P2 etc. Also, unencoded image block DDB
Since there is no corresponding code in the decoding table for ', it is not decoded and is restored as is. These are then combined to create and update a histogram.

FIG. 7 is a diagram showing the effect of interleaving processing. 6th
The data in the first block row in the figure is converted into line data by video conversion means 65.

The code encoding means 7 further performs interleaving processing on this line by line and converts it as shown in the first line of FIG. The interleaving process of the embodiment is performed, for example, for the data bits in the first row of FIG. ...9
This is a process of picking up items in column order.

In the embodiment, the number of columns of the dither matrix size is "4", so the sea fence is every 4 bits. As a result, black pixels are gathered in one place, and the run length of both white pixels and black pixels is improved. Therefore, encoded data ID
is encoded by, for example, an existing MH encoder 4 and sent to the receiving side.

Note that although the present invention is most suitable for encoding using the MH method, it is also applicable to the MR method.

In that case, a higher compression ratio can be obtained especially by using the scanning line one block row before as the reference line.

Furthermore, the size of the image block is not limited to M rows of the dither matrix, but an integral multiple thereof can also be used.

Conversely, it is also possible to divide the number of rows M of the dither matrix into several small blocks and associate a different histogram with each small block. These allow the size of the histogram to be adjusted appropriately and speed up the processing.

[Effects of the Invention] As described above, according to the present invention, for example, by simply adding a simple pre-processing device to an existing facsimile machine, the data compression rate of dithered images can be significantly improved, reducing transmission time. This also has the effect of reducing communication costs.

[Brief explanation of the drawing]

FIG. 1 is a block configuration diagram of the image processing device of the embodiment, FIG. 2 is a block configuration diagram of the pattern conversion means 6 of FIG. 1, and FIGS. 3(a) to (C) explain the masterpieces of FIG. Figure 4 is a graph showing an example of dithered image data, Figure 5 (a
) to (c) are graphs showing changes in the contents of the encoding table, FIG. 6 is a graph showing encoded image data, and FIG. 7 is a diagram showing the effect of interleaving processing. In the figure, 1... image reading section, 2... dither conversion section, 3
... Preprocessing unit, 4... MH encoder, 5... Data transmission unit, 6... Pattern conversion means, 7... Encoding means, 8... Line, 61... Image Blocking means, 6
2... Histogram creation means, 63... Code assignment means, 64... Image encoding means, 65... Video conversion means, 66... Block delay means.

Claims (7)

[Claims] (1) Image blocking means for forming dithered image information into blocks of a predetermined length in the column direction; histogram creation means for creating a histogram for the bit patterns of the image blocks that have been formed into blocks; and a code assigning means for assigning a code to a bit pattern of the image block; and an image encoding means for encoding an image block having the same pattern as a bit pattern to which a code has already been assigned among the image blocks with the assigned code. An image processing device characterized by: (2) The image processing apparatus according to claim 1, wherein the image blocking means blocks the dithered image information with a length equal to the number of rows of a dither matrix used for the dithered image information. (3) The code allocating means allocates codes with fewer 1 bits in order from bit patterns that occur more frequently in the histogram.
The image processing device described in Section 1. (4) The image processing apparatus according to claim 1 or 2, wherein the code assigning means assigns binary codes in ascending order from the bit pattern with the highest frequency of occurrence in the histogram. (5) The image processing apparatus according to claim 1 or 2, wherein the code assignment means assigns gray codes in ascending order from bit patterns that occur frequently in the histogram. (6) The image processing apparatus according to claim 1 or 2, wherein the code allocating means allocates codes having a large number of 1 bits in descending order of bit patterns that occur frequently in the histogram. (7) image blocking means for forming dithered image information into blocks of a predetermined length in the column direction; histogram creation means for creating a histogram for the bit pattern of the blocked image block; code assigning means for assigning a code to a bit pattern of the image block; image encoding means for encoding an image block of the image block having the same pattern as a bit pattern to which a code has already been assigned, with the assigned code; An image processing apparatus comprising: an encoding means for interleaving a mixed image block of an unencoded image block and the encoded image block every number of rows of the dither matrix size.