Image analysis – Histogram processing
Reexamination Certificate
1999-01-15
2002-06-25
Mehta, Bhavesh (Department: 2621)
Image analysis
Histogram processing
C358S522000
Reexamination Certificate
active
06411730
ABSTRACT:
BACKGROUND
The present invention relates generally to processing and displaying digital images. A digital image is a raster of rows and columns of picture elements, or “pixels.” The color of a given pixel is defined in accordance with a “color space,” which provides a data representation for a range of colors (a “color gamut”) in terms of basic color components (or “colorants”). A pixel's color is generally represented by a series of bits (the “color value”), with specific bits indicating the amount of each colorant used in the color. The specific colorants depend on the color system used. For example, in the CMYK color system, colors are represented as combinations of values for cyan (C), magenta (M), yellow (Y), and key (K) (generally black); in an RGB color system, colors are represented as combinations of values for red (R), green (G), and blue (B); and in the HSV color system, colors are represented as combinations of values for hue (H), saturation (S) and value (V). Thus, a 24-bit RGB data representation may allocate bits 0-7 to indicate the amount of red, bits 8-15 to indicate the amount of green, and bits 16-23 to indicate the amount of blue. Such a representation can produce a pixel in any one of nearly 17 million different pixel colors (i.e., the number of unique combinations of 256 intensity values of red, green, and blue). By contrast, systems that allocate fewer bits of memory to storing color data can produce only images having a limited number of colors. For example, an 8-bit color image can include only 256 different colors.
Although digital images are often created using 24 bits of color information, images are often compressed or “quantized” to conserve memory and decrease processing times. A typical digital image, even one created using 24 bits to store color information, may include only a relatively small number of colors. For more complex images, quantization (usually from 24 bit to 8 bit color) necessarily results in the loss of color resolution, raising the questions what set or palette of colors to use to display the image (a “display palette”), and how to map the remaining or “missing” image colors into the display palette.
One approach is to use a predetermined display palette and a fixed mapping from image colors to display palette. For example, an RGB color space may be divided into 256 equal-sized color regions and one display palette color may be selected from each region. The image may then be mapped into the display palette, with the missing colors being mapped to the closest color in the display palette (measured by proximity in an RGB color space).
Another approach is to select the display palette based on the actual distribution of colors in the image (often called “adaptive palettes”). For example, a “popularity algorithm” may be used to create a histogram of colors in the image and select the most frequent colors to use as the display palette. In this approach, the color space is again divided into a number of equal-sized regions—for example, 32,768 or more regions, corresponding to 32 or more divisions on each color axis in an RGB color space. The image colors are mapped to the region they fall in, and the 256 most popular regions are selected. One display palette color is selected from each of these 256 regions, and the image is mapped to the display palette with missing colors being mapped to the closest color in the display palette.
In a related approach, the quantization algorithm begins with an initial histogram stored as a list of colors in the image. Upon reaching a predetermined memory limit, the algorithm defaults to a low resolution histogram of predetermined size. This low resolution histogram is then used to generate a palette of colors to display the image as described above.
Another alternative is the use of an “octree” algorithm to obtain a palette of the K most popular colors in the image, where K is a predetermined number of “leaves” in the tree. In this method, the colors of the image are sequentially read into the octree and associated color counts are stored in leaves. For each new color, if the tree has fewer than K leaves with non-zero counts, the color is filtered down the tree until it reaches the leaf corresponding to the color. If the tree already has K leaves, a set of leaves are merged to make room in the tree for the new color. After the entire image has thus been processed, the display palette consists of the set of representative colors associated with each leaf, and the image is mapped to that palette.
SUMMARY
The invention provides methods for generating data structures representing the frequency with which colors occur in a collection of colors, such as occurs in a raster image, and apparatus (include computer program products) implementing or embodying the methods of the invention.
In general, in one aspect, the invention features a method of generating a data structure representing the frequency with which colors occur in a raster image. The method includes providing a list consisting essentially of first generation entries, each first generation entry having an associated color set of one or more colors, each first generation entry representing the frequency with which colors in the associated color set appear in the image, the color sets for all of the first generation entries being mutually non-intersecting; and combining first generation entries to form a list consisting essentially of second generation entries.
Implementations of the invention can include one or more of the following advantageous features. Each first generation entry and second generation entry includes an index identifying the color set. Each color set corresponds to a volume in a color space. The frequency is represented as a count. Each second generation entry has an associated second generation color set of one or more colors, each second generation entry representing the frequency with which colors in the associated color set appear in the image, the color sets for all of the second generation entries being mutually non-intersecting. Each second generation color set corresponds to a volume of the color space. All second generation color sets are of the same size. The method also includes using the list of second generation entries to generate a palette representing the colors in the image. The method also includes combining second generation entries to form a list consisting essentially of third generation entries. Each third generation entry has an associated third generation color set of one or more colors, where each third generation entry represents the frequency with which colors in the associated color set appear in the image, and the color sets for all of the third generation entries are mutually non-intersecting. The method also includes using the list of third generation entries to generate a palette representing the colors in the image.
In general, in another aspect, the invention features a method of generating a histogram for a collection of colors in which any color may occur zero, one, or more times, where the colors are selected from a range of color values in a color space. The method includes dividing the range of color values using an first set of divisions to define a first set of disjoint, uniform volumes in the color space; providing a first list consisting essentially of first generation entries, each first generation entry being associated with exactly one distinct volume of the first set of volumes; storing in an entry frequency data representing the frequency with which a color value within the associated volume occurs in the collection of colors; dividing the range of color values using a second set of divisions to define a second set of disjoint, uniform volumes in the color space; and creating a second list from the first list, the second list consisting essentially of second generation entries, each second generation entry being associated with exactly one distinct volume of the second set of volumes and storing combined frequency data for color values in the associated volume.
Implementation
Bartell Jason T.
Cox Christopher B.
Adobe Systems Incorporated
Fish & Richardson P.C.
Mehta Bhavesh
LandOfFree
Histogram for generating a palette of colors does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Histogram for generating a palette of colors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Histogram for generating a palette of colors will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2953477