home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / public / ImageMagick / magick / quantize.c < prev    next >
Encoding:
Text File  |  1994-08-02  |  58.3 KB  |  1,708 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 & 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. %  & 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 & 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 & 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 & 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 "magick.h"
  187. #include "image.h"
  188.  
  189. /*
  190.   Define declarations.
  191. */
  192. #define color_number  number_colors
  193. #define MaxNodes  266817
  194. #define MaxShift  8
  195. #define MaxTreeDepth  8  /* Log2(MaxRGB) */
  196. #define NodesInAList  2048
  197.  
  198. /*
  199.   Structures.
  200. */
  201. typedef struct _Node
  202. {
  203.   struct _Node
  204.     *parent,
  205.     *child[8];
  206.  
  207.   unsigned char
  208.     id,
  209.     level,
  210.     children,
  211.     mid_red,
  212.     mid_green,
  213.     mid_blue;
  214.  
  215.   unsigned long
  216.     number_colors,
  217.     number_unique,
  218.     total_red,
  219.     total_green,
  220.     total_blue;
  221. } Node;
  222.  
  223. typedef struct _Nodes
  224. {
  225.   Node
  226.     nodes[NodesInAList];
  227.  
  228.   struct _Nodes
  229.     *next;
  230. } Nodes;
  231.  
  232. typedef struct _Cube
  233. {
  234.   Node
  235.     *root;
  236.  
  237.   ColorPacket
  238.     color,
  239.     *colormap;
  240.  
  241.   unsigned int
  242.     depth;
  243.  
  244.   unsigned long
  245.     colors,
  246.     pruning_threshold,
  247.     next_pruning_threshold,
  248.     distance,
  249.     squares[MaxRGB+MaxRGB+1];
  250.  
  251.   unsigned int
  252.     shift[MaxTreeDepth+1],
  253.     nodes,
  254.     free_nodes,
  255.     color_number;
  256.  
  257.   Node
  258.     *next_node;
  259.  
  260.   Nodes
  261.     *node_queue;
  262. } Cube;
  263.  
  264. /*
  265.   Global variables.
  266. */
  267. static Cube
  268.   cube;
  269.  
  270. /*
  271.   Forward declarations.
  272. */
  273. static Node
  274.   *InitializeNode _Declare((unsigned int,unsigned int,Node *,unsigned int,
  275.     unsigned int,unsigned int));
  276.  
  277. static unsigned int
  278.   DitherImage _Declare((Image *));
  279.  
  280. static void
  281.   ClosestColor _Declare((Node *)),
  282.   Colormap _Declare((Node *)),
  283.   PruneLevel _Declare((Node *));
  284.  
  285. /*
  286. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  287. %                                                                             %
  288. %                                                                             %
  289. %                                                                             %
  290. %  A s s i g n m e n t                                                        %
  291. %                                                                             %
  292. %                                                                             %
  293. %                                                                             %
  294. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  295. %
  296. %  Procedure Assignment generates the output image from the pruned tree.  The
  297. %  output image consists of two parts: (1)  A color map, which is an
  298. %  array of color descriptions (RGB triples) for each color present in
  299. %  the output image;  (2)  A pixel array, which represents each pixel as
  300. %  an index into the color map array.
  301. %
  302. %  First, the assignment phase makes one pass over the pruned color
  303. %  description tree to establish the image's color map.  For each node
  304. %  with n2  > 0, it divides Sr, Sg, and Sb by n2 .  This produces the
  305. %  mean color of all pixels that classify no lower than this node.  Each
  306. %  of these colors becomes an entry in the color map.
  307. %
  308. %  Finally,  the assignment phase reclassifies each pixel in the pruned
  309. %  tree to identify the deepest node containing the pixel's color.  The
  310. %  pixel's value in the pixel array becomes the index of this node's mean
  311. %  color in the color map.
  312. %
  313. %  The format of the Assignment routine is:
  314. %
  315. %      Assignment(image,dither,colorspace,optimal)
  316. %
  317. %  A description of each parameter follows.
  318. %
  319. %    o image: Specifies a pointer to an Image structure;  returned from
  320. %      ReadImage.
  321. %
  322. %    o dither: Set this integer value to something other than zero to
  323. %      dither the quantized image.  The basic strategy of dithering is to
  324. %      trade intensity resolution for spatial resolution by averaging the
  325. %      intensities of several neighboring pixels.  Images which suffer
  326. %      from severe contouring when quantized can be improved with the
  327. %      technique of dithering.  Severe contouring generally occurs when
  328. %      quantizing to very few colors, or to a poorly-chosen colormap.
  329. %      Note, dithering is a computationally expensive process and will
  330. %      increase processing time significantly.
  331. %
  332. %    o colorspace: An unsigned integer value that indicates the colorspace.
  333. %
  334. %    o optimal: An unsigned integer value greater than zero indicates that
  335. %      the optimal representation of the reference image should be returned.
  336. %
  337. %
  338. */
  339. static void Assignment(image,dither,colorspace,optimal)
  340. Image
  341.   *image;
  342.  
  343. unsigned int
  344.   dither,
  345.   colorspace,
  346.   optimal;
  347. {
  348.   register int
  349.     i;
  350.  
  351.   register Node
  352.     *node;
  353.  
  354.   register RunlengthPacket
  355.     *p;
  356.  
  357.   register unsigned int
  358.     id;
  359.  
  360.   /*
  361.     Allocate image colormap.
  362.   */
  363.   if (image->colormap != (ColorPacket *) NULL)
  364.     (void) free((char *) image->colormap);
  365.   image->colormap=(ColorPacket *)
  366.     malloc((unsigned int) cube.colors*sizeof(ColorPacket));
  367.   if (image->colormap == (ColorPacket *) NULL)
  368.     {
  369.       Warning("Unable to quantize image","Memory allocation failed");
  370.       exit(1);
  371.     }
  372.   if (image->signature != (char *) NULL)
  373.     (void) free((char *) image->signature);
  374.   image->signature=(char *) NULL;
  375.   cube.colormap=image->colormap;
  376.   cube.colors=0;
  377.   Colormap(cube.root);
  378.   if ((cube.colors == 2)  && (colorspace == GRAYColorspace))
  379.     {
  380.       unsigned int
  381.         polarity;
  382.  
  383.       /*
  384.         Monochrome image.
  385.       */
  386.       polarity=Intensity(image->colormap[0]) > Intensity(image->colormap[1]);
  387.       image->colormap[polarity].red=0;
  388.       image->colormap[polarity].green=0;
  389.       image->colormap[polarity].blue=0;
  390.       image->colormap[!polarity].red=MaxRGB;
  391.       image->colormap[!polarity].green=MaxRGB;
  392.       image->colormap[!polarity].blue=MaxRGB;
  393.       dither|=((image->class == DirectClass) || (image->colors > 2));
  394.     }
  395.   image->alpha=False;
  396.   image->class=PseudoClass;
  397.   image->colors=(unsigned int) cube.colors;
  398.   /*
  399.     Create a reduced color image.  For the non-optimal case we trade
  400.     accuracy for speed improvements.
  401.   */
  402.   if (dither || !optimal)
  403.     dither=!DitherImage(image);
  404.   p=image->pixels;
  405.   if (!dither)
  406.     if (!optimal)
  407.       for (i=0; i < image->packets; i++)
  408.       {
  409.         /*
  410.           Identify the deepest node containing the pixel's color.
  411.         */
  412.         node=cube.root;
  413.         for ( ; ; )
  414.         {
  415.           id=(p->red > node->mid_red ? 1 : 0) |
  416.             (p->green > node->mid_green ? 1 : 0) << 1 |
  417.             (p->blue > node->mid_blue ? 1 : 0) << 2;
  418.           if ((node->children & (1 << id)) == 0)
  419.             break;
  420.           node=node->child[id];
  421.         }
  422.         p->index=(unsigned short) node->color_number;
  423.         p++;
  424.       }
  425.     else
  426.       for (i=0; i < image->packets; i++)
  427.       {
  428.         /*
  429.           Identify the deepest node containing the pixel's color.
  430.         */
  431.         node=cube.root;
  432.         for ( ; ; )
  433.         {
  434.           id=(p->red > node->mid_red ? 1 : 0) |
  435.             (p->green > node->mid_green ? 1 : 0) << 1 |
  436.            (p->blue > node->mid_blue ? 1 : 0) << 2;
  437.          if ((node->children & (1 << id)) == 0)
  438.            break;
  439.          node=node->child[id];
  440.        }
  441.        /*
  442.          Find closest color among siblings and their children.
  443.        */
  444.        cube.color.red=p->red;
  445.        cube.color.green=p->green;
  446.        cube.color.blue=p->blue;
  447.        cube.distance=(unsigned long) (~0);
  448.        ClosestColor(node->parent);
  449.        p->index=cube.color_number;
  450.        p++;
  451.      }
  452. }
  453.  
  454. /*
  455. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  456. %                                                                             %
  457. %                                                                             %
  458. %                                                                             %
  459. %  C l a s s i f i c a t i o n                                                %
  460. %                                                                             %
  461. %                                                                             %
  462. %                                                                             %
  463. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  464. %
  465. %  Procedure Classification begins by initializing a color description tree
  466. %  of sufficient depth to represent each possible input color in a leaf.
  467. %  However, it is impractical to generate a fully-formed color
  468. %  description tree in the classification phase for realistic values of
  469. %  cmax.  If colors components in the input image are quantized to k-bit
  470. %  precision, so that cmax= 2k-1, the tree would need k levels below the
  471. %  root node to allow representing each possible input color in a leaf.
  472. %  This becomes prohibitive because the tree's total number of nodes is
  473. %  1 + sum(i=1,k,8k).
  474. %
  475. %  A complete tree would require 19,173,961 nodes for k = 8, cmax = 255.
  476. %  Therefore, to avoid building a fully populated tree, QUANTIZE: (1)
  477. %  Initializes data structures for nodes only as they are needed;  (2)
  478. %  Chooses a maximum depth for the tree as a function of the desired
  479. %  number of colors in the output image (currently log2(colormap size)).
  480. %
  481. %  For each pixel in the input image, classification scans downward from
  482. %  the root of the color description tree.  At each level of the tree it
  483. %  identifies the single node which represents a cube in RGB space
  484. %  containing It updates the following data for each such node:
  485. %
  486. %    n1 : Number of pixels whose color is contained in the RGB cube
  487. %    which this node represents;
  488. %
  489. %    n2 : Number of pixels whose color is not represented in a node at
  490. %    lower depth in the tree;  initially,  n2 = 0 for all nodes except
  491. %    leaves of the tree.
  492. %
  493. %    Sr, Sg, Sb : Sums of the red, green, and blue component values for
  494. %    all pixels not classified at a lower depth. The combination of
  495. %    these sums and n2  will ultimately characterize the mean color of a
  496. %    set of pixels represented by this node.
  497. %
  498. %  The format of the Classification routine is:
  499. %
  500. %      Classification(image)
  501. %
  502. %  A description of each parameter follows.
  503. %
  504. %    o image: Specifies a pointer to an Image structure;  returned from
  505. %      ReadImage.
  506. %
  507. %
  508. */
  509. static void Classification(image)
  510. Image
  511.   *image;
  512. {
  513.   register int
  514.     i;
  515.  
  516.   register Node
  517.     *node;
  518.  
  519.   register RunlengthPacket
  520.     *p;
  521.  
  522.   register unsigned int
  523.     bisect,
  524.     count,
  525.     id,
  526.     level;
  527.  
  528.   p=image->pixels;
  529.   for (i=0; i < image->packets; i++)
  530.   {
  531.     if (cube.nodes > MaxNodes)
  532.       {
  533.         /*
  534.           Prune one level if the color tree is too large.
  535.         */
  536.         PruneLevel(cube.root);
  537.         cube.depth--;
  538.       }
  539.     /*
  540.       Start at the root and descend the color cube tree.
  541.     */
  542.     count=p->length+1;
  543.     node=cube.root;
  544.     for (level=1; level <= cube.depth; level++)
  545.     {
  546.       id=(p->red > node->mid_red ? 1 : 0) |
  547.         (p->green > node->mid_green ? 1 : 0) << 1 |
  548.         (p->blue > node->mid_blue ? 1 : 0) << 2;
  549.       if (node->child[id] == (Node *) NULL)
  550.         {
  551.           /*
  552.             Set colors of new node to contain pixel.
  553.           */
  554.           node->children|=1 << id;
  555.           bisect=(unsigned int) (1 << (MaxTreeDepth-level)) >> 1;
  556.           node->child[id]=InitializeNode(id,level,node,
  557.             node->mid_red+(id & 1 ? bisect : -bisect),
  558.             node->mid_green+(id & 2 ? bisect : -bisect),
  559.             node->mid_blue+(id & 4 ? bisect : -bisect));
  560.           if (node->child[id] == (Node *) NULL)
  561.             {
  562.               Warning("Unable to quantize image","Memory allocation failed");
  563.               exit(1);
  564.             }
  565.           if (level == cube.depth)
  566.             cube.colors++;
  567.         }
  568.       /*
  569.         Record the number of colors represented by this node.  Shift by level
  570.         in the color description tree.
  571.       */
  572.       node=node->child[id];
  573.       node->number_colors+=count << cube.shift[level];
  574.     }
  575.     /*
  576.       Increment unique color count and sum RGB values for this leaf for later
  577.       derivation of the mean cube color.
  578.     */
  579.     node->number_unique+=count;
  580.     node->total_red+=p->red*count;
  581.     node->total_green+=p->green*count;
  582.     node->total_blue+=p->blue*count;
  583.     p++;
  584.   }
  585. }
  586.  
  587. /*
  588. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  589. %                                                                             %
  590. %                                                                             %
  591. %                                                                             %
  592. %  C l o s e s t C o l o r                                                    %
  593. %                                                                             %
  594. %                                                                             %
  595. %                                                                             %
  596. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  597. %
  598. %  Procedure ClosestColor traverses the color cube tree at a particular node
  599. %  and determines which colormap entry best represents the input color.
  600. %
  601. %  The format of the ClosestColor routine is:
  602. %
  603. %      ClosestColor(node)
  604. %
  605. %  A description of each parameter follows.
  606. %
  607. %    o node: The address of a structure of type Node which points to a
  608. %      node in the color cube tree that is to be pruned.
  609. %
  610. %
  611. */
  612. static void ClosestColor(node)
  613. register Node
  614.   *node;
  615. {
  616.   register unsigned int
  617.     id;
  618.  
  619.   /*
  620.     Traverse any children.
  621.   */
  622.   if (node->children != 0)
  623.     for (id=0; id < 8; id++)
  624.       if (node->children & (1 << id))
  625.         ClosestColor(node->child[id]);
  626.   if (node->number_unique != 0)
  627.     {
  628.       register ColorPacket
  629.         *color;
  630.  
  631.       register unsigned int
  632.         blue_distance,
  633.         green_distance,
  634.         red_distance;
  635.  
  636.       register unsigned long
  637.         distance;
  638.  
  639.       /*
  640.         Determine if this color is "closest".
  641.       */
  642.       color=cube.colormap+node->color_number;
  643.       red_distance=(int) color->red-(int) cube.color.red+MaxRGB;
  644.       green_distance=(int) color->green-(int) cube.color.green+MaxRGB;
  645.       blue_distance=(int) color->blue-(int) cube.color.blue+MaxRGB;
  646.       distance=cube.squares[red_distance]+cube.squares[green_distance]+
  647.         cube.squares[blue_distance];
  648.       if (distance < cube.distance)
  649.         {
  650.           cube.distance=distance;
  651.           cube.color_number=(unsigned short) node->color_number;
  652.         }
  653.     }
  654. }
  655.  
  656. /*
  657. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  658. %                                                                             %
  659. %                                                                             %
  660. %                                                                             %
  661. %  C o l o r m a p                                                            %
  662. %                                                                             %
  663. %                                                                             %
  664. %                                                                             %
  665. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  666. %
  667. %  Procedure Colormap traverses the color cube tree and notes each colormap
  668. %  entry.  A colormap entry is any node in the color cube tree where the
  669. %  number of unique colors is not zero.
  670. %
  671. %  The format of the Colormap routine is:
  672. %
  673. %      Colormap(node)
  674. %
  675. %  A description of each parameter follows.
  676. %
  677. %    o node: The address of a structure of type Node which points to a
  678. %      node in the color cube tree that is to be pruned.
  679. %
  680. %
  681. */
  682. static void Colormap(node)
  683. register Node
  684.   *node;
  685. {
  686.   register unsigned int
  687.     id;
  688.  
  689.   /*
  690.     Traverse any children.
  691.   */
  692.   if (node->children != 0)
  693.     for (id=0; id < 8; id++)
  694.       if (node->children & (1 << id))
  695.         Colormap(node->child[id]);
  696.   if (node->number_unique > 0)
  697.     {
  698.       /*
  699.         Colormap entry is defined by the mean color in this cube.
  700.       */
  701.       cube.colormap[cube.colors].red=(unsigned char)
  702.         ((node->total_red+(node->number_unique >> 1))/node->number_unique);
  703.       cube.colormap[cube.colors].green=(unsigned char)
  704.         ((node->total_green+(node->number_unique >> 1))/node->number_unique);
  705.       cube.colormap[cube.colors].blue=(unsigned char)
  706.         ((node->total_blue+(node->number_unique >> 1))/node->number_unique);
  707.       node->color_number=cube.colors++;
  708.     }
  709. }
  710.  
  711. /*
  712. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  713. %                                                                             %
  714. %                                                                             %
  715. %                                                                             %
  716. %  D i t h e r I m a g e                                                      %
  717. %                                                                             %
  718. %                                                                             %
  719. %                                                                             %
  720. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  721. %
  722. %  Procedure DitherImage uses the Floyd-Steinberg algorithm to dither the
  723. %  image.  Refer to "An Adaptive Algorithm for Spatial GreySscale", Robert W.
  724. %  Floyd and Louis Steinberg, Proceedings of the S.I.D., Volume 17(2), 1976.
  725. %
  726. %  First find the closest representation to the reference pixel color in the
  727. %  colormap, the node pixel is assigned this color.  Next, the colormap color
  728. %  is subtracted from the reference pixels color, this represents the
  729. %  quantization error.  Various amounts of this error are added to the pixels
  730. %  ahead and below the node pixel to correct for this error.  The error
  731. %  proportions are:
  732. %
  733. %            P     7/16
  734. %      3/16  5/16  1/16
  735. %
  736. %  The error is distributed left-to-right for even scanlines and right-to-left
  737. %  for odd scanlines.
  738. %
  739. %  The format of the DitherImage routine is:
  740. %
  741. %      DitherImage(image)
  742. %
  743. %  A description of each parameter follows.
  744. %
  745. %    o image: Specifies a pointer to an Image structure;  returned from
  746. %      ReadImage.
  747. %
  748. %
  749. */
  750. static unsigned int DitherImage(image)
  751. Image
  752.   *image;
  753. {
  754. #define MaxError  32
  755.  
  756.   typedef struct _ErrorPacket
  757.   {
  758.     int
  759.       red,
  760.       green,
  761.       blue;
  762.   } ErrorPacket;
  763.  
  764.   ErrorPacket
  765.     *error;
  766.  
  767.   int
  768.     *cache;
  769.  
  770.   register int
  771.     blue_error,
  772.     green_error,
  773.     red_error,
  774.     step;
  775.  
  776.   register Node
  777.     *node;
  778.  
  779.   register RunlengthPacket
  780.     *q;
  781.  
  782.   register ErrorPacket
  783.     *cs,
  784.     *ns;
  785.  
  786.   register unsigned char
  787.     *range_limit;
  788.  
  789.   register unsigned int
  790.     id;
  791.  
  792.   unsigned char
  793.     blue,
  794.     green,
  795.     *range_table,
  796.     red;
  797.  
  798.   unsigned int
  799.     i,
  800.     x,
  801.     y;
  802.  
  803.   unsigned short
  804.     index;
  805.  
  806.   /*
  807.     Image must be uncompressed.
  808.   */
  809.   if (!UncompressImage(image))
  810.     return(True);
  811.   /*
  812.     Allocate memory.
  813.   */
  814.   cache=(int *) malloc((1 << 18)*sizeof(int));
  815.   error=(ErrorPacket *) malloc(((image->columns+2) << 1)*sizeof(ErrorPacket));
  816.   range_table=(unsigned char *) malloc(3*(MaxRGB+1)*sizeof(unsigned char));
  817.   if ((cache == (int *) NULL) || (error == (ErrorPacket *) NULL) ||
  818.       (range_table == (unsigned char *) NULL))
  819.     {
  820.       Warning("Unable to dither image","Memory allocation failed");
  821.       return(True);
  822.     }
  823.   /*
  824.     Initialize tables.
  825.   */
  826.   for (i=0; i < (1 << 18); i++)
  827.     cache[i]=(-1);
  828.   for (i=0; i < ((image->columns+2) << 1); i++)
  829.   {
  830.     error[i].red=0;
  831.     error[i].green=0;
  832.     error[i].blue=0;
  833.   }
  834.   for (i=0; i <= MaxRGB; i++)
  835.   {
  836.     range_table[i]=0;
  837.     range_table[i+(MaxRGB+1)]=(unsigned char) i;
  838.     range_table[i+(MaxRGB+1)*2]=MaxRGB;
  839.   }
  840.   range_limit=range_table+(MaxRGB+1);
  841.   /*
  842.     Dither image.
  843.   */
  844.   for (y=0; y < image->rows; y++)
  845.   {
  846.     q=image->pixels+image->columns*y;
  847.     cs=error+1;
  848.     ns=error+(image->columns+2)+1;
  849.     step=1;
  850.     if (y & 0x01)
  851.       {
  852.         /*
  853.           Distribute error right-to-left for odd scanlines.
  854.         */
  855.         q+=(image->columns-1);
  856.         cs=error+(image->columns+2)+(image->columns-1)+1;
  857.         ns=error+(image->columns-1)+1;
  858.         step=(-1);
  859.       }
  860.     for (x=0; x < image->columns; x++)
  861.     {
  862.       red_error=(cs->red+8)/16;
  863.       if (image->colors > 2)
  864.         if (red_error > MaxError)
  865.           red_error=MaxError;
  866.         else
  867.           if (red_error < -MaxError)
  868.             red_error=(-MaxError);
  869.       green_error=(cs->green+8)/16;
  870.       if (image->colors > 2)
  871.         if (green_error > MaxError)
  872.           green_error=MaxError;
  873.         else
  874.           if (green_error < -MaxError)
  875.             green_error=(-MaxError);
  876.       blue_error=(cs->blue+8)/16;
  877.       if (image->colors > 2)
  878.         if (blue_error > MaxError)
  879.           blue_error=MaxError;
  880.         else
  881.           if (blue_error < -MaxError)
  882.             blue_error=(-MaxError);
  883.       red=range_limit[q->red+red_error];
  884.       green=range_limit[q->green+green_error];
  885.       blue=range_limit[q->blue+blue_error];
  886.       i=(red >> 2) << 12 | (green >> 2) << 6 | blue >> 2;
  887.       if (cache[i] < 0)
  888.         {
  889.           /*
  890.             Identify the deepest node containing the pixel's color.
  891.           */
  892.           node=cube.root;
  893.           for ( ; ; )
  894.           {
  895.             id=(red > node->mid_red ? 1 : 0) |
  896.               (green > node->mid_green ? 1 : 0) << 1 |
  897.               (blue > node->mid_blue ? 1 : 0) << 2;
  898.             if ((node->children & (1 << id)) == 0)
  899.               break;
  900.             node=node->child[id];
  901.           }
  902.           /*
  903.             Find closest color among siblings and their children.
  904.           */
  905.           cube.color.red=red;
  906.           cube.color.green=green;
  907.           cube.color.blue=blue;
  908.           cube.distance=(unsigned long) (~0);
  909.           ClosestColor(node->parent);
  910.           cache[i]=cube.color_number;
  911.         }
  912.       index=(unsigned short) cache[i];
  913.       red_error=(int) red-(int) cube.colormap[index].red;
  914.       green_error=(int) green-(int) cube.colormap[index].green;
  915.       blue_error=(int) blue-(int) cube.colormap[index].blue;
  916.       q->index=index;
  917.       q+=step;
  918.       /*
  919.         Propagate the error in these proportions:
  920.                 Q     7/16
  921.           3/16  5/16  1/16
  922.       */
  923.       cs->red=0;
  924.       cs->green=0;
  925.       cs->blue=0;
  926.       cs+=step;
  927.       cs->red+=7*red_error;
  928.       cs->green+=7*green_error;
  929.       cs->blue+=7*blue_error;
  930.       ns-=step;
  931.       ns->red+=3*red_error;
  932.       ns->green+=3*green_error;
  933.       ns->blue+=3*blue_error;
  934.       ns+=step;
  935.       ns->red+=5*red_error;
  936.       ns->green+=5*green_error;
  937.       ns->blue+=5*blue_error;
  938.       ns+=step;
  939.       ns->red+=red_error;
  940.       ns->green+=green_error;
  941.       ns->blue+=blue_error;
  942.     }
  943.   }
  944.   /*
  945.     Free up memory.
  946.   */
  947.   (void) free((char *) range_table);
  948.   (void) free((char *) error);
  949.   (void) free((char *) cache);
  950.   return(False);
  951. }
  952.  
  953. /*
  954. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  955. %                                                                             %
  956. %                                                                             %
  957. %                                                                             %
  958. %  I n i t i a l i z e C u b e                                                %
  959. %                                                                             %
  960. %                                                                             %
  961. %                                                                             %
  962. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  963. %
  964. %  Function InitializeCube initialize the Cube data structure.
  965. %
  966. %  The format of the InitializeCube routine is:
  967. %
  968. %      InitializeCube(number_colors,tree_depth,number_pixels,optimal)
  969. %
  970. %  A description of each parameter follows.
  971. %
  972. %    o number_colors: This integer value indicates the maximum number of
  973. %      colors in the quantized image or colormap.  Here we use this value
  974. %      to determine the depth of the color description tree.
  975. %
  976. %    o tree_depth: Normally, this integer value is zero or one.  A zero or
  977. %      one tells Quantize to choose a optimal tree depth of Log4(number_colors).
  978. %      A tree of this depth generally allows the best representation of the
  979. %      reference image with the least amount of memory and the fastest
  980. %      computational speed.  In some cases, such as an image with low color
  981. %      dispersion (a few number of colors), a value other than
  982. %      Log4(number_colors) is required.  To expand the color tree completely,
  983. %      use a value of 8.
  984. %
  985. %    o number_pixels: Specifies the number of individual pixels in the image.
  986. %
  987. %    o optimal: An unsigned integer value greater than zero indicates that
  988. %      the optimal representation of the reference image should be returned.
  989. %
  990. */
  991. static void InitializeCube(number_colors,tree_depth,number_pixels,optimal)
  992. unsigned int
  993.   number_colors,
  994.   tree_depth,
  995.   number_pixels,
  996.   optimal;
  997. {
  998.   char
  999.     c;
  1000.  
  1001.   register int
  1002.     i;
  1003.  
  1004.   static int
  1005.     log4[6] = {4, 16, 64, 256, 1024, ~0};
  1006.  
  1007.   unsigned int
  1008.     bits,
  1009.     level,
  1010.     max_shift;
  1011.  
  1012.   /*
  1013.     Initialize tree to describe color cube.  Depth is: Log4(colormap size)+2;
  1014.   */
  1015.   cube.node_queue=(Nodes *) NULL;
  1016.   cube.nodes=0;
  1017.   cube.free_nodes=0;
  1018.   if (tree_depth > 1)
  1019.     cube.depth=Min(tree_depth,8);
  1020.   else
  1021.     {
  1022.       for (i=0; i < 6; i++)
  1023.         if (number_colors <= log4[i])
  1024.           break;
  1025.       cube.depth=i+2;
  1026.       if (!optimal)
  1027.         cube.depth--;
  1028.     }
  1029.   /*
  1030.     Initialize the shift values.
  1031.   */
  1032.   c=1;
  1033.   for (bits=0; c != (char) 0; bits++)
  1034.     c<<=1;
  1035.   for (max_shift=sizeof(unsigned int)*bits; number_pixels != 0; max_shift--)
  1036.     number_pixels>>=1;
  1037.   for (level=0; level <= cube.depth; level++)
  1038.   {
  1039.     cube.shift[level]=max_shift;
  1040.     if (max_shift != 0)
  1041.       max_shift--;
  1042.   }
  1043.   /*
  1044.     Initialize root node.
  1045.   */
  1046.   cube.root=InitializeNode(0,0,(Node *) NULL,(MaxRGB+1) >> 1,(MaxRGB+1) >> 1,
  1047.     (MaxRGB+1) >> 1);
  1048.   if (cube.root == (Node *) NULL)
  1049.     {
  1050.       Warning("Unable to quantize image","Memory allocation failed");
  1051.       exit(1);
  1052.     }
  1053.   cube.root->parent=cube.root;
  1054.   cube.root->number_colors=(unsigned long) (~0);
  1055.   cube.colors=0;
  1056.   /*
  1057.     Initialize the square values.
  1058.   */
  1059.   for (i=(-MaxRGB); i <= MaxRGB; i++)
  1060.     cube.squares[i+MaxRGB]=i*i;
  1061. }
  1062.  
  1063. /*
  1064. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1065. %                                                                             %
  1066. %                                                                             %
  1067. %                                                                             %
  1068. %  I n i t i a l i z e N o d e                                                %
  1069. %                                                                             %
  1070. %                                                                             %
  1071. %                                                                             %
  1072. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1073. %
  1074. %  Function InitializeNode allocates memory for a new node in the color cube
  1075. %  tree and presets all fields to zero.
  1076. %
  1077. %  The format of the InitializeNode routine is:
  1078. %
  1079. %      node=InitializeNode(node,id,level,mid_red,mid_green,mid_blue)
  1080. %
  1081. %  A description of each parameter follows.
  1082. %
  1083. %    o node: The InitializeNode routine returns this integer address.
  1084. %
  1085. %    o id: Specifies the child number of the node.
  1086. %
  1087. %    o level: Specifies the level in the classification the node resides.
  1088. %
  1089. %    o mid_red: Specifies the mid point of the red axis for this node.
  1090. %
  1091. %    o mid_green: Specifies the mid point of the green axis for this node.
  1092. %
  1093. %    o mid_blue: Specifies the mid point of the blue axis for this node.
  1094. %
  1095. %
  1096. */
  1097. static Node *InitializeNode(id,level,parent,mid_red,mid_green,mid_blue)
  1098. unsigned int
  1099.   id,
  1100.   level;
  1101.  
  1102. Node
  1103.   *parent;
  1104.  
  1105. unsigned int
  1106.   mid_red,
  1107.   mid_green,
  1108.   mid_blue;
  1109. {
  1110.   register int
  1111.     i;
  1112.  
  1113.   register Node
  1114.     *node;
  1115.  
  1116.   if (cube.free_nodes == 0)
  1117.     {
  1118.       register Nodes
  1119.         *nodes;
  1120.  
  1121.       /*
  1122.         Allocate a new nodes of nodes.
  1123.       */
  1124.       nodes=(Nodes *) malloc(sizeof(Nodes));
  1125.       if (nodes == (Nodes *) NULL)
  1126.         return((Node *) NULL);
  1127.       nodes->next=cube.node_queue;
  1128.       cube.node_queue=nodes;
  1129.       cube.next_node=nodes->nodes;
  1130.       cube.free_nodes=NodesInAList;
  1131.     }
  1132.   cube.nodes++;
  1133.   cube.free_nodes--;
  1134.   node=cube.next_node++;
  1135.   node->parent=parent;
  1136.   for (i=0; i < 8; i++)
  1137.     node->child[i]=(Node *) NULL;
  1138.   node->id=id;
  1139.   node->level=level;
  1140.   node->children=0;
  1141.   node->mid_red=mid_red;
  1142.   node->mid_green=mid_green;
  1143.   node->mid_blue=mid_blue;
  1144.   node->number_colors=0;
  1145.   node->number_unique=0;
  1146.   node->total_red=0;
  1147.   node->total_green=0;
  1148.   node->total_blue=0;
  1149.   return(node);
  1150. }
  1151.  
  1152. /*
  1153. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1154. %                                                                             %
  1155. %                                                                             %
  1156. %                                                                             %
  1157. %  P r u n e C h i l d                                                        %
  1158. %                                                                             %
  1159. %                                                                             %
  1160. %                                                                             %
  1161. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1162. %
  1163. %  Function PruneChild deletes the given node and merges its statistics into
  1164. %  its parent.
  1165. %
  1166. %  The format of the PruneSubtree routine is:
  1167. %
  1168. %      PruneChild(node)
  1169. %
  1170. %  A description of each parameter follows.
  1171. %
  1172. %    o node: pointer to node in color cube tree that is to be pruned.
  1173. %
  1174. %
  1175. */
  1176. static void PruneChild(node)
  1177. register Node
  1178.   *node;
  1179. {
  1180.   register Node
  1181.     *parent;
  1182.  
  1183.   /*
  1184.     Merge color statistics into parent.
  1185.   */
  1186.   parent=node->parent;
  1187.   parent->children&=~(1 << node->id);
  1188.   parent->number_unique+=node->number_unique;
  1189.   parent->total_red+=node->total_red;
  1190.   parent->total_green+=node->total_green;
  1191.   parent->total_blue+=node->total_blue;
  1192.   cube.nodes--;
  1193. }
  1194.  
  1195. /*
  1196. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1197. %                                                                             %
  1198. %                                                                             %
  1199. %                                                                             %
  1200. %  P r u n e L e v e l                                                        %
  1201. %                                                                             %
  1202. %                                                                             %
  1203. %                                                                             %
  1204. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1205. %
  1206. %  Procedure PruneLevel deletes all nodes at the bottom level of the color
  1207. %  tree merging their color statistics into their parent node.
  1208. %
  1209. %  The format of the PruneLevel routine is:
  1210. %
  1211. %      PruneLevel(node)
  1212. %
  1213. %  A description of each parameter follows.
  1214. %
  1215. %    o node: pointer to node in color cube tree that is to be pruned.
  1216. %
  1217. %
  1218. */
  1219. static void PruneLevel(node)
  1220. register Node
  1221.   *node;
  1222. {
  1223.   register int
  1224.     id;
  1225.  
  1226.   /*
  1227.     Traverse any children.
  1228.   */
  1229.   if (node->children != 0)
  1230.     for (id=0; id < 8; id++)
  1231.       if (node->children & (1 << id))
  1232.         PruneLevel(node->child[id]);
  1233.   if (node->level == cube.depth)
  1234.     PruneChild(node);
  1235. }
  1236.  
  1237. /*
  1238. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1239. %                                                                             %
  1240. %                                                                             %
  1241. %                                                                             %
  1242. %  R e d u c e                                                                %
  1243. %                                                                             %
  1244. %                                                                             %
  1245. %                                                                             %
  1246. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1247. %
  1248. %  Function Reduce traverses the color cube tree and prunes any node whose
  1249. %  number of colors fall below a particular threshold.
  1250. %
  1251. %  The format of the Reduce routine is:
  1252. %
  1253. %      Reduce(node)
  1254. %
  1255. %  A description of each parameter follows.
  1256. %
  1257. %    o node: pointer to node in color cube tree that is to be pruned.
  1258. %
  1259. %
  1260. */
  1261. static void Reduce(node)
  1262. register Node
  1263.   *node;
  1264. {
  1265.   register unsigned int
  1266.     id;
  1267.  
  1268.   /*
  1269.     Traverse any children.
  1270.   */
  1271.   if (node->children != 0)
  1272.     for (id=0; id < 8; id++)
  1273.       if (node->children & (1 << id))
  1274.         Reduce(node->child[id]);
  1275.   /*
  1276.     Node is a colormap entry if it has unique colors.
  1277.   */
  1278.   if (node->number_unique > 0)
  1279.     cube.colors++;
  1280.   /*
  1281.     Find minimum pruning threshold.
  1282.   */
  1283.   if (node->number_colors < cube.next_pruning_threshold)
  1284.     cube.next_pruning_threshold=node->number_colors;
  1285.   if (node->number_colors <= cube.pruning_threshold)
  1286.     PruneChild(node); /* Node has a sub-threshold color count */
  1287. }
  1288.  
  1289. /*
  1290. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1291. %                                                                             %
  1292. %                                                                             %
  1293. %                                                                             %
  1294. %  R e d u c t i o n                                                          %
  1295. %                                                                             %
  1296. %                                                                             %
  1297. %                                                                             %
  1298. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1299. %
  1300. %  Function Reduction repeatedly prunes the tree until the number of nodes
  1301. %  with n2 > 0 is less than or equal to the maximum number of colors allowed
  1302. %  in the output image.  On any given iteration over the tree, it selects
  1303. %  those nodes whose n1  count is minimal for pruning and merges their
  1304. %  color statistics upward. It uses a pruning threshold, ns, to govern
  1305. %  node selection as follows:
  1306. %
  1307. %    ns = 0
  1308. %    while number of nodes with (n2 > 0) > required maximum number of colors
  1309. %      prune all nodes such that n1 <= ns
  1310. %      Set ns to minimum n1 in remaining nodes
  1311. %
  1312. %  When a node to be pruned has offspring, the pruning procedure invokes
  1313. %  itself recursively in order to prune the tree from the leaves upward.
  1314. %  n2,  Sr, Sg,  and  Sb in a node being pruned are always added to the
  1315. %  corresponding data in that node's parent.  This retains the pruned
  1316. %  node's color characteristics for later averaging.
  1317. %
  1318. %  For each node, n2 pixels exist for which that node represents the
  1319. %  smallest volume in RGB space containing those pixel's colors.  When n2
  1320. %  > 0 the node will uniquely define a color in the output image. At the
  1321. %  beginning of reduction,  n2 = 0  for all nodes except a the leaves of
  1322. %  the tree which represent colors present in the input image.
  1323. %
  1324. %  The other pixel count, n1, indicates the total number of colors
  1325. %  within the cubic volume which the node represents.  This includes n1 -
  1326. %  n2  pixels whose colors should be defined by nodes at a lower level in
  1327. %  the tree.
  1328. %
  1329. %  The format of the Reduction routine is:
  1330. %
  1331. %      Reduction(number_colors)
  1332. %
  1333. %  A description of each parameter follows.
  1334. %
  1335. %    o number_colors: This integer value indicates the maximum number of
  1336. %      colors in the quantized image or colormap.  The actual number of
  1337. %      colors allocated to the colormap may be less than this value, but
  1338. %      never more.  Note, the number of colors is restricted to a value
  1339. %      less than or equal to 65536 if the continuous_tone parameter has a
  1340. %      value of zero.
  1341. %
  1342. %
  1343. */
  1344. static void Reduction(number_colors)
  1345. unsigned int
  1346.   number_colors;
  1347. {
  1348.   cube.next_pruning_threshold=1;
  1349.   while (cube.colors > number_colors)
  1350.   {
  1351.     cube.pruning_threshold=cube.next_pruning_threshold;
  1352.     cube.next_pruning_threshold=cube.root->number_colors-1;
  1353.     cube.colors=0;
  1354.     Reduce(cube.root);
  1355.   }
  1356. }
  1357.  
  1358. /*
  1359. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1360. %                                                                             %
  1361. %                                                                             %
  1362. %                                                                             %
  1363. %  Q u a n t i z a t i o n E r r o r                                          %
  1364. %                                                                             %
  1365. %                                                                             %
  1366. %                                                                             %
  1367. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1368. %
  1369. %  Function QuantizationError measures the difference between the original
  1370. %  and quantized images.  This difference is the total quantization error.
  1371. %  The error is computed by summing over all pixels in an image the distance
  1372. %  squared in RGB space between each reference pixel value and its quantized
  1373. %  value.
  1374. %
  1375. %  The format of the QuantizationError routine is:
  1376. %
  1377. %      QuantizationError(image,mean_error_per_pixel,
  1378. %        normalized_mean_square_error,normalized_maximum_square_error)
  1379. %
  1380. %  A description of each parameter follows.
  1381. %
  1382. %    o image: The address of a byte (8 bits) array of run-length
  1383. %      encoded pixel data of your reference image.  The sum of the
  1384. %      run-length counts in the reference image must be equal to or exceed
  1385. %      the number of pixels.
  1386. %
  1387. %    o mean_error_per_pixel: The address of an integer value.  The value
  1388. %      returned is the mean error for any single pixel in the image.
  1389. %
  1390. %    o normalized_mean_square_error: The address of a real value.  The value
  1391. %      returned is the normalized mean quantization error for any single
  1392. %      pixel in the image.  This distance measure is normalized to a
  1393. %      range between 0 and 1.  It is independent of the range of red,
  1394. %      green, and blue values in your image.
  1395. %
  1396. %    o normalized_maximum_square_error: The address of a real value.  The value
  1397. %      returned is the normalized maximum quantization error for any
  1398. %      single pixel in the image.  This distance measure is normalized to
  1399. %      a range between 0 and 1.  It is independent of the range of red,
  1400. %      green, and blue values in your image.
  1401. %
  1402. %
  1403. */
  1404. void QuantizationError(image,mean_error_per_pixel,normalized_mean_square_error,
  1405.   normalized_maximum_square_error)
  1406. Image
  1407.   *image;
  1408.  
  1409. unsigned int
  1410.   *mean_error_per_pixel;
  1411.  
  1412. double
  1413.   *normalized_mean_square_error,
  1414.   *normalized_maximum_square_error;
  1415. {
  1416.   register int
  1417.     i;
  1418.  
  1419.   register RunlengthPacket
  1420.     *p;
  1421.  
  1422.   register unsigned int
  1423.     blue_distance,
  1424.     green_distance,
  1425.     red_distance;
  1426.  
  1427.   unsigned long
  1428.     distance,
  1429.     maximum_error_per_pixel,
  1430.     total_error;
  1431.  
  1432.   /*
  1433.     For each pixel, collect error statistics.
  1434.   */
  1435.   for (i=(-MaxRGB); i <= MaxRGB; i++)
  1436.     cube.squares[i+MaxRGB]=i*i;
  1437.   maximum_error_per_pixel=0;
  1438.   total_error=0;
  1439.   p=image->pixels;
  1440.   for (i=0; i < image->packets; i++)
  1441.   {
  1442.     red_distance=(int) p->red-(int) image->colormap[p->index].red+MaxRGB;
  1443.     green_distance=(int) p->green-(int) image->colormap[p->index].green+MaxRGB;
  1444.     blue_distance=(int) p->blue-(int) image->colormap[p->index].blue+MaxRGB;
  1445.     distance=cube.squares[red_distance]+cube.squares[green_distance]+
  1446.       cube.squares[blue_distance];
  1447.     total_error+=(distance*(p->length+1));
  1448.     if (distance > maximum_error_per_pixel)
  1449.       maximum_error_per_pixel=distance;
  1450.     p++;
  1451.   }
  1452.   /*
  1453.     Compute final error statistics.
  1454.   */
  1455.   *mean_error_per_pixel=(unsigned int) total_error/(image->columns*image->rows);
  1456.   *normalized_mean_square_error=((double) *mean_error_per_pixel)/
  1457.     (3.0*(MaxRGB+1)*(MaxRGB+1));
  1458.   *normalized_maximum_square_error=((double) maximum_error_per_pixel)/
  1459.     (3.0*(MaxRGB+1)*(MaxRGB+1));
  1460. }
  1461.  
  1462. /*
  1463. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1464. %                                                                             %
  1465. %                                                                             %
  1466. %                                                                             %
  1467. %  Q u a n t i z e I m a g e                                                  %
  1468. %                                                                             %
  1469. %                                                                             %
  1470. %                                                                             %
  1471. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1472. %
  1473. %  Function QuantizeImage analyzes the colors within a reference image and
  1474. %  chooses a fixed number of colors to represent the image.  The goal of the
  1475. %  algorithm is to minimize the difference between the input and output image
  1476. %  while minimizing the processing time.
  1477. %
  1478. %  The format of the QuantizeImage routine is:
  1479. %
  1480. %      colors=QuantizeImage(image,number_colors,tree_depth,dither,optimal)
  1481. %
  1482. %  A description of each parameter follows.
  1483. %
  1484. %    o colors: The QuantizeImage function returns this integer
  1485. %      value.  It is the actual number of colors allocated in the
  1486. %      colormap.  Note, the actual number of colors allocated may be less
  1487. %      than the number of colors requested, but never more.
  1488. %
  1489. %    o image: Specifies a pointer to an Image structure;  returned from
  1490. %      ReadImage.
  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
  1494. %      colors allocated to the colormap may be less than this value, but
  1495. %      never more.  Note, the number of colors is restricted to a value
  1496. %      less than or equal to 65536 if the continuous_tone parameter has a
  1497. %      value of zero.
  1498. %
  1499. %    o tree_depth: Normally, this integer value is zero or one.  A zero or
  1500. %      one tells Quantize to choose a optimal tree depth of
  1501. %      Log4(number_colors).  A tree of this depth generally allows the best
  1502. %      representation of the reference image with the least amount of memory
  1503. %      and the fastest computational speed.  In some cases, such as an image
  1504. %      with low color dispersion (a few number of colors), a value other than
  1505. %      Log4(number_colors) is required.  To expand the color tree completely,
  1506. %      use a value of 8.
  1507. %
  1508. %    o dither: Set this integer value to something other than zero to
  1509. %      dither the quantized image.  The basic strategy of dithering is to
  1510. %      trade intensity resolution for spatial resolution by averaging the
  1511. %      intensities of several neighboring pixels.  Images which suffer
  1512. %      from severe contouring when quantized can be improved with the
  1513. %      technique of dithering.  Severe contouring generally occurs when
  1514. %      quantizing to very few colors, or to a poorly-chosen colormap.
  1515. %      Note, dithering is a computationally expensive process and will
  1516. %      increase processing time significantly.
  1517. %
  1518. %    o colorspace: An unsigned integer value that indicates the colorspace.
  1519. %      Empirical evidence suggests that distances in YUV or YIQ correspond to
  1520. %      perceptual color differences more closely than do distances in RGB
  1521. %      space.  The image is then returned to RGB colorspace after color
  1522. %      reduction.
  1523. %
  1524. %    o optimal: An unsigned integer value greater than zero indicates that
  1525. %      the optimal representation of the reference image should be returned.
  1526. %
  1527. %
  1528. */
  1529. void QuantizeImage(image,number_colors,tree_depth,dither,colorspace,optimal)
  1530. Image
  1531.   *image;
  1532.  
  1533. unsigned int
  1534.   number_colors,
  1535.   tree_depth,
  1536.   dither,
  1537.   colorspace,
  1538.   optimal;
  1539. {
  1540.   Nodes
  1541.     *nodes;
  1542.  
  1543.   /*
  1544.     Reduce the number of colors in the continuous tone image.
  1545.   */
  1546.   if (number_colors > MaxColormapSize)
  1547.     number_colors=MaxColormapSize;
  1548.   InitializeCube(number_colors,tree_depth,image->columns*image->rows,optimal);
  1549.   if (!dither || !optimal)
  1550.     if (image->packets == (image->columns*image->rows))
  1551.       CompressImage(image);
  1552.   if (colorspace != RGBColorspace)
  1553.     RGBTransformImage(image,colorspace);
  1554.   Classification(image);
  1555.   Reduction(number_colors);
  1556.   Assignment(image,dither,colorspace,optimal);
  1557.   if (colorspace != RGBColorspace)
  1558.     TransformRGBImage(image,colorspace);
  1559.   /*
  1560.     Release color cube tree storage.
  1561.   */
  1562.   do
  1563.   {
  1564.     nodes=cube.node_queue->next;
  1565.     (void) free((char *) cube.node_queue);
  1566.     cube.node_queue=nodes;
  1567.   }
  1568.   while (cube.node_queue != (Nodes *) NULL);
  1569. }
  1570.  
  1571. /*
  1572. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1573. %                                                                             %
  1574. %                                                                             %
  1575. %                                                                             %
  1576. %   Q u a n t i z e I m a g e s                                               %
  1577. %                                                                             %
  1578. %                                                                             %
  1579. %                                                                             %
  1580. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1581. %
  1582. %  QuantizeImages analyzes the colors within a set of reference images and
  1583. %  chooses a fixed number of colors to represent the set.  The goal of the
  1584. %  algorithm is to minimize the difference between the input and output images
  1585. %  while minimizing the processing time.
  1586. %
  1587. %  The format of the QuantizeImages routine is:
  1588. %
  1589. %      QuantizeImages(images,number_images,number_colors,tree_depth,dither,
  1590. %        optimal)
  1591. %
  1592. %  A description of each parameter follows:
  1593. %
  1594. %    o images: Specifies a pointer to a set of Image structures.
  1595. %
  1596. %    o number_images:  Specifies an unsigned integer representing the number
  1597. %      images in the image set.
  1598. %
  1599. %    o colormap_image: Specifies a pointer to a Image structure.  Reduce
  1600. %      images to a set of colors represented by this image.
  1601. %
  1602. %    o number_colors: This integer value indicates the maximum number of
  1603. %      colors in the quantized image or colormap.  The actual number of colors
  1604. %      allocated to the colormap may be less than this value, but never more.
  1605. %      Note, the number of colors is restricted to a value less than or equal
  1606. %      to 65536 if the quantized image is not DirectClass.
  1607. %
  1608. %    o tree_depth: Normally, this integer value is zero or one.  A zero or
  1609. %      one tells QUANTIZE to choose a optimal tree depth.  An optimal depth
  1610. %      generally allows the best representation of the reference image with the
  1611. %      fastest computational speed and the least amount of memory.  However,
  1612. %      the default depth is inappropriate for some images.  To assure the best
  1613. %      representation, try values between 2 and 8 for this parameter.
  1614. %
  1615. %    o dither: Set this integer value to something other than zero to
  1616. %      dither the quantized image.  The basic strategy of dithering is to
  1617. %      trade intensity resolution for spatial resolution by averaging the
  1618. %      intensities of several neighboring pixels.  Images which suffer
  1619. %      from severe contouring when quantized can be improved with the
  1620. %      technique of dithering.  Severe contouring generally occurs when
  1621. %      quantizing to very few colors, or to a poorly-chosen colormap.
  1622. %      Note, dithering is a computationally expensive process and will
  1623. %      increase processing time significantly.
  1624. %
  1625. %    o colorspace: An unsigned integer value that indicates the colorspace.
  1626. %      Empirical evidence suggests that distances in YUV or YIQ correspond to
  1627. %      perceptual color differences more closely than do distances in RGB
  1628. %      space.  The image is then returned to RGB colorspace after color
  1629. %      reduction.
  1630. %
  1631. %    o optimal: An unsigned integer value greater than zero indicates that
  1632. %      the optimal representation of the reference image should be returned.
  1633. %
  1634. %
  1635. */
  1636. void QuantizeImages(images,number_images,colormap_image,number_colors,
  1637.   tree_depth,dither,colorspace,optimal)
  1638. Image
  1639.   **images;
  1640.  
  1641. unsigned int
  1642.   number_images;
  1643.  
  1644. Image
  1645.   *colormap_image;
  1646.  
  1647. unsigned int
  1648.   number_colors,
  1649.   tree_depth,
  1650.   dither,
  1651.   colorspace,
  1652.   optimal;
  1653. {
  1654.   Nodes
  1655.     *nodes;
  1656.  
  1657.   register unsigned int
  1658.     i;
  1659.  
  1660.   /*
  1661.     Reduce the number of colors in the continuous tone image sequence.
  1662.   */
  1663.   InitializeCube(number_colors,tree_depth,~0,optimal);
  1664.   if (colormap_image != (Image *) NULL)
  1665.     {
  1666.       /*
  1667.         Reduce images to a set of colors represented by the colormap image.
  1668.       */
  1669.       if (!dither || !optimal)
  1670.         if (colormap_image->packets ==
  1671.              (colormap_image->columns*colormap_image->rows))
  1672.           CompressImage(colormap_image);
  1673.       if (colorspace != RGBColorspace)
  1674.         RGBTransformImage(colormap_image,colorspace);
  1675.       Classification(colormap_image);
  1676.       if (colorspace != RGBColorspace)
  1677.         TransformRGBImage(colormap_image,colorspace);
  1678.       optimal=True;
  1679.     }
  1680.   for (i=0; i < number_images; i++)
  1681.   {
  1682.     if (!dither || !optimal)
  1683.       if (images[i]->packets == (images[i]->columns*images[i]->rows))
  1684.         CompressImage(images[i]);
  1685.     if (colorspace != RGBColorspace)
  1686.       RGBTransformImage(images[i],colorspace);
  1687.     if (colormap_image == (Image *) NULL)
  1688.       Classification(images[i]);
  1689.   }
  1690.   Reduction(number_colors);
  1691.   for (i=0; i < number_images; i++)
  1692.   {
  1693.     Assignment(images[i],dither,colorspace,optimal);
  1694.     if (colorspace != RGBColorspace)
  1695.       TransformRGBImage(images[i],colorspace);
  1696.   }
  1697.   /*
  1698.     Release color cube tree storage.
  1699.   */
  1700.   do
  1701.   {
  1702.     nodes=cube.node_queue->next;
  1703.     (void) free((char *) cube.node_queue);
  1704.     cube.node_queue=nodes;
  1705.   }
  1706.   while (cube.node_queue != (Nodes *) NULL);
  1707. }
  1708.