From: d3g637@duke.oname (David P. Chassin)
Newsgroups: comp.ai.neural-nets
Subject: Re: ALGORITHM NEEDED:  Palette Selection
Date: 28 Jul 92 20:32:24 GMT
Article-I.D.: oracle.1992Jul28.203224.19657
Reply-To: d3g637@duke.oname
Organization: Battelle/Pacific Northwest Laboratories

In article 82z@undergrad.math.waterloo.edu, icfaragh@cayley.waterloo.edu (Chad Faragher) writes:
>
>The situation:  An image is stored by giving the rgb value for each pixel.
> 
>The problem:  How to find the best palette of size-n for a particular image
>stored (at arbitrary resolution) as above.
> 
>The solution:  HELP!!!
>
>Does the algorithm exist?  Is it memory intensive?  Can it be solved with 
>recursion (ie octree division)? 

If my memory serves me an approach to such a beast is to figure out a
3D histogram (RGB axes) of the image.  Then select the
regions with the highest density of entries and define colors for each
region.  You need to define the permissible deviation from the original
color.  The greater the permissible deviation the fewer palette entries
you will need.  The relationship between the deviation and the number
of entries is understandably unique to each image.  The net result of
this operation is a table which defines RGB values for each entry in
the table.  Then you go through each pixel in the image and map it
to the palette entry by finding which entry's RGB values are closest to
the pixels value.  Note that the RGB value you choose at a given 
entry may not _actually_ occur in the image, but may instead be
a kind of local centroid. 

BTW: a three dimensional histogram is a ***VERY*** memory intensive
affair.  There are ways around that problem though.  For example you
don't actually allocate a 256x256x256 histogram (assuming 24 bit RGB images)
table but simply record them as you go along.  Then again, there's a
speed cost.

>Can a neural-net be trained to arrive at
>a visually pleasing palette given the original image?
> 
>All input welcome.
> 
>Chad Faragher -- University of Waterloo


I can conceive of a neural net to do such a thing, but WOW!  You could
for example use a 256x256x256 input layer and a n-sized (palette entries)
output layer with RGB values.  Better yet you might simply provide the
image as an input and the palette as the output. 
I'm not very confident of these schema though,
they seems neither practical nor effective.  The training might work for a
given type of image, but I'm not sure it would work for all types.
I wonder if anyone's had any more practical ideas. It does sound like something
worth pursuing.  Neural Nets have been used for stock market analysis and that's
also a multidimensional statistical problem. Who knows...

BTW: how do you define visually pleasing?  I consider the algorithm effective
iff I cannot distinguish between the original and the compressed image on
a given medium.  It's a pretty binary test, and has little to do with pleasure.
Of course the medium of display is important to consider.


        Dave Chassin
        Email: dp_chassin@pnl.gov           "Life is either a daring
        Vox: (509)375-4369                    adventure or nothing"
        Fax: (509)375-3614                           - Helen Keller