billd@celerity.UUCP (Bill Davidson) (05/23/89)
In article <4706@uoregon.uoregon.edu> markv@tillamook.UUCP (Mark VandeWettering) writes: >This is comp.graphics. Pixels, frame buffers, point in polygon testing, >frame buffer quantization, halftoning, raytracing and radiosity are what >should be discussed here. O.K. I'm new to color quantization and I've written my first quantizer with reasonably good results and I have a few questions. I first attacked the problem a few weeks ago when someone mentioned that they wanted something to choose the best color map when converting a 24 bit image to 8 bits. It's something I'd thought about before and this set me to thinking about the problem. None of the CG books I have (Foley/Van Dam, Harrington, Newman/Sproull, Rogers, Artiwick) had anything on it. I played around with a few ideas, all of which produced exponential algorithms. I suppose I should check out image processing books more. Anybody out there have any good references? Also, I'm looking for some good references on Floyd-Steinberg dithering. A friend (Hi Jim) pointed me to Paul Heckbert's paper from SIGGRAPH '82 on the median cut algorithm. I implemented it. It has some problems though. If a color is way out away from all the other colors, it will get sucked into the other colors. This resulted in very purple sky in one of my images. I got better results when, instead of taking the centroid of the points in each box, I took the center of mass where the mass of each point was equal to it's frequency within the image. I don't have a proof but I believe that this will result in a lower quantization error over the entire image while creating larger maximum quantization errors within each box for those color farthest away. Anyway, my sky turned blue again :-). I also have an idea which I haven't had a chance to hack into my quantizer which is to use the same basic idea as median cut but instead of using the halfway point in the list associated with the box we are cutting, consider the mass of the list where the mass is defined as the number of pixels represented by all of these colors. Then we try to break it into two lists with approximately equal mass. The idea is that colors which are very common may get their own boxes and break off thus not messing up other colors. It'll take a bit more cpu but I don't think it will be prohibitive. Any authorities on this subject out there with comments? Bill Davidson ...!{ucsd,sdsu,fpssun,cogen,chip,photon}!celerity!billd
billd@celerity.UUCP (Bill Davidson) (05/23/89)
In article <310@celit.UUCP> billd@celerity (Bill Davidson) writes: >I also have an idea which I haven't had a chance to hack into my >quantizer which is to use the same basic idea as median cut but >instead of using the halfway point in the list associated with >the box we are cutting, consider the mass of the list where the >mass is defined as the number of pixels represented by all of these >colors. Then we try to break it into two lists with approximately >equal mass. The idea is that colors which are very common may get >their own boxes and break off thus not messing up other colors. >It'll take a bit more cpu but I don't think it will be prohibitive. I looked at this after I posted it and I decided it doesn't really explain what I mean. You'd never know I have a degree in math/cs. Let's try again: Assign to each color in the image a weight which is equal to it's frequency in the image. So if 432 pixels are (0,0,255), then that color would have weight of 432 and if 20 pixels in the image are (0,20,30) then that color would have weight 20. The weight of a list of colors would be the sum of weights of all the colors in the list. If we were splitting the box along the red axis, this list would be sorted by it's red values. We would run through the list adding the weights of each color to our new total as we went through it. When our new total was about half of our original total, we pick this spot to split the box. This is the essence of my change to Heckbert's algorithm which simply chose the midpoint of the list. Bill Davidson ...!{ucsd,sdsu,fpssun,cogen,chip,photon}!celerity!billd
jef@ace.ee.lbl.gov (Jef Poskanzer) (05/23/89)
First: In the referenced message, billd@celerity (Bill Davidson) wrote: }Also, I'm looking for some good references on Floyd-Steinberg dithering. "Digital Halftoning" by Ulichney. Grep through the recent comp.graphics articles for four or five more specific references. Now... }A friend (Hi Jim) pointed me to Paul Heckbert's paper from SIGGRAPH '82 }on the median cut algorithm. I implemented it. It has some problems }though. If a color is way out away from all the other colors, it will }get sucked into the other colors. This resulted in very purple sky in }one of my images. I got better results when, instead of taking the }centroid of the points in each box, I took the center of mass where the }mass of each point was equal to it's frequency within the image. }[...] }I also have an idea which I haven't had a chance to hack into my }quantizer which is to use the same basic idea as median cut but }instead of using the halfway point in the list associated with }the box we are cutting, consider the mass of the list where the }mass is defined as the number of pixels represented by all of these }colors. Then we try to break it into two lists with approximately }equal mass. Yes, while implementing median cut for my soon-to-be-released color version of PBM, I looked at just these two questions. Here are the relevant quotes from Heckbert's paper, all in the section headed "The Median Cut Algorithm": The box is "shrunk" to fit tightly around the points (colors) it encloses This indicates that "points" means colors, not pixels. Therefore: The enclosed points are sorted along the longest dimension of the box, and segregated into two halves at the median point. Approximately equal numbers of points will fall on each side of the cutting plane. this means that the median is computed by counting colors, not by counting pixels (the "mass of the list", in Bill's terminology). After K boxes are generated, the representative for each box is computed by averaging the colors contained in each. And this is pretty explicit, the color choice is done by an average in color space. Now let's look at what some of the publically-available implementations of median-cut actually do. Ed Falk's median.c: Computes the median by pixels; i.e., approx. equal numbers of pixels, not colors, fall on each side of the boundary. Assigns representatives by taking the center of the box, (minR+maxR)/2 etc. A comment mentions that he tried a "histogram-weighted center" (sounds like an average in pixel space), but didn't like the results. Michael Mauldin's fbquant.c (in FBM): Computes the median by pixels. Assigns representatives by averaging the colors. Robert Mecklenburg and John W. Peterson's mcut.c (in Utah Toolkit): Computes the median by pixels. Assigns representatives, unless I'm mis-reading the code, by averaging the colors weighted not by the number of pixels they represent but by the _square_ of the number of pixels. So, three implementations; all three use the same method of choosing the median, but not the method specified in the paper; and each of the three uses a different method of assigning a representative color, only one of which is the method specified in the paper. My own as-yet unreleased implementation (ppmquant.c) currently does the same things as Michael Mauldin's, but I really wonder if this is best. And Bill's version does the median by colors (but he's thinking of switching), and assigns representatives to boxes by averaging with pixel weights (a fourth method). Anyway, Bill, if you've actually read the paper and implemented it, then you are as much an expert as anyone else except Heckbert. And I asked him about this stuff a week ago, but he hasn't replied. --- Jef Jef Poskanzer jef@helios.ee.lbl.gov ...well!pokey "The trouble with paper designs is you don't get bloody enough." -- Butler Lampson
swilson@pprg.unm.edu (Scott Wilson [CHTM]) (05/24/89)
In article <311@celit.UUCP> billd@celerity (Bill Davidson) writes: >In article <310@celit.UUCP> billd@celerity (Bill Davidson) writes: >>I also have an idea which I haven't had a chance to hack into my >>quantizer which is to use the same basic idea as median cut but >>instead of using the halfway point in the list associated with >>the box we are cutting, consider the mass of the list where the >>mass is defined as the number of pixels represented by all of these >>colors. Then we try to break it into two lists with approximately >>equal mass. The idea is that colors which are very common may get >>their own boxes and break off thus not messing up other colors. >>It'll take a bit more cpu but I don't think it will be prohibitive. > .......etc > >We would run through the list adding the weights of each color >to our new total as we went through it. When our new total >was about half of our original total, we pick this spot to >split the box. > >Bill Davidson ...!{ucsd,sdsu,fpssun,cogen,chip,photon}!celerity!billd Here is a little modification that is similar to yours, and seems to be giving nice results for many types of images (including sunsets): 1. Choose about 50% of the desired number of colors by finding that "color box" with the largest number of occupants (actual colors), and splitting it in along its longest side. 2. Choose the remaining 50% of the desired number of colors by splitting that "color box" with the largest *diagonal* distance (i.e. 2-norm). Split along the longest side, as usual. The end result is that you preserve lots of detail in areas that have large color spans but not many pixels, but you also get smoothly varying changes in objects that have large spatial extent but not much color span (i.e. you get no "color contours"). You can play around with how many colors are assigned based on the above two metrics and get better/worse results for a particular image, but 50/50 seems to do pretty well for almost everything... Scott Wilson University of New Mexico Center for High Technology Materials Albuqerque, NM 87131 swilson@pprg.unm.edu
raveling@venera.isi.edu (Paul Raveling) (05/24/89)
In article <310@celit.UUCP> billd@celerity (Bill Davidson) writes: > >... If a color is way out away from all the other colors, it will >get sucked into the other colors. This resulted in very purple sky ... > [+ discussion of median cut alternatives] This is why the version of my tree-based quantization algorithm that a number of people have picked up recently has a weighting function. Briefly, the algorithm classifies pixels into an octree, reduces the tree until it represents the desired number of colors, and assigns final colors by reclassifying pixels in the reduced tree. The weighting is in reduction, where it uses a combination of frequency and depth in the tree to decide which nodes to eliminate. The effect is to retain breadth near in the tree at relatively shallow levels. The result is better retention of colors than with median cut -- i.e., if the original image has n colors at k-bit resolution (k=3 seems to be a meaningful resolution), and the output image has m colors at this resolution, this algorithm produce images with a higher value of m/n than median cut does. The result is substantially better images than with median cut in some cases, but using an octree produces trouble in the form of visible banding on others. The conceptually biggest problem is that it enforces a fixed cubic partitioning of RGB space, and the tree structure sometimes isolates neighboring sets of colors in branches that reduction doesn't recognize as neighbors. So, in spare time (images are no longer part of my job) I'm experimenting with variations to get around this and other problems. Recently I've tried binary trees & different ways to build somewhat octree-like non-octrees. Many of these variants perform better in different ways, but I haven't yet gotten one to perform better in ALL ways. Another technique that appears to work well is to weight selection based on pixel intensity. I found that some images, such as Lenna, were producing a large number of colors that were too dark to distinguish. Adding a crude adjustment for intensity makes it possible to maximize resolution for lighter colors, where humans perceive more detail. This is a correction that would improve perceived image quality but would produce "more quantization error" according to the usual mean squared error measure. ---------------- Paul Raveling Raveling@isi.edu
rokicki@polya.Stanford.EDU (Tomas G. Rokicki) (05/25/89)
raveling@venera.isi.edu (Paul Raveling) writes: > Another technique that appears to work well is to weight > selection based on pixel intensity. . . . Wouldn't it make sense to do color selection in the HSV cone rather than in the RGB cube, since the `distances' in HSV are more relevant to perceived differences in color? This shouldn't introduce too much additional complexity (a map-to at the start and a map-from at the end, but with some knowledge of what `points' in the cone are permissible in the middle) but should yield better results. Please, someone tell me I don't know what I'm talking about if this is the case, but RMS error only makes sense if the error terms are comparable, and this is certainly not the case in the RGB cube. -tom
billd@celerity.UUCP (Bill Davidson) (05/25/89)
In article <23862@pprg.unm.edu> swilson@pprg.unm.edu (Scott Wilson [CHTM]) writes: >Here is a little modification that is similar to yours, and seems to be >giving nice results for many types of images (including sunsets): > 1. Choose about 50% of the desired number of colors by finding that > "color box" with the largest number of occupants (actual colors), > and splitting it in along its longest side. > 2. Choose the remaining 50% of the desired number of colors by splitting > that "color box" with the largest *diagonal* distance (i.e. 2-norm). > Split along the longest side, as usual. >The end result is that you preserve lots of detail in areas that have >large color spans but not many pixels, but you also get smoothly >varying changes in objects that have large spatial extent but not much >color span (i.e. you get no "color contours"). This is an interesting idea (it took me a couple of seconds to figure out why it's so neat though :-). I forgot to mention that in my quantizer, I chose the box with the greatest number of colors and cut it along it's longest dimension for my regular median cut algorithm. This strategy was meant to cause an approximately equal number of colors in each box at the end. For my "mass" based method, I chose the box with the greatest weight which had more than one color in it (also along it's longest dimension). This strategy was meant to give each box approximately equal mass. Now I have yet another thing to try :-). --Bill Davidson (wannabegraphicsguru) Bill Davidson ...!{ucsd,sdsu,fpssun,cogen,chip,photon}!celerity!billd
bellutta@irst.UUCP (Paolo Bellutta) (05/25/89)
Two questions about color image processing:
First: What is the best way to compress 24 bit color images in 8 bit color
images but using always the same colormap? I tryed to assign 3 bits
for red and green and 2 bits for blue but the results are not very
good (the image in general has a very high contrast).
Second: I want to compute from 24 bit rgb images one image that contains
luminance information (Y = 0.299 * R + 0.587 * G + 0.114 * B) and
another image with chrominance information (C = R / (R + G)).
In parentheses I wrote what I'm using.
I found that in general the Y image has high contrast and the C
image has poor color resolution. I mean that if two sides of an object
have the same color but one is too dark, on the C image it is seen
as black.
Are there better algorithms to use?
I) I)
I a o l o I ) e l l u t t a
I.R.S.T.
loc. Pante' di Povo
38050 POVO (TN)
ITALY
vox: +39 461 810105
fax: +39 461 810851
e-mail: bellutta@irst.uucpraveling@venera.isi.edu (Paul Raveling) (05/25/89)
In article <9445@polya.Stanford.EDU> rokicki@polya.Stanford.EDU (Tomas G. Rokicki) writes: > >Wouldn't it make sense to do color selection in the HSV cone rather >than in the RGB cube, since the `distances' in HSV are more relevant >to perceived differences in color? Maybe, but it's not clear. About a year ago I tried some experiments using a different perceptual space suggested in a paper by Werner Frei, but got essentially the same end results as using RGB space. It's possible that limitations in the quantization algorithm could mask the benefits of using a different space; the best solution probably requires coordinated work to evolve both the color domain and algorithms using it. There are also some applications of quantization that would need an approach not based on human perception. I'm thinking of things such as multispectral imaging, including infrared, UV, X-ray, and magnetic resonance imaging. Some applications might call for a "linear" quantization, some might benefit by weighting for a "non-human" domain. ---------------- Paul Raveling Raveling@isi.edu
jlg@hpfcdq.HP.COM (Jeff Gerckens) (05/26/89)
Oops! Lost the text to which I am responding. Oh, well. Daryl Poe has done research into using a mean-cut rather than a median-cut algorithm with some positive results. He can be reached at poe%fokker@hplabs.hp.com. I don't think Daryl reads notes anymore, so he isn't likely to respond without direct intervention. :-) As for using the HSV color space, distances in the HSV space are not significantly more "real" than those in the RGB space. CIELUV is the reccommended space for acheiving uniformity and perceptual linearity. Color Science by Wysiecki and Stiles is a good general reference on color spaces and conversions, although not very good for quantization algorithms themselves. - Jeff Gerckens, Hewlett-Packard Graphics Technology Division (jlg%hpfcrg@hplabs.hp.com) "... Red is Grey, and Yellow White, But we decide which is right. And which is an illusion?" - Moody Blues
bdb@becker.UUCP (Bruce Becker) (05/27/89)
In article <390033@hpfcdq.HP.COM> jlg@hpfcdq.HP.COM (Jeff Gerckens) writes: | Color Science by Wysiecki and Stiles is |a good general reference on color spaces and conversions, |although not very good for quantization algorithms themselves. Does anyone have a copy of this text which I could buy? Thanks, -- __ Bruce Becker Toronto, Ont. w \cc/ Internet: bdb@becker.UUCP, bruce@gpu.utcs.utoronto.ca `/v/-e BitNet: BECKER@HUMBER.BITNET _< >_ "A virus is language from outer space" - James Brown
johnf@apollo.COM (John Francis) (05/30/89)
I have implemented Paul Heckbert's Color Quantization algorithm, but with the following modification (suggested in the original paper): Choose the box to split (and the axis along which it is to be split) such that at each step you get the largest reduction in the variance (this is equivalent to at each step choosing the split that reduces the overall root mean square error by the largest amount). I find that this gives a better result than Median Cut (the original method) or Mean Cut. I have also experimented with giving different weights to the three RGB axes. Weights of R=0.299, G=0.587, & B=0.114 produce a slightly different result in the overall appearance of the resulting picture which most of the people I have asked seem to feel is a very slight improvement. Your mileage may differ.
hutch@celerity.uucp (Jim Hutchison) (05/31/89)
In using a mean-cut or weighted-median-cut algorithm for quantizing colors,
there is another consideration to add other than just where on the line to
make the cut. There is how to make the line. Since we humans have a greater
perception of grey scale than of color shift, and a greater sensitivity to
green than red than blue. There is a certain amount of improvement which
can be gained by doing division by grey scale and weighting for grey more
strongly than color, green more strongly than red, and red more strongly
than blue. This would also probably help to maintain the contrast of the
image.
/* Jim Hutchison {dcdwest,ucbvax}!ucsd!celerity!hutch */
/* Disclaimor: I am not an official spokesman for FPS computing */jbm@eos.UUCP (Jeffrey Mulligan) (05/31/89)
From article <8490@venera.isi.edu>, by raveling@venera.isi.edu (Paul Raveling): > In article <9445@polya.Stanford.EDU> rokicki@polya.Stanford.EDU (Tomas G. Rokicki) writes: >> >>Wouldn't it make sense to do color selection in the HSV cone rather >>than in the RGB cube, since the `distances' in HSV are more relevant >>to perceived differences in color? > > Maybe, but it's not clear. [ text deleted ] > There are also some applications of quantization that would > need an approach not based on human perception. I'm thinking > of things such as multispectral imaging, including infrared, > UV, X-ray, and magnetic resonance imaging. Some applications > might call for a "linear" quantization, some might benefit > by weighting for a "non-human" domain. I'm not sure what you have in mind here. With these new imaging techniques, it would seem to me that you can divide the problem into two parts: first, what are the features that you want to detect? and second, how can you process the image to make those features most visible to a human observer while minimizing the noise or number of false targets? The first part doesn't have anything to do with vision, while the second part doesn't have anything to do with anything except vision. What is the "non-human" domain you are thinking of? There is an important point that has not been mentioned: namely that the spatial character of the acceptable quantization errors is different for luminance and chromatic errors. The visual system is blind to chromatic variations at medium to high spatial frequencies at which luminance modulations can still be clearly resolved. This is why it is generally acceptable that the chroma channels on NTSC video signals have lower bandwidths than the luminance signal. A few years ago I played around with a technique to try and exploit this. Imagine dithering an achromatic (black/white) grating. Since the R, G and B signals are the same, the dithered R, G and B images will be the same, so the quantization noise in the final composite image will be pure luminance noise with no chromatic error. Since the visual system is relatively insensitive to high frequency chromatic variation, it seemed that it would be preferable to introduce chromatic errors if it could be traded off to reduce the (more visible) luminance errors. The way I tried to do this was by using a modified error diffusion algorithm: the R, G and B images were processed in parallel; after pixel each was quantized the resulting error was partitioned into luminance and chromatic components. This error was then "diffused" with different spread functions for each of the components, with the normal weights being used for the luminance error, and larger spreads used for the two chromatic components. Before quantizing the next pixel, the error signals were converted back to R, G, and B components. This worked, but not surprisingly was slower than the already slow normal error diffusion. I never worked out a theory of the relation between the error diffusion spread function and the resulting noise spectrum, but the results were qualitatively as expected. -- Jeff Mulligan (jbm@aurora.arc.nasa.gov) NASA/Ames Research Ctr., Mail Stop 239-3, Moffet Field CA, 94035 (415) 694-6290
raveling@venera.isi.edu (Paul Raveling) (06/02/89)
In article <3800@eos.UUCP> jbm@eos.UUCP (Jeffrey Mulligan) writes: >From article <8490@venera.isi.edu>, by raveling@venera.isi.edu (Paul Raveling): > >> There are also some applications of quantization that would >> need an approach not based on human perception. I'm thinking >> of things such as multispectral imaging, including infrared, >> UV, X-ray, and magnetic resonance imaging. Some applications >> might call for a "linear" quantization, some might benefit >> by weighting for a "non-human" domain. > >I'm not sure what you have in mind here. With these new imaging >techniques, it would seem to me that you can divide the problem >into two parts: first, what are the features that you want to >detect? and second, how can you process the image to make those >features most visible to a human observer while minimizing the >noise or number of false targets? The first part doesn't have >anything to do with vision, while the second part doesn't have >anything to do with anything except vision. What is the "non-human" >domain you are thinking of? Let me illustrate with a couple hypothetical examples, rather than real ones, since I'm not directly involved with these application domains. One is medical image fusion. Take a CAT scan (X-Ray) image and a matching MRI scan image of the same cross-section of the same patient; preprocess them to match the images, then treat each image as a color component of a single fused image. I believe the X-Ray component excels at showing bone, but the MRI component is much better for resolving soft tissue. Combined, they offer the possibility of showing features not easily visible on either scan alone. Now quantize the fused image in this artificial color space. Quantization can produce various effects either deliberately or accidentally (e.g., banding) that could be desirable in this domain. For example, careful tuning could produce banding that enhances contrast for some of those fused features that are difficult to identify in the individual scans. The resulting image would be viewed in RGB space, but the colors represent a synthesized graphic domain with no relation to human perception. A second example might be to use similar fusion techniques with satellite images. For example, red might represent a radar image, green an infrared image, and blue a visual image. Instead of diagnosing diseased tissue, the goal might be something like correlating air pollution sources with environmental damage. Tuned quantization probably is useful as an additional tool for image processing, but to my knowledge noone has yet explored this possibility. ---------------- Paul Raveling Raveling@isi.edu
silva@c3.PLA.CA.US (Joe Silva) (06/09/89)
Dithering helps a lot. Check out Siggraph'82 Proceedings (Vol 16, Num 3) Page 297.