williams@vu-vlsi.UUCP (Thomas Williams) (01/12/87)
Question #2: Choosing colors
What's the best way to choose 256 24-bit colors from the possible
thousands (millions?!) which are used in an image. Supposedly a method
called 'median cut' was described in "Color image quantization for frame
buffer display", but this is an old-reference and I don't have the author's
name or publication (though it's probably Computer Graphics). Any ideas?
Question #1: The fractal dimension
I have always thought that a fractal dimension of 1 caused very flat
surfaces/lines and as this dimension approaches let`s say 2 the surface
or line become irregular and jagged. I even once remember reading that
with iteritive subdivision like in koch curves the fractal dimension equals
log(N)/log(1/r) where N is the number of sub-pieces resulting from an
iteration and r was the ratio of the size of the original piece to the
the size of the subpiece. (So if each piece is broken into 4 pieces each
1/3 the original size the fractal dimension would be 1.26, which gives
fairly nice results). Anyhow, I've just looked over a paper [1] which
describes gaussian random numbers to be chosen with a standard deviation
of S= k * 2**(-i*H), where i is the iteration level, k is a scale factor
and H is the fractal dimension. If this is true then I'm totally wrong
because a larger fractal dimension would usually create a smoother surface,
and a smaller one a more perturbed surface. Is this a 'different' fractal
dimension, or what?
[1] Gavin S.P. Miller, The Definition and Rendering of Terrian Maps,
SIGGRAPH '86, Computer Graphics, Vol 20, No 4.
Question #0:
Do any companies hire entry-level programmers for computer graphics
work? I haven't seen any so I'm beginning to think they only hire
PHD's or consultants with decades of experience. Who does most of the
hiring anyway, hardware manufacturer's.. software companies???????!
-thomas williams
------------------------------------------------------------------------------
UUCP: williams@vu-vlsi
BITNET: 135609021@vuvaxcomsierchio@milano.UUCP (01/14/87)
First of all, the choice of an arbitrary color set to represent an image is one I've been working on for some time. 256 is a tough one, since you can't allocate a certain number of bits/component as you can if you have 512 (ffor e.g.). The question is, what are you willing to give up? You may have to give up some spatial resolution by dithering, and thereby alleviating some of the problems associated with an arbitrary color set. Anyway, here's my strategy (you can quote me, and feel free to give me credit for the idea if it doesn't work for you :-) ) The basic approach is that of histogram specification. (get a book on image processing) 1) Construct a histogram of the colors actually in the picture. There aren't, by the way 16 million, since you surely don't have that many pixels! The histogram should be a three- dimensional matrix that counts the incidence of each triple (e.g., this 256 x 256 x 256 matrix will have in location [12, 3, 154] the number of pixels with that amnt. of R, G and B, respectively.) 2) The next task is more complicated and less susceptible to automation, but I didn't say this was easy. You must then find 256 (in your case) loci in this space based on a kind of "gravitational attraction" approach. These loci will be the colors that nearby colors will be mapped to. 3) In order not to get ugly quantization effects, which may occur because of the arbitrary boundaries that get drawn between these subspaces that map to points, I suggest that you dither the image when you map it to the reduced-color-map space. That means that the process of converting the image involves reading a pixel from the original image as input, using the histogram and color map you've constructed from it to get a new number (the locatiopn in the palette of the 256 colors you've chosen) and mapping it to the new image. If the actual values of the pixel in the original image place it near the boundary of another subspace, that's where the dithering comes in -- sometimes you will want to map it to the center of the nearby space. I hope this helps you some. As to fractal dimension, a line has a fractal dim of 1, so nearly linear objects have a fractal dim near 1. A plane has fractal dim of 2, so that fractal curves that have a smaller void fraction and nearly fill the space of a plane are near dim 2. -- Michael Sierchio @ MCC Software Technology Program UUCP: ut-sally!im4u!milano!sierchio ARPA: sierchio@mcc.ARPA "WE REVERSE THE RIGHT TO SERVE REFUSE TO ANYONE"
sierchio@milano.UUCP (01/15/87)
I was remiss in not referring you to the article on ~2bit/pixel quantization in SIGGRAPH '86 Conference Proceedings, as well as (and more importantly) Heckbert's article on quantization and colormap selection in the '82 SIGGRAPH proceedings. They give specific techniques that I merely outlined with hand-waving. -- Michael Sierchio @ MCC Software Technology Program UUCP: ut-sally!im4u!milano!sierchio ARPA: sierchio@mcc.ARPA "WE REVERSE THE RIGHT TO SERVE REFUSE TO ANYONE"
falk%peregrine@Sun.COM (Ed Falk) (01/15/87)
In article <563@vu-vlsi.UUCP> williams@vu-vlsi.UUCP (Thomas Williams) writes: > >Question #2: Choosing colors > What's the best way to choose 256 24-bit colors from the possible >thousands (millions?!) which are used in an image. Supposedly a method >called 'median cut' was described in "Color image quantization for frame >buffer display", but this is an old-reference and I don't have the author's >name or publication (though it's probably Computer Graphics). Any ideas? > Every two months, regular as clockwork, someone posts this question. Check out: Paul Heckbert Color Image Qantization for Frame Buffer Display SIGGRAPH '82 proceedings, pp. 297-307 This is starting to become one of the classics, like the original Bresenham paper. -ed falk, sun microsystems terrorist, cryptography, DES, drugs, cipher, secret, decode, NSA, CIA, NRO. (The above is food for the NSA line eater.)
montnaro@sprite.UUCP (01/18/87)
In article <563@vu-vlsi.UUCP> williams@vu-vlsi.UUCP (Thomas Williams) writes: > What's the best way to choose 256 24-bit colors from the possible >thousands (millions?!) which are used in an image. Tom DeFanti (why does his name keep coming up?) presented a paper at SIGGRAPH '86 on presenting 24 bit images on 6-bit frame buffers. I don't remember his technique to describe it, but his images looked awfully nice. I believe (but don't quote me) that he compared his method with medain cut. Skip Montanaro ARPA: montanaro%desdemona.tcpip@ge-crd.arpa UUCP: seismo!rochester!steinmetz!desdemona!montanaro GE DECnet: csbvax::mrgate!montanaro@desdemona@smtp@tcpgateway
ph@pixar.UUCP (Paul Heckbert) (01/20/87)
In article <563@vu-vlsi.UUCP>, williams@vu-vlsi.UUCP (Thomas Williams) asks
how to quantize a 24-bit image down to 8 bits. And Ed Falk is right
regarding the popularity of this topic: it does come up extremely often.
I count five independent queries about it here in the past 2 years!
Skip Montanaro's statement that DeFanti's technique can present a 24-bit
image on a 6-bit frame buffer isn't quite correct. What I did in my SIGGRAPH
'82 paper was quantization for display on frame buffers with a colormap,
but DeFanti's SIGGRAPH '86 paper is about image compression.
My goal was display on a limited frame buffer, while his was compact storage
and transmission.
For each 4x4 block of pixels DeFanti transmits a bitmap (16 bits) plus two 8-bit
pixel values which index into a colormap, so that's 32 bits / 16 pixels =
2 bits per pixel, plus one colormap per picture. It takes some hardware or
software processing to convert his coded blocks into pixel values.
His technique is more akin to other compression techniques (Huffman coding,
transform coding, etc.) than it is to simple quantization.
'Til next time,
Paul Heckbert
Pixar 415-258-2303
P.O. Box 13719 UUCP: {sun,ucbvax}!pixar!ph
San Rafael, CA 94913 ARPA: ph%pixar.uucp@ucbvax.berkeley.eduthomas%spline.uucp@utah-gr.UUCP (Spencer W. Thomas) (01/21/87)
The Utah Raster Toolkit (described in a paper at the 3rd Usenix Graphics
Workshop), which will be released soon (watch this space), includes a procedure
for taking a (nominally) 24 bit image and reducing it (via a simple dithering
technique) to display in any number of available color map entries (you need
at least 8 to get full color, though). It is not as good as median cut or
similar algorithms for any specific image, but will work "well" over the entire
space of images. It is also reasonably fast (the X implementation takes about
30 secs for a 512x512 image on a 68020 and 15 secs on a Vax 785).
Please defer requests for a week or so, until we can announce release of the
whole package (it's that close).
=Spencer ({ihnp4,decvax}!utah-cs!thomas, thomas@utah-cs.ARPA)