Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!apple!sun-barr!cs.utexas.edu!uunet!seismo!esosun!cogen!celerity!celit!billd
From: billd@celerity.UUCP (Bill Davidson)
Newsgroups: comp.graphics
Subject: Color Quantization (was Re: Discussion of Computer Pornography)
Message-ID: <310@celit.UUCP>
Date: 23 May 89 04:36:39 GMT
References: <4706@uoregon.uoregon.edu>
Sender: news@celerity
Reply-To: billd@celerity (Bill Davidson)
Organization: FPS Computing Inc., San Diego CA
Lines: 45

In article <4706@uoregon.uoregon.edu> markv@tillamook.UUCP (Mark VandeWettering) writes:
>This is comp.graphics.  Pixels, frame buffers, point in polygon testing,
>frame buffer quantization, halftoning, raytracing and radiosity are what
>should be discussed here.

O.K.  I'm new to color quantization and I've written my first quantizer
with reasonably good results and I have a few questions.

I first attacked the problem a few weeks ago when someone mentioned that
they wanted something to choose the best color map when converting a 24
bit image to 8 bits.  It's something I'd thought about before and this
set me to thinking about the problem.

None of the CG books I have (Foley/Van Dam, Harrington, Newman/Sproull,
Rogers, Artiwick) had anything on it.  I played around with a few ideas,
all of which produced exponential algorithms.  I suppose I should check
out image processing books more.  Anybody out there have any good
references?  Also, I'm looking for some good references on Floyd-Steinberg
dithering.

A friend (Hi Jim) pointed me to Paul Heckbert's paper from SIGGRAPH '82
on the median cut algorithm.  I implemented it.  It has some problems
though.  If a color is way out away from all the other colors, it will
get sucked into the other colors.  This resulted in very purple sky in
one of my images.  I got better results when, instead of taking the
centroid of the points in each box, I took the center of mass where the
mass of each point was equal to it's frequency within the image.  I
don't have a proof but I believe that this will result in a lower
quantization error over the entire image while creating larger maximum
quantization errors within each box for those color farthest away.
Anyway, my sky turned blue again :-).

I also have an idea which I haven't had a chance to hack into my
quantizer which is to use the same basic idea as median cut but
instead of using the halfway point in the list associated with
the box we are cutting, consider the mass of the list where the
mass is defined as the number of pixels represented by all of these
colors.  Then we try to break it into two lists with approximately
equal mass.  The idea is that colors which are very common may get
their own boxes and break off thus not messing up other colors.
It'll take a bit more cpu but I don't think it will be prohibitive.

Any authorities on this subject out there with comments?

Bill Davidson		...!{ucsd,sdsu,fpssun,cogen,chip,photon}!celerity!billd