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: Re: Color Quantization
Message-ID: <311@celit.UUCP>
Date: 23 May 89 05:47:15 GMT
References: <4706@uoregon.uoregon.edu> <310@celit.UUCP>
Sender: news@celerity
Reply-To: billd@celerity (Bill Davidson)
Organization: FPS Computing Inc., San Diego CA
Lines: 33

In article <310@celit.UUCP> billd@celerity (Bill Davidson) writes:
>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.

I looked at this after I posted it and I decided it doesn't really
explain what I mean.  You'd never know I have a degree in math/cs.
Let's try again:

Assign to each color in the image a weight which is equal to it's
frequency in the image.  So if 432 pixels are (0,0,255), then that
color would have weight of 432 and if 20 pixels in the image are
(0,20,30) then that color would have weight 20.

The weight of a list of colors would be the sum of weights of all
the colors in the list.  If we were splitting the box along the
red axis, this list would be sorted by it's red values.

We would run through the list adding the weights of each color
to our new total as we went through it.  When our new total
was about half of our original total, we pick this spot to
split the box.

This is the essence of my change to Heckbert's algorithm which
simply chose the midpoint of the list.

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