 |
Author |
Topic: how to extract palette from image? (Read 1556 times) |
|
lunetta
 
 
|
how to extract palette from image?
« on: Apr 23rd, 2004, 7:49am » |
|
Hello beloved Processers
I'm a guy with a giant gap between real world problems and algorithms/data structures.
My real world problem is: how to extract from 1 to 8 colors from an image, in a way just like photoshop save for web / gif / 8 color palette perceptual does?
I need something fast, to grab webcam video frames and extract their colors... building a color histogram from 16.7 million colors seems not to be the best idea...
anyone with ideas on what should I read, from where should I begin.... any help is great!!
Real thanks from "The gap guy"
|
|
|
|
|
lunetta
|
Re: how to extract palette from image?
« Reply #2 on: Apr 23rd, 2004, 5:13pm » |
|
Mario, Mario... always stealing my ideas... and stealing even before I have them!!! : )
Just kidding, thanks for your help, that's exactly what I needed and I didn't know where to begin... saved me again! By the way, you applet works great...
thanks!
|
|
|
|
|
Quasimondo
|
Re: how to extract palette from image?
« Reply #3 on: Apr 23rd, 2004, 8:07pm » |
|
 - well, I can already sense your next idea coming ... and it's ... red ... no ... green? nah ... it's ... gone, damn!
|
Mario Klingemann | Quasimondo | Incubator | côdeazur
|
|
|
narain
|
Re: how to extract palette from image?
« Reply #4 on: Apr 24th, 2004, 6:30am » |
|
Quasimondo, the output of the NeuQuant algorithm doesn't look quite right to me.
With about six to twelve colours, I'd expect the girl's dress to be red, the sky blue, and the grass green.
Instead everything becomes different shades of sepia.
I have a feeling colour quantization is a data clustering problem: classify all the colours in the image into, say, 256 clusters, and then pick one colour from each class. Maybe K-means clustring will work.
|
| « Last Edit: Apr 24th, 2004, 6:30am by narain » |
|
|
|
|
Quasimondo
|
Re: how to extract palette from image?
« Reply #5 on: Apr 24th, 2004, 3:00pm » |
|
Anthony Dekker mentions it on his page, that the method doesn't work for lesse than 64 colors, but somehow I didn't notice, that the outcome was not correct. But you are right, this can be improved.
|
Mario Klingemann | Quasimondo | Incubator | côdeazur
|
|
|
narain
|
Re: how to extract palette from image?
« Reply #6 on: May 1st, 2004, 3:34pm » |
|
Okay, I just managed to implement a K-Means algorithm for color quantization.
And boy, is it slow!  Well, the performance is proportional to the number of colours to be extracted, at least in my extremely naive implementation. (That's because in every iteration, I'm doing a comparison of every pixel in the image with every color in the palette!) For upto 16 colours it's almost acceptable (half a second or so), but beyond that it takes a horrendous amount of time. I know there are better ways to do this, and I'm going to use them as soon as I can figure them out.
Anyway, the results it gives are similar to NeuQuant for 4 colors or fewer, but it begins to catch the red of the dress and the meat after 6 colors or so. Considering NeuQuant's neural network tries to make a connected chain of colours, I figure that's why it has trouble handling very different colours like green and red without intermediates in the same palette.
Besides, I think another reason why we get different shades of sepia instead of different colours is because the RGB color space in which the algorithm currently works doesn't really give much importance to differences in hue. The human eye on the other hand is very sensitive to hue, because while brightness may vary drastically on a single object, the hue will typically be the same everywhere. So you'd prefer to merge two colours with same hue and different brightness over merging colours with similar brightness and different hue.
I tried weighting my K-Means sketch to do that, and it did improve the results a lot! I'll post code here once I get it working faster.
|
| « Last Edit: May 1st, 2004, 3:36pm by narain » |
|
|
|
|
Quasimondo
|
Re: how to extract palette from image?
« Reply #7 on: May 1st, 2004, 3:57pm » |
|
I wonder what happens, if I replace RGB by HSB and leave the rest of the code as it is...
And I'm looking forward to see your solution.
|
Mario Klingemann | Quasimondo | Incubator | côdeazur
|
|
|
narain
|
Re: how to extract palette from image?
« Reply #8 on: May 2nd, 2004, 7:38am » |
|
You can't directly replace RGB by HSB (or HSV or HSL or whatever other names people call it) because of two issues:
1. Hue values "wrap around" at 360'. (Unlike in Processing, hues are usually given in degrees: think of the colour wheel.) Red has hue 0', and going clockwise a little, orange's hue is 30'. But going anticlokwise, hot pink ( = red + magenta) has hue 330' (because -30' becomes 360' - 30'). So if you just go by HSB coordinates, you'd think red and pink are far apart.
2. When saturation is very low, differences in hue don't have much effect. Hue values may differ by a lot, but the colors will not differ much. But the program will think they do.
So I'm not using HSB at all. Instead, I'm just modifying my definition of the "distance" or difference between colors.
I first compute the luminance of the colors (apparently the human eye perceives the brightness of a color as lum = 0.3*red + 0.6*green + 0.1*blue, so that's what I use). Then I extract the color components, which are red-lum, green-lum and blue-lum.
Now instead of the standard "sum of differences in red, green and blue components", I define distance as "l*(difference in luminances) + k*(sum of differences in colour components)". l and k are the weights for luminance and color. I used l = 1 and k = 2, and it seems good.
I don't know if you can directly change the distance measure in NeuQuant, but you could get the same effect by first converting each color (which is conceptually an array of three elements) to an array of four elements: l times the luminance and k times each of the color components. Then run NeuQuant, and convert the results back to RGB. Of course, you'd have to modify NeuQuant to work in four dimensions rather than three. Shouldn't be hard.
I don't think I'll be able to show you my sketch anytime soon, since my college exams are beginning tomorrow. Plus I've done some testing and found that it isn't just my implementation's fault, K-Means itself takes way too many iterations to converge on large palettes. I don't know if making it run at an acceptable speed is even possible at all.
|
|
|
|
|
narain
|
Re: how to extract palette from image?
« Reply #9 on: May 2nd, 2004, 11:04am » |
|
I have a tendency to write excessively long posts.
Anyhow, I just thought I ought to mention that all I said about color distance effecively boils down to increasing the saturation of the colors before comparing them. That's pretty much it, except for keeping values as ints to avoid clipping at 0 and 255.
Oh, and it's also my first approximation to the CIE Lab color model (as seen in Photoshop).
|
|
|
|
|
lunetta
|
Re: how to extract palette from image?
« Reply #10 on: May 4th, 2004, 4:59am » |
|
Hi
By the way, I need an advice:
what would be the fastest quantization algorithm to reduce the color space from RGB to 4 colors? The quality doesn't matter too much, I'm just using the colors and not the image... I keep on finding hundreds of differents algorithms but I don't have a clue on the fastest+easy to implement solution...
Thanks again!
|
|
|
|
|
narain
|
Re: how to extract palette from image?
« Reply #11 on: May 4th, 2004, 5:56am » |
|
Oo, just four colours. K-Means works reasonably fast for four colours, and will definitely give you better results than the traditional methods like uniform, median cut, octree, etc. NeuQuant also fails on tiny palettes, so K-Means is a good option. Okay, scratch that. K-Means is very slow on big images.
For more than about a dozen colours, though also, K-Means is horribly slow. That's why it's never mentioned as a colour quantization method. Bigger palettes will improve the results' quality of almost any other quantization method though, so you have more choice here. Still, apparently NeuQuant's the best, and Quasimondo's already coded it up for you. Use the Source, Luke!
There's also this paper I found that promises the best of both K-Means and NeuQuant, but it doesn't give any exact implementation details.
I suggest you start with the simplest method that works, and see if it's good enough. If not, try the next more complex one, and so on. Assuming you have that much time on your hands
|
| « Last Edit: May 4th, 2004, 7:05am by narain » |
|
|
|
|
|
