Effective Gif/Image Color Quantization

fast performance when reading multiple *.gif images

you need to measure... without any sample image is hard to say and we can only guess. You need to take into account that loading/decoding JPG take time in milliseconds and encoding of GIF can be time consuming even 200 ms. Depends on kind of encoding. To speed up GIF encoding you can:

1. use single global palette + dithering

   GIF is 8 bpp and JPG is 24 bpp so your encoder needs to do the transformation. That is called color quantization and is the most expensive operation while encoding which can take even ~200 ms per frame on average PC machine in well optimized C++ code. for more info see:

   • Effective gif/image color quantization?

   To remedy this you can use single palette dedicated to dithering (like default VGA or use some WEB palette they have the same purpose) and use dithering with is much much faster. See:

   • simple and fast Dithering

   btw if you need to preserve colors take a look at this:

   • Images lose quality after saving as GIF

   So try to find out how to configure your encoder to force dithering instead of color quantization based on K-means or similar ....

2. limit encoding dictionary to less then 4096

   The encoding/decoding is based on creating dictionary and encoding need to search it more than once on per pixel basis. So lovering its size to 1024 gets significant boost to speed. Of coarse you need to access to encoding code to change this unless this can be configured somehow in it... The compression will be decreased by this however and more clear codes will be present in the stream.

3. use multi-threading

   you can fully parallelize this and encode with each core present in your system.

I strongly recommend you to measure how long it take to encode single frame of GIF. If you take advantage on both bullets #1,#2 then I estimate you can get near times around ~5 ms per frame with dithering and ~60 ms per frame with fast quantization. So with 3520 frames it would take around 17.6 or 211.2 seconds just to encode GIF so add the file memory and JPG manipulation and take into account all is heavily guessed/estimated as you did not provide sample data. And divide by number of cores if you use #3 +/- shared disc access waits.

Converting jpegs to gifs is too long

Firstly I have to thank to the @Spektre for this answer: Effective gif/image color quantization?

My colleague and I just translated it from the C++ to the Java. It shows good results in 4x less time. I'll try to improve it, but this is already much better result, than AnimatedGifEncoder.java (I used before)

Here is the code:

public static final int MAX_COLOR_COUNT = 65536;

/**
 * @param pixels rgb 888
 * @param palette int[256]
 * @return indices of colors in palette
 */
private int[][][] createPalette(int[] pixels, int[] palette) {

  final int[] histogram = new int[MAX_COLOR_COUNT]; // pixel count histogram
  final int[] indices = new int[MAX_COLOR_COUNT]; // here index is color value

  for (int i = 0; i < MAX_COLOR_COUNT; i++) {
    indices[i] = i;    
  }

  // creating histogram
  for (int color : pixels) {
    //                   0001 1111             0111 1110 0000         1111 1000 0000 0000
    color = ((color >> 3) & 0x1F) | ((color >> 5) & 0x7E0) | ((color >> 8) & 0xF800);
    if (histogram[color] < Integer.MAX_VALUE) { // picture must be really big
      histogram[color]++;
    }
  }

  // removing zeros
  int j = 0;
  for (int i = 0; i < MAX_COLOR_COUNT; i++) {
    histogram[j] = histogram[i];
    indices[j] = indices[i];
    if (histogram[j] != 0) {
      j++;
    }
  }
  final int histograms = j;

  // bubble sort
  for (int i = 1; i != 0; ) {
    i = 0;
    for (int x = 0, y = 1; y < histograms; x++, y++) {
      if (histogram[x] < histogram[y]) {
        i = histogram[x];
        histogram[x] = histogram[y];
        histogram[y] = i;
        i = indices[x];
        indices[x] = indices[y];
        indices[y] = i;
        i = 1;
      }
    }
  }

  final int[][][] colorMap = new int[32][64][32];

  int colorTableIndex = 0, x = 0;
  for (; x < histograms; x++) { // main colors
    final int color = indices[x];
    // 1f (16) = 0001 1111 (2)
    // 3f (16) = 0011 1111 (2)
    // (1111 1)(111 111)(1 1111)
    final int b = color & 0x1f;
    final int g = (color >> 5) & 0x3f;
    final int r = (color >> 11) & 0x1f;

    // skip if similar color already in palette[]
    int a = 0, i = 0;
    for (; i < colorTableIndex; i++) {
      final byte tempB = (byte) ((palette[i] >> 3) & 0x1f);
      final byte tempG = (byte) ((palette[i] >> 10) & 0x3f);
      final byte tempR = (byte) ((palette[i] >> 19) & 0x1f);

      // if difference between two colors is pretty small
      // taxicab distance
      int difference = tempB - b;
      if (difference < 0) {
        difference = -difference;
      }
      a = difference;
      difference = tempG - g;
      if (difference < 0) {
        difference = -difference;
      }
      a += difference;
      difference = tempR - r;
      if (difference < 0) {
        difference = -difference;
      }
      a += difference;
      if (a <= 2) { // smaller than 16/8
        a = 1;
        break;
      }
      a = 0;
    }

    if (a != 0) {
      colorMap[r][g][b] = i; // map to existing color
    } else {
      colorMap[r][g][b] = colorTableIndex; // map to new index

      // 1111 1000 1111 1100 1111 1000
      palette[colorTableIndex] = b << 3 | (g << 10) | (r << 19); // fill this index with new color
      colorTableIndex++;
      if (colorTableIndex >= 256/*palette.length*/) {
        x++;
        break;
      }
    }
  }   // colorTableIndex = new color table size

  for (; x < histograms; x++) { // minor colors

    final int color = indices[x];

    final int b = color & 0x1f;
    final int g = (color >> 5) & 0x3f;
    final int r = (color >> 11) & 0x1f;

    // find closest color
    int minDistance = -1;
    int colorIndex = 0;
    for (int a, i = 0; i < colorTableIndex; i++) {
      final byte tempB = (byte) ((palette[i] >> 3) & 0x1f);
      final byte tempG = (byte) ((palette[i] >> 10) & 0x3f);
      final byte tempR = (byte) ((palette[i] >> 19) & 0x1f);

      int difference = tempB - b;
      if (difference < 0) {
        difference = -difference;
      }
      a = difference;
      difference = tempG - g;
      if (difference < 0) {
        difference = -difference;
      }
      a += difference;
      difference = tempR - r;
      if (difference < 0) {
        difference = -difference;
      }
      a += difference;
      if ((minDistance < 0) || (minDistance > a)) {
        minDistance = a;
        colorIndex = i;
      }
    }
    colorMap[r][g][b] = colorIndex;
  }

  return colorMap;
}

private byte[] map(int[] pixels, int[][][] colorMap) {
  final int pixelsLength = pixels.length;

  final byte[] mapped = new byte[pixelsLength];
  for (int i = 0; i < pixelsLength; i++) {
    final int color =
        ((pixels[i] >> 3) & 0x1F) | ((pixels[i] >> 5) & 0x7E0) | ((pixels[i] >> 8) & 0xF800);

    final int b = color & 0x1f;
    final int g = (color >> 5) & 0x3f;
    final int r = (color >> 11) & 0x1f;

    mapped[i] = (byte) colorMap[r][g][b];
  }
  return mapped;
}

quantization (Reduction of colors of image)

Your code has two problems:

• it is terribly slow
• the quantization is not what I would expect.

Here is an original image, the result of your code and what Photoshop does when asked to reduce to 10 colors:

• Speeding up the code can be done in two steps:

  • Get rid of the most obnoxious time wasters
  • Turn the GetPixel and the SetPixel loops into Lockbits loops.

Here is a solution for step one, that speeds up the code by at least 100x:

Bitmap bm = (Bitmap)Bitmap.FromFile("d:\\ImgA_VGA.png");
pictureBox1.Image = bm;

Dictionary<Color, int> histo = new Dictionary<Color, int>();
for (int x = 0; x < bm.Size.Width; x++)
    for (int y = 0; y < bm.Size.Height; y++)
    {
        Color c = bm.GetPixel(x, y);   // **1**
        if (histo.ContainsKey(c))  histo[c] = histo[c] + 1;
        else histo.Add(c, 1);
    }
var result1 = histo.OrderByDescending(a => a.Value);
int number = 10;
var mostusedcolor = result1.Select(x => x.Key).Take(number).ToList();

Double temp;
Dictionary<Color, Double> dist = new Dictionary<Color, double>();
Dictionary<Color, Color> mapping = new Dictionary<Color, Color>();
foreach (var p in result1)
{
    dist.Clear();
    foreach (Color pp in mostusedcolor)
    {
        temp = Math.Abs(p.Key.R - pp.R) + 
               Math.Abs(p.Key.R - pp.R) + 
               Math.Abs(p.Key.R - pp.R);
        dist.Add(pp, temp);
    }
    var min = dist.OrderBy(k => k.Value).FirstOrDefault();
    mapping.Add(p.Key, min.Key);
}
Bitmap copy = new Bitmap(bm);

for (int x = 0; x < copy.Size.Width; x++)
    for (int y = 0; y < copy.Size.Height; y++)
    {
        Color c = copy.GetPixel(x, y);   // **2**
        copy.SetPixel(x, y, mapping[c]);
    }
pictureBox2.Image = copy;

Note that there is no need to calculate the distances with the full force of Pythagoras if all we want is to order the colors. The Manhattan distance will do just fine.

Also note that we already have the lookup dictionary mapping, which contains every color in the image as its key, so we can access the values directly. (This was by far the worst waste of time..)

The test image is processed in ~1s, so I don't even go for the LockBits modifications..

• But correcting the quantization is not so simple, I'm afraid and imo goes beyond the scope of a good SO question.

  • But let's look at what goes wrong: Looking at the result we can see it pretty much at the first glance: There is a lot of sky and all those many many blues pixels have more than 10 hues and so all colors on your top-10 list are blue.

  • So there are no other hues left for the whole image!

  • To work around that you best study the common quantization algorithms..

One simplistic approach at repairing the code would be to discard/map together all colors from the most-used-list that are too close to any one of those you already have. But finding the best minimum distance would require soma data analysis..

Update Another very simple way to improve on the code is to mask the real colors by a few of its lower bits to map similar colors together. Picking only 10 colors will still be too few, but the improvement is quite visible, even for this test image:

Color cutOff(Color c, byte mask)
{  return Color.FromArgb(255, c.R & mask, c.G & mask, c.B & mask );   }

Insert this here (1) :

byte mask = (byte)255 << 5 & 0xff;  // values of 3-5 worked best
Color c = cutOff(bm.GetPixel(x, y), mask);

and here (2) :

Color c = cutOff(copy.GetPixel(x, y), mask);

And we get:

Still all yellow, orange or brown hues are missing, but a nice improvement with only one extra line..

---

Related Topics