btc@hpcvlx.HP.COM (Bob Clark) (09/14/88)
Help!
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?
All comments, pointers, hints, clues and remarks are gratefully accepted.
Thanks in advance,
Bob Clark
Hewlett-Packard PCD
Corvallis, OR
{ucbvax!hplabs, harpo, ogcvax}!hp-pcd!hpcvlo!btc
btc%hp-pcd@hplabs.hp.comdavid@epicb.UUCP (David P. Cook) (09/18/88)
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 | -----------------------------------------------------------
naughton%wind@Sun.COM (Patrick Naughton) (09/18/88)
Yes folks... It's official! This is now the ``Most Asked Question on Comp.Graphics'' >> I have this image data... and it has more colors than my display... >> and I still want to see the correct colors. How do I do it? Well the last answer posted for this was mostly correct. I have a couple of nits though: Lou's last name is spelled Steinberg, not Stineberg. And the median-cut algorithm attributed to him is actually due to the man who brought us all "Ray Traced Bill Cosby Commercials..." Paul Heckbert, UCB CS grad student, and one of the only people on the net to actually flame himself. (remember the people without a sense of humor who flamed Paul for the Jell-O paper? well he was one of them... :-) I have coded and used both of these guys' algorithms and have been putting them to good use for some time now. (My first posting to comp.graphics asked this very question, to which Paul and Lou both responded personally, with code examples... Isn't USENET a wonderful resource?) Anyway, if you are looking to reduce color image data to a bilevel device such as a mono-printer, use F/S dithering only because you already know the that the colors in the output colormap are black and white; and use the CIQ algorithm for reducing the number of colors when the output is more than monochrome. In the latter case, F/S dithering after CIQ color selection can reduce some of the contours in cases where there are a low number of output colors (i.e. 16 or lower). At 256 output colors, the images sometimes look better w/o dithering. Good luck... here are the references to the original papers. Floyd, R.W. and Steinberg, L. ``An Adaptive Algorithm for Spatial Gray Scale.'', Proceedings of the Society for Information Display, Volume 17, Number 2, 2nd quarter 1976. Heckbert, Paul ``Color Image Quantization for Frame Buffer Display'', SIGGRAPH Proceedings on Computer Graphics, Volume 16, Number 3, June 1982, p. 297. -Patrick __________________________________________________________________ Patrick J. Naughton ARPA: naughton@Sun.COM Window Systems Group UUCP: ...!sun!naughton Sun Microsystems, Inc. AT&T: (415) 336 - 1080 ---``The X11/NeWS Merge... I love it now... you'll love it soon.'' ______________________________________________________________________ Patrick J. Naughton ARPA: naughton@Sun.COM Window Systems Group UUCP: ...!sun!naughton Sun Microsystems, Inc. AT&T: (415) 336 - 1080
jevans@.ucalgary.ca (David Jevans) (09/20/88)
In article <522@epicb.UUCP>, david@epicb.UUCP (David P. Cook) writes: > > 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 > 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: > ... > Color Cube Compression: ref: Proceedings of SIGGRAPH '85 Used a median cut algorithm to determine "best" colors. > ... Another reference for color cube compression is Proceedings of Computer Graphics International '88 (Geneva). I'm not sure of the author 'cuz the ref is in my office and i'm posting from home. Anyway, the proceedings are published every year in book format by Springer-Verlag. This year one (or both?) of the Thallmanns (sp?) from Montreal was (were) the editor(s). Essentially the author of the CGI paper used an octree data-structure which is allowed to have N root nodes (N = # of entries in your colortable). As colors are read in from a file they are inserted into the octree. When there are more than N colors the deepest nodes are merged into one color which is their weighted average. After the image has been read once the colortable is made (traverse the octree). The image is then re-read and each pixel's colortable value is found by indexing into the octree in the same manner as it was created. This results is fairly fast display time once the octree has been built since the colortable doesn't have to be searched for the nearest color to a given pixel's color. I implemented this algorithm one afternoon for my 8bit-color sun3/60. I wanted to be able to display my 24bit images without having to walk over to the the graphics lab and using an iris. If anyone is interested in the program you can try to email me and I'll send it. A friend ported it to an 8bit iris last week, so that is probably available too. The format that they use is a simple non-run-length-encoded rgb binary format with the xsize and ysize at the front of the file. It shouldn't take anyone more than a few minutes to convert to a different format. Dave Jevans (jevans@cpsc.UCalgary.CA <- probably incorrect?!?) "I've been waiting for a guide to come and take me by the hand."
pf@diab.se (Per Fogelstr|m) (09/24/88)
In article <7@cs-spool.calgary.UUCP> jevans@.ucalgary.ca (David Jevans) writes: > [ Description of implementation deleted ] > >I implemented this algorithm one afternoon for my 8bit-color sun3/60. I wanted >to be able to display my 24bit images without having to walk over to the >the graphics lab and using an iris. If anyone is interested in the >program you can try to email me and I'll send it. A friend ported it >to an 8bit iris last week, so that is probably available too. > >Dave Jevans (jevans@cpsc.UCalgary.CA <- probably incorrect?!?) Indeed it is ! All my tries have bounced !! I would like a copy of your program but been unable to reach you at this address. I have a few other algorithms wich works both quite good and less.. From your description i think i could do something similar but if you want to share your program i would be glad. It should save me some hacking.
falk@sun.uucp (Ed Falk) (10/03/88)
In article <522@epicb.UUCP>, david@epicb.UUCP (David P. Cook) writes: > 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. I recently posted an implementation of the Median Cut algorithm described by Heckbert in the '82 Siggraph proceedings. Try to look it up, it's pretty much the best source on this algorithm. If you can't find my median-cut implementation, let me know and I'll mail you a copy. -- -ed falk, sun microsystems sun!falk, falk@sun.com terrorist, cryptography, DES, drugs, cipher, secret, decode, NSA, CIA, NRO.