From david@epicb.UUCP Sat Sep 17 15:57:56 1988 Path: leah!uwmcsd1!mailrus!ames!vsi1!altnet!uunet!epicb!david From: david@epicb.UUCP (David P. Cook) Newsgroups: comp.graphics Subject: Re: Color Pallet Mapping? Message-ID: <522@epicb.UUCP> Date: 17 Sep 88 19:57:56 GMT References: <101880001@hpcvlx.HP.COM> Reply-To: david@epicb.UUCP (David P. Cook) Organization: Truevision Inc., Indianapolis, IN Lines: 126 In article <101880001@hpcvlx.HP.COM> btc@hpcvlx.HP.COM (Bob Clark) writes: >I am using an AT&T Targa 16 board to capture images from a video camera. >It stores each pixel in RGB with 5 bits/color. I would like to display >the image on a VGA display, except that it only has a color pallet of >256 colors. How should one map from the larger color pallet to the >smaller one? I naively thought this would be trivial, but am not satisfied >with my results. > >Also, as a side question, how to you map from RGB to HLS? Bob: Let's deal with the easy question first... that is, how to convert RGB to HLS. For a good reference, refer to: Fundamentals Of Interactive Computer Graphics By: J. D. Foley and A. Van Dam Pages 618 - 619 (section 17.4.5) gives the code... and eariler sections give the code for RGB to HSV. Also covered, is the reverse conversion. If you do not have the book handy (unbelievable), let me know via E-Mail and I will post you a copy of the pseudo-code. It's really pretty easy and only a few lines of code, and can be adapted to assembly language fairly simply. Now, for your RGB to Color Map question... This is more tough, since in the Targa 16, there are 32,768 colors possible. There are many approaches, three of which I will list here: Method #1: Conversion of the Color Map to a RGB simulation map In this method, you will create a RGB map out of the color map space. Since the VDA card has a total of 256 colors allowed at a time, this could be thought of as a 3 x 3 x 2 color space (as opposed to the T16 space of 5 x 5 x 5.) Note we diminish blue by one bit because blue is naturally recessive, and not easily seen anyways. With three bits per pixel, we get 8 levels of RED, 8 levels of GREEN and four levels of Blue (the 2 instead of 3). Now, since your color is actually 8 bits long (on the VDA), simply take your T16 color and shift the RED two bits to the right, the GREEN two bits to the right and the BLUE three bits to the right... this will give you an 8 bit number which will look-up in the color map. To color the map properly, simply divide 255 by 8 and place the interleaved colors into the map at the appropriate point (ie... Color Map 0: Red = 0, Green = 0, Blue = 0 Color Map 1: Red = 32, Green = 32, Blue = 64 etc.. This method will allow you to get a 'full color' image into the VDA space. Methods #2 and #3: Color selection The drawback to method #1 is that it uses the entire color space. You may, on the other hand, have an image which is primarily one or two tones (ie... perhaps the image is basically reds and tans, with no greens or blues). In this case, much of your VDA map is wasted. For this solution, you can COMPRESS the original image. Two methods exist: Popularity reduction: In popularity reduction, you would take only 256 of the most popular colors in the original T16 image. This is accomplished by counting the frequency of all the colors in the image, a simply task, and then sorting the result from most frequent to least. When you are done, only take the top 256 colors off the list and squirt them over to the VDA. This is accomplished by simply comparing each color in the original image to the 256 most frequent colors from your histogram anaylisis, and determing which color from your anaylisis is closest to the color in the image. Simple no! Color Cube Compression: The problem with Popularity is that occasionally, colors with the least frequency are important. For example, an image of a person with bright blue eyes. A person will have colors in the tanish range, while the eyes will be in the blue range. Since there will be MUCH MORE tanish colors, to blue colors (based on area of coverage) it is probable that the blue will be lost and converted to some form of blueish red. Color Cube compression circumvents this. Consider RGB color space... it can be thought of as a CUBE with black in one corner, red green and blue connected to black as the three dimensional axis of the cube, and cyan, magenta and yellow as the connections to the red, green and blue axis, with white in the opposite corner of the cube from black (draw it on paper, or look in Fundamentals for a picture). If you anaylize your T16 image, you will find that it contains some sub-set of the full RGB space. (IE.. what is the lowest red, green and blue, and the highest red, green and blue). This will create a sub-cube which fits somewhere on or inside of the total RGB cube. Now, you want a total of 256 colors in your final image... the trick is to subdivide the sub-cube into 256 smaller cubes.. To do this, you take the LONGEST AXIS and determine the half-way point (not true half way, but half way based on frequency along that axis) Subdivide the cube at that point. Now continue with the NEXT LONGEST AXIS... keep doing this until you have 256 sub-cubes. Now, convert the image simply by reading a color from the T16 image, determining what sub-cube it lays in and substituting it with the AVERAGE color from that sub-cube. While this last method is much more difficult to visualize, it gives the most promising results. This last method was written up in a SIGGRAPH proceedings, but I don't have the book in front of me at the moment or I would give you the issue and page number... however, I think it is from the 1985 issue (if not 85, than 84 or 86, but I'm pretty sure it's 85) and the article is towards the end of the issue and has pretty pictures of bison and color space... easy to find (I think the picture on the front of the issue is the Solar Sailor from TRON)... The article was, I believe, written by XEROX, and is called Floyd-Stineberg Dithering (hence, I believe the authors are Floyd and Stineberg, but don't quote me on that, without the article in front of me, it's alittle hard for me to remember). (Floyd or Stineberg, if your reading this, sorry, I probably spelled your names wrong too... I know your famous, I'm just forgetful, its not you, its me... sorry!) Hope this answers your questions. Feel free to E-Mail me any other questions you may have concerning your problem. -David Cook Truevision Inc. tongue -- | David P. Cook Net: uunet!epicb!david | | Truevision Inc. | "Specialization is for insects" | | Indianapolis, IN | -- Timothy Leary | -----------------------------------------------------------