po0o+@andrew.cmu.edu (Paul Andrew Olbrich) (12/12/88)
Hi-ho, I know that this was mentioned before, but I was unable to find any references on it after a quick direct look, so .. Can anyone give me some references to articles on optimizing a color palette. (That is, if I have a 24 bit color image, but my video buffer only handles 256 colors at a time, how do I go about choosing the "best" 256 colors to use, rather than just taking an evenly distributed sample of the 16M colors available?) Just explaining a good (and effective) way of doing this would be usefull, too. Thanks! Drew Olbrich po0o+@andrew.cmu.edu
Classic_-_Concepts@cup.portal.com (12/19/88)
Drew Olbrich writes: > "....Can anyone give me some references...on optimizing a color palette > (That is, if I have a 24 bit color image, but my video buffer only handles 56 colors at a time, how do I go about choosing the "best" 256 colors..." Drew you've bitten off a big one here, since the answer lies not only in mathematics, but in perception and biology, as well. You'll find that colors which are mathematically close or distant will not match perceptually in the same degree. That is, palette colors which are separated by 10 or 15 numbers may appear the same to the human eye in one part of the palette and quite different in another, particularly if it hits a 'color boundary'. To compli- cate matters, each system relies on a different color selection system and mapping system--a solution on one won't work on another. For the time being, writing a 'visual selector' and running through the palette with 'yes/no' re- sponses after the field has been narrowed mathematically to 350 or so might be the best strategy. It will at least eliminate those which are visual 'duplicates' or unacceptably unattractive colors. (continued...)
Classic_-_Concepts@cup.portal.com (12/19/88)
Drew Olbrich's query on selecting the 'best' palette colors, cont'd It may be possible, given the perceptual complications that the most effici- ent solution to this problem lies not in a mathematical algorithm, but in a 'database' approach. If someone were to go through each color/family of colors and visually 'identify' and mathematically code 'best' choices and store this information in some numerical form that could be used by other programs and programming languages, then it need only be done once (obvious- ly, given differences in systems approaches to storing and generating the colors, this is a bit idealistic, but for the purpose of discussion...) and made available through public domain channels. Julie Petersen, Computer Artist/Writer
jevans@cpsc.ucalgary.ca (David Jevans) (12/20/88)
Several articles have been written on choosing the best N colors
from >N. I don't have them in front of me right now, but there was
one in SIGGRAPH '84 (I believe, it may have been another year) on
reducing a 24 bit color space down to a smaller number of bits.
A median split algorithm is presented.
An article in the proceedings of CGI '88 (Springer-Verlag press)
describes an octree reduction of the 24 bit color cube down to
however many bits you have available. I implemented this and posted
the source here a couple of months ago. I use it for displaying
24bit (16 million colors) images on an 8bit color SUN (256 colors).
Maybe this helps?
Note: Picking the most used 256 colors doesn't work. You want to
chose the best colors (this may involve making new colors
which may not be present in your source image).
David Jevans, U of Calgary Computer Science, Calgary AB T2N 1N4 Canada
uucp: ...{ubc-cs,utai,alberta}!calgary!jevansdavid@epicb.UUCP (David P. Cook) (12/20/88)
The simplest method of reducing a 24 bit colored image to a smaller set of colors is to do popularity reduction. This this method, count the number of unique colors in the 24 bit image, keeping track of their frequency (ie.. how many pixels are color #1, how many are color #2 etc..) Now... to reduce to your 56 required colors, only take the 56 most frequent colors from the original image. Scan the image converting each color to the closest color from the list of 56 reduced colors. This method has the drawback that it does not preserve small areas of color. For example, of you have an image which is mostly redish, but has small quantity of other colors (consider a photograph of a person with bright green eyes... the person is primarily redish but the eyes present a small area of green... an area we wish to preserve). To do this, you must go to a more complex method, commonly called Color Cube Compression (devised by Paul Heckbert). In this method, you determine the corners of the color space used by the image in question. This will give you a cube (if you have never seen a RGB color cube, consult Fundamentals Of Interactive Computer Graphics.. or any other computer graphics book) which sits somewhere within total RGB color space. Now, the method consists of subdividing the large color cube into (in your case) 56 sub cubes. This is accomplished by always dividing the cube along the LONGEST AXIES. The division point should be as close to 1/2 the frequency of the axies as possible. For example, if the longest side is the Black-To-Red side, than your first subdivision should be along this side... at the point where approximatly 1/2 of the black-to-red pixels are on the left of the division, and the other half are on the right of the division. This subdivison continues, EACH TIME WITH THE LONGEST AXIES (ie. the longest axies after the last subdivision) until you have 56 (in your case) sub-cubes. Now, average all the colors for each sub-cube such that you end up for an average color per sub-cube. Now... to convert your image, simply read each pixel in the original image... determine which sub-cube they exist in and replace that pixel with the average for the sub-cube. In this way, small areas of vastly differing colors may be preserved. The original article for this method may be found in SigGraph proceedings. -- | David P. Cook Net: uunet!epicb!david | | Truevision Inc. | "Sometimes I cover my mouth with | | Indianapolis, IN | my hand to tell if I'm breathing" | -----------------------------------------------------------
keithd@gryphon.COM (Keith Doyle) (12/22/88)
In article <571@epicb.UUCP> david@epicb.UUCP (David P. Cook) writes: >To do this, you must go to 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. 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. The one question I have about the color-cube compression is that it appears the weighting of the color values is not addressed in these or the related algorithms. Example: let's say a given image is using 4096 colors, R 0-15, G 0-15, B 0-15. If 90% of these colors are used by only one pixel, yet another image using the same colors has a similar characteristic but the 10% colors used more often are completely different colors. The basic algorithm would seem to select the exact same palette based on the colors used, without taking which colors were used how much into any consideration. While I can see that when you are tallying the number of data points within a given sub-cube you could treat a color used by 300 pixels as 300 data points instead of 1, this could result in a single cube being selected for subdivision containing the most data points, yet all these points represented by a single color and unable to be subdivided further. I suppose then, the algorithm could mark such a sub-cube as unable to be further subdivided, and then ending the algorithm if all the cubes have been so marked if it occurs before reaching the desired number of cubes by subdivision. Is this a correct approach? The references I've been able to find so far leave out minor details like this. Keith Doyle keithd@gryphon.COM gryphon!keithd gryphon!keithd@elroy.jpl.nasa.gov
jlg@hpfcdq.HP.COM (Jeff Gerckens) (12/22/88)
Actually, a very close approximation to a linearly perceptual space can be obtained by converting the RGB values to CIELUV values. This allows use of mathematical averaging and distance metrics for closest color matches. CIELUV is defined in Supplement 2 to Publication 15 of the C.I.E., or can be found in "Color Science" by Wsyzecki (sp?).
kundert@cpsc.ucalgary.ca (Perry Kundert) (12/22/88)
If any is interested, I have implemented the sigGraph algorithm
for RGB space optimization. It seems to work fairly well, and,
although the code is twisted, it should be usefull at least
as a starting point. Mail me if you want the source.
"Stupidity cannot be cured | surface: Perry Kundert
with money, or through | 1089 Northmount Dr. N.W.
education, or by legislation." | Calgary, Canada, T2L 0C1
-RAH | uucp: {ubc-cs,utai,alberta}!calgary!kundertClassic_-_Concepts@cup.portal.com (12/22/88)
More thoughts on reducing palettes, since I have done a great many color
graphic images ...
One of the problems with sampling across the spectrum in a palette
reduction algorithm is that it ignores 'families of colors'. If you were
creating an image of a sunset--your palette would be predominantly reds,
yellows, blacks. If you imaged a china teapot (now who would want to do
that!), the palette changes to whites, beiges and whatever the background
is. Since image integrity is greater when you get as much mileage out of
a limited palette as possible, it is preferable to maintain it. Thus, if
you MUST do it algorithmically, it would be better, given a system with
sufficient speed, to 'sample' the image palette BEFORE algorithmically
selecting the 'best' colors. So, a possible scenario... Start from a
'database' (following the rationale in my previous post) including percep-
tually distinct and pleasing colors, sample the image to be displayed to
determine 'like' choices (i.e., family of colors), perform palette reduc-
tion to related colors. Display image. Julie Petersen
annala@neuro.usc.edu (A J Annala) (12/22/88)
It seems to me that in attempting to develop an algorithm for
maximizing the use of a 256 entry color table to represent the
spectrum present in a 24+ bit color table image that one might
want to us the peak frequency and decay curve of visible light
frequencies that can be detected by the three primary (LWS=R,
MWS=G, SWS=B cone system) and the sole secondary (rod system)
optical image detectors in the human eye. The pigments that
are used to capture optical radiation (before transforming it
via a high gain chemical [cGMP] amplification cascade) capture
light at the the following peak wavelengths:
RED cones (long wavelength system) = 419 nm
GREEN cones (medium wavelength sys) = 531 nm
BLUE cones (short wavelength sys) = 559 nm
rods (when simult active w/cones) = 496 nm
The ability of the eye to discriminate color differences must
be a product of the encoding made possible by light absorbed
at these wavelengths. Therefore, a system for compressing the
most significant perceived color spectrum in a given image may
need to take note of the device characteristics of the primary
optical radiation detectors as well as possible post processing
by higher cognitive centers.
In any case, maybe just one of the computer scientists and/or
electrical engineers out there might become interested in using
neurophysiological systems analysis of human visual perception
to design a more appropriate algorithm for compressing the code
for colors represented in a given image. I would be happy to
provide references to primary sources for anyone interested in
pursuing this approach to the palette optimization problem.
AJ Annala, USC Neuroscience Programbdb@becker.UUCP (Bruce Becker) (12/27/88)
In article <390024@hpfcdq.HP.COM> jlg@hpfcdq.HP.COM (Jeff Gerckens) writes: >[...] >CIELUV is defined in Supplement 2 to Publication 15 of the C.I.E., or >can be found in "Color Science" by Wsyzecki (sp?). /^^^^^^^^^^^^^\ ________/ \________ I'm looking for a second-hand copy of this, if anyone has it for sale. Thanks, -- Bruce Becker Toronto, Ont. Internet: bdb@becker.UUCP, bruce@gpu.utcs.toronto.edu BitNet: BECKER@HUMBER.BITNET
raveling@vaxb.isi.edu (Paul Raveling) (12/31/88)
We've implemented a color selection algorithm that differs a bit from the others I'm familiar with. I've drafted a paper about it, but would frankly prefer to do a refined variant of this algorithm before publishing. In comparisons with Paul Heckbert's median cut algorithm, it produces better results on many images, about the same on a most, and does relatively poorly on some. One virtue is that it's tunable -- it's possible to change one key number to change its bias toward how to select colors. This algorithm operates by classifying an image's colors into a tree, much like an octree, then reducing the tree by pruning upward from the leaves, and finally reclassifying pixels in the reduced tree. Classification produces a count of the number of pixels which classify into and through each node; in fact, each level of the tree can be viewed as a histogram at a particular resolution of prequantization (e.g. 1st level below root represents colors at 1-bit resolution, 2nd level at 2 bits, etc). The first cut at reduction chose the least populated nodes to prune and averaged their colors into their parent nodes. The current rendition uses a weighting factor to bias it toward retaining nodes near the top of the tree. This tends to increase the chance that any populated volume of RGB space will be represented in the output image, even if only at limited resolution. If time allows, I hope to do a two-tree variant that would let reduction effectively partition RGB space into volumes of arbitrary shape (not just cubes or boxes). It would be slower than the current version, but offers hope for better color palette optimization. One problem with optimizing color palettes is defining what's optimal. In our experience the most useful measure has been A/B comparisons by human observers. This doesn't always correlate completely with numerical measures such as mean square distance in RGB space. We tried one experiment with mean square distance in a perceptual space, but the results offered no more insight than RGB space. We also defined a "color retention" measure that appears to be meaningful but also doesn't fully support judgements of human observers. If anyone knows of other promising measures of image fidelity or image quality (not necessarily identical!), I'd be eager to hear of them. --------------------- Paul Raveling Raveling@vaxb.isi.edu
cek@notecnirp.Princeton.EDU (Craig Kolb) (01/04/89)
A number of people at the University of Regina have written a paper that describes a variant of Heckbert's median-cut algorithm. The key difference is that rather than always cutting along the 'longest edge' of a box, one makes cuts along axes at points which minimize the variance of the resulting set of representative colors with respect to the original image. Since color space is discrete, one can find these optimal cut-points by exhaustive search. In the paper, "Variance-based Color Image Quantization For Frame Buffer Display", the authors (Wan, Prusinkiewicz and Wong) compare the compression of two images using a number of algorithms, and show that their scheme is 'better' than median-cut, at least in terms of total quantization error. The paper has been submitted to Graphics Interface for publication. I've implemented this algorithm and the results are quite nice. Drop me a line if you'd be interested in a copy of the code. The program makes use of the Utah-Raster toolkit and has display routines for both the color Sun and Iris workstations. Craig Kolb Yale U. Math Department cek@princeton.edu or craig@lom1.math.yale.edu
raveling@vaxb.isi.edu (Paul Raveling) (01/05/89)
In article <13962@princeton.Princeton.EDU> cek@princeton.edu (Craig Kolb) writes: > >In the paper, "Variance-based Color Image Quantization For Frame Buffer >Display", the authors (Wan, Prusinkiewicz and Wong) compare the compression >of two images using a number of algorithms, and show that their scheme is >'better' than median-cut, at least in terms of total quantization error. > >The paper has been submitted to Graphics Interface for publication. > >I've implemented this algorithm and the results are quite nice. Drop me a >line if you'd be interested in a copy of the code. The program makes use of >the Utah-Raster toolkit and has display routines for both the color Sun and >Iris workstations. I'd definitely be interested in code for this algorithm as well as the paper. I'd particularly like to run some comparisons of it against our algorithm and the two implementations of Heckbert's that I've tested. --------------------- Paul Raveling Raveling@vaxb.isi.edu