Patent US5696601A successfully refreshed from Google Patents.
US5696601A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for redistributing error values from an error diffusion process
Assignee: Xerox Corp
•
Filing: 1994-08-03
•
Granted: 1997-12-09
•
Expires: 2014-08-03
Abstract
Abstract A method and system implements a redistributive characteristic into an error diffusion process. A grey level value representing a pixel is received. A threshold circuit thresholds the received grey level value and generates an error value as a result of the threshold. A portion of the error value is diffused to adjacent pixels on a next scanline. All the error for a single pixel on the next scanline is accumulated. Since this accumulated error has a greater number of bits than can be stored in a buffer, a portion of the accumulated error is truncated and redistributed to a down stream pixel for inclusion in the downstream pixel's error accumulation process. The grey level value has a first resolution which corresponds to an original input resolution. In a high addressabilty environment, the received grey level value is interpolated to subpixel grey level values before thresholding.
Inventors
- 👤 David J. Metcalfe
- 👤 Jeng-Nan Shiau
- 👤 Leon C. Williams
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 12:37
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/40; H04N1/405; H04N1/4051; H04N1/4052
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
175 words
A method of diffusing an error created by a grey level reduction process, comprising the steps of: (a) processing an image signal corresponding to a pixel on a scanline having a predetermined number of grey levels to reduce the predetermined number of grey levels to a number of grey levels renderable by an output system; (b) generating an error from the processing in said step (a); (c) distributing a portion of the error to predetermined pixels on a next scanline, the predetermined pixels on the next scanline receiving a portion of the error portion based on predetermined weighting coefficients; (d) adding together all error portions distributed to a first pixel on the next scanline to produce an error sum for the first pixel; (e) performing a truncation process upon the error sum for the first pixel to generate a truncated error sum value and a remaining error portion value; and (f) distributing the truncated error sum value to a second pixel, the second pixel being adjacent to the first pixel in a fast scan direction.
Claim 2
Independent Claim
175 words
A method of diffusing an error created by a grey level reduction process, comprising the steps of: (a) processing an image signal corresponding to a pixel on a scanline having a predetermined number of grey levels to reduce the predetermined number of grey levels to a number of grey levels renderable by an output system; (b) generating an error from the processing in said step (a); (c) distributing a portion of the error to predetermined pixels on a next scanline, the predetermined pixels on the next scanline receiving a portion of the error portion based on predetermined weighting coefficients; (d) adding together all error portions distributed to a first pixel on the next scanline to produce an error sum for the first pixel; (e) performing a truncation process upon the error sum for the first pixel to generate a truncated error sum value and a remaining error portion value; and (f) distributing the truncated error sum value to a second pixel, the second pixel being adjacent to the first pixel in a fast scan direction.
Claim 3
Dependent Claim
19 words
The method as claimed in claim 1, further comprising the step of: (g) storing the remaining error portion value.
Claim 4
Dependent Claim
24 words
The method as claimed in claim 1, further comprising the step of: (g) preventing a negative zero from being distributed by said step (f).
Claim 5
Dependent Claim
56 words
The method as claimed in claim 1, wherein said step (a) comprises the substeps of: (a1) receiving the image signal representing the pixel, the grey level value having a first resolution; (a2) conventing the image signal to a second resolution, the second resolution being higher than the first resolution; and (a3) thresholding the convented image signal.
Claim 6
Dependent Claim
95 words
The method as claimed in claim 4, wherein said substep (a2) comprises the substeps of: (a2i) computing a first grey level value from the image signal; (a2ii) computing a second grey level value from the image signal; and (a2iii) computing a plurality of subpixel grey level values B n , the subpixel grey level values B n being equal to P0+n(P1-P0)/N, wherein n is equal to 0 to N-1, P0 is equal to the first grey level value, P1 is equal to the second grey value, and N is equal to a high addressability characteristic.
Claim 7
Dependent Claim
95 words
The method as claimed in claim 5, wherein said step (b) comprises the substeps of: (b1) calculating a desired output, the desired output being equal to a sum of the first and second grey level values divided by two; (b2) calculating an actual output, the actual output being equal to a number of subpixels being equal to or greater than a threshold value multiplied by a maximum grey level value for a pixel divided by a high addressability characteristic; and (b3) calculating the error to be equal to the desired output minus the actual output.
Claim 8
Dependent Claim
29 words
The method as claimed in claim 5, further comprising the step of: (g) screening the image signal with a predetermined screen prior to the execution of said step (a).
Claim 9
Dependent Claim
116 words
The method as claimed in claim 7, wherein said step (b) comprises the substeps of: (b1) calculating a desired output, the desired output being equal to a sum of the first and second multi-level grey scale pixel values divided by two; (b2) calculating an actual output, the actual output being equal to a lowest screen value of the screen plus a number of subpixels being equal to or greater than a threshold value multiplied by a difference between a maximum screen value of the screen and the lowest screen value of the screen divided by a high addressability characteristic; and (b3) calculating the error value to be equal to the desired output minus the actual output.
Claim 10
Dependent Claim
27 words
The method as claimed in claim 1, wherein the truncated error sum value is the four least significant bits of the error sum of the first pixel.
Claim 11
Independent Claim
175 words
A system for diffusing an error created by a grey level reduction process, comprising: processing means for processing an image signal corresponding to a pixel on a scanline having a predetermined number of grey levels to reduce the predetermined number of grey levels to a number of grey levels renderable by an output system and for generating an error from the processing; distribution means for distributing a portion of the error to predetermined pixels on a next scanline, the predetermined pixels on the next scanline receiving a portion of the error portion based on predetermined weighting coefficients; adding means for adding together all error portions distributed to a first pixel on the next scanline to produce an error sum for the first pixel; truncating means for truncating the error sum for the first pixel to generate a truncated error sum value and a remaining error portion value; and redistribution means for distributing the truncated error sum value to a second pixel, the second pixel being adjacent to the first pixel in a fast scan direction.
Claim 12
Independent Claim
175 words
A system for diffusing an error created by a grey level reduction process, comprising: processing means for processing an image signal corresponding to a pixel on a scanline having a predetermined number of grey levels to reduce the predetermined number of grey levels to a number of grey levels renderable by an output system and for generating an error from the processing; distribution means for distributing a portion of the error to predetermined pixels on a next scanline, the predetermined pixels on the next scanline receiving a portion of the error portion based on predetermined weighting coefficients; adding means for adding together all error portions distributed to a first pixel on the next scanline to produce an error sum for the first pixel; truncating means for truncating the error sum for the first pixel to generate a truncated error sum value and a remaining error portion value; and redistribution means for distributing the truncated error sum value to a second pixel, the second pixel being adjacent to the first pixel in a fast scan direction.
Claim 13
Dependent Claim
17 words
The system as claimed in claim 10, further comprising: means for storing the remaining error portion value.
Claim 14
Dependent Claim
22 words
The system as claimed in claim 10, further comprising: means for preventing a negative zero from being distributed by said redistribution means.
Claim 15
Dependent Claim
70 words
The system as claimed in claim 10, wherein said processing means comprises: input means for receiving the image signal representing the pixel, the grey level value having a first resolution; converting means for converting the image signal to a second resolution, the second resolution being higher than the first resolution; threshold means for thresholding the converted image signal and for generating an error value as a result of the thresholding.
Claim 16
Dependent Claim
95 words
The system as claimed in claim 13, wherein said converting means comprises: first means for computing a first grey level value from the image signal and a second grey level value from the image signal; and second means for computing a plurality of subpixel grey level values B n , the subpixel grey level values B n being equal to P0+n(P1-P0)/N, wherein n is equal to 0 to N-1, P0 is equal to the first grey level value, P1 is equal to the second grey value, and N is equal to a high addressability characteristic.
Claim 17
Dependent Claim
98 words
The system as claimed in claim 14, wherein said threshold means comprises: first means for calculating a desired output, the desired output being equal to a sum of the first and second grey level values divided by two; second means for calculating an actual output, the actual output being equal to a number of subpixels being equal to or greater than a threshold value multiplied by a maximum grey level value for a pixel divided by a high addressability characteristic; and third means for calculating the error to be equal to the desired output minus the actual output.
Claim 18
Dependent Claim
26 words
The system as claimed in claim 14, further comprising: screen means for screening the image signal before the image signal is processed by said processing means.
Claim 19
Dependent Claim
119 words
The system as claimed in claim 16, wherein said threshold means comprises: first means for calculating a desired output, the desired output being equal to a sum of the first and second multi-level grey scale pixel values divided by two; second means for calculating an actual output, the actual output being equal to a lowest screen value of the screen plus a number of subpixels being equal to or greater than a threshold value multiplied by a difference between a maximum screen value of the screen and the lowest screen value of the screen divided by a high addressability characteristic; and third means for calculating the error value to be equal to the desired output minus the actual output.
Claim 20
Dependent Claim
27 words
The system as claimed in claim 10, wherein said truncated error sum value is the four least significant bits of the error sum of the first pixel.
Claim 21
Independent Claim
353 words
A method of diffusing an error created by a grey level reduction process, comprising the steps of: (a) processing a first image signal corresponding to a first pixel on a first scanline having a predetermined number of grey levels to reduce the predetermined number of grey levels to a number of grey levels renderable by an output system; (b) generating an error from processing the first image signal in said step (a); (c) distributing a portion of the error to a pixel on a second scanline, the pixel on the second scanline receiving a portion of the error portion based on predetermined weighting coefficients; (d) processing a second image signal corresponding to a second pixel on the first scanline having a predetermined number of grey levels to reduce the predetermined number of grey levels to a number of grey levels renderable by an output system; (e) generating an error from processing the second image signal in said step (d); (f) distributing a portion of the error to the pixel on the second scanline, the pixel on the second scanline receiving a portion of the error portion based on predetermined weighting coefficients; (g) processing a third image signal corresponding to a third pixel on the first scanline having a predetermined number of grey levels to reduce the predetermined number of grey levels to a number of grey levels renderable by an output system; (h) generating an error from processing the third image signal in said step (g); (I) distributing a portion of the error to the pixel on the second scanline, the pixel on the second scanline receiving a portion of the error portion based on predetermined weighting coefficients; (j) adding together all error portions distributed to the pixel on the second scanline to produce an error sum for the pixel; (k) performing a truncation process upon the error sum for the pixel on the second scanline to generate a truncated error sum value and a remaining error portion value; and (l) distributing the truncated error sum value to a pixel adjacent to the pixel on the second scanline in a fast scan direction.
Claim 22
Independent Claim
353 words
A method of diffusing an error created by a grey level reduction process, comprising the steps of: (a) processing a first image signal corresponding to a first pixel on a first scanline having a predetermined number of grey levels to reduce the predetermined number of grey levels to a number of grey levels renderable by an output system; (b) generating an error from processing the first image signal in said step (a); (c) distributing a portion of the error to a pixel on a second scanline, the pixel on the second scanline receiving a portion of the error portion based on predetermined weighting coefficients; (d) processing a second image signal corresponding to a second pixel on the first scanline having a predetermined number of grey levels to reduce the predetermined number of grey levels to a number of grey levels renderable by an output system; (e) generating an error from processing the second image signal in said step (d); (f) distributing a portion of the error to the pixel on the second scanline, the pixel on the second scanline receiving a portion of the error portion based on predetermined weighting coefficients; (g) processing a third image signal corresponding to a third pixel on the first scanline having a predetermined number of grey levels to reduce the predetermined number of grey levels to a number of grey levels renderable by an output system; (h) generating an error from processing the third image signal in said step (g); (I) distributing a portion of the error to the pixel on the second scanline, the pixel on the second scanline receiving a portion of the error portion based on predetermined weighting coefficients; (j) adding together all error portions distributed to the pixel on the second scanline to produce an error sum for the pixel; (k) performing a truncation process upon the error sum for the pixel on the second scanline to generate a truncated error sum value and a remaining error portion value; and (l) distributing the truncated error sum value to a pixel adjacent to the pixel on the second scanline in a fast scan direction.
Claim 23
Dependent Claim
19 words
The method as claimed in claim 19, further comprising the step of: (m) storing the remaining error portion value.
Claim 24
Dependent Claim
24 words
The method as claimed in claim 19, further comprising the step of: (m) preventing a negative zero from being distributed by said step (I).
Claim 25
Dependent Claim
57 words
The method as claimed in claim 19, wherein each of said steps (a), (d), and (g) comprise the substeps of: (adg1) receiving an image signal, the image signal having a first resolution; (adg2) converting the image signal to a second resolution, the second resolution being higher than the first resolution; and (adg3) thresholding the converted image signal.
Claim 26
Dependent Claim
95 words
The method as claimed in claim 22, wherein said substep (adg2) comprises the substeps of: (adg2i) computing a first grey level value from the image signal; (adg2ii) computing a second grey level value from the image signal; and (adg2iii) computing a plurality of subpixel grey level values B n , the subpixel grey level values B n being equal to P0+n(P1-P0)/N, wherein n is equal to 0 to N-1, P0 is equal to the first grey level value, P1 is equal to the second grey value, and N is equal to a high addressability characteristic.
Claim 27
Dependent Claim
101 words
The method as claimed in claim 23, wherein wherein each of said steps (b), (e), and (h) comprise the substeps of: (beh1) calculating a desired output, the desired output being equal to a sum of the first and second grey level values divided by two; (beh2) calculating an actual output, the actual output being equal to a number of subpixels being equal to or greater than a threshold value multiplied by a maximum grey level value for a pixel divided by a high addressability characteristic; and (beh3) calculating the error to be equal to the desired output minus the actual output.
Claim 28
Dependent Claim
66 words
The method as claimed in claim 23, further comprising the steps of: (m) screening the first image signal with a predetermined screen prior to the execution of said step (a); (n) screening the second image signal with a predetermined screen prior to the execution of said step (d); (o) screening the third image signal with a predetermined screen prior to the execution of said step (g).
Claim 29
Dependent Claim
121 words
The method as claimed in claim 25, wherein each of said steps (b), (e), and (h) comprise the substeps of: (beh1) calculating a desired output, ;the desired output being equal to a sum of the first and second multi-level grey scale pixel values divided by two; (beh2) calculating an actual output, the actual output being equal to a lowest screen value of the screen plus a number of subpixels being equal to or greater than a threshold value multiplied by a difference between a maximum screen value of the screen and the lowest screen value of the screen divided by a high addressability characteristic; and (beh3) calculating the error value to be equal to the desired output minus the actual output.
Claim 30
Dependent Claim
30 words
The method as claimed in claim 19, wherein the truncated error sum value is the four least significant bits of the error sum of the pixel on the second scanline.
Claim 31
Independent Claim
206 words
A method of printing an image using error diffusion, comprising the steps of: (a) receiving an image signal corresponding to a first pixel on a scanline having a predetermined number of grey levels; (b) processing the image signal of the first pixel to reduce the predetermined number of grey levels to a lower number of grey levels; (c) generating a mark on a receiving medium using the lower number of grey levels; (d) generating an error from the processing of the image signal in said step Co); (e) distributing a portion of the error to pixels on a next scanline, each pixel on the next scanline receiving a portion of the portion of error based on a predetermined set of weighting coefficients; (f) adding together all error portions distributed to a first pixel on the next scanline to produce an error sum for the first pixel; (g) performing a truncation process upon the error sum for the first pixel on the next scanline to generate a truncated error sum value and a remaining error portion value; and (h) distributing the truncated error sum value to a second pixel, the second pixel being adjacent to the first pixel on the next scanline in a fast scan direction.
Claim 32
Independent Claim
206 words
A method of printing an image using error diffusion, comprising the steps of: (a) receiving an image signal corresponding to a first pixel on a scanline having a predetermined number of grey levels; (b) processing the image signal of the first pixel to reduce the predetermined number of grey levels to a lower number of grey levels; (c) generating a mark on a receiving medium using the lower number of grey levels; (d) generating an error from the processing of the image signal in said step Co); (e) distributing a portion of the error to pixels on a next scanline, each pixel on the next scanline receiving a portion of the portion of error based on a predetermined set of weighting coefficients; (f) adding together all error portions distributed to a first pixel on the next scanline to produce an error sum for the first pixel; (g) performing a truncation process upon the error sum for the first pixel on the next scanline to generate a truncated error sum value and a remaining error portion value; and (h) distributing the truncated error sum value to a second pixel, the second pixel being adjacent to the first pixel on the next scanline in a fast scan direction.
Claim 33
Dependent Claim
31 words
The method as claimed in claim 28, wherein the truncated error sum value is the four least significant bits of the error sum of the first pixel on the next scanline.
References Cited (Backward Citations)
US3786490A
Cited
EP0174721A2
Cited
US4891710A
Cited
US4858163A
Cited
US4969052A
Cited
EP0356225A2
Cited
EP0389164A2
Cited
US5045952A
Cited
US5087981A
Cited
US5402506A
Cited
US5271070A
Cited
US5270836A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-12-08 | 2001-06-09 | 2001-12-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-12-08 | 2005-06-09 | 2005-12-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-12-08 | 2009-06-09 | 2009-12-09 | $7700.00 | Window Closed / Lapsed |