US5633729A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Processes for minimizing the quantization error in multi-level halftone transfer functions
Assignee: Eastman Kodak Co
•
Filing: 1994-12-22
•
Granted: 1997-05-27
•
Expires: 2014-12-22
Abstract
Abstract Improved processes for quantizing a set of mean-preserving Tone Transfer Functions (TTFs) for a multi-level halftoning system which minimize or at least significantly reduce the overall quantization error in the system as a function of a prespecified system halftone cell size, P, and the number of micro output levels, L y , supported by the multi-level halftoning system. The processes call for dividing the range of possible input contone representative intensity values into T subintervals, where T=PL y ; determining the values of the centers of the T-subintervals; and quantizing each of the normalized continuous mean preserving TTFs as a function of the values of the centers of the T-subintervals. According to a preferred embodiment, the quantizing is performed such that the quantized TTFs approximate the normalized continuous mean preserving TTFs and ideally satisfy the criteria that the maximum quantization error between any quantized and unquantized TTF is minimized. Further aspects of the invention are directed to methods for determining threshold levels for assignment to threshold matrices, and methods for specifying look-up tables, either of which (the matrices and look-up tables) may be used for converting input contone representative intensity values into a predetermined number of available micro output levels for a multilevel halftone system having a predetermined halftone cell size.
Inventors
- 👤 Craig M. Smith
- 👤 Rodney L. Miller
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 18:18
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/40; H04N1/40087
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
115 words
A method for quantizing a given set of P normalized continuous mean preserving Tone Transfer Functions (TTFs), v i with 1<=i<=P, for a multilevel halftone system having a predetermined halftone cell size of P, for converting each member, x, of a set of input contone representative intensity values into a predetermined number of available micro output levels, L y +1, comprising the steps of: (a) dividing the range of possible input contone representative intensity values into T subintervals where T=PL y ; (b) determining the values of the centers of the T-subintervals; and (c) quantizing each of said normalized continuous mean preserving TTFs as a function of the values of the centers of the T-subintervals.
Claim 2
Independent Claim
115 words
A method for quantizing a given set of P normalized continuous mean preserving Tone Transfer Functions (TTFs), v i with 1<=i<=P, for a multilevel halftone system having a predetermined halftone cell size of P, for converting each member, x, of a set of input contone representative intensity values into a predetermined number of available micro output levels, L y +1, comprising the steps of: (a) dividing the range of possible input contone representative intensity values into T subintervals where T=PL y ; (b) determining the values of the centers of the T-subintervals; and (c) quantizing each of said normalized continuous mean preserving TTFs as a function of the values of the centers of the T-subintervals.
Claim 3
Dependent Claim
27 words
A method as set forth in claim 1 wherein said step of quantizing is performed such that the quantized TTFs approximate said normalized continuous mean preserving TTFs.
Claim 4
Dependent Claim
35 words
A method as set forth in claim 2 wherein said step of quantizing satisfies the criteria that the maximum quantization error between any quantized and unquantized TTF is minimized thereby minimizing total system quantization error.
Claim 5
Dependent Claim
116 words
A method as set forth in claim 2 wherein said step of quantizing further comprises the steps of: (a) uniformly quantizing each of said given P normalized continuous mean preserving TTFs independently to obtain a first set of quantization boundaries; (b) sorting said first set of quantization boundaries in numerical order; (c) subsorting said first set of quantization boundaries in numerical order by TTF index i, whenever at least two of said resulting boundaries in said first set of quantization boundaries have the same value; and (d) replacing at least one member of the resulting set of sorted boundary values with at least one member of the set of values of the centers of said T-subintervals.
Claim 6
Dependent Claim
30 words
A method as set forth in claim 2 wherein said step of quantizing further comprises the step of sequentially approximating at each quantization boundary the normalized continuous mean preserving TTFs.
Claim 7
Dependent Claim
114 words
A method as set forth in claim 5 wherein said step of sequentially approximating further comprises the steps of: (a) sorting the values of the centers of said T-subintervals to create a list of T-subintervals centers in ascending order; (b) calculating, at the first T-subinterval center in said sorted set of values, the difference between each normalized continuous mean preserving Tone Transfer Function and its quantized value at said first T-subinterval center; (c) increasing the value of the quantized TTF, having the greatest difference as determined in step (b), by one modulation level; and (d) repeating steps (b) and (c) at the next T-subinterval center in said list for all entries in said list.
Claim 8
Independent Claim
92 words
A method for determining threshold levels for assignment to a set of threshold matrices used for converting each member, x, of a set of input contone representative intensity values into a predetermined number of available micro output levels, L y +1, for a multi-level halftone system having a predetermined halftone cell size of P, comprising the steps of: (a) dividing the range of possible input contone representative intensity values into T subintervals where T=PL y ; and (b) setting said threshold values to be the values of the centers of the T-subintervals.
Claim 9
Independent Claim
92 words
A method for determining threshold levels for assignment to a set of threshold matrices used for converting each member, x, of a set of input contone representative intensity values into a predetermined number of available micro output levels, L y +1, for a multi-level halftone system having a predetermined halftone cell size of P, comprising the steps of: (a) dividing the range of possible input contone representative intensity values into T subintervals where T=PL y ; and (b) setting said threshold values to be the values of the centers of the T-subintervals.
Claim 10
Independent Claim
157 words
A method for determining threshold levels for assignment to a set of threshold matrices used for converting each member, x, of a set of input contone representative intensity values into a predetermined number of available micro output levels, L y +1, for a multi-level halftone system having a predetermined halftone cell size of P, wherein said multilevel halftone system is defined by a given set of P normalized continuous mean preserving Tone Transfer Functions (TTFs), v i with 1<=i<=P, comprising the steps of: (a) dividing the range of possible input contone representative intensity values into T subintervals where T=PL y ; (b) setting said threshold values to be the values of the centers of the T-subintervals; and (c) assigning the values determined in step (b) to each threshold matrix in said set of threshold matrices so that the resulting set of matrices represent quantized TTFs which approximate the given set of P normalized continuous mean preserving TTFs.
Claim 11
Independent Claim
157 words
A method for determining threshold levels for assignment to a set of threshold matrices used for converting each member, x, of a set of input contone representative intensity values into a predetermined number of available micro output levels, L y +1, for a multi-level halftone system having a predetermined halftone cell size of P, wherein said multilevel halftone system is defined by a given set of P normalized continuous mean preserving Tone Transfer Functions (TTFs), v i with 1<=i<=P, comprising the steps of: (a) dividing the range of possible input contone representative intensity values into T subintervals where T=PL y ; (b) setting said threshold values to be the values of the centers of the T-subintervals; and (c) assigning the values determined in step (b) to each threshold matrix in said set of threshold matrices so that the resulting set of matrices represent quantized TTFs which approximate the given set of P normalized continuous mean preserving TTFs.
Claim 12
Dependent Claim
46 words
A method as set forth in claim 8 wherein said quantized TTFs which approximate the given set of P normalized continuous mean preserving TTFs satisfies the criteria that the maximum quantization error between any quantized and unquantized TTF is minimized thereby minimizing total system quantization error.
Claim 13
Dependent Claim
124 words
A method as set forth in claim 8 wherein said quantized TTFs which approximate the given set of P normalized continuous mean preserving TTFs are determined by a process comprising the steps of: (a) uniformly quantizing each of said given P normalized continuous mean preserving TTFs independently to obtain a first set of threshold values; (b) sorting said first set of threshold values in numerical order; (c) subsorting said first set of threshold values in numerical order by TTF index i, whenever at least two of said resulting thresholds in said first set of threshold values have the same value; and (d) replacing at least one member of the resulting set of sorted threshold values with the values of the centers of said T-subintervals.
Claim 14
Dependent Claim
39 words
A method as set forth in claim 8 wherein said quantized TTFs which approximate the given set of P normalized continuous mean preserving TTFs are determined by sequentially approximating at each threshold value the normalized continuous mean preserving TTFs.
Claim 15
Independent Claim
150 words
A method for determining look-up table values for assignment to a set of look-up tables used for converting each member, x, of a set of input contone representative intensity values into a predetermined number of available micro output levels, L y +1, for a multi-level halftone system having a predetermined halftone cell size of P, wherein said multilevel halftone system is defined by a given set of P normalized continuous mean preserving Tone Transfer Functions (TTFS), v i with 1<=i<=P, comprising the steps of: (a) dividing the range of possible input contone representative intensity values into T subintervals where T=PL y ; (b) determining the values of the centers of the T-subintervals; (c) quantizing each of said normalized continuous mean preserving TTFs as a function of the values of the centers of the T-subintervals; and (d) assigning the quantized TTFs determined in step (c) to said set of look-up tables.
Claim 16
Independent Claim
150 words
A method for determining look-up table values for assignment to a set of look-up tables used for converting each member, x, of a set of input contone representative intensity values into a predetermined number of available micro output levels, L y +1, for a multi-level halftone system having a predetermined halftone cell size of P, wherein said multilevel halftone system is defined by a given set of P normalized continuous mean preserving Tone Transfer Functions (TTFS), v i with 1<=i<=P, comprising the steps of: (a) dividing the range of possible input contone representative intensity values into T subintervals where T=PL y ; (b) determining the values of the centers of the T-subintervals; (c) quantizing each of said normalized continuous mean preserving TTFs as a function of the values of the centers of the T-subintervals; and (d) assigning the quantized TTFs determined in step (c) to said set of look-up tables.
Claim 17
Dependent Claim
27 words
A method as set forth in claim 12 wherein said step of quantizing is performed such that the quantized TTFs approximate said normalized continuous mean preserving TTFs.
Claim 18
Dependent Claim
46 words
A method as set forth in claim 13 wherein said quantized TTFs which approximate the given set of P normalized continuous mean preserving TTFs satisfies the criteria that the maximum quantization error between any quantized and unquantized TTF is minimized thereby minimizing total system quantization error.
Claim 19
Dependent Claim
131 words
A method as set forth in claim 13 wherein said quantized TTFs which approximate the given set of P normalized continuous mean preserving TTFs are determined by a process comprising the steps of: (a) uniformly quantizing each of said given P normalized continuous mean preserving TTFs independently to obtain a first set of boundary values; (b) sorting said first set of boundary values in numerical order; (c) subsorting said first set of boundary values in numerical order by TTF index i, whenever at least two of said resulting boundary values in said first set of quantization boundary values are equal; and (d) replacing at least one member of the resulting set of sorted boundary values with at least one member of the set of values of the centers of said T-subintervals.
Claim 20
Dependent Claim
39 words
A method as set forth in claim 13 wherein said quantized TTFs which approximate the given set of P normalized continuous mean preserving TTFs are determined by sequentially approximating at each boundary value the normalized continuous mean preserving TTFs.
Claim 21
Independent Claim
106 words
A method for quantizing a given set of P normalized continuous mean preserving Tone Transfer Functions (TTFs), v i with 1<=i<=P, for a multi-level halftone system having a predetermined halftone cell size of P, for converting each member, x, of a set of input contone representative intensity values into a predetermined number of available micro output levels, L y +1, comprising the steps of: (a) dividing the range of possible input contone representative intensity values into T regularly spaced subintervals where T=PL y ; and (b) quantizing each of said normalized continuous mean preserving TTFs at regular intervals as a function of said regularly space T-subintervals.
Claim 22
Independent Claim
106 words
A method for quantizing a given set of P normalized continuous mean preserving Tone Transfer Functions (TTFs), v i with 1<=i<=P, for a multi-level halftone system having a predetermined halftone cell size of P, for converting each member, x, of a set of input contone representative intensity values into a predetermined number of available micro output levels, L y +1, comprising the steps of: (a) dividing the range of possible input contone representative intensity values into T regularly spaced subintervals where T=PL y ; and (b) quantizing each of said normalized continuous mean preserving TTFs at regular intervals as a function of said regularly space T-subintervals.
Claim 23
Independent Claim
95 words
A method for determining threshold levels for assignment to a set of threshold matrices used for converting each member, x, of a set of input contone representative intensity values into a predetermined number of available micro output levels, L y +1, for a multilevel halftone system having a predetermined halftone cell size of P, comprising the steps of: (a) dividing the range of possible input contone representative intensity values into T regularly spaced subintervals where T=PL y ; and (b) setting said threshold values at regular intervals as a function of said regularly spaced T-subintervals.
Claim 24
Independent Claim
95 words
A method for determining threshold levels for assignment to a set of threshold matrices used for converting each member, x, of a set of input contone representative intensity values into a predetermined number of available micro output levels, L y +1, for a multilevel halftone system having a predetermined halftone cell size of P, comprising the steps of: (a) dividing the range of possible input contone representative intensity values into T regularly spaced subintervals where T=PL y ; and (b) setting said threshold values at regular intervals as a function of said regularly spaced T-subintervals.
Claim 25
Independent Claim
160 words
A method for determining threshold levels for assignment to a set of threshold matrices used for converting each member, x, of a set of input contone representative intensity values into a predetermined number of available micro output levels, L y +1, for a multilevel halftone system having a predetermined halftone cell size of P, wherein said multilevel halftone system is defined by a given set of P normalized continuous mean preserving Tone Transfer Functions (TTFs), v i with 1<=i<=P, comprising the steps of: (a) dividing the range of possible input contone representative intensity values into T regularly spaced subintervals where T=PL y ; (b) setting said threshold values at regular intervals as a function of said regularly spaced T-subintervals; and (c) assigning the values determined in step (b) to each threshold matrix in said set of threshold matrices so that the resulting set of matrices represent quantized TTFs which approximate the given set of P normalized continuous mean preserving TTFs.
Claim 26
Independent Claim
160 words
A method for determining threshold levels for assignment to a set of threshold matrices used for converting each member, x, of a set of input contone representative intensity values into a predetermined number of available micro output levels, L y +1, for a multilevel halftone system having a predetermined halftone cell size of P, wherein said multilevel halftone system is defined by a given set of P normalized continuous mean preserving Tone Transfer Functions (TTFs), v i with 1<=i<=P, comprising the steps of: (a) dividing the range of possible input contone representative intensity values into T regularly spaced subintervals where T=PL y ; (b) setting said threshold values at regular intervals as a function of said regularly spaced T-subintervals; and (c) assigning the values determined in step (b) to each threshold matrix in said set of threshold matrices so that the resulting set of matrices represent quantized TTFs which approximate the given set of P normalized continuous mean preserving TTFs.
Claim 27
Independent Claim
153 words
A method for determining look-up table values for assignment to a set of look-up tables used for converting each member, x, of a set of input contone representative intensity values into a predetermined number of available micro output levels, L y +1, for a multilevel halftone system having a predetermined halftone cell size of P, wherein said multilevel halftone system is defined by a given set of P normalized continuous mean preserving Tone Transfer Functions (TTFs), v i with 1<=i<=P, comprising the steps of: (a) dividing the range of possible input contone representative intensity values into T subintervals where T=PL y ; (b) setting said threshold values at regular intervals as a function of said regularly spaced T-subintervals; and (c) quantizing each of said normalized continuous mean preserving TTFs as a function of said regularly space T-subintervals; and (d) assigning the quantized TTFs determined in step (c) to said set of look-up tables.
Claim 28
Independent Claim
153 words
A method for determining look-up table values for assignment to a set of look-up tables used for converting each member, x, of a set of input contone representative intensity values into a predetermined number of available micro output levels, L y +1, for a multilevel halftone system having a predetermined halftone cell size of P, wherein said multilevel halftone system is defined by a given set of P normalized continuous mean preserving Tone Transfer Functions (TTFs), v i with 1<=i<=P, comprising the steps of: (a) dividing the range of possible input contone representative intensity values into T subintervals where T=PL y ; (b) setting said threshold values at regular intervals as a function of said regularly spaced T-subintervals; and (c) quantizing each of said normalized continuous mean preserving TTFs as a function of said regularly space T-subintervals; and (d) assigning the quantized TTFs determined in step (c) to said set of look-up tables.
References Cited (Backward Citations)
US3953668A
Cited
JPS59161183A
Cited
JPS6026966A
Cited
JPS60145767A
Cited
JPS6115466A
Cited
US4736254A
Cited
JPS62289054A
Cited
US4876611A
Cited
JPS63157558A
Cited
US4955065A
Cited
US4939589A
Cited
US5014138A
Cited
JPS63316974A
Cited
US4910603A
Cited
US4953013A
Cited
US4992955A
Cited
JPH01155771A
Cited
US5023729A
Cited
US5014333A
Cited
US4956638A
Cited
US4920501A
Cited
US5051844A
Cited
US4912562A
Cited
US4891714A
Cited
US5031051A
Cited
US5053866A
Cited
US4951159A
Cited
US5027078A
Cited
US5070413A
Cited
US5041920A
Cited
US5050000A
Cited
US5172267A
Cited
US5333069A
Cited
US5321427A
Cited
US5291311A
Cited
US5444551A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-05-26 | 2000-11-25 | 2001-05-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-05-26 | 2004-11-25 | 2005-05-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-05-26 | 2008-11-25 | 2009-05-27 | $7700.00 | Window Closed / Lapsed |