K-Means Quantization

K-Means Quantization

Quantization is the color reduction of images from 24-bit (full color) to less colors (like 4, 16 or 256 colors). There are many quantization algorithms. One of them is K-Means quantization.

K-Means quantization is one of the non-uniform quantization techniques. In general color spectrum is divided into clusters. Numbers of clusters determine the quantization levels. In an image, for example, there are 10 clusters. 10 cluster means there will be only 10 different colors which can be represented with 4-bits (10 is between 2³ and 2⁴). During cluster construction every pixel is put in a cluster having nearest mean value. Cluster construction is done continuously until difference between a pixel and its cluster mean value is smallest comparing to others.

Sample Quantized Images

(a)

(b)

Figure 1. A BMW car, (a) original 24-bit color and (b) quantized to 25 colors (5-bit).

(a)

(b)

(c)

Figure 2. An scene, (a) original 24-bit color, (b) quantized to 10 colors (4-bit) and

(a)

(b)

(c)

Figure 3. A monkey, (a) original 24-bit color, (b) quantized to 10 colors (4-bit) and

(a)

(b)

(c)

Figure 4. A motorbike, (a) original 24-bit color, (b) quantized to 10 colors (4-bit) and

C Source Code

Below there is only K-Means quantization procedure. The complete program can be found here. Note that this procedure is little buggy. In some quantization levels it produces wrong colors far from desired values. If you want to use it please be careful.

typedef struct {
   double Mean;
   long N;
} mean_pos;

typedef struct {
   unsigned long Red_Start;
   unsigned long Red_End;
   unsigned long Green_Start;
   unsigned long Green_End;
   unsigned long Blue_Start;
   unsigned long Blue_End;
} cluster_typ;

int Choose_Cluster_Ragions(  long **RRed,
                             long **GGreen,
                             long **BBlue,
                             long width,   long height,   cluster_typ Clusters[],   short colors)
{
   unsigned long i, j, hist_R[256]={0}, hist_G[256]={0}, hist_B[256]={0}, m, n;
   unsigned long AD[256], hist_max[256], hmx, hist_min[256], hmn;
   long k, ky, ka, js, s, x;
   pix_hist Chs_Min[256], Chs_Max[256];

   for(j=0;j<height;j++)
   {
                 for(i=0;i<width;i++)
                 {
                               hist_R[RRed[i][j]]++;
                               hist_G[GGreen[i][j]]++;
                               hist_B[BBlue[i][j]]++;
                 }
   }
   ////////////////////////////////
   //  RED COLOR CLUSTER PREPARE
   // find the local max's and local min's of hist_R
   j = 0;
   if (hist_R[1] >= hist_R[0])  // increase
                 k = 1;
   else                      // decrease
                 k = -1;
   i = 0;
   while (i<255)
   {
      s = k * (hist_R[i+1] - hist_R[i]);
      while ( s >= 0  )
      {
          i++;
          s = k * (hist_R[i+1] - hist_R[i]);
      }
      AD[j] = i;
      j++;
      k = -k;
   }
   if (hist_R[1] >= hist_R[0])  // increase
   {
      ky = 0;
      ka = 1;
   }
   else                      // decrease
   {
      ky = 1;
      ka = 0;
   }
   js = j/2;
   hmx = 0;
   for(i=0;i<js;i++)
   {
       Chs_Max[hmx].Gray_Color = hist_max[hmx] = AD[2*i+ky];
       Chs_Max[hmx].Hist = hist_R[AD[2*i+ky]];
       hmx++;
   }
   hmn = 0;
   for(i=0;i<js;i++)
   {
       Chs_Min[hmn].Gray_Color = hist_min[hmn] = AD[2*i+ka];
       Chs_Min[hmn].Hist = hist_R[AD[2*i+ka]];
       hmn++;
   }
   ///////////////////////////////////////////////////
   x = hmn/colors;
   if (x == 0)
   {
       printf("ERROR in Quantization");
       exit(0);
   }
   n = 0;
   j = 0;
   for(i=0;i<hmn;i=i+x)
   {
       m = Chs_Min[i].Gray_Color;
       Clusters[j].Red_Start = n;
       Clusters[j].Red_End = m;
       n = m;
       j++;
   }
   if (j > colors)
       Clusters[colors-1].Red_End = 256;
   ///////////////////////////////////

   ///////////////////////////////////
   //  GREEN COLOR CLUSTER PREPARE
   // find the local max's and local min's of hist_G
   j = 0;
   if (hist_G[1] >= hist_G[0])  // increase
       k = 1;
   else                      // decrease
       k = -1;
   i = 0;
   while (i<255)
   {
      s = k * (hist_G[i+1] - hist_G[i]);
      while ( s >= 0  )
      {
         i++;
         s = k * (hist_G[i+1] - hist_G[i]);
      }
      AD[j] = i;
      j++;
      k = -k;
   }
   if (hist_G[1] >= hist_G[0])  // increase
   {
       ky = 0;
       ka = 1;
   }
   else                      // decrease
   {
      ky = 1;
      ka = 0;
   }
   js = j/2;
   hmx = 0;
   for(i=0;i<js;i++)
   {
      Chs_Max[hmx].Gray_Color = hist_max[hmx] = AD[2*i+ky];
      Chs_Max[hmx].Hist = hist_G[AD[2*i+ky]];
      hmx++;
   }
   hmn = 0;
   for(i=0;i<js;i++)
   {
      Chs_Min[hmn].Gray_Color = hist_min[hmn] = AD[2*i+ka];
      Chs_Min[hmn].Hist = hist_G[AD[2*i+ka]];
      hmn++;
   }
   ///////////////////////////////////////////////////
   x = hmn/colors;
   if (x == 0)
   {
      printf("ERROR in Quantization");
      exit(0);
   }
   n = 0;
   j = 0;
   for(i=0;i<hmn;i=i+x)
   {
      m = Chs_Min[i].Gray_Color;
      Clusters[j].Green_Start = n;
      Clusters[j].Green_End = m;
      n = m;
      j++;
   }
   if (j > colors)
      Clusters[colors-1].Green_End = 256;
   ////////////////////////////////

   ////////////////////////////////
   //  BLUE COLOR CLUSTER PREPARE
   // find the local max's and local min's of hist_R
   j = 0;
   if (hist_B[1] >= hist_B[0])  // increase
      k = 1;
   else                      // decrease
      k = -1;
   i = 0;
   while (i<255)
   {
      s = k * (hist_B[i+1] - hist_B[i]);
      while ( s >= 0  )
      {
         i++;
         s = k * (hist_B[i+1] - hist_B[i]);
      }
      AD[j] = i;
      j++;
      k = -k;
   }
   if (hist_B[1] >= hist_B[0])  // increase
   {
      ky = 0;
      ka = 1;
   }
   else                      // decrease
   {
      ky = 1;
      ka = 0;
   }
   js = j/2;
   hmx = 0;
   for(i=0;i<js;i++)
   {
       Chs_Max[hmx].Gray_Color = hist_max[hmx] = AD[2*i+ky];
       Chs_Max[hmx].Hist = hist_B[AD[2*i+ky]];
       hmx++;
   }
   hmn = 0;
   for(i=0;i<js;i++)
   {
      Chs_Min[hmn].Gray_Color = hist_min[hmn] = AD[2*i+ka];
      Chs_Min[hmn].Hist = hist_B[AD[2*i+ka]];
      hmn++;
   }
   ///////////////////////////////////////////////////
   x = hmn/colors;
   if (x == 0)
   {
      printf("ERROR in Quantization");
      exit(0);
   }
   n = 0;
   j = 0;
   for(i=0;i<hmn;i=i+x)
   {
      m = Chs_Min[i].Gray_Color;
      Clusters[j].Blue_Start = n;
      Clusters[j].Blue_End = m;
      n = m;
      j++;
   }
   if (j > colors)
      Clusters[colors-1].Blue_End = 256;

   return 0;
}

int K_Means_Quantize(long **RRed,
                     long **GGreen,
                     long **BBlue, double in_value, long width, long height)
{
   mean_pos Mean_R[256]={0}, Mean_G[256]={0}, Mean_B[256]={0};
   long i, j, k, pix, c_limit, y, s, **Quant;
   short colors, yer;
   double Mnear;
   cluster_typ Clusters[256];
   unsigned long BmpPix;

   colors = (short)in_value;  // colors = number of clusters.
   ////////////////////////////
   /// COLOR QUANTIZE
   Choose_Cluster_Ragions(RRed, GGreen, BBlue, width, height, Clusters, colors);

   for(i=0;i<colors;i++)
   {
      Mean_R[i].Mean = (Clusters[i].Red_End + Clusters[i].Red_Start)/2;
      Mean_R[i].N = 0;
      Mean_G[i].Mean = (Clusters[i].Green_End + Clusters[i].Green_Start)/2;
      Mean_G[i].N = 0;
      Mean_B[i].Mean = (Clusters[i].Blue_End + Clusters[i].Blue_Start)/2;
      Mean_B[i].N = 0;
   }

   for(j=0;j<height;j++)
   {
       for(i=0;i<width;i++)
       {
          ///////////////////
          // RED COLOR
          BmpPix = RRed[i][j];
          s=-1;
          k=0;
          while ( (k < colors) && (s==-1))
          {
             if ((BmpPix >= (long)Clusters[k].Red_Start) && (BmpPix < (long)Clusters[k].Red_End))
                s = k;
             k++;
          }
          if (s >= 0)
          {
             RRed[i][j] = Mean_R[s].Mean;
          }
          else
          {
              printf("Error RED in quantisation");
              exit(0);
          }
          ///////////////////
          ///////////////////
          // GREEN COLOR
          BmpPix = GGreen[i][j];
          s=-1;
          k=0;
          while ( (k < colors) && (s==-1))
          {
             if ((BmpPix >= (long)Clusters[k].Green_Start) && (BmpPix < (long)Clusters[k].Green_End))
                 s = k;
             k++;
          }
          if (s >= 0)
          {
              GGreen[i][j] = Mean_G[s].Mean;
          }
          else
          {
             printf("Error GREEN in quantisation");
             exit(0);
          }
          ///////////////////
          ///////////////////
          // BLUE COLOR
          BmpPix = BBlue[i][j];
          s=-1;
          k=0;
          while ( (k < colors) && (s==-1))
          {
             if ((BmpPix >= (long)Clusters[k].Blue_Start) && (BmpPix < (long)Clusters[k].Blue_End))
                 s = k;
             k++;
          }
          if (s >= 0)
          {
             BBlue[i][j] = Mean_B[s].Mean;
          }
          else
          {
             printf("Error BLUE in quantisation");
             exit(0);
          }
          ///////////////////
       }
   }
   return 0;
}