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

Introversion

To stop the flickering between frames, construct a large image that includes all the individual frames, then create a colour palette from that to use for all frames. The GIF standard allows a single global colour table and local colour tables are optional - they can be omitted. – Lully

@Lully This is a possibility. I might look into it if all else fails. This seems to be a very technical thing (encoding animated gifs efficiently) so I'm really relying on others specialized libraries at the moment and would prefer to not have to code up my own solutions. Plus the number of frames per animation could be anywhere from 2 to 100 to 1000, not sure how that would work. – Introversion

Just to let you know, your question is likely to be closed since you are asking us to find a library. However, have you looked at: web.cs.wpi.edu/~matt/courses/cs563/talks/color_quant/… – Lully

Have you tried the k-means algorithm? – Their

@FTLRalph finally finished editing mine answer ... check mine approach – Ingeingeberg

The existing answers are great with a lot insight. If someone wants a ready-made library to work with. github.com/dragon66/animated-gif-writer is one of them I made. It uses Wu's quant algorithm which is comparable to Neuro quant in quality but way faster. You can also perform dither is you want . – Stonehenge

If you want to test more with different quant algorithms, you can take a look at github.com/dragon66/icafe/blob/master/src/com/icafe4j/image/gif/… which is part of a Java image library. From there, you will be able to find at least 3 quantization algorithms along with dither. – Stonehenge

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

Ingeingeberg

How to create animated gif with this? Can you provide sources for encoding animation? – Eady

you just need to add the GIF LZW compression (after quantization). Sadly No I can not share source because GIF (especially the LZW part) encoding/decoding is still licensed and would be illegal. Instead see https://mcmap.net/q/122597/-gif-image-getting-distorted-on-interlacing and all nested sub-links you will find all the information to code this yourself (even some code to parse chunks of GIF which was hard to code). But if you want to use it legally you will need to get a license. Easier option is to use 3th party already licensed plug-in. – Ingeingeberg

Thanks for the answer, are you able to watch this question (#33942267)? I tried to implement 3rd party libraries – Eady

@AntonShkurenko Have just added default VGA color palette as global palette + dithering into mine encoder and the speed is fantastic ... preserving colors even on dynamic changing color views :) – Ingeingeberg

Can you explain more ?:) I tried web-palette, but that was awful – Eady

@AntonShkurenko you need to use dithering for fixed palette. The VGA , WEB-Palette, and others are specifically constructed for dithering techniques. Without them the image will lose colors and details. With added dithering the output is often grainy (bit noisy) but colors are correct. Dithering is just few per pixel operations (fast) and no need for slow quantization – Ingeingeberg

Thanks, I will read about this. My project was ended about two months ago, but this is still interesting. I heard about dithering, but still don't know what is it – Eady

@AntonShkurenko Take a look at the link 4 comments up. There is my simple dithering example in C++ basically you take few colors and by their mixing you obtain more colors. Adding dithering to my gif encoder was matter of adding 3 additions and 3 substractions. For example you can have 8 colors (R,G,B,C,M,Y,Black,White at full intensity) and render true color image with them without much color lose .. the output will be just a bit grainy/noisy/patterny if zoomed (The more if the used colors are too far from the source image). – Ingeingeberg

Yeah, I checked your link. I will read about this. Great thanks to you – Eady

Sorry, I couldn't resist: This is fantastic! It's the algorithm around the fragments I sketched in my mind. The only additional idea which might be worth to checked out: Dark colors appear more similar than light colors. Hence, it could be worth to do the color reduction on gamma corrected colors. – Susiesuslik

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

Tharpe

Very interesting approach +1 ... It has a significant drawback and that is if the bin contains too different colors it can result in color artifacts ... to avoid it I managed to split the palette by grouping similar colors (not based on count but on relative distance of colors inside color bin). It needs adaptive thresholding but still its slightly faster. For images ~1500 distinct colors the whole GIF (512x512x24bpp) encoding with dithering and my approach is ~240ms and with yours 220ms however your approach result is worse visually (not too bad but still quite noticeable) – Ingeingeberg

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

Plagiarism

Hm, thanks for the links, appreciate your time. I've tried Gif89Encoder before. It's issue is it stores all frames in memory before encoding (very real possibility of crashing from too much memory allocated). "Animated GIF library for Java" seems to just be "AnimatedGifEncoder" wrapped in a new repository, but I may give it a shot to see if it's different. In my experience, it's slower and produces larger files. The second link seems like a program rather than a library? – Introversion