Color quantization/C: Difference between revisions

Content added Content deleted
(Created page with "This is a complete program that takes a PPM P6 image and a number, then writes out the image reduced to the number of colors to out.ppm. <lang c>#include <stdio.h> #include <stdl...")
 
(dithering)
Line 1: Line 1:
This is a complete program that takes a PPM P6 image and a number, then writes out the image reduced to the number of colors to out.ppm.
This is a complete program that takes a PPM P6 image and a number, then writes out the image reduced to the number of colors to out.ppm. There is optional dithering, too, which doesn't make a whole lot of difference with say 64 colors or more. And with low colors, the quantization did such a good job of picking average colors that it actually hurts the dithering process.
<lang c>#include <stdio.h>
<lang c>#include <stdio.h>
#include <stdlib.h>
#include <stdlib.h>
Line 7: Line 7:
#include <string.h>
#include <string.h>
#include <stdint.h>
#include <stdint.h>
#include <math.h>


typedef struct {
typedef struct {
Line 68: Line 69:


#define ON_INHEAP 1
#define ON_INHEAP 1

typedef struct oct_node_t oct_node_t, *oct_node;
typedef struct oct_node_t oct_node_t, *oct_node;
struct oct_node_t{
struct oct_node_t{
/* sum of all colors represented by this node. 64 bit in case of HUGE image */
int64_t r, g, b; /* sum of all child node colors */
uint64_t r, g, b;
int count, heap_idx;
int count, heap_idx;
oct_node kids[8], parent;
unsigned char n_kids, kid_idx, flags, depth;
unsigned char n_kids, kid_idx, flags, depth;
oct_node kids[8], parent;
};
};


Line 82: Line 83:
} node_heap;
} node_heap;


/* 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)
inline int cmp_node(oct_node a, oct_node b)
{
{
Line 89: Line 88:
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 ac = a->count >> a->depth;
int bc = b->count * (1 + b->kid_idx) >> b->depth;
int bc = b->count >> b->depth;
return ac < bc ? -1 : ac > bc;
return ac < bc ? -1 : ac > bc;
}
}
Line 195: Line 194:
oct_node node_insert(oct_node root, unsigned char *pix)
oct_node node_insert(oct_node root, unsigned char *pix)
{
{
# 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;
unsigned char i, bit, depth = 0;

for (bit = 1 << 7; ++depth < OCT_DEPTH; bit >>= 1) {
for (bit = 1 << 7; ++depth < 8; bit >>= 1) {
i = !!(pix[1] & bit) * 4 + !!(pix[0] & bit) * 2 + !!(pix[2] & bit);
i = !!(pix[1] & bit) * 4 + !!(pix[0] & bit) * 2 + !!(pix[2] & bit);
if (!root->kids[i])
if (!root->kids[i])
Line 231: Line 225:
}
}


/* 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)
void color_replace(oct_node root, unsigned char *pix)
{
{
Line 248: Line 240:
}
}


void color_quant(image im, int n_colors)
void error_diffuse(image im, node_heap *h)
{
oct_node nearest_color(int *v) {
int i;
int diff, max = 100000000;
oct_node o = 0;
for (i = 1; i < h->n; i++) {
diff = 3 * abs(h->buf[i]->r - v[0])
+ 5 * abs(h->buf[i]->g - v[1])
+ 2 * abs(h->buf[i]->b - v[2]);
if (diff < max) {
max = diff;
o = h->buf[i];
}
}
return o;
}

# define POS(i, j) (3 * ((i) * im->w + (j)))
int i, j;
int *npx = calloc(sizeof(int), im->h * im->w * 3), *px;
int v[3];
unsigned char *pix = im->pix;
oct_node nd;

#define C10 7
#define C01 5
#define C11 2
#define C00 1
#define CTOTAL (C00 + C11 + C10 + C01)

for (px = npx, i = 0; i < im->h; i++) {
for (j = 0; j < im->w; j++, pix += 3, px += 3) {
px[0] = (int)pix[0] * CTOTAL;
px[1] = (int)pix[1] * CTOTAL;
px[2] = (int)pix[2] * CTOTAL;
}
}
#define clamp(x, i) if (x[i] > 255) x[i] = 255; if (x[i] < 0) x[i] = 0
pix = im->pix;
for (px = npx, i = 0; i < im->h; i++) {
for (j = 0; j < im->w; j++, pix += 3, px += 3) {
px[0] /= CTOTAL;
px[1] /= CTOTAL;
px[2] /= CTOTAL;
clamp(px, 0); clamp(px, 1); clamp(px, 2);

nd = nearest_color(px);

v[0] = px[0] - nd->r;
v[1] = px[1] - nd->g;
v[2] = px[2] - nd->b;

pix[0] = nd->r; pix[1] = nd->g; pix[2] = nd->b;
if (j < im->w - 1) {
npx[POS(i, j+1) + 0] += v[0] * C10;
npx[POS(i, j+1) + 1] += v[1] * C10;
npx[POS(i, j+1) + 2] += v[2] * C10;
}
if (i >= im->h - 1) continue;

npx[POS(i+1, j) + 0] += v[0] * C01;
npx[POS(i+1, j) + 1] += v[1] * C01;
npx[POS(i+1, j) + 2] += v[2] * C01;

if (j < im->w - 1) {
npx[POS(i+1, j+1) + 0] += v[0] * C11;
npx[POS(i+1, j+1) + 1] += v[1] * C11;
npx[POS(i+1, j+1) + 2] += v[2] * C11;
}
if (j) {
npx[POS(i+1, j-1) + 0] += v[0] * C00;
npx[POS(i+1, j-1) + 1] += v[1] * C00;
npx[POS(i+1, j-1) + 2] += v[2] * C00;
}
}
}
free(npx);
}

void color_quant(image im, int n_colors, int dither)
{
{
int i;
int i;
Line 268: Line 340:
got->g = got->g / c + .5;
got->g = got->g / c + .5;
got->b = got->b / 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);
}
}


if (dither) error_diffuse(im, &heap);
for (i = 0, pix = im->pix; i < im->w * im->h; i++, pix += 3)
else
color_replace(root, pix);
for (i = 0, pix = im->pix; i < im->w * im->h; i++, pix += 3)
color_replace(root, pix);


node_free();
node_free();
Line 289: Line 361:


image im = read_ppm(v[1]);
image im = read_ppm(v[1]);
color_quant(im, c);
color_quant(im, c, 0);
write_ppm(im, "out.pnm");
write_ppm(im, "out.pnm");
free(im);
free(im);
Retrieved from "https://rosettacode.org/wiki/Color_quantization/C"