WO1992006554A1

WO1992006554A1 - Method and apparatus for performing clustered-dot dithering for laser printers

Info

Publication number: WO1992006554A1
Application number: PCT/US1991/007371
Authority: WO
Inventors: John Worthington; John Mark Gilbert; Lawrence J. Lukis; Leonard R. Steidel
Original assignee: Laser Master Corp
Current assignee: Laser Master Corp
Priority date: 1990-10-02
Filing date: 1991-10-02
Publication date: 1992-04-16
Anticipated expiration: 1993-04-02
Also published as: AU8949191A; JPH06501825A; WO1992006555A1; AU8949491A

Abstract

A digital halftone output image is rendered from a continuous tone input image having a plurality of input pixels which have been digitized as gray scale values. A page frame buffer (32) for storing a pixel representation of the halftone output image is defined in terms of a plurality of clustered-dot cells (50), each clustered-dot cell (50) encompassing a unique set of output pixels (52) in the page frame buffer (32). A number of interactive gray scale patterns (60) are defined for use in the clustered-dot dithering process in terms of the same number of output pixels (50) that define a single clustered-dot cell (50). Each interactive gray scale pattern (60) is capable of producing a unique gray scale value when applied to the clustered-dot cell (50). A computer processor (34) produces the halftone output image by dithering each input pixel of the continuous tone input image to produce a unique clustered-dot cell (50) in the page frame buffer (32) which is filled with one of the interactive gray scale patterns (60) closest to the gray scale value of that input pixel. Unlike classical ordered dithering techniques which use a series of ordered gray scale patterns, the use of the series of interactive gray scale patterns (60) results in more output gray scale values than there are output pixels (52) in the clustered-dot cell (50). The interactive gray scale patterns (60) utilize the interaction among output pixels (52) in order to generate gray scale patterns which have the same number of output pixels (52) turned on, but which produce different gray scale values when printed. Because the interaction among ouptut pixels (52) is most prominent in those types of laser printers and the like which cannot produce individually discrete output pixels or which have output pixels (52) with unequal horizontal and vertical dimensions, the effectiveness of the present invention is greatest among these types of graphic display devices.

Description

METHOD AND APPARATUS FOR PERFORMING

CLUSTERED-DOT DITHERING FOR LASER PRINTERS

TECHNICAL FIELD

This invention pertains to methods and apparatus for producing gray scale or halftone values on a bi-level graphic device, such as a laser printer. More particularly, this invention pertains to a method and apparatus for performing cluster-dot dithering for laser printers and the like, especially laser printers which cannot print individual discrete output pixels or which have output pixels with unequal horizontal and vertical dimensions.

BACKGROUND ART

The art of using digital halftones to simulate continuous tone images on a bi- level graphic device is well known. For a more detailed discussion of the background and various techniques associated with digital halftoning and the halftoning process known as spatial dithering, reference is made to Ulichney, R., Digital Halftoning. (MIT

Press), 1987.

Spatial dithering techniques are generally divided into two classes based upon the nature of the "dots" produced by the dithering technique, dispersed-dot dithering and clustered-dot dithering. Dispersed-dot ditheπng methods depict a gray level by covering a small area with evenly distributed output pixels, each output pixel representing a discrete, uniform size dot. Clustered-dot dithering methods depict a gray level by concentrating the output pixels in small groups or cells, each cell representing a variable size dot.

The classical techniques for clustered-dot dithering have been used with analog graphic devices such as the offset printing process for almost one hundred years. In digital graphic devices, however, distributed-dot dithering techniques are generally graphic devices such as the offset printing process for almost one hundred years. In digital graphic devices, however, distributed-dot dithering techniques are generally preferred if the device can properly reconstruct isolated and discrete output pixels. As a result, the majority of existing digital dithering algorithms relate to the type of dispersed- dot dithering which is associated with the class of graphic display devices that have a relatively low spatial resolution and allow for precise control of individual output pixels, e.g., plasma panels, liquid crystal displays and CRT monitors. Also included in this class of graphic display devices are laser printers with higher resolutions and more precise and expensive optics and mechanics which enable the reproduction of isolated and discrete output pixels. The use of clustered-dot dithering in connection with digital graphic display devices generally has been reserved for those bi-level display devices whose physical reconstruction functions are not capable of properly displaying discrete and isolated output pixels, e.g., many types of lower resolution laser printers and thermal printers. By far and away, the most common clustered-dot dithering technique used for laser printers and the like is ordered dithering. In fact, ordered dithering is the type of dithering which is generally assumed when referring to digital halftoning, and the most commonly used page description language for laser printers only has an ordered dithering technique for performing digital halftoning. Ordered dithering techniques replicate the more traditional analog clustered-dot dithering techniques by filling the output cell with a periodic or ordered pattern representing the various gray scales to be simulated (e.g., classical screen, spiral dot, line screen, etc.). An alternative to the ordered dithering techniques that was recently proposed in Velho, L. and Miranda Gomes, J. in "Digital Halftoning with Space Filling Curves", ACM Computer Graphics. Vol. 25, No. 4, July 1991, pp. 81-90, uses an aperiodic space filling curve, instead of an ordered pattern, to fill the individual pixels in the cluster-dot cells.

Regardless of the type of clustered-dot dithering technique which is used, the primary problem with present clustered-dot dithering techniques for digital graphic devices is that there is no good solution to the tradeoff between the desire to increase the resolution of the image, i.e., the number of lines per inch (lpi) or dots per inch

(dpi), and the desire to increase the number of gray levels which are reproduced. In essence, if the cell size is increased to increase the number of gray levels which can be created using standard ordered patterns, the clustered-dots themselves become apparent, thereby introducing a low frequency distraction into the output image. Conversely, if the overall resolution is increased, the size of the cells must be decreased and, hence, the number of gray levels decreases. This tradeoff is especially problematic for the smaller, less expensive laser printers associated with desktop publishing systems and the like. The standard resolution of the laser printers used with such systems, typically a 300 X 300 dpi print engine such as the Canon CX or SX- based laser printer, severely limits the effective size of the output cells, or conversely the number of gray levels which can be produced for this type of print engine.

Another problem with present clustered-dot dithering techniques is the difficulty in dispersing error among adjacent cells. The ability to successfully implement error dispersion or error diffusion techniques is partly responsible for the preference of dispersed-dot dithering over clustered-dot dithering for digital graphic devices. Unfortunately, error diffusion techniques which work well for distributed-dot dithering are not as successful when applied to the larger output cells associated with clustered- dot dithering. Because the error is dispersed across adjacent cells which are separated by a distance corresponding to the period of the raster line frequency, as opposed to dispersing error across adjacent pixels which are only separated a distance corresponding to the pixel resolution, the resulting image tends to blur or smear, particularly along image edges and areas of high tonal variation. U.S. Patent No. 4,654,721 describes one technique for implementing error diffusion for clustered-dot dithering wherein the entire error is dispersed to at least two adjacent cells in a random proportion. In the space filling curve technique described above, error diffusion is accomplished by propagating the entire error along the space filling curve to the first pixel in the next output cell being processed. In both of these cases, because the entire error is dispersed, the tendency of the error dispersion to blur the resulting image remains.

Another factor in implementing present clustered-dot dithering techniques is that classical ordered dither techniques assume a standard display device having equal resolutions in the horizontal and vertical dimensions, i.e., a square output pixel. However, some of the printer controller cards which have been introduced as a way to increase the speed and quality of the images produced with the smaller, less expensive laser printers have pixel resolutions which are non-square. Generally, such printer controller cards are installed directly in the personal computer and increase the quality and speed of the laser printers by using a separate co-processor and page frame buffer to create a pixel representation of the image that is then printed from the page frame buffer by directly controlling the modulation of the laser in the print-engine of the laser printer. In these printer controller cards it is possible to increase the horizontal resolution of the laser printer by controlling the modulation of the laser in the print- engine of the laser printer at a rate faster than the vertical resolution rate of the print engine. An example of such a printer control card is the LX6 Professional printer controller card available from LaserMaster Corporation, Eden Prairie, Minnesota, the assignee of the present invention, which can increase the horizontal component of the pixel resolution of the laser printer to 600 X 300 dpi or 1000 X 400 dpi, depending upon the type of laser printer. The increase in horizontal resolution generated by a printer controller card which produces non-square pixels significantly improves the quality of the resulting printed image; however, the output pixels which are defined in the page frame buffer of this system have unequal horizontal and vertical dimension. As a result, in order to use the classical ordered dithering techniques, a reseating of the input data to the aspect ratio of the printer is required. Even with this rescaling, the theoretical pixel assumed by these dithering techniques is still assumed to be a square pixel, rather than a pixel having horizontal and vertical dimension in accordance with the aspect ratio of the printer. This mismatch between the theoretical pixel used in the ordered dithering techniques and the non-square output pixel generated by the controller card may affect the performance of such systems when printing gray scale images. Consequently, using existing dithering algorithms and techniques which are designed for square pixel representations to perform digital halftoning with these types of printer controller cards is more complicated and may create unpredictable and unacceptable halftone output images. For digital graphics device which can produce isolated individual and discrete output pixels, distributed-dot dithering techniques are preferred because they provide a good solution to the tradeoff between the desire to increase the resolution of the image and the desire to increase the number of gray levels which are reproduced. Unfortunately, such techniques fail in the classical sense for print engines which cannot produce individually discrete output pixels. Consequently, there is a need for a clustered-dot dithering technique which can achieve the advantages of distributed-dot dithering techniques when used with laser printers and the like which cannot print individually discrete output pixels, especially laser printers which have output pixels with unequal horizontal and vertical dimensions. SUMMARY OF THE INVENTION

The present invention is a method and apparatus for clustered-dot dithering which is capable of rendering a halftone image on a laser printer or the like. Unlike classical ordered dithering techniques which use a series of ordered gray scale patterns, the present invention uses a series of interactive gray scale patterns which result in more output gray scale values than there are output pixels in the clustered-dot cell. The interactive gray scale patterns of the present invention utilize the interaction among output pixels in order to generate gray scale patterns which have the same number of output pixels turned on, but which produce different gray scale values when printed.

Because the interaction among output pixels is most prominent in those types of laser printers and the like which cannot produce individually discrete output pixels, the effectiveness of the present invention is greatest among these types of graphic display devices, particularly laser printers which have output pixels with unequal horizontal and vertical dimensions.

The present invention renders the digital halftone output image from a continuous tone input image having a plurality of input pixels which have been digitized as gray scale values, each gray scale value having a certain number of bits of resolution. A page frame buffer is used for storing a pixel representation of the halftone image. The page frame buffer is defined in terms of a plurality of clustered-dot cells, each clustered-dot cell encompassing a unique set of output pixels in the page frame buffer. A number of interactive gray scale patterns are defined for use in the clustered-dot dithering process in terms of the same number of output pixels that define a single clustered-dot cell. Each interactive gray scale pattern is capable of producing a unique gray scale value when applied to the clustered-dot cell. A computer processor produces the halftone output image by dithering each input pixel of the continuous tone input image to produce a unique clustered-dot cell in the page frame buffer which is filled with one of the interactive gray scale patterns closest to the gray scale value of that input pixel.

The interactive gray scale patterns used with the present invention include a certain number of the output gray scale values are created by different interactive gray scale patterns that have the same number of output pixels which are turned on in the clustered-dot cell. These different interactive gray scale patterns having the same number of output pixels which are turned "on" produce different output gray scale values due to differences in the selective positioning of the output pixels within the clustered-dot cell. As discussed in greater detail hereinafter, the effectiveness of selectively positioning the output pixels within the clustered-dot cell to create the interactive gray scale patterns of the present invention is most noticeable in those type of laser printers and the like which cannot print individually discrete output pixels, especially those which have output pixels with unequal horizontal and vertical dimensions.

To further enhance the effectiveness of the clustered-dot dithering technique of the present invention, a unique error diffusion technique is utilized. Li performing the clustered-dot dithering, the computer processor determines an eπror value representative of the mismatch between the gray scale value of the input pixel and the gray scale value of the interactive gray scale pattern selected to fill the clustered-dot cell for that input pixel. This error value is then diffused to a randomly selected one of a plurality of adjacent input pixels. In the preferred embodiment, the dithering of the input pixels to produce the clustered-dot cells in the page frame buffer is accomplished in a serpentine raster fashion and the error value is diffused to a randomly selected one of four adjacent input pixels which have yet to be processed and which are forward and inward relative to the input pixel being processed. Because the use of any error diffusion technique can result in the blurring or smearing of the resulting halftone image, particularly along image edges and areas of high tonal variation, a unique error diffusion scaling technique is applied to the error diffusion process to minimize the effects of this problem. As part of the error diffusion process, the computer processor determines an absolute difference between the gray scale value of the input pixel being processed and the gray scale value of the randomly selected input pixel to which the error value will be diffused. This absolute difference is then used to scale the error value which will be diffused. As a result, in low tonal contrast areas where error diffusion is most effective, the majority of the error will be dispersed, but in high tonal contrast areas, and especially image edges, the error will not be effectively dispersed because it is scaled by the difference in intensity between the two input pixels.

In the event that the input data is oversampled (i.e., the sampling density is greater than the clustered-dot cell density), the present invention may optionally use a sub-cell analysis to preserve the integrity of the oversampled input data. Unlike traditional clustered-dot dithering techniques which attempt to generate partial dots, the sub-cell analysis divides the clustered-dot cell of the present invention into sub-cells and analyzes the gray scale value of each sub-cell using the same technique of matching the interactive gray scale pattern as would be used for a full-sized clustered-dot cell. In the preferred embodiment, the present invention is implemented using a printer controller card which can modulate the print engine of the laser printer to produce output pixels having unequal horizontal and vertical resolutions. The output pixels in the preferred embodiment have an aspect ratio of 2.5 (i.e., 2.5 times as high as they are wide), and the clustered-dot cells are 2 pixels high by 10 output pixels wide for a 400x1000 dpi resolution system. Within the page frame buffer, the clustered-dot cells are positioned at equal offsets to each other on adjacent raster lines in the page frame buffer so as to form a diagonal pattern that will produce the halftone output image oriented at a 45° angle with respect to horizontal.

The effectiveness of selectively positioning the output pixels within the clustered-dot cell to create the interactive gray scale patterns of the present invention is most noticeable in those type of laser printers and the like which cannot print individually discrete output pixels, especially those which have output pixels with unequal horizontal and vertical dimensions. Instead of treating the fact that laser printers with lower resolution cannot print individually discrete output pixels as a disadvantage in the dithering process, the present invention utilizes this aspect of the physical reconstruction function of the print engine to enhance the dithering process. It will be recognized that the physical reconstruction function of a laser printer is neither truly binary nor truly gray scale. The physical reconstruction function of the print engine of a laser printer is binary in the sense that toner either sticks to the imaging drum or it does not. However, the physical reconstruction function is also not binary in the sense that the formation of neighboring pixels can and do contribute to the formation of the current pixel in the form of energy overlap of the spot image, especially for less expensive laser printers which do not have precise optical and mechanical control over the spot image. Those prior art dithering techniques which do attempt to address the issue of inability to print individual discrete output pixels because of spot image overlap in the print engine of the laser printer attempt to solve this phenomenon by the use of tone scale adjustments. The tone sale adjustment is used to compensate for a non-linear intensity reconstruction function caused, for example, by the apparent overlapping of contiguous pixels. In contrast to these solutions, the present invention recognizes that the overlap in the spot images of contiguous pixels can also be used as a means to control the interaction of adjacent pixels in order to produce "modified" output pixels which vary in the amount of toner that will be attracted to these pixels. The ability to control the formation of such "modified" output pixels is particularly suited to lower resolution laser printers which are modulated by a printer controlled card at a higher speed to produce output pixels having unequal horizontal and vertical dimensions. Because the laser in the print engine is modulated at a higher speed than the speed for the square pixels for which the print engine is designed, the threshold for toner attraction is altered and the ability to produce "modified" output pixels at a higher pixel resolution is created.

It will be recognized that the pixel representation created in the frame buffer for each horizontal raster line is used to control the laser in the laser printer. When the laser is turned on in response to an "on" pixel, a generally circular laser beam image is reflected on the print drum of the print engine to transfer charge elements to the drum.

The charge elements attract and pick up toner on the drum, or repel and erase toner from the drum in the case of an erase-white print engine. The toner remaining on the drum is then transferred to a sheet of paper. Although the pixel elements are thought of as square or rectangular shapes, in actuality, the edges of the pixels typically bleed into one another.

The parent application of the present invention taught that the method of selectively modifying pixels around a vertical transition point was effective at providing a non-gray scale anti-aliasing method for laser printers having unequal horizontal and vertical resolutions. It was thought that this method was effective due to the fact that the laser power function at the surface of the drum typically decreases with the distance from the center of the focal point over a generally circular or elliptical area covering a space larger than the theoretical rectangular pixel. Because the total laser power impinging on a given point determines the resulting amount of charge on the drum at that point which in turn determines whether toner will stick to that point or not, and because the laser beam spot image is larger than the theoretical pixel, the total laser energy impinging upon a given point on the drum may have components contributed by more than a single sweep of the laser beam.

It is believed that the present invention takes advantage of the physics of this process at the higher laser modulation rates to create the desired interactive gray scale patterns. For pixels in a first horizontal raster line that makes up the clustered-dot cell, some of those charge elements overlap onto the next horizontal raster line clustered-dot cell. In that next horizontal line, the application of the laser in response to the modified pixel representation briefly turns the laser on, for example, for a selectively modified "on" pixel. The duration of this pulse of laser energy is insufficient to charge this pixel location enough to attract toner, however, in the overlap region, sufficient charge may be added to the charge already deposited by pixels the lower raster line to alter the boundary of the region in which toner sticks to the drum. Thus, in effect, certain pixels within the clustered-dot cell may be controlled to within less than the height of a full pixel.

The present invention also recognizes that for laser printers where the buildup of toner from the bottom to the top of a raster line behaves in a non-linear fashion in response to the duty cycle of the control signal, it may be desirable to selectively modify the control signal by the application of a pseudo-duty cycle signal based upon the selective modification of pixels within the clustered-dot cell. It is believed for these types of laser printers that behave in a generally non-linear fashion, the physics of the overlapping of vertically adjacent pixels is such that there are an upper and lower limit to the duty cycle of the control signal that practically limit the effectiveness of the present invention. By using the present invention, clustered-dot dithering can be more effectively performed on laser printers, particularly less expensive, lower resolution laser printers and the like which cannot print individual discrete output pixels or which have output pixels with unequal horizontal and vertical dimensions. The present invention allows the advantages of distributed-dot dithering techniques to be realized by a clustered-dot approach. In addition, the clustered-dot dithering technique of the present invention allows images to be prepared for traditional offset and photo type setting printing press which require clustered-dot output images in order to produce gray scale patterns.

A primary objective of the present invention is to provide a simple and cost- effective solution that allows a clustered-dot dithering technique to achieve the advantages of distributed-dot dithering techniques when used with laser printers and the like which cannot print individually discrete output pixels or which have output pixels with unequal horizontal and vertical dimensions.

Another primary objective of the present invention is to provide a clustered-dot dithering technique with gray scale patterns which result in more output gray scale values than there are output pixels in the clustered-dot cell.

Another objective of the present invention is to provide a unique error diffusion technique, including an error scaling technique for use with the error diffusion technique, which is applicable to clustered-dot dithering. A further objective of the present invention is to provide a clustered-dot dithering technique which can print high quality halftone images using a printer controller card without increasing the amount of frame buffer memory required to store the pixel representation of that image.

A still further objective of the present invention is to provide a clustered-dot dithering technique which can print high quality halftone images using a printer controller card with a less expensive, lower resolution laser printer.

Still another objective of the present invention is to provide a clustered-dot dithering technique which can produce input images for traditional offset and photo type setting printing processes. These and other objectives of the present invention will become apparent with reference to the drawings, the detailed description of the preferred embodiment and the appended claims.

DESCRIPTION OF THE DRAWINGS Fig. 1 is a block diagram of a laser printing system having a printer controller card for generating an image to be printed by the laser printer.

Fig. 2 is a block diagram of the various functional components performed by the printer controller card of the preferred embodiment of the present invention.

Figs. 3a and 3b are graphical representations of the clustered-dot cell of the preferred embodiment of the present invention.

Fig. 4 is a graphic representation of the set of interactive gray scale patterns of the preferred embodiment of the present invention in the format for the clustered-dot cells shown in Fig. 3.

Fig. 5 is a graphical representation of the toner deposit functions of two different laser printers.

Figs. 6a and 6b are graphical representations of the spot images of the two different laser printers.

Fig. 7 is a flowchart showing the steps of the preferred embodiment of the dithering technique of the present invention. Fig. 8 is a graphic representation of a prior art set of classical ordered gray patterns for a spiral dot clustered-dot

DESCRIPTION OF THE PREFERRED EMBODIMENTS Referring now to Fig. 1, a typical personal computer system, such as a desktop publishing system 10, which includes a printer controller card that executes the software that comprises the preferred embodiment of the present invention will be described. The hardware for the desktop publishing system 10 is comprised of a personal computer 12 connected with a small, inexpensive laser printer 14. The personal computer 12 may be any one of a variety of personal computers such as an

IBM PC, XT/AT, 386, or PS/2, available from International Business Machines, Inc., or an Apple Macintosh II, available from Apple Computers, Inc. The personal computer 12 may be provided with a desktop publishing software package, such as Ventura Publisher, available from Xerox Corporation, PageMaker, available from Aldus Corporation, or GEM Desktop Publisher, available from Digital Research, Inc.

The personal computer 12 may also be provided with a graphics software package, such as Adobe Photo Shop, available from Adobe Systems, Inc. The laser printer 14 may be any type of Canon CX or SX laser printer such as the HP LaserJet Series II available from Hewlett Packard, the LaserWriter, available from Apple Computer, Inc., or the Canon LBP8-III, available from Canon Inc., although it will be recognized that other type of laser printer print engines can also work with the present invention.

In normal operation without a printer controller card, the personal computer 12 typically includes a main PC mother board 16 and a serial port 18 through which the personal computer 12 communicates with the internal controller 20 of the laser printer 14. The computer 12 sends a serial bit stream to the laser printer 14 over an RS-232-C serial interface 22 in the form of various commands and data that represent the image to be printed by the laser printer 14. The internal controller 20 decodes the serial bit stream and generates the control signals that will be supplied to the laser 24 to drive the print engine 26 that creates the printed images corresponding to the various commands and data received by the internal controller. For a more detailed explanation of the internal operation of the laser printer 14, reference is made to the LaserJet II Printer User's Manual, Edition 1, available from Hewlett-Packard.

Because of the inherent limitations on the speed at which the commands and data can be transferred over the serial interface and decoded by the internal controller 20, the page throughput for the laser printer 14 is typically very low, 6 pages per minute or less, depending upon the formatting and type of information being printed. To solve this problem and to simultaneously increase the quality and performance features of the laser printer, various printer controller cards 30 have been introduced, such as the LX6 Professional, available from LaserMaster Corporation, Eden Prairie,

Minnesota. The printer controller card 30 of the preferred embodiment is located in the personal computer 12 and communicates directly with the PC mother board 16 via an internal bus 28. It will be recognized, however, that the printer controller card 30 may be located in the laser printer 14 or that the present invention may be implemented within the internal controller 20 of the laser printer 14.

In the preferred embodiment, the printer controller card 30 is an LX6 Professional printer controller card selected to match the particular type of laser printer 14 being and personal computer 12 used in the desktop publishing system 10. The LX6 Professional controller consists of a frame buffer 32, a co-processor 34 and a video interface 36. The co-processor 34 receives the various commands and data representing the image to be printed from the PC mother board 16 via the bus 28. Because the bus 28 is a parallel bus, the transfer rate is much faster than for the serial port 18. As described in greater detail hereinafter in connection with the description of Fig. 2, the co-processor 34 is responsible for receiving the continuous tone digital image data and converting it to halftone digital image data to be stored in the frame buffer 32. When the laser printer 14 is ready to print a page or "frame" worth of images, the pixel representation in the frame buffer 32 is transferred to the laser printer 14 via the video interface 36 in the printer controller 30 that communicates directly with the laser 24 via a video cable 38. An internal switch 40 in the laser printer 14 allows the printer controller 30 to override the internal controller 20 of the laser printer and directly modulate the laser 24. It is this direct modulation of the laser 24 that allows the printer controller 30 to increase the horizontal resolution of the laser printer 14. For a more detailed explanation of the operation of the LX6 Professional controller 30, reference is made to the LX User Guide, which is incorporated herein by reference and is available from LaserMaster Corporation.

Referring now to Fig. 2, an overview of how the printer controller card 30 of the preferred embodiment of the present invention operates as an image rendering system will be described. When printing a gray scale image, the printer controller card 30 will receive a Continuous-tone Digital Image, J[n], from the computer 12. The Continuous-tone Digital Image J[n] typically includes a set of data points representative of the image to be printed, each point having a gray scale value represented in terms of N bits of resolution, where N is a number of bits greater than 1 and is most typically 8 bits. In most cases, the Continuous-tone Digital Image J[n] represents data points from a physical image which has been scanned. In other case, the Continuous-tone Digital

Image J[n] represents data points which have been generated by a computer graphics program. There are several standard graphic file formats for representing the data points which comprise the Continuous-tone Digital Image J[n], such as lF,PICT, EPS, GIF, etc. In the preferred embodiment, the input data from the graphic file format is converted into PostScript® format before being transferred to the printer controller card 30.

The Continuous-tone Digital Image J[n] is processed by the printer controller card 30 to generate the Halftone Digital Image I[n']. As described above, the Halftone Digital Image I[n'] is then supplied to the laser printer 14 in order to generate the desired Halftone Image, I(x). The Physical Reconstruction Function represents a system model for the given binary display device, in this case the laser printer 14, which takes as its input the binary discrete-space image represented by the Halftone Digital Image I[n'] and creates the continuous-space visual image represented by the Halftone Image I(x). It will be recognized that the Physical Reconstruction Function will vary widely with the particular binary display device and that the interactive gray scale values of the present invention can be modified to accommodate these variances in the Physical Reconstruction Function of the binary display device.

The various functional elements within the printer controller card 30 which accomplish the transformation of the Continuous-tone Digital Image J[n] into the Halftone Digital Image I[n'] include a Retrospective Resampler means 40, a Tone Scale

Adjust means 42, a Sharpen means 44 and a Halftone means 46. The Retrospective Resampler means 40 is typically a digital sealer which adjusts the resolution of the Continuous-tone Digital Image J[n] to the resolution of the Halftone Digital Image I[n']. Because of the lower resolutions of the laser printers 14 used in connection with the present invention, the scaling performed by the Retrospective Resampler means 30 may reduce the resolution of the Continuous-tone Digital Image J[n]. In the event that the input data is oversampled (i.e., the sampling density is greater than the clustered-dot cell density), the present invention may optionally use a sub-cell analysis to preserve the integrity of the oversampled input data. In the preferred embodiment, the Retrospective Resampler means 30 reconstructs the original continuous image from the given samples for J[n] by a process of interpolation, and then resamples this reconstruction at the resolution of the clustered-dot cells to produce a new Continuous- tone Digital Image J[n'] having a resolution that is equal to that of the Halftone Digital Image I[n']. The resolution of the Halftone Digital Image I[n'] of the preferred embodiment is either 141 lpi with a dot or cell size of 2 pixels high by 10 pixels wide, or 90 lpi with a dot or cell size of 3 pixels high by 16 pixels wide, depending upon the degree of resolution which is desired for the image.

Once the Continuous-tone Digital Image J[n'] is properly scaled, one or more adjustments may optionally be made to the data to enhance the end result, including

Tone Scale Adjust means 42 and Sharpen means 44. Typically, the Tone Scale Adjust means 42 applies a non-linear transformation to the Continuous-tone Digital Image J[n'] to compensate for the particular tone scale modifications peculiar to the Physical Reconstruction Function of the particular type of laser printer 14 in combination with the halftoning method which is used. In the prior art, this is the point at which most systems would attempt to compensate for the spot image overlap in the print engine of the laser printer by clipping the light and dark ranges of the Continuous-tone Digital Image J[n'] which are to be mapped as either completely black or completely white. Accordingly, it will be recognized that the prior art solution to the problems of dot overlap in the print engines was to effectively reduce the number of gray scale levels which would be produced by the system. The Sharpen means 44 can also operate on the data which is closest to the black or white levels so as to precompensate for the blurring of fine details in the image which tend to occur during the halftoning process. Again, however, the prior art has primarily used the Sharpen means 44 as a preparatory step to the halftoning process, not as part of the halftoning process.

Referring now to Figs. 3a and 3b, the preferred embodiment of the clustered- dot cells 50 generated by the Halftone means 46 will be described. As shown in Fig. 3a, each clustered-dot cell 50 is defined within the frame buffer 32 as comprising twenty output pixels 52 in a 2x10 rectangular grid. Because the output pixels 52 have an aspect ratio of 2.5 (400x1000 dpi resolution), the aspect ratio of each clustered-dot cell 50 is also 2.5. To orient the halftone grid at 45° with respect to horizontal, the clustered-dot cells 50 are staggered at half cell increments along each pair of raster lines. In the preferred embodiment, to ease the implementation of the present invention and to improve the high frequency detail of the halftone image which is retained across clustered-dot cell boundaries, theoretical clustered-dots 54 are actually defined across the boundaries of three clustered-dot cells 50 as shown. As a result, the use of the theoretical clustered-dots 54 disperses the gray scale values in the actual clustered-dot cells 50 across the boundaries of each cell. To implement the theoretical clustered-dots 54, the interactive gray scale patterns described in connection with Fig. 7 fill each clustered-dot cell 50 so as to create a half circle in the bottom of the clustered-dot cell 50 and two quarter circles in each upper comer of the clustered-dot cell 50.

Referring now to Fig. 4, the interactive gray scale patterns 60 of the preferred embodiment of the present invention will be described. The Halftone means 46 of the present invention uses a set of interactive gray scale patterns 60 to create more gray scale levels than there are pixels in the clustered-dot cell 50. The cross-hatched output pixels 52 in Fig. 4 indicate those pixels in the frame buffer 32 which would be turned "on" and the blank output pixels 52 indicate those pixels in the frame buffer which would be turned "off" to create the gray scale value for that particular gray scale pattern 60. The dark lines 62 indicate which pixels in the clustered-dot cell 50 will generally contribute to which theoretical cluster-dots 54 as shown in Fig. 3b. For comparison purposes, above each gray scale pattern 60 is the range of gray scale values shown in brackets □ for an 8 bit resolution continuous-tone digital input expressed from in terms of the values from 0 - 255 which are associated with that gray scale pattern. For examp- -., it will be seen that the gray scale pattern for the range [69-76] has the same number of output pixels 52 which are turned on (5 out of 20) as the gray scale pattern for the range from [77-84], The difference between these two patterns stems from the selective location of two of the "on" pixels as shown at 64 and 66. For the gray scale pattern for the range from [69-76], the pixels shown at 64 are separated by one pixel from each other, whereas for the gray scale pattern for the range from [77-84], the pixels shown at 66 are located adjacent each other. When the pixels 66 are adjacent each other, the spot images overlap and each pixel is fully charged to attract toner. When the pixels 64 are separated, neither pixel is fully charged to attract toner and, as a result, the total toner deposited for the clustered-dot cell 50 is less than when the pixels 66 are adjacent each other, even though the same total number of pixels are turned "on" in the clustered-dot cell 50.

As can be seen from the interactive gray scale patterns 60 shown in Fig. 4, there are a total of 32 gray scale value ranges which are represented in the preferred embodiment. For comparison, Fig. 8 shows a typical prior art spiral dot gay pattern for a 2x5 square pixel clustered-dot cell covering the same total surface area as the 2x10 cell of the preferred embodiment It will be seen that the present invention has almost three times as many gray levels as can be produced in the prior art scheme shown in Fig. 8. Even if a 2x10 cell with rectangular pixels is used as the clustered-dot cell 50, the present invention still provides 50% more gray levels than the theoretical maximum of twenty one gray scale values (4x5 pixels plus one for all white) which could be represented using the classical spiral dot ordered dithering technique.

It will be recognized that many different variations can be made to the gray scale patterns 60 within the scope of the present invention. For example, the size and shape of the clustered-dot cell 50 can be varied in accordance with the output resolution and number of gray scale levels which are desired. As explained in greater detail hereinafter, the manner in which adjacent output pixels 52 will interact may also vary, depending upon the physical and optical characteristics of the print engine of the laser printer 14. It will also be apparent that different fill techniques for dithering the clustered-dot cell 50 can be utilized other than filling the clustered-dot cell 50 according to the theoretical cluster-dot 54.

Another important variation to the implementation of the gray scale patterns 60 would be to vary the mapping or ranging of the gray scale patterns to the gray scale values those patterns represent. For example, in the preferred embodiment, the gray scale pattern 68 is set equal to a gray scale value range of [252-253] , even though there are 4 of the 20 pixels which are turned "off in this pattern. The reason for this is because the interaction of the pixels in the SX print engine in the preferred embodiment has been found to be such that less than 4 pixels turned "off" in this particular pattern effectively produces an entirely black clustered-dot cell 50 as the output result. Consequently, the gray scale patterns 60 are arranged to take advantage of the more significant differences in the interaction of pixels near the middle of the gray scale range. By varying the mapping or ranging of the gray scale values with respect to the gray scale patterns 60, both linear and non-linear mapping functions can be implemented for continuous-tone digital input images having gray scale values of varying resolutions.

The ability to create the interactive gray scale patterns 60 is based on obtaining a more accurate understanding of the Physical Reconstruction Function of the particular print engines of the laser printer 14 and applying that knowledge to create a better dithering process for the particular print engine. Referring now to Figs. 5 and 6a and 6b, a background explanation will be presented of why it is believed that the present invention is effective in creating multiple gray scale values for clustered-dot cells having the same number of output pixel which are to be printed by a binary imaging printer. Different types of print engines having uniquely different sizes, shapes and power densities associated with their laser beam spot images can affect the way in which toner will be deposited on the drum in response to a particular video control signal. Fig. 5 shows the response function of two different laser printers to a control signal having a varying duty cycle. The response function is plotted in terms of the buildup of toner from the bottom to the top of a raster line for the vertical height of a single pixel (vertical axis) versus the percentage duty cycle of the control signal (horizontal axis)

As shown by the function for print engine A, the buildup of toner from the bottom to the top of a raster line for this print engine in response to the control signal behaves in a generally linear fashion as the duty cycle of the control signal is increased. In other print engines, such as shown by the function for print engine B, the buildup of toner from the bottom to the top of a raster line will behave in a non-linear fashion in response to the duty cycle of the control signal.

It is believed that the differences in the toner buildup function in response to the duty cycle of a control signal for a particular print engine are due, in part, to the different type of spot images produced by different print engines. As shown in Fig. 6a, if the energy distribution function is a smooth gaussian function, then the toner buildup function will be linear and the best approach is to accumulate the "area error" as described in the parent application to the present invention. On the other hand, if the energy distribution function is like that shown in Fig. 6b (more exponential with a sharper center band most likely due to focusing of the laser beam by more expensive optics), then the toner buildup function in response to the duty cycle of a control signal will be non-linear. In this case, the technique of accumulating the area error may not result in the desired smoothing because of the smaller degree of overlap among vertically adjacent pixels.

Referring again to Fig. 5, the present invention also may allow multiple gray scale values for clustered-dot cells having the same number of output pixel to be created with binary imaging printers having a non-linear toner buildup function in response to the duty cycle of a control signal. As will be apparent from the figure, there are an upper and lower limit to the duty cycle of the signal, above and below which there is no practical effect on the height of the toner deposit in response to the control signal. Below the lower limit, the selective modification of pixels at these lower duty cycles does not result in any appreciable modification upward to the edge of the image. Similarly, above the upper limit, the selective modification of pixels at these higher duty cycles does not result in any appreciable modification downward to the edge of the image. However, the inventors of the present invention have discovered that a control signal having a duty cycle within these upper and lower limits can be effective in controlling the buildup of toner, even for those print engines having non-linear toner buildup in response to the control signal.

Referring now to Fig. 7, the preferred embodiment of the Halftone means 46 will be described. The modified input image J'[n'] is supplied to the Halftone means

46 after having had appropriate adjustment made for scaling resolution, tone scale and sharpening. In the preferred embodiment, the Dither means 46 of the present invention is accomplished by the co-processor 34 as it is generating each horizontal raster line 50 to be stored in the frame buffer 32. Typically, the horizontal raster lines are processed from top to bottom in the frame buffer 32 and the output pixels 52 in each horizontal raster line are processed from left to right and then right to left in a serpentine manner, although it will be recognized that the raster lines and output pixels 52 may be processed in any direction so long as the processing is consistent throughout an entire page in the frame buffer 32. To minimize the computational effort in performing the dithering by the co-processor 34, two tables relating to the interactive gray scale patterns 60 are created. The first table contains the assigned interactive gray scale pattern 60 for each of the 256 gray scale values represented by a gray scale input value having 8 bits of resolution. The second table contains the error in terms of gray scale value between the assigned interactive gray scale pattern and the actual gray scale value corresponding to the gray scale input value.

For each modified input pixel of J'[n'], at step 70 the co-processor 34 determines an Error Dispersion Pixel, J'[P'], which is downward and inward from the pixel presently being processed J'[P]. In the preferred embodiment, a random direction number from 0-3 will select one of the four pixels which are adjacent pixel J[P] and which have yet to be processed. By randomly assigning the direction in which the error will be dispersed in the form of the Error Dispersion Pixel, the present invention simply and easily avoids the tendency of worming or pebbling which would otherwise affect the error dispersion. At step 72, the value of the difference between the pixel J'JP] and the Error Dispersion Pixel, J'[P'], divided by the gray scale range (i.e., 256) is calculated. This value will be used to scale the amount of error to be dispersed to the Error Dispersion Pixel, J'[P']. At step 74, the Dispersion Error for J'[P] is determined by lookup from the second table. At step 76, the Dispersion Error is scaled by the result of step 72 and added to (or subtracted from) the Error Dispersion Pixel, J'[P']. Finally, at step 78, the interactive gray scale pattern from the first table corresponding to J'[P] is moved into the corresponding distributed-dot cell 50 in the frame buffer 32.

In an alternative embodiment which is not shown in Fig. 7, the co-processor may further sub-divide the dithering process in the event that the Continuous-tone Digital Image is presented with a higher degree of resolution than the output resolution as defined by the clustered-dot cells 50 (i.e., 141 lpi or 90 lpi). In this case, the analysis of each clustered-dot cell 50 for purposes of matching it to a corresponding gray scale pattern 60 could be divided into an analysis of sub-cells of the clustered-dot cell 50, e.g., four 1x5 sub-cells. Each sub-cell is then matched to that portion of the gray scale pattern which corresponds to the gray scale value of the Continuous-tone

Digital Image, as modified, which is associated with the sub-cell being processed. This process of dividing a cell into sub-cells in the event that the input resolution is higher than the output resolution provides a unique mechanism whereby the present invention can improve upon the process of partial dotting which is well known in the prior art. Although the description of the preferred embodiment has been presented, it is contemplated that various changes could be made without deviating from the spirit of the present invention. Accordingly, it is intended that the scope of the present invention be dictated by the appended claims rather than by the description of the preferred embodiment. We claim:

Claims

1. A clustered-dot dithering method for rendering a halftone image on a laser printer, the method comprising the steps of:

(a) providing a continuous tone input image having a plurality of input pixels which have been digitized as gray scale values having N-bits of resolution, where N is an integer greater than or equal to 2;

(b) defining a clustered-dot cell representing M output pixels in a page frame buffer, where M is an integer greater than 2 and less than N squared; (c) defining a number G of interactive gray scale patterns, each gray scale pattern capable of producing a unique gray scale value when applied to the clustered-dot cell, where G is a number greater than M; and

(d) using a processor means to produce a halftone output image of the continuous tone input image by dithering each input pixel to produce a unique clustered-dot cell in the page frame buffer which is filled with one of the interactive gray scale pattems representative of the gray scale value of that input pixel, whereby the resolution of the halftone output image produced is not in a directly inverse relationship to the number G of gray scale values. *

2. The clustered-dot dithering method of claim 1 wherein the interactive gray scale pattems utilize the interaction among output pixels in a laser printer which cannot print individually discrete output pixels to produce more output gray scale values than there are output pixels in the clustered-dot cell.

3. The clustered-dot dithering method of claim 2 wherein certain of the output gray scale values are created by multiple interactive gray scale patterns having the same number of output pixels which are turned on in the clustered-dot cell, the multiple interactive gray scale patterns producing different output gray scale values due to differences in the selective positioning of the output pixels within the clustered-dot cell.

4. The clustered-dot dithering method of claim 1 wherein the output pixels have unequal horizontal and vertical dimensions.

5. The clustered-dot dithering method of claim 4 wherein the clustered-dot cells are each 2 pixels high by 10 output pixels wide and are positioned to form a diagonal pattern of clustered-dot cells to form the halftone output image.

6. The clustered-dot dithering method of claim 1 further comprising the step of: (e) using the processor means to determine an error value representative of the mismatch between the gray scale value of the input pixel and the gray scale value of the interactive gray scale pattern selected to fill the clustered-dot cell for that input pixel and diffusing the error value to a randomly selected one of a plurality of adjacent input pixels.

7. The clustered-dot dithering method of claim 6 further comprising the step of:

(f) using the processor means to determine an absolute difference between the gray scale value of the input pixel being processed and the gray scale value the randomly selected input pixel to which the error value will be diffused and using the absolute difference to scale the error value which will be diffused.

8. The clustered-dot dithering method of claim 1 wherein step (d) comprises the steps of:

(dl) using the processor means to resample the continuous tone input image such that a modified input image is generated having the same resolution in terms of number of input pixels as the clustered-dot cells; (d2) using the processor means to perform a tone scale adjustment of the modified input image; (d3) using the processor means to sharpen the modified input image;

(d4) using the processor means to dither the modified input image to produce the halftone output image by selecting the interactive gray scale pattern which most closely approximates the input pixel of the modified input image to fill the clustered-dot cell associated with that input pixel.

9. The method of claim 1 wherein the resolution of the continuous-tone input image is greater than the resolution of the halftone ouφut image and step (d4) further comprises the steps of:

(d41 ) dividing the clustered-dot cells into a plurality of sub-cells; (d42) assigning the sub-cells to the input pixels of the modified input image which are a higher resolution than the halftone output image; and (d43) using the processor means to dither the modified input image to produce the halftone output image by selecting the interactive gray scale pattern which most closely approximates the input pixel of the modified input image assigned to the subcell to fill each of the subcells of the clustered-dot cell associated with that input pixel.

10 . A clustered-dot dithering method for rendering a halftone image on a laser printer, the method comprising the steps of:

(a) providing a continuous tone input image having a plurality of input pixels which have been digitized as gray scale values;

(b) defining a plurality of clustered-dot cells in a page frame buffer, each clustered-dot cell representing a plurality of output pixels;

(c) defining a number of gray scale pattems, each gray scale pattern capable of producing a unique gray scale value when applied to the clustered-dot cell;

(d) using a processor means to produce a halftone output image of the continuous tone input image by dithering each input pixel to produce a unique clustered-dot cell in the page frame buffer which is filled with one of the interactive gray scale pattems representative of the gray scale value of that input pixel; and

(e) using the processor means to determine an error value representative of the mismatch between the gray scale value of the input pixel and the gray scale value of the interactive gray scale pattern selected to fill the clustered-dot cell for that input pixel and diffusing the error value to a randomly selected one of a plurality of adjacent clustered-dot cells.

11. The clustered-dot dithering method of claim 9 further comprising the step of: (f) using the processor means to determine an absolute difference between the gray scale value of the input pixel being processed and the gray scale value the randomly selected input pixel to which the error value will be diffused and using the absolute difference to scale the error value which will be diffused.

12. The clustered-dot dithering method of claim 10 wherein the dithering of the input pixels to produce the clustered-dot cells in the page frame buffer is accomplished in a serpentine raster fashion and the error value is diffused to a randomly selected one of four input pixels which are forward and down relative to the input pixel being processed.

13. A clustered-dot dithering apparatus for rendering a halftone image on a laser printer from a continuous tone input image having a plurality of input pixels which have been digitized as gray scale values having N-bits of resolution, where N is an integer greater than or equal to 2, the apparatus comprising: page frame buffer means for storing a pixel representation of the halftone image, the page frame buffer means being defined in terms of a plurality of clustered-dot cell representing M output pixels in a page frame buffer, where M is an integer greater than 2 and less than N squared; storage means for storing a number G of interactive gray scale pattems, each gray scale pattern capable of producing a unique gray scale value when applied to the clustered-dot cell, where G is a number greater than M; and processor means for producing a halftone output image of the continuous tone input image by dithering each input pixel to produce a unique clustered-dot cell in the page frame buffer means which is filled with one of the interactive gray scale pattems representative of the gray scale value of that input pixel, whereby the resolution of the halftone output image produced is not in a directly inverse relationship to the number G of gray scale values.

14. The clustered-dot dithering apparatus of claim 13 wherein the interactive gray scale patterns utilize the interaction among output pixels in a laser printer which cannot print individually discrete output pixels to produce more output gray scale values than there are output pixels in the clustered-dot cell.

15. The clustered-dot dithering apparatus of claim 14 wherein certain of the output gray scale values are created by multiple interactive gray scale patterns having the same number of output pixels which are turned on in the clustered-dot cell, the multiple interactive gray scale patterns producing different output gray scale values due to differences in the selective positioning of the output pixels within the clustered-dot cell.

16. The clustered-dot dithering apparatus of claim 13 wherein the output pixels have unequal horizontal and vertical dimensions.

17. The clustered-dot dithering apparatus of claim 16 wherein the clustered-dot cells are each 2 pixels high by 10 output pixels wide and are positioned to form a diagonal pattern of clustered-dot cells to form the halftone output image.

18. The clustered-dot dithering apparatus of claim 13 further comprising: means for determining an error value representative of the mismatch between the gray scale value of the input pixel and the gray scale value of the interactive gray scale pattern selected to fill the clustered-dot cell for that input pixel and diffusing the error value to a randomly selected one of a plurality of adjacent clustered-dot cells.

19. The clustered-dot dithering apparatus of claim 18 further comprising: means for determining an absolute difference between the gray scale value of the input pixel being processed and the gray scale value the randomly selected input pixel to which the error value will be diffused and using the absolute difference to scale the error value which will be diffused.

20. The clustered-dot dithering apparatus of claim 13 wherein the processor means comprises: means for resampling the continuous tone input image such that a modified input image is generated having the same resolution in terms of number of input pixels as the clustered-dot cells; means for performing a tone scale adjustment of the modified input image; means for sharpen the modified input image; means for dithering the modified input image to produce the halftone output image by selecting the interactive gray scale pattern which most closely approximates the input pixel of the modified input image to fill the clustered-dot cell associated with that input pixel if the resolution of the continuous-tone input image is less than or equal to the resolution of the halftone output image; and means for dividing the clustered-dot cells into a plurality of sub-cells, assigning the sub-cells to the input pixels of the modified input image and dithering the modified input image to produce the halftone output image by selecting the interactive gray scale pattern which most closely approximates the input pixel of the modified input image assigned to the subcell to fill each of the subcells of the clustered-dot cell associated with that input pixel if the resolution of the continuous-tone input image is greater than the resolution of the halftone output image.