Digital display systems with color lookup table architecture are now quite common. The number of colors provided by a color lookup table system is equal to the number of registers in the system. Although it is advantageous in the fields of animation and image processing to increase the number of colors, the capacity of the color lookup table must be increased, which leads to the rise of cost. However, since image quality lowers if the number of colors is decreased, there is a tradeoff between the cost and image quality. Therefore, the problem is how to display color images effectively using a color lookup table of a limited capacity, in other words, which colors should be stored in the color lookup table.
A number of studies on the method of selecting colors stored in the color lookup table have been carried out, and these may be roughly divided into uniform sampling and tapered or adaptive sampling techniques. Uniform sampling is a method for sampling a color space such as RGB space, XYZ space, HLS space or L*u*v* space at equal intervals.
In this context, colors are represented by triplets, such as red, green and blue components and each color can then be defined by coordinates of a three dimensional space, or color space. The RGB space is that defined by red, green and blue components. The XYZ space is a space in which the entire spectrum of visible light can be represented by positive values of coordinates X, Y and Z. The HLS space is one in which each color is defined by hue, saturation and lightness coordinates. The L*u*v space is one in which the coordinates are defined such that the coordinate values correspond linearly with human color perception. XYZ and L*u*v spaces are described in more detail in "Uniform Color Scale Applications to Computer Graphics" by J. Tajima, which appeared in COMPUTER VISION, GRAPHICS, AND IMAGE PROCESSING, Vol. 21, No. 3, pp. 305-325, March 1983.
In adaptive sampling, the content of the table is changed depending on images to be displayed. A process for color image quantization by adaptive sampling is described below. It is assumed that the color space is the RGB space.
(1) Create a histogram by sampling an input image having n bits for each of the R, G and B components in a space having n bits for each of the R, G and B components where m is larger than n. The reason for the difference between m and n is that, though the space may be defined with high precision, related to m bits (e.g. 8 bits per primary color), the histogram can not be efficiently produced with this precision, so is calculated using n bits (e.g. 4 bits per primary color) by taking the n most significant bits of each m bit group.
(2) Select colors (representative colors) to be stored in the color lookup table from the histogram figures.
(3) Map each selected color in the RGB space into the lookup table.
(4) Assign to each pixel an appropriate color in the table.
The steps which greatly affect the quality of displayed images are (2) and (4). In step (3), calculation speed is important. In step (4), if the mapping calculated in step (3) is used as it is, clear stripes are often seen in the region where colors vary smoothly, due to the quantization error. In order to decrease the quantization error, various methods such as the random noise method and error diffusion method have been developed. For step (2), some algorithms such as the popularity algorithm in which representative colors are selected from the histogram in order of frequency, and population equalization algorithm in which the RGB space is divided into a plurality of subspaces corresponding to available representative colors, respectively, each subspace containing the same number of pixels. The former and latter algorithms are disclosed in P. Heckbert, "COLOR IMAGE QUANTIZATION FOR FRAME BUFFER DISPLAY", ACM SIGGRAPH '82, pp. 297-307, July 1972, and Japanese Patent Application No. 59-84259, respectively.
Although the color image quantization methods heretofore proposed have been satisfactory when only one image is displayed, there are some problems if a plurality of images are to be displayed simultaneously on a screen, because different images usually use different colors. For example, if colors to be stored in the color lookup table are selected by uniform sampling, a difference between a color of the original image and a color actually displayed is relatively small, but clear stripes appear in a region with a uniform chromaticity and smoothly varying brightness. In the case of adaptive sampling, since a plurality of images are processed collectively, the whole table must be rewritten each time an image is changed. Furthermore, in adaptive sampling, since frequently used colors are selected, a color of lower frequency may differ greatly from a color actually displayed.