Method of processing medium tone picture

Of a plurality of threshold matrices, one is selected at random for each predetermined number of picture elements of a medium tone picture which is the same as the number of threshold components of the matrix, or at a random time interval. The density levels of the respective picture elements are compared with the corresponding threshold components which constitute the selected matrix, whereby the density level of each output picture element is determined to be black level or white level. The density level of each picture element of a medium tone picture is compared with a threshold value which is a random number generated by a random number generator, thereby determining the density level of an output picture element to be black level or white level. The difference or error in density level between a selected picture element or picture element in question to be compared with a random number and its output picture element is calculated. The resultant error is distributed and added to the density levels of other picture elements which neighbor the picture element in question and are to be processed subsequently, in accordance with specific distribution coefficients. This compensates the density level of each neighboring picture element and thereby avoids excessive dispersion of high frequency components in output pictures, which is critical to high quality picture reproduction.

BACKGROUND OF THE INVENTION 
The present invention relates to a method of processing pictures of medium 
or half tone to reproduce them in black and white picture elements. 
A typical method for the reproduction of medium tone pictures in black and 
white picture elements is the dither method. In this method, the density 
level S(i,j) of each picture element (i,j) constituting a medium tone 
picture is compared with a corresponding threshold component T.sub.D (k,l) 
of a threshold matrix (dither matrix) T.sub.D which has M.times.N 
threshold components. If the density level S(i,j) is larger than or equal 
to the threshold component T.sub.D (k,l), the picture element will have a 
logical "1" or black density level when reproduced; if not, a logical "0" 
or white density level. 
Conversion of the picture element (k,j) and threshold component (k,l) is 
generally carried out according to equations: 
EQU k=Mod(i,M) Eq. (1) 
(if k=0, k=M) 
EQU l=Mod(j,N) Eq. (2) 
(if l=0, l=N) 
where Mod(x,y) is a function indicating a residual of division of x by y. 
The dither method provides output pictures of a significant quality if 
input pictures are ture medium tone images. However, the repetitive use of 
the same threshold component at a predetermined period produces moire 
fringes should input pictures be dot pictures or dither pictures. 
An implement heretofore known to eliminate such moire fringes consists in 
generating a random number for each picture element to designate a 
specific threshold component of a threshold matrix. Though succeeding in 
the elimination of moire fringes, such an implement has a drawback that, 
since a threshold component is designated by generating a random number 
for each picture element, the distance between picture elements where the 
same threshold component is designated is irregular resulting in 
noticeable noise in output images. Another drawback inherent in this known 
implement is that the generation of a random number for each picture 
element requires a high speed random number generator, which increases the 
cost of the entire apparatus. Stated another way, the total processing 
rate is dependent on the operation rate of the random number generator. 
SUMMARY OF THE INVENTION 
A method of processing a medium tone picture constituted by a plurality of 
elements embodying the present invention comprises the steps of (a) 
scanning the medium tone picture and detecting the density levels of the 
picture elements, (b) providing a plurality of threshold matrices, each 
matrix having a predetermined number of threshold components, (c) dividing 
the picture elements into a plurality of groups, each group having the 
same number of picture elements as the threshold components of each 
matrix, (d) selecting one of the matrices at random and comparing the 
threshold components of the selected matrix with the corresponding picture 
elements of one of the groups of picture elements respectively, and (e) 
determining the density level of each of the picture element to be a black 
density level when the density level of the picture element is higher than 
that of the corresponding threshold component and to be a white density 
level when the density level of the picture element is lower than that of 
the corresponding threshold component. 
Another method of processing a medium tone picture constituted by a 
plurality of picture elements embodying the present invention comprises 
the steps of (a) scanning the medium tone picture and detecting the 
density levels of the picture elements, (b) providing a plurality of 
random numbers and selecting one of the random numbers at random, (c) 
selecting a given picture element, (d) comparing the density level of the 
given picture element with the selected one of the random numbers, (e) 
determining the density level of the given picture element to be a black 
density level when the density level of the given picture element is 
higher than that of the selected one of the random numbers and to be a 
white density level when the density level of the given picture element is 
lower than that of the selected one of the random numbers, (f) picking out 
a predetermined plurality of picture elements adjacent to the given 
picture elements, (g) calculating a difference between the density level 
of the given picture element after the density level of the given picture 
element is compared with the selected one of the random numbers and the 
density level of the given picture element before the density level of the 
given picture element is compared with the selected one of the random 
numbers, (h) providing the same number of coefficients as the adjacent 
picture elements picked out, (i) multiplying the difference by the 
respective coefficients to provide a corresponding number of errors, (j) 
additionally selecting one of the random numbers at random, (k) adding 
each of the errors to the density level of the corresponding adjacent 
picture element (l) comparing the sum of each of the errors and the 
density of each of the adjacent picture elements with the additionally 
selected one of the random numbers, and (m) determining the density level 
of each of the adjacent picture elements to be a black density level when 
the sum is greater than the additionally selected one of the random 
numbers and to be white density level when the sum is smaller than the 
additionally selected one of the random numbers. 
In accordance with an aspect of the present invention, of a plurality of 
threshold matrices, one is selected at random for each predetermined 
number of picture elements of a medium tone picture which is the same as 
the number of threshold components of the matrix, or at random time 
interval. The density levels of the respective picture elements are 
compared with the corresponding threshold components which constitute the 
selected matrix, whereby the density level of each output picture element 
is determined to be black level or white level. 
In accordance with another aspect of the present invention, the density 
level of each picture element of a medium tone picture is compared with a 
threshold value which is a random number generated by a random number 
generator, thereby determining the density level of an output picture 
element to be black level or white level. The difference or error in 
density level between a selected picture element or picture element in 
question to be compared with a random number and its output picture 
element is calculated. The resultant error is distributed and added to the 
density levels of other picture elements which neighbor the picture 
element in question and are to be processed subsequently, in accordance 
with specific distribution coefficients. This compensates the density 
level of each neighboring picture element and thereby avoids excessive 
dispersion of high frequency components in output pictures, which is 
critical to high quality picture reproduction. 
It is an object of the present invention to provide a medium tone picture 
processing method which can reproduce quality pictures free from moire 
fringes or noise using a random number generator whose operation rate is 
not so high as that required for the prior art method. 
It is another object of the present invention to provide a generally 
improved method of processing medium tone pictures. 
Other objects, together with the foregoing, are attained in the embodiments 
described in the following description and illustrated in the accompanying 
drawings.

DESCRIPTION OF THE PREFERRED EMBODIMENTS 
While the medium tone picture processing method of the present invention is 
susceptible of numerous physical embodiments, depending upon the 
environment and requirements of use, substantial numbers of the herein 
shown and described embodiments have been made, tested and used, and all 
have performed in an eminently satisfactory manner. 
Reference will now be made to FIGS. 1-3 for describing a first embodiment 
of the present invention. 
Suppose that seventeen density levels, i.e. density levels 0-16, are 
employed for processing medium tone pictures. Then, four different 
threshold matrices T.sub.p (P=1-4) each having 4.times.4 (=M.times.N) 
threshold components are prepared as shown below. It will be seen that the 
pattern of threshold components in each matrix is different from the 
pattern of threshold components in each other matrix. 
##EQU1## 
While a better result is achievable as the number of threshold matrices 
increases, four matrices will suffice in practice. 
Where such threshold matrices T.sub.P are used to process a medium tone 
picture having the density level distribution shown in FIG. 1 by way of 
example, the picture elements are divided into groups each consisting of 
4.times.4 picture elements. Of the four threshold matrices, one is 
selected at random for each picture element group. For such random 
selection of a threshold matrix, an arrangement may be made such that, 
every time the picture element group to be processed shifts from one to 
another, a random number P (=1-4) is generated to pick up specific one 
T.sub.P of the four threshold matrices T.sub.1 -T.sub.4 stored in a table 
which corresponds to the random number P. 
For each picture element of a medium tone picture, its output picture 
element has a density level which is determined by applying a selected 
threshold matrix to a picture element group to which the picture element 
belongs, in a manner similar to the conventional dither method. The 
density level S(i,j) of a picture element (i,j) of a medium tone picture 
is compared with a corresponding threshold component T.sub.P (k,l) of a 
threshold matrix T.sub.P which has been selected for a group to which the 
picture element (i,j) concerned belongs. If the density level S(i,j) is 
larger than or equal to the threshold component T.sub.P (k,l), the density 
level O(i,j) of an output picture element will be logical "1" or black; if 
not, logical "0" or white. Conversion of the picture element (i,j) and 
threshold component (k,l) are carried out according to Equations (1) and 
(2). 
An output picture provided by processing the picture of FIG. 1 is 
illustrated in FIG. 2. This indicates an exemplary case wherein the 
threshold matrix T.sub.1 is applied to a group having picture elements (0, 
0)-(3, 3), the threshold matrix T.sub.3 to a group having picture elements 
(4, 0)-(7, 3), and the threshold matrix T.sub.2 to a group having picture 
elements (0, 4)-(3, 7). 
Referring to FIG. 3, an apparatus applicable for practicing the method of 
FIGS. 1 and 2 includes an analog-to-digital converter 12 to which an 
analog density signal is coupled from a scanner 10. The analog-to-digital 
converter 12 processes the analog density signal with respect to seventeen 
values (density levels 0-16) for each picture element in synchronism with 
clock pulses coupled thereto from a clock pulse generator 14. The output 
signal of the analog-to-digital converter 12 is supplied to a comparator 
circuit 16. A counter 18 triggers a random number generator 20 to generate 
a random number every time the medium tone picture is scanned through its 
four picture elements horizontally and vertically. A table 22 stores 
therein four threshold matrices T.sub.P (P=1-4). In response to the random 
number P, a threshold matrix T.sub.P on the designated co-ordinates is 
read from the table 22 and registered in a buffer memory 24. 
The comparator 16 is supplied with the picture element density signal from 
the comparator 16 and a corresponding threshold component of the matrix 
T.sub.P from the buffer memory 24. The comparator 16 compares the two 
inputs in the previously described manner and its output is delivered as a 
density signal of an output picture element. 
It will be seen that the method of the invention described hereinabove 
selects a plurality of threshold matrices one at a time in a random 
fashion and thereby eliminates moire fringes, which would result from 
periodical use of the same threshold value. Additionally, since the method 
is not of the type which designates a threshold component of a threshold 
matrix at random for each picture element, not only the noise is made 
insignificant but the random number generator needs only a moderate 
operation rate or speed. 
A second embodiment of the present invention is illustrated in FIGS. 4 and 
5. In FIG. 4, suppose that a picture element X is a picture element which 
is to be compared with a random number. The density level G(X) of the 
picture element X in question is compared with a random number Rn. If the 
density level G(X) is larger than or equal to the random number Rn, the 
output picture element will have a density level O(X) which is logical "1" 
or black; if not, a density level O(X) which is logical "0" or white. It 
should be noted, however, that the relationship between the logical "1" 
and "0" levels may be inverted. 
The density level O(X) of the output picture element is subtracted from the 
density level G(X) of the picture element in question to provide a 
difference (error) E(X), i.e. E(X)=G(X)-O(X). When O(X) is "1", E(X) is 
G(X)-1 and, when O(X) is "0", E(X) is equal to G(X). 
The error E(X) is multiplied by specific distribution coefficients W.sub.1, 
W.sub.2, W.sub.3 and W.sub.4 for a plurality of picture elements A, B, C 
and D which neighbor the picture element X in question and will undergo 
the process subsequently. The resultant distribution errors W.sub.1 E(X), 
W.sub.2 E(X), W.sub.3 E(X) and W.sub.4 E(X) are added to the density 
levels G(A), G(B), G(C) and G(D) of the picture elements A, B, C and D, 
respectively. Thus, the picture elements A, B, C and D after the addition 
of the error E(X) to their density levels will have density levels G'(A), 
G'(B), G'(C) and G'(D): 
EQU G'(A)=G(A)+W.sub.1 E(X) 
EQU G'(B)=G(B)+W.sub.2 E(X) 
EQU G'(C)=G(C)+W.sub.3 E(X) 
EQU G'(D)=G(D)+W.sub.4 E(X) 
It will be noted that picture elements on a horizontal scan line are 
processed horizontally in sequence. 
Experiments showed that, where the input density levels of picture elements 
of a medium tone picture are regularized to lie in the range of 0-1, an 
output picture of a high quality is achievable if the sum T of all the 
distribution coefficients W.sub.1, W.sub.2, W.sub.3 and W.sub.4 is in the 
range of 1.0&lt;T&lt;2.5. For example, the distribution coefficients W.sub.1, 
W.sub.2, W.sub.3 and W.sub.4 may be selected to be 0.6, 0.4, 0.6 and 0.4, 
respectively, so that the sum T is 2.0. Alternatively, the distribution 
coefficients W.sub.1, W.sub.2, W.sub.3 and W.sub.4 may be 0.7, 0.4, 0.7 
and 0.4, respectively, to provide a sum T which is 2.2. 
As the distribution or addition of the error E(X) is repeated, it may occur 
that the density level G' of each picture element (A-D for instance) 
overflows or underflows. For example, where the range of density levels G' 
is selected to lie in the range of 0.gtoreq.G'.gtoreq.2, the density level 
may underflow as -0.5 or overflow as 2.5. In such a case, the fraction 
outside the preselected range will be omitted so that -0.5 becomes 0 and 
2.5 becomes 2. 
The method according to the second embodiment is practicable with an 
apparatus illustrated in FIG. 5. In FIG. 5, an analog density signal of a 
medium tone picture is fed from a scanner 30 to an analog-to-digital 
converter 32 and thereby quantitized in response to clock pulses supplied 
by a clock pulse generator 34. The output of the analog-to-digital 
converter 32 is stored in a buffer memory 36. In this embodiment, the 
buffer memory 36 stores two scan lines of picture element density data. 
The density of a picture element in question (X in FIG. 4) is fed from the 
buffer memory 36 to a comparator 38. Also fed to the comparator 38 is a 
random number which is produced from a random number generator 40 in 
response to a clock pulse. The comparator 38 compares the density of the 
picture element in question with the random number (threshold value) and, 
if the former is larger than the latter, produces a logical "1" or black 
signal while producing a logical "0" or white signal if otherwise. The 
level of this output signal of the comparator 38 is the density level O(X) 
of an output picture element corresponding to the picture element X. 
A subtractor 42 subtracts the density level O(X) of the output picture 
element from the density level G(X) of the picture element in question and 
supplies the resultant error E(X) to a multiplier 44. The multiplier 44 
calculates distribution errors W.sub.i E(X) for the respective picture 
elements (A-D in FIG. 4) which neighbor the picture element X. An adder 46 
adds a distribution error W.sub.i E(X) supplied from the multiplier 44 to 
the densities G(A)-G(D) of the corresponding picture elements stored in 
the buffer memory 36. Based on these sums G'(A)-G'(D), corresponding data 
in the buffer memory 36 are renewed. 
It will be noted that the number and positions of picture elements to which 
the error is distributed are not limited to those described hereinabove. 
Also, the apparatus shown in FIG. 5 is not limitative but only 
illustrative. 
It will be seen from the above that the second embodiment of the present 
invention can reproduce quality pictures free from moire fringes even from 
medium tone pictures having periodic patterns such as dot images. 
Various modifications will become possible for those skilled in the art 
after receiving the teachings of the present disclosure without departing 
from the scope thereof.