Path: utzoo!attcan!uunet!lll-winken!ames!ncar!unmvax!pprg.unm.edu!swilson
From: swilson@pprg.unm.edu (Scott Wilson [CHTM])
Newsgroups: comp.graphics
Subject: Re: Color Quantization
Message-ID: <23862@pprg.unm.edu>
Date: 23 May 89 19:34:20 GMT
References: <4706@uoregon.uoregon.edu> <310@celit.UUCP> <311@celit.UUCP>
Reply-To: swilson@pprg.unm.edu (Scott Wilson [CHTM])
Organization: U. of New Mexico, Albuquerque
Lines: 50

In article <311@celit.UUCP> billd@celerity (Bill Davidson) writes:
>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.
>
    .......etc
>
>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.
>
>Bill Davidson		...!{ucsd,sdsu,fpssun,cogen,chip,photon}!celerity!billd

Here is a little modification that is similar to yours, and seems to be
giving nice results for many types of images (including sunsets):

  1. Choose about 50% of the desired number of colors by finding that
     "color box" with the largest number of occupants (actual colors),
     and splitting it in along its longest side. 

  2. Choose the remaining 50% of the desired number of colors by splitting
     that "color box" with the largest *diagonal* distance (i.e. 2-norm).
     Split along the longest side, as usual.

The end result is that you preserve lots of detail in areas that have
large color spans but not many pixels, but you also get smoothly
varying changes in objects that have large spatial extent but not much
color span (i.e. you get no "color contours").

You can play around with how many colors are assigned based on the above two
metrics and get better/worse results for a particular image, but 50/50 seems
to do pretty well for almost everything...

Scott Wilson
University of New Mexico
Center for High Technology Materials
Albuqerque, NM 87131

swilson@pprg.unm.edu