Facsimile and static presentation processing – Static presentation processing – Attribute control
Reexamination Certificate
2003-06-09
2004-10-05
Grant, II, Jerome (Department: 2626)
Facsimile and static presentation processing
Static presentation processing
Attribute control
C358S522000, C358S523000, C358S530000, C382S252000
Reexamination Certificate
active
06801337
ABSTRACT:
BACKGROUND AND SUMMARY OF THE INVENTION
Digital halftoning can be defined as a collection of techniques employed by various computer-controlled display and printing devices for converting continuous-tone images into binary information for displaying the image. The display is comprised of many individual picture elements, known as “pixels.” The computer generates data corresponding to the tone of the pixels to be displayed or printed. Hereafter, this data will be alternatively referred to as input tone values or tone value data.
The conversion and display of the tone value data is often referred to as rendering. As part of the rendering, the tone value data is associated with halftoning cells with which the display area is logically tiled. The pixels of those cells are colored (printed or displayed) in accord with the underlying halftoning technique. The halftoning techniques, or algorithms, can be generally broken-down into two classes.
One class comprises those algorithms that are relatively simple from a computational standpoint, thus providing good rendering speed. Exemplary of this first class of halftoning algorithms are those known as matrix-based, pattern, or ordered-dither algorithms. One of these is named for its originator, B. E. Bayer. (
An Optimum Method for Two
-
Level Rendition of Continuous
-
Tone Pictures, Proc. IEEE Int. Conf. Communication
, pp. 2611-2615, 1973.)
In one version of the Bayer algorithm, an 8×8 matrix of pixels defines the halftoning cell. Each of the 64 pixels in the matrix has associated with it a threshold value. The computer-generated tone value data (for example, levels from 0 to 255 of the colorants, cyan, magenta, and yellow) that correspond to each pixel of the cell are compared with the threshold level of the corresponding position in the matrix. If the tone value of the pixel is greater than the threshold value, an output pixel is produced (as by printing) with the appropriate colorant(s). For convenience, the remainder of this discussion will generally refer to printed output, although it is understood that the particulars of the present invention are applicable to other display devices.
These matrix-based algorithms, such as Bayer's, are computationally fast since they only require a comparison between the tone value and the threshold value. In addition, small matrices, on the order of 8×8 cells, generate output data streams (i.e., output tone values) that are amenable to speed-enhancing data compression inasmuch as the output data stream will contain many repeating bytes.
The advantages attributable to such a small-matrix based algorithm and its attendant repetitive output stream, however, may be overshadowed in certain instances, such as where generally light color tones are to be uniformly applied over a significantly sized area of the printed image. In such instances, the repetitive output data (generated, as it is, from an ordered-dither matrix) and the limited number of printable patterns introduces a noticeable and generally undesirable artifact in the printed image. The artifact is known as patterning.
Another class of halftoning algorithms includes those generally labeled as “error diffusion.” A popular version of an error diffusion halftoning algorithm is known as Floyd-Steinberg error diffusion. (
An Adaptive Algorithm for Spatial Grayscale
, Proc. SID, 17:75-77, 1976). With this technique, the tone value of each pixel is examined (for colored output, the tone values include those of each colorant) and compared to a threshold value provided by the algorithm. If the incoming tone value exceeds the threshold, an output pixel is generated and the difference between the output and input values (error) is diffused among four neighboring pixels. For example, the pixel immediately to the right of the current pixel is assigned {fraction (7/16)} of the error (the error can be positive or negative), the pixel beneath that one is assigned {fraction (1/16)} of the error, the pixel beneath the current pixel is assigned {fraction (5/16)} of the error, and the pixel to the left of that one is assigned {fraction (3/16)} of the error.
To further break-up geometric artifacts or patterns, some noise may be added to the error terms. The averaged value of the noise is 0, however, so that the image is not lightened or darkened as a result.
Error diffusion algorithms can enhance output quality (as compared to matrix-based algorithms) by the elimination of the patterning artifacts mentioned above. This advantage comes at a computational cost, however, that can reduce performance in terms of pixel throughput. Printing speed is reduced. This is particularly true in instances where noise is introduced into the error terms because the already somewhat-random appearing output is, as a result, made even more so, thus making the output data stream unsuitable for compression.
Selection of an algorithm from one or the other of the two groups outlined above, therefore, necessarily requires one to address the trade-off between rendering speed and compressibility (for which matrix-based algorithms are advantageously employed) and output quality (for which error diffusion approaches work best).
In the past, methods incorporated into and carried out by printer drivers or the like have been used for selecting between or otherwise blending algorithms from the two groups identified above. Such approaches, while producing acceptable results, introduce computational complexities of their own, thereby losing some of the performance gains that may otherwise be obtained.
The present invention is directed to a method and apparatus for optimally varying the halftoning algorithms applied to tone values by selecting among combinations of at least two algorithms that best address the tradeoff between output quality and rendering performance.
In a preferred embodiment of the invention, input tone values are scrutinized and matched with an algorithm combination that processes the associated tone values in a manner that increases rendering speed (including the use of data compression) without sacrificing output quality. As explained in detail below, the selection process is computationally simple and fast.
Moreover the process is reliable; providing predetermined combinations of halftoning algorithms that are established as a result of analysis of actual test samples of the printed output.
The somewhat subjective weighting of the speed versus output-quality that comes about when predetermining the algorithm combinations can be readily adjusted or “tuned” to accommodate other weightings. Such tuning does not, however, affect the computational simplicity of the process.
Notwithstanding the simplicity of the algorithm selection process, the overall color tone space can be optimized—with respect to speed and output quality—to within a respectably high resolution.
Other advantages and features of the present invention will become clear upon study of the following portion of this specification and drawings.
REFERENCES:
patent: 4413275 (1983-11-01), Horiuchi et al.
patent: 4500919 (1985-02-01), Schreiber
patent: 4680645 (1987-07-01), Dispoto et al.
patent: 4866514 (1989-09-01), Yeomans
patent: 4974171 (1990-11-01), Yeh et al.
patent: 5031050 (1991-07-01), Chan
patent: 5091734 (1992-02-01), Suzuki et al.
patent: 5131075 (1992-07-01), Wilkes et al.
patent: 5168552 (1992-12-01), Vaughn et al.
patent: 5519791 (1996-05-01), Webb et al.
patent: 5602971 (1997-02-01), Deschuytere
patent: 5731823 (1998-03-01), Miller et al.
patent: 5970178 (1999-10-01), Lin
patent: 5982951 (1999-11-01), Katayama
patent: 6002804 (1999-12-01), Bhaskar
patent: 6040927 (2000-03-01), Winter
patent: 6257693 (2001-07-01), Miller
patent: 6661533 (2003-12-01), Bhaskar
patent: 0 349 234 (1990-01-01), None
patent: 0 390 473 (1990-10-01), None
patent: 0 488 534 (1992-06-01), None
patent: 0 493 085 (1992-07-01), None
EPO/Patent Abstracts of Japan; Osawa Hideshi; Pub. No. 63205238; Aug. 24, 1988; 1 page.
EPO/Patent Abstracts of Japan; Idei Katsuto; Pub. No. 59163945; Sep. 17, 1984; 1 page.
Allen W. J.
Bhaskar Ranjit
Gondek Jay S
Hudson Kevin R.
Grant II Jerome
Hewlett--Packard Development Company, L.P.
LandOfFree
Tone dependent variable halftoning with adjustable algorithm... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Tone dependent variable halftoning with adjustable algorithm..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tone dependent variable halftoning with adjustable algorithm... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3325562