US5455600A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for mapping colors in an image through dithering and diffusion
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1993-05-27
•
Granted: 1995-10-03
•
Expires: 2013-05-27
Abstract
Abstract A high color resolution image is accurately approximated with a low resolution image through a unique combination of ordered dithering and error diffusion. The true color of each pixel is modified with error from previously rendered pixels and then dithered to an intermediate color of 15 bits. The intermediate color is then mapped to the nearest displayable color in a displayable color palette using a precomputed look-up table. Any error between a displayed color of a pixel and its true color is calculated and spread among neighboring pixels not yet rendered.
Inventors
- 👤 Steven J. Friedman
- 👤 Karen A. Hargrove
- 👤 Joseph M. Joy
- 👤 Nathan P. Myhrvold
- 👤 Sunita Shrivastava
- 👤 Gideon A. Yuval
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 09:32
CPC Classifications
G; G09; G09G; G09G5/00; G09G5/02; G09G5/06; H; H04; H04N; H04N1/00; H04N1/46; H04N1/52; G09G3/00; G09G3/20; G09G3/2007; G09G3/2044; G09G3/2051; G09G3/2059
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
126 words
A method of approximating a high color resolution image with a low color resolution image, comprising: increasing the boundaries of a color gamut for containing pixel colors; for each pixel of the high color resolution image, reading its true color from a memory where the image is stored; modifying the true color with error diffused from previously rendered pixels; clamping the modified true color to within the increased boundary of the color gamut; dithering the modified true color to an intermediate color; determining which displayable color of a displayable color palette is nearest to the intermediate color; rendering the pixel using a displayable color; calculating an error between the displayable color and the true pixel color; and diffusing the error to not yet rendered neighboring pixels.
Claim 2
Independent Claim
126 words
A method of approximating a high color resolution image with a low color resolution image, comprising: increasing the boundaries of a color gamut for containing pixel colors; for each pixel of the high color resolution image, reading its true color from a memory where the image is stored; modifying the true color with error diffused from previously rendered pixels; clamping the modified true color to within the increased boundary of the color gamut; dithering the modified true color to an intermediate color; determining which displayable color of a displayable color palette is nearest to the intermediate color; rendering the pixel using a displayable color; calculating an error between the displayable color and the true pixel color; and diffusing the error to not yet rendered neighboring pixels.
Claim 3
Dependent Claim
18 words
The method of claim 1 wherein increasing the boundaries of the color gamut comprises doubling the color gamut.
Claim 4
Dependent Claim
23 words
The method of claim 1 wherein clamping the modified true pixel color comprises selecting the nearest color value within the increased color gamut.
Claim 5
Dependent Claim
26 words
The method of claim 1 wherein the modifying step comprises adding or subtracting color intensity from each of the color dimensions of the pixel true color.
Claim 6
Dependent Claim
13 words
The method of claim 1 wherein the dithering step is an ordered dithering.
Claim 7
Dependent Claim
22 words
The method of claim 1 wherein the dithering step comprises reducing a 24-bit true color value to a 15-bit intermediate color value.
Claim 8
Dependent Claim
49 words
The method of claim 1 wherein the determining step comprises precomputing a look-up table having as an index intermediate color values and having as entries color numbers to a displayable color palette, the intermediate color values associated with color numbers representing the nearest colors in the displayable color palette.
Claim 9
Dependent Claim
18 words
The method of claim 1 wherein the calculating and diffusing steps comprise applying the Floyd-Steinberg error diffusion technique.
Claim 10
Dependent Claim
16 words
The method of claim 1 wherein the color gamut is based on a red-green-blue color model.
Claim 11
Dependent Claim
16 words
The method of claim 1 wherein the color gamut is based on a YUV color model.
Claim 12
Independent Claim
127 words
A method of approximating a high color resolution image with a low color resolution image, comprising: increasing the color gamut of a color model for containing pixel colors; for each pixel of the high color resolution image, reading its true color from a memory where the image is stored; modifying the true color with error diffused from previously rendered pixels; clamping the modified true color to within the boundary of the increased color gamut; order dithering the modified true color to an intermediate color; looking up in an intermediate table a displayable color nearest to the intermediate color; rendering the pixel using the displayable color; calculating an error between the displayable color and the true pixel color; and diffusing the error to not yet rendered neighboring pixels.
Claim 13
Independent Claim
127 words
A method of approximating a high color resolution image with a low color resolution image, comprising: increasing the color gamut of a color model for containing pixel colors; for each pixel of the high color resolution image, reading its true color from a memory where the image is stored; modifying the true color with error diffused from previously rendered pixels; clamping the modified true color to within the boundary of the increased color gamut; order dithering the modified true color to an intermediate color; looking up in an intermediate table a displayable color nearest to the intermediate color; rendering the pixel using the displayable color; calculating an error between the displayable color and the true pixel color; and diffusing the error to not yet rendered neighboring pixels.
Claim 14
Independent Claim
120 words
A method of approximating a high color resolution image with a low color resolution image, comprising: increasing the boundaries of a color gamut for containing pixel colors; for each pixel of the high color resolution image, reading its true color; modifying the true color with error diffused from previously rendered pixels; clamping the modified true color to within the increased boundary of the color gamut; dithering the modified true color to an intermediate color; looking up in an intermediate table a color number associated with a displayable color nearest to the intermediate color, the displayable color being one of a number in a displayable color palette; and rendering the pixel by displaying the displayable color associated with the color number.
Claim 15
Independent Claim
120 words
A method of approximating a high color resolution image with a low color resolution image, comprising: increasing the boundaries of a color gamut for containing pixel colors; for each pixel of the high color resolution image, reading its true color; modifying the true color with error diffused from previously rendered pixels; clamping the modified true color to within the increased boundary of the color gamut; dithering the modified true color to an intermediate color; looking up in an intermediate table a color number associated with a displayable color nearest to the intermediate color, the displayable color being one of a number in a displayable color palette; and rendering the pixel by displaying the displayable color associated with the color number.
Claim 16
Dependent Claim
13 words
The method of claim 12 wherein the dithering step is an ordered dithering.
Claim 17
Dependent Claim
22 words
The method of claim 12 wherein the dithering step comprises reducing a 24-bit true color value to a 15-bit intermediate color value.
Claim 18
Dependent Claim
47 words
The method of claim 12 including precomputing the intermediate table, the table having as an index intermediate color values and having as entries color numbers to the displayable color palette, the intermediate color values associated with color numbers representing the nearest colors in the displayable color palette.
Claim 19
Dependent Claim
25 words
The method of claim 12 including diffusing error between the displayed color of a pixel and its true color to not yet rendered neighboring pixels.
Claim 20
Independent Claim
144 words
An apparatus for approximating a high color resolution image with a low color resolution image, comprising: means for increasing the boundaries of a color gamut for containing pixel colors; means for reading a true color of each pixel of the high color resolution image from a memory where the image is stored; means for modifying the true color with error diffused from previously rendered pixels; means for clamping the modified true color to within the increased boundary of the color gamut; means for dithering the modified true color to an intermediate color; means for determining which displayable color of a displayable color palette is nearest to the intermediate color; means for rendering the pixel using a displayable color; means for calculating an error between the displayable color and the true pixel color; and means for diffusing the error to not yet rendered neighboring pixels.
Claim 21
Independent Claim
144 words
An apparatus for approximating a high color resolution image with a low color resolution image, comprising: means for increasing the boundaries of a color gamut for containing pixel colors; means for reading a true color of each pixel of the high color resolution image from a memory where the image is stored; means for modifying the true color with error diffused from previously rendered pixels; means for clamping the modified true color to within the increased boundary of the color gamut; means for dithering the modified true color to an intermediate color; means for determining which displayable color of a displayable color palette is nearest to the intermediate color; means for rendering the pixel using a displayable color; means for calculating an error between the displayable color and the true pixel color; and means for diffusing the error to not yet rendered neighboring pixels.
Claim 22
Independent Claim
108 words
A method of approximating a high color resolution image with a low color resolution image, comprising: increasing the boundaries of a color gamut for containing pixel colors; for each pixel of the high color resolution image, reading its true color from a memory where the image is stored; modifying the true color with error diffused from previously rendered pixels; clamping the modified true color to within the increased boundary of the color gamut; rendering the pixel using a displayable color associated with the modified true color; calculating an error between the displayable color and the true pixel color; and diffusing the error to not yet rendered neighboring pixels.
Claim 23
Independent Claim
108 words
A method of approximating a high color resolution image with a low color resolution image, comprising: increasing the boundaries of a color gamut for containing pixel colors; for each pixel of the high color resolution image, reading its true color from a memory where the image is stored; modifying the true color with error diffused from previously rendered pixels; clamping the modified true color to within the increased boundary of the color gamut; rendering the pixel using a displayable color associated with the modified true color; calculating an error between the displayable color and the true pixel color; and diffusing the error to not yet rendered neighboring pixels.
Claim 24
Dependent Claim
19 words
The method of claim 18 wherein rendering the pixel includes dithering the modified true color to an intermediate color.
Claim 25
Dependent Claim
25 words
The method of claim 19 wherein rendering the pixel includes determining which displayable color of a displayable color palette is nearest to the intermediate color.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-10-02 | 1999-04-03 | 1999-10-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-10-02 | 2003-04-03 | 2003-10-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-10-02 | 2007-04-03 | 2007-10-03 | $7700.00 | Window Closed / Lapsed |