1 /* +-------------------------------------------------------------------+ */
2 /* | Copyright (C) 1993, David Koblas (koblas@netcom.com) | */
3 /* | | */
4 /* | Permission to use, copy, modify, and to distribute this software | */
5 /* | and its documentation for any purpose is hereby granted without | */
6 /* | fee, provided that the above copyright notice appear in all | */
7 /* | copies and that both that copyright notice and this permission | */
8 /* | notice appear in supporting documentation. There is no | */
9 /* | representations about the suitability of this software for | */
10 /* | any purpose. this software is provided "as is" without express | */
11 /* | or implied warranty. | */
12 /* | | */
13 /* +-------------------------------------------------------------------+ */
14
15 /* $Id: imageComp.c,v 1.17 2005/03/20 20:15:32 demailly Exp $ */
16
17 /* reduce.c:
18
19 * reduce an image's colormap usage to a set number of colors. this also
20 * translates a true color image to a TLA-style image of `n' colors.
21 *
22 * this uses an algorithm by Paul Heckbert discussed in `Color Image
23 * Quantization for Frame Buffer Display,' _Computer Graphics_ 16(3),
24 * pp 297-307. this implementation is based on one discussed in
25 * 'A Few Good Colors,' _Computer Language_, Aug. 1990, pp 32-41 by
26 * Dave Pomerantz.
27 *
28 * this function cannot reduce to any number of colors larger than 32768.
29 *
30 * jim frost 04.18.91
31 *
32 */
33
34 /*
35 * Copyright 1989, 1990, 1991 Jim Frost
36 *
37 * Permission to use, copy, modify, distribute, and sell this software
38 * and its documentation for any purpose is hereby granted without fee,
39 * provided that the above copyright notice appear in all copies and
40 * that both that copyright notice and this permission notice appear
41 * in supporting documentation. The author makes no representations
42 * about the suitability of this software for any purpose. It is
43 * provided "as is" without express or implied warranty.
44 *
45 * THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
46 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
47 * NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, INDIRECT OR
48 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
49 * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
50 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE
51 * USE OR PERFORMANCE OF THIS SOFTWARE.
52 */
53
54 #include <X11/Intrinsic.h>
55 #include <stdio.h>
56
57 #ifndef NOSTDHDRS
58 #include <stdlib.h>
59 #include <unistd.h>
60 #endif
61
62 /*
63 ** swiped from X11/Xfuncproto.h
64 ** since qsort() may or may not be defined with a constant sub-function
65 */
66 #ifndef _Xconst
67 #if __STDC__ || defined(__cplusplus) || defined(c_plusplus) || (FUNCPROTO&4)
68 #define _Xconst const
69 #else
70 #define _Xconst
71 #endif
72 #endif /* _Xconst */
73
74 #include "image.h"
75 #include "hash.h"
76 #include "protocol.h"
77 #include "misc.h"
78
79 /*
80 ** This converts an RGB pixel into a 15-bit true color value.
81 */
82
83 #define TO_15BITS(r,g,b) ((r & 0xf8) << 7)|((g & 0xf8) << 2)|((b & 0xf8) >> 3)
84
85 /*
86 ** These macros extract color intensities, in the compressed range.
87 */
88
89 #define RED_INTENSITY(P) (((P) & 0x7c00) >> 10)
90 #define GREEN_INTENSITY(P) (((P) & 0x03e0) >> 5)
91 #define BLUE_INTENSITY(P) ((P) & 0x001f)
92
93 /*
94 ** These macros extract the 0..255 range value from the "true color" version
95 */
96 #define RED_VALUE(P) (((P) & 0x7c00) >> 7)
97 #define GREEN_VALUE(P) (((P) & 0x03e0) >> 2)
98 #define BLUE_VALUE(P) (((P) & 0x001f) << 3)
99
100 /*
101 * This structure defines a color area which is made up of an array of pixel
102 * values and a count of the total number of image pixels represented by
103 * the area. Color areas are kept in a list sorted by the number of image
104 * pixels they represent.
105 */
106
107 typedef struct color_area {
108 unsigned short *pixels; /* array of pixel values in this area */
109 unsigned short npixels; /* size of above array */
110 /* predicate func to sort with before * splitting */
111 int (*func) (unsigned short *, unsigned short *);
112 unsigned long count; /* # of image pixels we represent */
113 struct color_area *prev, *next;
114 } Area_t;
115
116 typedef struct {
117 unsigned short idx;
118 unsigned char r, g, b;
119 } color_t;
120
121 /*
122 ** Predicate functions for qsort
123 ** Generated code as you can see.
124 */
125
126 #ifndef __STDC__
127 #define SORT(ca, cb, cc) \
128 static int sort/**/ca/**/cb/**/cc(unsigned short *p1, unsigned short *p2) \
129 { \
130 unsigned int R1,R2,G1,G2,B1,B2; \
131 R1 = RED_INTENSITY(*p1); \
132 G1 = GREEN_INTENSITY(*p1); \
133 B1 = BLUE_INTENSITY(*p1); \
134 R2 = RED_INTENSITY(*p2); \
135 G2 = GREEN_INTENSITY(*p2); \
136 B2 = BLUE_INTENSITY(*p2); \
137 if (ca/**/1 == ca/**/2) \
138 if (cb/**/1 == cb/**/2) \
139 return (cc/**/1 < cc/**/2) ? -1 : 1; \
140 else \
141 return (cb/**/1 < cb/**/2) ? -1 : 1; \
142 else \
143 return (ca/**/1 < ca/**/2) ? -1 : 1; \
144 }
145 #else
146 #define SORT(ca, cb, cc) \
147 static int sort ## ca ## cb ## cc(unsigned short *p1, unsigned short *p2) \
148 { \
149 unsigned int R1,R2,G1,G2,B1,B2; \
150 R1 = RED_INTENSITY(*p1); \
151 G1 = GREEN_INTENSITY(*p1); \
152 B1 = BLUE_INTENSITY(*p1); \
153 R2 = RED_INTENSITY(*p2); \
154 G2 = GREEN_INTENSITY(*p2); \
155 B2 = BLUE_INTENSITY(*p2); \
156 if (ca ## 1 == ca ## 2) \
157 if (cb ## 1 == cb ## 2) \
158 return (cc ## 1 < cc ## 2) ? -1 : 1; \
159 else \
160 return (cb ## 1 < cb ## 2) ? -1 : 1; \
161 else \
162 return (ca ## 1 < ca ## 2) ? -1 : 1; \
163 }
164 #endif
165
166 SORT(R, G, B)
167 SORT(R, B, G)
168 SORT(G, R, B)
169 SORT(G, B, R)
170 SORT(B, G, R)
171 SORT(B, R, G)
172 #undef SORT
173
174 Image *outputImage;
175
176 /*
177 * this does calculations on a color area following a split and inserts
178 * the color area in the list of color areas.
179 */
180
181 static void
insertColorArea(unsigned long * counts,Area_t ** rlargest,Area_t ** rsmallest,Area_t * area)182 insertColorArea(unsigned long *counts,
183 Area_t ** rlargest, Area_t ** rsmallest, Area_t * area)
184 {
185 int i;
186 unsigned int red, green, blue;
187 unsigned int min_red, min_green, min_blue;
188 unsigned int max_red, max_green, max_blue = 0;
189 Area_t *largest, *smallest;
190
191 /*
192 ** update pixel count for this area and find RGB intensity widths
193 */
194 min_red = max_red = RED_INTENSITY(area->pixels[0]);
195 min_green = max_green = GREEN_INTENSITY(area->pixels[0]);
196 min_blue = max_blue = BLUE_INTENSITY(area->pixels[0]);
197
198 area->count = 0;
199 for (i = 1; i < area->npixels; i++) {
200 area->count += counts[area->pixels[i]];
201 red = RED_INTENSITY(area->pixels[i]);
202 green = GREEN_INTENSITY(area->pixels[i]);
203 blue = BLUE_INTENSITY(area->pixels[i]);
204
205 if (red < min_red)
206 min_red = red;
207 if (red > max_red)
208 max_red = red;
209 if (green < min_green)
210 min_green = green;
211 if (green > max_green)
212 max_green = green;
213 if (blue < min_blue)
214 min_blue = blue;
215 if (blue > max_blue)
216 max_blue = blue;
217 }
218
219 /*
220 ** calculate widths and determine which predicate function to use based
221 ** on the result
222 */
223
224 red = max_red - min_red;
225 green = max_green - min_green;
226 blue = max_blue - min_blue;
227
228 if (red > green)
229 if (green > blue)
230 area->func = sortRGB;
231 else if (red > blue)
232 area->func = sortRBG;
233 else
234 area->func = sortBRG;
235 else if (green > blue)
236 if (red > blue)
237 area->func = sortGRB;
238 else
239 area->func = sortGBR;
240 else
241 area->func = sortBGR;
242
243 /*
244 * insert color area in color area list sorted by number of pixels that
245 * the area represents
246 */
247
248 largest = *rlargest;
249 smallest = *rsmallest;
250
251 if (largest == NULL) {
252 largest = smallest = area;
253 area->prev = area->next = (Area_t *) NULL;
254 } else if (area->npixels < 2) {
255 /*
256 ** if we only have one element, our pixel count is immaterial so we get
257 ** stuck on the end of the list.
258 */
259 smallest->next = area;
260 area->prev = smallest;
261 area->next = (Area_t *) NULL;
262 smallest = area;
263 } else {
264 /*
265 ** insert node into list
266 */
267 Area_t *cur;
268
269 for (cur = largest; cur != NULL; cur = cur->next) {
270 if ((area->count > cur->count) || (cur->npixels < 2)) {
271 area->prev = cur->prev;
272 area->next = cur;
273 cur->prev = area;
274 if (area->prev != NULL)
275 area->prev->next = area;
276 else
277 largest = area;
278 break;
279 }
280 }
281 if (cur == NULL) {
282 area->prev = smallest;
283 area->next = (Area_t *) NULL;
284 smallest->next = area;
285 smallest = area;
286 }
287 }
288 *rlargest = largest;
289 *rsmallest = smallest;
290 }
291
292 /*
293 ** hash table support functions.
294 */
295 static int
cmpColor(void * a,void * b)296 cmpColor(void *a, void *b)
297 {
298 color_t *ca = (color_t *) a;
299 color_t *cb = (color_t *) b;
300
301 if (ca->r != cb->r)
302 return ca->r < cb->r ? -1 : 1;
303 if (ca->g != cb->g)
304 return ca->g < cb->g ? -1 : 1;
305 if (ca->b != cb->b)
306 return ca->b < cb->b ? -1 : 1;
307 return 0;
308 }
309
310 static void
freeColor(void * junk)311 freeColor(void *junk)
312 {
313 /*
314 ** Don't apply a free function to the hashtable items.
315 */
316 }
317
318 Image *
ImageCompress(Image * input,int ncolors,int noforce)319 ImageCompress(Image * input, int ncolors, int noforce)
320 {
321 unsigned long counts[32768];
322 unsigned short array[XtNumber(counts)];
323 unsigned char *ocp;
324 unsigned short *osp;
325 int x, y, i, count, nuniq;
326 int allocated;
327 Area_t *areas, *largest, *smallest;
328 Image *output;
329 void *htable;
330 color_t *ctable;
331
332 /*
333 ** make sure we have array space...
334 */
335 if (ncolors > XtNumber(counts))
336 ncolors = XtNumber(counts);
337
338 /*
339 ** Why are we trying to compress a b&w image?
340 ** or an image that already fits
341 */
342 if (input->isBW)
343 return input;
344 if (input->cmapSize != 0 && input->cmapSize < ncolors)
345 return input;
346
347 /*
348 ** Create a histogram of 15-bit color values.
349 ** also, save the "real" color values.
350 ** or at least enough of them so that we know
351 ** that compression is really necessary.
352 */
353 htable = HashCreate(cmpColor, freeColor, 256);
354 ctable = (color_t *) XtCalloc(sizeof(color_t), ncolors + 1);
355 nuniq = 0;
356
357 /* GRR: use memset() instead? */
358 for (i = 0; i < XtNumber(counts); i++)
359 counts[i] = 0;
360
361 for (y = 0; y < input->height; y++) {
362 for (x = 0; x < input->width; x++) {
363 unsigned char *dp;
364
365 dp = ImagePixel(input, x, y);
366
367 if (nuniq <= ncolors && htable != NULL) {
368 color_t *cptr = &ctable[nuniq];
369 cptr->r = dp[0];
370 cptr->g = dp[1];
371 cptr->b = dp[2];
372 if (HashFind(htable, dp[0], cptr) == NULL) {
373 cptr->idx = nuniq;
374 HashAdd(htable, dp[0], cptr);
375 nuniq++;
376 }
377 }
378 counts[TO_15BITS(dp[0], dp[1], dp[2])]++;
379 }
380
381 if (y % 256 == 0)
382 StateTimeStep();
383 }
384
385 if (nuniq <= ncolors) {
386 /*
387 ** Wow, this has few enough colors to fit in the requested colormap.
388 ** This should be able to renumber (compress) an existing
389 ** colormap, rather than creating a new image.
390 */
391 unsigned short *osp;
392 unsigned char *ocp;
393
394 output = ImageNewCmap(input->width, input->height, nuniq);
395 for (y = 0; y < nuniq; y++)
396 ImageSetCmap(output, y,
397 ctable[y].r, ctable[y].g, ctable[y].b);
398
399 osp = (unsigned short *) output->data;
400 ocp = output->data;
401
402 for (y = 0; y < input->height; y++) {
403 for (x = 0; x < input->width; x++, osp++, ocp++) {
404 unsigned char *dp;
405 color_t *cptr, col;
406
407 dp = ImagePixel(input, x, y);
408
409 col.r = dp[0];
410 col.g = dp[1];
411 col.b = dp[2];
412 cptr = HashFind(htable, dp[0], &col);
413
414 if (nuniq > 256)
415 *osp = cptr->idx;
416 else
417 *ocp = cptr->idx;
418 }
419
420 if (y % 256 == 0)
421 StateTimeStep();
422 }
423
424 output->cmapPacked = True;
425
426 HashDestroy(htable);
427 XtFree((XtPointer) ctable);
428 output->alpha = input->alpha;
429 input->alpha = NULL;
430 ImageDelete(input);
431 outputImage = output;
432 return output;
433 }
434 HashDestroy(htable);
435 XtFree((XtPointer) ctable);
436
437 /* GRR 960525: if not forcing compression to ncolors, return now */
438 if (noforce)
439 return NULL;
440
441 /*
442 ** Create an array of 15-bit pixel values that actually occur
443 ** in the image.
444 */
445 count = 0;
446 for (i = 0; i < XtNumber(counts); i++) {
447 if (counts[i] != 0)
448 array[count++] = i;
449 }
450
451 /*
452 ** Create the color areas and initialize the first element
453 */
454 areas = (Area_t *) XtCalloc(sizeof(Area_t), ncolors);
455 areas[0].pixels = array;
456 areas[0].npixels = count;
457
458 largest = smallest = NULL;
459 insertColorArea(counts, &largest, &smallest, areas);
460
461 allocated = 1;
462
463 /*
464 ** While there are areas still to be broken down
465 ** or the largest cannot be subdivided.
466 */
467 while (allocated < ncolors && largest->npixels >= 2) {
468 Area_t *newArea, *oldArea;
469 int i, midpoint;
470
471 qsort(largest->pixels, largest->npixels, sizeof(short),
472 (int (*)(_Xconst void *, _Xconst void *)) largest->func);
473
474 /*
475 ** Find the midpoint of the largest area an split
476 */
477 midpoint = largest->count / 2;
478 for (i = 0, count = 0; i < largest->npixels && count < midpoint; i++)
479 count += counts[largest->pixels[i]];
480
481 if (i == largest->npixels)
482 i--;
483 if (i == 0)
484 i = 1;
485 newArea = areas + allocated;
486 newArea->pixels = largest->pixels + i;
487 newArea->npixels = largest->npixels - i;
488 largest->npixels = i;
489 oldArea = largest;
490 largest = largest->next;
491 if (largest != NULL)
492 largest->prev = NULL;
493 else
494 smallest = NULL;
495
496 /*
497 ** recalculate for each area of split and insert in the area list
498 */
499 insertColorArea(counts, &largest, &smallest, newArea);
500 insertColorArea(counts, &largest, &smallest, oldArea);
501
502 allocated++;
503
504 if (allocated % 64 == 0)
505 StateTimeStep();
506 }
507
508 output = ImageNewCmap(input->width, input->height, allocated);
509 output->alpha = input->alpha;
510 input->alpha = NULL;
511
512 for (i = 0; i < allocated; i++) {
513 long red, green, blue;
514 int j;
515
516 /*
517 ** Calculate RGB table from each color area. This should really calculate
518 ** a new color by weighting the intensities by the number of pixels, but
519 ** it's a pain to scale so this just averages all the intensities. It
520 ** works pretty well regardless.
521 */
522 red = green = blue = 0;
523 for (j = 0; j < areas[i].npixels; j++) {
524 unsigned short pixel = areas[i].pixels[j];
525
526 red += RED_VALUE(pixel) & 0xff;
527 green += GREEN_VALUE(pixel) & 0xff;
528 blue += BLUE_VALUE(pixel) & 0xff;
529
530 counts[pixel] = i;
531 }
532 red /= areas[i].npixels;
533 green /= areas[i].npixels;
534 blue /= areas[i].npixels;
535
536 ImageSetCmap(output, i, red, green, blue);
537 }
538
539 /*
540 ** Done with the areas information.
541 */
542 XtFree((XtPointer) areas);
543
544 /*
545 ** Copy input to output
546 */
547
548 ocp = output->data;
549 osp = (unsigned short *) output->data;
550
551 for (y = 0; y < input->height; y++) {
552 for (x = 0; x < input->width; x++) {
553 unsigned char *dp;
554
555 dp = ImagePixel(input, x, y);
556
557 if (output->cmapSize > 256) {
558 *osp++ = counts[TO_15BITS(dp[0], dp[1], dp[2])];
559 } else {
560 *ocp++ = counts[TO_15BITS(dp[0], dp[1], dp[2])];
561 }
562 }
563 }
564
565 output->cmapPacked = True;
566 ImageDelete(input);
567 outputImage = output;
568 return output;
569 }
570