Method and apparatus for mapping colors in an image through dithering and diffusion

• US 5,455,600 A
• Filed: 05/27/1993
• Issued: 10/03/1995
• Est. Priority Date: 12/23/1992
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Myhrvold, Nathan P., Joy, Joseph M., Yuval, Gideon A., Shrivastava, Sunita, Friedman, Steven J., Hargrove, Karen A.
• Primary Examiner(s): Hjerpe, Richard
• Assistant Examiner(s): Liang, Regina
• Application Number:
  US08/068,925
• Time in Patent Office: 859 Days
• Field of Search: 345/150, 345/153, 345/154, 345/155, 345/132, 345/199, 358/500, 358/518, 358/522, 358/523, 358/524, 358/455
• US Class Current: 345/597
• CPC Class Codes: G09G 3/2051 with use of a spatial dither pattern
• CPC Class Codes: G09G 3/2059 using error diffusion
• CPC Class Codes: G09G 5/02 characterised by the way in which colour is displayed details of colour display specific for CRTs G09G1/28; specific for flat matrix panels other than liquid crystal displays G09G3/2003; specific for liquid crystal displays G09G3/3607
• CPC Class Codes: G09G 5/06 using colour palettes, e.g. look-up tables
• CPC Class Codes: H04N 1/52 Circuits or arrangements for halftone screening

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.

Claims

1. 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.

2. The method of claim 1 wherein increasing the boundaries of the color gamut comprises doubling the color gamut.

3. The method of claim 1 wherein clamping the modified true pixel color comprises selecting the nearest color value within the increased color gamut.

4. 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.

5. The method of claim 1 wherein the dithering step is an ordered dithering.

6. The method of claim 1 wherein the dithering step comprises reducing a 24-bit true color value to a 15-bit intermediate color value.

7. 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.

8. The method of claim 1 wherein the calculating and diffusing steps comprise applying the Floyd-Steinberg error diffusion technique.

9. The method of claim 1 wherein the color gamut is based on a red-green-blue color model.

10. The method of claim 1 wherein the color gamut is based on a YUV color model.

11. 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.

12. 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.

13. The method of claim 12 wherein the dithering step is an ordered dithering.

14. The method of claim 12 wherein the dithering step comprises reducing a 24-bit true color value to a 15-bit intermediate color value.

15. 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.

16. 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.

17. 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.

18. 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.

19. The method of claim 18 wherein rendering the pixel includes dithering the modified true color to an intermediate color.

20. 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.