Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.csd.uwm.edu!gem.mps.ohio-state.edu!ginosko!uunet!yale!craig
From: craig@weedeater.uucp (Craig Kolb)
Newsgroups: comp.graphics
Subject: Re: How to map 24-bit RGB to best EGA/VGA palette?
Keywords: RGB EGA VGA color
Message-ID: <71733@yale-celray.yale.UUCP>
Date: 6 Sep 89 23:10:20 GMT
References: <4379@cps3xx.UUCP> <126@vsserv.scri.fsu.edu> <3129@cbnewsm.ATT.COM> <7743@cbmvax.UUCP> <13319@well.UUCP> <586@celit.com> <4862@eos.UUCP> <13381@well.UUCP> <9464@venera.isi.edu> <9473@venera.isi.edu>
Sender: root@yale.UUCP
Reply-To: craig@weedeater.math.yale.edu (Craig Kolb)
Organization: Yale University Department of Mathematics
Lines: 37

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