Hello!

This is my first post to this newsgroup, so forgive my request if it is
not the proper group to discuss about it or if my problem has already
been discussed recently.

So here is my problem: I've got trouble with classical color
quantization algorithms (popularity, median-cut, octtree, and enven
k-mean) in that they miss some "border" colors that are important when
using error dispersion techniques later to approximate the full set of
original colors. This effect is particularily visible when reducing to a
very small set of colors (say less that 16) and quite imperceptible when
reducing down to 256 colors. I know some people says that this is caused
by the fact that there isn't enough colors to represent the color-set
but I have doubt about that.

To explain my point of view, I'll use the following simple example.
Suppose that we are working in a linear color space (to avoid problems
with gamma, etc) with an image representing 5 bands of colors of equal
surface ranging from full black (value=0.00) on the left side to
full-white (value=1.00) on the right side. Hence we have the following
normalized value in the initial color-set: 0.00, 0.25, 0.50, 0.75, 0.00.

Now given that set of colors, if we ask the classical algorithms to
reduce the set down to 2 colors only, one gets the values 0.25 and 0.75.
In a sense these two values minimize the total error of the image in
that they represents the centroid of both regions: 0.00->0.50 and
0.50->1.0. ok.

However the resulting image is rather poor visually because it misses
the min/max values 0.00 and 1.00 even if we use dithering technique to
interpolate the missing colors: There are uniform gray values on both
sides of the image. In that case a choice of 0.00 and 1.00 would have
produced a better output because all the five colors could be
interpolated (Note: the resolution of the reduced-color image is not
necessarily the same as the initial image, it can be twice or more).

The reason for that disparition of colors is that the classical
reduction techniques uses the centroid of color clusters and therefore
tend to stay away form the colors near the convex hull of the color-set.

In my opinion, colors defining the convex-hull are somehow important and
should not be negected because all of the original colors can be
represented by positive linear combination of these vertices-colors.
Indeed mixing colors from the convex hull using techniques like
error-diffusion allow representing all the colors inside of the hull.

Actually the exact convex hull of the colorset is probably not that
important and an over-approximation of the convex hull can bed enough
(for instance the 8 corners of the bounding box of the color set).
Having also colors inside the interior of the hull would also help
reucing the number of color needed to be mixed.

I'd like to know if there exist algorithm that take care of these
convex-hull colors in order to produce a reduced color-set well suited
to reproduce the initial colors without mixing too mainy of colors of
the final palette.

I don't know if that problem has already been adressed, but I'd grealty
appreciate if someone with theoritical or practical background in
computer graphics could provide me some pointers to algorithm or
freely-available papers on that topic. Note: I'm not an academics. My
initial concern was to reduce colorfull image down to 16color images for
obsolete computers.

Thank you for reading my (rather long) post.

regards,

sam.

I wonder if someone has ever used such a barier function to measure the
closeness of an interior-point to the convex-hull. Using such function,
I think it could be possible to tune color reduction in order to
preserve convex-hull colors. For instance, ponderate colors with their
barrier-value when choosing the representative of a cluster would imply
that clusters that are far away from the borders will be represented by
a point rather near the centroid, whereas clusters that touches or are
very close to the border will have their representative "attracted" by
the hull. I haven't found web-articles refering to such an idea.