US6356362B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Halftoning by enhanced error diffusion
Assignee: Canon Inc
•
Filing: 1998-11-02
•
Granted: 2002-03-12
•
Expires: 2018-11-02
Abstract
Abstract Halftoning by error diffusion, enhanced so as to reduce the presence of structural artifacts in the halftoned output while avoiding an artificial increase in halftoning image noise. Specifically, error diffusion according to the invention divides the input gray level intensity range into different segments for purposes of both thresholding and error diffusion. Different error diffusion threshold masks are applied for each respective segment, and different error diffusion weights are applied for each respective segment, with a decision being made as to whether or not to apply a different threshold mask being based on the local image gradient.
Inventors
- 👤 Victor Ostromoukhov
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 23:11
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/40; H04N1/405; H04N1/4051; H04N1/4052; H04N1/4053
Claims Analysis
Total Claims: 72
Claim 1
Independent Claim
139 words
A method for halftoning image data for a targeted one of plural pixels, comprising the steps of: testing to determine whether high frequency spatial characteristics are present in the image data at the target pixel; selecting a halftoning threshold for the target pixel, the halftoning threshold being selected based on whether high frequency spatial characteristics are present at the target pixel, and further being selected in accordance with intensity of the image data at the target pixel in a case where high frequency spatial characteristics are not present; determining a halftone output value for the target pixel based on a comparison between the selected threshold and the image data for the target pixel; and diffusing error between the halftone output value and the image data for the target pixel, the error being diffused to pixels adjacent the target pixel.
Claim 2
Independent Claim
139 words
A method for halftoning image data for a targeted one of plural pixels, comprising the steps of: testing to determine whether high frequency spatial characteristics are present in the image data at the target pixel; selecting a halftoning threshold for the target pixel, the halftoning threshold being selected based on whether high frequency spatial characteristics are present at the target pixel, and further being selected in accordance with intensity of the image data at the target pixel in a case where high frequency spatial characteristics are not present; determining a halftone output value for the target pixel based on a comparison between the selected threshold and the image data for the target pixel; and diffusing error between the halftone output value and the image data for the target pixel, the error being diffused to pixels adjacent the target pixel.
Claim 3
Dependent Claim
23 words
A method according to claim 1 , wherein image data for the target pixel is comprised of original image data plus accumulated error.
Claim 4
Dependent Claim
41 words
A method according to claim 1 , wherein in said testing step, the presence of high frequency spatial characteristics is determined based on a gradient between image data for the target pixel and at least one pixel adjacent the target pixel.
Claim 5
Dependent Claim
46 words
A method according to claim 1 , wherein in a case where said testing step determines that high frequency spatial characteristics are not present, said selecting step selects a halftoning threshold whose spread varies from a fixed threshold in dependence on intensity of the image data.
Claim 6
Dependent Claim
19 words
A method according to claim 4 , wherein the spread increases at each intensity corresponding to formation of artifacts.
Claim 7
Dependent Claim
23 words
A method according to claim 5 , wherein the spread increases at each intensity corresponding to an integral fraction of the intensity range.
Claim 8
Dependent Claim
20 words
A method according to claim 6 , wherein at intervening non-integral fractions of the intensity range, the spread is reduced.
Claim 9
Dependent Claim
58 words
A method according to claim 1 , wherein in a case where said testing step determines that high frequency spatial characteristics are not present, said selecting step comprises the steps of selecting one of plural threshold masks based on intensity of the image data for the target pixel, and selecting a halftoning threshold from the selected threshold mask.
Claim 10
Dependent Claim
38 words
A method according to claim 8 , wherein each of said plural threshold masks has only a limited number of threshold values, with spread of values in each such threshold mask varying based on its corresponding intensity level.
Claim 11
Independent Claim
136 words
A method for halftoning image data for each of plural pixels, comprising the steps of: determining whether to apply one of plural threshold masks, or whether to apply a fixed threshold, based on the presence of high frequency spatial characteristics of the input image; selecting, in a case that one of plural threshold masks is to be applied, one of said plural threshold masks based on intensity of the image data for a target pixel plus an accumulated error; determining a halftone output value for the target pixel based on a comparison between a selected threshold and the image data plus accumulated error for the target pixel; and diffusing error between the halftone output value and the image data plus accumulated error for the target pixel, the error being diffused to pixels adjacent the target pixel.
Claim 12
Independent Claim
136 words
A method for halftoning image data for each of plural pixels, comprising the steps of: determining whether to apply one of plural threshold masks, or whether to apply a fixed threshold, based on the presence of high frequency spatial characteristics of the input image; selecting, in a case that one of plural threshold masks is to be applied, one of said plural threshold masks based on intensity of the image data for a target pixel plus an accumulated error; determining a halftone output value for the target pixel based on a comparison between a selected threshold and the image data plus accumulated error for the target pixel; and diffusing error between the halftone output value and the image data plus accumulated error for the target pixel, the error being diffused to pixels adjacent the target pixel.
Claim 13
Dependent Claim
39 words
A member according to claim 10 , wherein each thresholding mask has only a limited number of threshold values, with each different one of the plural threshold masks being provided for a different segment of the input intensity range.
Claim 14
Dependent Claim
32 words
A method according to claim 10 , wherein each thresholding mask has only a limited number of threshold values, with a separate threshold mask being provided for each different input intensity value.
Claim 15
Dependent Claim
23 words
A method according to claim 10 , wherein the spread of values in each threshold mask varies based on its corresponding intensity level.
Claim 16
Dependent Claim
20 words
A method according to claim 10 , wherein the spread increases at each intensity range corresponding to formation of artifacts.
Claim 17
Dependent Claim
20 words
A method according to claim 14 , wherein at intervening non-integral fractions of the intensity range, the spread is reduced.
Claim 18
Dependent Claim
49 words
A method according to claim 10 , wherein the presence of high frequency spatial characteristics of the input image is determined based on a gradient test by which the spatial characteristics at each target pixel are determined based on whether there is a significant change relative to adjacent pixels.
Claim 19
Independent Claim
144 words
An apparatus for halftoning image data for each of plural pixels, said apparatus comprising: means for testing to determine whether high frequency spatial characteristics are present in the image data at the target pixel; means for selecting a halftoning threshold for the target pixel, the halftoning threshold being selected based on whether high frequency spatial characteristics are present at the target pixel, and further being selected in accordance with intensity of the image data at the target pixel in a case where high frequency spatial characteristics are not present; means for determining a halftone output value for the target pixel based on a comparison between the selected threshold and the image data for the target pixel; and means for diffusing error between the halftone output value and the image data for the target pixel, the error being diffused to pixels adjacent the target pixel.
Claim 20
Independent Claim
144 words
An apparatus for halftoning image data for each of plural pixels, said apparatus comprising: means for testing to determine whether high frequency spatial characteristics are present in the image data at the target pixel; means for selecting a halftoning threshold for the target pixel, the halftoning threshold being selected based on whether high frequency spatial characteristics are present at the target pixel, and further being selected in accordance with intensity of the image data at the target pixel in a case where high frequency spatial characteristics are not present; means for determining a halftone output value for the target pixel based on a comparison between the selected threshold and the image data for the target pixel; and means for diffusing error between the halftone output value and the image data for the target pixel, the error being diffused to pixels adjacent the target pixel.
Claim 21
Dependent Claim
23 words
An apparatus according to claim 17 , wherein image data for the target pixel is comprised of original image data plus accumulated error.
Claim 22
Dependent Claim
40 words
An apparatus according to claim 17 , wherein said means for testing determines the presence of high frequency spatial characteristics based on a gradient between image data for the target pixel and at least one pixel adjacent the target pixel.
Claim 23
Dependent Claim
47 words
An apparatus according to claim 17 , wherein in a case where said testing means determines that high frequency spatial characteristics are not present, said means for selecting selects a halftoning threshold whose spread varies from a fixed threshold in dependence on intensity of the image data.
Claim 24
Dependent Claim
19 words
An apparatus according to claim 20 , wherein the spread increases at each intensity corresponding to formation of artifacts.
Claim 25
Dependent Claim
23 words
An apparatus according to claim 20 , wherein the spread increases at each intensity corresponding to an integral fraction of the intensity range.
Claim 26
Dependent Claim
20 words
An apparatus according to claim 22 , wherein at intervening non-integral fractions of the intensity range, the spread is reduced.
Claim 27
Dependent Claim
62 words
An apparatus according to claim 17 , wherein in a case where said testing means determines that high frequency spatial characteristics are not present, said means for selecting comprises first means for selecting one of plural threshold masks based on intensity of the image data for the target pixel, and second means for selecting a halftoning threshold from the selected threshold mask.
Claim 28
Dependent Claim
38 words
An apparatus according to claim 24 , wherein each of said plural threshold masks has only a limited number of threshold values, with spread of values in each such threshold mask varying based on its corresponding intensity level.
Claim 29
Independent Claim
160 words
An apparatus for halftoning image data for each of plural pixels, comprising: a program memory for storing process steps executable to: (1) test to determine whether high frequency spatial characteristics are present in the image data at the target pixel, (2) select a halftoning threshold for the target pixel, the halftoning threshold being selected based on whether high frequency spatial characteristics are present at the target pixel, and further being selected in accordance with intensity of the image data at the target pixel in a case where high frequency spatial characteristics are not present, (3) determine a halftone output value for the target pixel based on a comparison between the selected threshold and the image data for the target pixel, and (4) diffuse error between the halftone output value and the image data for the target pixel, the error being diffused to pixels adjacent the target pixel; and a processor for executing the process steps stored in said program memory.
Claim 30
Independent Claim
160 words
An apparatus for halftoning image data for each of plural pixels, comprising: a program memory for storing process steps executable to: (1) test to determine whether high frequency spatial characteristics are present in the image data at the target pixel, (2) select a halftoning threshold for the target pixel, the halftoning threshold being selected based on whether high frequency spatial characteristics are present at the target pixel, and further being selected in accordance with intensity of the image data at the target pixel in a case where high frequency spatial characteristics are not present, (3) determine a halftone output value for the target pixel based on a comparison between the selected threshold and the image data for the target pixel, and (4) diffuse error between the halftone output value and the image data for the target pixel, the error being diffused to pixels adjacent the target pixel; and a processor for executing the process steps stored in said program memory.
Claim 31
Dependent Claim
23 words
An apparatus according to claim 26 , wherein image data for the target pixel is comprised of original image data plus accumulated error.
Claim 32
Dependent Claim
41 words
An apparatus according to claim 26 , wherein in said testing step, the presence of high frequency spatial characteristics is determined based on a gradient between image data for the target pixel and at least one pixel adjacent the target pixel.
Claim 33
Dependent Claim
45 words
Apparatus according to claim 26 , wherein in a case where said testing step determines that high frequency spatial characteristics are not present, said selecting step selects a halftoning threshold whose spread varies from a fixed threshold in dependence on intensity of the image data.
Claim 34
Dependent Claim
19 words
An apparatus according to claim 29 , wherein the spread increases at each intensity corresponding to formation of artifacts.
Claim 35
Dependent Claim
23 words
An apparatus according to claim 29 , wherein the spread increases at each intensity corresponding to an integral fraction of the intensity range.
Claim 36
Dependent Claim
20 words
An apparatus according to claim 31 , wherein at intervening non-integral fractions of the intensity range, the spread is reduced.
Claim 37
Dependent Claim
58 words
An apparatus according to claim 26 , wherein in a case where said testing step determines that high frequency spatial characteristics are not present, said selecting step comprises the steps of selecting one of plural threshold masks based on intensity of the image data for the target pixel, and selecting a halftoning threshold from the selected threshold mask.
Claim 38
Dependent Claim
38 words
An apparatus according to claim 33 , wherein each of said plural threshold masks has only a limited number of threshold values, with spread of values in each such threshold mask varying based on its corresponding intensity level.
Claim 39
Dependent Claim
161 words
Computer-executable process steps stored on a computer readable medium, said computer-executable process steps for halftoning image data for each of plural pixels, said computer-executable process steps comprising: testing step to test to determine whether high frequency spatial characteristics are present in the image data at the target pixel; selecting step to select a halftoning threshold for the target pixel, the halftoning threshold being selected based on whether high frequency spatial characteristics are present at the target pixel, and further being selected in accordance with intensity of the image data at the target pixel in a case where high frequency spatial characteristics are not present; determining step to determine a halftone output value for the target pixel based on a comparison between the selected threshold and the image data for the target pixel; and diffusing step to diffuse error between the halftone output value and the image data for the target pixel, the error being diffused to pixels adjacent the target pixel.
Claim 40
Dependent Claim
161 words
Computer-executable process steps stored on a computer readable medium, said computer-executable process steps for halftoning image data for each of plural pixels, said computer-executable process steps comprising: testing step to test to determine whether high frequency spatial characteristics are present in the image data at the target pixel; selecting step to select a halftoning threshold for the target pixel, the halftoning threshold being selected based on whether high frequency spatial characteristics are present at the target pixel, and further being selected in accordance with intensity of the image data at the target pixel in a case where high frequency spatial characteristics are not present; determining step to determine a halftone output value for the target pixel based on a comparison between the selected threshold and the image data for the target pixel; and diffusing step to diffuse error between the halftone output value and the image data for the target pixel, the error being diffused to pixels adjacent the target pixel.
Claim 41
Dependent Claim
24 words
Computer-executable process steps according to claim 35 , wherein image data for the target pixel is comprised of original image data plus accumulated error.
Claim 42
Dependent Claim
42 words
Computer-executable process steps according to claim 35 , wherein in said testing step, the presence of high frequency spatial characteristics is determined based on a gradient between image data for the target pixel and at least one pixel adjacent the target pixel.
Claim 43
Dependent Claim
47 words
Computer-executable process steps according to claim 35 , wherein in a case where said testing step determines that high frequency spatial characteristics are not present, said selecting step selects a halftoning threshold whose spread varies from a fixed threshold in dependence on intensity of the image data.
Claim 44
Dependent Claim
20 words
Computer-executable process steps according to claim 38 , wherein the spread increases at each intensity corresponding to formation of artifacts.
Claim 45
Dependent Claim
24 words
Computer-executable process steps according to claim 38 , wherein the spread increases at each intensity corresponding to an integral fraction of the intensity range.
Claim 46
Dependent Claim
21 words
Computer-executable process steps according to claim 40 , wherein at intervening non-integral fractions of the intensity range, the spread is reduced.
Claim 47
Dependent Claim
59 words
Computer-executable process steps according to claim 35 , wherein in a case where said testing step determines that high frequency spatial characteristics are not present, said selecting step comprises the steps of selecting one of plural threshold masks based on intensity of the image data for the target pixel, and selecting a halftoning threshold from the selected threshold mask.
Claim 48
Dependent Claim
39 words
Computer-executable process steps according to claim 42 , wherein each of said plural threshold masks has only a limited number of threshold values, with spread of values in each such threshold mask varying based on its corresponding intensity level.
Claim 49
Independent Claim
145 words
An apparatus for halftoning image data for each of plural pixels, said apparatus comprising: first means for determining whether to apply one of plural threshold masks, or whether to apply a fixed threshold, based on the presence of high frequency spatial characteristics of the input image; means for selecting, in a case that one of plural threshold masks is to be applied, one of said plural threshold masks based on intensity of the image data for a target pixel plus an accumulated error; second means for determining a halftone output value for the target pixel based on a comparison between a selected threshold and the image data plus accumulated error for the target pixel; and means for diffusing error between the halftone output value and the image data plus accumulated error for the target pixel, the error being diffused to pixels adjacent the target pixel.
Claim 50
Independent Claim
145 words
An apparatus for halftoning image data for each of plural pixels, said apparatus comprising: first means for determining whether to apply one of plural threshold masks, or whether to apply a fixed threshold, based on the presence of high frequency spatial characteristics of the input image; means for selecting, in a case that one of plural threshold masks is to be applied, one of said plural threshold masks based on intensity of the image data for a target pixel plus an accumulated error; second means for determining a halftone output value for the target pixel based on a comparison between a selected threshold and the image data plus accumulated error for the target pixel; and means for diffusing error between the halftone output value and the image data plus accumulated error for the target pixel, the error being diffused to pixels adjacent the target pixel.
Claim 51
Dependent Claim
39 words
An apparatus according to claim 44 , wherein each thresholding mask has only a limited number of threshold values, with each different one of the plural threshold masks being provided for a different segment of the input intensity range.
Claim 52
Dependent Claim
32 words
An apparatus according to claim 44 , wherein each thresholding mask has only a limited number of threshold values, with a separate threshold mask being provided for each different input intensity value.
Claim 53
Dependent Claim
23 words
An apparatus according to claim 44 , wherein the spread of values in each threshold mask varies based on its corresponding intensity level.
Claim 54
Dependent Claim
20 words
An apparatus according to claim 44 , wherein the spread increases at each intensity range corresponding to formation of artifacts.
Claim 55
Dependent Claim
20 words
An apparatus according to claim 48 , wherein at intervening non-integral fractions of the intensity range, the spread is reduced.
Claim 56
Dependent Claim
49 words
An apparatus according to claim 44 , wherein the presence of high frequency spatial characteristics of the input image is determined based on a gradient test by which the spatial characteristics at each target pixel are determined based on whether there is a significant change relative to adjacent pixels.
Claim 57
Independent Claim
159 words
An apparatus for halftoning image data for each of plural pixels, comprising: a program memory for storing process steps executable to: (1) determine whether to apply one of plural threshold masks, or whether to apply a fixed threshold, based on the presence of high frequency spatial characteristics of the input image, (2) select, in a case that one of plural threshold masks is to be applied, one of said plural threshold masks based on intensity of the image data for a target pixel plus an accumulated error, (3) determine a halftone output value for the target pixel based on a comparison between a selected threshold and the image data plus accumulated error for the target pixel, and (4) diffuse error between the halftone output value and the image data plus accumulated error for the target pixel, the error being diffused to pixels adjacent the target pixel; and a processor for executing the process steps stored in said program memory.
Claim 58
Independent Claim
159 words
An apparatus for halftoning image data for each of plural pixels, comprising: a program memory for storing process steps executable to: (1) determine whether to apply one of plural threshold masks, or whether to apply a fixed threshold, based on the presence of high frequency spatial characteristics of the input image, (2) select, in a case that one of plural threshold masks is to be applied, one of said plural threshold masks based on intensity of the image data for a target pixel plus an accumulated error, (3) determine a halftone output value for the target pixel based on a comparison between a selected threshold and the image data plus accumulated error for the target pixel, and (4) diffuse error between the halftone output value and the image data plus accumulated error for the target pixel, the error being diffused to pixels adjacent the target pixel; and a processor for executing the process steps stored in said program memory.
Claim 59
Dependent Claim
39 words
An apparatus according to claim 51 , wherein each thresholding mask has only a limited number of threshold values, with each different one of the plural threshold masks being provided for a different segment of the input intensity range.
Claim 60
Dependent Claim
32 words
An apparatus according to claim 51 , wherein each thresholding mask has only a limited number of threshold values, with a separate threshold mask being provided for each different input intensity value.
Claim 61
Dependent Claim
23 words
An apparatus according to claim 51 , wherein the spread of values in each threshold mask varies based on its corresponding intensity level.
Claim 62
Dependent Claim
20 words
An apparatus according to claim 51 , wherein the spread increases at each intensity range corresponding to formation of artifacts.
Claim 63
Dependent Claim
20 words
An apparatus according to claim 55 , wherein at intervening non-integral fractions of the intensity range, the spread is reduced.
Claim 64
Dependent Claim
49 words
An apparatus according to claim 51 , wherein the presence of high frequency spatial characteristics of the input image is determined based on a gradient test by which the spatial characteristics at each target pixel are determined based on whether there is a significant change relative to adjacent pixels.
Claim 65
Dependent Claim
166 words
Computer-executable process steps stored on a computer readable medium, said computer-executable process steps for halftoning image data for each of plural pixels, said computer-executable process steps comprising: a testing step to test to determine whether to apply one of plural threshold masks, or whether to apply a fixed threshold, based on the presence of high frequency spatial characteristics of the input image; a selecting step to select, in a case that one of plural threshold masks is to be applied, one of said plural threshold masks based on intensity of the image data for a target pixel plus an accumulated error; a determining step to determine a halftone output value for the target pixel based on a comparison between a selected threshold and the image data plus accumulated error for the target pixel; and a diffusing step to diffuse error between the halftone output value and the image data plus accumulated error for the target pixel, the error being diffused to pixels adjacent the target pixel.
Claim 66
Dependent Claim
166 words
Computer-executable process steps stored on a computer readable medium, said computer-executable process steps for halftoning image data for each of plural pixels, said computer-executable process steps comprising: a testing step to test to determine whether to apply one of plural threshold masks, or whether to apply a fixed threshold, based on the presence of high frequency spatial characteristics of the input image; a selecting step to select, in a case that one of plural threshold masks is to be applied, one of said plural threshold masks based on intensity of the image data for a target pixel plus an accumulated error; a determining step to determine a halftone output value for the target pixel based on a comparison between a selected threshold and the image data plus accumulated error for the target pixel; and a diffusing step to diffuse error between the halftone output value and the image data plus accumulated error for the target pixel, the error being diffused to pixels adjacent the target pixel.
Claim 67
Dependent Claim
40 words
Computer-executable process steps according to claim 58 , wherein each thresholding mask has only a limited number of threshold values, with each different one of the plural threshold masks being provided for a different segment of the input intensity range.
Claim 68
Dependent Claim
33 words
Computer-executable process steps according to claim 58 , wherein each thresholding mask has only a limited number of threshold values, with a separate threshold mask being provided for each different input intensity value.
Claim 69
Dependent Claim
24 words
Computer-executable process steps according to claim 58 , wherein the spread of values in each threshold mask varies based on its corresponding intensity level.
Claim 70
Dependent Claim
21 words
Computer-executable process steps according to claim 58 , wherein the spread increases at each intensity range corresponding to formation of artifacts.
Claim 71
Dependent Claim
21 words
Computer-executable process steps according to claim 62 , wherein at intervening non-integral fractions of the intensity range, the spread is reduced.
Claim 72
Dependent Claim
50 words
Computer-executable process steps according to claim 58 , wherein the presence of high frequency spatial characteristics of the input image is determined based on a gradient test by which the spatial characteristics at each target pixel are determined based on whether there is a significant change relative to adjacent pixels.
References Cited (Backward Citations)
US5251023A
Cited
US5337087A
Cited
US5276535A
Cited
US5438431A
Cited
US5535020A
Cited
US5422742A
Cited
WO1995027365A1
Cited
US5687303A
Cited
US5557709A
Cited
US5684932A
Cited
US5799108A
Cited
US5796435A
Cited
US5696602A
Cited
US5737453A
Cited
US5673121A
Cited
US5701366A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-03-11 | 2005-09-10 | 2006-03-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-03-11 | 2009-09-10 | 2010-03-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-03-11 | 2013-09-10 | 2014-03-12 | $7700.00 | Window Closed / Lapsed |