Histogram for generating a palette of colors

Abstract

Methods and apparatus that generate data structures representing the frequency with which colors occur in a collection of colors, such as occurs in a raster image. The invention provides a list consisting essentially of first generation entries and combines first generation entries to form a list consisting essentially of second generation entries. Each first generation entry has an associated color set of one or more colors. Each first generation entry represents the frequency with which colors in the associated color set appear in the image. The color sets for all of the first generation entries are mutually non-intersecting. Particular embodiments have the following features. Each second generation color set corresponds to a volume of the color space. All second generation color sets have the same size. The second generation entries can be combined to form a list of third generation entries. A list of entries is used to generate a palette In another aspect, the invention features a method of generating a histogram. The method includes (a) dividing the color space into a set of disjoint volumes; (b) for each occurrence of a color in the collection of colors, (i) identifying the volume in which the color is found, (ii) providing an entry associated with the identified volume in a list of entries, where each entry is associated with exactly one distinct volume, and (iii) updating the frequency data of the entry; (c) before all occurrences in the collection have been processed, (i) redividing the color space into a current set of larger, disjoint volumes, (ii) combining original entries in the list so that each resulting entry is associated with exactly one distinct volume and combines the frequency data of the original entries that were combined to form the resulting entry, and (iii) continuing the processing of step (b); and (d) generating a color frequency histogram from the newest entries in the list.