Generating an optimal palette from 24Bit

[Alhexx]

So, here's my new hardcore-problem:
I need to write a proggy that generates an 8-Bit Paletted Image from a 24Bit RGB Image.

Until now I used to scan the whole RGB Pixel Buffer and generare a Color List. Then I sorted the colors by the number they were used in the image.
However, this brings certain problems:
1. It takes a LOT of time of generate the Color List. (e.g. in a 600x400 Image there are 240.000 possible colors)
2. It takes even more time to sort the Color List via BubbleSort...
3. Let's say you've got an image of a sky with a rainbow on it. The sky will take 75% of the picture and only 25% are used by the rainbow. So it is clear that the palette generate will generate a palette with 240 blue colors (for the sky) and about 16 for the rainbow itself...

So this is no solution. I read something about a method called "Quantization" and I already downloaded a (scientific) document about it, however, I don't really understand it...

So is there anyone in here who knows how this algorithm works?
(If not,  I will have to ask my maths teacher on monday...)

Thanx

 - Alhexx

 - edit -
Oh, and things like dithering are not important: I have already included some dithering algorithms like Floyd-Steinberg and so on ... I just need to calculate an optimal palette...

[mirex]

I dont know about any good method, but there should be lots of them already on the net. try htpp://www.codeproject.com or some other source code web pages.

You can also create universal palette, something like

Code: [Select]

i=0
for r=0 to 6
 for g=0 to 6
  for b=0 to 6
   palette[ i++ ] = ( r*50, g*50, b*50 );
that should take 216 palette enteries, and then you assign pixels to most similar color from palette. But you will loose a lot of quality on that one.

And when i use graphic programs i get best results with method 'Optimized octree', maybe you should look for that one.

[Alhexx]

Okay, I found something about that octree algorithm, and yeah, it gives very good results!

 - Alhexx

 - edit -
BTW: A new command-line tool is going to be released soon...