home *** CD-ROM | disk | FTP | other *** search
/ vsiftp.vmssoftware.com / VSIPUBLIC@vsiftp.vmssoftware.com.tar / FREEWARE / FREEWARE40.ZIP / xpaint-244 / src / imagecomp.c < prev    next >
Text File  |  1996-06-02  |  16KB  |  566 lines
  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.5 1996/06/02 08:38:35 torsten 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. /*
  175.  * this does calculations on a color area following a split and inserts
  176.  * the color area in the list of color areas.
  177.  */
  178.  
  179. static void 
  180. insertColorArea(unsigned long *counts,
  181.         Area_t ** rlargest, Area_t ** rsmallest, Area_t * area)
  182. {
  183.     int i;
  184.     unsigned int red, green, blue;
  185.     unsigned int min_red, min_green, min_blue;
  186.     unsigned int max_red, max_green, max_blue = 0;
  187.     Area_t *largest, *smallest;
  188.  
  189.     /*
  190.     ** update pixel count for this area and find RGB intensity widths
  191.      */
  192.     min_red = max_red = RED_INTENSITY(area->pixels[0]);
  193.     min_green = max_green = GREEN_INTENSITY(area->pixels[0]);
  194.     min_blue = max_blue = BLUE_INTENSITY(area->pixels[0]);
  195.  
  196.     area->count = 0;
  197.     for (i = 1; i < area->npixels; i++) {
  198.     area->count += counts[area->pixels[i]];
  199.     red = RED_INTENSITY(area->pixels[i]);
  200.     green = GREEN_INTENSITY(area->pixels[i]);
  201.     blue = BLUE_INTENSITY(area->pixels[i]);
  202.  
  203.     if (red < min_red)
  204.         min_red = red;
  205.     if (red > max_red)
  206.         max_red = red;
  207.     if (green < min_green)
  208.         min_green = green;
  209.     if (green > max_green)
  210.         max_green = green;
  211.     if (blue < min_blue)
  212.         min_blue = blue;
  213.     if (blue > max_blue)
  214.         max_blue = blue;
  215.     }
  216.  
  217.     /*
  218.     ** calculate widths and determine which predicate function to use based
  219.     ** on the result
  220.      */
  221.  
  222.     red = max_red - min_red;
  223.     green = max_green - min_green;
  224.     blue = max_blue - min_blue;
  225.  
  226.     if (red > green)
  227.     if (green > blue)
  228.         area->func = sortRGB;
  229.     else if (red > blue)
  230.         area->func = sortRBG;
  231.     else
  232.         area->func = sortBRG;
  233.     else if (green > blue)
  234.     if (red > blue)
  235.         area->func = sortGRB;
  236.     else
  237.         area->func = sortGBR;
  238.     else
  239.     area->func = sortBGR;
  240.  
  241.     /*
  242.      * insert color area in color area list sorted by number of pixels that
  243.      * the area represents
  244.      */
  245.  
  246.     largest = *rlargest;
  247.     smallest = *rsmallest;
  248.  
  249.     if (largest == NULL) {
  250.     largest = smallest = area;
  251.     area->prev = area->next = (Area_t *) NULL;
  252.     } else if (area->npixels < 2) {
  253.     /*
  254.     **  if we only have one element, our pixel count is immaterial so we get
  255.     **  stuck on the end of the list.
  256.      */
  257.     smallest->next = area;
  258.     area->prev = smallest;
  259.     area->next = (Area_t *) NULL;
  260.     smallest = area;
  261.     } else {
  262.     /*
  263.     **  insert node into list
  264.      */
  265.     Area_t *cur;
  266.  
  267.     for (cur = largest; cur != NULL; cur = cur->next) {
  268.         if ((area->count > cur->count) || (cur->npixels < 2)) {
  269.         area->prev = cur->prev;
  270.         area->next = cur;
  271.         cur->prev = area;
  272.         if (area->prev != NULL)
  273.             area->prev->next = area;
  274.         else
  275.             largest = area;
  276.         break;
  277.         }
  278.     }
  279.     if (cur == NULL) {
  280.         area->prev = smallest;
  281.         area->next = (Area_t *) NULL;
  282.         smallest->next = area;
  283.         smallest = area;
  284.     }
  285.     }
  286.     *rlargest = largest;
  287.     *rsmallest = smallest;
  288. }
  289.  
  290. /*
  291. **  hash table support functions.
  292.  */
  293. static int 
  294. cmpColor(void *a, void *b)
  295. {
  296.     color_t *ca = (color_t *) a;
  297.     color_t *cb = (color_t *) b;
  298.  
  299.     if (ca->r != cb->r)
  300.     return ca->r < cb->r ? -1 : 1;
  301.     if (ca->g != cb->g)
  302.     return ca->g < cb->g ? -1 : 1;
  303.     if (ca->b != cb->b)
  304.     return ca->b < cb->b ? -1 : 1;
  305.     return 0;
  306. }
  307.  
  308. static void 
  309. freeColor(void *junk)
  310. {
  311.     /*
  312.     **    Don't apply a free function to the hashtable items.
  313.      */
  314. }
  315.  
  316. Image *
  317. ImageCompress(Image * input, int ncolors, int noforce)
  318. {
  319.     unsigned long counts[32768];
  320.     unsigned short array[XtNumber(counts)];
  321.     unsigned char *ocp;
  322.     unsigned short *osp;
  323.     int x, y, i, count, nuniq;
  324.     int allocated;
  325.     Area_t *areas, *largest, *smallest;
  326.     Image *output;
  327.     void *htable;
  328.     color_t *ctable;
  329.  
  330.     /*
  331.     **    make sure we have array space...
  332.      */
  333.     if (ncolors > XtNumber(counts))
  334.     ncolors = XtNumber(counts);
  335.  
  336.     /*
  337.     **    Why are we trying to compress a b&w image?
  338.     **      or an image that already fits
  339.      */
  340.     if (input->isBW)
  341.     return input;
  342.     if (input->cmapSize != 0 && input->cmapSize < ncolors)
  343.     return input;
  344.  
  345.     /*
  346.     **    Create a histogram of 15-bit color values.
  347.     **      also, save the "real" color values.
  348.     **      or at least enough of them so that we know
  349.     **      that compression is really necessary.
  350.      */
  351.     htable = HashCreate(cmpColor, freeColor, 256);
  352.     ctable = (color_t *) XtCalloc(sizeof(color_t), ncolors + 1);
  353.     nuniq = 0;
  354.  
  355.     /* GRR:  use memset() instead? */
  356.     for (i = 0; i < XtNumber(counts); i++)
  357.     counts[i] = 0;
  358.  
  359.     for (y = 0; y < input->height; y++) {
  360.     for (x = 0; x < input->width; x++) {
  361.         unsigned char *dp;
  362.  
  363.         dp = ImagePixel(input, x, y);
  364.  
  365.         if (nuniq <= ncolors && htable != NULL) {
  366.         color_t *cptr = &ctable[nuniq];
  367.         cptr->r = dp[0];
  368.         cptr->g = dp[1];
  369.         cptr->b = dp[2];
  370.         if (HashFind(htable, dp[0], cptr) == NULL) {
  371.             cptr->idx = nuniq;
  372.             HashAdd(htable, dp[0], cptr);
  373.             nuniq++;
  374.         }
  375.         }
  376.         counts[TO_15BITS(dp[0], dp[1], dp[2])]++;
  377.     }
  378.  
  379.     if (y % 256 == 0)
  380.         StateTimeStep();
  381.     }
  382.  
  383.     if (nuniq <= ncolors) {
  384.     /*
  385.     **  Wow, this has few enough colors to fit in the requested colormap.
  386.     **    This should be able to renumber (compress) an existing
  387.     **    colormap, rather than creating a new image.
  388.      */
  389.     unsigned short *osp;
  390.     unsigned char *ocp;
  391.  
  392.     output = ImageNewCmap(input->width, input->height, nuniq);
  393.     for (y = 0; y < nuniq; y++)
  394.         ImageSetCmap(output, y,
  395.              ctable[y].r, ctable[y].g, ctable[y].b);
  396.  
  397.     osp = (unsigned short *) output->data;
  398.     ocp = output->data;
  399.  
  400.     for (y = 0; y < input->height; y++) {
  401.         for (x = 0; x < input->width; x++, osp++, ocp++) {
  402.         unsigned char *dp;
  403.         color_t *cptr, col;
  404.  
  405.         dp = ImagePixel(input, x, y);
  406.  
  407.         col.r = dp[0];
  408.         col.g = dp[1];
  409.         col.b = dp[2];
  410.         cptr = HashFind(htable, dp[0], &col);
  411.  
  412.         if (nuniq > 256)
  413.             *osp = cptr->idx;
  414.         else
  415.             *ocp = cptr->idx;
  416.         }
  417.  
  418.         if (y % 256 == 0)
  419.         StateTimeStep();
  420.     }
  421.  
  422.     output->cmapPacked = True;
  423.  
  424.     HashDestroy(htable);
  425.     XtFree((XtPointer) ctable);
  426.     output->maskData = input->maskData;
  427.     input->maskData = NULL;
  428.     ImageDelete(input);
  429.     return output;
  430.     }
  431.     HashDestroy(htable);
  432.     XtFree((XtPointer) ctable);
  433.  
  434.     /* GRR 960525:  if not forcing compression to ncolors, return now */
  435.     if (noforce)
  436.         return NULL;
  437.  
  438.     /*
  439.     **    Create an array of 15-bit pixel values that actually occur 
  440.     **     in the image.
  441.      */
  442.     count = 0;
  443.     for (i = 0; i < XtNumber(counts); i++) {
  444.     if (counts[i] != 0)
  445.         array[count++] = i;
  446.     }
  447.  
  448.     /*
  449.     **    Create the color areas and initialize the first element
  450.      */
  451.     areas = (Area_t *) XtCalloc(sizeof(Area_t), ncolors);
  452.     areas[0].pixels = array;
  453.     areas[0].npixels = count;
  454.  
  455.     largest = smallest = NULL;
  456.     insertColorArea(counts, &largest, &smallest, areas);
  457.  
  458.     allocated = 1;
  459.  
  460.     /*
  461.     **    While there are areas still to be broken down 
  462.     **      or the largest cannot be subdivided.
  463.      */
  464.     while (allocated < ncolors && largest->npixels >= 2) {
  465.     Area_t *newArea, *oldArea;
  466.     int i, midpoint;
  467.  
  468.     qsort(largest->pixels, largest->npixels, sizeof(short),
  469.            (int (*)(_Xconst void *, _Xconst void *)) largest->func);
  470.  
  471.     /*
  472.     **  Find the midpoint of the largest area an split
  473.      */
  474.     midpoint = largest->count / 2;
  475.     for (i = 0, count = 0; i < largest->npixels && count < midpoint; i++)
  476.         count += counts[largest->pixels[i]];
  477.  
  478.     if (i == largest->npixels)
  479.         i--;
  480.     if (i == 0)
  481.         i = 1;
  482.     newArea = areas + allocated;
  483.     newArea->pixels = largest->pixels + i;
  484.     newArea->npixels = largest->npixels - i;
  485.     largest->npixels = i;
  486.     oldArea = largest;
  487.     largest = largest->next;
  488.     if (largest != NULL)
  489.         largest->prev = NULL;
  490.     else
  491.         smallest = NULL;
  492.  
  493.     /* 
  494.     **  recalculate for each area of split and insert in the area list
  495.      */
  496.     insertColorArea(counts, &largest, &smallest, newArea);
  497.     insertColorArea(counts, &largest, &smallest, oldArea);
  498.  
  499.     allocated++;
  500.  
  501.     if (allocated % 64 == 0)
  502.         StateTimeStep();
  503.     }
  504.  
  505.     output = ImageNewCmap(input->width, input->height, allocated);
  506.     output->maskData = input->maskData;
  507.     input->maskData = NULL;
  508.  
  509.     for (i = 0; i < allocated; i++) {
  510.     long red, green, blue;
  511.     int j;
  512.  
  513.     /* 
  514.     ** Calculate RGB table from each color area.  This should really calculate
  515.     ** a new color by weighting the intensities by the number of pixels, but
  516.     ** it's a pain to scale so this just averages all the intensities.  It
  517.     ** works pretty well regardless.
  518.      */
  519.     red = green = blue = 0;
  520.     for (j = 0; j < areas[i].npixels; j++) {
  521.         unsigned short pixel = areas[i].pixels[j];
  522.  
  523.         red += RED_VALUE(pixel) & 0xff;
  524.         green += GREEN_VALUE(pixel) & 0xff;
  525.         blue += BLUE_VALUE(pixel) & 0xff;
  526.  
  527.         counts[pixel] = i;
  528.     }
  529.     red /= areas[i].npixels;
  530.     green /= areas[i].npixels;
  531.     blue /= areas[i].npixels;
  532.  
  533.     ImageSetCmap(output, i, red, green, blue);
  534.     }
  535.  
  536.     /*
  537.     **    Done with the areas information.
  538.      */
  539.     XtFree((XtPointer) areas);
  540.  
  541.     /*
  542.     **    Copy input to output
  543.      */
  544.  
  545.     ocp = output->data;
  546.     osp = (unsigned short *) output->data;
  547.  
  548.     for (y = 0; y < input->height; y++) {
  549.     for (x = 0; x < input->width; x++) {
  550.         unsigned char *dp;
  551.  
  552.         dp = ImagePixel(input, x, y);
  553.  
  554.         if (output->cmapSize > 256) {
  555.         *osp++ = counts[TO_15BITS(dp[0], dp[1], dp[2])];
  556.         } else {
  557.         *ocp++ = counts[TO_15BITS(dp[0], dp[1], dp[2])];
  558.         }
  559.     }
  560.     }
  561.  
  562.     output->cmapPacked = True;
  563.     ImageDelete(input);
  564.     return output;
  565. }