Process for Selecting Output Levels for Multi-Level Halftone in the Presence of an Unstable Display Device

The present invention is directed to the field of multi-level halftoning and, more particularly, to a process for choosing multiple output density levels to be utilized by multi-level halftoning in the presence of an unstable output device.

For years, many types of display devices have essentially been used in a binary mode, capable of providing only two density levels at each pixel location. These technologies were combined with various forms of bi-tonal halftoning to provide a simulated continuous tone reproduction capability. In bi-tonal halftoning, the appearance of intermediate shades of gray are created by a spatial modulation of black and white.

Recent improvements and advances in display technology have resulted in the availability of display devices with the capability of providing more than two levels of density at each pixel location. A variety of halftone algorithms have been developed which utilize the additional levels. This practice, known as multi-level halftoning, creates the appearance of intermediate tones by the spatial modulation of more than two tones, i.e., black, white, and one or more shades of gray.

In the existing art, U.S. Pat. No. 4,547,811 addresses multi-level halftoning techniques. The '811 patent relates to a method and apparatus for gray level processing, wherein images with less gray levels and many gray levels are reproduced in high quality. Additionally, U.S. Pat. No. 4,792,979 to Nomura et al relates to a method and apparatus for correcting the gradation of an image represented by image data. Although the prior art addresses the problem of density levels, i.e., minimizing system artifacts such as contouring and noise, the existing art does not address unstable display devices.

It is seen then that it would be desirable to have a process for optimizing an unstable output device.

The present invention is a process for selecting output levels for multi-level halftones in the presence of an unstable device. More specifically, the present invention is a process for choosing multiple output density levels to be used by a multi-level halftoning algorithm in the presence of an unstable device. This process optimizes the performance and capabilities of a given multi-level half-tone algorithm by specifying output levels whose instability has a minimal impact on image quality.

In accordance with one aspect of the present invention, a process for selecting output levels for multi-level halftones in the presence of an unstable output device comprises the steps of: defining a function which quantifies undesirable mean level image artifacts for an unstable display device and then choosing density levels which minimize the function.

Accordingly, it is an object of the present invention to provide a process for selecting output levels for multi-level halftoning which can optimize the performance and capabilities of a given multi-level halftone algorithm. Other objects and advantages of the invention will be apparent from the following description, the accompanying drawings and the appended claims.

FIG. 1 is block diagram of a typical architecture employing a multi-level printer;

FIG. 2 is a graphical illustration of a printer tone transfer function for the multi-level printer in FIG. 1;

FIG. 3 is a graphical illustration of a target system tone transfer function from the input of the output calibration table to the output of the large-area average of FIG. 1;

FIGS. 4 and 5 are level rendering approaches with minimum and maximum modulation, respectively, for the output of the multi-level halftone of FIG. 1;

FIG. 6 is a tone transfer function for the thirteen available halftone levels rendered in FIGS. 4 and 5;

FIG. 7 is a graphical illustration of the output calibration table of FIG. 1;

FIG. 8 is a graphical illustration of a nominal system tone transfer function associated with the multi-level printer of FIG. 1 operating at a nominal setting superimposed on the target system tone transfer function of FIG. 3; and

FIG. 9 is a graphical illustration of the target system tone transfer of FIG. 3 and actual system tone transfers for the printer of FIG. 1 operating at extremes.

The present invention relates to a process for choosing multiple output density levels to be utilized by a multi-level halftoning algorithm in the presence of an unstable display device. Multi-level halftoning creates the appearance of intermediate tones by the spatial modulation of more than two tones, i.e., black, white, and one or more shades of gray.

Referring to the drawings, FIG. 1 illustrates an N-level display device or system 10 employing a multi-level halftoning printer 12. The multi-level printer 12, a multi-level halftone 14, and a printer control table 16 are shown as an output device 18 capable of printing N unique large-area densities. The output of the printer 12 must be processed through a large-area average box 20, indicative of integration over a large area, to determine the average density for evaluating an actual system tone transfer. The output of the printer 12 also provides a printed output 22. Typically, a calibration table, such as output calibration table 24, precedes the N-level output device 18 in order to achieve the target system tone transfer function between input image data 26 and the average density printed output 22.

In order to fully utilize all N output levels of the N-level display device 10, the dynamic resolution of the input 26 is usually greater than N, i.e., 2.sup.L >N. Following the output calibration table 24, the multi-level halftone algorithm 14 creates a spatially modulated M-level output signal where N>M. Each of the M levels is translated into a printer control signal Y.sub.i, through the printer control table 16. Typically, y.sub.i is K bits wide where M<<2.sup.K. Ideally, the display device 10 prints each pixel independently of those around it with a density that corresponds to the pixel code value Y.sub.i,

In the prior art, the printer control table 16 is built to minimize system artifacts such as contouring and noise. However, this approach assumes that all the density levels provided by the display device will be reasonably stable. Unfortunately, regions of the display device's density tone scale will often fluctuate due to factors such as component wear and changing environmental conditions. For example, as shown in FIG. 2, assuming K=9, a printer tone transfer function of the multi-level printer 12 may consist of a typical s-shape, as indicated by solid curve 28. The printer tone transfer function 28 is measured from the input of the printer 12 to the output of the printer 12, as the printer 12 represents the unstable component in the system 10. Over the life of the printer 12, the printer tone transfer function may fluctuate to either of the extremes represented by the dotted lines 30 and 32.

Consequently, to carry out the process of the present invention, a function is defined which quantifies undesirable mean level image artifacts for the unstable display device 10. One means for defining the function involves the identification of a target system tone transfer curve which specifies the average output density for each input level as processed by the system 10 of FIG. 1. Assuming L to be equal to eight, where L is usually a given system parameter, a target system tone transfer curve 34 will usually be non-linear, as illustrated in FIG. 3. Even though the input code value v along the horizontal axis in FIG. 3 is a discrete quantity, the curve 34 is shown as a continuous curve for the sake of simplicity, which extends out to the output of the large-area average of box 20 in FIG. 1. Due to display device instabilities, an actual system tone transfer will vary within some envelope, as indicated in FIG. 9. The actual shape of the envelope will depend on the nature of the multi-level halftone algorithm 14, the physical characteristics of the display substrate and display toners or inks, and the entries in the printer control table 16 which are to be optimized. This is accomplished by defining the function that is to be minimized, as described in more detail later.

For example, the nature of the multi-level halftone algorithm 14 may be to create a periodic one-dimensional micro-structure using halftone cells that are one pixel wide by four pixels long. If the output of the halftone algorithm is quantized to four levels, i.e., M=4, then for typical applications, a total of thirteen mean levels can be rendered.

Two approaches to rendering the thirteen levels are shown in FIGS. 4 and 5. FIG. 4 illustrates rendering the thirteen levels, form Level 0 to Level 12, with a minimum amount of modulation, and FIG. 5 illustrates rendering the thirteen levels, form Level 0 to Level 12, with a maximum amount of modulation. FIGS. 4 and 5 shown cross-sections of a segment of a waveform 36, where the waveform is equal to zero at Level 0 and equal to one at Level 12. Hence, FIGS. 4 and 5 show two extremes for going from a waveform of zero to a waveform of one. From FIGS. 4 and 5, it is obvious that the amount of modulation affects which of the M available density levels is used to synthesize the N output levels, thereby impacting the amount of variation that a tonally unstable pixel may have on any one of the N average output levels.

The physical characteristics of the hardcopy display device will also affect the shape of the instability envelope, due to the interaction of the modulated multi-level halftone image with the paper and toners. Given the density of each pixel, the first-order approximation of the average density over some region R is given by

where D.sub.ave is the average density of the region and d.sub.i is the density of the ith pixel in the region. Equation (1) represents computing the average reflectance or transmittance and then taking the log of the average. However, an alternate form,

may be more accurate due to second-order effects such as dot-growth, the paper spread function and multiple internal reflection. The actual average density for a given display technology will usually be bounded by the two extremes given in Equations (1) and (2). In a preferred embodiment of the present invention, the large-area average of box 20 in FIG. 1 is either measured or predicted, if possible, by models such as Equations (1) or (2).

It is assumed that for a system with M levels output from the multi-level halftone algorithm 14, one level will be placed at the D.sub.min of the display device and one level will be placed at the D.sub.max. For example, from FIG. 1 the first entry in the printer control table 16 will be zero and the last entry will be 2.sup.K -1. As a result, for a M-level system, there are M minus two entries which must be specified in the printer control table 16. The combination of a multi-level halftone algorithm 14, the printer control table 16, the printer tone transfer curve 28, and a method for calculating large-area densities to achieve the printed output 22 from the large-area average of box 20 defines the density out for each of the N code values input into the N-level display device 10.

For example, it can be assumed that N=13 and M=4, using the low modulation rendering approach of FIG. 4, and that the printer control table 16 is constructed such that the four density levels are evenly distributed from D.sub.min to D.sub.max. Table 1 below, then, lists the entries for the printer control table 16 as well as the associated densities, assuming the printer tone transfer curve 28 of FIG. 2.

Finally, assuming the large-area average box 20 is given by the simplified expression of Equation (2), this leads to the result illustrated in FIG. 6, where the average output density levels are linearly related to the code value, as indicated by curve 38 created by the thirteen graphed halftone levels. This result can be used in conjunction with the target output tone transfer curve 34 illustrated in FIG. 3, to specify an appropriate output calibration table 24 shown by step curve 40 in FIG. 7. This output calibration table 24 as depicted by step curve 40 in FIG. 7, combined with the rest of the specified system, leads to a nominal system tone transfer curve 42 depicted in FIG. 8, with the target system tone transfer curve 34 overlaid for purposes of comparison. The system described herein can produce thirteen unique levels, resulting in the nominal system tone transfer curve 42. The nominal system tone transfer curve 42 depicts the operation of the system 10 with the printer 12 operating at its nominal setting.

When the output calibration table is combined with the rest of the specified system, except that variation extremes 30 and 32 of the printer tone transfer are used instead of the printer tone transfer function indicated by the solid curve 28, which are also listed in Table 1, then the actual system tone transfer curve may be anywhere within the envelope depicted in FIG. 9. Dotted step curves 44 and 46 indicate the actual system tone transfer curves representative of the printer 12 operating at its extremes. The target tone transfer curve 28 is overlaid thereon for purposes of comparison.

In a preferred embodiment of the present invention, it is desired to simultaneously minimize the difference between the target system tone transfer curve 34 and both extremes 44 and 46 of the actual system tone transfer curve. This objective can be embodied in the following objective function of Equation (3), where the objective function to be determined is that function which is to be minimized:

where v.sub.i is the input into the halftone process, T(v.sub.i) is the target system tone transfer 34 of FIG. 3, A.sub.A (v.sub.i) is the actual system tone transfer assuming that the printer 12 is operating at variation extreme 44 of FIG. 9, and A.sub.B (v.sub.i) is the actual system tone transfer assuming that the printer 12 is operating at variation extreme 46 of FIG. 9.

One procedure for defining the function which quantifies undesirable mean level image artifacts for the unstable display device is as follows. First, the output calibration table 24 is specified so that when it is cascaded with the multi-level halftone algorithm 14, the printer control table 16, the multi-level printer 12 operating at its nominal setting, and the large-area average of box 20, there is minimum squared-error between the nominal system tone transfer and the target system tone transfer. Second, the output calibration table 24 as determined in the first step above is cascaded with the multi-level halftone algorithm 14, the printer control table 16, variation extreme 44 of the multi-level printer 12, and the large-area average of box 20, to specify A.sub.A (v.sub.i), the actual system tone transfer when the printer 12 is operating at variation extreme 44. Third, the output calibration table 24 as determined in the first step above is cascaded with the multi-level halftone algorithm 14, the printer control table 16, variation extreme 46 of the multi-level printer 12, and the large-area average of box 20, to specify A.sub.B (v.sub.i), the actual system tone transfer when the printer 12 is operating at variation extreme 46. Finally, the objective specified in Equation (3) is calculated, using the target system tone transfer 34, A.sub.A (v.sub.i), and A.sub.B (v.sub.i).

This particular method for minimizing the objective function is described for purposes of illustration only, and is not to be considered as limiting the scope of the invention. As will be obvious to those skilled in the art, any method for minimizing the objective function is included within the scope of this invention.

The present invention provides for a process of choosing multiple output density levels to be utilized by a multi-level halftoning algorithm in the presence of an unstable output device. The process involves defining a function which quantifies the undesirable image artifacts. The process is carried out by choosing density levels which minimize the function. The result will depend on the specific multi-level halftone algorithm used, the micro and macro characteristics of the display device, and the nature of the display device instability.

Industrial Applicability and Advantages

The present invention is useful in the field of multi-level halftoning and has the advantage of optimizing the performance of an unstable display device. The optimization process involves the selection of output levels for multi-level halftones in the presence of an unstable display device. The process has the advantage of optimizing performance and capabilities of a given multi-level halftone algorithm by specifying the output levels whose instability has a minimal impact on image quality. Consequently, the actual system tone transfer of a printing device is optimally stabilized and matched to a target system tone transfer even though the system contains unstable components. It is a further advantage that this is accomplished without adding additional components to the system or putting additional performance constraints on the unstable components.

Having described the invention in detail and by reference to the preferred embodiment thereof, it will be apparent that other modifications and variations are possible without departing from the scope of the invention defined in the appended claims.