JPH04431B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a color image encoding device for encoding an image including color halftone photographs having different screen angles and halftone dot pitches.

In general, color printing in magazines, newspapers, etc.
Multicolor plate making is used to print overlapping halftone images in four colors: cyan, magenta, yellow, and black. In this multicolor plate making, in order to prevent the occurrence of "moiré" (an unstable pattern that changes in various ways) due to the overlapping of halftone dot images of each color, the screen angle of the halftone dot image of each color (halftone lattice and The angle between the image and the horizontal direction is different.

Figure 1 shows an example of screen angles for preventing moiré, with cyan at 15 degrees, magenta at 75 degrees, yellow at 30 degrees, and black at 45 degrees.

In actual multicolor plate making, the combination of screen angles is not limited to this one, but also combinations of cyan 75°, magenta 45°, yellow 0°, black 15°, and cyan 15°, magenta 45°, yellow 0°, black. There is also a 75° combination. Furthermore, the halftone dot pitch (distance between the centers of halftone dots) also changes depending on the required image quality, and there are many types, ranging from about 60 to 300 halftone dots per inch. be.

In addition to such halftone photographs, color printed images also include characters and line drawings.

A device for adaptively switching between a predictor for halftone photographs and a predictor for characters, as disclosed in Patent Application No. 53-115357, as a conventional encoding device for pages containing halftone photographs such as newspapers. exists, but it is intended for those where the screen angle of the halftone photograph is constant.

For this reason, when a conventional encoding device is used for an image including a halftone photograph composed of various screen angles and halftone dot pitches, a drawback arises in that the data compression efficiency is low.

SUMMARY OF THE INVENTION An object of the present invention is to provide a color image encoding device that eliminates the drawbacks of the conventional encoding devices described above.

The color image encoding apparatus of the present invention is an apparatus for encoding an image including color halftone photographs having different screen angles and halftone dot pitches, where M and N are positive integers, and at least M types of screens of the color halftone photographs are encoded. Mx consisting of angle and N types of halftone dot pitches
a prediction means capable of setting a reference pixel arrangement according to each of the N types of combinations; a means for dividing a prediction error signal and a prediction state signal obtained from the prediction means into blocks; and prediction of the divided prediction error signal. means for comparing the number of out-of-place pixels by changing the arrangement of the reference pixels, and selecting any one set of a prediction error signal and a prediction state signal; and encoding means for encoding the selected prediction error signal.

The color image encoding device of the present invention uses a prediction means that can set a reference pixel arrangement according to each combination of a plurality of screen angles and halftone dot pitches as a prediction means, and uses a 1/m (m is a positive integer) scanning line By comparing the number of mispredicted pixels of the prediction error signal by changing the reference pixel arrangement, selecting one of the prediction methods, and efficiently encoding the prediction error signal, it is possible to This has the effect of greatly reducing the amount of information of an image containing a halftone photograph composed of halftone dot pitches.

The present invention will be described below with reference to drawings showing embodiments.

FIG. 2 is a block diagram showing one embodiment of the present invention. For ease of explanation, there are two types of screen angles (angle 1 and angle 2) and two types of dot pitches (angle 1 and 2) for halftone photographs. , Pitch 2), a total of 4 types of combinations (Angle 1 - Pitch 1) (Angle 1
- Encoding using a total of 5 types of predictors: a predictor adapted to pitch 2) (angle 2 - pitch 1) (angle 2 - pitch 2) and one type of predictor adapted to characters The device is shown.

In FIG. 2, an image signal 1 (for example, one scanning line) containing halftone photographs, characters, etc. is outputted by a timing generation circuit 9 to a clock 2 and a phase signal 3.
According to the control signal generated based on
The predictors shown in Figure A and for photographs use reference pixels that combine two types of screen angles and two types of dot pitches shown in Figures B to E, and have register, read, only memory, and This can be easily realized by combining the prediction error signal and the prediction state signal by adding a read-only memory for outputting the prediction state signal to the predictor shown in patent application No. 53-20457. converted.

The prediction error signal is passed through AND gates 10 to 14 to counters 15 to 19 and shift register 2.
0, and the predicted state signal is input to the shift register 21. The prediction error signals input to counters 15 to 19 are input to AND gates 10 to 1.
At step 4, the clock signal supplied from the timing generation circuit 9 is ANDed, so that only the portions where the prediction is incorrect are counted. In the comparator 23, the length of one scanning line divided into m equal parts is defined as one block, and the values of the counters 15 to 19 are compared in units of one block, and a control signal for selecting the one with the smallest value is output. This is because text and photographs are mixed in one scanning line of newspapers, etc., so the size of the paper is divided into n equal parts, for example, 1024 pixels.
This is because a higher compression ratio can be obtained by comparing and selecting the number of predicted errors in small units such as 2.5 cm. The shift registers 20 and 21 are one-block delay lines, and the prediction error signals and prediction state signals inputted from the predictors 4 to 8 are delayed by one block under the control of the timing generation circuit 9 and sent to the multiplexer 24. and 25. The multiplexers 24 and 25 select one set of the prediction error signal and the prediction state signal from among the prediction error signal and the prediction state signal delayed by the shift registers 20 and 21 in accordance with the control signal of the comparator 23, and the encoder 26 selects one set of the prediction error signal and the prediction state signal. given to. The encoder 26 performs encoding using a control signal for selecting a predictor, a prediction error signal, and a prediction state signal, and outputs a code 27. The encoder 26 used here is an encoder as shown in FIG. 5, which divides the prediction error signal into several groups according to the prediction state signal and encodes them.

FIGS. 3A to 3E are diagrams showing examples of reference pixels used in the predictors 4 to 8 of FIG. 2. Figure 3A
is an example of a reference pixel arrangement suitable for character prediction, in which 12 pixels a to l located near the pixel of interest (the target pixel for which prediction is currently being performed) are used as reference pixels. Figures 3B and C are examples of reference pixel placements that are suitable for predicting halftone photographs with a screen angle of 15°, and Figures 3D and E are examples of reference pixel placements that are contrary to the prediction of halftone photographs with a screen angle of 30°. This is an example. B
The reference pixel arrangement of ~E is made up of a total of 12 pixels: three pixels a to c near the pixel of interest x, and nine pixels d to l located a halftone pitch P away from the pixel of interest x depending on the screen angle. There is. B and D are arranged to match the dot pitch of _P1 , and C and E are arranged to match the dot pitch of _P2 .

In the embodiment shown in FIG. 1, for ease of explanation,
We have described the case where four types of predictors consisting of two types of screen angle and two types of dot pitch are used for halftone photographs, but the actual screen angles are 15°, 30°, 45°, and 60°. , 75°, 90°, 6 types,
Approximately 5 to 10 different dot pitches are required. Fourth
The figure shows examples of reference pixel arrangements suitable for predicting four types of halftone photographs with screen angles of 45°, 60°, 75°, and 90°.

Note that a plurality of character predictors can be provided by changing the reference pixel arrangement.

Next, a method of generating the prediction state signal s and the prediction error signal y from the reference pixels will be described. The relationship between the reference pixel pattern and the predicted signal z is determined by statistically examining in advance the frequency at which the target pixel signal becomes 1 for each of ²ⁿ reference pixel patterns formed by combinations of n reference pixels. That is, for each of the 2 ⁿ reference pixel patterns, the reference pixel is set so that when the frequency of the target pixel signal being 1 exceeds 0.5, the predicted signal z becomes 1, and when the frequency does not exceed 0.5, the predicted signal z becomes 0. Prediction signal z for the pattern
Create a logical table of occurrences.

The prediction error signal y is the pixel of interest signal x and the prediction signal z
It can be obtained from the following formula by taking the exclusive OR with

y=xz...(1) The relationship between the reference pixel pattern and the predicted state signal s is the conditional prediction error entropy calculated by the following equation.
The prediction discrepancy probability that almost minimizes Hm is statistically investigated and determined in advance.

Hm=H(G)Q(G)+H(B)Q(B) ……(2) H(G)=−P _E (G)logP _E (G)−{1−P _E (G)}log {1−P _E (G)} H(B)=−P _E (B)logP _E (B)−{1−P _E (B)}log {1−P _E (B)} Q(G) 〓 ⁱ ∈ ^G =Q(i), Q(B)= 〓 ⁱ ∈ ^B Q(i) P _E (G)= 〓 ⁱ ∈ ^G P _E (i)Q(i)／Q(G) P _E (B )= 〓 ⁱ ∈ ^B P _E (i)Q(i)/Q(B) Q(i): State probability, P _E (i): Conditional error signal probability of state i (prediction mismatch probability) In other words, n Find the probability that the predicted signal and the target pixel signal do not match for each of ²ⁿ reference pixel patterns created by combinations of reference pixels, and (2)
By creating a logical table in which the prediction state signal for the reference pixel pattern whose threshold value is equal to or greater than l is set to 0, and the opposite is set to 1, based on the prediction mismatch probability l that minimizes the conditional prediction error entropy of the formula. A predicted state signal s is generated.

FIG. 5 is a diagram showing an example of the encoder 26 of FIG. 2. This encoder has a predicted state signal of 1 bit,
That is, the prediction error signal is divided into two groups and encoded. That is, as shown in FIG. 2, the prediction error signal input to this encoder is divided into two groups depending on the value of the prediction state signal.In other words, when the prediction state signal is 0, the prediction error signal input to this encoder is divided into two groups. When the number is 1, the prediction error signals are rearranged so that they are arranged in order from the end of the division to be divided into two groups, and each group is encoded with different code assignments. first,
The input prediction error signal 31 is written to the memory 35, and the rearranged prediction error signal from the memory 36 is sent to the run-length encoder 44 (which predictor is used to input the synchronization signal part of a commonly used run-length encoder). The following describes the operation when the data is read into a system (with a function of adding a mode code indicating whether the number of generated prediction error signals is the smallest).
At this time, the multiplexer 38 selects the writing counters 39 and 40, and the multiplexer 37 selects the reading counter 41.
The multiplexer 43 selects the memory 36. counter 39,
40 and 41 are load signals generated by the timing control circuit 42 from the clock 33 and the block synchronization signal 34 (generated in units of 1024 clocks for 1 block of 1024 pixels) at the beginning of the block, and set addresses 0, 1023, and 0, respectively. .
When the input prediction state signal 32 is at a low level, the counter 39 counts up, and the multiplexer 38 selects the counter 39 to increase the prediction error signal 31 from address 0 of the memory 35 to a high level. Write in order. When the prediction state signal 32 is at a high level, the counter 40 counts down, and the multiplexer 38 selects the counter 40 to lower the prediction error signal 31 from address 1023 of the memory 35. Write in order. Through these operations, the prediction error signal 31 changes to 2 depending on the level of the prediction state signal 32.
The data is divided into two groups and written into the memory 35. At this time, the multiplexer 37 has selected the reading counter 41 and the memory 3
The contents of 6 are sequentially read out from address 0 to address 1023 according to the read clock of run-length encoder 44, and sent to run-length encoder 44 via multiplexer 43. This read operation is performed continuously, and the memories 35 and 36 alternately perform read and write operations to continuously send rearranged prediction error signals to the run-length encoder 44 in blocks. The operation of run-length encoder 44 is performed in three stages.
That is, the control signal 46 sent from the first timing control circuit 42 is encoded and added to the synchronization part as a mode code indicating which prediction error signal produced by which predictor has been selected. Second, the prediction error signals stored from address 0 to address k in the memory 36 are encoded in the first run length. The prediction error signals stored at addresses (k+1) to 1023 in the third memory 36 are encoded in a second run length. The above-mentioned value of k takes different fixed values for the text portion and the photograph portion. In other words,
Since the probability that the predicted state signal will be at a high level is different for photographs and characters, the value of k is determined separately for the character part and the photograph part, and the encoding efficiency is increased by performing run-length encoding. It is. here,
The first and second run-length encodings use different code assignments for run lengths. That is, at addresses 0 to k of the memory 26, the first
There is a high possibility that the prediction error signal in the prediction state (S = 0) is written (the value of k is obtained by averaging various papers, and when viewed in units of one block, it is not necessarily the prediction error signal in the prediction state (S = 0). The prediction error signal for the state (S=0) is not necessarily written at addresses 0 to k, and the boundary between the predicted states S=0 and S=1 may be larger or smaller than k, but the average Target 0~
The prediction error signal for the prediction state S=0 is written at address k) (k+1) to address 1023 are the second
It is highly likely that a prediction error signal in the prediction state (S=1) is written. Since the run length distributions for S=1 and S=0 are different, codes are assigned that are suitable for each.

FIG. 6 is a diagram for explaining the operation of the encoder shown in FIG. 5, and shows a case where the number of pixels in one block is 15. FIG. 6A shows the selected prediction error signal, in which the shaded areas represent incorrect predictions and the other areas represent successful predictions. Figure 6B shows the selected predicted state signal, and the shaded area is the second predicted state (S=1).
, and the others represent the first predicted state (S=0). FIG. 6C shows a prediction error signal obtained by rearranging the selected prediction error signal A according to the selected prediction state signal B. The selected prediction error signal A is divided into two states depending on the state of the prediction state signal B. In other words, as shown in the rearranged prediction error signal C in FIG. 6, when the prediction state S=0 of the prediction state signal B, the signals are arranged from the beginning of the block, and when the prediction state S=1, the signals are arranged from the end of the block. can be rearranged. Next, the prediction error signal C
is divided into two by the value of k and encoded using separate run-length codes. Here, if k=10, the first run-length code is assigned to y ₁ to y ₁₃ of the prediction error signal C, and the second run-length code is assigned to y ₁₅ to y ₃ . In an actual encoder, the period up to the prediction error is encoded as one run, so y ₁ to y ₁₂ are encoded as a run with a run length of 9, y ₁₃ to y ₁₀ are encoded as a run with a run length of 4, y ₇ and y ₃ is counted as a run with run length 1, and runs with run lengths 9 and 4 have the first run length code as run length 1.
A second run-length code is assigned to each of the two run-lengths.

In the explanation of the above embodiment, the value of k, which is the boundary for dividing the rearranged prediction error signal into two and using different run-length codes, is fixed for the text portion and the photo portion, but The value of k is made to match the boundary between the first prediction state (S = 0) and the second prediction state (S = 1), and the prediction error signal in the first prediction state uses the first run-length code, The prediction error signal, which is the second prediction state, can also be encoded using a second run-length code. However, in this case, decoding cannot be performed unless the value of k is added to the code.

Furthermore, in the embodiment described above, a separate predictor is provided for each combination of screen angle and halftone dot pitch, and a prediction error signal and a prediction state signal are generated simultaneously, but it is possible to make the reference pixel arrangement variable. It is also possible to generate prediction error signals and prediction state signals corresponding to all the predictors by using one or more predictors that can be used, changing the reference pixel arrangement in turn, and shifting the time.

Generally, the dot pitch is the same for the four types of dot images: cyan, magenta, yellow, and black. Using this, when encoding any one halftone image, prediction is performed by changing the reference pixel arrangement corresponding to all combinations of screen angles and halftone dot pitches, and prediction is performed for the other three halftone images. It is also possible to make predictions by matching the pitch of the reference pixel arrangement to the halftone dot pitch of the previously encoded halftone image and changing only the screen angle.

As described above, the apparatus of the present invention uses, as a prediction means, a prediction means that can set a reference pixel arrangement according to each combination of a plurality of screen angles and halftone dot pitches, and uses this prediction means to change the reference pixel arrangement. By selecting one of the plural prediction error signals and prediction state signal pairs by comparing the number of prediction errors of the prediction error signal and performing encoding using them, various screen angles and halftone dots can be generated. It performs efficient encoding of an image containing a halftone photograph composed of pitches and text.

[Brief explanation of drawings]

Fig. 1 is a diagram showing an example of screen angles for four types of color halftone photographs, Fig. 2 is a block diagram showing the configuration of an embodiment of the present invention, and Fig. 3 is one type used in the embodiment of Fig. 2. Figure 4 is a diagram showing an example of the reference pixel arrangement for characters and the reference pixel arrangement for four types of halftone photographs.
FIG. 5 is a block diagram showing the configuration of an encoder that is part of an embodiment of the present invention; FIG. FIG. 6 is a diagram for explaining the operation of the encoder. Each number in the figure indicates the following. 1... Image signal, 2... Clock, 3... Phase signal, 4-8... Predictor, 9... Timing generation circuit, 10-14... AND gate, 15-1
9... Counter, 20, 21... Shift register, 23... Comparator, 24, 25... Multiplexer, 26... Encoder, 27... Code, 31...
Prediction error signal, 32...Prediction state signal, 33...
Clock, 34...Block synchronization signal, 35, 3
6...Memory, 37, 38...Multiplexer,
39, 40, 41... Counter, 42... Timing control circuit, 43... Multiplexer, 44
. . . run-length encoder, 45 . . . code.

Claims (1)

[Claims] 1. In a color image encoding device that encodes an image including color halftone photographs having different screen angles and halftone dot pitches, M and N are positive integers, and at least M types of screen angles and N types of the color halftone photographs are used. a prediction means capable of setting a reference pixel arrangement according to each of M×N combinations of halftone dot pitches; means for dividing a prediction error signal and a prediction state signal obtained from the prediction means into blocks; means for comparing the number of mispredicted pixels of the divided prediction error signals by changing the arrangement of the reference pixels, and selecting any one set of prediction error signal and prediction state signal; a prediction state signal; and encoding means for encoding the selected prediction error signal based on the prediction state signal.