Quantization

Basic Concepts

• Quantization Cell
• Quantization Error

  (perceptual metric)

• Types
  • Uniform
  • Adaptive

Uniform Quantization

Strategy

• Assume Colors are Uniformly Distributed
• Decompose Color Space using Uniform Subdivision

Adaptive Quantization

Main Operations

• Compute Image Statistics
• Generate the Quantization Function
• Quantize the Image

Populosity Algorithm

• Select the k most frequent colors

Populosity Algorithm

Main Algorithm

Image *img_quant_popul(Image *i, int n, int nb)
{
  int u, v, k, *hist = NEWTARRAY(HIST_SIZE(nb), int);
  Image *q = img_init(IMG_MAPPCOL, i->w, i->h);

  img_histogram(i, hist, nb);
  cmap_select(n, hist, nb, img_cmap(q));

  for (k = 0; k < HIST_SIZE(nb); k++)
    hist[k] = cm_closest(img_cmap(q), index_to_rgb(k, nb, nb, nb));

  for (v = 0; v < i->h; v++) {
    for (u = 0 ; u < i->w; u++) {
      k = hist[rgb_to_index(img_getc(i, u, v), nb, nb, nb)];
      img_puti(q, u, v, k);
    }
  }
  efree(hist);
  return q;
}

Computing the Histogram

#define HIST_SIZE(n) (int)(pow(2.0, 3.0*(n)))

void img_histogram(Image *i, int *hist, int nb)
{
  int u, v, k, b, hsize = HIST_SIZE(nb);

  for (k = 0; k < hsize; k++)
    hist[k] = 0;
  for (v = 0; v < i->h; v++) {
    for (u = 0 ; u < i->w; u++) {
      Color c = img_getc(i,u,v);
      hist[rgb_to_index(c, nb, nb, nb)] += 1;
    }
  }
}

Selecting the Best n Colors

static void cmap_select(int n, int *hist, int nb, CMap *s)
{
  Color c;
  int k, l, cmax, imax, hsize = HIST_SIZE(nb);
  
  for (k = 0; k < n; k++) {
    cmax = -1;
    for (l = 0; l < hsize; l++) {
      if (hist[l] > cmax) {
        cmax = hist[l];
        imax = l;
      }
    }
    c = index_to_rgb(imax, nb, nb, nb);
    s->r[k] = RED(c);
    s->g[k] = GRN(c);
    s->b[k] = BLU(c);
    hist[imax] = -hist[imax];
  }
  for (k = n; k < 256; k++) {
    s->r[k] = s->g[k] = s->b[k] = 0;
  }
}