Hi, Ken, do you know any good algorithms for losslessly converting full-colour images to palette images? I've tried looking on the Internet, and most of it seems to be about approximate palettes with things like octrees. I've taken a quick look at the source code for pngrewrite and optipng, and it just seems to be creating a list and searching through it. That would probably do OK, but do you know any more efficient ways?
Awesoken at
Re: Exact palette generation algorithms
.. pngrewrite and optipng, and it just seems to be creating a list and searching through it.
If they are both using brute force for palette generation, that is pretty sad. The good news is there exists a very simple and elegant solution: a hash table. Here's a little test program I wrote just for you:
#include <memory.h> #include <stdlib.h> #include <stdio.h> int main (void) { #define PALSIZ 256 long i, j, rgbval, pal[PALSIZ]; //standard palette table long palhashead[2048], palhashnext[PALSIZ]; //lookup tables for hash
for(i=0;i<PALSIZ;i++) pal[i] = rand(); //Fill palette with random garbage pal[17] = 0xff0000; //Except for index 17, which will be red
//Now let's see if we can find our red index (17) rgbval = 0xff0000; for(i=palhashead[(((rgbval>>22)^(rgbval>>11))-rgbval)&2047],j=0;i>=0;i=palhashnext[i],j++) if (pal[i] == rgbval) break; if (i >= 0) printf("0x%06x matches palette index %d\n",rgbval,i); else printf("0x%06x not found\n",rgbval); printf("%d hash misses\n",j); return(0); }
counting_pine at
Hey, thanks! I'll give this a good look through. Looks simple to follow though.
Awesoken said at
If they are both using brute force for palette generation, that is pretty sad.
I guess pngrewrite is, by the author's own admission, a quick and dirty utility, so he's decided to make it more simple than streamlined. Optipng doesn't look as bad. It keeps the palette sorted while it generates it, and it uses a binary search.
There doesn't seem to be much easily accessible info about the best way to do something like this, which is pretty sad in itself.
counting_pine at
I took the code you posted and had a go at writing a function that would return the palette index for a given colour, adding it to the palette if necessary/possible. It seems to work properly, given a good workout of repeated entries, full palettes and hash collisions.
j = palfind(rgbval); if(j >= 0) printf("palette index %d\n", palfind(rgbval)); else printf("no room left in palette\n"); } printf("Collisions: %d\n\n", collns);
}
counting_pine at
I found another method for generating palettes. Here's a rough example of it in action. I don't know how its performance compares to other methods, but it uses tables so it doesn't have to do any searching.
static long pal[PALSIZ]; static long tab1[65536], tab2[65536]; static long tabp[PALSIZ * PALSIZ]; static long tab1cnt, tab2cnt; static long palcnt = 0;
int palfind (long rgbval) {
long n1 = (unsigned long)rgbval & 0xffff; long n2 = ((unsigned long)rgbval >> 16) & 0xffff; long np;
if(j >= 0) printf("palette index %d\n", j); else printf("no room left in palette\n"); }
}
Awesoken at
The only thing interesting about this algorithm is that its worst case is better than a hash's worst case. The hash is simpler, faster (on average), and requires much less memory.
counting_pine at
Hi. Thanks for your response. I guess it may not be the most practical algorithm in most situations. But still, I'd say that, given the apparent lack of info on the subject, any algorithm that has any sort of advantage is worthy of a mention.