home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / ai / neuraln / 3004 < prev    next >
Encoding:
Internet Message Format  |  1992-07-28  |  3.3 KB
  1. Path: sparky!uunet!ogicse!pnl-oracle!duke!d3g637
  2. From: d3g637@duke.oname (David P. Chassin)
  3. Newsgroups: comp.ai.neural-nets
  4. Subject: Re: ALGORITHM NEEDED:  Palette Selection
  5. Message-ID: <1992Jul28.203224.19657@oracle.pnl.gov>
  6. Date: 28 Jul 92 20:32:24 GMT
  7. Article-I.D.: oracle.1992Jul28.203224.19657
  8. References: <Bs1wLE.82z@undergrad.math.waterloo.edu>
  9. Sender: news@oracle.pnl.gov
  10. Reply-To: d3g637@duke.oname
  11. Organization: Battelle/Pacific Northwest Laboratories
  12. Lines: 61
  13.  
  14. In article 82z@undergrad.math.waterloo.edu, icfaragh@cayley.waterloo.edu (Chad Faragher) writes:
  15. >
  16. >The situation:  An image is stored by giving the rgb value for each pixel.
  17. > 
  18. >The problem:  How to find the best palette of size-n for a particular image
  19. >stored (at arbitrary resolution) as above.
  20. > 
  21. >The solution:  HELP!!!
  22. >
  23. >Does the algorithm exist?  Is it memory intensive?  Can it be solved with 
  24. >recursion (ie octree division)? 
  25.  
  26. If my memory serves me an approach to such a beast is to figure out a
  27. 3D histogram (RGB axes) of the image.  Then select the
  28. regions with the highest density of entries and define colors for each
  29. region.  You need to define the permissible deviation from the original
  30. color.  The greater the permissible deviation the fewer palette entries
  31. you will need.  The relationship between the deviation and the number
  32. of entries is understandably unique to each image.  The net result of
  33. this operation is a table which defines RGB values for each entry in
  34. the table.  Then you go through each pixel in the image and map it
  35. to the palette entry by finding which entry's RGB values are closest to
  36. the pixels value.  Note that the RGB value you choose at a given 
  37. entry may not _actually_ occur in the image, but may instead be
  38. a kind of local centroid. 
  39.  
  40. BTW: a three dimensional histogram is a ***VERY*** memory intensive
  41. affair.  There are ways around that problem though.  For example you
  42. don't actually allocate a 256x256x256 histogram (assuming 24 bit RGB images)
  43. table but simply record them as you go along.  Then again, there's a
  44. speed cost.
  45.  
  46. >Can a neural-net be trained to arrive at
  47. >a visually pleasing palette given the original image?
  48. > 
  49. >All input welcome.
  50. > 
  51. >Chad Faragher -- University of Waterloo
  52.  
  53.  
  54. I can conceive of a neural net to do such a thing, but WOW!  You could
  55. for example use a 256x256x256 input layer and a n-sized (palette entries)
  56. output layer with RGB values.  Better yet you might simply provide the
  57. image as an input and the palette as the output. 
  58. I'm not very confident of these schema though,
  59. they seems neither practical nor effective.  The training might work for a
  60. given type of image, but I'm not sure it would work for all types.
  61. I wonder if anyone's had any more practical ideas. It does sound like something
  62. worth pursuing.  Neural Nets have been used for stock market analysis and that's
  63. also a multidimensional statistical problem. Who knows...
  64.  
  65. BTW: how do you define visually pleasing?  I consider the algorithm effective
  66. iff I cannot distinguish between the original and the compressed image on
  67. a given medium.  It's a pretty binary test, and has little to do with pleasure.
  68. Of course the medium of display is important to consider.
  69.  
  70.  
  71.         Dave Chassin
  72.         Email: dp_chassin@pnl.gov           "Life is either a daring
  73.         Vox: (509)375-4369                    adventure or nothing"
  74.         Fax: (509)375-3614                           - Helen Keller
  75.