JPH07101919B2 - Dither image encoding device - Google Patents

Description

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a dither image coding apparatus for coding a pseudo-halftone image binarized by a dither method (hereinafter referred to as a dither image). .

2. Description of the Related Art As a conventional dither image coding device, for example, by applying the dither image coding device shown in FIG. 7, as shown in FIG.
Run length coding is performed in areas where the number of coded bits is less than the corresponding number of pixels (long run areas), and in areas where the number of coded bits is less than the corresponding number of pixels (short run areas), identification codes are sandwiched directly without run length coding. It has been implemented by means such as transmitting a pixel row as uncompressed image data.

This will be described in detail with reference to FIG. 7. First, the input dither image signal 1 includes a delay shift register 2 and
It is input to each change point detection unit 3 that detects a change point in a line to be encoded.

When the change point is detected in the detecting unit 3, the counter 4 for counting the run length is stopped, and the run length code generating unit 5 generates the run length code corresponding to the count value input from the counter 4. The generated code is temporarily stored in the run length code generation unit 5.

When the encoding of the predetermined length is completed, the run-length accumulating unit 6 notifies the completion to the run-length code generating unit 5 and the identification code addition unit 7. The run-length code generation unit 5 that has received the notification outputs the stored code number to the comparator 8.

The comparator 8 compares the code number (coded bit number) with the corresponding pixel number and outputs a selection signal to the selector 9. The selector 9 receiving the signal selects the run length code from the run length code generation unit 5 when the number of codes is smaller, and from the identification code addition unit 7 when the number of corresponding pixels is smaller. The identification code is selected, and this is output as encoded data (output encoded signal) 10.

In this way, the dither image is encoded.

However, according to such means, when the target image is a random and dither image with many fine pixel arrays (patterns), it is possible to avoid the situation where the total number of codes exceeds the total number of pixels. However, in the case of a dither image in which a pattern appears periodically or the appearance frequency of the pattern is deviated, it is not possible to fully utilize the characteristics of the dither image. There was a problem that efficiency could not be obtained.

Therefore, it is an object of the present invention to provide a dither image coding apparatus capable of obtaining high coding efficiency even in such a case.

Means for Solving the Problems In order to solve the above-mentioned problems, the present invention uses a dither method.
Input means for inputting a binarized pseudo-halftone image, and detection for each block of M × N pixels of the pseudo-halftone image input by this input means, and any of 2 ^{(M × N)} types of image patterns A recognition means for recognizing whether or not, and for each of the 2 ^{(M × N)} types of image patterns, the pattern array is used as a pattern plane for 2 ^{(M × N).
× N)} Type Creating and storing means for storing, connecting means for connecting the pattern planes created by this creating and storing means in the main scanning direction according to the frequency of the image pattern, and lines of the pattern planes connected by this connecting means The number of divisions is divided by N, and the replacement means is arranged so that the same remainder line can be divided according to the remainder, and the coding means for two-dimensionally coding the images replaced by this replacement means. Be prepared.

Operation The present invention has the above-described configuration, detects a pseudo-halftone image binarized by the input dither method for each M × N block, and recognizes any of 2 ^{(M × N)} types of image patterns. Then, for each 2 ^{(M × N)} types of image patterns, the pattern array is stored as a pattern plane and 2 ^{(M × N)} types are created and stored, and the pattern planes are connected in the main scanning direction according to the frequency of the image pattern, The number of lines on the connected pattern planes is divided by N, the lines are replaced so that the same line can be divided according to the remainder, and two-dimensional encoding is performed on the replaced image.

Embodiment FIG. 1 is a schematic block diagram showing an embodiment of a dither coding apparatus suitable for implementing the present invention, and FIG. 2 is a dither image coded by the coding apparatus shown in FIG. It is a schematic block diagram which shows one Example of a decoding apparatus. In this embodiment, as the dither image divided into MXN areas (blocks), 1 × 4 pixels (4 bits) arranged in series in the main scanning direction are used as a unit block as shown in FIG. Dither image is used.

FIG. 4 is a conceptual diagram showing an outline of the procedure for carrying out the method of the present invention. First, the dither image 12 dithered by the N × N dither matrix 11 is divided into, for example, 16 pattern planes 13 from the pattern plane 0 to the pattern plane F.

Next, the 16 pattern planes O to F are rearranged in the main scanning direction in descending order of the frequency of appearance of each pattern on each plane (O to F) (see “Table” below),
A connected image (connected pattern plane) 14 of the pattern plane is generated. FIG. 5 shows an overall image of the connection pattern plane 14.

This table shows each pattern (4-bit parallel pattern) OF of 16 pattern planes OF obtained by a certain image (here, a dither image having 1 × 4 pixels as a unit block shown in FIG. 3). (See FIG. 6, the shaded area in each 4-bit parallel pattern 16 in FIG. 6 represents a black pixel.) The frequency of occurrence (%) is shown. The connection pattern plane 14 is generated.

Next, line replacement processing is periodically performed on the connection pattern plane 14 so that the two-dimensional correlation in the sub-scanning direction within the plane becomes strong.

The size of the dither matrix is N × N as described above.
Then, the threshold value for binarizing the original image is the same for every N lines in the sub-scanning direction, so the binarized image (dither image) has a strong two-dimensional correlation for every N lines. It will be.

Lines are numbered from O, and the line obtained by dividing the line by N and the remainder being O is arranged in order is referred to as {O} line. A bit plane (a connection pattern plane after line replacement) 15 is a line in which {O} lines to {N-1} lines are arranged in order, and this bit plane 15 is two-dimensionally encoded (redundancy degree). Suppression coded).

Therefore, referring to FIG. 1, reference numeral 17 is a 4-bit serial input dither image signal, 18 is a 4-bit serial input dither image signal, and 18 is a 4-bit serial input dither image signal 17 which is 4-bit parallel. A serial / parallel conversion unit for converting into a dither image signal, 19 is a parallel data signal for one block converted into 4 bits in parallel, and 20 is a pattern of one block, which is a pattern O to a pattern F. A pattern detection unit for detection, 21 is a 16-bit parallel output signal of the pattern detection unit 20, and 22 is a memory unit (pattern memory unit) for 16 pattern planes, which has 16 pattern memories OF. are doing. 23 is an output signal of the memory unit 22, 24 is a selector for selecting the output of the memory unit 22, and 25 is a selector output signal, and one of the pattern memories OF is output. 26 is a modified read encoder, which is one of the two-dimensional encoders, 27 is encoded output data (encoded data signal), and 28 is pattern memories OF.
A memory control unit for controlling the sub-scanning direction, 29 is an address counter in the sub-scanning direction, 30 is a control signal of the address counter 29, and 31 is an output of the address counter 29 for identifying a line in the sub-scanning direction. 32 is a control signal to the pattern memories 0 to F, 33 is an address counter in the main scanning direction, 34 is a control signal from the address counter 33, and 35 is an output signal from the address counter 33 to identify the pixel position in the main scanning direction. 36 is a pattern memory OF
Is a control signal for selecting the output signal 23, 37 is a control signal for instructing the start and end of encoding, and 38 is a control timing signal for the memory control unit 28.

Further, in FIG. 2, 39 is an input encoded data signal, and 40 is
Is the modified read decoder, 41 is the decoded data,
Reference numeral 42 is a memory unit (pattern memory unit) for 16 pattern planes, which has 16 pattern memories OF. 43
Is an output signal of the pattern memory unit 42, 44 is a pattern reproducing unit for reproducing a block of a dither image from the output signal 43 of the pattern memory unit 42, 45 is a 4-bit parallel signal of the pattern reproducing unit 44, and 46 is a 4-bit parallel signal 45. Is a parallel / serial conversion unit for converting a serial signal into a serial signal, and 47 is a restored serial signal (decoded dither image signal). 48 is a control signal for instructing the start of encoding, 49 is a read of the pattern memories O to F,
A memory control unit for controlling writing, 50 is an address counter in the main scanning direction, 51 is a control signal of the address counter 50,
A main scanning address counter output 52 identifies a pixel position in the main scanning direction. 53 is an address counter in the sub-scanning direction,
Reference numeral 54 is a control signal for the address counter 53, and 55 is a sub-scanning address counter output, which identifies a line in the sub-scanning direction. 56
Is a control signal to the pattern memories OF.

Next, the operation of the method of the present invention will be described with reference to FIGS. 1 and 2.

First, on the encoding side (see FIG. 1), the input dither image signal
The serial / parallel conversion unit 18 converts 17 into a 4-bit parallel unit block, which is input to the pattern detection unit 20. The pattern detection section 20 detects whether the 4-bit unit block is one of the patterns shown in FIG. 6, and at the same time outputs the control timing signal 38 to the memory control section 28.

The output signal 21 of the pattern detection unit 20 is a 16-bit parallel signal. For example, if the pattern detection result is the pattern O, the output signal 21 is (1,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0) are output in parallel. Here, "1" is pattern 0
Is detected.

The main scanning address counter 33 and the sub-scanning address counter 29 are activated by the control signals 34 and 30 by the control timing signal 38 from the pattern detection unit 20 to the memory control unit 28, and the pattern detection unit output signal 21 is set to which address (main scanning). Whether to write in the sub-scan) is controlled / determined by the main scanning address counter output 35 and the sub-scanning address counter output 31, and the output signal 21 of the pattern detection unit 20 is output to the determined address by the memory control signal 32. Written.

The above operation is repeated until the final unit block of the first line of the input dither image signal 17. As a result, the pattern memories O to F have the first patterns of the respective pattern planes.
The line is written.

By repeating the above operation until the final line of the input dither image signal 17, pattern plane 2 ^(MXN) sheets (16 sheets in this embodiment ^{) of the} binary image are generated.

By the above processing, the continuity of the pattern is changed to the continuity of pixels in the pattern plane, and when a certain pattern appears continuously, black pixels (signal “1”) are continuous on the corresponding pattern plane. In this way, when the processing for one page is completed and 16 pattern planes are generated, the memory control unit 28 outputs the control signal 36 to the selector 24.

The selector 24 selects one of the pattern memories of the pattern memory unit 22 to be two-dimensionally encoded by the control signal 36. In other words, when the patterns 0 to F are arranged in the descending order of the frequency of appearance from the above table, it becomes as follows.

A, F, 5,0,1,7, D, 4,8, B, E, 2, C, 3,9,6 (1) The memory control unit 28 is the selector 24 in the order of (1) above. The pattern memories 22 are used to select the pattern memories to be two-dimensionally encoded one by one.

The signal of the selected pattern memory to be encoded is modified by the selector 24 as the selector output signal 25.
It is output to the read encoder 26.

The modified read encoder 26 two-dimensionally encodes the selector output signal 25 and outputs this as an encoded data signal.
Output as 27. The start / stop of the encoder 26 is controlled by the control signal 37.

Here, the processing operation of the encoder 26 will be described more specifically.

First, when a synchronization signal indicating the beginning of a line is input, then the 0th line of each pattern plane is encoded in the order shown in (1) above. That is, since the pattern having the highest appearance frequency than that in (1) is "A", the memory control unit 28 selects the pattern memory A via the selector 24, and the 0th line is sent to the encoder 26. . When the data of the 0th line of the pattern memory A has been sent to the encoder 26, the memory control unit 28 next selects the pattern memory F and sends the data to the encoder 26. In this way, the 0th line of each pattern plane is connected and encoded in the order shown in (1) above.

After the coding of the 0th line, the 4th line of each pattern plane is connected in the order of (1) above with reference to the 0th line, and this is coded. Similarly, the eighth line is then encoded with reference to the fourth line.

Assuming that the lines in the pattern plane are line numbered (encoded) from the 0th line to the mth line (m is the last line) in sequence, this process can be expressed as follows.

That is, a line in which the remainder obtained by dividing the line number by N is 0 is defined as one group and defined as a {0} line. Similarly, this definition processing is performed from the {1} line to the {N-1} line. For example, if N is 4, the {0} line includes the 0th line, the 4th line of each pattern plane,
Lines whose line numbers are 4 × n (n is 0, 1, 2 ...) Such as the 8th line are arranged in order. Similarly, {1}
Within the line, the line number is 4 × n + 1 (n = 0,1,2 ...)
The lines represented by will be arranged in order, and
The same applies to the {2}, {3}, ... {N-1} lines.

The above line replacement process is realized by controlling the sub-scanning address counter 29 by the memory control unit 28.

In addition, the encoding in the encoder 26 first encodes all the lines classified as the {0} lines in the order of the pattern plane shown in (1) above, and when this is completed, the same applies to the {1} lines. Encoding is performed, and the {3} line is sequentially encoded. This completes the encoding of one page.

Next, on the decoding side (see FIG. 2), the input coded data signal 39 is decoded by the modified read decoder 40. The timing of memory control is transmitted to the memory controller 49 by the control signal 48.

Since the input coded data signal 39 is sent with lines connected in the order of the pattern plane shown in (1) above, the decoded data 41 is written in each pattern memory of the pattern memory unit 42 in this order. This control is performed by the memory controller
Control signal 56 from 49 is used.

Data in the connection pattern plane is {0} line, {1}
Lines, {2} lines, and {3} lines are sent in this order, so the address (main scanning, sub-scanning) to which the decoded data 41 is written is output from the main-scanning address counter 50 and the sub-scanning address counter 53. Controlled and determined by signals 52 and 55.

When all the lines from the {0} line to the {3} line are decoded, all the pattern planes are restored in the pattern memory unit 42.

When this process ends, the pattern reproducing section 44 generates 4-bit parallel patterns 0 to F shown in FIG. For example, if the input signal 43 of the pattern reproducing unit 44 is (1,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0), the output signal 45 of the pattern reproducing unit 44 becomes a 4-bit parallel (0,0,0,0) signal. When this is converted into serial data by the parallel / serial converter 46, the same signal as the input dither image signal 17 of FIG. 1 is obtained as the decoded dither image signal 47.

EFFECTS OF THE INVENTION As is apparent from the above description, the present invention detects a binary halftone image binarized by the dither method for each block of M × N, and selects any of 2 ^{(M × N)} types of image patterns. 2 ^{(M × N)} types of image patterns are created for each 2 ^{(M × N)} type image pattern as a pattern plane, and the pattern planes are connected in the main scanning direction according to the frequency of the image pattern. Then
Divide by N the number of lines on the connected pattern planes,
Since the remaining lines are interchanged so that they can be divided according to the remainder and the two-dimensional encoding is performed on the interchanged images, when a certain pattern appears continuously, black pixels appear on the corresponding pattern plane. Subsequently, since the lines are switched every cycle N of the dither image, the two-dimensional correlation becomes strong also in the sub-scanning direction and the consistency with the two-dimensional encoding is enhanced, and the high compression rate is obtained for any dither image. Can be efficiently realized.

[Brief description of drawings]

FIG. 1 is a schematic block diagram showing an embodiment of a dither image coding apparatus for carrying out the present invention, and FIG. 2 is an embodiment of a dither image decoding apparatus corresponding to the apparatus of FIG. FIG. 3 is a schematic block diagram showing the configuration, FIG. 3 is a pixel arrangement diagram showing an example of the size of a pixel block (region) of a dither image used in the embodiment of the present invention, and FIG. 4 is a concept showing an outline of the implementation procedure of the present invention. 5 and 5 are conceptual diagrams showing an overall image of a concatenated pattern plane, FIG. 6 is a conceptual diagram for explaining patterns used in the embodiments of the present invention, and FIG. 7 is a schematic block diagram of a conventional dither image encoding device. FIG. 8 is a pixel layout diagram for explaining a conventional device. 11 …… NXN size dither matrix, 12 …… Dither image, 13 …… Pattern plane, 14 …… Concatenation pattern plane, 15 …… Concatenation pattern plane (bit plane) after line replacement, 16 …… 4 bits Parallel pattern, 17 ... Input dither image signal, 18 ... Serial / parallel converter, 20 ...
... Pattern detection section, 22 ... Pattern memory section, 24 ... Selector, 26 ... Modified read encoder, 28 ...
... Memory controller, 29 ... Sub-scanning address counter, 33 ...
... Main scanning address counter, 39 ... Encoded data signal,
40 …… Modified read decoder, 42 …… Pattern memory block, 44 …… Pattern playback block, 46 …… Parallel /
Serial conversion unit, 47 ... Decoded dither image signal, 49 ... Memory control unit, 50 ... Main scanning address counter, 53 ... Sub scanning address counter.

Claims (1)

[Claims] 1. Input means for inputting a pseudo-halftone image binarized by the dither method, and a pseudo-halftone image input by this input means is detected for each block of M × N pixels,
2 recognition means for recognizing one of ^{(M × N)} kinds of image patterns, created to 2 ^{(M × N)} kinds of 2 ^{(M × N)} kinds create stores the pattern arrangement in the image pattern each as a pattern plan The storage means, a connecting means for connecting the pattern planes created by the creating and storing means in the main scanning direction according to the frequency of the image pattern, and the number of lines of the pattern planes connected by the connecting means are divided by N. A dither image coding apparatus comprising a replacement unit that replaces the remaining lines so that the same remaining line can be divided according to the remainder, and a coding unit that performs two-dimensional encoding on the image replaced by the replacement unit.