keithd@gryphon.COM (Keith Doyle) (12/05/88)
I'm trying to improve a palette reduction algorithm I'm using, I know it can get better because I've also been using a couple of programs that clearly do a better job. What I'm currently doing (where ncolors is how many colors I want in the resultant palette): 1. computing the histogram 2. sorting it into a most-used-first table 3. starting at ncolors/2, scanning up through the table successively eliminating colors that are within x distance of a color already in the palette, and adjusting x until I've reduced to ncolors. This works, but I've found my palettes seem to be somewhat more saturated and a little brighter than a couple of commercial programs I've tried that do a little better job. There's a lot of things I could try, but I really have no idea what works better than what. For example, I could, before throwing away a color because of it's closeness to a current palette color, decide to modify the current palette color to be a little more like the color I'm throwing away, based on the histogram information or something. But then I can imagine some of the colors wandering off in various directions as it's closeness to other colors has then been modified. Or, I could adjust how many colors in the most-used list I'm willing to throw away due to closeness, but which direction? The only reference I've been able to dredge is one by Paul Heckbert in Siggraph '82, unfortunately my collection begins in '83. Most of the major CG books don't even mention the problem. Any ideas? Keith Doyle gryphon!keithd
thomson@wasatch.UUCP (Rich Thomson) (12/06/88)
In article <9274@gryphon.COM> keithd@gryphon.COM (Keith Doyle) writes:
:I'm trying to improve a palette reduction algorithm I'm using,
:I know it can get better because I've also been using a couple
:of programs that clearly do a better job.
:
:What I'm currently doing:
:
:1. computing the histogram
:2. sorting it into a most-used-first table
:3. starting at ncolors/2, scanning up through the
: table successively eliminating colors that are within
: x distance of a color already in the palette, and adjusting
: x until I've reduced to ncolors.
[stuff deleted]
Check out chapter six of _Digital Picture Processing_, 2nd ed., by
Azriel Rosenfield and Avinash C. Kak. This chapter covers techniques of
'histogram sharpening' and other histogram modification techniques.
Basically, 'histogram sharpening' is an iterative process that will sharpen
the histogram peaks of the image, then you can reduce the number of palette
entries to just those taken up by the peaks of the histogram. Upon
glancing at the description of the method, it appears to modify the
original image (at least in terms of the color values used for the pixels)
which may not be what you want. Anyway, there's lots of useful stuff in
this book (I think), so you may want to check it out anyway.
-- Rich
--
Rich Thomson thomson@cs.utah.edu {bellcore,hplabs}!utah-cs!thomson
"Tyranny, like hell, is not easily conquered; yet we have this consolation with
us, that the harder the conflict, the more glorious the triumph. What we obtain
too cheap, we esteem too lightly." Thomas Paine, _The Crisis_, Dec. 23rd, 1776