home *** CD-ROM | disk | FTP | other *** search
/ Big Green CD 8 / BGCD_8_Dev.iso / NEXTSTEP / UNIX / Web / Utilities / wwwcount-2.3 / combine / quantize.c < prev    next >
Encoding:
Text File  |  1995-11-19  |  54.2 KB  |  1,595 lines
  1. /*
  2. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  3. %                                                                             %
  4. %                                                                             %
  5. %                                                                             %
  6. %           QQQ   U   U   AAA   N   N  TTTTT  IIIII   ZZZZZ  EEEEE            %
  7. %          Q   Q  U   U  A   A  NN  N    T      I        ZZ  E                %
  8. %          Q   Q  U   U  AAAAA  N N N    T      I      ZZZ   EEEEE            %
  9. %          Q  QQ  U   U  A   A  N  NN    T      I     ZZ     E                %
  10. %           QQQQ   UUU   A   A  N   N    T    IIIII   ZZZZZ  EEEEE            %
  11. %                                                                             %
  12. %                                                                             %
  13. %              Reduce the Number of Unique Colors in an Image                 %
  14. %                                                                             %
  15. %                                                                             %
  16. %                                                                             %
  17. %                           Software Design                                   %
  18. %                             John Cristy                                     %
  19. %                              July 1992                                      %
  20. %                                                                             %
  21. %  Copyright 1994 E. I. du Pont de Nemours and Company                        %
  22. %                                                                             %
  23. %  Permission to use, copy, modify, distribute, and sell this software and    %
  24. %  its documentation for any purpose is hereby granted without fee,           %
  25. %  provided that the above Copyright notice appear in all copies and that     %
  26. %  both that Copyright notice and this permission notice appear in            %
  27. %  supporting documentation, and that the name of E. I. du Pont de Nemours    %
  28. %  and Company not be used in advertising or publicity pertaining to          %
  29. %  distribution of the software without specific, written prior               %
  30. %  permission.  E. I. du Pont de Nemours and Company makes no representations %
  31. %  about the suitability of this software for any purpose.  It is provided    %
  32. %  "as is" without express or implied warranty.                               %
  33. %                                                                             %
  34. %  E. I. du Pont de Nemours and Company disclaims all warranties with regard  %
  35. %  to this software, including all implied warranties of merchantability      %
  36. %  and fitness, in no event shall E. I. du Pont de Nemours and Company be     %
  37. %  liable for any special, indirect or consequential damages or any           %
  38. %  damages whatsoever resulting from loss of use, data or profits, whether    %
  39. %  in an action of contract, negligence or other tortuous action, arising     %
  40. %  out of or in connection with the use or performance of this software.      %
  41. %                                                                             %
  42. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  43. %
  44. %  Realism in computer graphics typically requires using 24 bits/pixel to
  45. %  generate an image.  Yet many graphic display devices do not contain
  46. %  the amount of memory necessary to match the spatial and color
  47. %  resolution of the human eye.  The QUANTIZE program takes a 24 bit
  48. %  image and reduces the number of colors so it can be displayed on
  49. %  raster device with less bits per pixel.  In most instances, the
  50. %  quantized image closely resembles the original reference image.
  51. %
  52. %  A reduction of colors in an image is also desirable for image
  53. %  transmission and real-time animation.
  54. %
  55. %  Function Quantize takes a standard RGB or monochrome images and quantizes
  56. %  them down to some fixed number of colors.
  57. %
  58. %  For purposes of color allocation, an image is a set of n pixels, where
  59. %  each pixel is a point in RGB space.  RGB space is a 3-dimensional
  60. %  vector space, and each pixel, pi,  is defined by an ordered triple of
  61. %  red, green, and blue coordinates, (ri, gi, bi).
  62. %
  63. %  Each primary color component (red, green, or blue) represents an
  64. %  intensity which varies linearly from 0 to a maximum value, cmax, which
  65. %  corresponds to full saturation of that color.  Color allocation is
  66. %  defined over a domain consisting of the cube in RGB space with
  67. %  opposite vertices at (0,0,0) and (cmax,cmax,cmax).  QUANTIZE requires
  68. %  cmax = 255.
  69. %
  70. %  The algorithm maps this domain onto a tree in which each node
  71. %  represents a cube within that domain.  In the following discussion
  72. %  these cubes are defined by the coordinate of two opposite vertices:
  73. %  The vertex nearest the origin in RGB space and the vertex farthest
  74. %  from the origin.
  75. %
  76. %  The tree's root node represents the the entire domain, (0,0,0) through
  77. %  (cmax,cmax,cmax).  Each lower level in the tree is generated by
  78. %  subdividing one node's cube into eight smaller cubes of equal size.
  79. %  This corresponds to bisecting the parent cube with planes passing
  80. %  through the midpoints of each edge.
  81. %
  82. %  The basic algorithm operates in three phases: Classification,
  83. %  Reduction, and Assignment.  Classification builds a color
  84. %  description tree for the image.  Reduction collapses the tree until
  85. %  the number it represents, at most, the number of colors desired in the
  86. %  output image.  Assignment defines the output image's color map and
  87. %  sets each pixel's color by reclassification in the reduced tree.
  88. %
  89. %  Classification begins by initializing a color description tree of
  90. %  sufficient depth to represent each possible input color in a leaf.
  91. %  However, it is impractical to generate a fully-formed color
  92. %  description tree in the classification phase for realistic values of
  93. %  cmax.  If colors components in the input image are quantized to k-bit
  94. %  precision, so that cmax= 2k-1, the tree would need k levels below the
  95. %  root node to allow representing each possible input color in a leaf.
  96. %  This becomes prohibitive because the tree's total number of nodes is
  97. %  1 + sum(i=1,k,8k).
  98. %
  99. %  A complete tree would require 19,173,961 nodes for k = 8, cmax = 255.
  100. %  Therefore, to avoid building a fully populated tree, QUANTIZE: (1)
  101. %  Initializes data structures for nodes only as they are needed;  (2)
  102. %  Chooses a maximum depth for the tree as a function of the desired
  103. %  number of colors in the output image (currently log2(colormap size)).
  104. %
  105. %  For each pixel in the input image, classification scans downward from
  106. %  the root of the color description tree.  At each level of the tree it
  107. %  identifies the single node which represents a cube in RGB space
  108. %  containing the pixel's color.  It updates the following data for each
  109. %  such node:
  110. %
  111. %    n1 : Number of pixels whose color is contained in the RGB cube
  112. %    which this node represents;
  113. %
  114. %    n2 : Number of pixels whose color is not represented in a node at
  115. %    lower depth in the tree;  initially,  n2 = 0 for all nodes except
  116. %    leaves of the tree.
  117. %
  118. %    Sr, Sg, Sb : Sums of the red, green, and blue component values for
  119. %    all pixels not classified at a lower depth. The combination of
  120. %    these sums and n2  will ultimately characterize the mean color of a
  121. %    set of pixels represented by this node.
  122. %
  123. %  Reduction repeatedly prunes the tree until the number of nodes with
  124. %  n2 > 0 is less than or equal to the maximum number of colors allowed
  125. %  in the output image.  On any given iteration over the tree, it selects
  126. %  those nodes whose n1  count is minimal for pruning and merges their
  127. %  color statistics upward. It uses a pruning threshold, ns, to govern
  128. %  node selection as follows:
  129. %
  130. %    ns = 0
  131. %    while number of nodes with (n2 > 0) > required maximum number of colors
  132. %      prune all nodes such that n1 <= ns
  133. %      Set ns to minimum n1 in remaining nodes
  134. %
  135. %  When a node to be pruned has offspring, the pruning procedure invokes
  136. %  itself recursively in order to prune the tree from the leaves upward.
  137. %  n2,  Sr, Sg,  and  Sb in a node being pruned are always added to the
  138. %  corresponding data in that node's parent.  This retains the pruned
  139. %  node's color characteristics for later averaging.
  140. %
  141. %  For each node, n2 pixels exist for which that node represents the
  142. %  smallest volume in RGB space containing those pixel's colors.  When n2
  143. %  > 0 the node will uniquely define a color in the output image. At the
  144. %  beginning of reduction,  n2 = 0  for all nodes except a the leaves of
  145. %  the tree which represent colors present in the input image.
  146. %
  147. %  The other pixel count, n1, indicates the total number of colors
  148. %  within the cubic volume which the node represents.  This includes n1 -
  149. %  n2  pixels whose colors should be defined by nodes at a lower level in
  150. %  the tree.
  151. %
  152. %  Assignment generates the output image from the pruned tree.  The
  153. %  output image consists of two parts: (1)  A color map, which is an
  154. %  array of color descriptions (RGB triples) for each color present in
  155. %  the output image;  (2)  A pixel array, which represents each pixel as
  156. %  an index into the color map array.
  157. %
  158. %  First, the assignment phase makes one pass over the pruned color
  159. %  description tree to establish the image's color map.  For each node
  160. %  with n2  > 0, it divides Sr, Sg, and Sb by n2 .  This produces the
  161. %  mean color of all pixels that classify no lower than this node.  Each
  162. %  of these colors becomes an entry in the color map.
  163. %
  164. %  Finally,  the assignment phase reclassifies each pixel in the pruned
  165. %  tree to identify the deepest node containing the pixel's color.  The
  166. %  pixel's value in the pixel array becomes the index of this node's mean
  167. %  color in the color map.
  168. %
  169. %  For efficiency, QUANTIZE requires that the reference image be in a
  170. %  run-length encoded format.
  171. %
  172. %  With the permission of USC Information Sciences Institute, 4676 Admiralty
  173. %  Way, Marina del Rey, California  90292, this code was adapted from module
  174. %  ALCOLS written by Paul Raveling.
  175. %
  176. %  The names of ISI and USC are not used in advertising or publicity
  177. %  pertaining to distribution of the software without prior specific
  178. %  written permission from ISI.
  179. %
  180. %
  181. */
  182.  
  183. /*
  184.   Include declarations.
  185. */
  186. #include "combine.h"
  187. #include "defines.h"
  188.  
  189.  
  190. /*
  191.   Define declarations.
  192. */
  193. #define color_number  number_colors
  194. #define MaxNodes  266817
  195. #define MaxShift  8
  196. #define MaxTreeDepth  8  /* Log2(MaxRGB) */
  197. #define NodesInAList  2048
  198.  
  199. /*
  200.   Structures.
  201. */
  202. typedef struct _Node
  203. {
  204.   struct _Node
  205.     *parent,
  206.     *child[8];
  207.  
  208.   unsigned char
  209.     id,
  210.     level,
  211.     children,
  212.     mid_red,
  213.     mid_green,
  214.     mid_blue;
  215.  
  216.   unsigned long
  217.     number_colors,
  218.     number_unique,
  219.     total_red,
  220.     total_green,
  221.     total_blue;
  222. } Node;
  223.  
  224. typedef struct _Nodes
  225. {
  226.   Node
  227.     nodes[NodesInAList];
  228.  
  229.   struct _Nodes
  230.     *next;
  231. } Nodes;
  232.  
  233. typedef struct _Cube
  234. {
  235.   Node
  236.     *root;
  237.  
  238.   RGB
  239.     color,
  240.     *colormap;
  241.  
  242.   unsigned int
  243.     depth;
  244.  
  245.   unsigned long
  246.     colors,
  247.     pruning_threshold,
  248.     next_pruning_threshold,
  249.     distance,
  250.     squares[MaxRGB+MaxRGB+1];
  251.  
  252.   unsigned int
  253.     shift[MaxTreeDepth+1],
  254.     nodes,
  255.     free_nodes,
  256.     color_number;
  257.  
  258.   Node
  259.     *next_node;
  260.  
  261.   Nodes
  262.     *node_queue;
  263. } Cube;
  264.  
  265. /*
  266.   Global variables.
  267. */
  268. static Cube
  269.   cube;
  270.  
  271. /*
  272.   Forward declarations.
  273. */
  274. static Node
  275.   *InitializeNode _FD((unsigned int,unsigned int,Node *,unsigned int,
  276.     unsigned int,unsigned int));
  277.  
  278. static unsigned int
  279.   DitherImage _FD((Image *));
  280.  
  281. static void
  282.   ClosestColor _FD((Node *)),
  283.   MColormap _FD((Node *)),
  284.   PruneLevel _FD((Node *));
  285.  
  286. /*
  287. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  288. %                                                                             %
  289. %                                                                             %
  290. %                                                                             %
  291. %  A s s i g n m e n t                                                        %
  292. %                                                                             %
  293. %                                                                             %
  294. %                                                                             %
  295. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  296. %
  297. %  Procedure Assignment generates the output image from the pruned tree.  The
  298. %  output image consists of two parts: (1)  A color map, which is an
  299. %  array of color descriptions (RGB triples) for each color present in
  300. %  the output image;  (2)  A pixel array, which represents each pixel as
  301. %  an index into the color map array.
  302. %
  303. %  First, the assignment phase makes one pass over the pruned color
  304. %  description tree to establish the image's color map.  For each node
  305. %  with n2  > 0, it divides Sr, Sg, and Sb by n2 .  This produces the
  306. %  mean color of all pixels that classify no lower than this node.  Each
  307. %  of these colors becomes an entry in the color map.
  308. %
  309. %  Finally,  the assignment phase reclassifies each pixel in the pruned
  310. %  tree to identify the deepest node containing the pixel's color.  The
  311. %  pixel's value in the pixel array becomes the index of this node's mean
  312. %  color in the color map.
  313. %
  314. %  The format of the Assignment routine is:
  315. %
  316. %      Assignment(image,number_colors,dither,colorspace,optimal)
  317. %
  318. %  A description of each parameter follows.
  319. %
  320. %    o image: Specifies a pointer to an Image structure;  returned from
  321. %      ReadImage.
  322. %
  323. %    o number_colors: This integer value indicates the maximum number of
  324. %      colors in the quantized image or colormap.  Here we use this value
  325. %      to determine the depth of the color description tree.
  326. %
  327. %    o dither: Set this integer value to something other than zero to
  328. %      dither the quantized image.  The basic strategy of dithering is to
  329. %      trade intensity resolution for spatial resolution by averaging the
  330. %      intensities of several neighboring pixels.  Images which suffer
  331. %      from severe contouring when quantized can be improved with the
  332. %      technique of dithering.  Severe contouring generally occurs when
  333. %      quantizing to very few colors, or to a poorly-chosen colormap.
  334. %      Note, dithering is a computationally expensive process and will
  335. %      increase processing time significantly.
  336. %
  337. %    o colorspace: An unsigned integer value that indicates the colorspace.
  338. %
  339. %    o optimal: An unsigned integer value greater than zero indicates that
  340. %      the optimal representation of the reference image should be returned.
  341. %
  342. %
  343. */
  344. static void Assignment(image,number_colors,dither,colorspace,optimal)
  345. Image
  346.   *image;
  347.  
  348. unsigned int
  349.   number_colors,
  350.   dither,
  351.   colorspace,
  352.   optimal;
  353. {
  354.   register int
  355.     i;
  356.  
  357.   register Node
  358.     *node;
  359.  
  360.   register Runlength
  361.     *p;
  362.  
  363.   register unsigned int
  364.     id;
  365.  
  366.   /*
  367.     Allocate image colormap.
  368.   */
  369.   if (image->colormap != (RGB *) NULL)
  370.     (void) free((char *) image->colormap);
  371.   image->colormap=(RGB *)
  372.     malloc((unsigned int) cube.colors*sizeof(RGB));
  373.   if (image->colormap == (RGB *) NULL)
  374.     {
  375.       (void) fprintf (stderr,
  376.         "Unable to quantize image,Memory allocation failed\n");
  377.       exit(1);
  378.     }
  379.   if (image->signature != (char *) NULL)
  380.     (void) free((char *) image->signature);
  381.   image->signature=(char *) NULL;
  382.   cube.colormap=image->colormap;
  383.   cube.colors=0;
  384.   MColormap(cube.root);
  385.   if ((number_colors == 2)  && (colorspace == GRAYColorspace))
  386.     {
  387.       unsigned int
  388.         polarity;
  389.  
  390.       /*
  391.         Monochrome image.
  392.       */
  393.       polarity=Intensity(image->colormap[0]) > Intensity(image->colormap[1]);
  394.       image->colormap[polarity].red=0;
  395.       image->colormap[polarity].green=0;
  396.       image->colormap[polarity].blue=0;
  397.       image->colormap[!polarity].red=MaxRGB;
  398.       image->colormap[!polarity].green=MaxRGB;
  399.       image->colormap[!polarity].blue=MaxRGB;
  400.     }
  401.   image->alpha=False;
  402.   image->class=PseudoClass;
  403.   image->colors=(unsigned int) cube.colors;
  404.   /*
  405.     Create a reduced color image.  For the non-optimal case we trade
  406.     accuracy for speed improvements.
  407.   */
  408.   if (dither || !optimal)
  409.     dither=!DitherImage(image);
  410.   p=image->pixels;
  411.   if (!dither)
  412.     if (!optimal)
  413.       for (i=0; i < image->packets; i++)
  414.       {
  415.         /*
  416.           Identify the deepest node containing the pixel's color.
  417.         */
  418.         node=cube.root;
  419.         for ( ; ; )
  420.         {
  421.           id=(p->red > node->mid_red ? 1 : 0) |
  422.             (p->green > node->mid_green ? 1 : 0) << 1 |
  423.             (p->blue > node->mid_blue ? 1 : 0) << 2;
  424.           if ((node->children & (1 << id)) == 0)
  425.             break;
  426.           node=node->child[id];
  427.         }
  428.         p->index=(unsigned short) node->color_number;
  429.         p++;
  430.       }
  431.     else
  432.       for (i=0; i < image->packets; i++)
  433.       {
  434.         /*
  435.           Identify the deepest node containing the pixel's color.
  436.         */
  437.         node=cube.root;
  438.         for ( ; ; )
  439.         {
  440.           id=(p->red > node->mid_red ? 1 : 0) |
  441.             (p->green > node->mid_green ? 1 : 0) << 1 |
  442.            (p->blue > node->mid_blue ? 1 : 0) << 2;
  443.          if ((node->children & (1 << id)) == 0)
  444.            break;
  445.          node=node->child[id];
  446.        }
  447.        /*
  448.          Find closest color among siblings and their children.
  449.        */
  450.        cube.color.red=p->red;
  451.        cube.color.green=p->green;
  452.        cube.color.blue=p->blue;
  453.        cube.distance=(unsigned long) (~0);
  454.        ClosestColor(node->parent);
  455.        p->index=cube.color_number;
  456.        p++;
  457.      }
  458. }
  459.  
  460. /*
  461. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  462. %                                                                             %
  463. %                                                                             %
  464. %                                                                             %
  465. %  C l a s s i f i c a t i o n                                                %
  466. %                                                                             %
  467. %                                                                             %
  468. %                                                                             %
  469. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  470. %
  471. %  Procedure Classification begins by initializing a color description tree
  472. %  of sufficient depth to represent each possible input color in a leaf.
  473. %  However, it is impractical to generate a fully-formed color
  474. %  description tree in the classification phase for realistic values of
  475. %  cmax.  If colors components in the input image are quantized to k-bit
  476. %  precision, so that cmax= 2k-1, the tree would need k levels below the
  477. %  root node to allow representing each possible input color in a leaf.
  478. %  This becomes prohibitive because the tree's total number of nodes is
  479. %  1 + sum(i=1,k,8k).
  480. %
  481. %  A complete tree would require 19,173,961 nodes for k = 8, cmax = 255.
  482. %  Therefore, to avoid building a fully populated tree, QUANTIZE: (1)
  483. %  Initializes data structures for nodes only as they are needed;  (2)
  484. %  Chooses a maximum depth for the tree as a function of the desired
  485. %  number of colors in the output image (currently log2(colormap size)).
  486. %
  487. %  For each pixel in the input image, classification scans downward from
  488. %  the root of the color description tree.  At each level of the tree it
  489. %  identifies the single node which represents a cube in RGB space
  490. %  containing It updates the following data for each such node:
  491. %
  492. %    n1 : Number of pixels whose color is contained in the RGB cube
  493. %    which this node represents;
  494. %
  495. %    n2 : Number of pixels whose color is not represented in a node at
  496. %    lower depth in the tree;  initially,  n2 = 0 for all nodes except
  497. %    leaves of the tree.
  498. %
  499. %    Sr, Sg, Sb : Sums of the red, green, and blue component values for
  500. %    all pixels not classified at a lower depth. The combination of
  501. %    these sums and n2  will ultimately characterize the mean color of a
  502. %    set of pixels represented by this node.
  503. %
  504. %  The format of the Classification routine is:
  505. %
  506. %      Classification(image)
  507. %
  508. %  A description of each parameter follows.
  509. %
  510. %    o image: Specifies a pointer to an Image structure;  returned from
  511. %      ReadImage.
  512. %
  513. %
  514. */
  515. static void Classification(image)
  516. Image
  517.   *image;
  518. {
  519.   register int
  520.     i;
  521.  
  522.   register Node
  523.     *node;
  524.  
  525.   register Runlength
  526.     *p;
  527.  
  528.   register unsigned int
  529.     bisect,
  530.     count,
  531.     id,
  532.     level;
  533.  
  534.   p=image->pixels;
  535.   for (i=0; i < image->packets; i++)
  536.   {
  537.     if (cube.nodes > MaxNodes)
  538.       {
  539.         /*
  540.           Prune one level if the color tree is too large.
  541.         */
  542.         PruneLevel(cube.root);
  543.         cube.depth--;
  544.       }
  545.     /*
  546.       Start at the root and descend the color cube tree.
  547.     */
  548.     count=p->length+1;
  549.     node=cube.root;
  550.     for (level=1; level <= cube.depth; level++)
  551.     {
  552.       id=(p->red > node->mid_red ? 1 : 0) |
  553.         (p->green > node->mid_green ? 1 : 0) << 1 |
  554.         (p->blue > node->mid_blue ? 1 : 0) << 2;
  555.       if (node->child[id] == (Node *) NULL)
  556.         {
  557.           /*
  558.             Set colors of new node to contain pixel.
  559.           */
  560.           node->children|=1 << id;
  561.           bisect=(unsigned int) (1 << (MaxTreeDepth-level)) >> 1;
  562.           node->child[id]=InitializeNode(id,level,node,
  563.             node->mid_red+(id & 1 ? bisect : -bisect),
  564.             node->mid_green+(id & 2 ? bisect : -bisect),
  565.             node->mid_blue+(id & 4 ? bisect : -bisect));
  566.           if (node->child[id] == (Node *) NULL)
  567.             {
  568.               (void) fprintf (stderr,
  569.                 "Unable to quantize image,Memory allocation failed\n");
  570.               exit(1);
  571.             }
  572.           if (level == cube.depth)
  573.             cube.colors++;
  574.         }
  575.       /*
  576.         Record the number of colors represented by this node.  Shift by level
  577.         in the color description tree.
  578.       */
  579.       node=node->child[id];
  580.       node->number_colors+=count << cube.shift[level];
  581.     }
  582.     /*
  583.       Increment unique color count and sum RGB values for this leaf for later
  584.       derivation of the mean cube color.
  585.     */
  586.     node->number_unique+=count;
  587.     node->total_red+=p->red*count;
  588.     node->total_green+=p->green*count;
  589.     node->total_blue+=p->blue*count;
  590.     p++;
  591.   }
  592. }
  593.  
  594. /*
  595. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  596. %                                                                             %
  597. %                                                                             %
  598. %                                                                             %
  599. %  C l o s e s t C o l o r                                                    %
  600. %                                                                             %
  601. %                                                                             %
  602. %                                                                             %
  603. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  604. %
  605. %  Procedure ClosestColor traverses the color cube tree at a particular node
  606. %  and determines which colormap entry best represents the input color.
  607. %
  608. %  The format of the ClosestColor routine is:
  609. %
  610. %      ClosestColor(node)
  611. %
  612. %  A description of each parameter follows.
  613. %
  614. %    o node: The address of a structure of type Node which points to a
  615. %      node in the color cube tree that is to be pruned.
  616. %
  617. %
  618. */
  619. static void ClosestColor(node)
  620. register Node
  621.   *node;
  622. {
  623.   register unsigned int
  624.     id;
  625.  
  626.   /*
  627.     Traverse any children.
  628.   */
  629.   if (node->children != 0)
  630.     for (id=0; id < 8; id++)
  631.       if (node->children & (1 << id))
  632.         ClosestColor(node->child[id]);
  633.   if (node->number_unique != 0)
  634.     {
  635.       register RGB
  636.         *color;
  637.  
  638.       register unsigned int
  639.         blue_distance,
  640.         green_distance,
  641.         red_distance;
  642.  
  643.       register unsigned long
  644.         distance;
  645.  
  646.       /*
  647.         Determine if this color is "closest".
  648.       */
  649.       color=cube.colormap+node->color_number;
  650.       red_distance=(int) color->red-(int) cube.color.red+MaxRGB;
  651.       green_distance=(int) color->green-(int) cube.color.green+MaxRGB;
  652.       blue_distance=(int) color->blue-(int) cube.color.blue+MaxRGB;
  653.       distance=cube.squares[red_distance]+cube.squares[green_distance]+
  654.         cube.squares[blue_distance];
  655.       if (distance < cube.distance)
  656.         {
  657.           cube.distance=distance;
  658.           cube.color_number=(unsigned short) node->color_number;
  659.         }
  660.     }
  661. }
  662.  
  663. /*
  664. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  665. %                                                                             %
  666. %                                                                             %
  667. %                                                                             %
  668. %  C o l o r m a p                                                            %
  669. %                                                                             %
  670. %                                                                             %
  671. %                                                                             %
  672. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  673. %
  674. %  Procedure Colormap traverses the color cube tree and notes each colormap
  675. %  entry.  A colormap entry is any node in the color cube tree where the
  676. %  number of unique colors is not zero.
  677. %
  678. %  The format of the Colormap routine is:
  679. %
  680. %      MColormap(node)
  681. %
  682. %  A description of each parameter follows.
  683. %
  684. %    o node: The address of a structure of type Node which points to a
  685. %      node in the color cube tree that is to be pruned.
  686. %
  687. %
  688. */
  689. static void MColormap(node)
  690. register Node
  691.   *node;
  692. {
  693.   register unsigned int
  694.     id;
  695.  
  696.   /*
  697.     Traverse any children.
  698.   */
  699.   if (node->children != 0)
  700.     for (id=0; id < 8; id++)
  701.       if (node->children & (1 << id))
  702.         MColormap(node->child[id]);
  703.   if (node->number_unique != 0)
  704.     {
  705.       /*
  706.         Colormap entry is defined by the mean color in this cube.
  707.       */
  708.       cube.colormap[cube.colors].red=(unsigned char)
  709.         ((node->total_red+(node->number_unique >> 1))/node->number_unique);
  710.       cube.colormap[cube.colors].green=(unsigned char)
  711.         ((node->total_green+(node->number_unique >> 1))/node->number_unique);
  712.       cube.colormap[cube.colors].blue=(unsigned char)
  713.         ((node->total_blue+(node->number_unique >> 1))/node->number_unique);
  714.       node->color_number=cube.colors++;
  715.     }
  716. }
  717.  
  718. /*
  719. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  720. %                                                                             %
  721. %                                                                             %
  722. %                                                                             %
  723. %  D i t h e r I m a g e                                                      %
  724. %                                                                             %
  725. %                                                                             %
  726. %                                                                             %
  727. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  728. %
  729. %  Procedure DitherImage uses the Floyd-Steinberg algorithm to dither the
  730. %  image.  Refer to "An Adaptive Algorithm for Spatial GreySscale", Robert W.
  731. %  Floyd and Louis Steinberg, Proceedings of the S.I.D., Volume 17(2), 1976.
  732. %
  733. %  First find the closest representation to the reference pixel color in the
  734. %  colormap, the node pixel is assigned this color.  Next, the colormap color
  735. %  is subtracted from the reference pixels color, this represents the
  736. %  quantization error.  Various amounts of this error are added to the pixels
  737. %  ahead and below the node pixel to correct for this error.  The error
  738. %  proportions are:
  739. %
  740. %            P     7/16
  741. %      3/16  5/16  1/16
  742. %
  743. %  The error is distributed left-to-right for even scanlines and right-to-left
  744. %  for odd scanlines.
  745. %
  746. %  The format of the DitherImage routine is:
  747. %
  748. %      DitherImage(image)
  749. %
  750. %  A description of each parameter follows.
  751. %
  752. %    o image: Specifies a pointer to an Image structure;  returned from
  753. %      ReadImage.
  754. %
  755. %
  756. */
  757. static unsigned int DitherImage(image)
  758. Image
  759.   *image;
  760. {
  761.   typedef struct _ErrorPacket
  762.   {
  763.     int
  764.       red,
  765.       green,
  766.       blue;
  767.   } ErrorPacket;
  768.  
  769.   ErrorPacket
  770.     *error;
  771.  
  772.   int
  773.     *cache,
  774.     step;
  775.  
  776.   Node
  777.     *node;
  778.  
  779.   register int
  780.     i,
  781.     blue_error,
  782.     green_error,
  783.     red_error;
  784.  
  785.   register Runlength
  786.     *q;
  787.  
  788.   register ErrorPacket
  789.     *cs,
  790.     *ns;
  791.  
  792.   register unsigned char
  793.     *range_limit;
  794.  
  795.   unsigned char
  796.     blue,
  797.     green,
  798.     *range_table,
  799.     red;
  800.  
  801.   unsigned int
  802.     id,
  803.     x,
  804.     y;
  805.  
  806.   unsigned short
  807.     index;
  808.  
  809.   /*
  810.     Image must be uncompressed.
  811.   */
  812.   if (!UncompressImage(image))
  813.     return(True);
  814.   /*
  815.     Allocate memory.
  816.   */
  817.   cache=(int *) malloc((1 << 18)*sizeof(int));
  818.   error=(ErrorPacket *) malloc(((image->columns+2) << 1)*sizeof(ErrorPacket));
  819.   range_table=(unsigned char *) malloc(3*(MaxRGB+1)*sizeof(unsigned char));
  820.   if ((cache == (int *) NULL) || (error == (ErrorPacket *) NULL) ||
  821.       (range_table == (unsigned char *) NULL))
  822.     {
  823.       (void) fprintf (stderr,
  824.         "Unable to dither image,Memory allocation failed\n");
  825.       return(True);
  826.     }
  827.   /*
  828.     Initialize color cache.
  829.   */
  830.   for (i=0; i < (1 << 18); i++)
  831.     cache[i]=(-1);
  832.   /*
  833.     Initialize error tables.
  834.   */
  835.   for (i=0; i < ((image->columns+2) << 1); i++)
  836.   {
  837.     error[i].red=0;
  838.     error[i].green=0;
  839.     error[i].blue=0;
  840.   }
  841.   /*
  842.     Initialize range tables.
  843.   */
  844.   for (i=0; i <= MaxRGB; i++)
  845.   {
  846.     range_table[i]=0;
  847.     range_table[i+(MaxRGB+1)]=(unsigned char) i;
  848.     range_table[i+(MaxRGB+1)*2]=MaxRGB;
  849.   }
  850.   range_limit=range_table+(MaxRGB+1);
  851.   /*
  852.     Dither image.
  853.   */
  854.   for (y=0; y < image->rows; y++)
  855.   {
  856.     q=image->pixels+image->columns*y;
  857.     cs=error+1;
  858.     ns=cs+(image->columns+2);
  859.     step=y & 0x01 ? 1 : -1;
  860.     if (step < 0)
  861.       {
  862.         /*
  863.           Distribute error right-to-left for odd scanlines.
  864.         */
  865.         q+=(image->columns-1);
  866.         ns=error+(image->columns-1)+1;
  867.         cs=ns+(image->columns+2);
  868.       }
  869.     for (x=0; x < image->columns; x++)
  870.     {
  871.       red_error=(cs->red+8)/16;
  872.       green_error=(cs->green+8)/16;
  873.       blue_error=(cs->blue+8)/16;
  874.       red=range_limit[(int) q->red+red_error];
  875.       green=range_limit[(int) q->green+green_error];
  876.       blue=range_limit[(int) q->blue+blue_error];
  877.       i=(red >> 2) << 12 | (green >> 2) << 6 | blue >> 2;
  878.       if (cache[i] < 0)
  879.         {
  880.           /*
  881.             Identify the deepest node containing the pixel's color.
  882.           */
  883.           node=cube.root;
  884.           for ( ; ; )
  885.           {
  886.             id=(red > node->mid_red ? 1 : 0) |
  887.               (green > node->mid_green ? 1 : 0) << 1 |
  888.               (blue > node->mid_blue ? 1 : 0) << 2;
  889.             if ((node->children & (1 << id)) == 0)
  890.               break;
  891.             node=node->child[id];
  892.           }
  893.           /*
  894.             Find closest color among siblings and their children.
  895.           */
  896.           cube.color.red=red;
  897.           cube.color.green=green;
  898.           cube.color.blue=blue;
  899.           cube.distance=(unsigned long) (~0);
  900.           ClosestColor(node->parent);
  901.           cache[i]=cube.color_number;
  902.         }
  903.       index=(unsigned short) cache[i];
  904.       red_error=(int) red-(int) cube.colormap[index].red;
  905.       green_error=(int) green-(int) cube.colormap[index].green;
  906.       blue_error=(int) blue-(int) cube.colormap[index].blue;
  907.       q->index=index;
  908.       q+=step;
  909.       /*
  910.         Propagate the error in these proportions:
  911.                 Q     7/16
  912.           3/16  5/16  1/16
  913.       */
  914.       cs->red=0;
  915.       cs->green=0;
  916.       cs->blue=0;
  917.       cs+=step;
  918.       cs->red+=7*red_error;
  919.       cs->green+=7*green_error;
  920.       cs->blue+=7*blue_error;
  921.       ns-=step;
  922.       ns->red+=3*red_error;
  923.       ns->green+=3*green_error;
  924.       ns->blue+=3*blue_error;
  925.       ns+=step;
  926.       ns->red+=5*red_error;
  927.       ns->green+=5*green_error;
  928.       ns->blue+=5*blue_error;
  929.       ns+=step;
  930.       ns->red+=red_error;
  931.       ns->green+=green_error;
  932.       ns->blue+=blue_error;
  933.     }
  934.   }
  935.   /*
  936.     Free up memory.
  937.   */
  938.   (void) free((char *) range_table);
  939.   (void) free((char *) error);
  940.   (void) free((char *) cache);
  941.   return(False);
  942. }
  943.  
  944. /*
  945. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  946. %                                                                             %
  947. %                                                                             %
  948. %                                                                             %
  949. %  I n i t i a l i z e C u b e                                                %
  950. %                                                                             %
  951. %                                                                             %
  952. %                                                                             %
  953. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  954. %
  955. %  Function InitializeCube initialize the Cube data structure.
  956. %
  957. %  The format of the InitializeCube routine is:
  958. %
  959. %      InitializeCube(number_colors,tree_depth,number_pixels,optimal)
  960. %
  961. %  A description of each parameter follows.
  962. %
  963. %    o number_colors: This integer value indicates the maximum number of
  964. %      colors in the quantized image or colormap.  Here we use this value
  965. %      to determine the depth of the color description tree.
  966. %
  967. %    o tree_depth: Normally, this integer value is zero or one.  A zero or
  968. %      one tells Quantize to choose a optimal tree depth of Log4(number_colors).
  969. %      A tree of this depth generally allows the best representation of the
  970. %      reference image with the least amount of memory and the fastest
  971. %      computational speed.  In some cases, such as an image with low color
  972. %      dispersion (a few number of colors), a value other than
  973. %      Log4(number_colors) is required.  To expand the color tree completely,
  974. %      use a value of 8.
  975. %
  976. %    o number_pixels: Specifies the number of individual pixels in the image.
  977. %
  978. %    o optimal: An unsigned integer value greater than zero indicates that
  979. %      the optimal representation of the reference image should be returned.
  980. %
  981. */
  982. static void InitializeCube(number_colors,tree_depth,number_pixels,optimal)
  983. unsigned int
  984.   number_colors,
  985.   tree_depth,
  986.   number_pixels,
  987.   optimal;
  988. {
  989.   char
  990.     c;
  991.  
  992.   register int
  993.     i;
  994.  
  995.   static int
  996.     log4[6] = {4, 16, 64, 256, 1024, ~0};
  997.  
  998.   unsigned int
  999.     bits,
  1000.     level,
  1001.     max_shift;
  1002.  
  1003.   /*
  1004.     Initialize tree to describe color cube.  Depth is: Log4(colormap size)+2;
  1005.   */
  1006.   cube.node_queue=(Nodes *) NULL;
  1007.   cube.nodes=0;
  1008.   cube.free_nodes=0;
  1009.   if (tree_depth > 1)
  1010.     cube.depth=Min(tree_depth,8);
  1011.   else
  1012.     {
  1013.       for (i=0; i < 6; i++)
  1014.         if (number_colors <= log4[i])
  1015.           break;
  1016.       cube.depth=i+2;
  1017.       if (!optimal)
  1018.         cube.depth--;
  1019.     }
  1020.   /*
  1021.     Initialize the shift values.
  1022.   */
  1023.   c=1;
  1024.   for (bits=0; c != (char) 0; bits++)
  1025.     c<<=1;
  1026.   for (max_shift=sizeof(unsigned int)*bits; number_pixels != 0; max_shift--)
  1027.     number_pixels>>=1;
  1028.   for (level=0; level <= cube.depth; level++)
  1029.   {
  1030.     cube.shift[level]=max_shift;
  1031.     if (max_shift != 0)
  1032.       max_shift--;
  1033.   }
  1034.   /*
  1035.     Initialize root node.
  1036.   */
  1037.   cube.root=InitializeNode(0,0,(Node *) NULL,(MaxRGB+1) >> 1,(MaxRGB+1) >> 1,
  1038.     (MaxRGB+1) >> 1);
  1039.   if (cube.root == (Node *) NULL)
  1040.     {
  1041.       (void) fprintf (stderr,
  1042.         "Unable to quantize image,Memory allocation failed\n");
  1043.       exit(1);
  1044.     }
  1045.   cube.root->parent=cube.root;
  1046.   cube.root->number_colors=(unsigned long) (~0);
  1047.   cube.colors=0;
  1048.   /*
  1049.     Initialize the square values.
  1050.   */
  1051.   for (i=(-MaxRGB); i <= MaxRGB; i++)
  1052.     cube.squares[i+MaxRGB]=i*i;
  1053. }
  1054.  
  1055. /*
  1056. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1057. %                                                                             %
  1058. %                                                                             %
  1059. %                                                                             %
  1060. %  I n i t i a l i z e N o d e                                                %
  1061. %                                                                             %
  1062. %                                                                             %
  1063. %                                                                             %
  1064. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1065. %
  1066. %  Function InitializeNode allocates memory for a new node in the color cube
  1067. %  tree and presets all fields to zero.
  1068. %
  1069. %  The format of the InitializeNode routine is:
  1070. %
  1071. %      node=InitializeNode(node,id,level,mid_red,mid_green,mid_blue)
  1072. %
  1073. %  A description of each parameter follows.
  1074. %
  1075. %    o node: The InitializeNode routine returns this integer address.
  1076. %
  1077. %    o id: Specifies the child number of the node.
  1078. %
  1079. %    o level: Specifies the level in the classification the node resides.
  1080. %
  1081. %    o mid_red: Specifies the mid point of the red axis for this node.
  1082. %
  1083. %    o mid_green: Specifies the mid point of the green axis for this node.
  1084. %
  1085. %    o mid_blue: Specifies the mid point of the blue axis for this node.
  1086. %
  1087. %
  1088. */
  1089. static Node *InitializeNode(id,level,parent,mid_red,mid_green,mid_blue)
  1090. unsigned int
  1091.   id,
  1092.   level;
  1093.  
  1094. Node
  1095.   *parent;
  1096.  
  1097. unsigned int
  1098.   mid_red,
  1099.   mid_green,
  1100.   mid_blue;
  1101. {
  1102.   register int
  1103.     i;
  1104.  
  1105.   register Node
  1106.     *node;
  1107.  
  1108.   if (cube.free_nodes == 0)
  1109.     {
  1110.       register Nodes
  1111.         *nodes;
  1112.  
  1113.       /*
  1114.         Allocate a new nodes of nodes.
  1115.       */
  1116.       nodes=(Nodes *) malloc(sizeof(Nodes));
  1117.       if (nodes == (Nodes *) NULL)
  1118.         return((Node *) NULL);
  1119.       nodes->next=cube.node_queue;
  1120.       cube.node_queue=nodes;
  1121.       cube.next_node=nodes->nodes;
  1122.       cube.free_nodes=NodesInAList;
  1123.     }
  1124.   cube.nodes++;
  1125.   cube.free_nodes--;
  1126.   node=cube.next_node++;
  1127.   node->parent=parent;
  1128.   for (i=0; i < 8; i++)
  1129.     node->child[i]=(Node *) NULL;
  1130.   node->id=id;
  1131.   node->level=level;
  1132.   node->children=0;
  1133.   node->mid_red=mid_red;
  1134.   node->mid_green=mid_green;
  1135.   node->mid_blue=mid_blue;
  1136.   node->number_colors=0;
  1137.   node->number_unique=0;
  1138.   node->total_red=0;
  1139.   node->total_green=0;
  1140.   node->total_blue=0;
  1141.   return(node);
  1142. }
  1143.  
  1144. /*
  1145. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1146. %                                                                             %
  1147. %                                                                             %
  1148. %                                                                             %
  1149. %  P r u n e C h i l d                                                        %
  1150. %                                                                             %
  1151. %                                                                             %
  1152. %                                                                             %
  1153. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1154. %
  1155. %  Function PruneChild deletes the given node and merges its statistics into
  1156. %  its parent.
  1157. %
  1158. %  The format of the PruneSubtree routine is:
  1159. %
  1160. %      PruneChild(node)
  1161. %
  1162. %  A description of each parameter follows.
  1163. %
  1164. %    o node: pointer to node in color cube tree that is to be pruned.
  1165. %
  1166. %
  1167. */
  1168. static void PruneChild(node)
  1169. register Node
  1170.   *node;
  1171. {
  1172.   register Node
  1173.     *parent;
  1174.  
  1175.   /*
  1176.     Merge color statistics into parent.
  1177.   */
  1178.   parent=node->parent;
  1179.   parent->children&=~(1 << node->id);
  1180.   parent->number_unique+=node->number_unique;
  1181.   parent->total_red+=node->total_red;
  1182.   parent->total_green+=node->total_green;
  1183.   parent->total_blue+=node->total_blue;
  1184.   cube.nodes--;
  1185. }
  1186.  
  1187. /*
  1188. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1189. %                                                                             %
  1190. %                                                                             %
  1191. %                                                                             %
  1192. %  P r u n e L e v e l                                                        %
  1193. %                                                                             %
  1194. %                                                                             %
  1195. %                                                                             %
  1196. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1197. %
  1198. %  Procedure PruneLevel deletes all nodes at the bottom level of the color
  1199. %  tree merging their color statistics into their parent node.
  1200. %
  1201. %  The format of the PruneLevel routine is:
  1202. %
  1203. %      PruneLevel(node)
  1204. %
  1205. %  A description of each parameter follows.
  1206. %
  1207. %    o node: pointer to node in color cube tree that is to be pruned.
  1208. %
  1209. %
  1210. */
  1211. static void PruneLevel(node)
  1212. register Node
  1213.   *node;
  1214. {
  1215.   register int
  1216.     id;
  1217.  
  1218.   /*
  1219.     Traverse any children.
  1220.   */
  1221.   if (node->children != 0)
  1222.     for (id=0; id < 8; id++)
  1223.       if (node->children & (1 << id))
  1224.         PruneLevel(node->child[id]);
  1225.   if (node->level == cube.depth)
  1226.     PruneChild(node);
  1227. }
  1228.  
  1229. /*
  1230. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1231. %                                                                             %
  1232. %                                                                             %
  1233. %                                                                             %
  1234. %  R e d u c e                                                                %
  1235. %                                                                             %
  1236. %                                                                             %
  1237. %                                                                             %
  1238. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1239. %
  1240. %  Function Reduce traverses the color cube tree and prunes any node whose
  1241. %  number of colors fall below a particular threshold.
  1242. %
  1243. %  The format of the Reduce routine is:
  1244. %
  1245. %      Reduce(node)
  1246. %
  1247. %  A description of each parameter follows.
  1248. %
  1249. %    o node: pointer to node in color cube tree that is to be pruned.
  1250. %
  1251. %
  1252. */
  1253. static void Reduce(node)
  1254. register Node
  1255.   *node;
  1256. {
  1257.   register unsigned int
  1258.     id;
  1259.  
  1260.   /*
  1261.     Traverse any children.
  1262.   */
  1263.   if (node->children != 0)
  1264.     for (id=0; id < 8; id++)
  1265.       if (node->children & (1 << id))
  1266.         Reduce(node->child[id]);
  1267.   /*
  1268.     Node is a colormap entry if it has unique colors.
  1269.   */
  1270.   if (node->number_unique != 0)
  1271.     cube.colors++;
  1272.   /*
  1273.     Find minimum pruning threshold.
  1274.   */
  1275.   if (node->number_colors < cube.next_pruning_threshold)
  1276.     cube.next_pruning_threshold=node->number_colors;
  1277.   if (node->number_colors <= cube.pruning_threshold)
  1278.     PruneChild(node); /* Node has a sub-threshold color count */
  1279. }
  1280.  
  1281. /*
  1282. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1283. %                                                                             %
  1284. %                                                                             %
  1285. %                                                                             %
  1286. %  R e d u c t i o n                                                          %
  1287. %                                                                             %
  1288. %                                                                             %
  1289. %                                                                             %
  1290. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1291. %
  1292. %  Function Reduction repeatedly prunes the tree until the number of nodes
  1293. %  with n2 > 0 is less than or equal to the maximum number of colors allowed
  1294. %  in the output image.  On any given iteration over the tree, it selects
  1295. %  those nodes whose n1  count is minimal for pruning and merges their
  1296. %  color statistics upward. It uses a pruning threshold, ns, to govern
  1297. %  node selection as follows:
  1298. %
  1299. %    ns = 0
  1300. %    while number of nodes with (n2 > 0) > required maximum number of colors
  1301. %      prune all nodes such that n1 <= ns
  1302. %      Set ns to minimum n1 in remaining nodes
  1303. %
  1304. %  When a node to be pruned has offspring, the pruning procedure invokes
  1305. %  itself recursively in order to prune the tree from the leaves upward.
  1306. %  n2,  Sr, Sg,  and  Sb in a node being pruned are always added to the
  1307. %  corresponding data in that node's parent.  This retains the pruned
  1308. %  node's color characteristics for later averaging.
  1309. %
  1310. %  For each node, n2 pixels exist for which that node represents the
  1311. %  smallest volume in RGB space containing those pixel's colors.  When n2
  1312. %  > 0 the node will uniquely define a color in the output image. At the
  1313. %  beginning of reduction,  n2 = 0  for all nodes except a the leaves of
  1314. %  the tree which represent colors present in the input image.
  1315. %
  1316. %  The other pixel count, n1, indicates the total number of colors
  1317. %  within the cubic volume which the node represents.  This includes n1 -
  1318. %  n2  pixels whose colors should be defined by nodes at a lower level in
  1319. %  the tree.
  1320. %
  1321. %  The format of the Reduction routine is:
  1322. %
  1323. %      Reduction(number_colors)
  1324. %
  1325. %  A description of each parameter follows.
  1326. %
  1327. %    o number_colors: This integer value indicates the maximum number of
  1328. %      colors in the quantized image or colormap.  The actual number of
  1329. %      colors allocated to the colormap may be less than this value, but
  1330. %      never more.  Note, the number of colors is restricted to a value
  1331. %      less than or equal to 65536 if the continuous_tone parameter has a
  1332. %      value of zero.
  1333. %
  1334. %
  1335. */
  1336. static void Reduction(number_colors)
  1337. unsigned int
  1338.   number_colors;
  1339. {
  1340.   cube.next_pruning_threshold=1;
  1341.   while (cube.colors > number_colors)
  1342.   {
  1343.     cube.pruning_threshold=cube.next_pruning_threshold;
  1344.     cube.next_pruning_threshold=cube.root->number_colors-1;
  1345.     cube.colors=0;
  1346.     Reduce(cube.root);
  1347.   }
  1348. }
  1349.  
  1350. /*
  1351. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1352. %                                                                             %
  1353. %                                                                             %
  1354. %                                                                             %
  1355. %  Q u a n t i z e I m a g e                                                  %
  1356. %                                                                             %
  1357. %                                                                             %
  1358. %                                                                             %
  1359. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1360. %
  1361. %  Function QuantizeImage analyzes the colors within a reference image and
  1362. %  chooses a fixed number of colors to represent the image.  The goal of the
  1363. %  algorithm is to minimize the difference between the input and output image
  1364. %  while minimizing the processing time.
  1365. %
  1366. %  The format of the QuantizeImage routine is:
  1367. %
  1368. %      colors=QuantizeImage(image,number_colors,tree_depth,dither,optimal)
  1369. %
  1370. %  A description of each parameter follows.
  1371. %
  1372. %    o colors: The QuantizeImage function returns this integer
  1373. %      value.  It is the actual number of colors allocated in the
  1374. %      colormap.  Note, the actual number of colors allocated may be less
  1375. %      than the number of colors requested, but never more.
  1376. %
  1377. %    o image: Specifies a pointer to an Image structure;  returned from
  1378. %      ReadImage.
  1379. %
  1380. %    o number_colors: This integer value indicates the maximum number of
  1381. %      colors in the quantized image or colormap.  The actual number of
  1382. %      colors allocated to the colormap may be less than this value, but
  1383. %      never more.  Note, the number of colors is restricted to a value
  1384. %      less than or equal to 65536 if the continuous_tone parameter has a
  1385. %      value of zero.
  1386. %
  1387. %    o tree_depth: Normally, this integer value is zero or one.  A zero or
  1388. %      one tells Quantize to choose a optimal tree depth of
  1389. %      Log4(number_colors).  A tree of this depth generally allows the best
  1390. %      representation of the reference image with the least amount of memory
  1391. %      and the fastest computational speed.  In some cases, such as an image
  1392. %      with low color dispersion (a few number of colors), a value other than
  1393. %      Log4(number_colors) is required.  To expand the color tree completely,
  1394. %      use a value of 8.
  1395. %
  1396. %    o dither: Set this integer value to something other than zero to
  1397. %      dither the quantized image.  The basic strategy of dithering is to
  1398. %      trade intensity resolution for spatial resolution by averaging the
  1399. %      intensities of several neighboring pixels.  Images which suffer
  1400. %      from severe contouring when quantized can be improved with the
  1401. %      technique of dithering.  Severe contouring generally occurs when
  1402. %      quantizing to very few colors, or to a poorly-chosen colormap.
  1403. %      Note, dithering is a computationally expensive process and will
  1404. %      increase processing time significantly.
  1405. %
  1406. %    o colorspace: An unsigned integer value that indicates the colorspace.
  1407. %      Empirical evidence suggests that distances in YUV or YIQ correspond to
  1408. %      perceptual color differences more closely than do distances in RGB
  1409. %      space.  The image is then returned to RGB colorspace after color
  1410. %      reduction.
  1411. %
  1412. %    o optimal: An unsigned integer value greater than zero indicates that
  1413. %      the optimal representation of the reference image should be returned.
  1414. %
  1415. %
  1416. */
  1417. void QuantizeImage(image,number_colors,tree_depth,dither,colorspace,optimal)
  1418. Image
  1419.   *image;
  1420.  
  1421. unsigned int
  1422.   number_colors,
  1423.   tree_depth,
  1424.   dither,
  1425.   colorspace,
  1426.   optimal;
  1427. {
  1428.   Nodes
  1429.     *nodes;
  1430.  
  1431.   /*
  1432.     Reduce the number of colors in the continuous tone image.
  1433.   */
  1434.  
  1435.   if (number_colors > MaxColormapSize)
  1436.     number_colors=MaxColormapSize;
  1437.   InitializeCube(number_colors,tree_depth,image->columns*image->rows,optimal);
  1438.  
  1439.   if (!dither || !optimal)
  1440.     if (image->packets == (image->columns*image->rows))
  1441.       CompressImage(image);
  1442.   if (colorspace != RGBColorspace)
  1443.     RGBTransformImage(image,colorspace);
  1444.   Classification(image);
  1445.   Reduction(number_colors);
  1446.   Assignment(image,number_colors,dither,colorspace,optimal);
  1447.   if (colorspace != RGBColorspace)
  1448.     TransformRGBImage(image,colorspace);
  1449.   /*
  1450.     Release color cube tree storage.
  1451.   */
  1452.   do
  1453.   {
  1454.     nodes=cube.node_queue->next;
  1455.     (void) free((char *) cube.node_queue);
  1456.     cube.node_queue=nodes;
  1457.   }
  1458.   while (cube.node_queue != (Nodes *) NULL);
  1459. }
  1460.  
  1461. /*
  1462. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1463. %                                                                             %
  1464. %                                                                             %
  1465. %                                                                             %
  1466. %   Q u a n t i z e I m a g e s                                               %
  1467. %                                                                             %
  1468. %                                                                             %
  1469. %                                                                             %
  1470. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1471. %
  1472. %  QuantizeImages analyzes the colors within a set of reference images and
  1473. %  chooses a fixed number of colors to represent the set.  The goal of the
  1474. %  algorithm is to minimize the difference between the input and output images
  1475. %  while minimizing the processing time.
  1476. %
  1477. %  The format of the QuantizeImages routine is:
  1478. %
  1479. %      QuantizeImages(images,number_images,number_colors,tree_depth,dither,
  1480. %        optimal)
  1481. %
  1482. %  A description of each parameter follows:
  1483. %
  1484. %    o images: Specifies a pointer to a set of Image structures.
  1485. %
  1486. %    o number_images:  Specifies an unsigned integer representing the number
  1487. %      images in the image set.
  1488. %
  1489. %    o colormap_image: Specifies a pointer to a Image structure.  Reduce
  1490. %      images to a set of colors represented by this image.
  1491. %
  1492. %    o number_colors: This integer value indicates the maximum number of
  1493. %      colors in the quantized image or colormap.  The actual number of colors
  1494. %      allocated to the colormap may be less than this value, but never more.
  1495. %      Note, the number of colors is restricted to a value less than or equal
  1496. %      to 65536 if the quantized image is not DirectClass.
  1497. %
  1498. %    o tree_depth: Normally, this integer value is zero or one.  A zero or
  1499. %      one tells QUANTIZE to choose a optimal tree depth.  An optimal depth
  1500. %      generally allows the best representation of the reference image with the
  1501. %      fastest computational speed and the least amount of memory.  However,
  1502. %      the default depth is inappropriate for some images.  To assure the best
  1503. %      representation, try values between 2 and 8 for this parameter.
  1504. %
  1505. %    o dither: Set this integer value to something other than zero to
  1506. %      dither the quantized image.  The basic strategy of dithering is to
  1507. %      trade intensity resolution for spatial resolution by averaging the
  1508. %      intensities of several neighboring pixels.  Images which suffer
  1509. %      from severe contouring when quantized can be improved with the
  1510. %      technique of dithering.  Severe contouring generally occurs when
  1511. %      quantizing to very few colors, or to a poorly-chosen colormap.
  1512. %      Note, dithering is a computationally expensive process and will
  1513. %      increase processing time significantly.
  1514. %
  1515. %    o colorspace: An unsigned integer value that indicates the colorspace.
  1516. %      Empirical evidence suggests that distances in YUV or YIQ correspond to
  1517. %      perceptual color differences more closely than do distances in RGB
  1518. %      space.  The image is then returned to RGB colorspace after color
  1519. %      reduction.
  1520. %
  1521. %    o optimal: An unsigned integer value greater than zero indicates that
  1522. %      the optimal representation of the reference image should be returned.
  1523. %
  1524. %
  1525. */
  1526. void QuantizeImages(images,number_images,colormap_image,number_colors,
  1527.   tree_depth,dither,colorspace,optimal)
  1528. Image
  1529.   **images;
  1530.  
  1531. unsigned int
  1532.   number_images;
  1533.  
  1534. Image
  1535.   *colormap_image;
  1536.  
  1537. unsigned int
  1538.   number_colors,
  1539.   tree_depth,
  1540.   dither,
  1541.   colorspace,
  1542.   optimal;
  1543. {
  1544.   Nodes
  1545.     *nodes;
  1546.  
  1547.   register unsigned int
  1548.     i;
  1549.  
  1550.   /*
  1551.     Reduce the number of colors in the continuous tone image sequence.
  1552.   */
  1553.   InitializeCube(number_colors,tree_depth,(unsigned int) (~0),optimal);
  1554.   if (colormap_image != (Image *) NULL)
  1555.     {
  1556.       /*
  1557.         Reduce images to a set of colors represented by the colormap image.
  1558.       */
  1559.       if (colorspace != RGBColorspace)
  1560.         RGBTransformImage(colormap_image,colorspace);
  1561.       Classification(colormap_image);
  1562.       if (colorspace != RGBColorspace)
  1563.         TransformRGBImage(colormap_image,colorspace);
  1564.       optimal=True;
  1565.     }
  1566.   else
  1567.     for (i=0; i < number_images; i+=Max((number_images+16) >> 5,1))
  1568.     {
  1569.       if (!dither || !optimal)
  1570.         if (images[i]->packets == (images[i]->columns*images[i]->rows))
  1571.           CompressImage(images[i]);
  1572.       if (colorspace != RGBColorspace)
  1573.         RGBTransformImage(images[i],colorspace);
  1574.       if (colormap_image == (Image *) NULL)
  1575.         Classification(images[i]);
  1576.     }
  1577.   Reduction(number_colors);
  1578.   for (i=0; i < number_images; i++)
  1579.   {
  1580.     Assignment(images[i],number_colors,dither,colorspace,optimal);
  1581.     if (colorspace != RGBColorspace)
  1582.       TransformRGBImage(images[i],colorspace);
  1583.   }
  1584.   /*
  1585.     Release color cube tree storage.
  1586.   */
  1587.   do
  1588.   {
  1589.     nodes=cube.node_queue->next;
  1590.     (void) free((char *) cube.node_queue);
  1591.     cube.node_queue=nodes;
  1592.   }
  1593.   while (cube.node_queue != (Nodes *) NULL);
  1594. }
  1595.