Photographic image reproduction device using digital halftoning to screen images allowing adjustable coarseness

Abstract

In the generation of screened halftones of photographic images for low resolution marking devices, conventional screen techniques are too coarse, and adaptive dither techniques are too fine. The present invention preserves the advantages of the adaptive dither techniques, while creating screen patterns with an adjustable degree of coarseness. The invention applies a hysteresis constant and recursion techniques previously limited to adaptive screening with fixed dot patterns to vary the size of dots in the screened image, thereby allowing adjustment of the image coarseness by adjusting the hysteresis constant.

What is claimed is:  
     
       1. An image reproducing system, comprising: 
       a) a scanning means for reading input image data corresponding to the image to be reproduced;  
       b) a screening device comprising:  
       memory means for storing the input image data as gray scale values for sequences of pluralities of input points, and for storing a plurality of binary output signals which direct a marking device to mark and not mark indicia on a medium;  
       means for generating signals allocating the marking and not marking of the indicia on the medium based on a value of a current input point in a sequence of input points, a previous output signal corresponding to a previous input point in the sequence and an error representing a difference between the previous input point and the corresponding output signals scaled relative to a maximum gray scale, the error influencing output signals for subsequent input points in the sequence; and  
       c) a marking device to receive the output signals from the screening device, whereby the marking device marks variable size dots comprising indicia corresponding to said output signals;  
       
         each of said variable size dots being formed of a plurality of adjacent output indicia, the size of each plurality of adjacent output indicia being determined from a recursive relationship between said current input point in a sequence of input points, said previous output signal corresponding to a previous input point in the sequence and said error representing a difference between the previous input points and the corresponding output signals, and wherein said means for generating signals allocating the marking and not marking of the indicia on said medium comprises;  
       
       
         means for accumulating a prior error corresponding to the difference between at least one said previous output signal and said previous input signal to form an accumulated prior error;  
       
       
         means for storing at least one previous output signal adjacent to the current output signal to form a previous stored output signal;  
       
       
         means for multiplying said previous stored output signal by a hysteresis constant to form a hysteresis value;  
       
       
         means for comparing the algebraic sum of said accumulated prior error said current input point and said hysteresis value to a predetermined threshold value;  
       
       
         means for generating a signal for marking a present indicia on said output medium if said algebraic sum corresponding to said accumulated prior error and said hysteresis value is greater than said predetermined threshold value wherein the hysteresis value is of a polarity to cause the present output signal to tend to be the same value as said adjacent previous stored output signal; and  
       
         means for generating a signal for not marking a present indicia on said output medium if said algebraic sum corresponding to said accumulated prior error and said hysteresis value is less than said predetermined threshold value wherein hysteresis value is of the polarity to cause the present output signal to tend to be the same value as said adjacent output signal .  
     
     
       2. The apparatus recited in  claim 1  wherein the scanning device scans a plurality of lines corresponding to the image and the sequence corresponds to a plurality of points on at least one line. 
     
     
       3. A method for reproducing a photographic image comprising the steps of scanning 
       scanning a plurality of input points of an original image for reading input image data corresponding to the input pixels of the image to be reproduced;  
       for a present input pixel, adding an error value previously generated for a first pixel adjacent in a first scanning direction to the present input pixel with an error value generated for a second pixel adjacent to the present input pixel in a second scanning direction orthogonal to the first scanning direction and creating a first result;  
       dividing said first result by two and creating a second result;  
       adding an input data to said second result creating a third result;  
       adding an output value previously generated for the first pixel with an output value previously generated for the second pixel to create a fourth result;  
       multiplying said fourth result by a hysteresis constant to create a fifth result;  
       adding said fifth result to said third result to create a sixth result;  
       storing a seventh result of 1 if said sixth result is not less than zero and if said sixth result is less than zero storing a seventh result of 0;  
       multiplying said seventh result by a constant creating an eighth result;  
       subtracting said eighth result from said third result to create a present error value and  
       marking indicia on an output medium in accordance with said seventh result.  
     
     
       4. A photographic image reproducing system comprising: 
       a scanning device receiving an input array i(x,y) corresponding to an original image to be reproduced, wherein x and y represent scanning directions;  
       a marking device receiving output signals o(x,y) from a screening device for marking indicia on an output medium in accordance with said output signals o(x,y);  
       the screening device using said input array i(x,y) in a recurrence relation calculation means for calculating a recurrence relation given by the following equations:  
       
         
           e′(x,y)=(d(x−e,y)+e(x,y−1))/ 2+i(x,y);   (a)  
         
       
       
         
           o(x,y)=1 if (e′(x,y)+h·  (b)  
         
       
        (o(x−d,y)+d(x,y−1))>=o); =0 otherwise 
       
         
           e(x,y)=e′(x,y)−fs·o(x,y); and  (c)  
         
       
       
         
           d=−1 y =1−2·(y mod 2).  (d)  
         
       
       wherein  
       fs is a maximum allowable value of members of said array i(x,y), and  
       h is a hysteresis constant, E (X, Y) defines an error function, and E′(X, Y) defines a secondary error function.  
     
     
       5. A photographic image reproducing system as recited in  claim 4  wherein: 
       e(x,−1)=0;  
       e(−1, y)=0;  
       e(width,y)=0;  
       o(x,−1)=0;  
       o(−1,y)=0; and  
       o(width,y)=0.  
     
     
       6. A method of producing a halftone image comprising the steps of: 
       scanning a plurality of input points of an original image and generating a numerical value representing a shade of gray for each input point scanned;  
       outputting a screened image having a plurality of dots, each dot of said plurality of dots being one of black or white, the size of each plurality of dots being determined from a recursive relationship between a value of a current input point, a previous output, and an error representing a difference between a value of a previous input point and the previous output; and  
       transmitting signals representing the screened image to a marking device for marking on an output medium;  
         wherein the recursive relationship employs hysteresis .  
     
     
       7. The method recited in  claim 6  wherein the recursive relationship employs a hysteresis constant, the hysteresis constant determining the coarseness of the screened image. 
     
     
       8. The method recited in  claim 7  wherein the hysteresis constant defines an allowable excursion of the error around zero. 
     
     
       9. The method recited in  claim 6  wherein the scanning is performed in two dimensions. 
     
     
       10. The method recited in  claim 6  wherein the error is allocated in two dimension. 
     
     
       11. The method recited in  claim 10  wherein the error is allocated equally in each of the two dimensions. 
     
     
       12. The method recited in  claim 6  wherein recursive relationship is defined as:                  e   ′          (     x   ,   y     )       =         (       e        (       x   -   d     ,   y     )       +     e        (     x   ,     y   -   1       )         )     /   2     +     i        (     x   ,   y     )                       o        (     x   ,   y     )       =     1                 if                   (         e        (       x   -   d     ,   y     )       +     h   *     (       o        (       x   -   d     ,   y     )       +     o        (     x   ,     y   -   1       )         )         >=   0     )                   =     0                 otherwise                     e        (     x   ,   y     )       =         e   ′          (     x   ,   y     )       -     fs   *     o        (     x   ,   y     )                   d   =       -     1   y       =     1   -     2   *     (     y                 mod                 2     )                           
       where 
       x refers to pixels in a scan line,  
       y refers to the scan lines,  
       i(x, y) and o(x, y) are the input and output arrays, respectively,  
       fs is the full scale input value, typically 255 in the case of an eight bit array,  
       and h is an hysteresis constant typically of value 0.5 times the value of fs and where larger values of h result in a coarser screen, E (X, Y) defines an error function, E′ (X,Y) defines a secondary error function.  
     
     
       13. The method in  claim 12  wherein fs is a value representing a maximum gray shade and h is a product of fs and a number not less than zero. 
     
     
       14. The method recited in  claim 6  wherein the black dots and white dots are produced by marking and not marking the medium, respectively. 
     
     
       15. An apparatus for producing a halftone image comprising: 
       means for scanning a plurality of input points of an original image and generating a numerical value representing a shade of gray for each input point scanned;  
       means for outputting a screened image having a plurality of dots, each dot of said plurality of dots being one of black or white, the size of each plurality of dots being determined from a recursive relationship between a value of a current input point, a previous output, and an error representing a difference between a value of a previous input point and the previous output; and  
       means for transmitting signals representing the screened image to a marking device for marking on an output medium;  
         wherein the recursive relationship employs hysteresis .  
     
     
       16. The apparatus recited in  claim 15  wherein the recursive relationship employs a hysteresis constant, the hysteresis constant determining the coarseness of the screened image. 
     
     
       17. The apparatus recited in  claim 16  wherein the hysteresis constant defines an allowable excursion of the error around zero. 
     
     
       18. The apparatus recited in  claim 15  wherein the scanning is performed in two dimensions. 
     
     
       19. The apparatus recited in  claim 15  wherein the error is performed in two dimensions. 
     
     
       20. The apparatus recited in  claim 19  wherein the error is allocated equally in each of the two dimensions. 
     
     
       21. The apparatus recited in  claim 15  wherein the recursive relationship is defined as:                  e   ′          (     x   ,   y     )       =         (       e        (       x   -   d     ,   y     )       +     e        (     x   ,     y   -   1       )         )     /   2     +     i        (     x   ,   y     )                       o        (     x   ,   y     )       =     1                 if                   (         e        (       x   -   d     ,   y     )       +     h   *     (       o        (       x   -   d     ,   y     )       +     o        (     x   ,     y   -   1       )         )         >=   0     )                   =     0                 otherwise                     e        (     x   ,   y     )       =         e   ′          (     x   ,   y     )       -     fs   *     o        (     x   ,   y     )                   d   =       -     1   y       =     1   -     2   *     (     y                 mod                 2     )                           
       where 
       x refers to pixels in a scan line,  
       y refers to the scan lines,  
       i(x, y) and o(x, y) are the input and output arrays, respectively,  
       fs is the full scale input value, typically 255 in the case of an eight bit array,  
       and h is a hysteresis constant typically of value 0.5 times the value of fs and where larger values of h, result in a coarser screen, E (X,Y) defines an error function, E″(X,Y) defines a secondary error function.  
     
     
       22. The apparatus recited in  claim 21  wherein fs is a value representing a maximum gray shade and h is a product of fs and a number not less than zero. 
     
     
       23. The apparatus cited in  claim 15  wherein the black and white dots correspond to marking and not marking the output medium, respectively. 
     
     
       24. An apparatus for reproducing a photographic image comprising: 
       means for scanning a plurality of input points of an original image for reading input image data corresponding to the input pixels of the image to be reproduced;  
       means for isolating a present input pixel and adding an error value previously generated for a first pixel adjacent in a first scanning direction to the present input pixel with an error value generated for a second pixel adjacent to the present input pixel in a second scanning direction orthogonal to the first scanning direction and creating a first result;  
       means for dividing said first result by two and creating a second result;  
       means for adding an input data to said second result creating a third result;  
       means for adding an output value previously generated for the first pixel with an output value previously generated for the second pixel to create a fourth result;  
       means for multipliying said fourth result by a hysteresis constant to create a fifth result;  
       means for adding said fifth result to said third result to create a sixth result;  
       means for storing a seventh result of 1 if said sixth result is not less than zero and if said sixth result is less than zero storing a seventh result of 0;  
       means for multpliying said seventh result by a constant creating an eighth result;  
       means for subtracting said eighth result from said third result to create a present error value and means for marking indicia on an output medium in accordance with said seventh result.  
     
     
       25. An image reproducing system for generating on an input medium an image corresponding to an original image, the system comprising: 
       a) a scanning means for reading input data of the original image to be reproduced, the scanning means generating signals representing gray scale values corresponding to each pixel of the original;  
       b) a screening device comprising: memory means for storing the image data corresponding to each pixel and a plurality of output signals which direct a marking device to mark one of black or white indicia on the output medium for each output signal, each output signal corresponding to a pixel on the output medium;  
       means for generating signals allocating the black or white indicia on the output medium based on the gray scale value of a current gray scale scale signal, a previous output signal and an error signal representing a difference between the current gray scale signals and at least one previously generated output signal;  
       c) a marking device to receive the output signals from the screening device, the marking device thereby generating variable size dots comprising indicia corresponding to the output signals.  
     
     
       26. The apparatus recited in  claim 25  wherein the black and white indicia correspond to marking and not marking of the output medium respectively.