zap@lysator.liu.se (Zap Andersson) (04/30/91)
Hello, fellow netters and fellow graphicists (!?) I have always, always, always wondered one thing: * Is there ANY sane reason whatsoever, when trying to quantize a 24 bit image to an 8 bit image, to make a histogram? As I see it, the fact that a certain color is used MORE OFTEN than another, has NOTHING whatsoever to do with if it should be found in the palette or not. I have a good example of this. Assume I have a 24 bit image of a small, red, spaceship flying in front of a rainbow-colored background. The spaceship only occupies about 4-5% of the image, nevertheless it is very important that it is represented accurately. However, the background, being so massively over-represented in the image, (and so variant in color) rips all 256 palette entries from under our feet, leaving none (or very few) to the spaceship! If *I* had been the quantizer, I would have realized that the ship was important, and perhaps replaced the rainbow background with a red, a green and a blue color (3 colors!!) that via dithering created the 'same' rainbow effect. Then I would use the other 253 colors for the spaceship. Ok, that was a bit drastic :-) but think of how much gain there could be in letting the RENDERER do the quantization as the image is built, because it may 'know' such things (this surface is less important, that is more important). But the loss is also obvious: The renderer cannot now a priori how the image will look, until it IS rendered....and it must 'try and fail' to squeeze colors into the palette, and then squeeze the PALETTE if it gets full. This can be a time consuming task (I know - my renderer does exactly this). However, the RESULT of my renderer is MUCH better 8 bit images than using any 'standard' algorithm. And the main bottleneck (I think) is the histo- gram they (all?) use. To create one, you need to pre-quantize to a manageable number of colors, most often 5 bits per channel, yielding 15 bits (32768 colors). BUT 5 BITS PER COLOR IS NOT ENOUGH! If you forget the pre-quantization stage, and forget that stupid histogram (that only decreases image quality) the result is much better. What I like to "know" is: Q: Any comments on the above? Q: When are these STUPID 8 bit displays gonna disappear for good :-) ? /Z -- * * * * * * * * * * * * * * * * * (This rent for space) * My signature is smaller than * Be warned! The letter 'Z' is Copyright 1991 * yours! - zap@lysator.liu.se * by Zap Inc. So are the colors Red, Green and * * * * * * * * * * * * * * * * * Greenish-yellow (Blue was taken by IBM)
coy@ssc-vax (Stephen B Coy) (05/02/91)
In article <606@lysator.liu.se> zap@lysator.liu.se (Zap Andersson) writes: >* Is there ANY sane reason whatsoever, when trying to quantize a 24 bit > image to an 8 bit image, to make a histogram? Yes, sometimes it looks better when the popularity of the colors is taken into account. Sometimes it also looks worse. So allow the user to experiment and decide for each image. >However, the RESULT of my renderer is MUCH better 8 bit images than using >any 'standard' algorithm. Rendering and color quantization are two seperate processes. Are you saying that your renderer is better than others you've seen or that your quantization is better? >To create one, you need to pre-quantize to a >manageable number of colors, most often 5 bits per channel, yielding >15 bits (32768 colors). BUT 5 BITS PER COLOR IS NOT ENOUGH! You're right. For most images 5 bits is not enough. I've found for converting to VGA that 6 bits works best. Since VGA cards have 6-bit DACs this should be no surprise. Keeping track of 18bit color running under MSDOS is challenging but not impossible. BTW I've seen some of the anims from RayTracker. Looks like a nice program. If you'd like to see what I consider fairly good quantization get a copy of my ray tracer, Vivid. It's somewhere out there... The quantization program I include does do a histogram but allows you to limit the max count for a color. Stephen Coy coy@ssc-vax.UUCP
graeme@labtam.labtam.oz (Graeme Gill) (05/02/91)
In article <606@lysator.liu.se>, zap@lysator.liu.se (Zap Andersson) writes: > I have always, always, always wondered one thing: > > * Is there ANY sane reason whatsoever, when trying to quantize a 24 bit > image to an 8 bit image, to make a histogram? > > As I see it, the fact that a certain color is used MORE OFTEN than another, > has NOTHING whatsoever to do with if it should be found in the palette or > not. Unfortunately it is difficult to make a computer program see a picture the way a human sees it. It is only a human judgment that a spaceship on a background is the most important object in a scene. Not having the ability to program an "AI" module into a 24 to 8 bit quantizer, it is necessary to fall back on other means of assessing the importance of objects in a scene - like their relative popularity. Sometimes this produces poor results. The suggestion I have is that if you want to be able to get good results on all scenes, then you need a means of telling the quantizer what parts of a picture are of high interest, and what areas are of low interest. - ie. put a human in the loop to asses the importance of objects within a picture (after all, the desired result is to please someone looking at the picture). This feature could be added to something like rlequan (The variance based 24 to 8 bit quantiser in the URT toolkit) by making it understand comments inserted into the source file of the form: area_of_interest=x,y,w,h,m where x and y are the integer co-ordinates of the bottom left corner of the area of interest, w and h are the width and height of the rectangular area of interest, and m is the floating point multiplier. (Note that the URT toolkit uses a co-ordinate system with 0,0 being at the bottom left). Comments can be added and deleted with rleaddcom, and examined with rlehdr. rlequant would need to be hacked to recognize the comments and scale the stats. of the pixels falling within the area by the multiplier m. This way you could force the quantizer to allocate more colour maps to the area of interest, and "fine tune" the result to your taste. The advantage of having this info as comments in the source file is that the 8 bit file can be re-created automatically. I haven't got around to trying this idea out yet. The main reason that most quantizer pre-quantize the 24 bit image to 15 bits is so that they can build the histogram in a 2^15 table. One can keep full 24 bit precision by using a different data structure (ie. a linked list), but this can use a lot of memory, and can be rather slow in accumulating the statistics on input and in locating the nearest colours on output. I have written a quantizer that maintains full 24 bit precision throughout, and it does not add a great deal to the picture quality. Graeme Gill Labtam Australia
zap@lysator.liu.se (Zap Andersson) (05/03/91)
coy@ssc-vax (Stephen B Coy) writes: >>However, the RESULT of my renderer is MUCH better 8 bit images than using >>any 'standard' algorithm. >Rendering and color quantization are two seperate processes. Are >you saying that your renderer is better than others you've seen or >that your quantization is better? Ok, I've tried Autodesk 3D studio. Output stinks in 320x200 VGA. I've tried Autodesk renderman and quantized with their own 'convert' program. Still stinks (same algo I assume). I think they prequantize to 5 bits, then do some median-cut with or without dithering (dont know what kind, guess it's floyd-Steinberg). I still think it stinks. Perhaps, like you said , it's all in the 5 bit preQ that i do not do. Dont know. (My 'aim' with my posting was to get some interesting discussion back into comp.gfx) :-) >>15 bits (32768 colors). BUT 5 BITS PER COLOR IS NOT ENOUGH! >You're right. For most images 5 bits is not enough. I've found for >converting to VGA that 6 bits works best. Since VGA cards have >6-bit DACs this should be no surprise. Keeping track of 18bit color >running under MSDOS is challenging but not impossible. Ah, but could someone tell me WHY i should keep track at them ,eh? Here is the hated histogram again! I can agree that you have a one- bit histogram that tells if a color is used at all or not. But not more. >BTW I've seen some of the anims from RayTracker. Looks like a nice >program. If you'd like to see what I consider fairly good Ehem :-) some of the tolsun.oulu anims are farily old (sweat shudder) so you shouldn't (sweat shudder shudder) judge on those (sweat sweat) :-) I could mail you a new-ish image if you like. Just mail me a 'yo'. >quantization get a copy of my ray tracer, Vivid. It's somewhere out >there... The quantization program I include does do a histogram but >allows you to limit the max count for a color. Sounds clever! >Stephen Coy >coy@ssc-vax.UUCP -- * * * * * * * * * * * * * * * * * (This rent for space) * My signature is smaller than * Be warned! The letter 'Z' is Copyright 1991 * yours! - zap@lysator.liu.se * by Zap Inc. So are the colors Red, Green and * * * * * * * * * * * * * * * * * Greenish-yellow (Blue was taken by IBM) -- * * * * * * * * * * * * * * * * * (This rent for space) * My signature is smaller than * Be warned! The letter 'Z' is Copyright 1991 * yours! - zap@lysator.liu.se * by Zap Inc. So are the colors Red, Green and * * * * * * * * * * * * * * * * * Greenish-yellow (Blue was taken by IBM)
zap@lysator.liu.se (Zap Andersson) (05/03/91)
graeme@labtam.labtam.oz (Graeme Gill) writes: >In article <606@lysator.liu.se>, zap@lysator.liu.se (Zap Andersson) writes: >> I have always, always, always wondered one thing: >> >> * Is there ANY sane reason whatsoever, when trying to quantize a 24 bit > Unfortunately it is difficult to make a computer program see a picture >the way a human sees it. It is only a human judgment that a spaceship on a >background is the most important object in a scene. Not having the ability >to program an "AI" module into a 24 to 8 bit quantizer, it is necessary to Ah, but that was one of my small 'points': The renderer knows, and since it is the renderer doing quantization in my case, things can get nice. (but slow) :-( >fall back on other means of assessing the importance of objects in a scene - >like their relative popularity. Sometimes this produces poor results. Yeah, that is agreed. I'm not interested in ye olde quadliteral 'area of interest'. Someone (hi someone, my mail to you bounced :-( ) suggested render the spaceship with an alpha channel and overlay separately with an intelligen quant software, and I agree totally. But IS there some intelligent overlay-32-bit-images-with-different-criteria-of-importance- while-qiantizing-to-8-bit-code.c source around :-) >statistics on input and in locating the nearest colours on output. I have >written a quantizer that maintains full 24 bit precision throughout, and it >does not add a great deal to the picture quality. No, but 5 vs 6 bits makes a LOT of difference (it's just on the edge of what you see, especially at yucky resolutions, such as PC bleach 320 x 200 that I'm (semi) stuck with :-( ((and must support)) ) > Graeme Gill > Labtam Australia -- * * * * * * * * * * * * * * * * * (This rent for space) * My signature is smaller than * Be warned! The letter 'Z' is Copyright 1991 * yours! - zap@lysator.liu.se * by Zap Inc. So are the colors Red, Green and * * * * * * * * * * * * * * * * * Greenish-yellow (Blue was taken by IBM)
graeme@labtam.labtam.oz (Graeme Gill) (05/08/91)
In article <610@lysator.liu.se>, zap@lysator.liu.se (Zap Andersson) writes: > render the spaceship with an alpha channel and overlay separately with > an intelligen quant software, and I agree totally. But IS there some > intelligent overlay-32-bit-images-with-different-criteria-of-importance- > while-qiantizing-to-8-bit-code.c source around :-) That would be a good way of letting the renderer supply the information, while still allowing the quantization to take place as a separate procedure. (The UNIX toolkit approach is a fairly powerful one) The URT file format allows for up to 256 channels per pixel, so it would be relatively easy to add this to a renderer and quantizer that uses this format. By convention, channels 0,1 and 2 are red, green and blue, and channel 255 is the alpha channel. You could choose one of the other channels to carry importance weighting information. I am not convinced that it is any easier for the renderer to figure out which objects are of interest than it is for the quantizer though. It is typical of art that a collection of otherwise un-interesting objects will attract ones interest when arranged, lit and viewed in certain ways. This is a purely human interpretation. > No, but 5 vs 6 bits makes a LOT of difference (it's just on the edge > of what you see, especially at yucky resolutions, such as PC bleach > 320 x 200 that I'm (semi) stuck with :-( ((and must support)) ) I still suggest you try out rlequant. It has consistently given me good results where other quantizer using median cut have failed dismally. Graeme Gill Labtam Australia
bobl@tessi.UUCP (Bob Lewis) (05/10/91)
In article <606@lysator.liu.se> zap@lysator.liu.se (Zap Andersson) writes: ... >However, the RESULT of my renderer is MUCH better 8 bit images than using >any 'standard' algorithm. And the main bottleneck (I think) is the histo- >gram they (all?) use. To create one, you need to pre-quantize to a >manageable number of colors, most often 5 bits per channel, yielding >15 bits (32768 colors). BUT 5 BITS PER COLOR IS NOT ENOUGH! If you >forget the pre-quantization stage, and forget that stupid histogram (that >only decreases image quality) the result is much better. > >What I like to "know" is: > >Q: Any comments on the above? As you suggest, the pre-quantization isn't really necessary. It's still possible to use a histogram, though, if you treat the it as a sparse array with hashed indices derived from the 24-bit (or whatever) RGB values. This is, of course, a big virtual memory consumer if the input image has distinct values in every pixel, but it seems to perform adequately on typical (SPD, for example) images, which typically only have a few thousand distinct values. Your "tiny spaceship and big rainbow" example is a good one. Median cut (the way I do it, at least) does ignore spatial coherence. Perhaps the algorithm could be enhanced to give additional weight to values of pixels surrounded by pixels with similar values. The more similar, the greater the weight. >Q: When are these STUPID 8 bit displays gonna disappear for good :-) ? Probably about the time we can get the 24-bit wall units. Ah, progress! B-) - Bob Lewis ...!sun!nosun!tessi!bobl