swilson@natasha.unm.edu (Scott R. Wilson) (05/13/91)
Archive-name: x11/image-processing/khoros/1991-05-01 Archive-directory: pprg.unm.edu:/pub/khoros/ [129.24.13.10] Original-posting-by: swilson@natasha.unm.edu (Scott R. Wilson) Original-subject: Color quantization and histograms Reposted-by: emv@msen.com (Edward Vielmetti, MSEN) This is in response to an earlier posting about the 24 to 8 bit color quantization problem - I lost the posting but remember the main points. The complaint was primarily about having to use a histogram to obtain the color information, and having to truncate the data to 5 bits/pixel/color in order to *get* the histogram. The next complaint is that the 5 bit truncation is not enough precision. Both of these are valid, especially the 5-bit one. Back in '89 I wrote a 24 to 8 routine for the KHOROS image processing package and had to address these same complaints. I got much better results, but it took some work. Here's what I did: 1. Start with Heckbert's median cut algorithm. 2. Replace the direct indexed histogram step with one that builds a hash-indexed *sparse* histogram data structure out of linked lists, etc. 3. Allow the use of variable color precision. Everything from full precision (8 bits per color band) down to 1 bit per per band is allowed, where the precision is a parameter passed to the routine. 4. Begin the "box splitting" process like Paul does, but change a few things. First, use a different metric for choosing the box to split. Volume is pretty neat, but it wipes out when you hit a distribution of colors that is coplanar and is normal to a coordinate axis - you get zero volume! I use the squared diagonal distance across the box. This improves things a great deal. Second, use two *different* splitting metrics during the quantization. My second metric was simply the population of the color box. Now what you do is perform a fraction of the box splits initially with the box diagonal metric and do the remaining ones with the population metric. What this does is try to get accurate color representations of large areas with smoothly varying hues, and then grab the ones that seem to be "most important" too. Colors that are way off by themselves in the histogram are very likely to get a color to themselves in the end, depending on the parameters and image statistics. About a 50% ratio works very well. 5. Remove the locally ordered search step - if you keep some extra information about pixel offsets you can delete this entirely! This can also let you detect Mach bands while you're creating them (have not done mucch more than a cursory investiagtion of this to far). That's it. NO DITHERING. Most of the time you don't need it. The results may have some small Mach bands but you'll have to look hard to find them. Additionally, you can change how much work you are going to do by supplying different precisions. For a quick conversion, do it with 6 bits. For a slower one that is much better, do it with 8 bits per color. The processing speed is about the same as the median cut for 6 bits of precision per color and 512x512 images. For full precision it may take 30 sec or so - sometimes longer (both timings on a DEC 3100). This technique is very sensitive to the image statistics. Images with lots of coherence (ray traced stuff) usually goes real fast. Images with many different colors (at 24 bits) scattered all over the place spatially will take longer. The biggest full precision one I have experienced was one where we wanted to quantize a raytraces 24-bit *movie* for display on an 8 bit system. We wanted all the images to have the same color map so there would be no "techno-flashing". We made one big image by putting all the frames side-by-side and ended up with something around 4500x5000 in 24 bit color. Quantized that, and extracted the frames back out with a shared color map. Works very well (took a long time though - system started paging). So in the end, you still *want* to use the histogram - just a different implementation of it. In fact, I use an extended version of the above method for quantization of images with up to 1024 bands of *floating point* data! Works nice! You can get the code for free too. The whole KHOROS package is free from the University of New Mexico. Use anonymous ftp from pprg.unm.edu. Check the FAQ posting. Note that a new release of KHOROS is rumored to be coming out in a few days, so you might want to watch for that - the BETA version is what you'll find on pprg. There's alot of really neat stuff in there. Anyway, I intend to publish this algo real soon now - got to get my defense out of the way (tomorrow AM -arrggghh)! Scott Wilson Center for High Technology Materials Department of Electrical and Computer Engineering University of New Mexico Albuquerque, NM 87131 (505)277-0780 swilson@bullwinkle.unm.edu -- comp.archives file verification pprg.unm.edu total 7 -rw-r--r-- 1 root 612 May 12 08:38 README drwxr-sr-x 2 root 512 May 11 14:18 release drwxr-sr-x 2 root 512 May 11 14:02 system drwxr-sr-x 4 root 512 May 11 11:37 bin drwxr-sr-x 2 root 512 May 11 11:26 src drwxr-sr-x 2 root 512 May 11 10:00 contrib drwxr-sr-x 2 root 512 May 11 09:33 data found khoros ok pprg.unm.edu:/pub/khoros/