Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!apple!ames!pasteur!helios.ee.lbl.gov!ace.ee.lbl.gov!jef
From: jef@ace.ee.lbl.gov (Jef Poskanzer)
Newsgroups: comp.graphics
Subject: Re: Color Quantization
Summary: Yep.
Message-ID: <2707@helios.ee.lbl.gov>
Date: 23 May 89 16:51:07 GMT
References: <310@celit.UUCP>
Sender: usenet@helios.ee.lbl.gov
Reply-To: Jef Poskanzer <jef@helios.ee.lbl.gov>
Organization: Paratheo-Anametamystikhood Of Eris Esoteric, Ada Lovelace Cabal
Lines: 92

First:

In the referenced message, billd@celerity (Bill Davidson) wrote:
}Also, I'm looking for some good references on Floyd-Steinberg dithering.

"Digital Halftoning" by Ulichney.  Grep through the recent comp.graphics
articles for four or five more specific references.  Now...

}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 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.

Yes, while implementing median cut for my soon-to-be-released color
version of PBM, I looked at just these two questions.  Here are the
relevant quotes from Heckbert's paper, all in the section headed "The
Median Cut Algorithm":

    The box is "shrunk" to fit tightly around the points (colors) it
    encloses

This indicates that "points" means colors, not pixels.  Therefore:

    The enclosed points are sorted along the longest dimension of the box,
    and segregated into two halves at the median point.  Approximately
    equal numbers of points will fall on each side of the cutting plane.

this means that the median is computed by counting colors, not by counting
pixels (the "mass of the list", in Bill's terminology).

    After K boxes are generated, the representative for each box is
    computed by averaging the colors contained in each.

And this is pretty explicit, the color choice is done by an average in
color space.

Now let's look at what some of the publically-available implementations
of median-cut actually do.

Ed Falk's median.c:

    Computes the median by pixels; i.e., approx. equal numbers of pixels,
    not colors, fall on each side of the boundary.

    Assigns representatives by taking the center of the box, (minR+maxR)/2
    etc.  A comment mentions that he tried a "histogram-weighted center"
    (sounds like an average in pixel space), but didn't like the results.

Michael Mauldin's fbquant.c (in FBM):

    Computes the median by pixels.

    Assigns representatives by averaging the colors.

Robert Mecklenburg and John W. Peterson's mcut.c (in Utah Toolkit):

    Computes the median by pixels.

    Assigns representatives, unless I'm mis-reading the code, by averaging
    the colors weighted not by the number of pixels they represent but by
    the _square_ of the number of pixels.

So, three implementations; all three use the same method of choosing
the median, but not the method specified in the paper; and each of the
three uses a different method of assigning a representative color, only
one of which is the method specified in the paper.  My own as-yet
unreleased implementation (ppmquant.c) currently does the same things
as Michael Mauldin's, but I really wonder if this is best.  And Bill's
version does the median by colors (but he's thinking of switching), and
assigns representatives to boxes by averaging with pixel weights (a
fourth method).

Anyway, Bill, if you've actually read the paper and implemented it, then
you are as much an expert as anyone else except Heckbert.  And I asked him
about this stuff a week ago, but he hasn't replied.
---
Jef

            Jef Poskanzer   jef@helios.ee.lbl.gov   ...well!pokey
      "The trouble with paper designs is you don't get bloody enough."
                              -- Butler Lampson