home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / vg-2.03 / quant.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-03  |  5.7 KB  |  323 lines
  1. /*
  2.  * Copyright (C) 1990-1992 Michael Davidson.
  3.  * All rights reserved.
  4.  *
  5.  * Permission to use, copy, modify, and distribute this software
  6.  * and its documentation for any purpose and without fee is hereby
  7.  * granted, provided that the above copyright notice appear in all
  8.  * copies and that both that copyright notice and this permission
  9.  * notice appear in supporting documentation.
  10.  *
  11.  * This software is provided "as is" without express or implied warranty.
  12.  */
  13.  
  14. #include    <stdio.h>
  15.  
  16. #ifndef    STATIC
  17. #define    STATIC    static
  18. #endif
  19.  
  20. /*
  21.  * median cut color quantization
  22.  */
  23.  
  24. #define    BITS_PER_RGB    5
  25. #define    MAX_PIXVAL    ((1 << BITS_PER_RGB) - 1)
  26. #define    MAX_COLORS    (1 << 15)
  27.  
  28. #define    RED_SHIFT    10
  29. #define    GREEN_SHIFT    5
  30. #define    BLUE_SHIFT    0
  31. #define    COLOR_MASK    0x1f
  32.  
  33. #define    RED(p)            ( ((p) >> RED_SHIFT)   & COLOR_MASK )
  34. #define    GREEN(p)        ( ((p) >> GREEN_SHIFT) & COLOR_MASK )
  35. #define    BLUE(p)            ( ((p) >> BLUE_SHIFT)  & COLOR_MASK )
  36.  
  37. #define    RED_SORT(p, n)        color_sort(p, n, RED_SHIFT)
  38. #define    GREEN_SORT(p, n)    color_sort(p, n, GREEN_SHIFT)
  39. #define    BLUE_SORT(p, n)        color_sort(p, n, BLUE_SHIFT)
  40.  
  41. extern void    *alloca(int);
  42.  
  43. typedef struct color
  44. {
  45.     unsigned char red;
  46.     unsigned char green;
  47.     unsigned char blue;
  48. } color_t;
  49.  
  50. struct box
  51. {
  52.     int index;
  53.     int colors;
  54.     int sum;
  55. };
  56.  
  57. STATIC void    sort_box();
  58. STATIC void    split_box();
  59. STATIC void    average_box();
  60. STATIC void    color_sort();
  61.  
  62. void
  63. quantize(
  64.     unsigned long    *histogram,
  65.     color_t        *colormap,
  66.     unsigned char    *lookup,
  67.     int            newcolors
  68.     )
  69. {
  70.     unsigned        colors;
  71.     unsigned        sum;
  72.     unsigned short    *color_vec;
  73.     unsigned short    *cp;
  74.     struct box        box[256];
  75.     int            boxes;
  76.     int            i, j;
  77.  
  78.     /*
  79.      * count the total number of colors
  80.      */
  81.     colors    = 0;
  82.     sum        = 0;
  83.  
  84.     for (i = 0; i < MAX_COLORS; i++)
  85.     {
  86.     if (histogram[i] != 0)
  87.     {
  88.         sum += histogram[i];
  89.         colors++;
  90.     }
  91.     }
  92.  
  93.     /*
  94.      * build a table of all the colors that were found
  95.      */
  96.     color_vec    = alloca(colors * sizeof(color_vec[0]));
  97.     cp        = color_vec;
  98.  
  99.     for (i = 0; i < MAX_COLORS; i++)
  100.     {
  101.     if (histogram[i] != 0)
  102.         *cp++ = i;
  103.     }
  104.  
  105.     /*
  106.      * put all of the colors in the first box
  107.      */
  108.     box[0].index    = 0;
  109.     box[0].colors    = colors;
  110.     box[0].sum        = sum;
  111.     boxes        = 1;
  112.  
  113.     /*
  114.      * split the boxes until we have the desired number of colors
  115.      */
  116.  
  117.     while (boxes < newcolors)
  118.     {
  119.     /*
  120.      * Find the first splittable box.
  121.      */
  122.     for (i = 0, j = 0; i < boxes; i++ )
  123.         if (box[i].colors > box[j].colors)
  124.         j = i;
  125.  
  126.     if (box[j].colors <= 1)
  127.         break;
  128.     /*
  129.      * sort the box
  130.      */
  131.     sort_box(&box[j], color_vec);
  132.  
  133.     split_box(&box[j], &box[boxes++], color_vec, histogram);
  134.     }
  135.  
  136.     for (i = 0; i < boxes; i++)
  137.     {
  138.     int j;
  139.     int index    = box[i].index;
  140.     int colors    = box[i].colors;
  141.  
  142.     average_box(&box[i], color_vec, histogram, &colormap[i]);
  143.  
  144.     for (j = 0; j < colors; j++)
  145.         lookup[color_vec[index + j]] = (unsigned char) i;
  146.     }
  147.  
  148. }
  149.  
  150. STATIC void
  151. sort_box(
  152.     struct box        *bp,
  153.     unsigned short    *cv
  154.     )
  155. {
  156.     unsigned    maxr, minr;
  157.     unsigned    maxg, ming;
  158.     unsigned    maxb, minb;
  159.     int        i;
  160.     int        n;
  161.  
  162.     /*
  163.      * find the range of rgb components in this box
  164.      */
  165.     minr =
  166.     ming =
  167.     minb = MAX_PIXVAL;
  168.  
  169.     maxr =
  170.     maxg =
  171.     maxb = 0;
  172.  
  173.     for (i = bp->index, n = bp->colors; --n >= 0; i++)
  174.     {
  175.     register unsigned     color;
  176.     register unsigned    v;
  177.  
  178.     color = cv[i];
  179.  
  180.     v = RED(color);
  181.     if ( v < minr ) minr = v;
  182.     if ( v > maxr ) maxr = v;
  183.     v = GREEN(color);
  184.     if ( v < ming ) ming = v;
  185.     if ( v > maxg ) maxg = v;
  186.     v = BLUE(color);
  187.     if ( v < minb ) minb = v;
  188.     if ( v > maxb ) maxb = v;
  189.     }
  190.  
  191.     /*
  192.      * now choose which color to sort by
  193.      */
  194.  
  195.      maxr = (maxr - minr) * 77;
  196.      maxg = (maxg - ming) * 150;
  197.      maxb = (maxb - minb) * 29;
  198.  
  199.     if (maxr >= maxg && maxr >= maxb)
  200.     RED_SORT(&cv[bp->index], bp->colors);
  201.     else if (maxg >= maxb)
  202.     GREEN_SORT(&cv[bp->index], bp->colors);
  203.     else
  204.     BLUE_SORT(&cv[bp->index], bp->colors);
  205. }
  206.  
  207. STATIC void
  208. split_box(
  209.     struct box        *bp,
  210.     struct box        *np,
  211.     unsigned short    *cv,
  212.     unsigned long    *hist
  213.     )
  214. {
  215.     int        i;
  216.     int        idx;
  217.     int        median;
  218.     int        sum;
  219.  
  220.     median    = bp->sum / 2;
  221.  
  222.     idx    = bp->index;
  223.     sum = hist[cv[idx++]];
  224.  
  225.     for (i = 1; i < bp->colors - 1; i++)
  226.     {
  227.     if (sum >= median)
  228.         break;
  229.  
  230.     sum += hist[cv[idx++]];
  231.     }
  232.  
  233.  
  234.  
  235.     *np        = *bp;
  236.  
  237.     np->index    += i;
  238.     np->colors    -= i;
  239.     np->sum    -= sum;
  240.  
  241.     bp->colors    = i;
  242.     bp->sum    = sum;
  243. }
  244.  
  245. STATIC void
  246. average_box(
  247.     struct box        *bp,
  248.     unsigned short    *cv,
  249.     unsigned long    *hist,
  250.     color_t        *cmap
  251.     )
  252. {
  253.  
  254.     int        index = bp->index;
  255.     int        colors= bp->colors;
  256.  
  257.     long r = 0, g = 0, b = 0, sum = 0;
  258.     register int i;
  259.  
  260.     if (colors == 0)
  261.     return;
  262.  
  263.     for (i = 0; i < colors; i++)
  264.     {
  265.     unsigned long value;
  266.     register unsigned  color;
  267.  
  268.     color = cv[index + i];
  269.     value = hist[color];
  270.     r += RED(color) * value;
  271.     g += GREEN(color) * value;
  272.     b += BLUE(color) * value;
  273.     sum += value;
  274.     }
  275.  
  276.     r *= 8;
  277.     r = r / sum;
  278.     if ( r > 255 ) r = 255;
  279.     g *= 8;
  280.     g = g / sum;
  281.     if ( g > 255 ) g = 255;
  282.     b *= 8;
  283.     b = b / sum;
  284.     if ( b > 255 ) b = 255;
  285.  
  286.     cmap->red    = (unsigned char) r;
  287.     cmap->green    = (unsigned char) g;
  288.     cmap->blue    = (unsigned char) b;
  289. }
  290.  
  291.  
  292. STATIC void
  293. color_sort(
  294.     register unsigned short    *p,
  295.     int            n,
  296.     register int    shift
  297.     )
  298. {
  299.     unsigned long    count[MAX_PIXVAL+1];
  300.     unsigned short    *temp_vec;
  301.     register int    i;
  302.  
  303. #define    COLOR(p)    (((p) >> shift) & COLOR_MASK)
  304.  
  305.     temp_vec    = alloca(n * sizeof(temp_vec[0]));
  306.  
  307.     for (i = 0; i <= MAX_PIXVAL; i++)
  308.     count[i] = 0;
  309.  
  310.     for (i = 0; i < n; i++)
  311.     count[COLOR(p[i])] ++;
  312.  
  313.     for (i = 1; i <= MAX_PIXVAL; i++)
  314.     count[i] += count[i-1];
  315.  
  316.     for (i = n; --i >= 0; )
  317.     temp_vec[--count[COLOR(p[i])]] = p[i];
  318.  
  319.     for (i = 0; i < n; i++)
  320.     p[i] = temp_vec[i];
  321. }
  322.  
  323.