Method of color quantization in color images

Details Method of color quantization in color images Method of color quantization in color images

2000-01-26

2004-01-13

Boudreau, Leo (Department: 2721)

Image analysis

Color image processing

C358S518000, C358S001900

Reexamination Certificate

active

06678406

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to the processing of two-dimensional color images. More particularly, the invention relates to methods for assigning to each pixel of such an image a symbol representing a selection from a limited set of colors.
ART BACKGROUND
It is well known from studies of color perception that any color can be reproduced in a suitable display device as a combination of three primary colors. Thus, for purposes of image storage, transmission and display, it is convenient to represent the color of each pixel of a digitized image by specifying three coefficients, each representing the contribution from a respective primary color. Because human beings perceive a continuous range of colors, it would, in principle, require an infinite amount of information to specify any one particular color. That is, each of the three coefficients would be of unlimited length.
Such a representational system would of course be impractical. However, it has been found sufficient, for many purposes, to replace the continuous range of colors by a discrete set of colors. The specification of a discrete set of colors is referred to as “color quantization.” For example, a so-called full-color display system allocates eight bits to each of the three primary color coefficients. Therefore, each color in such a system is specified by a total of 24 bits, and the total number of specifiable colors is therefore 2
24
, or about seventeen million separate colors.
In fact, there are many applications in which an even smaller selection of colors suffices. Thus, for example, a string of fewer than 24 bits, typically of only 8, 12, or 16 bits, represents each displayable color in most currently available display monitors. Here, we refer to each such string as a “symbol.”
Typically, some subset of available colors, referred to as the “color codebook,” is selected from the full color set. The selection may be the same for all images, in which case the color codebook is said to be “image independent.” Alternatively, the selection may be specially adapted for individual images or groups of images. In that case, the color codebook is said to be “image dependent.”
Each symbol serves as an index into the color codebook, for retrieving a corresponding color. Thus, a given symbol does not necessarily bear a direct relation to the three primary color coefficients that would be used in a display to reconstruct the corresponding color. Instead, the information necessary for reconstruction would be retrieved from stored information.
In fact, the symbols in many conventional color codebooks are randomly assigned and bear no correlation with the underlying colors. As a consequence, the digital processing of color information in conventional systems cannot take place directly at the symbolic level. Instead, each symbol must be converted to a point in a multidimensional color space for processing.
By contrast, the “color” values of gray-scale images fall along a single axis, i.e., a one-dimensional space. As a consequence, each pixel of such an image is readily assigned a symbol that relates directly to the quantized gray-scale value of that pixel. Simple and computationally fast algorithms are available for performing spatial filtering and other processing of gray-scale images that have been color-quantized in such a manner.
Until now, however, there has lacked any method for quantizing color images that affords similar advantages of simple and computationally fast image-processing algorithms that operate, at least partially, in the symbolic domain.
SUMMARY OF THE INVENTION
We have invented a new method of color quantization. According to our method, a luminance value is selected from a discrete set of quantized luminance values, and a chrominance value is selected from an ordered discrete set of quantized chrominance values. A color symbol is composed from an index of the selected luminance value and an index of an ordinal position of the selected chrominance value, and the color symbol is stored.
In particular embodiments of our invention, the discrete sets of quantized luminance and chrominance values are obtained by quantizing a continuous three-dimensional color space. This is done, in effect, by partitioning the color space into planes of constant luminance, and sampling each resulting plane at a substantially uniform spatial distribution of discrete points.
Significantly, an order is imposed on the sampled points in each plane. Symbols are assigned to the sampled points. Each assigned symbol identifies the luminance level and the ordinality of the corresponding point in color space.
The resulting set of symbols bears a close relationship to the structure of the underlying color space. As a consequence, processing of the color information can be carried out, at least partially, at the symbolic level. This affords advantages of simple and computationally fast processing enjoyed hitherto only in the processing of gray-scale images.
Advantageously, the sampled three-dimensional color space is a space in which the Euclidean distance between two points corresponds to the perceptual difference in color between those points. Within each constant-luminance plane, the sampled points advantageously constitute a spiral lattice. In such a lattice, the radial position of the n'th point is a real power of n, and the angular position of the n'th point is a multiple of n given by 2&pgr;&eegr;&ggr;, where &ggr; is a real number, preferably in the vicinity of a Markoff irrational number. In specific embodiments of the invention, the spiral lattice is a Fibonacci lattice, i.e., a spiral lattice in which the radial position is given by the square root of n, and &ggr; is approximately equal to
±
5
-
1
2
·


REFERENCES:
patent: 5233413 (1993-08-01), Fuchsberger
patent: 5394518 (1995-02-01), Friedman et al.
patent: 5450216 (1995-09-01), Kasson
patent: 5517334 (1996-05-01), Morag et al.
patent: 5544284 (1996-08-01), Allebach et al.
patent: 5668890 (1997-09-01), Winkleman
patent: 0 555 835 (1993-08-01), None
G. Wyszecki et al.Color Science, John Wiley, New York (1982).
Pei, Soo-Chang, et al., “Color Image Processing by Using Binary Quaternion-Moment-Preserving Thresholding Technique”,IEEE Transaction On Image Processing, vol. 8, No. 5, pp. 614-628 (1999).
A. Zaccarin, et al. “A Novel Approach for Coding Color Quantized Images”,IEEE Transactions On Image Processing, vol. 2, No. 4, pp. 442-453 (1993).
M. T. Orchard, et al., “Color Quantization of Images”,IEEE Transactions On Signal Processing, vol. 39, No. 12, pp. 2677-2690 (1991).
G. Sharma, et al., “Digital Color Imaging”,IEEE Transactions On Image Processing, vol. 6, No. 7, pp. 901-932 (1997).

Affiliated with

Also associated with

Rating

Method of color quantization in color images does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of color quantization in color images, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of color quantization in color images will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3215378