bolte@umn-cs.UUCP (05/27/85)
Greetings: I am doing some ray tracing as an independent study project and have run up against a brick wall. The problem is allocating the color lookup map (8 bits deep) properly to match whatever distribution of colors result from any single run. I would appreciate either algorithms other people have worked out or a reference to a paper on the topic. Thanks in advance, Scott Bolte U. of Minnesota AI Lab CSNET:bolte.umn-cs@csnet-relay USNET:ihnp4!umn-cs!bolte Motto of the month: SIGGRAPH or Broke!
papke@dicomed.UUCP (Kurt Papke) (05/29/85)
In article <12800001@umn-cs.UUCP> bolte@umn-cs.UUCP writes: >have run up against a brick wall. The problem is allocating the color >lookup map (8 bits deep) properly to match whatever distribution of colors >result from any single run. I would appreciate either algorithms other people >have worked out or a reference to a paper on the topic. > There is an excellent paper on exactly that topic in the July '82 edition of the Siggraph Proceedings (Volume 16, No 3). It is entitled: "Color Image Quantization for Frame Buffer Display" by Paul Heckbert, then of NYIT/CGL. In it he describes several algorithms for getting the most of an 8-bit frame buffer with a LUT. Happy ray tracing !!
wfi@rti-sel.UUCP (William Ingogly) (05/30/85)
In article <12800001@umn-cs.UUCP> bolte@umn-cs.UUCP writes: > I am doing some ray tracing as an independent study project and >have run up against a brick wall. The problem is allocating the color >lookup map (8 bits deep) properly to match whatever distribution of colors >result from any single run. I would appreciate either algorithms other people >have worked out or a reference to a paper on the topic. It's not clear to me whether you're having problems understanding how the color lookup process works, or how to actually assign colors to the map. At any rate, the following references should help: Fundamentals of Interactive Computer Graphics, by J.D. Foley and A. Van Dam -- Section 12.4 has a discussion on storing lookup table entries. You should also read Chapter 17, on intensity and color. Color Table Animation, by R. Shoup, in SIGGRAPH '79 Proceedings. This tells how to store multiple images in a frame buffer for animation and manipulate the display by changing lookup table entries. Color Map Techniques, by K. Sloan and C. Brown, in Computer Graphics and Image Processing, Vol. 10 Num. 4, August 1979. I haven't read this article, so I can't tell you much about it. The widely-available Principles of Interactive Computer Graphics isn't very helpful on this topic, unfortunately. -- Cheers, Bill Ingogly
dmmartindale@watcgl.UUCP (Dave Martindale) (06/06/85)
This is a hard problem, I think. What you really want is to find a set of 256 points in RGB space such that when the set of all colours present in the image are each mapped to their nearest represented colour, the sum of the errors are minimized. And you probably want to weight this sum according to the visibility to the eye of each error. I think there was a paper presented at SIGGRAPH a year or two ago that dealt with the subject; unfortunately my proceedings are still packed somewhere. What most people do with 8-bit frame buffers is just allocate 3 bits for red, 3 bits for green, and 2 bits for blue. The colour map is easy to build, and encoding the pixels is easy. If you want the image to look realistic, don't forget to include gamma correction when building the colour map.
leo@apple.UUCP (Leo Hourvitz) (06/10/85)
The problem of finding an optimal color map for a given image was discussed by Paul Heckbert: "Color Image Quantization for Framebuffer Display," Siggraph '82, page 297. He discusses two algorithms he had used, plus variations/extensions, etc. The basic methods he examines are popularity alogrithm (pick the most popular colors) and median cut algorithm (read the paper). I have C code for popularity alogrithm, write if interested. Enjoy, Leovitch leo%apple.csnet (Leo Hourvitz)
skinner@saber.UUCP (Robert Skinner) (06/10/85)
*** REPLACE THIS LINE WITH YOUR MESSAGE *** > This is a hard problem, I think. What you really want is to find a set > of 256 points in RGB space such that when the set of all colours present > in the image are each mapped to their nearest represented colour, > the sum of the errors are minimized. And you probably want to weight > this sum according to the visibility to the eye of each error. > I think there was a paper presented at SIGGRAPH a year or two ago that > dealt with the subject; unfortunately my proceedings are still packed > somewhere. > The paper that Dave is refering to is in the 1982 SIGGRAPH proceedings, page 297, "Color Image Quantization for Frame Buffer Display. What this amounts to, it seems, is a two dimensional sort of the color space, with a correction for colors that are poorly represented. (i.e. if the image has a little blue, but mostly red and green, we don't want to exclude blue from the color map entirely as a straight sort would imply.) > What most people do with 8-bit frame buffers is just allocate 3 bits for > red, 3 bits for green, and 2 bits for blue. The colour map is easy > to build, and encoding the pixels is easy. If you want the image > to look realistic, don't forget to include gamma correction when > building the colour map. The above method of truncation is easy and accurate for 8 bits, but it breaks down quickly if the target frame buffer has only 4 or 3 bits (color hardcopy). The last section of the above article describes a good dithering algoritm that I have used successfully in reducing 24 bit images down to 3 bits for a color printer. The paper uses integer fractions, where I used floats, and I extended the color error in four directions instead of three, but the principle is the same. To me, the dithering algorithm resembles Bresenham's line drawing algorithm extended to two dimensions. Surprisingly, the dithering method works best for high frequency information (hair), but tends to show contouring for smooth shades. Preventing the contouring is something I'd like to spend some time researching in the future. One of the images I used this algorithm on while at Seiko Instruments was of a blonde girl holding a cat. Seiko gives away lots of hardcopies of this image at Siggraph and NCGA, so its fairly easy to get a look at the results. I will also be glad to give any more information to those that want it. Robert Skinner Saber Technology, Inc. San Jose, CA
ken@turtlevax.UUCP (Ken Turkowski) (06/10/85)
In article <12800001@umn-cs.UUCP> bolte@umn-cs.UUCP writes: > I am doing some ray tracing as an independent study project and >have run up against a brick wall. The problem is allocating the color >lookup map (8 bits deep) properly to match whatever distribution of colors >result from any single run. I would appreciate either algorithms other people >have worked out or a reference to a paper on the topic. There was a paper in the February 1984 issue of IEEE Computer Graphics and Applications by A.F. Lehar and R.J. Stevens called "High-Speed Manipulation of the Color Chromaticity of Digital Images". It scans the 3-dimensional color space with a Peano curve, yielding a 1-dimensional signal that is trivial to cluster for quantization purposes. While suboptimal, it is very fast and quite produces remarkable results. If the quantization isn't quite good enough, it can be used as the starting point of an iterative optimal clustering procedure. -- Ken Turkowski @ CADLINC, Menlo Park, CA UUCP: {amd,decwrl,hplabs,nsc,seismo,spar}!turtlevax!ken ARPA: turtlevax!ken@DECWRL.ARPA
ph@nyit.UUCP (Paul Heckbert) (06/25/85)
> ... The problem is allocating the color > lookup map (8 bits deep) properly to match whatever distribution of colors > result from any single run [of my ray tracer] ... Thanks to Kurt Papke and Leo Hourvitz for recommending my SIG'82 paper. It sounds like Scott basically has two choices: (a) Generate and store the picture in full color (24 bits) and then quantize down to 8 bits as a post-process, by looking at the statistical distribution of the picture's colors. (b) Pick a colormap a priori and quantize all pictures to it. 3 bits red, 3 bits green, 2 bits blue works well. The first method is more difficult but can yield superior results. The latter method can be done on the fly, so that the picture is written to the frame buffer as it is computed, and it also has the advantage that all of the pictures will use the same colormap, which makes compositing easier. In either case I recommend dithering. [ADVERTISEMENT] If you're into other 8-bit frame buffer tricks, perhaps you'd be interested in another paper I wrote: Techniques for Real-Time Frame Buffer Animation FX'84, London, Oct. 1984 I'll mail you a copy if you send your USmail address. Paul Heckbert NYIT Computer Graphics Lab ucbvax!decvax!philabs!sbcs!nyit!ph allegra!sbcs!nyit!ph (Sorry about the delay on this response; we've had some network problems here for the past few weeks) -- ucbvax!decvax!philabs!sbcs!nyit!ph Paul Heckbert allegra!sbcs!nyit!ph NYIT Computer Graphics Lab