Image analysis – Color image processing
Reexamination Certificate
2000-05-18
2004-04-27
Chen, Wenpeng (Department: 2624)
Image analysis
Color image processing
C358S518000
Reexamination Certificate
active
06728398
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to creating indexed-color images.
Current image processing systems provide numerous methods for converting an image into an indexed-color image. One system provides a color lookup table for the image and uses a tree algorithm or a brute force algorithm to invert the color lookup table to create the indexed-color image. Another system provides a color lookup table for the image and uses a 32768 entry table indexed with 3 5-bit numbers to invert the lookup table. The system first fills the 32768 entry table with the closest index in the color lookup table corresponding to the direct color represented by each 3 channel, 5-bit per channel number that indexes the 32768 entry table. For a direct color value of the image, the most significant 5 bits of each channel in the direct color value (e.g., the red channel in an RGB color value) are used as an index into the 32768 entry table. The color lookup table index that is stored in the 32768 entry table at that location is used to represent the color in the indexed image.
In general, the number of entries in a color lookup table ranges from 2 to 256. However, this number is limited only by the number of bits used to define each color in the indexed-color image. If the image has 256 or fewer distinct colors, the color lookup table defines an exact palette consisting of the exact colors used in the image. Alternatively, the color lookup table defines an adaptive palette formed by taking a sample of all the colors in the image (i.e., the most commonly-used colors in the image or the colors providing the best coverage of the image). An adaptive palette can be used by a dithering process to approximate colors that do not specifically appear in the image. If the image is going to be reproduced on a web-site, for example, the color lookup table can be a web palette that consists of the 216 web-safe colors shared by most computers.
Conventionally, to convert each pixel's color value to an index value, a system searches the color lookup table to find the entry having the color value closest to the color value of the pixel, and places the index of the entry into the indexed-color image. This process is time-consuming and computationally inefficient.
SUMMARY OF THE INVENTION
In general, in one aspect, the invention provides a method and apparatus, including a computer program product, implementing techniques for creating an indexed-color image from a direct-color image. The techniques include receiving a color lookup table comprising an indexed list of direct color values; receiving an associative data structure, the associative data structure being different from the lookup table and associating direct color values in the direct-color image with indices into the color lookup table; and for each pixel of the indexed-color image, performing a lookup operation in the associative data structure to determine whether a corresponding direct color value was previously associated with an index value. If the corresponding direct color value was previously associated with an index value, then the associated index value is used as the pixel value. Otherwise, an entry in the color lookup table is selected for the corresponding direct color value of the pixel, the index value of the selected entry is used as the pixel value, and the index value of the selected entry is associated with the corresponding direct color value in the associative data structure.
Advantages that can be seen in implementations of the invention include one or more of the following. The invention uses an associative data structure, such as a hash table, to provide good speed performance in converting direct color values to index values. The use of associative data structures provides for more accurate results compared to the approximations resulting from the use of the 555 lookup table algorithm or the tree algorithm.
REFERENCES:
patent: 5068644 (1991-11-01), Batson et al.
patent: 5517334 (1996-05-01), Morag et al.
patent: 5764807 (1998-06-01), Pearlman et al.
patent: 5963201 (1999-10-01), McGreggor et al.
patent: 6225974 (2001-05-01), Marsden et al.
Adobe Systems Incorporated
Chen Wenpeng
Fish & Richardson P.C.
LandOfFree
Color table inversion using associative data structures does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Color table inversion using associative data structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Color table inversion using associative data structures will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3212831