US6160921A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Error diffusion with homogeneous distribution in highlight and shadow regions
Assignee: Apple Inc
•
Filing: 1998-06-15
•
Granted: 2000-12-12
•
Expires: 2018-06-15
Abstract
Abstract To eliminate artifacts resulting from the quantization of images by means of an error diffusion process, a determination is made whether a current pixel being processed is within a shadow or highlight region of an image. If so, a dot of a complementary value is placed in the region only if a distance constraint between the current pixel and neighbor dots is satisfied. If the distance constraint is not satisfied, the placement of the dot is postponed. The distance constraint is based upon the grayscale level of the current pixel. A road map for determining the distance to other dots is defined in a manner such that it expands further from the location of the current pixel as the grayscale value of that pixel approaches the extreme limits of the grayscale range. As a result, a homogenous distribution of dots in highlight and shadow regions of an image is produced.
Inventors
- 👤 Gabriel G. Marcu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 16:46
CPC Classifications
H; H04; H04N; H04N1/00; H04N1/40; H04N1/405; H04N1/4051; H04N1/4052
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
154 words
A method for quantizing image data, comprising the steps of: retrieving image data for a selected pixel of an image; determining whether the selected pixel lies within a highlight or shadow region of the image; detecting whether another pixel within a predetermined distance of the selected pixel has a quantized value representative of a dot that is complementary to the determined region of the image, when the selected pixel is determined to be in a highlight or shadow region of the image; quantizing the image data for the selected pixel to a value representative of a dot that is complementary to the determined region of the image if no other pixel within said predetermined distance has a quantized value representative of a dot that is complementary to the determined region of the image; and otherwise quantizing the image data for the selected pixel to a value associated with the determined region of the image.
Claim 2
Independent Claim
154 words
A method for quantizing image data, comprising the steps of: retrieving image data for a selected pixel of an image; determining whether the selected pixel lies within a highlight or shadow region of the image; detecting whether another pixel within a predetermined distance of the selected pixel has a quantized value representative of a dot that is complementary to the determined region of the image, when the selected pixel is determined to be in a highlight or shadow region of the image; quantizing the image data for the selected pixel to a value representative of a dot that is complementary to the determined region of the image if no other pixel within said predetermined distance has a quantized value representative of a dot that is complementary to the determined region of the image; and otherwise quantizing the image data for the selected pixel to a value associated with the determined region of the image.
Claim 3
Dependent Claim
22 words
The method of claim 1 wherein said predetermined distance is related to the magnitude of the image data for the selected pixel.
Claim 4
Dependent Claim
25 words
The method of claim 2 wherein the predetermined distance increases as the magnitude of the image data approaches an extreme value for the image data.
Claim 5
Dependent Claim
41 words
The method of claim 1 wherein selected pixel is determined to be in a highlight or shadow region of an image if the magnitude of the image data is within a predetermined range adjacent an extreme value for the image data.
Claim 6
Dependent Claim
19 words
The method of claim 4 wherein said predetermined range is approximately 15% of the total range of image data.
Claim 7
Independent Claim
128 words
A method for quantizing image data, comprising the steps of: retrieving an image data value for a selected pixel of an image; determining an initial quantization value for the selected pixel, based upon its image data value; defining a region of image pixels which are adjacent the selected pixel, wherein the number of pixels in said region is determined by an image data value for the selected pixel; detecting whether any of the pixels in said region has a quantized value which is the same as the initial quantization value for the selected pixel; and changing the quantization value for the selected pixel to a value different from said initial quantization value if any of the pixels in said region is the same as said initial quantization value.
Claim 8
Independent Claim
128 words
A method for quantizing image data, comprising the steps of: retrieving an image data value for a selected pixel of an image; determining an initial quantization value for the selected pixel, based upon its image data value; defining a region of image pixels which are adjacent the selected pixel, wherein the number of pixels in said region is determined by an image data value for the selected pixel; detecting whether any of the pixels in said region has a quantized value which is the same as the initial quantization value for the selected pixel; and changing the quantization value for the selected pixel to a value different from said initial quantization value if any of the pixels in said region is the same as said initial quantization value.
Claim 9
Dependent Claim
23 words
The method of claim 6 wherein said region is defined by a path of pixels which extends progressively outward from the selected pixel.
Claim 10
Dependent Claim
20 words
The method of claim 7 wherein the length of said path is determined by image data for the selected pixel.
Claim 11
Dependent Claim
40 words
The method of claim 6 further including the step of determining whether the retrieved image data value is within a predetermined range of data values, and changing said quantization value only if said retrieved data value is within said range.
Claim 12
Dependent Claim
21 words
The method of claim 9 wherein said range of data values is associated with highlight and shadow regions of an image.
Claim 13
Independent Claim
107 words
A system for quantizing image data comprising: an error diffusion processor which processes pixel data values in accordance with quantization errors to generate modified pixel values; a first look-up table storing path length values that are associated with modified pixel values; a second look-up table storing pixel position values that are associated with said path length values; and a quantization processor which generates quantized pixel values from said modified pixel values, and which examines quantized pixel values along a path of pixels in an image which are selected in accordance with the values stored in said look-up tables to selectively prohibit predetermined quantized values from being generated.
Claim 14
Independent Claim
107 words
A system for quantizing image data comprising: an error diffusion processor which processes pixel data values in accordance with quantization errors to generate modified pixel values; a first look-up table storing path length values that are associated with modified pixel values; a second look-up table storing pixel position values that are associated with said path length values; and a quantization processor which generates quantized pixel values from said modified pixel values, and which examines quantized pixel values along a path of pixels in an image which are selected in accordance with the values stored in said look-up tables to selectively prohibit predetermined quantized values from being generated.
Claim 15
Dependent Claim
36 words
The system of claim 11 wherein said quantization processor prohibits a quantized pixel value which is complementary to the values of adjacent pixels from being generated if a pixel along said path has said complementary value.
Claim 16
Dependent Claim
31 words
The system of claim 11 wherein said quantization processor selectively prohibits said predetermined quantized values from being generated only when a pixel value is within a predetermined range of pixel values.
Claim 17
Dependent Claim
24 words
The system of claim 13 wherein said predetermined range is within approximately 15% of the extreme values in the total range of pixel values.
Claim 18
Independent Claim
96 words
A system for quantizing image data comprising: an error diffusion processor which processes image data values in accordance with quantization errors to generate modified data values; a memory storing neighborhoods of pixel positions that are respectively associated with modified data values; and a quantization processor which generates quantized data values from said modified data values, and which examines quantized data values within a neighborhood of pixels in an image which are selected in accordance with the modified data value for a given pixel to selectively prohibit predetermined quantized values from being generated for said given pixel.
Claim 19
Independent Claim
96 words
A system for quantizing image data comprising: an error diffusion processor which processes image data values in accordance with quantization errors to generate modified data values; a memory storing neighborhoods of pixel positions that are respectively associated with modified data values; and a quantization processor which generates quantized data values from said modified data values, and which examines quantized data values within a neighborhood of pixels in an image which are selected in accordance with the modified data value for a given pixel to selectively prohibit predetermined quantized values from being generated for said given pixel.
Claim 20
Dependent Claim
39 words
The system of claim 15 wherein said quantization processor prohibits a quantized value which is complementary to the values of adjacent pixels from being generated for said given pixel if a pixel within said neighborhood has said complementary value.
Claim 21
Dependent Claim
35 words
The system of claim 15 wherein said quantization processor selectively prohibits said predetermined quantized values from being generated only when a data value for said given pixel is within a predetermined range of data values.
Claim 22
Dependent Claim
24 words
The system of claim 17 wherein said predetermined range is within approximately 15% of the extreme values in the total range of data values.
Claim 23
Dependent Claim
148 words
A computer readable medium containing a program which executes the steps of: determining whether retrieved image data for a selected pixel of an image represents a predetermined type of image data; detecting whether another pixel within a predefined distance of the selected pixel has a quantized value representative of a dot that is complementary to the predetermined type of image data, when the retrieved image data is determined to represent said predetermined type of image data; quantizing the image data for the selected pixel to a value representative of a dot that is complementary to said predetermined type of image data if no other pixel within said predetermined distance has a quantized value representative of a dot that is complementary to the predetermined type of image data; and otherwise quantizing the image data for the selected pixel to a value associated with the predetermined type of image data.
Claim 24
Dependent Claim
148 words
A computer readable medium containing a program which executes the steps of: determining whether retrieved image data for a selected pixel of an image represents a predetermined type of image data; detecting whether another pixel within a predefined distance of the selected pixel has a quantized value representative of a dot that is complementary to the predetermined type of image data, when the retrieved image data is determined to represent said predetermined type of image data; quantizing the image data for the selected pixel to a value representative of a dot that is complementary to said predetermined type of image data if no other pixel within said predetermined distance has a quantized value representative of a dot that is complementary to the predetermined type of image data; and otherwise quantizing the image data for the selected pixel to a value associated with the predetermined type of image data.
Claim 25
Dependent Claim
24 words
The computer readable medium of claim 19 wherein said predetermined type of image data is associated with highlight and shadow regions of an image.
Claim 26
Dependent Claim
31 words
The computer readable medium of claim 19 wherein said predetermined type of image data has a value within approximately 15% of the extreme values in the total range of data values.
Claim 27
Dependent Claim
121 words
A computer readable medium containing a program which executes the steps of: determining an initial quantization value for a selected pixel of an image, based upon its image data value; defining a region of image pixels which are adjacent the selected pixel, wherein the number of pixels in said region is determined by an image data value for the selected pixel; detecting whether any of the pixels in said region has a quantized value which is the same as the initial quantization value for the selected pixel; and changing the quantization value for the selected pixel to a value different from said initial quantization value if any of the pixels in said region is the same as said initial quantization value.
Claim 28
Dependent Claim
121 words
A computer readable medium containing a program which executes the steps of: determining an initial quantization value for a selected pixel of an image, based upon its image data value; defining a region of image pixels which are adjacent the selected pixel, wherein the number of pixels in said region is determined by an image data value for the selected pixel; detecting whether any of the pixels in said region has a quantized value which is the same as the initial quantization value for the selected pixel; and changing the quantization value for the selected pixel to a value different from said initial quantization value if any of the pixels in said region is the same as said initial quantization value.
Claim 29
Dependent Claim
25 words
The computer readable medium of claim 22 wherein said region is defined by a path of pixels which extends progressively outward from the selected pixel.
Claim 30
Dependent Claim
22 words
The computer readable medium of claim 23 wherein the length of said path is determined by image data for the selected pixel.
Claim 31
Dependent Claim
42 words
The computer readable medium of claim 22 further including the step of determining whether the retrieved image data value is within a predetermined range of data values, and changing said quantization value only if said retrieved data value is within said range.
Claim 32
Dependent Claim
23 words
The computer readable medium of claim 25 wherein said range of data values is associated with highlight and shadow regions of an image.
References Cited (Backward Citations)
US5045952A
Cited
US5055942A
Cited
US5917614A
Cited
US5353127A
Cited
US5835238A
Cited
US5748785A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-12-12 | 2004-06-12 | 2004-12-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-12-12 | 2008-06-12 | 2008-12-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-12-12 | 2012-06-12 | 2012-12-12 | $7700.00 | Window Closed / Lapsed |