Abstract:
Artifact reduction is achieved by altering the growth of sub-cells for each super-cell in either a pre-determined or random manner. The means of alteration is selected such that the sum of all the groups equals a halftone value. In another embodiment, the random group is selected by using predetermined patterns which are different among sub-cells, such as different means of constructing a dot. Preferably a different pattern is used in adjacent super-cells. In yet another embodiment, the method selects sub-cells patterns that are not aligned on the super-cell boundaries.

Description:
BACKGROUND OF THE INVENTION 
   The present invention relates generally to image output devices and more specifically to reducing engine and halftoning artifacts. 
   Image output systems such as printer, copiers, facsimile machines receive an input and generate an image based on the received input. Often the input has several shades or various degrees of toning, and the image output device tries to imitate the shade or tone while using inks or other media which are much darker than the desired shade by printing on a sheet of paper that is much lighter than the desired shade. One method for obtaining the desired shade is halftoning. Halftoning is the reproduction of grayscale images using dots of a single shade, but varying their size to simulate the different sizes of grey. Laser printers that cannot print different sized dots produce halftones by varying the number of dots in a given area. Halftoning is also used to produce a black and white version of a color document using shades of gray in place of the original colors. 
   Simple halftoning methods that are well known in the art can have problems with artifacts, which are manifested as undesirable macro effects. For example, a monochrome default halftoning pattern for a 16×16 cell that has 8 sub-cells can provide the illusion of continuous tone from paper white to device black. If all of the 8 sub-cells grow the same so the code-values for all sub-cells are identical macro effect of equal dot growth can produce horizontal, vertical, slanted line artifacts or repeated pattern artifacts. Halftoning methods which use patterns, often in conjunction with code-values may still exhibit macro effects because of the continuous repetition of the same pattern. 
   Thus, a need exists for a halftoning method that eliminates line patterns or any other artifact patterns or other macro effects. 
   BRIEF SUMMARY OF THE INVENTION 
   In view of the aforementioned needs, the invention contemplates in one embodiment a method that within a super-cell, the sub-cell growth is randomized. For example, if a 50 percent halftone is desired, one sub-cell may have 50 percent of its cells grown, the next sub-cell may have 48 percent of its sub-cells grown, and the next super-cell may have 52 percent of the sub-cells grown. Thus the average value of the super-cells if 50 percent. 
   In another embodiment of the present invention, sub-cells are selected into groupings such that the groupings cross the boundaries of the super-cells. The sub-cells within each group are then grown either by using a random bias value for each grouping, or using predetermined biases for each grouping. The groupings may also vary in size. For example one grouping may contain 64 sub-cells while another grouping only has 16. By using groupings that are not aligned on super-cell boundaries, one part of a super-cell may be increasing in growth while the other part of the super-cell is decreasing in growth with a net result of increasing density. 
   As those skilled in the art can readily appreciate, the present invention may be implemented in software, hardware or a combination thereof. While the description herein is directed to black and white image or grayscale images, the present invention is equally adaptable to color printers. 
   Still other objects of the present invention will become readily apparent to those skilled in this art from the following description wherein there is shown and described a preferred embodiment of this invention, simply by way of illustration of one of the best modes best suited for to carry out the invention. As it will be realized, the invention is capable of other different embodiments and its several details are capable of modifications in various obvious aspects all without from the invention. Accordingly, the drawing and descriptions will be regarded as illustrative in nature and not as restrictive. 

   
     BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING 
     The accompanying drawings incorporated in and forming a part of the specification, illustrates several aspects of the present invention, and together with the description serve to explain the principles of the invention. In the drawings: 
       FIG. 1  is an example of a super-cell grid composed of sixteen sub-cells; 
       FIG. 2  is an example of four super-cells, each super-cell with sixteen sub-cells; 
       FIG. 3  is a graph illustrating an example of output sub-cell growth based on input; 
       FIG. 4  is an embodiment wherein sub-cells groupings are made that cross super-cell boundaries; 
       FIG. 5  is an example of a super-cell grid with random sub-cells biased in each super-cell; and 
       FIG. 6  is an example of a super-cell grid using a combination of random patterns and a random code-value for each super-cell. 
   

   DETAILED DESCRIPTION OF INVENTION 
   Throughout this description, the preferred embodiment and examples shown should be considered as exemplars, rather than limitations, of the present invention. 
   The present invention contemplates various methods of halftoning for artifact reduction. Artifact reduction may be accomplished by dispersing the growth of sub-cells so that the sub-cells do not grow in the same manner and are constrained by super-cell boundaries. One method is by growing sub-cells based on a random value for each super-cell. Another method is growing sub-cells based on random patterns, preferably in a manner such that adjacent super-cells have different patterns. Another method is to disperse the growth of sub-cells are grouped wherein the groupings are not constrained by super-cell boundaries. 
   Referring to  FIG. 3  there is shown a graph illustrating the relationship of the input to an image output device to the output. The bottom left of the graph represent minimum input and output, which would typically be the case where no ink or media is used and the output is just plain paper. The right side of the input axis is the maximum input, or typically complete black input and the maximum output is the upper end of the axis for the output. Line  302  is the case where the input is mapped perfectly to the output. However, line  304  illustrates a randomized growth pattern for the system described in this invention. As can be seen by  304 , the growth is, at some places, slower than that of line  302  and at other places, faster. Other irregular growth patterns similar to  304  can be implemented for other sub-cells. 
   Referring to  FIG. 1 , there is shown a super-cell  100  that is comprised of sixteen sub-cells,  102   a ,  102   b ,  102   c ,  102   d ,  102   e ,  102   f ,  102   g ,  102   h ,  102   i ,  102   j ,  102   k ,  102   m ,  102   n ,  102   p ,  102   q  and  102   r . While the illustrations in this application use super-cells of 16 sub-cells, as those skilled in the art can readily appreciate the super-cells may comprise any number of sub-cells, which ordinarily would be an integer multiple of 16 such as 16, 64, 128 or 256 sub-cells per super-cell. The methods described herein for the 16 sub-cell super-cell are easily adaptable to other size super-cells. 
   Halftones are produced by biasing a certain number of sub-cells of the super-cell. For example for a 50 percent halftone, eight of the sixteen sub-cells may be biased. The eight sub-cells may be the top half of the super-cell, e.g. sub-cells  102   a ,  102   e ,  102   i ,  102   n ,  102   b ,  102   f ,  102   j  and  102   p , the bottom half of the super-cell, e.g. sub-cells  102   c ,  102   g ,  102   k ,  102   q ,  102   d ,  102   h ,  102   m  and  102   r , the left-half of the super-cell, e.g.  102   a ,  102   b ,  102   c ,  102   d ,  102   e ,  102   f ,  102   g  and  102   h , the right-half of the super-cell, e.g.  102   i ,  102   j ,  102   k ,  102   m ,  102   n ,  102   p ,  102   q  and  102   r , alternate rows of the super-cell, e.g. cells  102   a ,  102   e ,  102   i ,  102   h ,  102   c ,  102   g ,  102   k  and  102   q  or alternate columns of the super-cell, e.g. cells  102   a ,  102   b ,  102   c ,  102   d ,  102   i ,  102   j ,  102   k  and  102   m . One method contemplated by use with the present invention is to use random sub-cells of the super-cell, for example for a 50% halftone sub-cells  102   a ,  102   c ,  102   f ,  102   h ,  102   k ,  102   j , and  102   n  and  102   r  could be used. Another method contemplated by the present invention is to use a pattern for the super-cell such as a square wave, thus for a 50% halftone sub-cells  102   d ,  102   c ,  102   b ,  102   a ,  102   e ,  102   i ,  102   j  and  102   k  may be biased. 
   Referring now to  FIG. 2  there is shown a grid  200  of four super-cells  200 . The first super-cell is comprised of sub-cells,  102   a ,  102   b ,  102   c ,  102   d ,  102   e ,  102   f ,  102   g ,  102   h ,  102   i ,  102   j ,  102   k ,  102   m ,  102   n ,  102   p ,  102   q  and  102   r . The second super-cell is comprised of sub-cells sub-cells,  104   a ,  104   b ,  104   c ,  104   d ,  104   e ,  104   f ,  104   g ,  104   h ,  104   i ,  104   j ,  104   k ,  104   m ,  104   n ,  104   p ,  104   q  and  104   r . The third super-cell comprises sub-cells  106   a ,  106   b ,  106   c ,  106   d ,  106   e ,  106   f ,  106   g ,  106   h ,  106   i ,  106   j ,  106   k ,  106   m ,  106   n ,  106   p ,  106   q  and  106   r . The fourth super-cell comprises sub-cells  108   a ,  108   b ,  108   c ,  108   d ,  108   e ,  108   f ,  108   g ,  108   h ,  108   i ,  108   j ,  108   k ,  108   m ,  108   n ,  108   p ,  108   q  and  108   r.    
   Referring now to  FIG. 5 , there is illustrated an example of one method of the present invention. For this example, it is desired that the halftoning is 50%. One embodiment of the present invention contemplates using random patterns to obtain the 50% halftone wherein each super-cell has 50% of its sub-cells biased. For example, in  FIG. 5 , sub-cells  102   a ,  102   c ,  102   f ,  102   h ,  102   i ,  102   k ,  102   p  and  102   r  of the first super-cell are biased. For the second super-cell, sub-cells  104   b ,  104   d ,  104   f ,  104   g ,  104   j ,  104   m ,  104   p  and  104   q  are biased. For the third super-cell, sub-cells  106   a ,  106   b ,  106   c ,  106   d ,  106   i ,  106   j ,  106   q  and  106   r  are biased. For the fourth super-cell, sub-cells  108   d ,  108   f ,  108   g ,  108   h ,  108   i ,  108   k ,  108   p  and  108   r  are biased. For this particular embodiment, each super-cell has 50% of the sub-cells biased. Preferably for each super-cell, the adjacent super-cells have different random sub-cells biased. 
   Randomization can be further enhanced by causing each sub-cell to grow in a different pattern. For example, one sub-cell can grow as a cluster dot, another can grow as an elliptical dot, etc. 
   Referring now to  FIG. 6  there is yet another embodiment of the present invention. This embodiment uses a combination of random sub-cell biasing along with a random number of sub-cells per super-cell. In this example, a 50% halftone is desired. The first super-cell has nine sub-cells biased,  102   a ,  102   b ,  102   c ,  102   d ,  1022   i ,  102   j ,  102   k ,  102   m  and  102   q . The second super-cell has seven sub-cells biased,  104   e ,  104   f ,  104   g ,  104   h ,  104   p ,  104   q ,  104   r . The third super-cell has only four sub-cells biased,  106   b ,  106   f ,  106   j  and  106   p , while the fourth super-cell has twelve sub-cells biased,  108   a ,  108   b ,  108   c ,  108   e ,  108   f ,  108   g ,  108   i ,  108   j ,  108   k ,  108   n ,  108   p  and  108   q . While none of the super-cells have a 50% halftone, the aggregate of all four super-cells is that all 50% of the sub-cells are biased. Furthermore the first and second super-cells use a vertical pattern whereas the third and fourth super-cell are using a horizontal pattern. 
   Referring now to  FIG. 4  there is illustrated another embodiment of the present invention. In this embodiment, the grid  400  comprises super-cells  402 ,  404 ,  406 ,  408 ,  410 ,  412 ,  414 ,  416 ,  418 ,  420 ,  422 ,  424 ,  426 ,  428 ,  430  and  432 . In this embodiment, the growth of pixels are not aligned on cell boundaries. For example a first grouping of sub-cells  450  has sub-cells from super-cell  402 ,  410 ,  404  and  412 . The second grouping of sub-cells  452  has sub-cells from super-cells  410 ,  418  and other super-cells off the grid  400 . The third grouping of sub-cells  454  has sub-cells from super-cells  418 ,  430  and other super-cells off the grid  400 . A fourth grouping of sub-cells  456  has sub-cells from super-cells  412 ,  414 ,  420  and  422 . It is further contemplated that the groupings  450 ,  452 ,  454  and  456  may be of varying sizes or numbers of super-cells as well as varying shapes. 
   The foregoing description of a preferred embodiment of the invention has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed. Obvious modifications or variations are possible in light of the above teachings. The embodiment was chosen and described to provide the best illustration of the principles of the invention and its practical application to thereby enable one of the ordinary skill in the art to utilize the invention in various embodiments and with various modifications as are suited to the particular use contemplated. All such modifications and variations are within the scope of the invention as determined by the appended claims when interpreted in accordance to the breadth to which they are fairly, legally and equitably entitled.