Effective color quantization of gif / image?

Question

So, I am trying to encode some animated gif files in my Java application. I use some classes / algorithms found on the Internet, but none of them work well enough.

I now use this quantization class to reduce the color of the image to 256: http://www.java2s.com/Code/Java/2D-Graphics-GUI/Anefficientcolorquantizationalgorithm.htm

The problem is that she doesn't seem very smart.

If I transmit an image with more than 256 colors, it reduces the number of colors, but not very well. (Red blue, etc. are very obvious errors like this).

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

---

Note: I know 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 flicker between frames).

Answer 1

you can use google for other algorithms like mid slice, population, k-tool, etc.

I needed this too, but I was also pleased to look fast (I needed this to capture real-time video), so I managed to do something like this:

• convert to 15 bit rgb

  If you already have RGB, you can skip this step, but use shift / and to match the 5-bit channels. You can also use a 5: 6: 5 pattern

• execute a histogram

  15-bit rgb results in 32768 entries, so create 2 arrays

  • his[32768] - number of pixels (histogram)
  • idx[32768] - index = color value

  When counting colors, make sure the counters do not overflow when using low bit counts or high resolutions

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

  also count nonzero entries in his[] and call it hists

• (index) sort hist[],idx[] , so hist[] sorted in descending order;

• create an N-color palette

  Take the color idx[i] ( i={ 0,1,2,3,...,hists-1 } ) and see if your palette has the same color. if you ignore this color (set it as the closest one found), otherwise add it to the palette. if you reach a stop of N colors

• create color matching

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

• repainting image

This is the source of C ++:

 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 the following:

 // 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 

• pyx[],bmp contains the original 32-bit image
• pyx1[],bmp1 is a temporary 8-bit image for encoding

So repainting 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 are some sample output:

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

At the top is a color palette (the original image contains a palette from the middle image)

here is a real color photo:

and reduced to 256 colors:

This took ~ 185 ms to encode in GIF (including color reduction). I am very pleased with the result, but as you can see, the images do not match. Green grass clusters differ slightly after re-color (less area / intensity?)

[Note]

The code is not yet optimized, so there should be a way to make it faster. You can increase the encoding speed:

• reduction of the maximum word size for encoding
• using an index table for a dictionary or three structures to speed up the search
• can change the sorting of the histogram bubbles to speed up the sorting of algo (but this part of the code is far from critical)
• you can use one palette to encode the sequence (if the scene does not change too much)
• If you want even more speed, then create a static palette and use smoothing, and all this

Here's an example of an RT video recording (the source was 50 frames per second, so I reduce the resolution to match the speed):

Answer 2

you can use Gif89Encoder

In this Java class library for GIF encoding, it covers more of the advanced set of GIF89a functions, including animations and inline text comments, than any other free Java GIF encoder.

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

or Animated GIF Library for Java

I used the Animated GIF Library for Java with good results

Answer 3

Here ... I wrote this and it works a little faster than Octree, and seems to give better results on most images (and it was much easier to code LOL). It basically works like Octree, but vice versa ... it creates an initial list of colors, and then splits the list with the highest number of unique colors according to the ordered bits (followed by decreasing bit #) as needed, until there are as many lists as desired flowers. 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):