JPH03187573A - Pseudo half tone picture encoding system - Google Patents

Abstract

PURPOSE:To enable efficient compression and encoding by encoding a value, which calculates exclusive OR between a forecasting value to forecast an attention picture element as black or white and the value of the attention picture element in an inputted picture element, as forecasting error as a function to be mathematically calculated from the number of black picture elements in the two peripheral picture element areas of the attention picture element. CONSTITUTION:A scanning part 1, a pseudo half tone generating part 2, a line memories 3 and 4, D flip-flops 51-55, 61-65 and 71-75 for picture element delay, black picture element counting parts 81-84, an arithmetic calculation part 9 and a run length encoding part 10 are provided. The forecasting error signal is encoded by a compressing and encoding means such as run length encoding, etc., being the exclusive OR between the forecasting value of the attention picture element, which is determined by arithmetic calculation form the number of the black picture elements counting the number of the black picture elements in first and second peripheral areas of the attention picture element, and the value of the real attention picture element. Thus, the pseudo half tone picture can be efficiently compressed and encoded by an error diffusing system.

Description

Detailed Description of the Invention [Industrial Application Field] This invention relates to a pseudo-halftone image encoding method for use in the present invention, and particularly relates to a pseudo-halftone image encoding method for converting a halftone image into a binary image using an error diffusion method. .

[Conventional technology]

Conventionally, a number of methods have been known for pseudo-halftone image encoding, as shown below. The first method is called multilevel encoding, in which halftone images are A/D converted and nb
It is expressed as it/pixel, and this is compressed and encoded. There are various types of compression encoding methods, and broadly speaking, there are many known methods such as predictive encoding, orthogonal transform encoding, process truncation encoding, bit-brain encoding, and vector quantization encoding.

The second method is binary encoding, which first converts the halftone image into a binary image by some method, and then further converts the halftone image into a binary image.
It compresses and encodes value images.

A halftone image converted into a binary image is called a pseudo halftone image. Comparing multilevel encoding and binary encoding, for images scanned at the same linear density (sampling density), multilevel encoding naturally provides more information and better image quality. On the other hand, with binary encoding, the amount of information is already reduced to l bits/pixel at the time of conversion to a binary image, and although the image quality is inferior compared to multilevel images, the amount of encoded data is small. Therefore, the transmission time can also be shortened.

By the way, as recording devices for reproducing images on the receiving side, there are recording methods such as silver halide photography that can basically reproduce gradation, but there are also recording devices such as thermal recording methods and lasers that are normally used in facsimile machines, copying machines, etc. In recording devices such as beam printers (LBP), printing machines, and the like, the recording device has no or very low gradation reproduction ability, and basically many of them mainly reproduce binary values. Therefore, even if high-quality images are transmitted using multilevel encoding, they are converted to binary images when recording.
Recently, binary encoding has been widely used because it is often reproduced as a pseudo-halftone image.

Various pseudo-halftone methods are known for converting a halftone image into a binary image, but the most typical one is the so-called dither method. Among them, the systematic dither method that is particularly commonly used is a method in which a different threshold value is set for each pixel in a block, and each pixel is binarized using this threshold value, as shown in Figure 5 (a). be. An example of an image obtained by binarizing a uniform image with a predetermined density (7) using the dither method is shown in FIG. 5(b). As shown in this example, the halftone level W is determined by the number of black pixels in the whole
expressed similarly. Predictive encoding is known as a method for further compressing and encoding the dithered image obtained in this manner. As the simplest example of predictive coding, for example, if a pixel of interest is the same as the previous n pixels (n is the period of the threshold pattern in Fig. 5(a), n = 4 in the example of Fig. 5), There are ways to make predictions. As can be seen from the example in Figure 5(b), the pixel n pixels before is binarized with the same threshold as the pixel of interest, so if there is no density change in the original image during that time, the binarized image will be The pixel of interest has the same value as the pixel n pixels before, so in many cases the above prediction will be true,
The exclusive logic between the predicted value and the actual input pixel, 1111 (referred to as prediction error), is O. Therefore, the prediction error signal obtained in this manner has a property that there are extremely many 0's and few 1's. The entropy of such a prediction error signal is -PiOgp-(1-P) Ilog (1-P) (
It is known that the entropy can be compressed as close as possible to the entropy, for example, by run-length encoding (a method of encoding the distance from a pixel with a prediction error of 1 to a pixel with a next prediction error of 1). It is being In actual predictive coding of dithered images, slightly more complex predictions are often used, but they all use the periodicity of the dithered threshold pattern, and are basically the same as the simple example above. .

On the other hand, there is a method called an error diffusion method as a method for generating pseudo-halftone images. The algorithm of this method will be explained with reference to FIG. Here, the original image value is converted. If the result is black (1), the error between the actual pixel value and l (a value between 0 and -1) is distributed and added to the adjacent pixels after that pixel. If the result is white (0), the error between the actual pixel value and O (
(values from 0 to -) are added in a distributed manner. For the next pixel, the value corrected by the error value just added is binarized using the threshold value -, and the error is similarly dispersed and added to the adjacent pixel. FIG. 6 shows an example in which the first pixel 5 is binarized (b) and the second pixel 5 is binarized (c) for an original image (a) of a predetermined density (-). Compared to the dither method, this method has no periodicity in the dither pattern, so smooth gradation changes can be obtained in areas where the density changes, and there is less deterioration in resolution, so a better pseudo-halftone image can be obtained than the dither method.

[Problem to be solved by the invention]

In the error diffusion method of the conventional pseudo-halftone image encoding method described above, since there is no periodicity like that of a dithered image, a prediction method such as that applied to a dithered image cannot be applied, and efficient compression encoding cannot be performed. Therefore, it has the disadvantage that the amount of data is large and the communication time is long.

[Means to solve the problem]

The pseudo-halftone image encoding method of the present invention, in encoding a binary-expressed pseudo-halftone image, includes means for counting the number of black pixels in a predetermined first surrounding area of a pixel of interest; means for counting black pixels in a second peripheral area different from the peripheral area of the target pixel, the pixel of interest is counted as black or The image forming apparatus includes means for encoding, as a prediction error, a value obtained by calculating an exclusive OR of a predicted value predicted to be white and the value of the pixel of interest of the input image.

〔Example〕

Next, the present invention will be explained with reference to the drawings.

FIG. 1 is a block diagram of one embodiment of the present invention.

First, the error diffusion method of this embodiment will be explained.
Original image (halftone image) at pixel position (x, y) in the figure
The value at f (x, y) (0≦f(x, y)≦1) The value at the J pseudo-halftone image obtained by the error diffusion method is g
(x,y)(g(x.

y) = 0.1), then g(x, y) = Q(f(x, y) + B(x, y))
==(1) It can be expressed as equation (1). Here, Q(・) is an appropriate fixed value (x, y) is the adjacent preceding pixel position (x-1° y), (x-1, y-1), (x, y-1), (x+1
, y-1) is the sum of error diffusion values generated by binarization. That is, the error due to binarization of the pixel position (x, y) is e (x, y)=f (x.

y) + E (x, y) - g (x, y), then E(
x+y)=a+o・e(x-1,y)+ane(x-
1,y-1)+ao+e(x,y-1)+a-1Ie(
x+1. y-1)...(2) Formula (2). here alG+ all+ aolz
a-11 is the error diffusion coefficient in each direction; al. +
a,,+a,.

+ & −u = 1. For simplicity, equation (2) is written as E
(x.

y) = Σ a-e(i, D...2a formula (Mitsugu, y). Now, for a certain image area, the number of black pixels in that area is Σg(x,y)=Σ(f(x,y)+E(x,y)−e
(x, y)) = Σf (x, y) + ΣE (x, y)
−Σe (x, y), but ΣE (x, y)−
Σe (X+y) is territory D
In area D, E (x, y) and e (x,
y) cancel each other out, and the diffusion error from outside the area approaches 0 as the area size increases, so it can be seen that for a fairly wide area, the average density of that part is expressed by the amount of black pixels within the area. .

Next, compression encoding of this embodiment will be explained.

As described above, in the error diffusion method, the average density within an area is expressed by the amount of black pixels within that area. Therefore, two surrounding areas D of the pixel of interest (X, Y) 1. D
2 to D 1. It is determined that all pixels in D2 have been binarized, and the area is + (X, Y).

The average concentration of D, +(X, Y) is (Σg(x, y
) 10g (X, Y)) / (N (D+) + 1) i ...... (3) (Σg (x, y) + g (X, Y)) / (N (D2)
+1)...(4) However, N (Dl) and N (Dz) are the total number of pixels in the areas D1 and D2, respectively (3) and are represented by equations (4). Area DI, D! Assuming there is no large concentration change inside and at position (X, Y) (3)
.

In both equations (4), the halftone value f at the pixel position (X, Y)
Since it is considered to be close to (X, Y), g (X.

The predicted value g (X, Y) of Y) is determined so that the difference between equations (3) and (4) is as small as possible.

That is, The formula (5) is obtained.

......(5) Exclusive OR g(x,
y)0g (x, y) is used as a prediction error signal, and by performing run-length encoding on this, for example, the amount of data can be reduced.

Furthermore, in this embodiment, the area DI (X, Y)D2
The pixel area shown in FIG. 4 is used as (X, Y).

In FIG. 1, a scanning section 1 scans an original, A/D converts the image signal, and outputs a digital halftone image signal.

The J pseudo-halftone generation unit 2 converts the halftone image signal into a pseudo-halftone using an error diffusion method.

Line memories 3 and 4 delay the 1-bit/pixel image signal converted into each pseudo-halftone by one scanning line.

D flip-flop 51-55.61-65.71-7
5 is an image signal from the pseudo halftone generation unit (2), an image signal from line memory (1) 3, and a line memory (2), respectively.
The image signals from 4 are sequentially delayed by one pixel.

Black counting parts 81-83 are 54 and 55, respectively.61-65
．． The number of black pixels at pixel positions corresponding to D flip-flops 71 to 75 is counted. Black pixel counting section (3) 84 is 52
．． The number of black pixels at pixel positions corresponding to D flip-flops 62 to 64 is counted. Arithmetic operation unit 9 is 54, 62, 6
A predicted value is determined in accordance with the sum of the pixel values (black or white) corresponding to 3 and 64 and the number of black pixels from the black pixel counting section. The encoding unit 10 performs run-length encoding on a signal (that is, a prediction error signal) obtained by exclusive ORing the predicted value from the arithmetic operation unit (9) and the pixel of interest that is output from the D flip-flop (53). do. In FIG. 2, the black pixel counting section 81~
83 is shown in detail. In Figure 1, the pixel of interest (
The value of the pixel you are trying to predict is D-F/F (53)
It is output from. At this time, the area shown in Figure 8 is (X, Y
) are D-F/F54, 55, 61 to 65.
．． The outputs are 71 to 75.

The operation of this embodiment will be described below with reference to the timing chart of FIG. First, at the start of each scanning line operation, the counter 802 and all D-F/Fs are cleared to "0" by a clear signal not shown. Therefore, counter 802 is then indicating the number of black pixels in region D I (x, y) within each corresponding scan line. Now, the pixel (
m-1, n) is the pixel position of interest, that is, D-F/F (5
Consider the state at the output of 3). At this time, the value of the area Dr (m-1, n) of each scanning line corresponds to the black pixel coefficient part (81
-83) is output from the counter (802). In this state, the area of each scanning line is (m-1,
n) and is included in area D+(m.

Pixels not included in S i 2 (i=1 to 3), pixels not included in area D+ (m 1.n), and pixels not included in area D1 (
Pixels included in m, n) are output to 5i1 (i=1 to 3). At the rising edge of the shift clock (not shown in FIGS. 1 and 2), each pixel is shifted by the D-F/F. At that time, as can be seen from FIG. 2, if the values of Sil and Si2 are equal, the counter 802 is enabled. Terminal EN is “
When Sil is "1" (black) and Si2 is "0" (white), the counter value does not change and the number of black pixels (per scanning line) in area D1 does not change. 802
Since the enable terminal EN of is "H" and the DN/lower terminal is "L", the counter 802 performs an up-count operation and increases by l. On the other hand, the number of black pixels in the area D1 also increases by one. Similarly, Sil is “0” (white) and Si2 is “1”
” (black), both the value of the counter (802) and the number of black pixels in the area D1 decrease by 1. From the above, inductively, the counter (802) always calculates the value for each scanning line for the pixel of interest (X, Y). It can be seen that the number of black pixels in the area D+ is shown.The black pixel counting section 84 is realized by a ROM and
, 62, 63, and 64 are output as a 2-bit binary code to S7. The arithmetic operation unit 9 calculates the predicted value g (X, Y) of the result of the arithmetic operation of equation (5) based on the number of black pixels 84 to S6 for each scanning line in the area D1 and the value of the number of black pixels 87 in the area D2. occurs. In this embodiment, the inputs of the arithmetic operation unit 9 are 372, 842, and S
5゜S6, 3 each, total of 10, and one ROM (Re
This can be realized by writing the calculation result value in advance into the ad 0nly Memory).

〔Effect of the invention〕

As explained above, according to the present invention, the predicted value of the pixel of interest and the actual value of the pixel of interest are determined by an arithmetic operation from the number of black pixels obtained by counting the number of black pixels in the first and second surrounding areas of the pixel of interest. By encoding the prediction error signal, which is the exclusive OR of This has the effect of shortening transmission time.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing one embodiment of the present invention, FIG. 2 is a detailed block diagram of the black pixel counting section in this embodiment, and FIG.
The figure is a timing diagram for explaining the operation of this embodiment, FIG. 4 is a diagram showing a reference pixel area in this embodiment, and FIGS. 5, 6, and 7 are conventional pseudo halftone image encoding systems. It is a figure for explaining an example. 1... Scanning section, 2... 4 Pseudo halftone generation section, 3° 4... Line memory, 51 to 55.6
1-65° 71-75...D flip-flop for pixel delay, 81-84...Black pixel counting unit, 9
... Arithmetic operation section, IO ... Run length encoding section, 801 ... Exclusive OR gate,
802...Up/down counter.

Claims (1)

[Claims] In encoding a binary-expressed pseudo-halftone image, means for counting the number of black pixels in a predetermined first surrounding area of a pixel of interest;
means for counting black pixels in the peripheral area of the first
and the number of black pixels in the second peripheral pixel area, and the exclusive OR of the predicted value of the pixel of interest predicted to be black or white and the value of the pixel of interest of the input image. 1. A method for encoding a pseudo-halftone image, comprising means for encoding the determined value as a prediction error.