US6020978A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for color halftoning using interlocked threshold arrays
Assignee: Lexmark International Inc
•
Filing: 1997-09-30
•
Granted: 2000-02-01
•
Expires: 2017-09-30
Abstract
Abstract A dispersed-dot stochastic dither array is provided for rendering halftone images having excellent visual quality and are created by a minimum density variance method. By minimizing the variance in the number of dots within each local region of the image, a smooth and dispersed distribution of dots may be obtained. For color printing, a separate threshold array is generated for each of the color planes, however, the stochastic screens are interlocked so that the threshold arrays are generated while considering the other color threshold arrays. In this manner, a blue noise distribution may be produced by the individual arrays as well as by any combination of the individual arrays. When generating a single threshold array for a color plane, a particular criterion is used to determine where the next threshold value should be located, and the selection of a threshold location in each array considers the criterion for all the threshold arrays being generated. This may reduce the quality of an individual array by a small amount, but it allows for the combination of the arrays to have a significantly better distribution. The simplest approach uses the average of the criteria for all threshold arrays, however, to improve the quality of the individual arrays, the preferred method of the present invention uses a weighted average. When selecting a threshold location for an array "i" using weighted averages, the criterion associated with array i may be assigned a greater weight than each of the other individual arrays' criteria. By using the interlocked stochastic screens approach, the overall visual affect will be improved for both individual threshold arrays and for a combination of more than one of the threshold arrays. The interlocked approach is clearly superior for lighter shades, given any number of color planes.
Inventors
- 👤 Brian Edward Cooper
- 👤 Shaun Timothy Love
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 19:25
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/40; H04N1/405; H04N1/4051; H04N1/46; H04N1/52
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
288 words
In a computer system having a processing circuit that operates on data and a memory circuit that stores data, a method for creating a plurality of interlocked threshold arrays for halftoning color images, said method comprising the steps of generating a plurality of single tone levels for a plurality of threshold arrays of color planes by: (a) allocating sufficient memory to hold a plurality of dot profiles, wherein each one of said plurality of dot profiles corresponds to one of a plurality of color planes; (b) repeatedly generating one of said plurality of single tone levels for each one of said plurality of color planes, by: (i) determining a quantity of dots needed for one of said plurality of color planes for the present one of said plurality of single tone levels; (ii) evaluating a numeric decision criterion for a combination of the present one of said plurality of color planes and the present one of said plurality of single tone levels; (iii) combining said numeric decision criteria for all of said plurality of color planes for the present one of said plurality of single tone levels in a manner such that at least one interlocked "newdot" location is determined in each of said plurality of color planes; (iv) placing a numeric value corresponding to the present one of said plurality of single tone levels in at least one interlocked "newdot" location in one of said plurality of threshold arrays that correspond to each of said plurality of color planes; and (c) performing steps (b)(i) through (b)(iv) for each of said plurality of single tone levels until all of said tone levels have been generated, thereby completing all entries in said plurality of threshold arrays of color planes.
Claim 2
Dependent Claim
288 words
In a computer system having a processing circuit that operates on data and a memory circuit that stores data, a method for creating a plurality of interlocked threshold arrays for halftoning color images, said method comprising the steps of generating a plurality of single tone levels for a plurality of threshold arrays of color planes by: (a) allocating sufficient memory to hold a plurality of dot profiles, wherein each one of said plurality of dot profiles corresponds to one of a plurality of color planes; (b) repeatedly generating one of said plurality of single tone levels for each one of said plurality of color planes, by: (i) determining a quantity of dots needed for one of said plurality of color planes for the present one of said plurality of single tone levels; (ii) evaluating a numeric decision criterion for a combination of the present one of said plurality of color planes and the present one of said plurality of single tone levels; (iii) combining said numeric decision criteria for all of said plurality of color planes for the present one of said plurality of single tone levels in a manner such that at least one interlocked "newdot" location is determined in each of said plurality of color planes; (iv) placing a numeric value corresponding to the present one of said plurality of single tone levels in at least one interlocked "newdot" location in one of said plurality of threshold arrays that correspond to each of said plurality of color planes; and (c) performing steps (b)(i) through (b)(iv) for each of said plurality of single tone levels until all of said tone levels have been generated, thereby completing all entries in said plurality of threshold arrays of color planes.
Claim 3
Dependent Claim
23 words
The method as recited in claim 1, wherein each of said plurality of threshold arrays of color planes comprises a stochastic threshold array.
Claim 4
Dependent Claim
124 words
The method as recited in claim 1, wherein the step of determining a quantity of dots needed for one of said plurality of color planes for the present one of said plurality of single tone levels comprises the sub-steps of: selecting a value for each of a plurality of variables named "dotsneeded[i]" per each of said plurality of color planes "[i]"; determining if at least one of said plurality of color planes "[i]" requires one of dots to be added {or dots to be removed}; and, if so, determining the exact quantity of dots to be added to {or removed from} the present one of said plurality of single tone levels and for said at least one of said plurality of color planes "[i]".
Claim 5
Dependent Claim
59 words
The method as recited in claim 1, wherein during the step of evaluating a numeric decision criterion for a combination of the present one of said plurality of color planes and the present one of said plurality of single tone levels, said numeric decision criterion comprises a minimum density variance statistical approach in generating a dispersed-dot stochastic dither array.
Claim 6
Dependent Claim
127 words
The method as recited in claim 1, wherein during the step of combining said numeric decision criteria for all of said plurality of color planes for the present one of said plurality of single tone levels in a manner such that at least one interlocked "newdot" location is determined in each of said plurality of color planes, comprises the sub-steps of: summing the numeric values for the entries of a plurality of intermediate arrays for all of said plurality of color planes after said numeric decision criteria has been applied to the present one of said plurality of color planes and the present one of said plurality of single tone levels, thereby determining at least one minimum array location for placement {or removal} of said interlocked "newdot".
Claim 7
Dependent Claim
23 words
The method as recited in claim 5, wherein said numeric values for each intermediate array entry correspond to a combined density sum array.
Claim 8
Dependent Claim
134 words
The method as recited in claim 5, wherein the sub-step of summing the numeric values for the entries of a plurality of intermediate arrays for all of said plurality of color planes after said numeric decision criteria has been applied to the present one of said plurality of color planes and the present one of said plurality of single tone levels comprises: taking the weighted average of each of said intermediate array entries for all of said plurality of color planes, thereby generating an interlocked array of numeric values that correspond to array locations each having a numeric value assigned that relates to the desirability of adding an interlocked "newdot" to {or removing interlocked "newdot" from} one of said plurality of color planes for the present one of said plurality of single tone levels.
Claim 9
Dependent Claim
47 words
The method as recited in claim 1, wherein for CMYK printing, the color planes that are generated are only for cyan, magenta, and black, and further comprising the step of generating a yellow color plane that is not interlocked with said cyan, magenta, and black color planes.
Claim 10
Dependent Claim
24 words
The method as recited in claim 1, wherein for CMYK printing, the color planes that are generated are for cyan, magenta, yellow, and black.
Claim 11
Dependent Claim
45 words
The method as recited in claim 1, wherein for CMY printing, the color planes that are generated are only for cyan and magenta, and further comprising the step of generating a yellow color plane that is not interlocked with said cyan and magenta color planes.
Claim 12
Dependent Claim
24 words
The method as recited in claim 1, wherein for CMY printing, the color planes that are generated are for cyan and magenta, and yellow.
Claim 13
Dependent Claim
45 words
The method as recited in claim 1, wherein for a variable color print job, a first color mode selects from a plurality of sets of threshold arrays, and a second color mode selects from a different one of said plurality of sets of threshold arrays.
Claim 14
Dependent Claim
30 words
The method as recited in claim 12, wherein said first color mode selects a black-only threshold array, and said second color mode selects a multi-color set of interlocked threshold arrays.
Claim 15
Dependent Claim
303 words
A computer system, comprising: a memory circuit that stores data, and a processing circuit; wherein said processing circuit is configured to create a plurality of interlocked threshold arrays used for halftoning color images, by generating a plurality of single tone levels for a plurality of threshold arrays of color planes, and wherein said processing circuit allocates sufficient space in said memory circuit to hold a plurality of dot profiles, each one of said plurality of dot profiles corresponding to one of a plurality of color planes; (a) said processing circuit being further configured to repeatedly generate one of said plurality of single tone levels for each one of said plurality of color planes, by: (i) determining a quantity of dots needed for one of said plurality of color planes for the present one of said plurality of single tone levels; (ii) evaluating a numeric decision criterion for a combination of the present one of said plurality of color planes and the present one of said plurality of single tone levels; (iii) combining said numeric decision criteria for all of said plurality of color planes for the present one of said plurality of single tone levels in a manner such that at least one interlocked "newdot" location is determined in each of said plurality of color planes; (iv) placing a numeric value corresponding to the present one of said plurality of single tone levels in at least one interlocked "newdot" location in one of said plurality of threshold arrays that correspond to each of said plurality of color planes; and (b) said processing circuit also being configured to implement steps (a)(i) through (a)(iv) for each of said plurality of single tone levels until all of said tone levels have been generated, thereby completing all entries in said plurality of threshold arrays of color planes.
Claim 16
Dependent Claim
303 words
A computer system, comprising: a memory circuit that stores data, and a processing circuit; wherein said processing circuit is configured to create a plurality of interlocked threshold arrays used for halftoning color images, by generating a plurality of single tone levels for a plurality of threshold arrays of color planes, and wherein said processing circuit allocates sufficient space in said memory circuit to hold a plurality of dot profiles, each one of said plurality of dot profiles corresponding to one of a plurality of color planes; (a) said processing circuit being further configured to repeatedly generate one of said plurality of single tone levels for each one of said plurality of color planes, by: (i) determining a quantity of dots needed for one of said plurality of color planes for the present one of said plurality of single tone levels; (ii) evaluating a numeric decision criterion for a combination of the present one of said plurality of color planes and the present one of said plurality of single tone levels; (iii) combining said numeric decision criteria for all of said plurality of color planes for the present one of said plurality of single tone levels in a manner such that at least one interlocked "newdot" location is determined in each of said plurality of color planes; (iv) placing a numeric value corresponding to the present one of said plurality of single tone levels in at least one interlocked "newdot" location in one of said plurality of threshold arrays that correspond to each of said plurality of color planes; and (b) said processing circuit also being configured to implement steps (a)(i) through (a)(iv) for each of said plurality of single tone levels until all of said tone levels have been generated, thereby completing all entries in said plurality of threshold arrays of color planes.
Claim 17
Dependent Claim
24 words
The computer system as recited in claim 14, wherein each of said plurality of threshold arrays of color planes comprises a stochastic threshold array.
Claim 18
Dependent Claim
128 words
The computer system as recited in claim 14, wherein said processing circuit, while determining the quantity of dots needed for one of said plurality of color planes for the present one of said plurality of single tone levels, is still further configured to select a value for each of a plurality of variables named "dotsneeded[i]" per each of said plurality of color planes "[i]"; determine if at least one of said plurality of color planes "[i]" requires one of dots to be added {or dots to be removed}; and, if so, then determine the exact quantity of dots to be added to {or removed from} the present one of said plurality of single tone levels and for said at least one of said plurality of color planes "[i]".
Claim 19
Dependent Claim
66 words
The computer system as recited in claim 14, wherein said processing circuit, while evaluating the numeric decision criterion for a combination of the present one of said plurality of color planes and the present one of said plurality of single tone levels, is still further configured to use, for said numeric decision criterion, a minimum density variance statistical approach in generating a dispersed-dot stochastic dither array.
Claim 20
Dependent Claim
129 words
The computer system as recited in claim 14, wherein said processing circuit, while combining said numeric decision criteria for all of said plurality of color planes for the present one of said plurality of single tone levels in a manner such that at least one interlocked "newdot" location is determined in each of said plurality of color planes, is still further configured to: sum the numeric values for the entries of a plurality of intermediate arrays for all of said plurality of color planes after said numeric decision criteria has been applied to the present one of said plurality of color planes and the present one of said plurality of single tone levels, thereby determining at least one minimum array location for placement {or removal} of said interlocked "newdot".
Claim 21
Dependent Claim
24 words
The computer system as recited in claim 18, wherein said numeric values for each intermediate array entry correspond to a combined density sum array.
Claim 22
Dependent Claim
140 words
The computer system as recited in claim 18, wherein said processing circuit, while summing the numeric values for the entries of a plurality of intermediate arrays for all of said plurality of color planes after said numeric decision criteria has been applied to the present one of said plurality of color planes and the present one of said plurality of single tone levels, is still further configured to: take the weighted average of each of said intermediate array entries for all of said plurality of color planes, thereby generating an interlocked array of numeric values that correspond to array locations each having a numeric value assigned that relates to the desirability of adding an interlocked "newdot" to or removing interlocked "newdot" from one of said plurality of color planes for the present one of said plurality of single tone levels.
Claim 23
Dependent Claim
52 words
The computer system as recited in claim 14, wherein for CMYK printing, the color planes that are generated are only for cyan, magenta, and black, and wherein said processing circuit is still further configured to generate a yellow color plane that is not interlocked with said cyan, magenta, and black color planes.
Claim 24
Dependent Claim
25 words
The computer system as recited in claim 14, wherein for CMYK printing, the color planes that are generated are for cyan, magenta, yellow, and black.
Claim 25
Dependent Claim
50 words
The computer system as recited in claim 14, wherein for CMY printing, the color planes that are generated are only for cyan and magenta, and wherein said processing circuit is still further configured to generate a yellow color plane that is not interlocked with said cyan and magenta color planes.
Claim 26
Dependent Claim
25 words
The computer system as recited in claim 14, wherein for CMY printing, the color planes that are generated are for cyan and magenta, and yellow.
Claim 27
Dependent Claim
46 words
The computer system as recited in claim 14, wherein for a variable color print job, a first color mode selects from a plurality of sets of threshold arrays, and a second color mode selects from a different one of said plurality of sets of threshold arrays.
Claim 28
Dependent Claim
31 words
The computer system as recited in claim 25, wherein said first color mode selects a black-only threshold array, and said second color mode selects a multi-color set of interlocked threshold arrays.
References Cited (Backward Citations)
US5214517A
Cited
US5111310A
Cited
US5317418A
Cited
US5745660A
Cited
US5696612A
Cited
US5812744A
Cited
US5673121A
Cited
US5787238A
Cited
US5859955A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-01-31 | 2003-08-02 | 2004-02-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-01-31 | 2007-08-02 | 2008-02-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-01-31 | 2011-08-02 | 2012-02-01 | $7700.00 | Window Closed / Lapsed |