schapira@cbnewsm.ATT.COM (alexander.d.schapira) (08/23/89)
Can anyone shed some *light* on algorithms for mapping 24-bit RGB
pixel data (such as found in some image files) into the "best"
EGA or VGA palette?
Any references will be appreciated. Thanks in advance.
-Al Schapira ...!m21ux!ads ads@m21ux.att.commitchell@cbmvax.UUCP (Fred Mitchell - QA) (08/24/89)
In article <3129@cbnewsm.ATT.COM> schapira@cbnewsm.ATT.COM (alexander.d.schapira) writes: >Can anyone shed some *light* on algorithms for mapping 24-bit RGB >pixel data (such as found in some image files) into the "best" >EGA or VGA palette? One way that you can do it is this (since I am not totally familar with how the VGA palette works, you may have to adapt this): NOTE: in all of this, treat all your colors as a R-G-B 'vector'. Determine your target color range in terms of the 24-bit pallette- that is, come up with a color-equivalency table for your target colors (all of them) that matches the 24-bit colors as closely as possible. Next, take a random color sample of your 24-bit image. How large of a sample you'll have to experiment with, but start off with 10 * #target-colors. Next, set up a weighted color-range-substitution table that will basically map the 24-bit colors onto your target palette. Normally, this will simply be the nearest-color match in terms of the RGB representation of your source pixel and target color range. Then determine the relative frequency of the colors for each color range. Take the highest of these and use them for your color palette. Now, just go through each pixel and substitute the 'mapped' color in your table (or the nearest color) and use that as the color for your VGA pixel. Of course, if the size of your source and target images differ, you'll have to deal with that too. This is, I know, a very sketchy description of one possible solution. There may be better and/or faster approaches to this, but what I have described above has been used in a Ray-Tracing package that I am working on. If you need more help, just drop me E-MAIL or call me (voice) at 215-228-7490. -- |*******************************************| -Compliments of /// |* All thoughts and comments are soley *| Fred Mitchell \\\/// |* thoses of The Author and has nothing to *| \XX/ |* do with Commodore-Amiga. *| Software QA - Commodore-Amiga |*******************************************|
gors@well.UUCP (Gordon Stewart) (08/24/89)
The classic paper on this subject is in SIGGRAPH notes (1982?) by
Paul Heckbert, (paraphrased) "Color Image Quantization for Frame
Buffer Display."
Several improvements are possible: some of these are mentioned in the
article, such as using different criteria for selecting a sub-range
to partition.
I myself have a color-selection algorithm which obviates truncating
the pixels to 15 bits. It doesn't use a histogram, but a multi-way
partition method, and if applied using Heckbert's criterion (longest
box),it is equivalent to the Heckbert method using a 24-bit histogram.
The process, as described in Heckbert, is two-fold (possibly three-fold)"
1) Select the best N colors;
2) Render the image via mapping function;
opt. 3) While rendering, apply a dithering scheme to trade spatial
for color resolution (effective if the target N colors are
few - say, 16 or less - though this varies from image to image)
--
{apple, pacbell, hplabs, ucbvax}!well!gors
gors@well.sf.ca.us
(Doolan) | (Meyer) | (Sierchio) | (Stewart)billd@fps.com (Bill Davidson) (08/25/89)
In article <13319@well.UUCP> gors@well.UUCP (Gordon Stewart) writes: >The classic paper on this subject is in SIGGRAPH notes (1982?) by >Paul Heckbert, (paraphrased) "Color Image Quantization for Frame >Buffer Display." It was '82. Most libraries don't carry it. Find people who've been into graphics a while. >I myself have a color-selection algorithm which obviates truncating >the pixels to 15 bits. It doesn't use a histogram, but a multi-way >partition method, and if applied using Heckbert's criterion (longest >box),it is equivalent to the Heckbert method using a 24-bit histogram. I'd like a more detailed description of this. I'm collecting color quantization algorithms (kind of like Jim Blinn and his margarine tubs, er circle algorithms :-). I have several modifications to Heckbert's algorithm as well as a tree-based subdivision algorithm by Paul Raveling. >The process, as described in Heckbert, is two-fold (possibly three-fold)" > > 1) Select the best N colors; This is the median-cut method which *IS* Heckbert's paper. The other two steps are peripheral (but important). If you try and try and can't find a copy of the SIGGRAPH '82 proceedings, send me email and I'll sumarize the method for you. > 2) Render the image via mapping function; >opt. 3) While rendering, apply a dithering scheme to trade spatial > for color resolution (effective if the target N colors are > few - say, 16 or less - though this varies from image to image) Speaking of dithering, I understand how to use Floyd-Steinberg for color. It's quite simple since you keep an error vector in RGB three-space instead of just an error value. This makes sense since it will pull colors back against the error in the adjacent pixels. How would one do an ordered dither in color or does this even make sense? It doesn't make sense to me. Do you set up more matrices? --Bill
jbm@eos.UUCP (Jeffrey Mulligan) (08/26/89)
billd@fps.com (Bill Davidson) writes: >Speaking of dithering, I understand how to use Floyd-Steinberg for >color. It's quite simple since you keep an error vector in RGB >three-space instead of just an error value. This makes sense since >it will pull colors back against the error in the adjacent pixels. I have experimented with transforming the rgb error to luminance and chromatic components, and then diffusing the error using different spread functions for these components, imotivated by the observation that the eye is less sensitive to chromatic modulation than to luminance modulation. This works fairly well, although it is hard to quantify the improvement. >How would one do an ordered dither in color or does this even make >sense? It doesn't make sense to me. Do you set up more matrices? What I've done is just dither r, g, and b independently and then combine them into a 3 (or more) bit image. There are some interesting questions regarding the choice of the three matrices. I am working on a paper on this topic for the February SPIE meeting (to be held in Santa Clara), so if anyone knows of any prior work in the area I would very much like to hear about it. jeff -- Jeff Mulligan (jbm@aurora.arc.nasa.gov) NASA/Ames Research Ctr., Mail Stop 239-3, Moffet Field CA, 94035 (415) 694-6290
rokicki@polya.Stanford.EDU (Tomas G. Rokicki) (08/26/89)
> What I've done is just dither r, g, and b independently and then > combine them into a 3 (or more) bit image. There are some interesting > questions regarding the choice of the three matrices. In my experiments, I've found that using identical matrices is better than using different matrices, whether for ordered dither or classic dither. (Not much you can do about F-S.) This has two advantages and one disadvantage. With coincident matrices, the output simply looks better; there are no extraneous pixels of a very wrong color, just some that are almost off. (Ie, if you had 0.8 r, 0.8 g, and 0.2 b, with coincident matrices, you would never have a blue-only pixel, but with other matrices, you would.) Secondly, at least on some printers, the ability to maximize use of black ink seems to add contrast. As a disadvantage, well, don't do color separations this way---it's unlikely that your printer can duplicate the alignment that closely. -tom
gors@well.UUCP (Gordon Stewart) (08/28/89)
Actually, doing R, G & B separately has a few problems -- that's "taxicab"
distance, rather than Euclidean distance, for one -- the other is that such
an error measure relies on a uniform color metric, and the RGB cube is not
uniform, in that equidistant colors in the color cube are not equidistant
to the "standard" observer's perceptual apparatus.
As for the numerous requests for my color selection method without
histogram, I am trying to work out a paper that gives this as an example of
a novel classification scheme that could be applied to other fields, as well.
--
{apple, pacbell, hplabs, ucbvax}!well!gors
gors@well.sf.ca.us
(Doolan) | (Meyer) | (Sierchio) | (Stewart)pepke@loligo (Eric Pepke) (08/29/89)
In article <13381@well.UUCP> gors@well.UUCP (Michael Sierchio) writes: >Actually, doing R, G & B separately has a few problems -- that's "taxicab" >distance, rather than Euclidean distance, for one -- the other is that such >an error measure relies on a uniform color metric, and the RGB cube is not >uniform, in that equidistant colors in the color cube are not equidistant >to the "standard" observer's perceptual apparatus. One could try other color spaces, such as HSV for example. I have not done this. However, I have done the brighness quantizations in perceptual space, that is, brightness corrected for logarithmic eyeball response and the gamma of the tube. I did not spend a lot of time on this, but the few pictures that I tried indicated that the difference in quality was not worth writing home about. Eric Pepke INTERNET: pepke@gw.scri.fsu.edu Supercomputer Computations Research Institute MFENET: pepke@fsu Florida State University SPAN: scri::pepke Tallahassee, FL 32306-4052 BITNET: pepke@fsu Disclaimer: My employers seldom even LISTEN to my opinions. Meta-disclaimer: Any society that needs disclaimers has too many lawyers.
mitchell@cbmvax.UUCP (Fred Mitchell - QA) (08/29/89)
In article <13381@well.UUCP> gors@well.UUCP (Michael Sierchio) writes: >Actually, doing R, G & B separately has a few problems -- that's "taxicab" >distance, rather than Euclidean distance, for one -- the other is that such >an error measure relies on a uniform color metric, and the RGB cube is not >uniform, in that equidistant colors in the color cube are not equidistant >to the "standard" observer's perceptual apparatus. What you state is true, but you must keep in mind that we are going from 16 million colors to 16 or 64 colors. The amount of error encountered would not be significant enough to be noticed at such a color quantization level. Also, I've neglected to consider dithering in my approach, which should've been addressed, but I am in the process of working out the details. If you know of a *fast*, reasonably accurate algorithm to accomplish this, then by all means, tell! My current implementation (written in 'C' on a 68000-based machine) takes about a minute to process a 24-bit image down to a 32-color pallette, at 320x400. With optimization, I could speed it up a bit, but I would rather have it do it in 1/10 the time. Speed is of the esscence! -- |*******************************************| -Compliments of /// |* All thoughts and comments are soley *| Fred Mitchell \\\/// |* thoses of The Author and has nothing to *| \XX/ |* do with Commodore-Amiga. *| Software QA - Commodore-Amiga |*******************************************|
billd@fps.com (Bill Davidson) (08/30/89)
In article <13381@well.UUCP> gors@well.UUCP (Michael Sierchio) writes: >Actually, doing R, G & B separately has a few problems -- that's "taxicab" >distance, rather than Euclidean distance, for one -- the other is that such >an error measure relies on a uniform color metric, and the RGB cube is not >uniform, in that equidistant colors in the color cube are not equidistant >to the "standard" observer's perceptual apparatus. and then: In article <126@vsserv.scri.fsu.edu> pepke@loligo.UUCP (Eric Pepke) writes: >One could try other color spaces, such as HSV for example. I have not done >this. However, I have done the brighness quantizations in perceptual space, >that is, brightness corrected for logarithmic eyeball response and the gamma >of the tube. I did not spend a lot of time on this, but the few pictures >that I tried indicated that the difference in quality was not worth writing >home about. Well guess what? Somebody has tried this. From my files: In article <8490@venera.isi.edu> raveling@venera.isi.edu (Paul Raveling) sez: [this is from May in response to someone suggesting HSV] Maybe, but it's not clear. About a year ago I tried some experiments using a different perceptual space suggested in a paper by Werner Frei, but got essentially the same end results as using RGB space. It's possible that limitations in the quantization algorithm could mask the benefits of using a different space; the best solution probably requires coordinated work to evolve both the color domain and algorithms using it. It's not clear that this is HSV but it was in response to someone who asked about it (I don't have the paper. Can you elaborate Paul?). This makes sense because most of the quantizations that you'll ever do involve colors which are going to be close in any color system. Colors which are close in RGB are also going to be close in HSV, HLS, YIQ, CMY, CIEXYZ, whatever. The relative distances will only change slightly and relatively rarely will they cross over. Remember that the boxes are going to be small almost all the time. Also, if you apply Floyd-Steinberg dithering the box choices only have to be "close" to their optimal value. In terms of matching a color to it's appropriate box, that's another matter but intuitively it doesn't seem to me that it's going to make that much of a difference. The RGB cube is not so skewed as to be irrelevant. Colors which are close in the cube will also be close perceptually. If you have 24-bit's then using some other model will probably improve your image significantly. If you have 20000 colors and only 8 bits to show them with then you're going to have a crude approximation no matter what you do. Quantization is going to eat the subtleties. Is Roy Hall on the net? If you're out there, what do you think of this subject? (I noticed that he barely touched the subject in his book and I was wondering why). An experiment I would *LOVE TO TRY* except I don't have any 24-bit frame buffers to play with is to compare the various quantization algorithms against the original 24-bit image. I'd also like to try and HSV scheme (and perhaps CIEXYZ) even though I don't especially have much faith in a change for better or worse (might make a good paper :-). --Bill Davidson
sparks@corpane.UUCP (John Sparks) (08/30/89)
<586@celit.com> <4862@eos.UUCP> <13381@well.UUCP> <7771@cbmvax.UUCP> Sender: Reply-To: sparks@corpane.UUCP (John Sparks) Followup-To: Distribution: na Organization: Corpane Industries, Inc. Keywords: RGB EGA VGA color In article <7771@cbmvax.UUCP> mitchell@cbmvax.UUCP (Fred Mitchell - QA) writes: >In article <13381@well.UUCP> gors@well.UUCP (Michael Sierchio) writes: >What you state is true, but you must keep in mind that we are going from >16 million colors to 16 or 64 colors. The amount of error encountered would >not be significant enough to be noticed at such a color quantization level. > You may have a *palette* of 16 million but the actual colors used in the picture will generally be a lot less than that. You need to figure out exactly how many tones are actually being used in the picture and go from there. For example an 800 X 800 pixel image can only have at the most 640,000 different colors, and thats only if each pixel is a different color. Most images will have a much smaller range of colors. The big problem is how to convert 32 shades of blue (example) down to just 16 shades of blue. To keep the picture from looking banded, you will have to dither the blues. BTW: Maybe the thing to do is figure out how an Image Capture board (framegrabber) figures out it's color palette when capturing a live scene. The situation is the same, millions of real colors, condensed into a few. One of the best products I've seen is the Digiview digitizer for the Amiga. It uses a black and white camera and a color filter (Just like Voyager! :-) And converts a full color scene into Amiga HAM mode (4096 colors) It has a terrific dithering scheme. -- John Sparks | {rutgers|uunet}!ukma!corpane!sparks | D.I.S.K. 24hrs 1200bps ||||||||||||||| sparks@corpane.UUCP | 502/968-5401 thru -5406 A virtuous life is its own punishment.
raveling@isi.edu (Paul Raveling) (08/31/89)
In article <126@vsserv.scri.fsu.edu>, pepke@loligo (Eric Pepke) writes: > > One could try other color spaces, such as HSV for example.... In the last few days I've been experimenting with 3D renderings of images in RGB space. Most look generally like a plume around an axis running roughly from black to white; some are fairly conical, most are flattened to some extent, some show definite fan-shaped planes. In many the central axis runs from slightly on the blue side of black to slightly on the red/yellow side of white -- that's possibly due to lighting in images digitized from outdoor photos, with relatively blue ambient light and relatively red/yellow specular reflections. One thing this suggests is that using a polar-coordinate representation of RGB space is likely to reduce quantization error with typical algorithms. Does anyone have an existing **VERY FAST** algorithm for transforming between polar and rectangular coordinates in 3-space? ---------------- Paul Raveling Raveling@isi.edu
flynn@pixel.cps.msu.edu (Patrick J. Flynn) (08/31/89)
In article <9464@venera.isi.edu> raveling@isi.edu (Paul Raveling) writes: >In article <126@vsserv.scri.fsu.edu>, pepke@loligo (Eric Pepke) writes: >> >> One could try other color spaces, such as HSV for example.... > > In the last few days I've been experimenting with 3D > renderings of images in RGB space. Most look generally > like a plume around an axis running roughly from black > to white; some are fairly conical, most are flattened > to some extent, some show definite fan-shaped planes. In many > the central axis runs from slightly on the blue side of > black to slightly on the red/yellow side of white -- that's > possibly due to lighting in images digitized from outdoor > photos, with relatively blue ambient light and relatively > red/yellow specular reflections. Now *this* is interesting! A geometric look at color space. How do the shapes of the plumes vary as one + changes the ambient lighting + changes the basis for color space (RGB to HSV, etc.) ? On interesting, realistic images, do well-formed clusters appear in the 3D color space? If so, one *could* attempt to reduce the pallette through the application of a traditional clustering algorithm (there was an article in ACM TOMS on this last year; they came up with a clustering alg. for color quantization and compared it to Heckbert's median-cut and the K-means clustering method). I say `could' with asterisks because most clustering methods make quite a few assumptions about the statistical properties of the data, and run for quite a while, and I seriously doubt that the `clusters' in color space (if any) are (say) multivariate Gaussian; I also doubt that people are willing to wait hours (!) for a clustering algorithm to reduce their pallette. However, it would be interesting to compare some clustering methods (perhaps a representative squared-error method and a graph-theoretic approach) against the algorithms arising from the graphics community. Patrick Flynn -- flynn@cps.msu.edu -- FLYNN@MSUEGR.BITNET -- uunet!frith!flynn "Ah don' want no Tea; it give me a headache." -- Pete Puma
raveling@isi.edu (Paul Raveling) (09/01/89)
> > Now *this* is interesting! A geometric look at color space. How do > the shapes of the plumes vary as one > + changes the ambient lighting > + changes the basis for color space (RGB to HSV, etc.) ? I haven't looked at enough yet to have a good feel for lighting changes. Since most of the images are digitized photos, it requires a little intuition. A further refinement that I hope to try today is to add another input knob to control a popularity threshold. By twiddling this knob it should be possible to get something like a time-multiplexed histogram (pixel frequency over the RGB domain). I haven't tried HSV yet. Maybe next week... this is still "extracurricular" work. > On interesting, realistic images, do well-formed clusters appear in > the 3D color space? For the most part, yes. Most are much more well-formed than I'd expected them to be. Some images also show fields with a scatter of points that are clearly related but not very dense in RGB space. Synthetic images, such as one of Cristy's molecules or a Bill The Cat cartoon, look like a very sparse set of points that sometimes allow a "connect the dots" approach to make sense of them -- sort of like drawing constellations among the stars. > If so, one *could* attempt to reduce the pallette > through the application of a traditional clustering algorithm (there > was an article in ACM TOMS on this last year; ... Good question. I'll look for the article & read it when time allows. (BTW, right now I'm officially testing changes to xrn before releasing it to our users.) It might be possible that a Monte Carlo color selection algorithm would work well for some images. I may try that as an experiment too. > ... and I > seriously doubt that the `clusters' in color space (if any) are > (say) multivariate Gaussian; I also doubt that people are willing to wait > hours (!) for a clustering algorithm to reduce their pallette. Caramba! Maybe I'll only skim that article. ---------------- Paul Raveling Raveling@isi.edu
pepke@loligo (Eric Pepke) (09/01/89)
In article <9464@venera.isi.edu> raveling@isi.edu (Paul Raveling) writes: > One thing this suggests is that using a polar-coordinate > representation of RGB space is likely to reduce quantization > error with typical algorithms. Does anyone have an existing > **VERY FAST** algorithm for transforming between polar and > rectangular coordinates in 3-space? I once did an approximation of R-P and P-R for a computer game on the Macintosh. It's pretty straightforward and obvious, and it requires nothing more onerous than an integer divide with precision double what the input and output precision is. I'll see if I can dig it up. Wanna collaborate on a a paper? Respond to the INTERNET address below. Eric Pepke INTERNET: pepke@gw.scri.fsu.edu Supercomputer Computations Research Institute MFENET: pepke@fsu Florida State University SPAN: scri::pepke Tallahassee, FL 32306-4052 BITNET: pepke@fsu Disclaimer: My employers seldom even LISTEN to my opinions. Meta-disclaimer: Any society that needs disclaimers has too many lawyers.
raveling@isi.edu (Paul Raveling) (09/02/89)
> ... A further refinement that I hope > to try today is to add another input knob to control a > popularity threshold. By twiddling this knob it should be > possible to get something like a time-multiplexed histogram > (pixel frequency over the RGB domain). That variant went into code late yesterday and I've looked at 2 images. The results are again "illuminating" and a bit surprising. Most of the RGB space volume occupied by image colors is at a VERY low density. Shift from displaying all colors to those which occur in only 2 or more pictures, and the "color clouds" shrink dramatically. Contine up to show only pixels with ~1/2 dozen and the "clouds" shrink to modest-sized spindles or small planes -- in fact they look something like shreds of stratus clouds. Beyond ~6 shrinkage slows, leaving a "hard core" of colors. This suggests an obvious question: Would quantization benefit by discarding the very-low frequency colors before selecting the final set? I think it would depend on how the quantization algorithm balances popularity and geometry (RGB space partitioning), but mean square error measurements would be the most likely to show a difference. I'm not sure about color retention measures. ---------------- Paul Raveling Raveling@isi.edu
dhelrod@cup.portal.com (David Hunter Elrod) (09/06/89)
There has been occasoinal mention of performing calculations in HSV space, or selecting colors in HSV instead of RGB. I'm curious why the CIE-LUV color space isn't used. Converting back and forth from RGB to HSV is NOT a 1:1 mapping. Even with perfect math, it is possible to go from HSV to RGB and back and have a DIFFERENT value than the one you started with. The CIE (Commission Internationale de l'Eclairage (International Commission on Illumination)) defined a color space in 1931. This color space is used throughout the world for specifying a specific color in a device independent way. In all three CIE color spaces (CIE-1931(or CIE-xyY), CIE-LUV, and CIE-LAB) the color indicies range from 0.0 to 1.0. Although only a portion of this space is valid. A problem with the original CIE color space is that equal distances in the color space represented UNequal distances in human visual spaces. For example, moving from (0.1,0.6) to (0.1,0.7) is a small change from one green to a similar green. While moving from (0.5,0.3) to (0.5,0.4) is a change from red to orange. This problem was somewhat solved by the CIE-LUV space in 1976. The LUV color space was a compromise between a space where equal distances represented equal percieved color changes, and it wasn't too complex to translate to/from that space. Another space, CIE-LAB, is a more linear space, but requires cubes and cube roots to convert from a color cube and back. So, why all the above?? Well, CIE-LUV isn't that hard to convert to/from RGB, and it IS a space where equal sized chunks of color space represent approximately equal sized portions of what the "CIE standard observer" can see. Seems to me that this should be the space to put the histogram bins in. Especially if each bin represents several colors. All colors falling in a single bin would be percieved as being very similar. When I was studying color, I looked at a lot of the available literature. This included several of the newer books that have come out discussing color. I found the following two to be the best for what I was doing (which was looking at lighting and shading, "true" color representation in a device independent way, and color space transformations for high end graphics accelerators). References: Procedural Elements For Computer Graphics by David F. Rogers McGraw-Hill Book Company ISBN 0-07-053534-5 Copyright 1985 This book was the best of all that I looked at for explaining what was going on and giving sample code that you could play with to make sure you REALLY understood. It still leaves some stuff to the reader... Color Science: Concepts and Methods, Quantitative Data and Formulae Second Edition by Gunter Wyszecki W.S. Stiles John Wiley & Sons ISBN 0-471-02106-7 Copyright 1982 This is "THE" book on color. It is a huge book that covers more than I ever wanted to know about color. A GREAT reference book. It also has a lot of the facts figures and values needed for some types of calculations in the appendicies. =============================== David Elrod Rivendell dhelrod@cup.portal.com
craig@weedeater.uucp (Craig Kolb) (09/07/89)
In article <9473@venera.isi.edu> raveling@isi.edu (Paul Raveling) writes: >> If so, one *could* attempt to reduce the pallette >> through the application of a traditional clustering algorithm (there >> was an article in ACM TOMS on this last year; ... > > Good question. I'll look for the article & read it when > time allows. (BTW, right now I'm officially testing changes > to xrn before releasing it to our users.) > > It might be possible that a Monte Carlo color selection algorithm > would work well for some images. I may try that as an experiment > too. > >> ... and I >> seriously doubt that the `clusters' in color space (if any) are >> (say) multivariate Gaussian; I also doubt that people are willing to wait >> hours (!) for a clustering algorithm to reduce their pallette. > > Caramba! Maybe I'll only skim that article. Unless I'm mistaken, the article in question is: Wan, Wong, and Prusinkiewicz, An Algorithm for Multidimensional Data Clustering, Transactions on Mathematical Software, Vol 14, #2 (June '88), pp. 153-162 This is the paper upon which the "Variance-based Color Quantization" code I posted to the net two weeks ago is based. The vanilla algorithm is basically modified median-cut -- see the paper for details. As far as speed is concerned, quantizing a 512x512x24-bit version of "lenna" to 256 colors on my Iris 4D60 takes approximately 5 seconds, which is typical for most images of similar size. Cheers, Craig Kolb kolb@yale.edu
flynn@pixel.cps.msu.edu (Patrick J. Flynn) (09/07/89)
In article <71733@yale-celray.yale.UUCP> craig@weedeater.math.yale.edu (Craig Kolb) writes: >In article <9473@venera.isi.edu> raveling@isi.edu (Paul Raveling) writes: >> [In the >>> article, Pat Flynn wrote:] >>> If so, one *could* attempt to reduce the palette >>> through the application of a traditional clustering algorithm (there >>> was an article in ACM TOMS on this last year; ... >> >> [...] >> It might be possible that a Monte Carlo color selection algorithm >> would work well for some images. I may try that as an experiment >> too. >> >>> ... and I >>> seriously doubt that the `clusters' in color space (if any) are >>> (say) multivariate Gaussian; I also doubt that people are willing to wait >>> hours (!) for a clustering algorithm to reduce their palette. >> >> Caramba! Maybe I'll only skim that article. > >Unless I'm mistaken, the article in question is: > >Wan, Wong, and Prusinkiewicz, An Algorithm for Multidimensional > Data Clustering, Transactions on Mathematical Software, > Vol 14, #2 (June '88), pp. 153-162 That's the one I was referring to. Next time I follow up, I'll do it from my office (where the journals are), not from home :-) . > [...] >As far as speed is concerned, quantizing a 512x512x24-bit version of "lenna" >to 256 colors on my Iris 4D60 takes approximately 5 seconds, which is >typical for most images of similar size. Good to see some actual numbers. I should emphasize that taking a clustering approach to color quantization does not *guarantee* that your results will take a long time to come. Taking a *naive* approach to clustering often may. \begin{pedantic} Most clustering algorithms base membership decisions on a proximity measure defined on the `feature space' of interest. Here, our feature space is 3D; it may be RGB, maybe HSV, maybe something else. The data to be clustered is a sample from this space. The two crucial differences between the data we typically see in exploratory data anlaysis and the data used in color quantization are - Color data is discrete; for 24-bit color you only have 256^3 distinct triplets. In image regions of uniform color and intensity you may have multiple instances of the same triplet, and it's probably *not* a good idea to ignore the duplicates; they convey important information about the distribution of color in the image. In many `traditional' clustering algm's, these duplicates might be ignored. - There's a hell of a lot more data than many clustering algorithms are designed to *realistically* handle (e.g., 256K 3-vectors for a 512x512 image). Algorithms that compute a proximity measure for *each* pair of 3-vectors will take forever to run on such a data set. The statistician in me would normally say: `No problem. subsample the image to get, say, 1K 3-vectors, find a 256-cluster solution, and classify the remaining pixels by finding the Euclidean distance in color space between them and the various cluster centers that you obtained.' Unfortunately, subsampling creates the possibility that you'll subsample perceptually-important image structures out of existence. Consider the example of two boring dark orange regions separated by a really nice-looking, bright purple border. If your subsampling scheme doesn't pick up the border pixels, the reduced-pallette result will have a blurred border (or none at all!); perceptually, you'd probably prefer a little less discrimination between fine shades of dark orange in favor of a faithful reproduction of the bright purple. So, if color quantization is to be attacked using cluster analysis, we need to pay careful attention to the special issues presented by discrete, voluminous image data. \end{pedantic} Here's one possible application of clustering, used as a postprocessing step for a poor-quality color quantizer. I probably won't get around to implementing it anytime soon (gotta finish that PhD), but maybe someone with spare time would be interested. Suppose you have a true-color image, and one quick&dirty color quantization routine, which produces only tolerable output. View each of the 256 color bins as a cluster center for a 256-cluster partitioning of the color space occupied by the image. Construct a (stratified?) sample from the original image by picking up a subset of the true-color pixels falling into each bin (so you have a few 3-vectors from each of the bins). Then cluster those babies. See if the resultant clustering is an improvement. If it is, publish it in SIGGRAPH and make big bucks. Aside: it's interesting to examine the almost-inverse relationship between color quantization (pallette reduction for data compression) and pseudocoloring of monochrome or multispectral data (pallete *expansion* for increased perceptual detail). The image processing book by Wayne Niblack has a very nice discussion of color bases and pseudocoloring of Landsat data. I use pseudocoloring to judge the noisiness of the imagery I get from a triangulation-based rangefinder. It's surprising the detail that the eye will extract from color contours that it can't get from gray-scale. Best Pat Flynn ------------------------------------------------------------------------------ Patrick Flynn, CS, Mich. State Univ. -- flynn@cps.msu.edu -- uunet!frith!flynn
bdb@becker.UUCP (Bruce Becker) (09/07/89)
In article <21898@cup.portal.com> dhelrod@cup.portal.com (David Hunter Elrod) writes: |[...] |Color Science: Concepts and Methods, Quantitative Data and Formulae | Second Edition | by Gunter Wyszecki W.S. Stiles | John Wiley & Sons | ISBN 0-471-02106-7 | Copyright 1982 | This is "THE" book on color. It is a huge book that covers more than I | ever wanted to know about color. A GREAT reference book. It also has | a lot of the facts figures and values needed for some types of calculations | in the appendicies. Indeed it is "the" book, if only I could find it! I suppose I could special-order it, but if anyone has it used & for sale, I'd be glad to work out a favorable exchange, puh-leez... Thanks, -- \__/ Bruce Becker Toronto, Ont. w \@@/ Internet: bdb@becker.UUCP, bruce@gpu.utcs.toronto.edu `/~/-e BitNet: BECKER@HUMBER.BITNET _< \_ Happiness is a warm gnu, yes it is - R. M. Soulman
tuna@athena.mit.edu (Kirk 'UhOh' Johnson) (09/08/89)
In article <4503@cps3xx.UUCP> flynn@pixel.cps.msu.edu (Patrick J. Flynn) writes:
%
% Here's one possible application of clustering, used as a
% postprocessing step for a poor-quality color quantizer. I probably
% won't get around to implementing it anytime soon (gotta finish that
% PhD), but maybe someone with spare time would be interested.
%
% Suppose you have a true-color image, and one quick&dirty color
% quantization routine, which produces only tolerable output. View
% each of the 256 color bins as a cluster center for a 256-cluster
% partitioning of the color space occupied by the image. Construct a
% (stratified?) sample from the original image by picking up a subset
% of the true-color pixels falling into each bin (so you have a few
% 3-vectors from each of the bins). Then cluster those babies. See if
% the resultant clustering is an improvement. If it is, publish it in
% SIGGRAPH and make big bucks.
although your description is not extremely detailed, it sounds like
you're describing a standard vector-quantization (VQ) algorithm
("Lloyd-Max Quantization", or something like that). _Digital Coding of
Waveforms_ by Jayant and Noll (Prentice Hall) provides a reasonable
description of the algorithm. it is a mechanism for iteratively
improving the "quality" (based on some error criterion) of a
particular quantization (or what you folks are calling "clustering").
it could certainly be applied to the problem at hand; i've used it in
other application domains (speech compression) and had pretty good
luck.
kirkraveling@isi.edu (Paul Raveling) (09/09/89)
> It's not clear that this is HSV but it was in response to someone who > asked about it (I don't have the paper. Can you elaborate Paul?). It wasn't HSV, but I don't recall details any more, don't have the code, and can't find the paper. (ISI's library has shrunk a bit while it's occupying temporary quarters -- it's permanent home floor is being remodeled.) > This makes sense because most of the quantizations that you'll ever do > involve colors which are going to be close in any color system. Colors > which are close in RGB are also going to be close in HSV, HLS, YIQ, CMY, > CIEXYZ, whatever. The relative distances will only change slightly and > relatively rarely will they cross over. In this hack for visualizing images I've added a switch to show them in either RGB or HSV. It appears that the patterns in RGB space would be much easier for quantization to work on than those in HSV. Colors tend to form relatively well-defined shapes in RGB space, somewhat reminiscent of clouds. In in HSV they spread out into relatively more planar forms that look more like curtains without clearly defined "top" boundaries. HSV seems to be better for showing all chroma info that's present, but in most cases there's a lack of clearly defined boundaries -- colors are more diffuse, grading gradually from high-density areas to low density without well-defined edges or surfaces. I'll probably try some other color spaces as time goes on, but RGB still looks most promising for quantization algorithms. It makes me think mother nature (aka "the laws of physics") operates naturally in either RGB or something with 1-1 mapping to it. Trying to account for human perception is where it gets more confusing. ---------------- Paul Raveling Raveling@isi.edu
ph@miro.Berkeley.EDU (Paul Heckbert) (09/12/89)
I'd like to comment on some of the interesting ideas that people have proposed recently regarding color image quantization algorithms. (1) ITERATIVE IMPROVEMENT OF A COLORMAP Patrick Flynn (flynn@pixel.cps.msu.edu) suggested: | ... Construct a (stratified?) sample from the original image by picking | up a subset of the true-color pixels falling into each bin Then cluster | those babies. See if the resultant clustering is an improvement. If | it is, publish it in SIGGRAPH and make big bucks. Actually, I tried this and discussed such an iterative quantization improvement algorithm in my paper: Paul Heckbert, "Color Image Quantization for Frame Buffer Display" SIGGRAPH '82 Proceedings Once you've got a colormap, it can be improved by iterating the following step: For each color in the colormap, find the colors from the original image whose nearest neighbor in the colormap is that color (like finding the Voronoi diagram in color space), find the centroid of those original colors, and move the colormap color there. The method converges to a (usually local) minimum of the error metric. The technique was first proposed, I believe, in Lloyd, S. P., "Least squares quantization in PCM's", Bell Telephone Labs Memo, Murray Hill, N.J., 1957 and improved upon by Gray, R. M., Kieffer, J. C., and Linde, Y. "Locally optimal block quantizer design", Information and Control 45, 1980, pp. 178-198. Such techniques are common in clustering/classification algorithms for pattern recognition. I believe the K-MEANS algorithm uses it. The method works fairly well in my experience: you can start with a pretty poor colormap such as a uniform grid in RGB space with 3 bits red, 3 bits green, 2 bits blue, iterate it maybe 10 times and the quantization is much improved. The results were not as good as median cut in my experiments, however. A digression into deeper issues: Actually, the way I was making the final color choice in my median cut algorithm, as the centroid of the colors in a rectilinear box, is inferior to the centroid-of-Voronoi-cell method used by such an iteration scheme. The median cut algorithm and many other rectilinear subdivision clustering algorithms approximate the true Voronoi cells, which are convex polyhedra of varying topology, with boxes. A multidimensional quantization (clustering) algorithm attempting to find the global error minimum using true Voronoi cells would probably be extremely hairy. The problem is tractable in 1-D, however, because Voronoi cells in 1-D have fixed topology: they're intervals. In fact, optimal monochrome image quantization can be done in polynomial time using dynamic programming. I mention the algorithm in my SIGGRAPH paper and it's described in full in my Bachelor's thesis: Paul Heckbert, "Color Image Quantization for Frame Buffer Display" Bachelor's thesis, Math Dept, 1980 (copies probably available through the MIT Media Lab) and in Bruce, J. D., "Optimum quantization", MIT R.L.E. Technical Report #429, 1965. (2) QUANTIZATION AS INVERSE COLORMAPS Patrick also suggested: | ... it's interesting to examine the almost-inverse relationship | between color quantization and pseudocoloring... Yes, I've often found it helpful to think of these data structures or procedures for finding nearest neighbors in the colormap as inverse colormaps. Colormaps take an index as input and return a color; while nearest-color-in-colormap functions take a color as input and return an index. Any cosmic significance here?? Who knows? (3) FLESH TONES AND PERCEPTUAL IMAGE DIFFERENCE METRICS Michael L. Mauldin (mlm@nl.cs.cmu.edu) brought up the subject of flesh tones: | Has anyone experimented with psychological color preferences ... | In some images containing people's faces, where the face is | only a small part of the image, very few colors are assigned | to "flesh" color. The result is banding/loss of resolution in | an area of the image that is interesting to the viewer ... Yes! When I was testing quantization algorithms (popularity, median cut, iterative, and others), I found that the quantization errors in many images were not perceptually bothersome. On the mandrill or other images with lots of high frequencies, the contours and color errors are lost in the noise, so to speak, and on expressionist paintings (I did a lot of experiments with Franz Marc's painting "Blue Horses") the errors aren't so bothersome, because who's to say what color a blue horse is supposed to be, anyway? :-) The numerical error as computed by the quantitative metric (sum of squared distances in RGB space, in my case) could be very high yet the eye didn't care. On the other hand, when I ran my algorithms on "Pamela" [Playboy, April 1978], any contouring on the low-frequency areas of the face or color errors on the lips or eyes were very noticeable. Many of the colormap selection algorithms I tried failed to pick a good red for the lips or a good blue for the eyes. The median cut algorithm fared better than the others, but I never found an algorithm that could select a 4-color colormap for Pamela as well as I could by hand. Clearly, a truly perceptually-based image difference metric would have to go far beyond merely using a perceptual color space. It would have to take spatial differences into account as well, dealing with such issues as contour edges, dithering, noise, frequency, spatial distortions, and ultimately, image understanding. Humans have evolved and learned to focus their vision on faces, so a perceptual image difference metric would weight such regions of an image more heavily than less "interesting" portions of the image. As a quick hack for my Bachelor's thesis, I implemented a program called "doodle" that allowed the user to manually indicate the regions of the picture that needed extra weight in the error calculation, by tracing over them with a tablet. For Pamela, I'd doodle over her eyes and lips. This technique, also recently suggested by Eric Pepke (pepke@gw.scri.fsu.edu), helped quite a bit, but it was a slow, iterative process for the user to wait a few minutes (back then) for the resulting quantized image to come out. Ken Sloan of U. of Washington has suggested that this could be automated by weighting all edges more than smooth regions, but this doesn't sound quite right to me, because it is was the smoothly shaded, distinctive colors of the eyes and lips that gave me the most trouble, not the edges and high frequency regions (such as hair). I think it's easy to ascribe too much meaning to the numerical value of simplistic error metrics such as the one I used. I was disappointed that Wan et al, in their paper: S. J. Wan, K. M. Wong, P. Prusinkiewicz, "An Algorithm for Multidimensional Data Clustering", ACM Trans. on Mathematical Software, vol. 14, no. 2, June 1988, pp. 153-162. didn't show more pictures (did they show any color pictures?) to allow comparison of the perceptual, subjective difference with their quantitative, objective one. Their variation on the median cut algorithm splits at the point that minimizes the variance in the two sub-boxes, rather than at the median; a technique that I discussed (but did not analyze) in my BS thesis and SIGGRAPH paper. Has anybody else tried automatic weighting in image difference metrics, for color image quantization or any other purpose? -- The popularity of this color image quantization topic in comp.graphics never ceases to amaze me! I almost didn't publish my 1982 paper because I figured then that the 8 bit frame buffers of the time would all be replaced by 24-bit ones in a few years. The worldwide average depth today, however, must be around 4 bits! Paul Heckbert, CS grad student 508-7 Evans Hall, UC Berkeley ARPA: ph@miro.berkeley.edu Berkeley, CA 94720 UUCP: ucbvax!miro.berkeley.edu!ph