Video monitors display color images by modulating the intensity of the three primary colors (red, green, and blue) at each pixel of the image. In a digitized color image, each primary color is usually quantized with 8 bits of resolution in order to eliminate distinguishable quantization steps in luminance, color hue and color saturation. Thus, full color, digital display systems use 24 bits to specify the color of each pixel on the screen. Because the cost of high speed, high resolution monitors make many applications impractical, an alternative approach used by many less costly displays, is to provide a limited number of bits, such as 8, for specifying the color at each pixel. The user is then allowed to define a mapping between those 2.sup.8 =256 values and the full range of 2.sup.24 =16,777,216 colors. The set of colors available through this mapping is called palette.
Before proceeding further several definitions are useful. Quantization is the process of assigning representation values to ranges of input values. In image processing, the value being quantized can be an analog or digital signal Color image quantization is the process of selecting a set of colors to represent all the colors of an image, and computing the mapping from color space to representative colors. The invention described herein is an improved method for color image quantization and for applying the quantized colors to a pixel map to yield the highest quality image.
A number of approaches have been suggested for the design of color palettes that involve iterative refinement of an initial palette. See for instance: G. Braudaway, "A Procedure for Optimum Choice of a Small Number of Colors from a Large Color Palette for Color Imaging," IBM internal report, RC 11367 (#51227), Sept. 16, 1985, and P Heckbert, "Color Image Quantization for Frame Buffer Display," Computer Graphics, vol. 16, no. 3, pp. 297-307, July 1982.
Heckbert's method constructs an initial palette by assigning to each color from the palette an approximately equal number of pixels in the image. To improve this initial color palette, ar iterative procedure is performed, derived from the Lloyd-Max method for quantizer design, which attempts to minimize the total squared error (TSE) between the original pixels and colors assigned from the palette.
Braudaway proposes constructing an initial color palette by centering colors at peaks in the color value histogram. To avoid concentrating too many colors about one peak, the histogram values are reduced in a region surrounding each assigned color after the color is selected. Beginning at this initial palette, the same iterative approach is used as employed by Heckbert. The iterative procedure attempts to minimize the TSE, but converges only to a local minimum which is greatly influenced by the choice of the initial color palette. Since the initial color palettes in both methods do not attempt to minimize TSE, the local minimum which is reached is unlikely to be close to the global minimum. In addition, the iterative procedure is computationally intensive since, at each iteration, it requires a search of the full color palette for each pixel.
Once a color palette has been selected, pixel mapping involves assigning a color from the palette to each pixel in the image in a way which produces the highest quality display. In many applications, the efficiency of algorithms for performing color palette design and pixel mapping is important. This is particularly true in applications involving large image data bases. In such applications, images are in some common format which must be displayed on monitors having different limitations of color palette size. This requires that each display design its own color palette and perform pixel mapping after receiving each image.
Even if the color palette is transmitted with each image, standard image coding techniques require that pixel mapping be performed locally by each display system. This is because standard image coding techniques make use of the high correlation between the values of the primary colors of neighboring pixels to reduce transmission bit-rates. The color palette indices of neighboring pixels are not highly correlated and, therefore, cannot be coded with high efficiency. Thus, each local display must either design a color palette for each received image or, if a color map is provided, perform pixel mapping of the primary color values contained in the decoded image.
Accordingly, it is an object of this invention to provide an algorithm for color image quantization which selects the best set of colors, called a color palette, to represent an image containing a much larger set of colors.
It is another object of this invention to provide an algorithm which maps the pixels of an image with colors from a color palette to yield the highest quality color image, within the capabilities of a display system.
It is a further object of this invention to provide an algorithm for color image quantization and pixel color mapping which is computationally efficient.