Patent US5208658A successfully refreshed from Google Patents.
Patent US5798764A successfully refreshed from Google Patents.
Patent US5405476A successfully refreshed from Google Patents.
Patent US6563957B1 successfully refreshed from Google Patents.
US6563957B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Tone dependent error diffusion
Assignee: Hewlett Packard Development Co LP
•
Filing: 1999-05-07
•
Granted: 2003-05-13
•
Expires: 2019-05-07
Abstract
Abstract A tone dependent error diffusion halftoning system uses tone dependent thresholds and error weightings that are optimized by minimizing a model based cost function. An upper and lower threshold are used to compare with the modified pixel value. If the modified pixel value is greater than the upper threshold, a dot is printed, if less than the lower threshold, no dot is printed, and if between, a binary bitmap is used to determine whether a dot should be printed. For each midtone threshold level, a halftone image is generated by a direct binary search method and an error diffusion method. The magnitudes of the fast Fourier transforms, of the halftone images are compared using a visual cost function and the thresholds and error weightings are altered to minimize the cost function. For highlight and shadow tone levels, a filtered halftone image from an error diffusion system is compared to the continuous tone image after filtering the image via a human visual system model. Again by minimizing the cost function, the thresholds and error weightings are optimized.
Inventors
- 👤 Pingshan Li
- 👤 Jan P. Allebach
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 14:00
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/40; H04N1/405; H04N1/4051; H04N1/4052
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
64 words
A method of tone dependent error diffusion halftoning, the method comprising: performing error diffusion with at least one threshold value and a plurality of error weightings; and obtaining said at least one threshold value and said plurality of error weightings based on an input pixel value, wherein the at least one threshold value and plurality of error weightings are determined using a cost function.
Claim 2
Independent Claim
64 words
A method of tone dependent error diffusion halftoning, the method comprising: performing error diffusion with at least one threshold value and a plurality of error weightings; and obtaining said at least one threshold value and said plurality of error weightings based on an input pixel value, wherein the at least one threshold value and plurality of error weightings are determined using a cost function.
Claim 3
Dependent Claim
89 words
The method of claim 1 , the method further comprising: inputting an input pixel value; generating a modified pixel value based on the input pixel value and diffused quantizer errors from previously processed pixels; comparing the at least one threshold value with the modified pixel value to generate a binary output pixel value; generating a quantizer error based on the difference between the binary output pixel value and the modified pixel value; and diffusing the quantizer error with the plurality of error weightings to pixels to be subsequently processed.
Claim 4
Dependent Claim
64 words
The method of claim 2 , wherein obtaining at least one threshold value comprises obtaining an upper threshold value and a lower threshold value, comparing the at least one threshold value with the modified pixel value comprises comparing the upper threshold value with the modified pixel value and comparing the lower threshold value with the modified pixel value to generate the binary output pixel.
Claim 5
Dependent Claim
63 words
The method of claim 3 , wherein if the modified pixel value is between the upper threshold value and the lower threshold value, the method further comprises: providing a binary bitmap pattern having an approximately midtone level; and using the pixel value of the binary bitmap pattern that is in the same coordinates of the input pixel to generate the binary output pixel.
Claim 6
Dependent Claim
62 words
The method of claim 3 , wherein if the modified pixel value is between the upper threshold value and the lower threshold value, the method further comprises: providing a screen pattern having a matrix of threshold values; and using the threshold value of the screen pattern that is in the same coordinates of the input pixel to generate the binary output pixel.
Claim 7
Dependent Claim
27 words
The method of claim 2 , further comprising diffusing the entire quantizer error in an approximately vertical direction when halftoning a region with absorptance 0 or 1.
Claim 8
Dependent Claim
30 words
The method of claim 2 , wherein the method further comprises: diffusing the entire quantizer error in a diagonal direction when halftoning a region with absorptance of 0 or 1.
Claim 9
Dependent Claim
101 words
The method of claim 2 , wherein the method further comprises: diffusing the quantizer error with the plurality of error weightings to pixels to be subsequently processed over a first area when the input pixel value is at a highlight or shadow tone level, wherein less then all the pixels in the first area receive a portion of the quantizer error; diffusing the quantizer error with the plurality of error weightings to pixels to be subsequently processed over a second area when the input pixel value is at a midtone level; wherein the first area is larger than the second area.
Claim 10
Dependent Claim
83 words
The method of claim 8 , further comprising: diffusing the quantizer error with the plurality of error weightings to pixels to be subsequently processed over a third area when the input pixel value is at a transition level between the highlight and midtone levels and the shadow and midtone levels, wherein less then all the pixels in the third area receive a portion of the quantizer error; wherein the third area is larger than the second area and smaller than the first area.
Claim 11
Dependent Claim
87 words
The method of claim 1 , wherein at least one threshold value and the plurality of error weightings are optimized comprises: providing a patch having a tone level; generating a first halftone pattern of the patch by direct binary search halftoning; generating a second halftone pattern of the patch by error diffusion halftoning using an initial threshold value and initial error weightings; comparing the first halftone pattern with the second halftone pattern; altering the initial threshold value and initial error weightings to minimize a first cost function.
Claim 12
Dependent Claim
76 words
The method of claim 10 , wherein the first cost function is: ɛ = ∑ u ∑ v [ G TDED ( u , v ) - G DBS ( u , v ) ] 2 where G DBS (u,v) denotes the expectation magnitude of the fast Fourier transform of the first halftone pattern and G TDED (u,v) denotes the expectation magnitude of the fast Fourier transform of the second halftone pattern.
Claim 13
Dependent Claim
106 words
The method of claim 1 , wherein at least one threshold value and the plurality of error weightings are optimized comprises: providing a patch having a tone level; filtering the patch using a human visual system model to generate a first filtered image; generating a first halftone pattern of the patch by error diffusion halftoning using an initial threshold value and initial error weightings; filtering the first halftone pattern using a human visual system model to generate a second filtered image; comparing the first filtered image with the second filtered image; altering the initial threshold value and initial error weightings to minimize a first cost function.
Claim 14
Dependent Claim
17 words
The method of claim 12 , wherein the first cost function is the total perceived squared error.
Claim 15
Dependent Claim
179 words
The method of claim 13 , further comprising: providing a second patch having a tone level; generating a second halftone pattern of the second patch by direct binary search halftoning; generating a third halftone pattern of the second by error diffusion halftoning using an initial threshold value and initial error weightings; comparing the second halftone pattern with the third halftone pattern; altering the initial threshold value and initial error weightings to minimize a second cost function that is ɛ = ∑ u ∑ v [ G TDED ( u , v ) - G DBS ( u , v ) ] 2 where G DBS (u,v) denotes the expectation magnitude of the fast Fourier transform of the second halftone pattern and G TDED (u,v) denotes the expectation magnitude of the fast Fourier transform of the third halftone pattern; wherein the first cost function is used for tone levels at the extreme ends of a tone level range and the second cost function is used for tone levels at the midtones of the tone level range.
Claim 16
Dependent Claim
36 words
The method of claim 1 , further comprising preventing start-up artifacts by adding a random variable to the modification term, wherein the modification term is the sum of the diffused quantizer errors from previously processed pixels.
Claim 17
Independent Claim
143 words
A method of optimizing the tone dependent thresholds and error weightings for a tone dependent error diffusion halftoning system, the method comprising: (a) providing a patch having a first tone level; (b) generating a first halftone pattern of the patch by direct binary search halftoning; (c) generating a second halftone pattern of the patch by error diffusion halftoning using an initial threshold value and initial error weightings; (d) comparing the first halftone pattern with the second halftone pattern; (e) altering the initial threshold value and initial error weightings to minimize a cost function; (f) repeating (b) through (e) until the cost function can no longer be minimized, wherein the initial threshold values and initial error weightings are the threshold values and error weightings that minimize the cost function; (g) providing a second patch having a second tone level and repeating (b) through (f).
Claim 18
Independent Claim
143 words
A method of optimizing the tone dependent thresholds and error weightings for a tone dependent error diffusion halftoning system, the method comprising: (a) providing a patch having a first tone level; (b) generating a first halftone pattern of the patch by direct binary search halftoning; (c) generating a second halftone pattern of the patch by error diffusion halftoning using an initial threshold value and initial error weightings; (d) comparing the first halftone pattern with the second halftone pattern; (e) altering the initial threshold value and initial error weightings to minimize a cost function; (f) repeating (b) through (e) until the cost function can no longer be minimized, wherein the initial threshold values and initial error weightings are the threshold values and error weightings that minimize the cost function; (g) providing a second patch having a second tone level and repeating (b) through (f).
Claim 19
Dependent Claim
75 words
The method of claim 16 , wherein the cost function is: ɛ = ∑ u ∑ v [ G TDED ( u , v ) - G DBS ( u , v ) ] 2 where G DBS (u,v) denotes the expectation magnitude of the fast Fourier transform of the first halftone pattern and G TDED (u,v) denotes the expectation magnitude of the fast Fourier transform of the second halftone pattern.
Claim 20
Dependent Claim
119 words
The method of claim 16 , further comprising repeating (a) through (g) until at least a portion of a midtone range is optimized, the method further comprising: providing a third patch having a tone level outside the midtone range; filtering the third patch using a human visual system model to generate a first filtered image; generating a second halftone pattern of the third patch by error diffusion halftoning using an initial threshold value and initial error weightings; filtering the second halftone pattern using a human visual system model to generate a second filtered image; comparing the first filtered image with the second filtered image; altering the initial threshold value and initial error weightings to minimize a second cost function.
Claim 21
Dependent Claim
19 words
The method of claim 18 , wherein the second cost function is the total perceived root mean square error.
Claim 22
Independent Claim
307 words
A method of tone dependent error diffusion halftoning, the method comprising: comparing an input pixel value with a threshold to determine if a dot should be printed; generating a quantizer error based at least on whether it was determined if a dot should be printed; obtaining a plurality of error weightings based on the input pixel value; diffusing the quantizer error with the plurality of error weightings to pixels to be subsequently processed over a first area when the input pixel value is in one of a first region and second region of tone values, wherein less than all the pixels in the first area receive a portion of the quantizer error; and diffusing the quantizer error with the plurality of error weightings to pixels to be subsequently processed over a second area when the input pixel value is in a third region of tone values, wherein the third region of tone values is greater than the first region of tone values and less than the second region of tone values and wherein the first area is larger than the second area; diffusing the quantizer error with the plurality of error weightings to pixels to be subsequently processed over a third area when the input pixel value is in one of a fourth region of tone values and a fifth region of tone values, wherein less than all the pixels in the third area receive a portion of the quantizer error, the fourth region of tone values is greater than the first region of tone values and less than the third region of tone values and the fifth region of tone values is greater than the third region of tone values and less than the second region of tone values, and wherein the third area is larger than the second area and smaller than the first area.
Claim 23
Independent Claim
307 words
A method of tone dependent error diffusion halftoning, the method comprising: comparing an input pixel value with a threshold to determine if a dot should be printed; generating a quantizer error based at least on whether it was determined if a dot should be printed; obtaining a plurality of error weightings based on the input pixel value; diffusing the quantizer error with the plurality of error weightings to pixels to be subsequently processed over a first area when the input pixel value is in one of a first region and second region of tone values, wherein less than all the pixels in the first area receive a portion of the quantizer error; and diffusing the quantizer error with the plurality of error weightings to pixels to be subsequently processed over a second area when the input pixel value is in a third region of tone values, wherein the third region of tone values is greater than the first region of tone values and less than the second region of tone values and wherein the first area is larger than the second area; diffusing the quantizer error with the plurality of error weightings to pixels to be subsequently processed over a third area when the input pixel value is in one of a fourth region of tone values and a fifth region of tone values, wherein less than all the pixels in the third area receive a portion of the quantizer error, the fourth region of tone values is greater than the first region of tone values and less than the third region of tone values and the fifth region of tone values is greater than the third region of tone values and less than the second region of tone values, and wherein the third area is larger than the second area and smaller than the first area.
Claim 24
Dependent Claim
67 words
A printing system including a printer and a computer, the printing system printing a halftoned image, the method performed by the printing system comprising: performing tone dependent error diffusion halftoning with at least one threshold value and a plurality of error weightings determined by an input pixel value, wherein the at least one threshold value and plurality of error weightings are determined based on a cost function.
Claim 25
Dependent Claim
67 words
A printing system including a printer and a computer, the printing system printing a halftoned image, the method performed by the printing system comprising: performing tone dependent error diffusion halftoning with at least one threshold value and a plurality of error weightings determined by an input pixel value, wherein the at least one threshold value and plurality of error weightings are determined based on a cost function.
Claim 26
Dependent Claim
13 words
The system of claim 21 , wherein the printer is an inkjet printer.
Claim 27
Dependent Claim
21 words
The system of claim 22 , wherein the inkjet printer comprises at least one inkjet print cartridge which prints black ink.
References Cited (Backward Citations)
US4876610A
Cited
EP0544511A2
Cited
US5313287A
Cited
US5696846A
Cited
US6144775A
Cited
US5757976A
Cited
US5737453A
Cited
US6172768B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-05-12 | 2006-11-11 | 2007-05-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-05-12 | 2010-11-11 | 2011-05-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-05-12 | 2014-11-11 | 2015-05-13 | $7700.00 | Window Closed / Lapsed |