quantization (Reduction of colors of image)

Question

I am trying to quantize an image into 10 colors in C# and I have a problem in draw the quantized image, I have made the mapping table and it is correct, I have made a copy of the original image and I am changing the color of pixels based on the mapping table , I am using the below code:

bm = new Bitmap(pictureBox1.Image);
        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);
                if (histo.ContainsKey(c))
                    histo[c] = histo[c] + 1;
                else
                    histo.Add(c, 1);
            }
        var result1 = histo.OrderByDescending(a => a.Value);
                  int ind = 0;
        List<Color> mostusedcolor = new List<Color>();
        foreach (var entry in result1)
        {
            if (ind < 10)
            {
                mostusedcolor.Add(entry.Key);
                ind++;
            }
            else
                break;
        }
        Double temp_red,temp_green,temp_blue,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_red = Math.Pow((Convert.ToDouble(p.Key.R) - Convert.ToDouble(pp.R)), 2.0);
                temp_green = Math.Pow((Convert.ToDouble(p.Key.G) - Convert.ToDouble(pp.G)), 2.0);
                temp_blue = Math.Pow((Convert.ToDouble(p.Key.B) - Convert.ToDouble(pp.B)), 2.0);
                temp = Math.Sqrt((temp_red + temp_green + temp_blue));
                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);
                Boolean flag = false;
                foreach (var entry3 in mapping)
                {
                    if (c.R == entry3.Key.R && c.G == entry3.Key.G && c.B == entry3.Key.B)
                    {
                        copy.SetPixel(x, y, entry3.Value);
                        flag = true;
                    }
                    if (flag == true)
                        break;

                }
            }
pictureBox2.Image=copy;

Answer 1

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