e6d32dcd0db8decf655754a976f17a23f8ca1979
[alioth/magicpoint.git] / image / reduce.c
1 /* reduce.c:
2  *
3  * reduce an image's colormap usage to a set number of colors.  this also
4  * translates a true color image to a TLA-style image of `n' colors.
5  *
6  * this uses an algorithm by Paul Heckbert discussed in `Color Image
7  * Quantization for Frame Buffer Display,' _Computer Graphics_ 16(3),
8  * pp 297-307.  this implementation is based on one discussed in
9  * 'A Few Good Colors,' _Computer Language_, Aug. 1990, pp 32-41 by
10  * Dave Pomerantz.
11  *
12  * this function cannot reduce to any number of colors larger than 32768.
13  *
14  * jim frost 04.18.91
15  *
16  * Copyright 1991 Jim Frost.
17  * See LICENCE file for complete legalities.
18  */
19
20 #include "image.h"
21
22 #include <stdlib.h> /* for qsort */
23
24 /* this converts a TLA-style pixel into a 15-bit true color pixel
25  */
26
27 #define TLA_TO_15BIT(TABLE,PIXEL)           \
28   ((((TABLE).red[PIXEL] & 0xf800) >> 1) |   \
29    (((TABLE).green[PIXEL] & 0xf800) >> 6) | \
30    (((TABLE).blue[PIXEL] & 0xf800) >> 11))
31
32 /* this converts a 24-bit true color pixel into a 15-bit true color pixel
33  */
34
35 #define TRUE_TO_15BIT(PIXEL)     \
36   ((((PIXEL) & 0xf80000) >> 9) | \
37    (((PIXEL) & 0x00f800) >> 6) | \
38    (((PIXEL) & 0x0000f8) >> 3))
39
40 /* these macros extract color intensities from a 15-bit true color pixel
41  */
42
43 #define RED_INTENSITY(P)   (((P) & 0x7c00) >> 10)
44 #define GREEN_INTENSITY(P) (((P) & 0x03e0) >> 5)
45 #define BLUE_INTENSITY(P)   ((P) & 0x001f)
46
47 /* this structure defines a color area which is made up of an array of pixel
48  * values and a count of the total number of image pixels represented by
49  * the area.  color areas are kept in a list sorted by the number of image
50  * pixels they represent.
51  */
52
53 struct color_area {
54     unsigned short    *pixels;       /* array of pixel values in this area */
55     unsigned short     num_pixels;   /* size of above array */
56     /* predicate func to sort with before splitting */
57     int              (*sort_func)(unsigned short *, unsigned short *);
58     unsigned long      pixel_count;  /* # of image pixels we represent */
59     struct color_area *prev, *next;
60 };
61
62 /* predicate functions for qsort
63  */
64
65 static int
66 sortRGB(unsigned short *p1, unsigned short *p2)
67 { unsigned int red1, green1, blue1, red2, green2, blue2;
68
69   red1= RED_INTENSITY(*p1);
70   green1= GREEN_INTENSITY(*p1);
71   blue1= BLUE_INTENSITY(*p1);
72   red2= RED_INTENSITY(*p2);
73   green2= GREEN_INTENSITY(*p2);
74   blue2= BLUE_INTENSITY(*p2);
75
76   if (red1 == red2)
77     if (green1 == green2)
78       if (blue1 < blue2)
79         return(-1);
80       else
81         return(1);
82     else if (green1 < green2)
83       return(-1);
84     else
85       return(1);
86   else if (red1 < red2)
87     return(-1);
88   else
89     return(1);
90 }
91
92 static int
93 sortRBG(unsigned short *p1, unsigned short *p2)
94 { unsigned int red1, green1, blue1, red2, green2, blue2;
95
96   red1= RED_INTENSITY(*p1);
97   green1= GREEN_INTENSITY(*p1);
98   blue1= BLUE_INTENSITY(*p1);
99   red2= RED_INTENSITY(*p2);
100   green2= GREEN_INTENSITY(*p2);
101   blue2= BLUE_INTENSITY(*p2);
102
103   if (red1 == red2)
104     if (blue1 == blue2)
105       if (green1 < green2)
106         return(-1);
107       else
108         return(1);
109     else if (blue1 < blue2)
110       return(-1);
111     else
112       return(1);
113   else if (red1 < red2)
114     return(-1);
115   else
116     return(1);
117 }
118
119 static int
120 sortGRB(unsigned short *p1, unsigned short *p2)
121 { unsigned int red1, green1, blue1, red2, green2, blue2;
122
123   red1= RED_INTENSITY(*p1);
124   green1= GREEN_INTENSITY(*p1);
125   blue1= BLUE_INTENSITY(*p1);
126   red2= RED_INTENSITY(*p2);
127   green2= GREEN_INTENSITY(*p2);
128   blue2= BLUE_INTENSITY(*p2);
129
130   if (green1 == green2)
131     if (red1 == red2)
132       if (blue1 < blue2)
133         return(-1);
134       else
135         return(1);
136     else if (red1 < red2)
137       return(-1);
138     else
139       return(1);
140   else if (green1 < green2)
141     return(-1);
142   else
143     return(1);
144 }
145
146 static int
147 sortGBR(unsigned short *p1, unsigned short *p2)
148 { unsigned int red1, green1, blue1, red2, green2, blue2;
149
150   red1= RED_INTENSITY(*p1);
151   green1= GREEN_INTENSITY(*p1);
152   blue1= BLUE_INTENSITY(*p1);
153   red2= RED_INTENSITY(*p2);
154   green2= GREEN_INTENSITY(*p2);
155   blue2= BLUE_INTENSITY(*p2);
156
157   if (green1 == green2)
158     if (blue1 == blue2)
159       if (red1 < red2)
160         return(-1);
161       else
162         return(1);
163     else if (blue1 < blue2)
164       return(-1);
165     else
166       return(1);
167   else if (green1 < green2)
168     return(-1);
169   else
170     return(1);
171 }
172
173 static int
174 sortBRG(unsigned short *p1, unsigned short *p2)
175 { unsigned int red1, green1, blue1, red2, green2, blue2;
176
177   red1= RED_INTENSITY(*p1);
178   green1= GREEN_INTENSITY(*p1);
179   blue1= BLUE_INTENSITY(*p1);
180   red2= RED_INTENSITY(*p2);
181   green2= GREEN_INTENSITY(*p2);
182   blue2= BLUE_INTENSITY(*p2);
183
184   if (blue1 == blue2)
185     if (red1 == red2)
186       if (green1 < green2)
187         return(-1);
188       else
189         return(1);
190     else if (red1 < red2)
191       return(-1);
192     else
193       return(1);
194   else if (blue1 < blue2)
195     return(-1);
196   else
197     return(1);
198 }
199
200 static int
201 sortBGR(unsigned short *p1, unsigned short *p2)
202 { unsigned int red1, green1, blue1, red2, green2, blue2;
203
204   red1= RED_INTENSITY(*p1);
205   green1= GREEN_INTENSITY(*p1);
206   blue1= BLUE_INTENSITY(*p1);
207   red2= RED_INTENSITY(*p2);
208   green2= GREEN_INTENSITY(*p2);
209   blue2= BLUE_INTENSITY(*p2);
210
211   if (blue1 == blue2)
212     if (green1 == green2)
213       if (red1 < red2)
214         return(-1);
215       else
216         return(1);
217     else if (green1 < green2)
218       return(-1);
219     else
220       return(1);
221   else if (blue1 < blue2)
222     return(-1);
223   else
224     return(1);
225 }
226
227 /* this does calculations on a color area following a split and inserts
228  * the color area in the list of color areas.
229  */
230
231 static void
232 insertColorArea(unsigned long *pixel_counts,
233     struct color_area **rlargest, struct color_area **rsmallest,
234     struct color_area *area)
235 { int a;
236   unsigned int red, green, blue;
237   unsigned int min_red, min_green, min_blue;
238   unsigned int max_red, max_green, max_blue= 0;
239   struct color_area *largest, *smallest, *tmp_area;
240
241   min_red= min_green= min_blue= 31;
242   max_red= max_green= max_blue= 0;
243
244   /* update pixel count for this area and find RGB intensity widths
245    */
246
247   area->pixel_count= 0;
248   for (a= 0; a < area->num_pixels; a++) {
249     area->pixel_count += pixel_counts[area->pixels[a]];
250     red= RED_INTENSITY(area->pixels[a]);
251     green= GREEN_INTENSITY(area->pixels[a]);
252     blue= BLUE_INTENSITY(area->pixels[a]);
253     if (red < min_red)
254       min_red= red;
255     if (red > max_red)
256       max_red= red;
257     if (green < min_green)
258       min_green= green;
259     if (green > max_green)
260       max_green= green;
261     if (blue < min_blue)
262       min_blue= blue;
263     if (blue > max_blue)
264       max_blue= blue;
265   }
266
267   /* calculate widths and determine which predicate function to use based
268    * on the result
269    */
270
271   red= max_red - min_red;
272   green= max_green - min_green;
273   blue= max_blue - min_blue;
274
275   if (red > green)
276     if (green > blue)
277       area->sort_func= sortRGB;
278     else if (red > blue)
279       area->sort_func= sortRBG;
280     else
281       area->sort_func= sortBRG;
282   else if (green > blue)
283     if (red > blue)
284       area->sort_func= sortGRB;
285     else
286       area->sort_func= sortGBR;
287   else
288     area->sort_func= sortBGR;
289
290   /* insert color area in color area list sorted by number of pixels that
291    * the area represents
292    */
293
294   largest= *rlargest;
295   smallest= *rsmallest;
296
297   if (!largest) {
298     largest= smallest= area;
299     area->prev= area->next= (struct color_area *)NULL;
300   }
301
302   /* if we only have one element, our pixel count is immaterial so we get
303    * stuck on the end of the list.
304    */
305
306   else if (area->num_pixels < 2) {
307     smallest->next= area;
308     area->prev= smallest;
309     area->next= (struct color_area *)NULL;
310     smallest= area;
311   }
312
313   /* insert node into list
314    */
315
316   else {
317     for (tmp_area= largest; tmp_area; tmp_area= tmp_area->next)
318       if ((area->pixel_count > tmp_area->pixel_count) ||
319           (tmp_area->num_pixels < 2)) {
320         area->prev= tmp_area->prev;
321         area->next= tmp_area;
322         tmp_area->prev= area;
323         if (area->prev)
324           area->prev->next= area;
325         else
326           largest= area;
327         break;
328       }
329     if (!tmp_area) {
330       area->prev= smallest;
331       area->next= (struct color_area *)NULL;
332       smallest->next= area;
333       smallest= area;
334     }
335   }
336   *rlargest= largest;
337   *rsmallest= smallest;
338 }
339
340 Image *
341 reduce(Image *image, unsigned int n, unsigned int verbose)
342 { unsigned long pixel_counts[32768]; /* pixel occurrance histogram */
343   unsigned short pixel_array[32768];
344   unsigned long count, midpoint;
345   int x, y, num_pixels, allocated, depth;
346   byte *pixel, *dpixel;
347   struct color_area *areas, *largest_area, *smallest_area;
348   struct color_area *new_area, *old_area;
349   Image *new_image;
350   char buf[BUFSIZ];
351
352   goodImage(image, "reduce");
353   if (n > 32768) /* max # of colors we can handle */
354     n= 32768;
355
356   /* create a histogram of particular pixel occurrances
357    */
358
359   memset(pixel_counts, 0, 32768 * sizeof(unsigned long));
360   switch (image->type) {
361   case IBITMAP:
362       return(image);
363
364   case IRGB:
365     if (image->rgb.used <= n)
366       return(image); /* xxx kazu right? */
367     if (verbose) {
368       fprintf(stderr, "  Reducing RGB image color usage to %d colors...", n);
369       fflush(stderr);
370     }
371     pixel= image->data;
372     for (y= 0; y < image->height; y++)
373       for (x= 0; x < image->width; x++) {
374         pixel_counts[TLA_TO_15BIT(image->rgb,
375                                   memToVal(pixel, image->pixlen))]++;
376         pixel += image->pixlen;
377       }
378     break;
379
380   case ITRUE:
381     if (image->pixlen != 3) {
382       fprintf(stderr, "reduce: true color image has strange pixel length?\n");
383       return(image);
384     }
385     if (verbose) {
386       fprintf(stderr, "  Converting true color image to RGB image with %d colors...",
387              n);
388       fflush(stderr);
389     }
390
391     pixel= image->data;
392     for (y= 0; y < image->height; y++)
393       for (x= 0; x < image->width; x++) {
394         pixel_counts[TRUE_TO_15BIT(memToVal(pixel, 3))]++;
395         pixel += 3;
396       }
397     break;
398
399   default:
400       return(image); /* not something we can reduce, thank you anyway */
401   }
402
403   /* create array of 15-bit pixel values that actually occur in the image
404    */
405
406   num_pixels= 0;
407   for (x= 0; x < 32768; x++)
408     if (pixel_counts[x] > 0)
409       pixel_array[num_pixels++]= (short)x;
410   if (verbose) {
411     fprintf(stderr, "image uses %d colors...", num_pixels);
412     fflush(stderr);
413   }
414
415   /* create color area array and initialize first element
416    */
417
418   areas= (struct color_area *)lmalloc(n * sizeof(struct color_area));
419   areas[0].pixels= pixel_array;
420   areas[0].num_pixels= num_pixels;
421   largest_area= smallest_area= (struct color_area *)NULL;
422   insertColorArea(pixel_counts, &largest_area, &smallest_area, areas);
423   allocated= 1;
424
425   /* keep splitting the color area until we have as many color areas as we
426    * need
427    */
428
429   while (allocated < n) {
430
431     /* if our largest area can't be broken down, we can't even get the
432      * number of colors they asked us to
433      */
434
435     if (largest_area->num_pixels < 2)
436       break;
437
438     /* find midpoint of largest area and do split
439      */
440
441     qsort(largest_area->pixels, largest_area->num_pixels, sizeof(short),
442           largest_area->sort_func);
443     count= 0;
444     midpoint= largest_area->pixel_count / 2;
445     for (x= 0; x < largest_area->num_pixels; x++) {
446       count += pixel_counts[largest_area->pixels[x]];
447       if (count > midpoint)
448         break;
449     }
450     if (x == 0) /* degenerate case; divide in half */
451       x= 1;
452     new_area= areas + allocated;
453     new_area->pixels= largest_area->pixels + x;
454     new_area->num_pixels= largest_area->num_pixels - x;
455     largest_area->num_pixels= x;
456     old_area= largest_area;
457     largest_area= largest_area->next;
458     if (largest_area)
459       largest_area->prev= (struct color_area *)NULL;
460     else
461       smallest_area= (struct color_area *)NULL;
462
463     /* recalculate for each area of split and insert in the area list
464      */
465
466     insertColorArea(pixel_counts, &largest_area, &smallest_area, old_area);
467     insertColorArea(pixel_counts, &largest_area, &smallest_area, new_area);
468
469     allocated++;
470   }
471
472   /* get destination image
473    */
474
475   depth= colorsToDepth(n);
476   new_image= newRGBImage(image->width, image->height, depth);
477   if (image->title) {
478     sprintf(buf, "%s (%d colors)", image->title, n);
479     new_image->title= dupString(buf);
480   }
481
482   /* calculate RGB table from each color area.  this should really calculate
483    * a new color by weighting the intensities by the number of pixels, but
484    * it's a pain to scale so this just averages all the intensities.  it
485    * works pretty well regardless.
486    */
487
488   for (x= 0; x < allocated; x++) {
489     long red, green, blue, pixel2;
490
491     red= green= blue= 0;
492     for (y= 0; y < areas[x].num_pixels; y++) {
493       pixel2= areas[x].pixels[y];
494       red += RED_INTENSITY(pixel2);
495       green += GREEN_INTENSITY(pixel2);
496       blue += BLUE_INTENSITY(pixel2);
497       pixel_counts[pixel2]= x;
498     }
499     red /= areas[x].num_pixels;
500     green /= areas[x].num_pixels;
501     blue /= areas[x].num_pixels;
502     new_image->rgb.red[x]= (unsigned short)(red << 11);
503     new_image->rgb.green[x]= (unsigned short)(green << 11);
504     new_image->rgb.blue[x]= (unsigned short)(blue << 11);
505   };
506   new_image->rgb.used= allocated;
507   new_image->rgb.compressed= 1;
508
509   lfree(areas);
510
511   /* copy old image into new image
512    */
513
514   pixel= image->data;
515   dpixel= new_image->data;
516
517   switch(image->type) {
518   case IRGB:
519     for (y= 0; y < image->height; y++)
520       for (x= 0; x < image->width; x++) {
521         valToMem(pixel_counts[TLA_TO_15BIT(image->rgb,
522                                            memToVal(pixel, image->pixlen))],
523                  dpixel, new_image->pixlen);
524         pixel += image->pixlen;
525         dpixel += new_image->pixlen;
526       }
527     if (image->trans >= 0)
528       new_image->trans = pixel_counts[TLA_TO_15BIT(image->rgb, image->trans)];
529     break;
530
531   case ITRUE:
532     for (y= 0; y < image->height; y++)
533       for (x= 0; x < image->width; x++) {
534         valToMem(pixel_counts[TRUE_TO_15BIT(memToVal(pixel, 3))],
535                  dpixel, new_image->pixlen);
536         pixel += 3;
537         dpixel += new_image->pixlen;
538       }
539     if (image->trans >= 0)
540       new_image->trans = pixel_counts[TRUE_TO_15BIT(image->trans)];
541     break;
542   }
543   if (verbose)
544     fprintf(stderr, "done\n");
545   return(new_image);
546 }
547
548 /* expand an image into a true color image
549  */
550
551 Image *
552 expand(Image *image)
553 {
554   Image *new_image;
555   int x, y;
556   Pixel spixval, dpixval;
557   byte *spixel, *dpixel, *line;
558   unsigned int linelen;
559   byte mask;
560
561   goodImage(image, "expand");
562   if TRUEP(image)
563     return(image);
564
565   new_image= newTrueImage(image->width, image->height);
566   new_image->title= dupString(image->title);
567
568   switch (image->type) {
569   case IBITMAP:
570     line= image->data;
571     dpixel= new_image->data;
572     linelen= (image->width / 8) + (image->width % 8 ? 1 : 0);
573     spixval = RGB_TO_TRUE(image->rgb.red[0],
574                           image->rgb.green[0],
575                           image->rgb.blue[0]);
576     dpixval = RGB_TO_TRUE(image->rgb.red[1],
577                           image->rgb.green[1],
578                           image->rgb.blue[1]);
579     for (y= 0; y < image->height; y++) {
580       spixel= line;
581       mask= 0x80;
582       for (x= 0; x < image->width; x++) {
583         valToMem((mask & *spixel ? dpixval : spixval), dpixel, 3);
584         mask >>= 1;
585         if (!mask) {
586           mask= 0x80;
587           spixel++;
588         }
589         dpixel += new_image->pixlen;
590       }
591       line += linelen;
592     }
593     if (image->trans >= 0)
594       new_image->trans = image->trans ? dpixval : spixval;
595     break;
596   case IRGB:
597          spixel= image->data;
598          dpixel= new_image->data;
599     for (y= 0; y < image->height; y++)
600       for (x= 0; x < image->width; x++) {
601         spixval= memToVal(spixel, image->pixlen);
602         valToMem(RGB_TO_TRUE(image->rgb.red[spixval],
603                              image->rgb.green[spixval],
604                              image->rgb.blue[spixval]),
605                  dpixel, new_image->pixlen);
606         spixel += image->pixlen;
607         dpixel += new_image->pixlen;
608       }
609     if (image->trans >= 0)
610       new_image->trans = RGB_TO_TRUE(image->rgb.red[image->trans],
611                                      image->rgb.green[image->trans],
612                                      image->rgb.blue[image->trans]);
613     break;
614   }
615   return(new_image);
616 }