Color quantization

Color quantization is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

full color

Example: Gimp 16 color

Color quantization is the process of reducing number of colors used in an image while trying to maintain the visual appearance of the original image. In general, it is a form of cluster analysis, if each RGB color value is considered as a coordinate triple in the 3D colorspace. There are some well know algorithms [[1]], each with its own advantages and drawbacks.

Task: Take an RGB color image and reduce its colors to some smaller number (< 256). For this task, use the frog as input and reduce colors to 16, and output the resulting colors. The chosen colors should be adaptive to the input image, meaning you should not use a fixed palette such as Web colors or Windows system palette. Dithering is not required.

Note: the funny color bar on top of the frog image is intentional.

C

C output

Using an octree to store colors. Here are only the relevant parts. For full C code see Color_quantization/C. It's different from the standard octree method in that:

1. Each node can both be leaf node and have child nodes;
2. Leaf nodes are not folded until all pixels are in. This removes the possibility of early pixels completely bias the tree. And child nodes are reduced one at a time instead of typical all or nothing approach.
3. Node folding priorities are tracked by a binary heap instead of typical linked list.

The output image is better at preserving textures of the original than Gimp, though it obviously depends on the input image. This particular frog image has the color bar added at the top specifically to throw off some early truncation algorithms, which Gimp is suseptible to. <lang c>typedef struct oct_node_t oct_node_t, *oct_node; struct oct_node_t{ /* sum of all colors represented by this node. 64 bit in case of HUGE image */ uint64_t r, g, b; int count, heap_idx; oct_node kids[8], parent; unsigned char n_kids, kid_idx, flags, depth; };

/* cmp function that decides the ordering in the heap. This is how we determine

  which octree node to fold next, the heart of the algorithm. */

inline int cmp_node(oct_node a, oct_node b) { if (a->n_kids < b->n_kids) return -1; if (a->n_kids > b->n_kids) return 1;

int ac = a->count * (1 + a->kid_idx) >> a->depth; int bc = b->count * (1 + b->kid_idx) >> b->depth; return ac < bc ? -1 : ac > bc; }

/* adding a color triple to octree */ oct_node node_insert(oct_node root, unsigned char *pix) {

1. define OCT_DEPTH 8

/* 8: number of significant bits used for tree. It's probably good enough for most images to use a value of 5. This affects how many nodes eventually end up in the tree and heap, thus smaller values helps with both speed and memory. */

unsigned char i, bit, depth = 0; for (bit = 1 << 7; ++depth < OCT_DEPTH; bit >>= 1) { i = !!(pix[1] & bit) * 4 + !!(pix[0] & bit) * 2 + !!(pix[2] & bit); if (!root->kids[i]) root->kids[i] = node_new(i, depth, root);

root = root->kids[i]; }

root->r += pix[0]; root->g += pix[1]; root->b += pix[2]; root->count++; return root; }

/* remove a node in octree and add its count and colors to parent node. */ oct_node node_fold(oct_node p) { if (p->n_kids) abort(); oct_node q = p->parent; q->count += p->count;

q->r += p->r; q->g += p->g; q->b += p->b; q->n_kids --; q->kids[p->kid_idx] = 0; return q; }

/* traverse the octree just like construction, but this time we replace the pixel

  color with color stored in the tree node */

void color_replace(oct_node root, unsigned char *pix) { unsigned char i, bit;

for (bit = 1 << 7; bit; bit >>= 1) { i = !!(pix[1] & bit) * 4 + !!(pix[0] & bit) * 2 + !!(pix[2] & bit); if (!root->kids[i]) break; root = root->kids[i]; }

pix[0] = root->r; pix[1] = root->g; pix[2] = root->b; }

/* Building an octree and keep leaf nodes in a bin heap. Afterwards remove first node

  in heap and fold it into its parent node (which may now be added to heap), until heap
  contains required number of colors. */

void color_quant(image im, int n_colors) { int i; unsigned char *pix = im->pix; node_heap heap = { 0, 0, 0 };

oct_node root = node_new(0, 0, 0), got; for (i = 0; i < im->w * im->h; i++, pix += 3) heap_add(&heap, node_insert(root, pix));

while (heap.n > n_colors + 1) heap_add(&heap, node_fold(pop_heap(&heap)));

double c; for (i = 1; i < heap.n; i++) { got = heap.buf[i]; c = got->count; got->r = got->r / c + .5; got->g = got->g / c + .5; got->b = got->b / c + .5; printf("%2d | %3llu %3llu %3llu (%d pixels)\n", i, got->r, got->g, got->b, got->count); }

for (i = 0, pix = im->pix; i < im->w * im->h; i++, pix += 3) color_replace(root, pix);

node_free(); free(heap.buf); }</lang>

J

Here, we use a simplistic averaging technique to build an initial set of colors and then use k-means clustering to refine them.

<lang j>kmc=:4 :0

 C=. /:~ 256 #.inv ,y  NB. colors
 G=. x (i.@] <.@* %) #C  NB. groups (initial)
 Q=. _  NB. quantized list of colors (initial
 whilst.-. Q-:&<.&(x&*)Q0 do.
   Q0=. Q
   Q=. /:~C (+/ % #)&.:*:/.~ G
   G=. (i. <./)"1 C +/&.:*: .- |:Q
 end.Q

)</lang>

The left argument is the number of colors desired.

The right argument is the image, with pixels represented as bmp color integers (base 256 numbers).

The result is the colors represented as pixel triples (blue, green, red). They are shown here as fractional numbers, but they should be either rounded to the nearest integer in the range 0..255 (and possibly converted back to bmp integer form) or scaled so they are floating point triples in the range 0..1.

<lang j> 16 kmc img 9.80722 22.2588 9.92601 12.8858 55.3493 0.708304 44.8472 84.209 3.24633 49.5887 121.661 2.71833 61.0382 136.5 4.76339 71.2045 145.562 7.98981 80.1206 109.635 13.7218 82.6982 144.239 11.4763 89.7106 154.822 17.5081 102.164 155.482 46.7242 134.026 167.051 24.0749 136.929 166.168 123.302 155.496 191.33 51.0613 176.638 208.89 85.1443 196.541 218.097 146.705 222.381 228.162 235.962</lang>

Here's a variation where colors are averaged linearly, rather than using root-mean-square, to find the center of each cluster:

<lang j>kmcL=:4 :0

 C=. /:~ 256 #.inv ,y  NB. colors
 G=. x (i.@] <.@* %) #C  NB. groups (initial)
 Q=. _  NB. quantized list of colors (initial
 whilst.-. Q-:&<.&(x&*)Q0 do.
   Q0=. Q
   Q=. /:~C (+/ % #)/.~ G
   G=. (i. <./)"1 C +/&.:*: .- |:Q
 end.Q

)

  16 kmcL img

7.52532 22.3347 0.650468 8.20129 54.4678 0.0326828 33.1132 69.8148 0.622265 54.2232 125.682 2.67713 56.7064 99.5008 3.04013 61.2135 136.42 4.2015 68.1246 140.576 6.37512 74.6006 143.606 7.57854 78.9101 150.792 10.2563 89.5873 148.621 14.6202 98.9523 154.005 25.7583 114.957 159.697 47.6423 145.816 178.136 33.8845 164.969 199.742 67.0467 179.849 207.594 109.973 209.229 221.18 204.513</lang>

And here is a variation on the linear approach where the initial set of points is chosen to try and spread out the most saturated colors in the image.

<lang j>kmcL2=:4 :0

 C=. (/: ] \:"1 +/) 256 #.inv ,y  NB. colors
 G=. x (i.@] <.@* %) #C  NB. groups (initial)
 Q=. _  NB. quantized list of colors (initial
 whilst.-. Q-:&<.&(x&*)Q0 do.
   Q0=. Q
   Q=. /:~C (+/ % #)/.~ G
   G=. (i. <./)"1 C +/&.:*: .- |:Q
 end.Q

)

  16 kmcL2 img
6.3768 19.3842  0.450336

9.01105 54.032 0.0164816 35.1247 74.7197 0.632245 46.7907 118.7 1.24327 57.9989 135.993 3.79941 67.9831 99.8956 4.91735 70.0663 134.648 6.13967

73.149 147.314    8.2013

89.2982 139.949 10.3272 90.4751 155.646 17.0229 102.234 154.252 44.3833 135.415 165.153 119.621

138.46 171.992   26.9326

165.804 200.575 64.9008 189.073 215.419 116.504 215.207 224.239 219.339</lang>

And, finally, an RMS variant that tries to separate the saturated colors:

<lang j>kmc2=:4 :0

 C=. (/: ] \:"1 +/) 256 #.inv ,y  NB. colors
 G=. x (i.@] <.@* %) #C  NB. groups (initial)
 Q=. _  NB. quantized list of colors (initial
 whilst.-. Q-:&<.&(x&*)Q0 do.
   Q0=. Q
   Q=. /:~C (+/ % #)&.:*:/.~ G
   G=. (i. <./)"1 C +/&.:*: .- |:Q
 end.Q

)

  16 kmc2 img

9.99887 21.7136 10.4787 11.6264 54.7053 0.715709 38.5676 78.0004 2.58646 53.2072 129.149 3.37507 60.4996 101.115 5.19625 66.9068 140.709 6.27453 76.7198 148.346 10.1477 87.2009 152.2 16.6881 89.2835 117.687 18.7302

104.18 157.488  26.3586

111.069 158.247 67.0767 144.853 177.753 34.9499 150.507 171.42 151.653 170.225 203.868 74.0487 194.476 219.757 129.133 222.407 229.012 230.327</lang>