Abstract:
A halftone screening method includes a method of moire suppression, in which the input image is first screened in a trial screening module. The input image is then subtracted from the trial screened image to produce an error image which contains both the trial screen pattern and the moire pattern introduced by the trial screening process. The error image is filtered in a lowpass filter to remove the trial screen pattern, leaving only the moire pattern, which is then subtracted from the input image to produce a compensated image. Finally, the compensated image is then screened in a final screening module. The moire image component of the compensated image tends to cancel the moire pattern introduced by the final screening module so as to suppress moire patterns in the final screened image. In two alternate embodiments, filter refinements are provided to reduce grayscale distortions and improve moire suppression in the extreme light and shadow regions of the image.

Description:
FIELD OF THE INVENTION 
     The present invention relates to the field of image processing, and more particularly, the present invention relates to the field of halftone screening of photographic images using improved methods and apparatus. 
     BACKGROUND OF THE INVENTION 
     Halftone screening is a process by which shades of gray can be represented in images formed with a bi-level marking system, such as black ink on white paper. As is the case in most printing systems, whether color or black and white, the absence or presence of the ink on the paper is used to represent the printed image. In order to represent halftones (shades between the presence or absence of the printed ink), the original image is screened to produce a pattern, made up of variable size dots, which appear to the human eye as a halftone image. Thus to prepare a photograph for printing, it is necessary to perform the process of halftone screening. which converts the continuous gray shades of the original into dots of varying size and shape. 
     Originally, photomechanical screening systems used physical photographic screens. In computer based screening systems, images are typically stored in a memory by representing tone values for each pixel of the original image. For a black and white image, the stored pixels represent the grayscale value corresponding to each pixel. For a color image, each color plane is stored as an array of pixels each representing the tone value for each pixel of the image in each respective color plane. For example, if each of the pixels of a black and white image is represented by an 8 bit digital word, then the tone value for a given image pixel is one of 256 values between the black level and the white level, with 0 corresponding to white and all ones (or 255), corresponding to black. 
     Digital screening devices and digital raster scan printing devices simulate the generation of a halftone cell to produce a screened image. The most common form of digital screening is to generate a repeating spot function corresponding to the halftone cell, and compare each pixel of the grayscale image with a corresponding pixel in the repeating spot function. The period and angle of the repeating spot function correspond to that of the resulting grid of dots, while the shape of the surface defined by a single repeating halftone cell spot function determines the shape of the resulting dots for each shade of gray. 
     There are also many screening methods that make use of a screen pattern cell, which can be a one dimensional strip. a band, or any two dimensional area, such as a square, that contains a section of the final screen spanning more than one halftone cell. The screening method will repeatedly generate the screen pattern cell, resulting in a final screen of the desired ruling and angle. The critical step in halftone screening is the generation of the screen pattern cell which will be repeated to form the final screen covering the entire input image area. Examples of prior art techniques include rational tangent (U.S. Pat. No. 4,149,194 to Holladay), rational supercell (European patent document 0 427 380 A 2 , corresponding to U.S. Pat. No. 5,235,435), irrational tangent (U.S. Pat. Nos. 4,499,489 to Gall et al, and 4,350,996 to Rosenfeld). In addition, three alternative screening techniques described in three patents by the inventor of the present invention, namely U.S. Pat. No. 5,291,310, U.S. Pat. No. 5,307,181, and U.S. Pat. No. 5,315,406, may each be used to generate a suitable screen pattern cell. 
     Digital halftone screening consists of first generating a spot function or screen pattern cell. The spot function is usually stored as a fairly small pattern that repeats itself or is repeatedly generated by programming, At any point where the original image is greater than the spot function, the output is marked. At any point where the image is not greater than the spot function, the output is not marked. In other words, if the value of the image pixel is greater than corresponding value of the spot function, a mark is generated by the marking engine, whereas if the value of the image pixel is less or equal to the spot function value, then no mark is generated by the marking engine, or vice versa. In this way, the final screened image, composed of dots, is produced. In color printing, there are four separate steps of halftone screening, one each for the cyan, magenta, yellow, and black inks. 
     Much prior art work has been devoted to producing screens which will produce good results and avoid artifacts in the final image. One such artifact to be avoided is the moire pattern. There are a number of sources of moire in the halftoning process. One source of moire is the moire between the screen girds used for the different ink planes in a color image. To counteract the tendency for moire patterns to result, color screens are angled at 0 (yellow), 15 (cyan), 75 (magenta) and 45 degrees (black). If these angles are adhered to precisely, as well as the screen ruling being precisely identical for all four planes, then optimum results (minimum moire) are achieved. Screening at these angles in photomechanical screening systems is achieved by rotating the photographic screen carriers. In digital screening devices and digital raster scan imaging devices, however, there is some difficulty in exactly reproducing irrational numbers, such as the tangent of 15 degrees or the tangent of 75 degrees. (Rational numbers can be represented as the ratio of two integers; irrational numbers are endless non-repeating decimals). Both rational tangent, and irrational tangent digital screening systems are known. 
     In general, the use of a repeating spot function, or screen pattern cell, for screening does work, and is used for the overwhelming majority of printing today. Aside from simplicity of implementation, the great strength of a repeating spot function, is its ability to render areas of constant or smoothly varying gray value. Many attempts to improve various aspects of the halftoning process (including error diffusion and so-called &#34;stochastic&#34; techniques) abandon the precise repetition of identically shaped dots, thereby introducing a grainy appearance. 
     Nonetheless, the quest for the highest quality image continues. Traditional halftoning techniques suffer from one persistent problem, that of unwanted moire patterns caused by the interference between patterns in the original grayscale image and the generated spot function, which could be called subject moire. (A different source of artifacts in digital raster scan screening systems is screener induced moire, which results from the interaction between the screen and the finite resolution of the output image forming device). Screener induced moire artifacts are more pronounced when using fine screen rulings, low output resolutions, or a combination of both. As a result, it is typical to use a 3500 dot per inch (dpi) output resolution to minimize screener induced moire artifacts and obtain a quality image. 
     SUMMARY OF THE INVENTION 
     The present invention is embodied in a method and apparatus for suppressing subject moire artifacts by compensating for predicted moire patterns. First, the moire pattern which results from screening is predicted. Then the predicted moire is combined with the original image to produce a compensated image, which compensated image is then screened. The moire pattern created by screening tends to be canceled by the predicted moire in the final halftone image. The effect is to suppress or cancel the moire patterns which are introduced by the halftone screening process. 
     To predict a moire pattern, a trial screen is made, using the unmodified halftone process. Then the original image is subtracted from the trial screen to produce an error image corresponding to the moire pattern. The error image is filtered to extract the moire signal only, The extracted moire signal is subtracted from the original grayscale image, to produce an image with a correction factor. Finally, the image with the correction factor is screened, producing the final halftone. Since the correction factor is derived from a negative image of the moire image, it tends to cancel the moire patterns introduced by the halftone screening process. 
     In addition, the present invention includes refinements which correct for undesirable grayscale distortions introduced into the compensated image, improve rendition of whites and blacks, and increase the effectiveness of the suppression of moire in regions adjacent to solid black and white regions. 
    
    
     BRIEF DESCRIPTION OF THE FIGURES 
     FIG. 1 is a block diagram of a halftone screening system for suppressing moire patterns in accordance with the present invention. 
     FIG. 2A is an illustration of a spot function used for screening a grayscale image used in conjunction with the present invention. 
     FIG. 2B is a representation of a trial image used in conjunction with the present invention. 
     FIG. 2C is a representation of an error image generated in accordance with the present invention. 
     FIG. 2D is a representation of a predicted moire image generated in accordance with the present invention. 
     FIG. 2E is an illustration of a compensated grayscale image and a modified spot function in accordance with the present invention. 
     FIG. 2F is an illustration of a final halftone image in accordance with the present invention. 
     FIG. 3 is a block diagram of an alternate embodiment of a halftone screening system for suppressing moire patterns in accordance with the present invention. 
     FIG. 4 is a graph of grayscale versus gain for function F in FIG. 3, 
     FIG. 5 is a block diagram of yet another alternate embodiment of a halftone screening system for suppressing moire patterns in accordance with the present invention. 
     FIG. 6 is a graph of grayscale versus gain for function F in FIG. 5. 
     FIG. 7 is a graph of grayscale versus gain for function F2 in FIG. 5. 
    
    
     DETAILED DESCRIPTION 
     A halftone screening system 10 in accordance with the present invention is shown in FIG. 1. The system 10 includes a first halftone screening module 22 for generating a trial halftone screened image. a first adder 28, a lowpass filter (LPF) 30. a second adder 32, and a second halftone screening module 24 for generating a final halftone screened image. The trial screening module 22 and the final screening module 24 use substantially the same screening method so that each will tend to produce substantially the same moire pattern in the respective output. for substantially the same input image. 
     The first and second adders 28, 32. perform signed addition, and as actually used in the figures, perform subtraction to compute the difference between two inputs. In particular, the first adder 28 subtracts the input image 12 from the screened image output 14 from the trial screening module 22, which is then filtered in a Iowpass filter 30. The second adder 32 subtracts the output of the lowpass filter 30 from the original image 12 to produce a compensated image 20. The compensated image 20 is screened in the final halftone screening module 24. 
     As used herein, terms are defined as follows: 
     &#34;Image pixels&#34; shall mean the grayscale values for an input grayscale image to be screened. 
     &#34;Screen pixels&#34; shall mean the individual pixels corresponding to the marking signals to the marking device, which term is also equivalent to the term &#34;output pixels&#34;. 
     &#34;Spot function&#34; shall mean a function of grayscale values corresponding to each screen pixel of an output pixel array. 
     &#34;Halftone cell&#34; shall mean the output pixel array of screen pixels corresponding to the spot function. The halftone cell also corresponds to the array in which a halftone dot is formed. The halftone dot is formed by applying the spot function to the corresponding input image pixels. 
     &#34;Screen pattern&#34; shall mean an array of halftone cells arranged on a regular grid. 
     &#34;Screen pattern cell&#34; a two dimensional area that contains a section of a screen pattern spanning more than one halftone cell. 
     A &#34;halftone&#34;. a &#34;halftone screened image&#34; or a &#34;screened image&#34; is an image formed by halftone dots of various sizes so as to give the effect of a continuous tone when viewed at normal reading distance, 
     The input 12 to the screening process is an original grayscale image, wherein each image pixel represents the tone value for each pixel of the image in each respective color plane. The output pixels 26 from the screening process are coupled to the marking device to form the resulting halftone image. 
     The first step is to produce a trial halftone screened image 14 of the original image 12. There are many methods for producing the trial halftone screened image. The present invention may be used with many such prior art screening methods. The trial halftone image 14 and be analyzed into three components: the original input image, the screen pattern (generated internally to the trial screening module 22), and unwanted moire. 
     The second step is to subtract 28 the original image 12 from the trial screened image 14. To subtract a grayscale image 12 from a bi-level screened image 14. each grayscale pixel is subtracted from each screen pixel. The difference between the input image 12 and the trial screened image 14 is an error image 16. Since the original image 12 has been subtracted from the trial screened image 14, the error image 16 contains only two components: the screen pattern and the moire pattern. 
     The third step is to lowpass filter 30 the error image 16, resulting in a moire image 18. The trial screening module 22. adder 28 and LPF 30 form a moire prediction module 13. by which the moire pattern which would result from halftone screening an input image 12 is predicted. The predicted moire image 18 is used to generate a correction factor to the original input image 12. 
     In theory, the screen pattern consists only of high spatial frequencies, and the moire only of low spatial frequencies, so all of the screen pattern is effectively filtered out by LPF 30, leaving only the moire. In practice, the lowpass filter 30 must be a bit &#34;leaky&#34;. allowing some of the screen pattern to leak through, and attenuating some of the moire signal. However, the practical considerations of leaky lowpass filters is discussed below in connection with two lowpass filter refinements. 
     The fourth step is to subtract the moire image 18 (the correction factor) from the original grayscale image 12 in adder 32, giving an output image 20 with correction factor. The final step is to halftone screen the image 20 with the correction factor, giving a final halftone 26. The theory is that the moire generated by the image 20 with correction factor in the final halftone screening module 24, will be similar or identical to the moire generated in the trial screening module 22, the latter of which is captured in the correction signal, so that the final halftone moire and the correction factor will cancel each other, producing an image with reduced moire. 
     First Refinement: 
     A Modified Spot Function to Reduce Grayscale Distortion 
     As indicated, for an ideal system in accordance with FIG. 1, the trial screening module 22 and the final screening module 24 use substantially the same screening method. In one embodiment, the trial screening module 22, and the final halftone screening module 24, use different spot functions. 
     In general, matching the grayscale exactly for the trial and final screens is possible only when the system satisfies a given constraint: that as the shade of gray presented at the input image grows darker, the grayscale value presented at the input to the final screen, measured at the locations of the edges of the dots as produced by the final halftone screen, must grow darker as well. Because the given constraint states that a signal must increase monotonically in response to increasing the input gray value, the given constraint is often termed the monotonicity constraint. The monotonicity constraint becomes easier to satisfy as the cutoff frequency of the lowpass filter becomes smaller. If the monotonicity constraint is not satisfied, the consequence is an inability to faithfully reproduce image detail in extreme highlight and shadow regions (i.e. very light and very dark grays). 
     Yet, if the cutoff frequency becomes too low, the risk is that the filter will attenuate the higher frequencies of the moire signal, rendering the suppression of moire less effective. Further, as the cutoff frequency decreases, the support of the filter grows in size, increasing the likelihood of artifacts. 
     However, the lowpass filter 30 must be leaky. Even if its spectral response were carefully optimized to completely suppress the screen frequencies, such optimization would increase the extent of the filter and possibly exhibit a &#34;ringing&#34; effect, which would be noticeable as artifacts in the final halftone image. Yet, the leakiness of the filter will produce artifacts of its own, most notably a distortion of the grayscale as reproduced by the system. 
     It is desirable to provide a spot function for the final halftone screening module 24 which is different from the spot function for the trial screening module 22, so as to correct for the distortion of the grayscale introduced into the compensated image. By way of example, for flat shades of gray in FIGS. 2A-2F. the modified spot function must be such that the final halftone 26 is as identical as possible to that produced by trial screening module, i.e., the same as produced by traditional techniques. 
     The input image 36 in FIG. 2A consists of a constant shade of gray. No moire results from halftoning a constant shade image. Even so, it is desired that the grayshade of the final halftone (FIG. 2F) resembles that of the trial halftone (FIG. 2B) as closely as possible. The grayscale distortion results from the fact that the image with a correction factor consists of a constant with an attenuated &#34;carrier wave&#34; function corresponding to the spot function. 
     The screening of a constant shade of gray is illustrated in FIGS. 2A-2F, for a one-dimensional variant of the process. 
     FIG. 2A shows the original grayscale image 36 superimposed with a spot function 34. FIG. 2B shows the resulting trial halftone 38. FIG. 2C shows the error image 40 after subtracting the original image 36 from the trial halftone 38. FIG. 2D shows the moire image 42 at the output of the lowpass filter. FIG. 2E shows the compensated image 44 which is input to the final halftone screening module. Finally, FIG. 2F shows the resulting final halftone. 
     The input to the final halftone screening module 44 contains the added carrier wave signal 42. Had the final halftone screening module used the same spot function 34 of the trial screening module, then the grayscale of the final halftone would be distorted, with smaller dots, and thus giving the final halftone an overall darker appearance than the trial halftone in FIG. 2B. which has the correct grayscale. In general, using the same spot function 34, the final halftone would result in a higher contrast than required for correct reproduction of the grayscale. 
     A solution to this problem is to use a modified spot function 41 in the final screen, rather than the same spot function 34 used in the trial screen. The idea is to use a spot function 41 designed such that, for a constant shade of gray as input image. the result of the final screen is the same as that for the trial screen. Since the nature of the grayscale distortion is to increase contrast, the use of a screen which decreases contrast would accomplish the desired effect. 
     The spot function is a function of a two-dimensional vector x representing position. A spot function signal is denoted as sf(x). Sf trial  is the spot function for the trial screening module. Sf final  is the spot function for the final screening module. Let the input image consist of a single shade of gray g, and let ic(g.x) denote the compensated image with correction factor, i.e. the input to the final halftone screening module, for input gray shade g at position x. Then, the final spot function, sf final  (X), can be derived from the trial spot function, sf trial  (x) using a simple formula: 
     
         sf.sub.final (x)=ic(sf.sub.trial (x)x) 
    
     Second Refinement 
     Reduce the Correction Factor in the Highlight and Shadow Regions 
     The monotonicity constraint is relatively easy to satisfy in the middle of the grayscale: it is particularly difficult to satisfy in the extreme highlight and shadow regions. The purpose of the second refinement is to reduce the amplitude of the correction factor in the extreme highlight and shadow regions. thus satisfying the monotonicity constraint without requiring too low a cutoff frequency for the lowpass filter. 
     A halftone screening system with the second refinement is shown in FIG. 3. This system is essentially identical to that of FIG. 1 with the addition of a function F, 76, and a multiplier 74. The output of a multiplier is the product of its inputs. The multiplier 74 scales the moire image 18 (the correction factor) to form a scaled moire image 60 before being subtracted from the original image 12 in adder 72, and screened in the final halftone screening module 64. The output pixels 66 from the screening process are coupled to the marking device to form the resulting halftone image. 
     The original grayscale image is input to function F, to produce a gain signal ranging from 0 to 1 for input to multiplier 72. The curve showing the response of function F is illustrated in FIG. 4. The gain is 0 when the input is white or black, and 1 for shades of gray ranging from very light to very dark. In between, there is a smooth transition from 0 to 1 between white and very light gray, and a smooth transition from 1 to 0 between very dark gray and black. Thus, function F reduces the correction factor 18 in the grayscale regions near black and white by multiplication in multiplier 74, but does not reduce the correction factor for shades of gray in the midrange. 
     The effect of interposing the function F and multiplier 74 is to eliminate the correction factor 18 in areas of white and black, and reduce the correction factor 18 in areas of extreme highlights and shadow. Thus, it becomes easier to satisfy the monotonicity constraint, and therefore reproduce the entire grayscale of the input image without distortion. 
     Third Refinement 
     Reduce Moire in the Highlight and Shadow Regions 
     However, reducing the amplitude of the correction signal at extreme highlights and shadow also reduces the effectiveness of the correction signal in reducing moire in those regions. In particular, for sections of the image consisting of image detail adjacent to white (without loss of generality), much of the moire correction signal is lost, particularly in images consisting of gray line art or text on a white background. 
     For example, assume that in the trial halftone the line is reproduced as lighter than its actual weight because it falls between two rows of dots. The moire correction signal would make the grayscale image of the line and its surrounding neighborhood darker, correcting the moire. However, the correction signal in the neighborhood of the line is eliminated because it is white, and function F for white regions of the image is zero. Thus, the moire correction would be less effective, leaving some amount of moire in the final halftone. 
     A halftone screening system which enhances the effectiveness of moire suppression in the extreme highlight and shadow regions is shown in FIG. 5. The system of FIG. 5 is essentially identical to the system shown in FIG. 3, with the addition of pathway consisting of a second function F2, 108. and a second lowpass filter 110, the output of which is coupled to a third input of a three input multiplier 104, The multiplier 104 scales the moire image 18 (the correction factor) to form a scaled moire image 105 before being subtracted from the original image 12 in adder 102. and screened in the final halftone screening module 94. The output pixels 96 from the screening process are coupled to the marking device to form the resulting halftone image. 
     The response of the second function F2 is shown in FIG. 6. The gain is 2 when the input is white or black, and 1 for shades of gray ranging from very light to very dark. In between, there is a smooth transition in gain from 2 to 1 between white and very light gray, and a smooth transition in gain from 1 to 2 between very dark gray and black. Thus, function F2 increases the correction factor 18 in the grayscale regions near black and white by multiplication (greater than 1) in multiplier 74, but does not change the correction factor for shades of gray in the midrange. 
     The effect of adding function F2, LPF 110 and the third input of multiplier 104 is to make the gain depend on the local neighborhood of the input image rather than a single point. For example, for a single point surrounded by a white region, the gain is greater than one. In particular. for the specific response curve of F2 shown in FIG. 6, the output is 2. 
     Thus, for the example of the gray line on a white background, the moire correction signal is amplified within the line itself, and suppressed in the neighboring white region. Ideally, the total moire correction signal within the entire neighborhood is roughly equal to what it would have been in the basic system of FIG. 1. 
     In general, the combined effect of function F 76, function F2 108, lowpass filter 110. and multiplier 104 is to increase the amplitude of the moire image 18 in image areas proximal to areas of solid black or solid white, or proximal to areas nearly solid black or solid white. 
     There are two advantages to the system shown in FIG. 5 over that shown in FIG. 1, in addition to making it easier to meet the monotonicity constraint. First, preventing the formation of dots in adjacent white and black areas makes the final halftone image appear cleaner, reproducing edges with higher acuity. Second, it avoids clipping artifacts resulting from adding the moire correction factor to the image. 
     In the gray line on a white background example above. the line as reproduced was not dark enough. Assume now that the reproduction of the line is too dark, for example because the line coincides with a row of dots. In the basic embodiment of FIG. 1, the effect of the correction factor is to lighten the surrounding neighborhood. The line, being gray can be lightened. but the surrounding white area cannot be made any lighter than white thus reducing the effectiveness of the moire reduction. In the embodiment of FIG. 5, removing the correction factor from the white areas and reallocating it entirely within the gray line avoids the problem of clipping altogether.