colors

extract colors from pictures
git clone git://git.2f30.org/colors.git
Log | Files | Refs | README | LICENSE

colors.c (6611B)


      1 /* See LICENSE file for copyright and license details. */
      2 #include <err.h>
      3 #include <errno.h>
      4 #include <limits.h>
      5 #include <stdio.h>
      6 #include <stdlib.h>
      7 #include <time.h>
      8 
      9 #include "arg.h"
     10 #include "colors.h"
     11 #include "tree.h"
     12 
     13 #define LEN(x) (sizeof (x) / sizeof *(x))
     14 
     15 struct point {
     16 	int x;
     17 	int y;
     18 	int z;
     19 	long long freq;
     20 	struct cluster *c;
     21 	RB_ENTRY(point) e;
     22 };
     23 
     24 struct cluster {
     25 	struct point center;
     26 	size_t nelems;
     27 	struct {
     28 		long long nmembers;
     29 		long long x, y, z;
     30 	} tmp;
     31 };
     32 
     33 char *argv0;
     34 
     35 struct cluster *clusters;
     36 size_t nclusters = 8;
     37 RB_HEAD(pointtree, point) pointhead;
     38 size_t npoints;
     39 size_t niters;
     40 
     41 int eflag;
     42 int rflag;
     43 int hflag;
     44 int pflag;
     45 int vflag;
     46 
     47 int
     48 distance(struct point *p1, struct point *p2)
     49 {
     50 	int dx, dy, dz;
     51 
     52 	dx = (p1->x - p2->x) * (p1->x - p2->x);
     53 	dy = (p1->y - p2->y) * (p1->y - p2->y);
     54 	dz = (p1->z - p2->z) * (p1->z - p2->z);
     55 	return dx + dy + dz;
     56 }
     57 
     58 int
     59 pointcmp(struct point *p1, struct point *p2)
     60 {
     61 	unsigned int a, b;
     62 
     63 	a = p1->x << 16 | p1->y << 8 | p1->z;
     64 	b = p2->x << 16 | p2->y << 8 | p2->z;
     65 	return a - b;
     66 }
     67 RB_PROTOTYPE(pointtree, point, e, pointcmp)
     68 RB_GENERATE(pointtree, point, e, pointcmp)
     69 
     70 int
     71 isempty(struct cluster *c)
     72 {
     73 	return c->nelems == 0;
     74 }
     75 
     76 void
     77 adjmeans(struct cluster *c, size_t n)
     78 {
     79 	struct point *p;
     80 	size_t i;
     81 
     82 	for (i = 0; i < n; i++) {
     83 		c[i].tmp.nmembers = 0;
     84 		c[i].tmp.x = 0;
     85 		c[i].tmp.y = 0;
     86 		c[i].tmp.z = 0;
     87 	}
     88 
     89 	RB_FOREACH(p, pointtree, &pointhead) {
     90 		p->c->tmp.nmembers += p->freq;
     91 		p->c->tmp.x += p->x * p->freq;
     92 		p->c->tmp.y += p->y * p->freq;
     93 		p->c->tmp.z += p->z * p->freq;
     94 	}
     95 
     96 	for (i = 0; i < n; i++) {
     97 		if (isempty(&c[i]))
     98 			continue;
     99 		c[i].center.x = c[i].tmp.x / c[i].tmp.nmembers;
    100 		c[i].center.y = c[i].tmp.y / c[i].tmp.nmembers;
    101 		c[i].center.z = c[i].tmp.z / c[i].tmp.nmembers;
    102 	}
    103 }
    104 
    105 void
    106 initcluster_greyscale(struct cluster *c, int i)
    107 {
    108 	c->nelems = 0;
    109 	c->center.x = i;
    110 	c->center.y = i;
    111 	c->center.z = i;
    112 }
    113 
    114 void
    115 initcluster_pixel(struct cluster *c, int i)
    116 {
    117 	struct point *p;
    118 
    119 	c->nelems = 0;
    120 	RB_FOREACH(p, pointtree, &pointhead)
    121 		if (i-- == 0)
    122 			break;
    123 	c->center = *p;
    124 }
    125 
    126 struct hue {
    127 	int rgb[3];
    128 	int i; /* index in rgb[] of color to change next */
    129 } huetab[] = {
    130 	{ { 0xff, 0x00, 0x00 }, 2 }, /* red */
    131 	{ { 0xff, 0x00, 0xff }, 0 }, /* purple */
    132 	{ { 0x00, 0x00, 0xff }, 1 }, /* blue */
    133 	{ { 0x00, 0xff, 0xff }, 2 }, /* cyan */
    134 	{ { 0x00, 0xff, 0x00 }, 0 }, /* green */
    135 	{ { 0xff, 0xff, 0x00 }, 1 }, /* yellow */
    136 };
    137 
    138 struct point
    139 hueselect(int i)
    140 {
    141 	struct point p = { 0 };
    142 	struct hue h;
    143 	int idx, mod;
    144 
    145 	idx = i / 256;
    146 	mod = i % 256;
    147 	h = huetab[idx];
    148 
    149 	switch (h.rgb[h.i]) {
    150 	case 0x00:
    151 		h.rgb[h.i] += mod;
    152 		break;
    153 	case 0xff:
    154 		h.rgb[h.i] -= mod;
    155 		break;
    156 	}
    157 	p.x = h.rgb[0];
    158 	p.y = h.rgb[1];
    159 	p.z = h.rgb[2];
    160 	return p;
    161 }
    162 
    163 void
    164 initcluster_hue(struct cluster *c, int i)
    165 {
    166 	c->nelems = 0;
    167 	c->center = hueselect(i);
    168 }
    169 
    170 void (*initcluster)(struct cluster *c, int i);
    171 size_t initspace;
    172 
    173 void
    174 initclusters(struct cluster *c, size_t n)
    175 {
    176 	size_t i, next;
    177 	size_t step = initspace / n;
    178 
    179 	clusters = malloc(sizeof(*clusters) * n);
    180 	if (!clusters)
    181 		err(1, "malloc");
    182 	for (i = 0; i < n; i++) {
    183 		next = rflag ? rand() % initspace : i * step;
    184 		initcluster(&clusters[i], next);
    185 	}
    186 }
    187 
    188 void
    189 addmember(struct cluster *c, struct point *p)
    190 {
    191 	c->nelems++;
    192 	p->c = c;
    193 }
    194 
    195 void
    196 delmember(struct cluster *c, struct point *p)
    197 {
    198 	c->nelems--;
    199 	p->c = NULL;
    200 }
    201 
    202 int
    203 ismember(struct cluster *c, struct point *p)
    204 {
    205 	return p->c == c;
    206 }
    207 
    208 void
    209 process(void)
    210 {
    211 	struct point *p;
    212 	int *dists, mind, mini, i, done = 0;
    213 
    214 	dists = malloc(nclusters * sizeof(*dists));
    215 	if (!dists)
    216 		err(1, "malloc");
    217 
    218 	while (!done) {
    219 		done = 1;
    220 		niters++;
    221 		RB_FOREACH(p, pointtree, &pointhead) {
    222 			for (i = 0; i < nclusters; i++)
    223 				dists[i] = distance(p, &clusters[i].center);
    224 
    225 			/* find the cluster that is nearest to the point */
    226 			mind = dists[0];
    227 			mini = 0;
    228 			for (i = 1; i < nclusters; i++) {
    229 				if (mind > dists[i]) {
    230 					mind = dists[i];
    231 					mini = i;
    232 				}
    233 			}
    234 
    235 			if (ismember(&clusters[mini], p))
    236 				continue;
    237 
    238 			/* not done yet, move point to nearest cluster */
    239 			done = 0;
    240 			for (i = 0; i < nclusters; i++) {
    241 				if (ismember(&clusters[i], p)) {
    242 					delmember(&clusters[i], p);
    243 					break;
    244 				}
    245 			}
    246 			addmember(&clusters[mini], p);
    247 		}
    248 		adjmeans(clusters, nclusters);
    249 	}
    250 }
    251 
    252 void
    253 fillpoints(int r, int g, int b)
    254 {
    255 	struct point n = { 0 };
    256 	struct point *p;
    257 
    258 	n.x = r, n.y = g, n.z = b;
    259 	p = RB_FIND(pointtree, &pointhead, &n);
    260 	if (p) {
    261 		p->freq++;
    262 		return;
    263 	}
    264 
    265 	p = malloc(sizeof(*p));
    266 	if (!p)
    267 		err(1, "malloc");
    268 	p->x = r;
    269 	p->y = g;
    270 	p->z = b;
    271 	p->freq = 1;
    272 	p->c = NULL;
    273 	npoints++;
    274 	RB_INSERT(pointtree, &pointhead, p);
    275 }
    276 
    277 void
    278 printclusters(void)
    279 {
    280 	int i;
    281 
    282 	for (i = 0; i < nclusters; i++)
    283 		if (!isempty(&clusters[i]) || eflag)
    284 			printf("#%02x%02x%02x\n",
    285 			       clusters[i].center.x,
    286 			       clusters[i].center.y,
    287 			       clusters[i].center.z);
    288 }
    289 
    290 void
    291 printstatistics(void)
    292 {
    293 	struct point *p;
    294 	size_t ntotalpoints = 0;
    295 	size_t navgcluster = 0;
    296 
    297 	RB_FOREACH(p, pointtree, &pointhead) {
    298 		ntotalpoints += p->freq;
    299 		navgcluster++;
    300 	}
    301 	navgcluster /= nclusters;
    302 
    303 	fprintf(stderr, "Total number of points: %zu\n", ntotalpoints);
    304 	fprintf(stderr, "Number of unique points: %zu\n", npoints);
    305 	fprintf(stderr, "Number of clusters: %zu\n", nclusters);
    306 	fprintf(stderr, "Average number of unique points per cluster: %zu\n",
    307 	        navgcluster);
    308 	fprintf(stderr, "Number of iterations to converge: %zu\n", niters);
    309 }
    310 
    311 void
    312 usage(void)
    313 {
    314 	fprintf(stderr, "usage: %s [-erv] [-h | -p] [-n clusters]\n", argv0);
    315 	exit(1);
    316 }
    317 
    318 int
    319 main(int argc, char *argv[])
    320 {
    321 	char *e;
    322 	int c;
    323 
    324 	ARGBEGIN {
    325 	case 'e':
    326 		eflag = 1;
    327 		break;
    328 	case 'r':
    329 		rflag = 1;
    330 		break;
    331 	case 'v':
    332 		vflag = 1;
    333 		break;
    334 	case 'h':
    335 		hflag = 1;
    336 		pflag = 0;
    337 		break;
    338 	case 'p':
    339 		pflag = 1;
    340 		hflag = 0;
    341 		break;
    342 	case 'n':
    343 		errno = 0;
    344 		nclusters = strtol(EARGF(usage()), &e, 10);
    345 		if (*e || errno || !nclusters)
    346 			errx(1, "invalid number");
    347 		break;
    348 	default:
    349 		usage();
    350 	} ARGEND;
    351 
    352 	if (argc != 0)
    353 		usage();
    354 
    355 	if ((c = getc(stdin)) == EOF || ungetc(c, stdin) == EOF)
    356 		return 1;
    357 
    358 	RB_INIT(&pointhead);
    359 
    360 	(c == 'f' ? parseimg_ff : parseimg_png)(stdin, fillpoints);
    361 
    362 	initcluster = initcluster_greyscale;
    363 	initspace = 256;
    364 
    365 	if (rflag)
    366 		srand(time(NULL));
    367 	if (pflag) {
    368 		initcluster = initcluster_pixel;
    369 		initspace = npoints;
    370 	}
    371 	if (hflag) {
    372 		initcluster = initcluster_hue;
    373 		initspace = LEN(huetab) * 256;
    374 	}
    375 	/* cap number of clusters */
    376 	if (nclusters > initspace)
    377 		nclusters = initspace;
    378 
    379 	initclusters(clusters, nclusters);
    380 	process();
    381 	printclusters();
    382 	if (vflag)
    383 		printstatistics();
    384 	return 0;
    385 }