Pattern dithering

Details Pattern dithering Pattern dithering

1999-04-30

2003-08-12

Lee, Thomas D. (Department: 2624)

Facsimile and static presentation processing

Static presentation processing

Attribute control

C358S003130, C358S518000, C382S167000, C345S597000

Reexamination Certificate

active

06606166

ABSTRACT:

BACKGROUND
In computer graphics systems, each non-transparent pixel of an image has a color. A color can be expressed as a vector. For example, a color can be expressed as (57, 180, 200), corresponding to values for red, green, and blue, respectively. A color palette defines the colors available to the image. To display the image using a different color palette, the color of each pixel is converted from a color of the source color palette to a color of the target color palette. However, differences in the palettes and resolutions of the images can result in an undesirable target image, such as when source color values are not found in the target palette. Techniques have been developed to address target image quality by using patterns or random collections of colors from the target palette to emulate the source palette. These techniques are called “dithering” or “halftoning.”
One conventional technique for dithering is noise dithering. In noise dithering, a noise function is applied to the source image to perturb the colors of the pixels. The resulting pixels are then mapped to the closest colors in the target palette. The noise function can be random or can use a recurring pattern. This approach is typically applied when the target palette has a high degree of structure and the colors are distributed in even steps. Applying this technique to a target palette consisting of only black and white is halftoning. One common structured target palette is a “web palette” used with images accessed through the World Wide Web. The typical web palette has 216 colors based on six steps in each of red, green, and blue.
Another conventional technique for dithering is error diffusion dithering. Starting with one source pixel, the color in the target palette closest to the color of the source pixel is assigned to the target pixel. An error value or difference between the source pixel and the target pixel is calculated and distributed to neighboring source pixels which have not yet been processed. This technique uses a sequential processing of pixels and is not well suited for parallel processing of pixels. For example, in one version of error diffusion dithering, when the source pixel color is 60% gray and the nearest color in the target palette is 50% gray, the remaining 10% gray (or a portion) is distributed to the neighboring unprocessed pixels. These neighboring pixels will be more likely to be expressed using darker colors in the target palette. Error from these neighboring pixels also propagates in a similar manner when they are processed.
SUMMARY
The invention provides methods and apparatus implementing techniques for generating a target image having a target palette from a source, image. In general, in one aspect, a technique for generating from a source image a target image comprising target pixels having colors limited to colors found in a target palette includes: determining a source color of a region of the source image corresponding to a location of a target pixel; generating two or more candidate colors for the source color, where the candidate colors are in the target palette; selecting one candidate color from the two or more candidate colors; and setting a target color of the target pixel to be the selected candidate color.
Advantages of implementations of the technique include one or more of the following: the target palette can have an arbitrary structure, where the distribution of colors is even or uneven (e.g., relatively dense in areas and relatively sparse in other areas); the color of a target pixel is determined independently of other target pixels and so avoids neighborhood effects of other target pixels; the color of a target pixel is determined statistically; for a target pixel at a particular location in the target image, the same target color is selected from the target palette for a particular source color, independent of the neighboring source colors; the selection of colors from the target palette reflects human perception of luminance and so provides a desirable target image.


REFERENCES:
patent: 5210602 (1993-05-01), Mintzer
patent: 5319742 (1994-06-01), Edgar
patent: 5341464 (1994-08-01), Friedman et al.
patent: 5455600 (1995-10-01), Friedman et al.
patent: 5664080 (1997-09-01), Lucas et al.
patent: 5990864 (1999-11-01), DeAguiar et al.
Paul Woods, “Taming the Monsters of Web Imagery,” Adobe Systems Incorporated, 1998.
“Adobe ImageReady: New Product Highlights”, Adobe Systems Incorporated, Version 2, 1998.
“Adobe ImageReady:At A Glance”, Adobe Systems Incorporated, Version 2, 1998.

Affiliated with

Also associated with

Rating

Pattern dithering does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Pattern dithering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pattern dithering will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3098767