ph@miro.Berkeley.EDU (Paul Heckbert) (12/24/88)
The topic of color image quantization seems to recur in comp.graphics every three months or so. Sometimes it's satisfying, to see others citing my work, but other times... In article <571@epicb.UUCP> david@epicb.UUCP (David P. Cook) writes: > The simplest method of reducing a 24 bit colored image to a smaller set > of colors is to do popularity reduction. ... a more complex method, > commonly called Color Cube Compression (devised by Paul Heckbert) ... > The original article for this method may be found in SigGraph proceedings. The paper you're referring to is (in refer(1) format): %A Paul S. Heckbert %T Color Image Quantization for Frame Buffer Display %J Computer Graphics (SIGGRAPH '82 Proceedings) %V 16 %N 3 %D July 1982 %P 297-307 I NEVER CALLED MY METHOD "COLOR CUBE COMPRESSION" AND I NEVER WILL. FLAME{ People could give comp.graphics a tinge of integrity of they'd glance at the references first before summarizing them to the rest of the world }EMALF. Let's get our terminology straight (this is not just my terminology, but the terminology of the image processing/pattern recognition community). QUANTIZATION is a mapping from a continuous domain to a discrete domain or from a large discrete domain to a small one, for instance mapping analog voltage to discrete, 8-bit quantities in a A/D converter, or, to use a political example, categorizing a person as "liberal" or "conservative". COLOR IMAGE QUANTIZATION is quantization of color images, where a common problem is converting 24-bit rgb image data into an 8-bit image and specially selected colormap, so it can be displayed on an 8-bit frame buffer. An extreme example of image quantization is the creation of bitmaps: the quantization of grayscale data to one bit per pixel. This can be done with THRESHOLDING, HALFTONING, or DITHERING. COMPRESSION is transformation of digital data for more efficient storage and transmission, for instance Huffman encoding of arbitrary data streams or run-length encoding of pictures. In the most ambitious forms of compression, anything goes -- in TRANSFORM CODING you transform a signal or picture into, say, the frequency domain and compress it there (with a combination of quantization, masking, and run-length encoding tricks) -- whereas in color image quantization for most frame buffer architectures, you have a fixed number of bits for each pixel, so you can't use run-length, Huffman, transform coding, or any of the other exotic compression techniques. Quantization is thus a specific form of compression. CLASSIFICATION is roughly a synonym for quantization, but its meaning in syntactic pattern recognition is the assignment of an object to a class based on a set of measured features, e.g. classifying a rock based on its color, density, and hardness. In remote sensing, classification usually refers to the categorization of pixels from multispectral satellite data into one of several classes such as "forest", "water", "meadow", "snow", etc. Classification can be either "supervised" or "unsupervised" depending on whether the set of classes is known a priori or not. (The median cut algorithm is thus an unsupervised classification algorithm.) See the book [Duda & Hart, Pattern Classification, Wiley] for more. CLUSTERING is a general term, a synonym for classification. The problem I addressed in my siggraph '82 paper was color image quantization. I discussed two algorithms for doing this, which I called the popularity algorithm and the median cut algorithm. As David mentioned, the popularity algorithm makes a histogram of the colors in the picture and selects the K most frequent as the colormap. The median cut algorithm recursively fits a box around the colors used by the picture, in a 3-D color space, and splits the box along the longer dimension at its median. This continues until K boxes are made. The centroid of each is selected as the colormap entry. David failed to mention that prequantization of the original image's colors from 24=8+8+8 bit colors to, say, 15=5+5+5 bit colors is critical to the popularity algorithm's success. Prequantization clusters nearby colors, ameliorating the general flaws in the popularity algorithm. I mentioned the popularity algorithm in the paper not as a recommended solution, but as a simpler algorithm with which to contrast the superior median cut algorithm. In my paper I also mentioned that Euclidean distance in RGB space is not a good color difference metric, that more perceptual color spaces would give better results. There are a number of variations on the median cut algorithm that I and others have explored. In the paper, I split the boxes recursively, developing a balanced binary k-d tree [Bentley & Friedman, Data Structures for Range Searching, Computing Surveys, Dec. 1979], but a better variation is to always split the largest, or perhaps the most populous box. I also mentioned a variation we can call "variance minimization" in which the box is split at the point that minimizes the sum of variances of the two sub-boxes. Wan, Wong, and Prusinkiewicz have investigated variance minimization and found that always splitting the box with the maximum variance, along the axis with maximum variance, at the plane that minimizes the sum of the new variances, is the best heuristic among the algorithms they tested at minimizing the mean squared error of the whole quantization. They took a more quantitative and objective approach rather than a more perceptual, subjective one. See their paper: %A S. J. Wan %A K. M. Wong %A P. Prusinkiewicz %T An Algorithm for Multidimensional Data Clustering %J ACM Trans. on Mathematical Software %V 14 %N 2 %D June 1988 %P 153-162 %K quantization, clustering %Z discusses alternatives to median cut and k-means Campbell et al described a "Color Cell Compression" algorithm at SIGGRAPH 86, which is properly titled because it is not just a quantization scheme. In CCC, each 4x4 cell of pixels is represented by two colors, the pattern of which is indicated by a 4x4 bitmap, and which are each encoded by 8-bit color indices into a colormap constructed with the median cut (or similar) color image quantization algorithm. They achieve compression to 2-bits per pixel with good results for certain types of images. Their method is properly called compression and not quantization because each pixel is not encoded by a unique group of bytes. Their paper was: %A Graham Campbell, et al %T Two Bit/Pixel Full Color Encoding %J Computer Graphics (SIGGRAPH '86 Proceedings) %V 20 %N 4 %D Aug. 1986 %P 215-223 %K color image compression, color image quantization ---- And finally, In reference to my paper, keithd@gryphon.com (Keith Doyle) said: > I'm still chasing a copy of this article, though I have been able to > piece together much of it from various postings and other references. Please don't trust what you hear on the net (including what you're reading right now (except for this paragraph))! Go to the original sources! Get it from the horse's mouth! Implement algorithms you read about before trusting them! Happy researching, Paul Paul Heckbert, CS grad student 508-7 Evans Hall, UC Berkeley UUCP: ucbvax!miro.berkeley.edu!ph Berkeley, CA 94720 ARPA: ph@miro.berkeley.edu