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