Computer graphics processing and selective visual display system – Display driving control circuitry – Controlling the condition of display elements
Reexamination Certificate
1997-11-12
2003-02-11
Huynh, Ra (Department: 2173)
Computer graphics processing and selective visual display system
Display driving control circuitry
Controlling the condition of display elements
C345S589000, C345S593000, C345S601000, C382S168000
Reexamination Certificate
active
06518981
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention concerns generating and using a color palette, and more particularly, a color palette which can be used for displaying, storing and transmitting color images in a computer or other digital image processing device.
2. Description of the Related Art
To process or display a color image in a computer or other digital image processing device, the color component values for each pixel in the image must be specified. For example, in the RGB (red, green, blue) color space, a color image can be represented by specifying each of the red, green and blue intensity levels for each pixel in the image. In this regard, 8 bits per color have been found to yield visually acceptable results. However, this requires 24 bits per pixel which, given the high resolutions frequently used, can mean that a significant amount of data is required to represent a single color image. Manipulating such a large amount of data requires both a large amount of memory and a large amount of processing time.
Accordingly, conventional techniques have been proposed to use a much smaller set of colors to represent an image. Such a set is conventionally known as a color palette, and often contains 256 different colors. As previously noted, each pixel in a color image is ordinarily represented by 24 bits, which can define 2
24
or more than 16.7 million different colors. Therefore, by replacing each color in a color image with one of the colors in a 256 color palette, each pixel in a color image can be represented by an 8 bit index into the color palette, rather than 24 bits of color information. Moreover, if the palette colors are selected correctly and a unique palette is used for a particular image, in many cases the image quality is not significantly decreased.
One problem then is how to appropriately select the palette colors. Stated another way, given that 24-bit color image data may have up to 16.7 million colors, the problem is how to select 256 out of those 16.7 million colors that will represent the image well.
Various conventional techniques have been proposed for generating palette colors. However, each has its own problems. For example, some conventional techniques do not in many cases select the palette of colors that would provide good visual results for the subject image. Other conventional techniques ignore small isolated colors, even though such colors may be important to the overall impression of the image. Some other conventional techniques are very computationally intensive, and consequently result in slow processing speeds. With still other techniques, after the palette colors are generated, mapping from the image colors to the palette colors is difficult. That is, after the palette colors have been identified, it is cumbersome to identify for each pixel in the input image which palette color is “closest” to the true image color.
SUMMARY OF THE INVENTION
The present invention addresses the foregoing problems by generating a color palette for an image by partitioning the color space into a predetermined number of cells, which is less than the number of colors required in the palette, selecting at least one color from each cell in which an image color exists, and selecting the remaining palette colors based on how the remaining image colors are distributed among the cells.
According to one aspect of the invention, to generate a color palette having m colors (such as 2
8
=256 colors) from a color image described in a color space, pixel image data corresponding to the color image is first obtained. A frequency of occurrence for each color in the pixel image data is then determined. Each color in the pixel image data is assigned to one of a predetermined number (k) of cells into which the color space has been partitioned, where k<m. For instance, each axis of the color space might be divided into 6 approximately equal-sized intervals, resulting in k=6×6×6=216 rectangular box-shaped cells. The most commonly occurring color is selected in each cell in which a color exists, so as to obtain n palette colors, with n≦k. A vote value is calculated for each unselected color, the vote value being based at least in part on the frequency of occurrence of the color in the pixel image and a weighting factor based on a rank of the color in its corresponding cell, the unselected colors being the colors not selected in the first selecting step. Thereafter, the remaining m-n palette colors are selected as the unselected colors with the highest vote values.
By virtue of the foregoing arrangement, each and every original color in the input color image will have a palette color that is close, regardless of how infrequently an original color occurs. As a result, even colors having a relatively low frequency of occurrence in the image can be closely represented in the palette. Moreover, since each palette color is associated with a cell, a structure is inherently provided for organizing the palette colors, and the input image colors can therefore be readily mapped to corresponding palette colors.
According to a further aspect of the invention, a color palette having m colors (such as 256 colors) is generated from a color image having a number of pixels, each pixel described in a color space. The color of each pixel in the color image is first quantized by zeroing least significant bits of each color component for the pixel. The frequency of occurrence of each quantized color is counted. Each quantized color in the color image is assigned to one of a predetermined number (k) of cells into which the color space has been partitioned, where k<m. For instance, each axis of the color space might be divided into 6 approximately equal-sized intervals, resulting in k=6×6×6=216 rectangular box-shaped cells. The most commonly occurring quantized color in each cell in which a quantized color exists is selected, based on the count, so as to obtain n palette colors, with n≦k. The unselected colors in each cell are then ranked based on their relative frequencies of occurrence, with higher ranking colors occurring more frequently than lower ranking colors in the same cell, the unselected colors being the quantized colors not selected in the first selecting step. A weighting factor is calculated for each unselected color, the weighting factor being based on the rank of the unselected color, with higher ranking colors receiving a greater weighting factor than lower ranking colors. A vote value is assigned to each unselected color, the vote value being based at least in part on the frequency of occurrence of the quantized color and the assigned weighting factor for the quantized color. Finally, the remaining m-n palette colors are selected as the unselected colors with the highest vote values.
By virtue of the foregoing, the present invention can simultaneously select palette colors so as to produce good visual results for a variety of input images, identify the palette colors quickly, and provide a structure for organizing the palette colors which permits fast mapping of the input image colors.
According to a still further aspect of the invention, input colors in a color image described in a color space are mapped to a reduced palette of m colors derived by partitioning the color space into a predetermined number of cells, there being at least one palette color in each cell that includes an input color. The mapping is performed by determining in which cell each input color lies, and mapping each input color to the closest palette color from among all palette colors in the cell identified for that input color.
By virtue of the foregoing arrangement, the processing time for mapping of colors in an input color image to the selected palette colors can be reduced, since only distances to palette colors in the same cell need to be calculated.
According to more particularized aspects of the invention, the cell in which an input color lies is determined by finding a three-dimensional vector. The vector is d
Hui Jonathan
Kohler Timothy L.
Zhao Jun
Canon Kabushiki Kaisha
Fitzpatrick ,Cella, Harper & Scinto
Huynh Ra
LandOfFree
Generating and using a color palette does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Generating and using a color palette, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generating and using a color palette will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3151301