US5341464A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Luminance emphasized color image rendering
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1993-06-16
•
Granted: 1994-08-23
•
Expires: 2013-06-16
Abstract
Abstract A high color resolution image is rendered using a palette having a lower color resolution. The color of each pixel in the image is mapped to the nearest of the palette colors located on or between levels of uniform luminance adjacent to the pixel color. The mapping of the pixel color is further constrained to exclude palette colors for which double the error to the pixel color is outside the color gamut. The mapping is performed efficiently by a look-up table, the size of which is reduced by first dithering the pixel color to a color in an intermediate palette and then indexing the table using the intermediate palette color to find the reduced palette color. The mapping can be performed in an error diffusion process in which the pixel's color is modified by error diffused from any previously rendered neighboring pixels, then mapped to a reduced palette color to render the pixel with the reduced palette color, and finally diffuse any error between the pixel's color and the reduced palette color to any not yet rendered pixels.
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-01 12:01
CPC Classifications
G; G06; G06T; G06T11/00; G06T11/10
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
170 words
A method for reproducing a color image at a lower color resolution, the color image comprising a plurality of pixels each having one of a plurality of colors in an original palette, the method comprising the steps of: defining at least three discrete luminance levels; defining a reduced resolution palette comprising a plurality of colors, at least one of the reduced resolution palette colors being nearer to a first original palette color than any of the reduced resolution palette colors on or between two of the at least three luminance levels that are adjacent the first original palette color; for each pixel color in the color image, mapping the pixel color to a selected color in the reduced resolution palette that, out of a plurality of colors in the reduced resolution palette on or between two of the at least three luminance levels that are adjacent to the pixel color, is nearest to the pixel color; and reproducing the color image using the selected colors in the reduced resolution palette.
Claim 2
Independent Claim
170 words
A method for reproducing a color image at a lower color resolution, the color image comprising a plurality of pixels each having one of a plurality of colors in an original palette, the method comprising the steps of: defining at least three discrete luminance levels; defining a reduced resolution palette comprising a plurality of colors, at least one of the reduced resolution palette colors being nearer to a first original palette color than any of the reduced resolution palette colors on or between two of the at least three luminance levels that are adjacent the first original palette color; for each pixel color in the color image, mapping the pixel color to a selected color in the reduced resolution palette that, out of a plurality of colors in the reduced resolution palette on or between two of the at least three luminance levels that are adjacent to the pixel color, is nearest to the pixel color; and reproducing the color image using the selected colors in the reduced resolution palette.
Claim 3
Dependent Claim
15 words
The method of claim 1 further comprising the step of error diffusing the color image.
Claim 4
Dependent Claim
137 words
The method of claim 2 further comprising for each of a plurality of pixels of the color image the steps of: reading a true pixel color from a memory where the image is stored; modifying the true pixel color with error diffused from any previously rendered, neighboring pixels; determining which one of the colors of the reduced resolution palette on or between two of the at least three luminance levels that are adjacent to the modified pixel color is nearest in an RGB color gamut to the modified pixel color, said one of the colors being an approximate palette color for the pixel; rendering the pixel using the determined approximate palette color; calculating an error between the determined approximate palette color and the true pixel color; and diffusing the error to any not yet rendered neighboring pixels.
Claim 5
Dependent Claim
44 words
The method of claim 3 wherein the step of modifying further comprises the steps of: scaling errors diffused from any previously rendered neighboring pixels; accumulating the scaled errors; and adding to the pixel color the accumulated, scaled errors to form the modified pixel color.
Claim 6
Dependent Claim
25 words
The method of claim 3 further comprising, after the step of modifying, clamping the modified pixel color to the boundaries of the RGB color gamut.
Claim 7
Dependent Claim
161 words
The method of claim 2 further comprising for each of a plurality of pixels of the color image the steps of: reading a true pixel color from a memory where the image is stored; modifying the true pixel color with error diffused from previously rendered, neighboring pixels; clamping the modified pixel color to the boundaries of an RGB color gamut; ordered dithering the modified pixel color to an intermediate palette color; determining which one of the colors of the reduced resolution palette on or between two of the at least three luminance levels that are adjacent to the color in the intermediate palette is nearest in the RGB color gamut to the color in the intermediate palette, said one of the colors being an approximate palette color for the pixel; rendering the pixel using the approximate palette color; calculating an error between the approximate palette color and the true pixel color; and diffusing the error to not yet rendered neighboring pixels.
Claim 8
Dependent Claim
19 words
The method of claim 1 wherein the step of reproducing comprising reproducing the color image in visually perceptible form.
Claim 9
Dependent Claim
60 words
The method of claim 1 further comprising for each pixel of the color image the steps of: reading the color of the pixel from a memory where the image is stored; and determining which one of the colors of the reduced resolution palette on or between two luminance levels adjacent to the pixel color is nearest to the pixel color.
Claim 10
Dependent Claim
93 words
The method of claim 1 wherein the step of mapping further comprises: when a highly saturated pixel color is mapped to a selected color having a low saturation, if a color at twice the error of the highly saturated pixel color from the selected color is outside an RGB color gamut containing each color in the reduced resolution palette, mapping the pixel color to a color which is the next nearest of the palette colors located on or between two of the at least three luminance levels that are adjacent the pixel color.
Claim 11
Dependent Claim
54 words
The method of claim 1 further comprising the steps of: selecting colors of the reduced resolution palette from colors located on the discrete luminance levels in an RGB color gamut, the spacing in the RGB color gamut between adjacent luminance levels increasing between a level of minimum luminance and a level of maximum luminance.
Claim 12
Dependent Claim
15 words
The method of claim 10 further comprising the step of error diffusing the resulting image.
Claim 13
Independent Claim
181 words
A method for reproducing a color image using a uniform luminance levels palette, the color image comprising a plurality of pixels each having one of a plurality of true colors in an original palette, the method comprising: for each pixel in a color image, selecting a mapping color nearest in an RGB color gamut to the true color of the pixel from the colors in a uniform luminance levels palette on two out of more than two discrete luminance levels that are adjacent the true color, the uniform luminance levels palette consisting of a plurality of colors located on each of the discrete luminance levels intersecting the RGB color gamut, the spacing in the RGB color gamut between adjacent luminance levels increasing between a level of minimum luminance to a level of maximum luminance, at least one of the colors in the uniform luminance levels palette being nearer to a first original palette color than any of the colors in the uniform luminance levels palette on two out of the discrete luminance levels that are adjacent the first original palette color.
Claim 14
Independent Claim
181 words
A method for reproducing a color image using a uniform luminance levels palette, the color image comprising a plurality of pixels each having one of a plurality of true colors in an original palette, the method comprising: for each pixel in a color image, selecting a mapping color nearest in an RGB color gamut to the true color of the pixel from the colors in a uniform luminance levels palette on two out of more than two discrete luminance levels that are adjacent the true color, the uniform luminance levels palette consisting of a plurality of colors located on each of the discrete luminance levels intersecting the RGB color gamut, the spacing in the RGB color gamut between adjacent luminance levels increasing between a level of minimum luminance to a level of maximum luminance, at least one of the colors in the uniform luminance levels palette being nearer to a first original palette color than any of the colors in the uniform luminance levels palette on two out of the discrete luminance levels that are adjacent the first original palette color.
Claim 15
Dependent Claim
61 words
The method of claim 12 wherein the step of selecting further comprises: when a color at twice the error of the pixel's true color from the selected mapping color is outside the RGB color gamut, selecting as the mapping color a color which is the next nearest of the palette colors located on the two luminance levels adjacent the pixel color.
Claim 16
Dependent Claim
11 words
The method of claim 12 further comprising error diffusing the image.
Claim 17
Dependent Claim
143 words
The method of claim 14 wherein the step of selecting comprises: dithering the pixel's true color to a color in an intermediate palette comprised of a plurality of colors in the form of a grid having fewer blue intensity levels than green intensity levels; looking up a color in the uniform luminance levels palette for the pixel according to the pixel's intermediate palette color in a table, the table associating each of the intermediate palette colors with a corresponding color in the uniform luminance levels palette that is nearest of the uniform luminance levels palette colors that are on the two luminance levels adjacent such intermediate palette color and for which double the error from such intermediate palette color is not outside the RGB color gamut; and selecting the uniform luminance levels palette color looked up in the table as the mapping color.
Claim 18
Dependent Claim
202 words
The method of claim 14 comprising for each pixel in the image: adding error diffused from any previously rendered neighboring pixels to the true pixel color to form a modified pixel color; dithering the modified pixel color to a color in an intermediate palette comprised of a plurality of colors in the form of a grid having uniformly spaced green intensity levels, uniformly spaced red intensity levels, uniformly spaced blue intensity levels, and fewer blue intensity levels than green intensity levels; looking up a color in the uniform luminance levels palette for the pixel according to the pixel's intermediate palette color in a table, the table associating each of the intermediate palette colors with a corresponding color in the uniform luminance levels palette that is nearest of the uniform luminance levels palette colors that are on the two luminance levels adjacent such intermediate palette color and for which double the error from such intermediate palette color is not outside the RGB color gamut; selecting the uniform luminance levels palette color looked up in the table as the mapping color; determining an error between the mapping color and the true pixel color; and diffusing the error to any not yet rendered neighboring pixels.
Claim 19
Independent Claim
229 words
An apparatus for reproducing a color image using a reduced resolution palette, the apparatus comprising: image storage means for storing a color image as an array of pixels, the pixels associated with color values in a first palette; a look-up table addressable by color values for returning, when addressed by a first color value corresponding to a first color, a second color value corresponding to a second color which is the nearest to the first color in an RGB color gamut of a plurality of colors in a reduced resolution palette on two luminance levels adjacent to the first color out of at least three discrete luminance levels, the reduced resolution palette comprised of a plurality of color values corresponding to colors on the discrete luminance levels inside the RGB color gamut, the spacing in the RGB color gamut between adjacent luminance levels increasing between a level of minimum luminance and a level of maximum luminance; table addressing means for associating each pixel of the color image with a color value in the reduced resolution palette by associating the pixel with a color value of the reduced resolution palette returned by the look-up table when addressed by a color value associated with the pixel; image rendering means for forming the color image with each pixel of the color image associated with a color value in the reduced resolution palette.
Claim 20
Independent Claim
229 words
An apparatus for reproducing a color image using a reduced resolution palette, the apparatus comprising: image storage means for storing a color image as an array of pixels, the pixels associated with color values in a first palette; a look-up table addressable by color values for returning, when addressed by a first color value corresponding to a first color, a second color value corresponding to a second color which is the nearest to the first color in an RGB color gamut of a plurality of colors in a reduced resolution palette on two luminance levels adjacent to the first color out of at least three discrete luminance levels, the reduced resolution palette comprised of a plurality of color values corresponding to colors on the discrete luminance levels inside the RGB color gamut, the spacing in the RGB color gamut between adjacent luminance levels increasing between a level of minimum luminance and a level of maximum luminance; table addressing means for associating each pixel of the color image with a color value in the reduced resolution palette by associating the pixel with a color value of the reduced resolution palette returned by the look-up table when addressed by a color value associated with the pixel; image rendering means for forming the color image with each pixel of the color image associated with a color value in the reduced resolution palette.
Claim 21
Dependent Claim
73 words
The apparatus of claim 17 wherein the look-up table returns, when addressed by the first color value, a second color value corresponding to a second color which is the nearest to the first color in the RGB color gamut of the colors in the reduced resolution palette on the two luminance levels adjacent to the first color and for which double the error to the first color is inside the RGB color gamut.
Claim 22
Dependent Claim
27 words
The apparatus of claim 17 wherein the reduced resolution palette comprises the colors at the vertices of cross-sections of the RGB color gamut at alternate luminance levels.
Claim 23
Dependent Claim
52 words
The apparatus of claim 17 further comprising: ordered dithering means for performing ordered dithering of the first palette color associated with each pixel to quantize the color associated with each pixel to colors in an intermediate palette, the table addressing means addressing the look-up table with color values of the intermediate palette.
Claim 24
Dependent Claim
43 words
The apparatus of claim 17 further comprising: error diffusion means for performing error diffusion of an error between the reduced resolution palette color value associated with a pixel and the first palette color associated with the pixel to not yet rendered neighboring pixels.
References Cited (Backward Citations)
US4689669A
Cited
US4843379A
Cited
US4907075A
Cited
US5068644A
Cited
US5130701A
Cited
US5233684A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-08-22 | 1998-02-21 | 1998-08-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-08-22 | 2002-02-21 | 2002-08-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-08-22 | 2006-02-21 | 2006-08-23 | $7700.00 | Window Closed / Lapsed |