Effective gif/image color quantization?

Question

So I'm trying to encode some animated gif files in my Java application. I've been using some classes/algorithms found online, but none seem to be working well enough.

Right now I'm using this quantize class to reduce the colors of an image down to 256: http://www.java2s.com/Code/Java/2D-Graphics-GUI/Anefficientcolorquantizationalgorithm.htm

The problem is, it doesn't seem to be very "smart."

If I pass in an image with more than 256 colors, it does reduce the color number, but not very well. (Reds turn blue, etc - very obvious errors like this).

Are there any other algorithms/libraries for color quantization in Java that you can recommend?

---

Note: I'm aware of Neuquant, used in this algorithm: http://www.java2s.com/Code/Java/2D-Graphics-GUI/AnimatedGifEncoder.htm

It is very slow and produces "eh" results (colors flickering between frames).

Answer 1

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):

Answer 2

Here... I wrote this and it works a little faster than Octree and seems to yield better results on most images (and was a hell of a lot easier to code lol). It basically works like an Octree but in the opposite... it creates an initial list of colors and then splits the list with the highest number of unique colors by ordered bits (with a subsequently lowering bit #) as needed until it has as many lists as desired colors. Then it returns an array containing the average color from each list...

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;


namespace SeelWorks.Libraries.Imaging.Quantization {

    public static class BitSplitQuantizer {

        public static Color[] CreatePalette(IEnumerable<Color> sourceColors, int maxColors = 256) {
            var collections = new List<Collection>();
            collections.Add(new Collection());
            foreach(var _ in sourceColors) collections[0].Add(_);
            var offset = 1;
            while(collections.Count < maxColors) {
                if(offset > collections.Count) {
                    break;
                } else {
                    collections = collections.OrderBy(_ => _.Colors.Count).ToList();
                    var split = collections[collections.Count - offset].Split();
                    if((split.Count == 1) || ((collections.Count + split.Count - 1) > maxColors)) {
                        offset++;
                    } else {
                        offset = 1;
                        collections.RemoveAt(collections.Count - 1);
                        collections.AddRange(split);
                    }
                }
            }
            return collections.Select(_ => _.GetAverageColor()).ToArray();
        }


        private class Collection {
            public Dictionary<Color, int> Colors = new Dictionary<Color, int>();
            public int Level = -1;

            public void Add(Color color) {
                if(!Colors.ContainsKey(color)) Colors.Add(color, 0);
                Colors[color]++;
            }

            public List<Collection> Split() {
                var colors = Colors.OrderBy(_ => _.Value).Select(_ => _.Key).ToList();
                var level = (7 - Level - 1);
                var indexes = new int[8] { -1, -1, -1, -1, -1, -1, -1, -1 };
                var ret = new List<Collection>();
                foreach(var _ in colors) {
                    var index_ = ((((_.R >> level) & 1) << 2) | (((_.G >> level) & 1) << 1) | ((_.B >> level) & 1));
                    if(indexes[index_] == -1) {
                        ret.Add(new Collection());
                        indexes[index_] = (ret.Count - 1);
                        ret[ret.Count - 1].Level = (Level + 1);
                    }
                    ret[indexes[index_]].Colors[_] = Colors[_];
                }
                return ret;
            }

            public Color GetAverageColor() {
                var r = 0.0;
                var g = 0.0;
                var b = 0.0;
                var t = 0.0;
                foreach(var _ in Colors) {
                    r += (_.Key.R * _.Value);
                    g += (_.Key.G * _.Value);
                    b += (_.Key.B * _.Value);
                    t += _.Value;
                }
                return Color.FromArgb((int)Math.Round(r / t), (int)Math.Round(g / t), (int)Math.Round(b / t));
            }
        }

    }

}

Original Image:

Octree Quantized (0.145s):

BitSplit Quantized (0.100s):

Original Image:

Octree Quantized (0.233s):

BitSplit Quantized (0.213s):

Answer 3

you could use Gif89Encoder

This Java class library for encoding GIFs it covers more of the extended GIF89a feature set, including animation and embedded textual comments, than any other free Java GIF encoder.

or http://imagej.nih.gov/ij/

or Animated GIF library for Java

I have used Animated GIF library for Java with good results