Effective gif/image color quantization?

you can google for another algorithms like median cut,population,k-means,etc..

I recently needed this too but had to be nice looking and fast also (I need this for real time video capture) so I managed to do something like this:

1. convert to 15-bit rgb

   if you already have RGB you can skip this step but apply shift/and to match 5-bit per channel. You can use also 5:6:5 scheme

2. do a histogram

   15-bit rgb lead to 32768 entries so create 2 arrays

   • his[32768] is the pixel count (histogram)
   • idx[32768] is index = color value

   While counting colors ensure that counters do not overflow if using low bit count or high resolutions

3. reorder arrays so zeros in his[] are at the end of array

   also count the non zero entries in his[] and call it hists

4. (index) sort hist[],idx[] so hist[] is ordered descending;

5. create the N-color palette

   Take color idx[i] (i={ 0,1,2,3,...,hists-1 }) and look if in your palette is no similar color. if is ignore this color (set it as the most close one found) otherwise add it to palette. if you reach the N colors stop

6. create color mapping

   So take each color and find the most close color in palette (this can be partially done in step 5) I call this table recolor[32][32][32]

7. recolor image

This is C++ source:

BYTE db,*p;
AnsiString code;
int e,b,bits,adr;
int x0,x1,y0,y1,x,y,c;
DWORD ix,cc,cm,i0,i,mask;
union { DWORD dd; BYTE db[4]; } c0,c1;


    DWORD r,g,b; int a,aa,hists;
    DWORD his[32768];
    DWORD idx[32768];
    // 15bit histogram
    for (x=0;x<32768;x++) { his[x]=0; idx[x]=x; }
    for (y=0;y<ys;y++)
     for (x=0;x<xs;x++)
        {
        cc=pyx[y][x];
        cc=((cc>>3)&0x1F)|((cc>>6)&0x3E0)|((cc>>9)&0x7C00);
        if (his[cc]<0xFFFFFFFF) his[cc]++;
        }
    // remove zeroes
     for (x=0,y=0;y<32768;y++)
        {
        his[x]=his[y];
        idx[x]=idx[y];
        if (his[x]) x++;
        } hists=x;
    // sort by hist
    for (i=1;i;)
     for (i=0,x=0,y=1;y<hists;x++,y++)
      if (his[x]<his[y])
        {
        i=his[x]; his[x]=his[y]; his[y]=i;
        i=idx[x]; idx[x]=idx[y]; idx[y]=i; i=1;
        }
    // set lcolor color palete
    for (i0=0,x=0;x<hists;x++) // main colors
        {
        cc=idx[x];
        b= cc     &31;
        g=(cc>> 5)&31;
        r=(cc>>10)&31;
        c0.db[0]=b;
        c0.db[1]=g;
        c0.db[2]=r;
        c0.dd=(c0.dd<<3)&0x00F8F8F8;
        // skip if similar color already in lcolor[]
        for (a=0,i=0;i<i0;i++)
            {
            c1.dd=lcolor[i];
            aa=int(BYTE(c1.db[0]))-int(BYTE(c0.db[0])); if (aa<=0) aa=-aa; a =aa;
            aa=int(BYTE(c1.db[1]))-int(BYTE(c0.db[1])); if (aa<=0) aa=-aa; a+=aa;
            aa=int(BYTE(c1.db[2]))-int(BYTE(c0.db[2])); if (aa<=0) aa=-aa; a+=aa;
            if (a<=16) { a=1; break; } a=0; // *** treshold ***
            }
        if (a) recolor[r][g][b]=i;
        else{
            recolor[r][g][b]=i0;
            lcolor[i0]=c0.dd; i0++;
            if (i0>=DWORD(lcolors)) { x++; break; }
            }
        }   // i0 = new color table size
    for (;x<hists;x++)  // minor colors
        {
        cc=idx[x];
        b= cc     &31;
        g=(cc>> 5)&31;
        r=(cc>>10)&31;
        c0.db[0]=b;
        c0.db[1]=g;
        c0.db[2]=r;
        c0.dd=(c0.dd<<3)&0x00F8F8F8;
        // find closest color
        int dc=-1; DWORD ii=0;
        for (a=0,i=0;i<i0;i++)
            {
            c1.dd=lcolor[i];
            aa=int(BYTE(c1.db[0]))-int(BYTE(c0.db[0])); if (aa<=0) aa=-aa; a =aa;
            aa=int(BYTE(c1.db[1]))-int(BYTE(c0.db[1])); if (aa<=0) aa=-aa; a+=aa;
            aa=int(BYTE(c1.db[2]))-int(BYTE(c0.db[2])); if (aa<=0) aa=-aa; a+=aa;
            if ((dc<0)||(dc>a)) { dc=a; ii=i; }
            }
        recolor[r][g][b]=ii;
        }

And the owner image class contains this:

// image data
Graphics::TBitmap *bmp,*bmp0,*bmp1; // actual and restore to 32bit frames,and 8bit input conversion frame
int xs,ys;                      // resolution
int *py;                        // interlace table
DWORD **pyx,**pyx0;             // ScanLine[] of bmp,bmp0
BYTE  **pyx1;

// colors (colors are computed from color_bits)
DWORD gcolor[256];              //hdr
DWORD lcolor[256];              //img
BYTE  recolor[32][32][32];      //encode reduce color table
int scolors,scolor_bits;        //hdr screen color depth
int gcolors,gcolor_bits;        //hdr global pallete
int lcolors,lcolor_bits;        //img/hdr local palette

• the pyx[],bmp contains the source 32bit image
• the pyx1[],bmp1 is temp 8bit image for encoding

This is how the recolor is done:

    // recolor to lcolors
    for (y=0;y<ys;y++)
     for (x=0;x<xs;x++)
        {
        int r,g,b;
        c0.dd=(pyx[y][x]>>3)&0x001F1F1F;
        b=c0.db[0];
        g=c0.db[1];
        r=c0.db[2];
        i=recolor[r][g][b];
//      pyx [y][x]=lcolor[i];   // 32 bit output (visual)
        pyx1[y][x]=i;           // 8  bit output (encoding)
        }

Here some examples of output:

this is comparison between VCL/GDI color reduction, my approach and original image)

In the upper part is the color palette draw (the original image contains palette from middle image)

here true color photo:

and reduced to 256 colors:

This took ~185ms to encode into GIF (color reduction included). I am very pleased with the result but as you can see the images are not the same. The green grass clusters are bit different after recolor (less area/intensity ?)

[Notes]

Code is not yet optimized so it should be a way to make it more fast. You can boost speed of encoding by:

1. lowering the max encoding dictionary size
2. using index table for dictionary or three structure to speed up the searching
3. can change the histogram bubble sort to faster sorting algo (but that part of code is far from critical)
4. to encode sequence you can use single palette (if scene is not too much color changing)
5. If you want even more speed then create static palette and use dithering instead all of this

Here an example of RT captured video (source was 50fps so i reduce the resolution to match speed):