granicus.if.org Git - imagemagick/blob - magick/quantize.c

   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 %    MagickCore Methods to Reduce the Number of Unique Colors in an Image     %
  14 %                                                                             %
  15 %                           Software Design                                   %
  16 %                             John Cristy                                     %
  17 %                              July 1992                                      %
  18 %                                                                             %
  19 %                                                                             %
  20 %  Copyright 1999-2010 ImageMagick Studio LLC, a non-profit organization      %
  21 %  dedicated to making software imaging solutions freely available.           %
  22 %                                                                             %
  23 %  You may not use this file except in compliance with the License.  You may  %
  24 %  obtain a copy of the License at                                            %
  25 %                                                                             %
  26 %    http://www.imagemagick.org/script/license.php                            %
  27 %                                                                             %
  28 %  Unless required by applicable law or agreed to in writing, software        %
  29 %  distributed under the License is distributed on an "AS IS" BASIS,          %
  30 %  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.   %
  31 %  See the License for the specific language governing permissions and        %
  32 %  limitations under the License.                                             %
  33 %                                                                             %
  34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  35 %
  36 %  Realism in computer graphics typically requires using 24 bits/pixel to
  37 %  generate an image.  Yet many graphic display devices do not contain the
  38 %  amount of memory necessary to match the spatial and color resolution of
  39 %  the human eye.  The Quantize methods takes a 24 bit image and reduces
  40 %  the number of colors so it can be displayed on raster device with less
  41 %  bits per pixel.  In most instances, the quantized image closely
  42 %  resembles the original reference image.
  43 %
  44 %  A reduction of colors in an image is also desirable for image
  45 %  transmission and real-time animation.
  46 %
  47 %  QuantizeImage() takes a standard RGB or monochrome images and quantizes
  48 %  them down to some fixed number of colors.
  49 %
  50 %  For purposes of color allocation, an image is a set of n pixels, where
  51 %  each pixel is a point in RGB space.  RGB space is a 3-dimensional
  52 %  vector space, and each pixel, Pi,  is defined by an ordered triple of
  53 %  red, green, and blue coordinates, (Ri, Gi, Bi).
  54 %
  55 %  Each primary color component (red, green, or blue) represents an
  56 %  intensity which varies linearly from 0 to a maximum value, Cmax, which
  57 %  corresponds to full saturation of that color.  Color allocation is
  58 %  defined over a domain consisting of the cube in RGB space with opposite
  59 %  vertices at (0,0,0) and (Cmax, Cmax, Cmax).  QUANTIZE requires Cmax =
  60 %  255.
  61 %
  62 %  The algorithm maps this domain onto a tree in which each node
  63 %  represents a cube within that domain.  In the following discussion
  64 %  these cubes are defined by the coordinate of two opposite vertices:
  65 %  The vertex nearest the origin in RGB space and the vertex farthest from
  66 %  the origin.
  67 %
  68 %  The tree's root node represents the entire domain, (0,0,0) through
  69 %  (Cmax,Cmax,Cmax).  Each lower level in the tree is generated by
  70 %  subdividing one node's cube into eight smaller cubes of equal size.
  71 %  This corresponds to bisecting the parent cube with planes passing
  72 %  through the midpoints of each edge.
  73 %
  74 %  The basic algorithm operates in three phases: Classification,
  75 %  Reduction, and Assignment.  Classification builds a color description
  76 %  tree for the image.  Reduction collapses the tree until the number it
  77 %  represents, at most, the number of colors desired in the output image.
  78 %  Assignment defines the output image's color map and sets each pixel's
  79 %  color by restorage_class in the reduced tree.  Our goal is to minimize
  80 %  the numerical discrepancies between the original colors and quantized
  81 %  colors (quantization error).
  82 %
  83 %  Classification begins by initializing a color description tree of
  84 %  sufficient depth to represent each possible input color in a leaf.
  85 %  However, it is impractical to generate a fully-formed color description
  86 %  tree in the storage_class phase for realistic values of Cmax.  If
  87 %  colors components in the input image are quantized to k-bit precision,
  88 %  so that Cmax= 2k-1, the tree would need k levels below the root node to
  89 %  allow representing each possible input color in a leaf.  This becomes
  90 %  prohibitive because the tree's total number of nodes is 1 +
  91 %  sum(i=1, k, 8k).
  92 %
  93 %  A complete tree would require 19,173,961 nodes for k = 8, Cmax = 255.
  94 %  Therefore, to avoid building a fully populated tree, QUANTIZE: (1)
  95 %  Initializes data structures for nodes only as they are needed;  (2)
  96 %  Chooses a maximum depth for the tree as a function of the desired
  97 %  number of colors in the output image (currently log2(colormap size)).
  98 %
  99 %  For each pixel in the input image, storage_class scans downward from
 100 %  the root of the color description tree.  At each level of the tree it
 101 %  identifies the single node which represents a cube in RGB space
 102 %  containing the pixel's color.  It updates the following data for each
 103 %  such node:
 104 %
 105 %    n1: Number of pixels whose color is contained in the RGB cube which
 106 %    this node represents;
 107 %
 108 %    n2: Number of pixels whose color is not represented in a node at
 109 %    lower depth in the tree;  initially,  n2 = 0 for all nodes except
 110 %    leaves of the tree.
 111 %
 112 %    Sr, Sg, Sb: Sums of the red, green, and blue component values for all
 113 %    pixels not classified at a lower depth. The combination of these sums
 114 %    and n2  will ultimately characterize the mean color of a set of
 115 %    pixels represented by this node.
 116 %
 117 %    E: the distance squared in RGB space between each pixel contained
 118 %    within a node and the nodes' center.  This represents the
 119 %    quantization error for a node.
 120 %
 121 %  Reduction repeatedly prunes the tree until the number of nodes with n2
 122 %  > 0 is less than or equal to the maximum number of colors allowed in
 123 %  the output image.  On any given iteration over the tree, it selects
 124 %  those nodes whose E count is minimal for pruning and merges their color
 125 %  statistics upward. It uses a pruning threshold, Ep, to govern node
 126 %  selection as follows:
 127 %
 128 %    Ep = 0
 129 %    while number of nodes with (n2 > 0) > required maximum number of colors
 130 %      prune all nodes such that E <= Ep
 131 %      Set Ep to minimum E in remaining nodes
 132 %
 133 %  This has the effect of minimizing any quantization error when merging
 134 %  two nodes together.
 135 %
 136 %  When a node to be pruned has offspring, the pruning procedure invokes
 137 %  itself recursively in order to prune the tree from the leaves upward.
 138 %  n2,  Sr, Sg,  and  Sb in a node being pruned are always added to the
 139 %  corresponding data in that node's parent.  This retains the pruned
 140 %  node's color characteristics for later averaging.
 141 %
 142 %  For each node, n2 pixels exist for which that node represents the
 143 %  smallest volume in RGB space containing those pixel's colors.  When n2
 144 %  > 0 the node will uniquely define a color in the output image. At the
 145 %  beginning of reduction,  n2 = 0  for all nodes except a the leaves of
 146 %  the tree which represent colors present in the input image.
 147 %
 148 %  The other pixel count, n1, indicates the total number of colors within
 149 %  the cubic volume which the node represents.  This includes n1 - n2
 150 %  pixels whose colors should be defined by nodes at a lower level in the
 151 %  tree.
 152 %
 153 %  Assignment generates the output image from the pruned tree.  The output
 154 %  image consists of two parts: (1)  A color map, which is an array of
 155 %  color descriptions (RGB triples) for each color present in the output
 156 %  image;  (2)  A pixel array, which represents each pixel as an index
 157 %  into the color map array.
 158 %
 159 %  First, the assignment phase makes one pass over the pruned color
 160 %  description tree to establish the image's color map.  For each node
 161 %  with n2  > 0, it divides Sr, Sg, and Sb by n2 .  This produces the mean
 162 %  color of all pixels that classify no lower than this node.  Each of
 163 %  these colors becomes an entry in the color map.
 164 %
 165 %  Finally,  the assignment phase reclassifies each pixel in the pruned
 166 %  tree to identify the deepest node containing the pixel's color.  The
 167 %  pixel's value in the pixel array becomes the index of this node's mean
 168 %  color in the color map.
 169 %
 170 %  This method is based on a similar algorithm written by Paul Raveling.
 171 %
 172 */
 173 \f
 174 /*
 175   Include declarations.
 176 */
 177 #include "magick/studio.h"
 178 #include "magick/cache-view.h"
 179 #include "magick/color.h"
 180 #include "magick/color-private.h"
 181 #include "magick/colormap.h"
 182 #include "magick/colorspace.h"
 183 #include "magick/enhance.h"
 184 #include "magick/exception.h"
 185 #include "magick/exception-private.h"
 186 #include "magick/histogram.h"
 187 #include "magick/image.h"
 188 #include "magick/image-private.h"
 189 #include "magick/list.h"
 190 #include "magick/memory_.h"
 191 #include "magick/monitor.h"
 192 #include "magick/monitor-private.h"
 193 #include "magick/option.h"
 194 #include "magick/pixel-private.h"
 195 #include "magick/quantize.h"
 196 #include "magick/quantum.h"
 197 #include "magick/string_.h"
 198 \f
 199 /*
 200   Define declarations.
 201 */
 202 #define CacheShift  2
 203 #define ErrorQueueLength  16
 204 #define MaxNodes  266817
 205 #define MaxTreeDepth  8
 206 #define NodesInAList  1920
 207 \f
 208 /*
 209   Typdef declarations.
 210 */
 211 typedef struct _RealPixelPacket
 212 {
 213   MagickRealType
 214     red,
 215     green,
 216     blue,
 217     opacity;
 218 } RealPixelPacket;
 219
 220 typedef struct _NodeInfo
 221 {
 222   struct _NodeInfo
 223     *parent,
 224     *child[16];
 225
 226   MagickSizeType
 227     number_unique;
 228
 229   RealPixelPacket
 230     total_color;
 231
 232   MagickRealType
 233     quantize_error;
 234
 235   size_t
 236     color_number,
 237     id,
 238     level;
 239 } NodeInfo;
 240
 241 typedef struct _Nodes
 242 {
 243   NodeInfo
 244     *nodes;
 245
 246   struct _Nodes
 247     *next;
 248 } Nodes;
 249
 250 typedef struct _CubeInfo
 251 {
 252   NodeInfo
 253     *root;
 254
 255   size_t
 256     colors,
 257     maximum_colors;
 258
 259   ssize_t
 260     transparent_index;
 261
 262   MagickSizeType
 263     transparent_pixels;
 264
 265   RealPixelPacket
 266     target;
 267
 268   MagickRealType
 269     distance,
 270     pruning_threshold,
 271     next_threshold;
 272
 273   size_t
 274     nodes,
 275     free_nodes,
 276     color_number;
 277
 278   NodeInfo
 279     *next_node;
 280
 281   Nodes
 282     *node_queue;
 283
 284   ssize_t
 285     *cache;
 286
 287   RealPixelPacket
 288     error[ErrorQueueLength];
 289
 290   MagickRealType
 291     weights[ErrorQueueLength];
 292
 293   QuantizeInfo
 294     *quantize_info;
 295
 296   MagickBooleanType
 297     associate_alpha;
 298
 299   ssize_t
 300     x,
 301     y;
 302
 303   size_t
 304     depth;
 305
 306   MagickOffsetType
 307     offset;
 308
 309   MagickSizeType
 310     span;
 311 } CubeInfo;
 312 \f
 313 /*
 314   Method prototypes.
 315 */
 316 static CubeInfo
 317   *GetCubeInfo(const QuantizeInfo *,const size_t,const size_t);
 318
 319 static NodeInfo
 320   *GetNodeInfo(CubeInfo *,const size_t,const size_t,NodeInfo *);
 321
 322 static MagickBooleanType
 323   AssignImageColors(Image *,CubeInfo *),
 324   ClassifyImageColors(CubeInfo *,const Image *,ExceptionInfo *),
 325   DitherImage(Image *,CubeInfo *),
 326   SetGrayscaleImage(Image *);
 327
 328 static size_t
 329   DefineImageColormap(Image *,CubeInfo *,NodeInfo *);
 330
 331 static void
 332   ClosestColor(const Image *,CubeInfo *,const NodeInfo *),
 333   DestroyCubeInfo(CubeInfo *),
 334   PruneLevel(const Image *,CubeInfo *,const NodeInfo *),
 335   PruneToCubeDepth(const Image *,CubeInfo *,const NodeInfo *),
 336   ReduceImageColors(const Image *,CubeInfo *);
 337 \f
 338 /*
 339 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 340 %                                                                             %
 341 %                                                                             %
 342 %                                                                             %
 343 %   A c q u i r e Q u a n t i z e I n f o                                     %
 344 %                                                                             %
 345 %                                                                             %
 346 %                                                                             %
 347 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 348 %
 349 %  AcquireQuantizeInfo() allocates the QuantizeInfo structure.
 350 %
 351 %  The format of the AcquireQuantizeInfo method is:
 352 %
 353 %      QuantizeInfo *AcquireQuantizeInfo(const ImageInfo *image_info)
 354 %
 355 %  A description of each parameter follows:
 356 %
 357 %    o image_info: the image info.
 358 %
 359 */
 360 MagickExport QuantizeInfo *AcquireQuantizeInfo(const ImageInfo *image_info)
 361 {
 362   QuantizeInfo
 363     *quantize_info;
 364
 365   quantize_info=(QuantizeInfo *) AcquireAlignedMemory(1,sizeof(*quantize_info));
 366   if (quantize_info == (QuantizeInfo *) NULL)
 367     ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
 368   GetQuantizeInfo(quantize_info);
 369   if (image_info != (ImageInfo *) NULL)
 370     {
 371       const char
 372         *option;
 373
 374       quantize_info->dither=image_info->dither;
 375       option=GetImageOption(image_info,"dither");
 376       if (option != (const char *) NULL)
 377         quantize_info->dither_method=(DitherMethod) ParseMagickOption(
 378           MagickDitherOptions,MagickFalse,option);
 379       quantize_info->measure_error=image_info->verbose;
 380     }
 381   return(quantize_info);
 382 }
 383 \f
 384 /*
 385 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 386 %                                                                             %
 387 %                                                                             %
 388 %                                                                             %
 389 +   A s s i g n I m a g e C o l o r s                                         %
 390 %                                                                             %
 391 %                                                                             %
 392 %                                                                             %
 393 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 394 %
 395 %  AssignImageColors() generates the output image from the pruned tree.  The
 396 %  output image consists of two parts: (1)  A color map, which is an array
 397 %  of color descriptions (RGB triples) for each color present in the
 398 %  output image;  (2)  A pixel array, which represents each pixel as an
 399 %  index into the color map array.
 400 %
 401 %  First, the assignment phase makes one pass over the pruned color
 402 %  description tree to establish the image's color map.  For each node
 403 %  with n2  > 0, it divides Sr, Sg, and Sb by n2 .  This produces the mean
 404 %  color of all pixels that classify no lower than this node.  Each of
 405 %  these colors becomes an entry in the color map.
 406 %
 407 %  Finally,  the assignment phase reclassifies each pixel in the pruned
 408 %  tree to identify the deepest node containing the pixel's color.  The
 409 %  pixel's value in the pixel array becomes the index of this node's mean
 410 %  color in the color map.
 411 %
 412 %  The format of the AssignImageColors() method is:
 413 %
 414 %      MagickBooleanType AssignImageColors(Image *image,CubeInfo *cube_info)
 415 %
 416 %  A description of each parameter follows.
 417 %
 418 %    o image: the image.
 419 %
 420 %    o cube_info: A pointer to the Cube structure.
 421 %
 422 */
 423
 424 static inline void AssociateAlphaPixel(const CubeInfo *cube_info,
 425   const PixelPacket *pixel,RealPixelPacket *alpha_pixel)
 426 {
 427   MagickRealType
 428     alpha;
 429
 430   if ((cube_info->associate_alpha == MagickFalse) ||
 431       (pixel->opacity == OpaqueOpacity))
 432     {
 433       alpha_pixel->red=(MagickRealType) pixel->red;
 434       alpha_pixel->green=(MagickRealType) pixel->green;
 435       alpha_pixel->blue=(MagickRealType) pixel->blue;
 436       alpha_pixel->opacity=(MagickRealType) pixel->opacity;
 437       return;
 438     }
 439   alpha=(MagickRealType) (QuantumScale*(QuantumRange-pixel->opacity));
 440   alpha_pixel->red=alpha*pixel->red;
 441   alpha_pixel->green=alpha*pixel->green;
 442   alpha_pixel->blue=alpha*pixel->blue;
 443   alpha_pixel->opacity=(MagickRealType) pixel->opacity;
 444 }
 445
 446 static inline Quantum ClampToUnsignedQuantum(const MagickRealType value)
 447 {
 448   if (value <= 0.0)
 449     return((Quantum) 0);
 450   if (value >= QuantumRange)
 451     return((Quantum) QuantumRange);
 452   return((Quantum) (value+0.5));
 453 }
 454
 455 static inline size_t ColorToNodeId(const CubeInfo *cube_info,
 456   const RealPixelPacket *pixel,size_t index)
 457 {
 458   size_t
 459     id;
 460
 461   id=(size_t) (
 462     ((ScaleQuantumToChar(ClampToUnsignedQuantum(pixel->red)) >> index) & 0x1) |
 463     ((ScaleQuantumToChar(ClampToUnsignedQuantum(pixel->green)) >> index) & 0x1) << 1 |
 464     ((ScaleQuantumToChar(ClampToUnsignedQuantum(pixel->blue)) >> index) & 0x1) << 2);
 465   if (cube_info->associate_alpha != MagickFalse)
 466     id|=((ScaleQuantumToChar(ClampToUnsignedQuantum(pixel->opacity)) >> index) & 0x1)
 467       << 3;
 468   return(id);
 469 }
 470
 471 static inline MagickBooleanType IsSameColor(const Image *image,
 472   const PixelPacket *p,const PixelPacket *q)
 473 {
 474   if ((p->red != q->red) || (p->green != q->green) || (p->blue != q->blue))
 475     return(MagickFalse);
 476   if ((image->matte != MagickFalse) && (p->opacity != q->opacity))
 477     return(MagickFalse);
 478   return(MagickTrue);
 479 }
 480
 481 static MagickBooleanType AssignImageColors(Image *image,CubeInfo *cube_info)
 482 {
 483 #define AssignImageTag  "Assign/Image"
 484
 485   ssize_t
 486     y;
 487
 488   MagickBooleanType
 489     proceed;
 490
 491   RealPixelPacket
 492     pixel;
 493
 494   register ssize_t
 495     i,
 496     x;
 497
 498   register const NodeInfo
 499     *node_info;
 500
 501   ssize_t
 502     count;
 503
 504   size_t
 505     id,
 506     index;
 507
 508   /*
 509     Allocate image colormap.
 510   */
 511   if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
 512       (cube_info->quantize_info->colorspace != CMYKColorspace))
 513     (void) TransformImageColorspace((Image *) image,
 514       cube_info->quantize_info->colorspace);
 515   else
 516     if ((image->colorspace != GRAYColorspace) &&
 517         (image->colorspace != RGBColorspace) &&
 518         (image->colorspace != CMYColorspace))
 519       (void) TransformImageColorspace((Image *) image,RGBColorspace);
 520   if (AcquireImageColormap(image,cube_info->colors) == MagickFalse)
 521     ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
 522       image->filename);
 523   image->colors=0;
 524   cube_info->transparent_pixels=0;
 525   cube_info->transparent_index=(-1);
 526   (void) DefineImageColormap(image,cube_info,cube_info->root);
 527   /*
 528     Create a reduced color image.
 529   */
 530   if ((cube_info->quantize_info->dither != MagickFalse) &&
 531       (cube_info->quantize_info->dither_method != NoDitherMethod))
 532     (void) DitherImage(image,cube_info);
 533   else
 534     {
 535       ExceptionInfo
 536         *exception;
 537
 538       CacheView
 539         *image_view;
 540
 541       exception=(&image->exception);
 542       image_view=AcquireCacheView(image);
 543       for (y=0; y < (ssize_t) image->rows; y++)
 544       {
 545         register IndexPacket
 546           *restrict indexes;
 547
 548         register PixelPacket
 549           *restrict q;
 550
 551         q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,
 552           exception);
 553         if (q == (PixelPacket *) NULL)
 554           break;
 555         indexes=GetCacheViewAuthenticIndexQueue(image_view);
 556         for (x=0; x < (ssize_t) image->columns; x+=count)
 557         {
 558           /*
 559             Identify the deepest node containing the pixel's color.
 560           */
 561           for (count=1; (x+count) < (ssize_t) image->columns; count++)
 562             if (IsSameColor(image,q,q+count) == MagickFalse)
 563               break;
 564           AssociateAlphaPixel(cube_info,q,&pixel);
 565           node_info=cube_info->root;
 566           for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
 567           {
 568             id=ColorToNodeId(cube_info,&pixel,index);
 569             if (node_info->child[id] == (NodeInfo *) NULL)
 570               break;
 571             node_info=node_info->child[id];
 572           }
 573           /*
 574             Find closest color among siblings and their children.
 575           */
 576           cube_info->target=pixel;
 577           cube_info->distance=(MagickRealType) (4.0*(QuantumRange+1.0)*
 578             (QuantumRange+1.0)+1.0);
 579           ClosestColor(image,cube_info,node_info->parent);
 580           index=cube_info->color_number;
 581           for (i=0; i < (ssize_t) count; i++)
 582           {
 583             if (image->storage_class == PseudoClass)
 584               indexes[x+i]=(IndexPacket) index;
 585             if (cube_info->quantize_info->measure_error == MagickFalse)
 586               {
 587                 q->red=image->colormap[index].red;
 588                 q->green=image->colormap[index].green;
 589                 q->blue=image->colormap[index].blue;
 590                 if (cube_info->associate_alpha != MagickFalse)
 591                   q->opacity=image->colormap[index].opacity;
 592               }
 593             q++;
 594           }
 595         }
 596         if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
 597           break;
 598         proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) y,
 599           image->rows);
 600         if (proceed == MagickFalse)
 601           break;
 602       }
 603       image_view=DestroyCacheView(image_view);
 604     }
 605   if (cube_info->quantize_info->measure_error != MagickFalse)
 606     (void) GetImageQuantizeError(image);
 607   if ((cube_info->quantize_info->number_colors == 2) &&
 608       (cube_info->quantize_info->colorspace == GRAYColorspace))
 609     {
 610       Quantum
 611         intensity;
 612
 613       register PixelPacket
 614         *restrict q;
 615
 616       /*
 617         Monochrome image.
 618       */
 619       q=image->colormap;
 620       for (i=0; i < (ssize_t) image->colors; i++)
 621       {
 622         intensity=(Quantum) (PixelIntensity(q) < ((MagickRealType)
 623           QuantumRange/2.0) ? 0 : QuantumRange);
 624         q->red=intensity;
 625         q->green=intensity;
 626         q->blue=intensity;
 627         q++;
 628       }
 629     }
 630   (void) SyncImage(image);
 631   if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
 632       (cube_info->quantize_info->colorspace != CMYKColorspace))
 633     (void) TransformImageColorspace((Image *) image,RGBColorspace);
 634   return(MagickTrue);
 635 }
 636 \f
 637 /*
 638 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 639 %                                                                             %
 640 %                                                                             %
 641 %                                                                             %
 642 +   C l a s s i f y I m a g e C o l o r s                                     %
 643 %                                                                             %
 644 %                                                                             %
 645 %                                                                             %
 646 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 647 %
 648 %  ClassifyImageColors() begins by initializing a color description tree
 649 %  of sufficient depth to represent each possible input color in a leaf.
 650 %  However, it is impractical to generate a fully-formed color
 651 %  description tree in the storage_class phase for realistic values of
 652 %  Cmax.  If colors components in the input image are quantized to k-bit
 653 %  precision, so that Cmax= 2k-1, the tree would need k levels below the
 654 %  root node to allow representing each possible input color in a leaf.
 655 %  This becomes prohibitive because the tree's total number of nodes is
 656 %  1 + sum(i=1,k,8k).
 657 %
 658 %  A complete tree would require 19,173,961 nodes for k = 8, Cmax = 255.
 659 %  Therefore, to avoid building a fully populated tree, QUANTIZE: (1)
 660 %  Initializes data structures for nodes only as they are needed;  (2)
 661 %  Chooses a maximum depth for the tree as a function of the desired
 662 %  number of colors in the output image (currently log2(colormap size)).
 663 %
 664 %  For each pixel in the input image, storage_class scans downward from
 665 %  the root of the color description tree.  At each level of the tree it
 666 %  identifies the single node which represents a cube in RGB space
 667 %  containing It updates the following data for each such node:
 668 %
 669 %    n1 : Number of pixels whose color is contained in the RGB cube
 670 %    which this node represents;
 671 %
 672 %    n2 : Number of pixels whose color is not represented in a node at
 673 %    lower depth in the tree;  initially,  n2 = 0 for all nodes except
 674 %    leaves of the tree.
 675 %
 676 %    Sr, Sg, Sb : Sums of the red, green, and blue component values for
 677 %    all pixels not classified at a lower depth. The combination of
 678 %    these sums and n2  will ultimately characterize the mean color of a
 679 %    set of pixels represented by this node.
 680 %
 681 %    E: the distance squared in RGB space between each pixel contained
 682 %    within a node and the nodes' center.  This represents the quantization
 683 %    error for a node.
 684 %
 685 %  The format of the ClassifyImageColors() method is:
 686 %
 687 %      MagickBooleanType ClassifyImageColors(CubeInfo *cube_info,
 688 %        const Image *image,ExceptionInfo *exception)
 689 %
 690 %  A description of each parameter follows.
 691 %
 692 %    o cube_info: A pointer to the Cube structure.
 693 %
 694 %    o image: the image.
 695 %
 696 */
 697
 698 static inline void SetAssociatedAlpha(const Image *image,CubeInfo *cube_info)
 699 {
 700   MagickBooleanType
 701     associate_alpha;
 702
 703   associate_alpha=image->matte;
 704   if (cube_info->quantize_info->colorspace == TransparentColorspace)
 705     associate_alpha=MagickFalse;
 706   if ((cube_info->quantize_info->number_colors == 2) &&
 707       (cube_info->quantize_info->colorspace == GRAYColorspace))
 708     associate_alpha=MagickFalse;
 709   cube_info->associate_alpha=associate_alpha;
 710 }
 711
 712 static MagickBooleanType ClassifyImageColors(CubeInfo *cube_info,
 713   const Image *image,ExceptionInfo *exception)
 714 {
 715 #define ClassifyImageTag  "Classify/Image"
 716
 717   CacheView
 718     *image_view;
 719
 720   ssize_t
 721     y;
 722
 723   MagickBooleanType
 724     proceed;
 725
 726   MagickRealType
 727     bisect;
 728
 729   NodeInfo
 730     *node_info;
 731
 732   RealPixelPacket
 733     error,
 734     mid,
 735     midpoint,
 736     pixel;
 737
 738   size_t
 739     count;
 740
 741   size_t
 742     id,
 743     index,
 744     level;
 745
 746   /*
 747     Classify the first cube_info->maximum_colors colors to a tree depth of 8.
 748   */
 749   SetAssociatedAlpha(image,cube_info);
 750   if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
 751       (cube_info->quantize_info->colorspace != CMYKColorspace))
 752     (void) TransformImageColorspace((Image *) image,
 753       cube_info->quantize_info->colorspace);
 754   else
 755     if ((image->colorspace != GRAYColorspace) &&
 756         (image->colorspace != CMYColorspace) &&
 757         (image->colorspace != RGBColorspace))
 758       (void) TransformImageColorspace((Image *) image,RGBColorspace);
 759   midpoint.red=(MagickRealType) QuantumRange/2.0;
 760   midpoint.green=(MagickRealType) QuantumRange/2.0;
 761   midpoint.blue=(MagickRealType) QuantumRange/2.0;
 762   midpoint.opacity=(MagickRealType) QuantumRange/2.0;
 763   error.opacity=0.0;
 764   image_view=AcquireCacheView(image);
 765   for (y=0; y < (ssize_t) image->rows; y++)
 766   {
 767     register const PixelPacket
 768       *restrict p;
 769
 770     register ssize_t
 771       x;
 772
 773     p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
 774     if (p == (const PixelPacket *) NULL)
 775       break;
 776     if (cube_info->nodes > MaxNodes)
 777       {
 778         /*
 779           Prune one level if the color tree is too large.
 780         */
 781         PruneLevel(image,cube_info,cube_info->root);
 782         cube_info->depth--;
 783       }
 784     for (x=0; x < (ssize_t) image->columns; x+=(ssize_t) count)
 785     {
 786       /*
 787         Start at the root and descend the color cube tree.
 788       */
 789       for (count=1; (x+count) < image->columns; count++)
 790         if (IsSameColor(image,p,p+count) == MagickFalse)
 791           break;
 792       AssociateAlphaPixel(cube_info,p,&pixel);
 793       index=MaxTreeDepth-1;
 794       bisect=((MagickRealType) QuantumRange+1.0)/2.0;
 795       mid=midpoint;
 796       node_info=cube_info->root;
 797       for (level=1; level <= MaxTreeDepth; level++)
 798       {
 799         bisect*=0.5;
 800         id=ColorToNodeId(cube_info,&pixel,index);
 801         mid.red+=(id & 1) != 0 ? bisect : -bisect;
 802         mid.green+=(id & 2) != 0 ? bisect : -bisect;
 803         mid.blue+=(id & 4) != 0 ? bisect : -bisect;
 804         mid.opacity+=(id & 8) != 0 ? bisect : -bisect;
 805         if (node_info->child[id] == (NodeInfo *) NULL)
 806           {
 807             /*
 808               Set colors of new node to contain pixel.
 809             */
 810             node_info->child[id]=GetNodeInfo(cube_info,id,level,node_info);
 811             if (node_info->child[id] == (NodeInfo *) NULL)
 812               (void) ThrowMagickException(exception,GetMagickModule(),
 813                 ResourceLimitError,"MemoryAllocationFailed","`%s'",
 814                 image->filename);
 815             if (level == MaxTreeDepth)
 816               cube_info->colors++;
 817           }
 818         /*
 819           Approximate the quantization error represented by this node.
 820         */
 821         node_info=node_info->child[id];
 822         error.red=QuantumScale*(pixel.red-mid.red);
 823         error.green=QuantumScale*(pixel.green-mid.green);
 824         error.blue=QuantumScale*(pixel.blue-mid.blue);
 825         if (cube_info->associate_alpha != MagickFalse)
 826           error.opacity=QuantumScale*(pixel.opacity-mid.opacity);
 827         node_info->quantize_error+=sqrt((double) (count*error.red*error.red+
 828           count*error.green*error.green+count*error.blue*error.blue+
 829           count*error.opacity*error.opacity));
 830         cube_info->root->quantize_error+=node_info->quantize_error;
 831         index--;
 832       }
 833       /*
 834         Sum RGB for this leaf for later derivation of the mean cube color.
 835       */
 836       node_info->number_unique+=count;
 837       node_info->total_color.red+=count*QuantumScale*pixel.red;
 838       node_info->total_color.green+=count*QuantumScale*pixel.green;
 839       node_info->total_color.blue+=count*QuantumScale*pixel.blue;
 840       if (cube_info->associate_alpha != MagickFalse)
 841         node_info->total_color.opacity+=count*QuantumScale*pixel.opacity;
 842       p+=count;
 843     }
 844     if (cube_info->colors > cube_info->maximum_colors)
 845       {
 846         PruneToCubeDepth(image,cube_info,cube_info->root);
 847         break;
 848       }
 849     proceed=SetImageProgress(image,ClassifyImageTag,(MagickOffsetType) y,
 850       image->rows);
 851     if (proceed == MagickFalse)
 852       break;
 853   }
 854   for (y++; y < (ssize_t) image->rows; y++)
 855   {
 856     register const PixelPacket
 857       *restrict p;
 858
 859     register ssize_t
 860       x;
 861
 862     p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
 863     if (p == (const PixelPacket *) NULL)
 864       break;
 865     if (cube_info->nodes > MaxNodes)
 866       {
 867         /*
 868           Prune one level if the color tree is too large.
 869         */
 870         PruneLevel(image,cube_info,cube_info->root);
 871         cube_info->depth--;
 872       }
 873     for (x=0; x < (ssize_t) image->columns; x+=(ssize_t) count)
 874     {
 875       /*
 876         Start at the root and descend the color cube tree.
 877       */
 878       for (count=1; (x+count) < image->columns; count++)
 879         if (IsSameColor(image,p,p+count) == MagickFalse)
 880           break;
 881       AssociateAlphaPixel(cube_info,p,&pixel);
 882       index=MaxTreeDepth-1;
 883       bisect=((MagickRealType) QuantumRange+1.0)/2.0;
 884       mid=midpoint;
 885       node_info=cube_info->root;
 886       for (level=1; level <= cube_info->depth; level++)
 887       {
 888         bisect*=0.5;
 889         id=ColorToNodeId(cube_info,&pixel,index);
 890         mid.red+=(id & 1) != 0 ? bisect : -bisect;
 891         mid.green+=(id & 2) != 0 ? bisect : -bisect;
 892         mid.blue+=(id & 4) != 0 ? bisect : -bisect;
 893         mid.opacity+=(id & 8) != 0 ? bisect : -bisect;
 894         if (node_info->child[id] == (NodeInfo *) NULL)
 895           {
 896             /*
 897               Set colors of new node to contain pixel.
 898             */
 899             node_info->child[id]=GetNodeInfo(cube_info,id,level,node_info);
 900             if (node_info->child[id] == (NodeInfo *) NULL)
 901               (void) ThrowMagickException(exception,GetMagickModule(),
 902                 ResourceLimitError,"MemoryAllocationFailed","%s",
 903                 image->filename);
 904             if (level == cube_info->depth)
 905               cube_info->colors++;
 906           }
 907         /*
 908           Approximate the quantization error represented by this node.
 909         */
 910         node_info=node_info->child[id];
 911         error.red=QuantumScale*(pixel.red-mid.red);
 912         error.green=QuantumScale*(pixel.green-mid.green);
 913         error.blue=QuantumScale*(pixel.blue-mid.blue);
 914         if (cube_info->associate_alpha != MagickFalse)
 915           error.opacity=QuantumScale*(pixel.opacity-mid.opacity);
 916         node_info->quantize_error+=sqrt((double) (count*error.red*error.red+
 917           count*error.green*error.green+error.blue*error.blue+
 918           count*error.opacity*error.opacity));
 919         cube_info->root->quantize_error+=node_info->quantize_error;
 920         index--;
 921       }
 922       /*
 923         Sum RGB for this leaf for later derivation of the mean cube color.
 924       */
 925       node_info->number_unique+=count;
 926       node_info->total_color.red+=count*QuantumScale*pixel.red;
 927       node_info->total_color.green+=count*QuantumScale*pixel.green;
 928       node_info->total_color.blue+=count*QuantumScale*pixel.blue;
 929       if (cube_info->associate_alpha != MagickFalse)
 930         node_info->total_color.opacity+=count*QuantumScale*pixel.opacity;
 931       p+=count;
 932     }
 933     proceed=SetImageProgress(image,ClassifyImageTag,(MagickOffsetType) y,
 934       image->rows);
 935     if (proceed == MagickFalse)
 936       break;
 937   }
 938   image_view=DestroyCacheView(image_view);
 939   if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
 940       (cube_info->quantize_info->colorspace != CMYKColorspace))
 941     (void) TransformImageColorspace((Image *) image,RGBColorspace);
 942   return(MagickTrue);
 943 }
 944 \f
 945 /*
 946 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 947 %                                                                             %
 948 %                                                                             %
 949 %                                                                             %
 950 %   C l o n e Q u a n t i z e I n f o                                         %
 951 %                                                                             %
 952 %                                                                             %
 953 %                                                                             %
 954 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 955 %
 956 %  CloneQuantizeInfo() makes a duplicate of the given quantize info structure,
 957 %  or if quantize info is NULL, a new one.
 958 %
 959 %  The format of the CloneQuantizeInfo method is:
 960 %
 961 %      QuantizeInfo *CloneQuantizeInfo(const QuantizeInfo *quantize_info)
 962 %
 963 %  A description of each parameter follows:
 964 %
 965 %    o clone_info: Method CloneQuantizeInfo returns a duplicate of the given
 966 %      quantize info, or if image info is NULL a new one.
 967 %
 968 %    o quantize_info: a structure of type info.
 969 %
 970 */
 971 MagickExport QuantizeInfo *CloneQuantizeInfo(const QuantizeInfo *quantize_info)
 972 {
 973   QuantizeInfo
 974     *clone_info;
 975
 976   clone_info=(QuantizeInfo *) AcquireAlignedMemory(1,sizeof(*clone_info));
 977   if (clone_info == (QuantizeInfo *) NULL)
 978     ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
 979   GetQuantizeInfo(clone_info);
 980   if (quantize_info == (QuantizeInfo *) NULL)
 981     return(clone_info);
 982   clone_info->number_colors=quantize_info->number_colors;
 983   clone_info->tree_depth=quantize_info->tree_depth;
 984   clone_info->dither=quantize_info->dither;
 985   clone_info->dither_method=quantize_info->dither_method;
 986   clone_info->colorspace=quantize_info->colorspace;
 987   clone_info->measure_error=quantize_info->measure_error;
 988   return(clone_info);
 989 }
 990 \f
 991 /*
 992 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 993 %                                                                             %
 994 %                                                                             %
 995 %                                                                             %
 996 +   C l o s e s t C o l o r                                                   %
 997 %                                                                             %
 998 %                                                                             %
 999 %                                                                             %
1000 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1001 %
1002 %  ClosestColor() traverses the color cube tree at a particular node and
1003 %  determines which colormap entry best represents the input color.
1004 %
1005 %  The format of the ClosestColor method is:
1006 %
1007 %      void ClosestColor(const Image *image,CubeInfo *cube_info,
1008 %        const NodeInfo *node_info)
1009 %
1010 %  A description of each parameter follows.
1011 %
1012 %    o image: the image.
1013 %
1014 %    o cube_info: A pointer to the Cube structure.
1015 %
1016 %    o node_info: the address of a structure of type NodeInfo which points to a
1017 %      node in the color cube tree that is to be pruned.
1018 %
1019 */
1020 static void ClosestColor(const Image *image,CubeInfo *cube_info,
1021   const NodeInfo *node_info)
1022 {
1023   register ssize_t
1024     i;
1025
1026   size_t
1027     number_children;
1028
1029   /*
1030     Traverse any children.
1031   */
1032   number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
1033   for (i=0; i < (ssize_t) number_children; i++)
1034     if (node_info->child[i] != (NodeInfo *) NULL)
1035       ClosestColor(image,cube_info,node_info->child[i]);
1036   if (node_info->number_unique != 0)
1037     {
1038       MagickRealType
1039         pixel;
1040
1041       register MagickRealType
1042         alpha,
1043         beta,
1044         distance;
1045
1046       register PixelPacket
1047         *restrict p;
1048
1049       register RealPixelPacket
1050         *restrict q;
1051
1052       /*
1053         Determine if this color is "closest".
1054       */
1055       p=image->colormap+node_info->color_number;
1056       q=(&cube_info->target);
1057       alpha=1.0;
1058       beta=1.0;
1059       if (cube_info->associate_alpha == MagickFalse)
1060         {
1061           alpha=(MagickRealType) (QuantumScale*GetAlphaPixelComponent(p));
1062           beta=(MagickRealType) (QuantumScale*GetAlphaPixelComponent(q));
1063         }
1064       pixel=alpha*p->red-beta*q->red;
1065       distance=pixel*pixel;
1066       if (distance < cube_info->distance)
1067         {
1068           pixel=alpha*p->green-beta*q->green;
1069           distance+=pixel*pixel;
1070           if (distance < cube_info->distance)
1071             {
1072               pixel=alpha*p->blue-beta*q->blue;
1073               distance+=pixel*pixel;
1074               if (distance < cube_info->distance)
1075                 {
1076                   pixel=alpha-beta;
1077                   distance+=pixel*pixel;
1078                   if (distance < cube_info->distance)
1079                     {
1080                       cube_info->distance=distance;
1081                       cube_info->color_number=node_info->color_number;
1082                     }
1083                 }
1084             }
1085         }
1086     }
1087 }
1088 \f
1089 /*
1090 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1091 %                                                                             %
1092 %                                                                             %
1093 %                                                                             %
1094 %   C o m p r e s s I m a g e C o l o r m a p                                 %
1095 %                                                                             %
1096 %                                                                             %
1097 %                                                                             %
1098 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1099 %
1100 %  CompressImageColormap() compresses an image colormap by removing any
1101 %  duplicate or unused color entries.
1102 %
1103 %  The format of the CompressImageColormap method is:
1104 %
1105 %      MagickBooleanType CompressImageColormap(Image *image)
1106 %
1107 %  A description of each parameter follows:
1108 %
1109 %    o image: the image.
1110 %
1111 */
1112 MagickExport MagickBooleanType CompressImageColormap(Image *image)
1113 {
1114   QuantizeInfo
1115     quantize_info;
1116
1117   assert(image != (Image *) NULL);
1118   assert(image->signature == MagickSignature);
1119   if (image->debug != MagickFalse)
1120     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
1121   if (IsPaletteImage(image,&image->exception) == MagickFalse)
1122     return(MagickFalse);
1123   GetQuantizeInfo(&quantize_info);
1124   quantize_info.number_colors=image->colors;
1125   quantize_info.tree_depth=MaxTreeDepth;
1126   return(QuantizeImage(&quantize_info,image));
1127 }
1128 \f
1129 /*
1130 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1131 %                                                                             %
1132 %                                                                             %
1133 %                                                                             %
1134 +   D e f i n e I m a g e C o l o r m a p                                     %
1135 %                                                                             %
1136 %                                                                             %
1137 %                                                                             %
1138 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1139 %
1140 %  DefineImageColormap() traverses the color cube tree and notes each colormap
1141 %  entry.  A colormap entry is any node in the color cube tree where the
1142 %  of unique colors is not zero.  DefineImageColormap() returns the number of
1143 %  colors in the image colormap.
1144 %
1145 %  The format of the DefineImageColormap method is:
1146 %
1147 %      size_t DefineImageColormap(Image *image,CubeInfo *cube_info,
1148 %        NodeInfo *node_info)
1149 %
1150 %  A description of each parameter follows.
1151 %
1152 %    o image: the image.
1153 %
1154 %    o cube_info: A pointer to the Cube structure.
1155 %
1156 %    o node_info: the address of a structure of type NodeInfo which points to a
1157 %      node in the color cube tree that is to be pruned.
1158 %
1159 */
1160 static size_t DefineImageColormap(Image *image,CubeInfo *cube_info,
1161   NodeInfo *node_info)
1162 {
1163   register ssize_t
1164     i;
1165
1166   size_t
1167     number_children;
1168
1169   /*
1170     Traverse any children.
1171   */
1172   number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
1173   for (i=0; i < (ssize_t) number_children; i++)
1174     if (node_info->child[i] != (NodeInfo *) NULL)
1175       (void) DefineImageColormap(image,cube_info,node_info->child[i]);
1176   if (node_info->number_unique != 0)
1177     {
1178       register MagickRealType
1179         alpha;
1180
1181       register PixelPacket
1182         *restrict q;
1183
1184       /*
1185         Colormap entry is defined by the mean color in this cube.
1186       */
1187       q=image->colormap+image->colors;
1188       alpha=(MagickRealType) ((MagickOffsetType) node_info->number_unique);
1189       alpha=1.0/(fabs(alpha) <= MagickEpsilon ? 1.0 : alpha);
1190       if (cube_info->associate_alpha == MagickFalse)
1191         {
1192           q->red=ClampToQuantum((MagickRealType) (alpha*QuantumRange*
1193             node_info->total_color.red));
1194           q->green=ClampToQuantum((MagickRealType) (alpha*QuantumRange*
1195             node_info->total_color.green));
1196           q->blue=ClampToQuantum((MagickRealType) (alpha*QuantumRange*
1197             node_info->total_color.blue));
1198           SetOpacityPixelComponent(q,OpaqueOpacity);
1199         }
1200       else
1201         {
1202           MagickRealType
1203             opacity;
1204
1205           opacity=(MagickRealType) (alpha*QuantumRange*
1206             node_info->total_color.opacity);
1207           q->opacity=ClampToQuantum(opacity);
1208           if (q->opacity == OpaqueOpacity)
1209             {
1210               q->red=ClampToQuantum((MagickRealType) (alpha*QuantumRange*
1211                 node_info->total_color.red));
1212               q->green=ClampToQuantum((MagickRealType) (alpha*QuantumRange*
1213                 node_info->total_color.green));
1214               q->blue=ClampToQuantum((MagickRealType) (alpha*QuantumRange*
1215                 node_info->total_color.blue));
1216             }
1217           else
1218             {
1219               MagickRealType
1220                 gamma;
1221
1222               gamma=(MagickRealType) (QuantumScale*(QuantumRange-
1223                 (MagickRealType) q->opacity));
1224               gamma=1.0/(fabs(gamma) <= MagickEpsilon ? 1.0 : gamma);
1225               q->red=ClampToQuantum((MagickRealType) (alpha*gamma*QuantumRange*
1226                 node_info->total_color.red));
1227               q->green=ClampToQuantum((MagickRealType) (alpha*gamma*
1228                 QuantumRange*node_info->total_color.green));
1229               q->blue=ClampToQuantum((MagickRealType) (alpha*gamma*QuantumRange*
1230                 node_info->total_color.blue));
1231               if (node_info->number_unique > cube_info->transparent_pixels)
1232                 {
1233                   cube_info->transparent_pixels=node_info->number_unique;
1234                   cube_info->transparent_index=(ssize_t) image->colors;
1235                 }
1236             }
1237         }
1238       node_info->color_number=image->colors++;
1239     }
1240   return(image->colors);
1241 }
1242 \f
1243 /*
1244 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1245 %                                                                             %
1246 %                                                                             %
1247 %                                                                             %
1248 +   D e s t r o y C u b e I n f o                                             %
1249 %                                                                             %
1250 %                                                                             %
1251 %                                                                             %
1252 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1253 %
1254 %  DestroyCubeInfo() deallocates memory associated with an image.
1255 %
1256 %  The format of the DestroyCubeInfo method is:
1257 %
1258 %      DestroyCubeInfo(CubeInfo *cube_info)
1259 %
1260 %  A description of each parameter follows:
1261 %
1262 %    o cube_info: the address of a structure of type CubeInfo.
1263 %
1264 */
1265 static void DestroyCubeInfo(CubeInfo *cube_info)
1266 {
1267   register Nodes
1268     *nodes;
1269
1270   /*
1271     Release color cube tree storage.
1272   */
1273   do
1274   {
1275     nodes=cube_info->node_queue->next;
1276     cube_info->node_queue->nodes=(NodeInfo *) RelinquishMagickMemory(
1277       cube_info->node_queue->nodes);
1278     cube_info->node_queue=(Nodes *) RelinquishMagickMemory(
1279       cube_info->node_queue);
1280     cube_info->node_queue=nodes;
1281   } while (cube_info->node_queue != (Nodes *) NULL);
1282   if (cube_info->cache != (ssize_t *) NULL)
1283     cube_info->cache=(ssize_t *) RelinquishMagickMemory(cube_info->cache);
1284   cube_info->quantize_info=DestroyQuantizeInfo(cube_info->quantize_info);
1285   cube_info=(CubeInfo *) RelinquishMagickMemory(cube_info);
1286 }
1287 \f
1288 /*
1289 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1290 %                                                                             %
1291 %                                                                             %
1292 %                                                                             %
1293 %   D e s t r o y Q u a n t i z e I n f o                                     %
1294 %                                                                             %
1295 %                                                                             %
1296 %                                                                             %
1297 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1298 %
1299 %  DestroyQuantizeInfo() deallocates memory associated with an QuantizeInfo
1300 %  structure.
1301 %
1302 %  The format of the DestroyQuantizeInfo method is:
1303 %
1304 %      QuantizeInfo *DestroyQuantizeInfo(QuantizeInfo *quantize_info)
1305 %
1306 %  A description of each parameter follows:
1307 %
1308 %    o quantize_info: Specifies a pointer to an QuantizeInfo structure.
1309 %
1310 */
1311 MagickExport QuantizeInfo *DestroyQuantizeInfo(QuantizeInfo *quantize_info)
1312 {
1313   (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1314   assert(quantize_info != (QuantizeInfo *) NULL);
1315   assert(quantize_info->signature == MagickSignature);
1316   quantize_info->signature=(~MagickSignature);
1317   quantize_info=(QuantizeInfo *) RelinquishMagickMemory(quantize_info);
1318   return(quantize_info);
1319 }
1320 \f
1321 /*
1322 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1323 %                                                                             %
1324 %                                                                             %
1325 %                                                                             %
1326 +   D i t h e r I m a g e                                                     %
1327 %                                                                             %
1328 %                                                                             %
1329 %                                                                             %
1330 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1331 %
1332 %  DitherImage() distributes the difference between an original image and
1333 %  the corresponding color reduced algorithm to neighboring pixels using
1334 %  serpentine-scan Floyd-Steinberg error diffusion. DitherImage returns
1335 %  MagickTrue if the image is dithered otherwise MagickFalse.
1336 %
1337 %  The format of the DitherImage method is:
1338 %
1339 %      MagickBooleanType DitherImage(Image *image,CubeInfo *cube_info)
1340 %
1341 %  A description of each parameter follows.
1342 %
1343 %    o image: the image.
1344 %
1345 %    o cube_info: A pointer to the Cube structure.
1346 %
1347 */
1348
1349 static MagickBooleanType FloydSteinbergDither(Image *image,CubeInfo *cube_info)
1350 {
1351 #define DitherImageTag  "Dither/Image"
1352
1353   CacheView
1354     *image_view;
1355
1356   ExceptionInfo
1357     *exception;
1358
1359   ssize_t
1360     u,
1361     v,
1362     y;
1363
1364   MagickBooleanType
1365     proceed;
1366
1367   RealPixelPacket
1368     color,
1369     *current,
1370     pixel,
1371     *previous,
1372     *scanlines;
1373
1374   register CubeInfo
1375     *p;
1376
1377   size_t
1378     index;
1379
1380   /*
1381     Distribute quantization error using Floyd-Steinberg.
1382   */
1383   scanlines=(RealPixelPacket *) AcquireQuantumMemory(image->columns,
1384     2*sizeof(*scanlines));
1385   if (scanlines == (RealPixelPacket *) NULL)
1386     return(MagickFalse);
1387   p=cube_info;
1388   exception=(&image->exception);
1389   image_view=AcquireCacheView(image);
1390   for (y=0; y < (ssize_t) image->rows; y++)
1391   {
1392     register IndexPacket
1393       *restrict indexes;
1394
1395     register ssize_t
1396       i,
1397       x;
1398
1399     register PixelPacket
1400       *restrict q;
1401
1402     q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
1403     if (q == (PixelPacket *) NULL)
1404       return(MagickFalse);
1405     indexes=GetCacheViewAuthenticIndexQueue(image_view);
1406     current=scanlines+(y & 0x01)*image->columns;
1407     previous=scanlines+((y+1) & 0x01)*image->columns;
1408     v=(ssize_t) ((y & 0x01) ? -1 : 1);
1409     for (x=0; x < (ssize_t) image->columns; x++)
1410     {
1411       u=(y & 0x01) ? (ssize_t) image->columns-1-x : x;
1412       AssociateAlphaPixel(cube_info,q+u,&pixel);
1413       if (x > 0)
1414         {
1415           pixel.red+=7*current[u-v].red/16;
1416           pixel.green+=7*current[u-v].green/16;
1417           pixel.blue+=7*current[u-v].blue/16;
1418           if (cube_info->associate_alpha != MagickFalse)
1419             pixel.opacity+=7*current[u-v].opacity/16;
1420         }
1421       if (y > 0)
1422         {
1423           if (x < (ssize_t) (image->columns-1))
1424             {
1425               pixel.red+=previous[u+v].red/16;
1426               pixel.green+=previous[u+v].green/16;
1427               pixel.blue+=previous[u+v].blue/16;
1428               if (cube_info->associate_alpha != MagickFalse)
1429                 pixel.opacity+=previous[u+v].opacity/16;
1430             }
1431           pixel.red+=5*previous[u].red/16;
1432           pixel.green+=5*previous[u].green/16;
1433           pixel.blue+=5*previous[u].blue/16;
1434           if (cube_info->associate_alpha != MagickFalse)
1435             pixel.opacity+=5*previous[u].opacity/16;
1436           if (x > 0)
1437             {
1438               pixel.red+=3*previous[u-v].red/16;
1439               pixel.green+=3*previous[u-v].green/16;
1440               pixel.blue+=3*previous[u-v].blue/16;
1441               if (cube_info->associate_alpha != MagickFalse)
1442                 pixel.opacity+=3*previous[u-v].opacity/16;
1443             }
1444         }
1445       pixel.red=(MagickRealType) ClampToUnsignedQuantum(pixel.red);
1446       pixel.green=(MagickRealType) ClampToUnsignedQuantum(pixel.green);
1447       pixel.blue=(MagickRealType) ClampToUnsignedQuantum(pixel.blue);
1448       if (cube_info->associate_alpha != MagickFalse)
1449         pixel.opacity=(MagickRealType) ClampToUnsignedQuantum(pixel.opacity);
1450       i=(ssize_t) ((ScaleQuantumToChar(ClampToUnsignedQuantum(pixel.red)) >> CacheShift) |
1451         (ScaleQuantumToChar(ClampToUnsignedQuantum(pixel.green)) >> CacheShift) << 6 |
1452         (ScaleQuantumToChar(ClampToUnsignedQuantum(pixel.blue)) >> CacheShift) << 12);
1453       if (cube_info->associate_alpha != MagickFalse)
1454         i|=((ScaleQuantumToChar(ClampToUnsignedQuantum(pixel.opacity)) >> CacheShift)
1455           << 18);
1456       if (p->cache[i] < 0)
1457         {
1458           register NodeInfo
1459             *node_info;
1460
1461           register size_t
1462             id;
1463
1464           /*
1465             Identify the deepest node containing the pixel's color.
1466           */
1467           node_info=p->root;
1468           for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
1469           {
1470             id=ColorToNodeId(cube_info,&pixel,index);
1471             if (node_info->child[id] == (NodeInfo *) NULL)
1472               break;
1473             node_info=node_info->child[id];
1474           }
1475           /*
1476             Find closest color among siblings and their children.
1477           */
1478           p->target=pixel;
1479           p->distance=(MagickRealType) (4.0*(QuantumRange+1.0)*(QuantumRange+
1480             1.0)+1.0);
1481           ClosestColor(image,p,node_info->parent);
1482           p->cache[i]=(ssize_t) p->color_number;
1483         }
1484       /*
1485         Assign pixel to closest colormap entry.
1486       */
1487       index=(size_t) p->cache[i];
1488       if (image->storage_class == PseudoClass)
1489         indexes[u]=(IndexPacket) index;
1490       if (cube_info->quantize_info->measure_error == MagickFalse)
1491         {
1492           (q+u)->red=image->colormap[index].red;
1493           (q+u)->green=image->colormap[index].green;
1494           (q+u)->blue=image->colormap[index].blue;
1495           if (cube_info->associate_alpha != MagickFalse)
1496             (q+u)->opacity=image->colormap[index].opacity;
1497         }
1498       if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
1499         return(MagickFalse);
1500       /*
1501         Store the error.
1502       */
1503       AssociateAlphaPixel(cube_info,image->colormap+index,&color);
1504       current[u].red=pixel.red-color.red;
1505       current[u].green=pixel.green-color.green;
1506       current[u].blue=pixel.blue-color.blue;
1507       if (cube_info->associate_alpha != MagickFalse)
1508         current[u].opacity=pixel.opacity-color.opacity;
1509       proceed=SetImageProgress(image,DitherImageTag,p->offset,p->span);
1510       if (proceed == MagickFalse)
1511         return(MagickFalse);
1512       p->offset++;
1513     }
1514   }
1515   scanlines=(RealPixelPacket *) RelinquishMagickMemory(scanlines);
1516   image_view=DestroyCacheView(image_view);
1517   return(MagickTrue);
1518 }
1519
1520 static MagickBooleanType
1521   RiemersmaDither(Image *,CacheView *,CubeInfo *,const unsigned int);
1522
1523 static void Riemersma(Image *image,CacheView *image_view,CubeInfo *cube_info,
1524   const size_t level,const unsigned int direction)
1525 {
1526   if (level == 1)
1527     switch (direction)
1528     {
1529       case WestGravity:
1530       {
1531         (void) RiemersmaDither(image,image_view,cube_info,EastGravity);
1532         (void) RiemersmaDither(image,image_view,cube_info,SouthGravity);
1533         (void) RiemersmaDither(image,image_view,cube_info,WestGravity);
1534         break;
1535       }
1536       case EastGravity:
1537       {
1538         (void) RiemersmaDither(image,image_view,cube_info,WestGravity);
1539         (void) RiemersmaDither(image,image_view,cube_info,NorthGravity);
1540         (void) RiemersmaDither(image,image_view,cube_info,EastGravity);
1541         break;
1542       }
1543       case NorthGravity:
1544       {
1545         (void) RiemersmaDither(image,image_view,cube_info,SouthGravity);
1546         (void) RiemersmaDither(image,image_view,cube_info,EastGravity);
1547         (void) RiemersmaDither(image,image_view,cube_info,NorthGravity);
1548         break;
1549       }
1550       case SouthGravity:
1551       {
1552         (void) RiemersmaDither(image,image_view,cube_info,NorthGravity);
1553         (void) RiemersmaDither(image,image_view,cube_info,WestGravity);
1554         (void) RiemersmaDither(image,image_view,cube_info,SouthGravity);
1555         break;
1556       }
1557       default:
1558         break;
1559     }
1560   else
1561     switch (direction)
1562     {
1563       case WestGravity:
1564       {
1565         Riemersma(image,image_view,cube_info,level-1,NorthGravity);
1566         (void) RiemersmaDither(image,image_view,cube_info,EastGravity);
1567         Riemersma(image,image_view,cube_info,level-1,WestGravity);
1568         (void) RiemersmaDither(image,image_view,cube_info,SouthGravity);
1569         Riemersma(image,image_view,cube_info,level-1,WestGravity);
1570         (void) RiemersmaDither(image,image_view,cube_info,WestGravity);
1571         Riemersma(image,image_view,cube_info,level-1,SouthGravity);
1572         break;
1573       }
1574       case EastGravity:
1575       {
1576         Riemersma(image,image_view,cube_info,level-1,SouthGravity);
1577         (void) RiemersmaDither(image,image_view,cube_info,WestGravity);
1578         Riemersma(image,image_view,cube_info,level-1,EastGravity);
1579         (void) RiemersmaDither(image,image_view,cube_info,NorthGravity);
1580         Riemersma(image,image_view,cube_info,level-1,EastGravity);
1581         (void) RiemersmaDither(image,image_view,cube_info,EastGravity);
1582         Riemersma(image,image_view,cube_info,level-1,NorthGravity);
1583         break;
1584       }
1585       case NorthGravity:
1586       {
1587         Riemersma(image,image_view,cube_info,level-1,WestGravity);
1588         (void) RiemersmaDither(image,image_view,cube_info,SouthGravity);
1589         Riemersma(image,image_view,cube_info,level-1,NorthGravity);
1590         (void) RiemersmaDither(image,image_view,cube_info,EastGravity);
1591         Riemersma(image,image_view,cube_info,level-1,NorthGravity);
1592         (void) RiemersmaDither(image,image_view,cube_info,NorthGravity);
1593         Riemersma(image,image_view,cube_info,level-1,EastGravity);
1594         break;
1595       }
1596       case SouthGravity:
1597       {
1598         Riemersma(image,image_view,cube_info,level-1,EastGravity);
1599         (void) RiemersmaDither(image,image_view,cube_info,NorthGravity);
1600         Riemersma(image,image_view,cube_info,level-1,SouthGravity);
1601         (void) RiemersmaDither(image,image_view,cube_info,WestGravity);
1602         Riemersma(image,image_view,cube_info,level-1,SouthGravity);
1603         (void) RiemersmaDither(image,image_view,cube_info,SouthGravity);
1604         Riemersma(image,image_view,cube_info,level-1,WestGravity);
1605         break;
1606       }
1607       default:
1608         break;
1609     }
1610 }
1611
1612 static MagickBooleanType RiemersmaDither(Image *image,CacheView *image_view,
1613   CubeInfo *cube_info,const unsigned int direction)
1614 {
1615 #define DitherImageTag  "Dither/Image"
1616
1617   MagickBooleanType
1618     proceed;
1619
1620   RealPixelPacket
1621     color,
1622     pixel;
1623
1624   register CubeInfo
1625     *p;
1626
1627   size_t
1628     index;
1629
1630   p=cube_info;
1631   if ((p->x >= 0) && (p->x < (ssize_t) image->columns) &&
1632       (p->y >= 0) && (p->y < (ssize_t) image->rows))
1633     {
1634       ExceptionInfo
1635         *exception;
1636
1637       register IndexPacket
1638         *restrict indexes;
1639
1640       register ssize_t
1641         i;
1642
1643       register PixelPacket
1644         *restrict q;
1645
1646       /*
1647         Distribute error.
1648       */
1649       exception=(&image->exception);
1650       q=GetCacheViewAuthenticPixels(image_view,p->x,p->y,1,1,exception);
1651       if (q == (PixelPacket *) NULL)
1652         return(MagickFalse);
1653       indexes=GetCacheViewAuthenticIndexQueue(image_view);
1654       AssociateAlphaPixel(cube_info,q,&pixel);
1655       for (i=0; i < ErrorQueueLength; i++)
1656       {
1657         pixel.red+=p->weights[i]*p->error[i].red;
1658         pixel.green+=p->weights[i]*p->error[i].green;
1659         pixel.blue+=p->weights[i]*p->error[i].blue;
1660         if (cube_info->associate_alpha != MagickFalse)
1661           pixel.opacity+=p->weights[i]*p->error[i].opacity;
1662       }
1663       pixel.red=(MagickRealType) ClampToUnsignedQuantum(pixel.red);
1664       pixel.green=(MagickRealType) ClampToUnsignedQuantum(pixel.green);
1665       pixel.blue=(MagickRealType) ClampToUnsignedQuantum(pixel.blue);
1666       if (cube_info->associate_alpha != MagickFalse)
1667         pixel.opacity=(MagickRealType) ClampToUnsignedQuantum(pixel.opacity);
1668       i=(ssize_t) ((ScaleQuantumToChar(ClampToUnsignedQuantum(pixel.red)) >> CacheShift) |
1669         (ScaleQuantumToChar(ClampToUnsignedQuantum(pixel.green)) >> CacheShift) << 6 |
1670         (ScaleQuantumToChar(ClampToUnsignedQuantum(pixel.blue)) >> CacheShift) << 12);
1671       if (cube_info->associate_alpha != MagickFalse)
1672         i|=((ScaleQuantumToChar(ClampToUnsignedQuantum(pixel.opacity)) >> CacheShift)
1673           << 18);
1674       if (p->cache[i] < 0)
1675         {
1676           register NodeInfo
1677             *node_info;
1678
1679           register size_t
1680             id;
1681
1682           /*
1683             Identify the deepest node containing the pixel's color.
1684           */
1685           node_info=p->root;
1686           for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
1687           {
1688             id=ColorToNodeId(cube_info,&pixel,index);
1689             if (node_info->child[id] == (NodeInfo *) NULL)
1690               break;
1691             node_info=node_info->child[id];
1692           }
1693           /*
1694             Find closest color among siblings and their children.
1695           */
1696           p->target=pixel;
1697           p->distance=(MagickRealType) (4.0*(QuantumRange+1.0)*((MagickRealType)
1698             QuantumRange+1.0)+1.0);
1699           ClosestColor(image,p,node_info->parent);
1700           p->cache[i]=(ssize_t) p->color_number;
1701         }
1702       /*
1703         Assign pixel to closest colormap entry.
1704       */
1705       index=(size_t) (1*p->cache[i]);
1706       if (image->storage_class == PseudoClass)
1707         *indexes=(IndexPacket) index;
1708       if (cube_info->quantize_info->measure_error == MagickFalse)
1709         {
1710           q->red=image->colormap[index].red;
1711           q->green=image->colormap[index].green;
1712           q->blue=image->colormap[index].blue;
1713           if (cube_info->associate_alpha != MagickFalse)
1714             q->opacity=image->colormap[index].opacity;
1715         }
1716       if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
1717         return(MagickFalse);
1718       /*
1719         Propagate the error as the last entry of the error queue.
1720       */
1721       (void) CopyMagickMemory(p->error,p->error+1,(ErrorQueueLength-1)*
1722         sizeof(p->error[0]));
1723       AssociateAlphaPixel(cube_info,image->colormap+index,&color);
1724       p->error[ErrorQueueLength-1].red=pixel.red-color.red;
1725       p->error[ErrorQueueLength-1].green=pixel.green-color.green;
1726       p->error[ErrorQueueLength-1].blue=pixel.blue-color.blue;
1727       if (cube_info->associate_alpha != MagickFalse)
1728         p->error[ErrorQueueLength-1].opacity=pixel.opacity-color.opacity;
1729       proceed=SetImageProgress(image,DitherImageTag,p->offset,p->span);
1730       if (proceed == MagickFalse)
1731         return(MagickFalse);
1732       p->offset++;
1733     }
1734   switch (direction)
1735   {
1736     case WestGravity: p->x--; break;
1737     case EastGravity: p->x++; break;
1738     case NorthGravity: p->y--; break;
1739     case SouthGravity: p->y++; break;
1740   }
1741   return(MagickTrue);
1742 }
1743
1744 static inline ssize_t MagickMax(const ssize_t x,const ssize_t y)
1745 {
1746   if (x > y)
1747     return(x);
1748   return(y);
1749 }
1750
1751 static inline ssize_t MagickMin(const ssize_t x,const ssize_t y)
1752 {
1753   if (x < y)
1754     return(x);
1755   return(y);
1756 }
1757
1758 static MagickBooleanType DitherImage(Image *image,CubeInfo *cube_info)
1759 {
1760   CacheView
1761     *image_view;
1762
1763   MagickBooleanType
1764     status;
1765
1766   register ssize_t
1767     i;
1768
1769   size_t
1770     depth;
1771
1772   if (cube_info->quantize_info->dither_method == FloydSteinbergDitherMethod)
1773     return(FloydSteinbergDither(image,cube_info));
1774   /*
1775     Distribute quantization error along a Hilbert curve.
1776   */
1777   (void) ResetMagickMemory(cube_info->error,0,ErrorQueueLength*
1778     sizeof(*cube_info->error));
1779   cube_info->x=0;
1780   cube_info->y=0;
1781   i=MagickMax((ssize_t) image->columns,(ssize_t) image->rows);
1782   for (depth=1; i != 0; depth++)
1783     i>>=1;
1784   if ((ssize_t) (1L << depth) < MagickMax((ssize_t) image->columns,(ssize_t) image->rows))
1785     depth++;
1786   cube_info->offset=0;
1787   cube_info->span=(MagickSizeType) image->columns*image->rows;
1788   image_view=AcquireCacheView(image);
1789   if (depth > 1)
1790     Riemersma(image,image_view,cube_info,depth-1,NorthGravity);
1791   status=RiemersmaDither(image,image_view,cube_info,ForgetGravity);
1792   image_view=DestroyCacheView(image_view);
1793   return(status);
1794 }
1795 \f
1796 /*
1797 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1798 %                                                                             %
1799 %                                                                             %
1800 %                                                                             %
1801 +   G e t C u b e I n f o                                                     %
1802 %                                                                             %
1803 %                                                                             %
1804 %                                                                             %
1805 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1806 %
1807 %  GetCubeInfo() initialize the Cube data structure.
1808 %
1809 %  The format of the GetCubeInfo method is:
1810 %
1811 %      CubeInfo GetCubeInfo(const QuantizeInfo *quantize_info,
1812 %        const size_t depth,const size_t maximum_colors)
1813 %
1814 %  A description of each parameter follows.
1815 %
1816 %    o quantize_info: Specifies a pointer to an QuantizeInfo structure.
1817 %
1818 %    o depth: Normally, this integer value is zero or one.  A zero or
1819 %      one tells Quantize to choose a optimal tree depth of Log4(number_colors).
1820 %      A tree of this depth generally allows the best representation of the
1821 %      reference image with the least amount of memory and the fastest
1822 %      computational speed.  In some cases, such as an image with low color
1823 %      dispersion (a few number of colors), a value other than
1824 %      Log4(number_colors) is required.  To expand the color tree completely,
1825 %      use a value of 8.
1826 %
1827 %    o maximum_colors: maximum colors.
1828 %
1829 */
1830 static CubeInfo *GetCubeInfo(const QuantizeInfo *quantize_info,
1831   const size_t depth,const size_t maximum_colors)
1832 {
1833   CubeInfo
1834     *cube_info;
1835
1836   MagickRealType
1837     sum,
1838     weight;
1839
1840   size_t
1841     length;
1842
1843   register ssize_t
1844     i;
1845
1846   /*
1847     Initialize tree to describe color cube_info.
1848   */
1849   cube_info=(CubeInfo *) AcquireAlignedMemory(1,sizeof(*cube_info));
1850   if (cube_info == (CubeInfo *) NULL)
1851     return((CubeInfo *) NULL);
1852   (void) ResetMagickMemory(cube_info,0,sizeof(*cube_info));
1853   cube_info->depth=depth;
1854   if (cube_info->depth > MaxTreeDepth)
1855     cube_info->depth=MaxTreeDepth;
1856   if (cube_info->depth < 2)
1857     cube_info->depth=2;
1858   cube_info->maximum_colors=maximum_colors;
1859   /*
1860     Initialize root node.
1861   */
1862   cube_info->root=GetNodeInfo(cube_info,0,0,(NodeInfo *) NULL);
1863   if (cube_info->root == (NodeInfo *) NULL)
1864     return((CubeInfo *) NULL);
1865   cube_info->root->parent=cube_info->root;
1866   cube_info->quantize_info=CloneQuantizeInfo(quantize_info);
1867   if (cube_info->quantize_info->dither == MagickFalse)
1868     return(cube_info);
1869   /*
1870     Initialize dither resources.
1871   */
1872   length=(size_t) (1UL << (4*(8-CacheShift)));
1873   cube_info->cache=(ssize_t *) AcquireQuantumMemory(length,
1874     sizeof(*cube_info->cache));
1875   if (cube_info->cache == (ssize_t *) NULL)
1876     return((CubeInfo *) NULL);
1877   /*
1878     Initialize color cache.
1879   */
1880   for (i=0; i < (ssize_t) length; i++)
1881     cube_info->cache[i]=(-1);
1882   /*
1883     Distribute weights along a curve of exponential decay.
1884   */
1885   weight=1.0;
1886   for (i=0; i < ErrorQueueLength; i++)
1887   {
1888     cube_info->weights[ErrorQueueLength-i-1]=1.0/weight;
1889     weight*=exp(log(((double) QuantumRange+1.0))/(ErrorQueueLength-1.0));
1890   }
1891   /*
1892     Normalize the weighting factors.
1893   */
1894   weight=0.0;
1895   for (i=0; i < ErrorQueueLength; i++)
1896     weight+=cube_info->weights[i];
1897   sum=0.0;
1898   for (i=0; i < ErrorQueueLength; i++)
1899   {
1900     cube_info->weights[i]/=weight;
1901     sum+=cube_info->weights[i];
1902   }
1903   cube_info->weights[0]+=1.0-sum;
1904   return(cube_info);
1905 }
1906 \f
1907 /*
1908 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1909 %                                                                             %
1910 %                                                                             %
1911 %                                                                             %
1912 +   G e t N o d e I n f o                                                     %
1913 %                                                                             %
1914 %                                                                             %
1915 %                                                                             %
1916 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1917 %
1918 %  GetNodeInfo() allocates memory for a new node in the color cube tree and
1919 %  presets all fields to zero.
1920 %
1921 %  The format of the GetNodeInfo method is:
1922 %
1923 %      NodeInfo *GetNodeInfo(CubeInfo *cube_info,const size_t id,
1924 %        const size_t level,NodeInfo *parent)
1925 %
1926 %  A description of each parameter follows.
1927 %
1928 %    o node: The GetNodeInfo method returns a pointer to a queue of nodes.
1929 %
1930 %    o id: Specifies the child number of the node.
1931 %
1932 %    o level: Specifies the level in the storage_class the node resides.
1933 %
1934 */
1935 static NodeInfo *GetNodeInfo(CubeInfo *cube_info,const size_t id,
1936   const size_t level,NodeInfo *parent)
1937 {
1938   NodeInfo
1939     *node_info;
1940
1941   if (cube_info->free_nodes == 0)
1942     {
1943       Nodes
1944         *nodes;
1945
1946       /*
1947         Allocate a new queue of nodes.
1948       */
1949       nodes=(Nodes *) AcquireAlignedMemory(1,sizeof(*nodes));
1950       if (nodes == (Nodes *) NULL)
1951         return((NodeInfo *) NULL);
1952       nodes->nodes=(NodeInfo *) AcquireQuantumMemory(NodesInAList,
1953         sizeof(*nodes->nodes));
1954       if (nodes->nodes == (NodeInfo *) NULL)
1955         return((NodeInfo *) NULL);
1956       nodes->next=cube_info->node_queue;
1957       cube_info->node_queue=nodes;
1958       cube_info->next_node=nodes->nodes;
1959       cube_info->free_nodes=NodesInAList;
1960     }
1961   cube_info->nodes++;
1962   cube_info->free_nodes--;
1963   node_info=cube_info->next_node++;
1964   (void) ResetMagickMemory(node_info,0,sizeof(*node_info));
1965   node_info->parent=parent;
1966   node_info->id=id;
1967   node_info->level=level;
1968   return(node_info);
1969 }
1970 \f
1971 /*
1972 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1973 %                                                                             %
1974 %                                                                             %
1975 %                                                                             %
1976 %  G e t I m a g e Q u a n t i z e E r r o r                                  %
1977 %                                                                             %
1978 %                                                                             %
1979 %                                                                             %
1980 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1981 %
1982 %  GetImageQuantizeError() measures the difference between the original
1983 %  and quantized images.  This difference is the total quantization error.
1984 %  The error is computed by summing over all pixels in an image the distance
1985 %  squared in RGB space between each reference pixel value and its quantized
1986 %  value.  These values are computed:
1987 %
1988 %    o mean_error_per_pixel:  This value is the mean error for any single
1989 %      pixel in the image.
1990 %
1991 %    o normalized_mean_square_error:  This value is the normalized mean
1992 %      quantization error for any single pixel in the image.  This distance
1993 %      measure is normalized to a range between 0 and 1.  It is independent
1994 %      of the range of red, green, and blue values in the image.
1995 %
1996 %    o normalized_maximum_square_error:  Thsi value is the normalized
1997 %      maximum quantization error for any single pixel in the image.  This
1998 %      distance measure is normalized to a range between 0 and 1.  It is
1999 %      independent of the range of red, green, and blue values in your image.
2000 %
2001 %  The format of the GetImageQuantizeError method is:
2002 %
2003 %      MagickBooleanType GetImageQuantizeError(Image *image)
2004 %
2005 %  A description of each parameter follows.
2006 %
2007 %    o image: the image.
2008 %
2009 */
2010 MagickExport MagickBooleanType GetImageQuantizeError(Image *image)
2011 {
2012   CacheView
2013     *image_view;
2014
2015   ExceptionInfo
2016     *exception;
2017
2018   IndexPacket
2019     *indexes;
2020
2021   ssize_t
2022     y;
2023
2024   MagickRealType
2025     alpha,
2026     area,
2027     beta,
2028     distance,
2029     maximum_error,
2030     mean_error,
2031     mean_error_per_pixel;
2032
2033   size_t
2034     index;
2035
2036   assert(image != (Image *) NULL);
2037   assert(image->signature == MagickSignature);
2038   if (image->debug != MagickFalse)
2039     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
2040   image->total_colors=GetNumberColors(image,(FILE *) NULL,&image->exception);
2041   (void) ResetMagickMemory(&image->error,0,sizeof(image->error));
2042   if (image->storage_class == DirectClass)
2043     return(MagickTrue);
2044   alpha=1.0;
2045   beta=1.0;
2046   area=3.0*image->columns*image->rows;
2047   maximum_error=0.0;
2048   mean_error_per_pixel=0.0;
2049   mean_error=0.0;
2050   exception=(&image->exception);
2051   image_view=AcquireCacheView(image);
2052   for (y=0; y < (ssize_t) image->rows; y++)
2053   {
2054     register const PixelPacket
2055       *restrict p;
2056
2057     register ssize_t
2058       x;
2059
2060     p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
2061     if (p == (const PixelPacket *) NULL)
2062       break;
2063     indexes=GetCacheViewAuthenticIndexQueue(image_view);
2064     for (x=0; x < (ssize_t) image->columns; x++)
2065     {
2066       index=1UL*indexes[x];
2067       if (image->matte != MagickFalse)
2068         {
2069           alpha=(MagickRealType) (QuantumScale*(GetAlphaPixelComponent(p)));
2070           beta=(MagickRealType) (QuantumScale*(QuantumRange-
2071             image->colormap[index].opacity));
2072         }
2073       distance=fabs(alpha*p->red-beta*image->colormap[index].red);
2074       mean_error_per_pixel+=distance;
2075       mean_error+=distance*distance;
2076       if (distance > maximum_error)
2077         maximum_error=distance;
2078       distance=fabs(alpha*p->green-beta*image->colormap[index].green);
2079       mean_error_per_pixel+=distance;
2080       mean_error+=distance*distance;
2081       if (distance > maximum_error)
2082         maximum_error=distance;
2083       distance=fabs(alpha*p->blue-beta*image->colormap[index].blue);
2084       mean_error_per_pixel+=distance;
2085       mean_error+=distance*distance;
2086       if (distance > maximum_error)
2087         maximum_error=distance;
2088       p++;
2089     }
2090   }
2091   image_view=DestroyCacheView(image_view);
2092   image->error.mean_error_per_pixel=(double) mean_error_per_pixel/area;
2093   image->error.normalized_mean_error=(double) QuantumScale*QuantumScale*
2094     mean_error/area;
2095   image->error.normalized_maximum_error=(double) QuantumScale*maximum_error;
2096   return(MagickTrue);
2097 }
2098 \f
2099 /*
2100 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2101 %                                                                             %
2102 %                                                                             %
2103 %                                                                             %
2104 %   G e t Q u a n t i z e I n f o                                             %
2105 %                                                                             %
2106 %                                                                             %
2107 %                                                                             %
2108 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2109 %
2110 %  GetQuantizeInfo() initializes the QuantizeInfo structure.
2111 %
2112 %  The format of the GetQuantizeInfo method is:
2113 %
2114 %      GetQuantizeInfo(QuantizeInfo *quantize_info)
2115 %
2116 %  A description of each parameter follows:
2117 %
2118 %    o quantize_info: Specifies a pointer to a QuantizeInfo structure.
2119 %
2120 */
2121 MagickExport void GetQuantizeInfo(QuantizeInfo *quantize_info)
2122 {
2123   (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
2124   assert(quantize_info != (QuantizeInfo *) NULL);
2125   (void) ResetMagickMemory(quantize_info,0,sizeof(*quantize_info));
2126   quantize_info->number_colors=256;
2127   quantize_info->dither=MagickTrue;
2128   quantize_info->dither_method=RiemersmaDitherMethod;
2129   quantize_info->colorspace=UndefinedColorspace;
2130   quantize_info->measure_error=MagickFalse;
2131   quantize_info->signature=MagickSignature;
2132 }
2133 \f
2134 /*
2135 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2136 %                                                                             %
2137 %                                                                             %
2138 %                                                                             %
2139 %   P o s t e r i z e I m a g e                                               %
2140 %                                                                             %
2141 %                                                                             %
2142 %                                                                             %
2143 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2144 %
2145 %  PosterizeImage() reduces the image to a limited number of colors for a
2146 %  "poster" effect.
2147 %
2148 %  The format of the PosterizeImage method is:
2149 %
2150 %      MagickBooleanType PosterizeImage(Image *image,const size_t levels,
2151 %        const MagickBooleanType dither)
2152 %
2153 %  A description of each parameter follows:
2154 %
2155 %    o image: Specifies a pointer to an Image structure.
2156 %
2157 %    o levels: Number of color levels allowed in each channel.  Very low values
2158 %      (2, 3, or 4) have the most visible effect.
2159 %
2160 %    o dither: Set this integer value to something other than zero to
2161 %      dither the mapped image.
2162 %
2163 */
2164 MagickExport MagickBooleanType PosterizeImage(Image *image,
2165   const size_t levels,const MagickBooleanType dither)
2166 {
2167   CacheView
2168     *posterize_view;
2169
2170   ExceptionInfo
2171     *exception;
2172
2173   Image
2174     *posterize_image;
2175
2176   IndexPacket
2177     *indexes;
2178
2179   ssize_t
2180     j,
2181     k,
2182     l,
2183     n;
2184
2185   MagickBooleanType
2186     status;
2187
2188   QuantizeInfo
2189     *quantize_info;
2190
2191   register ssize_t
2192     i;
2193
2194   register PixelPacket
2195     *restrict q;
2196
2197   size_t
2198     length;
2199
2200   /*
2201     Posterize image.
2202   */
2203   assert(image != (Image *) NULL);
2204   assert(image->signature == MagickSignature);
2205   if (image->debug != MagickFalse)
2206     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
2207   posterize_image=AcquireImage((ImageInfo *) NULL);
2208   if (posterize_image == (Image *) NULL)
2209     return(MagickFalse);
2210   l=1;
2211   length=(size_t) (levels*levels*levels);
2212   while ((l*l*l) < (ssize_t) MagickMin((ssize_t) length,MaxColormapSize+1))
2213     l++;
2214   status=SetImageExtent(posterize_image,(size_t) (l*l*l),1);
2215   if (status == MagickFalse)
2216     {
2217       posterize_image=DestroyImage(posterize_image);
2218       return(MagickFalse);
2219     }
2220   status=AcquireImageColormap(posterize_image,levels*levels*levels);
2221   if (status == MagickFalse)
2222     {
2223       posterize_image=DestroyImage(posterize_image);
2224       return(MagickFalse);
2225     }
2226   posterize_view=AcquireCacheView(posterize_image);
2227   exception=(&image->exception);
2228   q=QueueCacheViewAuthenticPixels(posterize_view,0,0,posterize_image->columns,1,
2229     exception);
2230   if (q == (PixelPacket *) NULL)
2231     {
2232       posterize_view=DestroyCacheView(posterize_view);
2233       posterize_image=DestroyImage(posterize_image);
2234       return(MagickFalse);
2235     }
2236   indexes=GetCacheViewAuthenticIndexQueue(posterize_view);
2237   n=0;
2238   for (i=0; i < l; i++)
2239     for (j=0; j < l; j++)
2240       for (k=0; k < l; k++)
2241       {
2242         posterize_image->colormap[n].red=(Quantum) (QuantumRange*i/
2243           MagickMax(l-1L,1L));
2244         posterize_image->colormap[n].green=(Quantum)
2245           (QuantumRange*j/MagickMax(l-1L,1L));
2246         posterize_image->colormap[n].blue=(Quantum) (QuantumRange*k/
2247           MagickMax(l-1L,1L));
2248         posterize_image->colormap[n].opacity=OpaqueOpacity;
2249         *q++=posterize_image->colormap[n];
2250         indexes[n]=(IndexPacket) n;
2251         n++;
2252       }
2253   if (SyncCacheViewAuthenticPixels(posterize_view,exception) == MagickFalse)
2254     {
2255       posterize_view=DestroyCacheView(posterize_view);
2256       posterize_image=DestroyImage(posterize_image);
2257       return(MagickFalse);
2258     }
2259   posterize_view=DestroyCacheView(posterize_view);
2260   quantize_info=AcquireQuantizeInfo((ImageInfo *) NULL);
2261   quantize_info->dither=dither;
2262   status=RemapImage(quantize_info,image,posterize_image);
2263   quantize_info=DestroyQuantizeInfo(quantize_info);
2264   posterize_image=DestroyImage(posterize_image);
2265   return(status);
2266 }
2267 \f
2268 /*
2269 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2270 %                                                                             %
2271 %                                                                             %
2272 %                                                                             %
2273 +   P r u n e C h i l d                                                       %
2274 %                                                                             %
2275 %                                                                             %
2276 %                                                                             %
2277 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2278 %
2279 %  PruneChild() deletes the given node and merges its statistics into its
2280 %  parent.
2281 %
2282 %  The format of the PruneSubtree method is:
2283 %
2284 %      PruneChild(const Image *image,CubeInfo *cube_info,
2285 %        const NodeInfo *node_info)
2286 %
2287 %  A description of each parameter follows.
2288 %
2289 %    o image: the image.
2290 %
2291 %    o cube_info: A pointer to the Cube structure.
2292 %
2293 %    o node_info: pointer to node in color cube tree that is to be pruned.
2294 %
2295 */
2296 static void PruneChild(const Image *image,CubeInfo *cube_info,
2297   const NodeInfo *node_info)
2298 {
2299   NodeInfo
2300     *parent;
2301
2302   register ssize_t
2303     i;
2304
2305   size_t
2306     number_children;
2307
2308   /*
2309     Traverse any children.
2310   */
2311   number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2312   for (i=0; i < (ssize_t) number_children; i++)
2313     if (node_info->child[i] != (NodeInfo *) NULL)
2314       PruneChild(image,cube_info,node_info->child[i]);
2315   /*
2316     Merge color statistics into parent.
2317   */
2318   parent=node_info->parent;
2319   parent->number_unique+=node_info->number_unique;
2320   parent->total_color.red+=node_info->total_color.red;
2321   parent->total_color.green+=node_info->total_color.green;
2322   parent->total_color.blue+=node_info->total_color.blue;
2323   parent->total_color.opacity+=node_info->total_color.opacity;
2324   parent->child[node_info->id]=(NodeInfo *) NULL;
2325   cube_info->nodes--;
2326 }
2327 \f
2328 /*
2329 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2330 %                                                                             %
2331 %                                                                             %
2332 %                                                                             %
2333 +  P r u n e L e v e l                                                        %
2334 %                                                                             %
2335 %                                                                             %
2336 %                                                                             %
2337 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2338 %
2339 %  PruneLevel() deletes all nodes at the bottom level of the color tree merging
2340 %  their color statistics into their parent node.
2341 %
2342 %  The format of the PruneLevel method is:
2343 %
2344 %      PruneLevel(const Image *image,CubeInfo *cube_info,
2345 %        const NodeInfo *node_info)
2346 %
2347 %  A description of each parameter follows.
2348 %
2349 %    o image: the image.
2350 %
2351 %    o cube_info: A pointer to the Cube structure.
2352 %
2353 %    o node_info: pointer to node in color cube tree that is to be pruned.
2354 %
2355 */
2356 static void PruneLevel(const Image *image,CubeInfo *cube_info,
2357   const NodeInfo *node_info)
2358 {
2359   register ssize_t
2360     i;
2361
2362   size_t
2363     number_children;
2364
2365   /*
2366     Traverse any children.
2367   */
2368   number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2369   for (i=0; i < (ssize_t) number_children; i++)
2370     if (node_info->child[i] != (NodeInfo *) NULL)
2371       PruneLevel(image,cube_info,node_info->child[i]);
2372   if (node_info->level == cube_info->depth)
2373     PruneChild(image,cube_info,node_info);
2374 }
2375 \f
2376 /*
2377 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2378 %                                                                             %
2379 %                                                                             %
2380 %                                                                             %
2381 +  P r u n e T o C u b e D e p t h                                            %
2382 %                                                                             %
2383 %                                                                             %
2384 %                                                                             %
2385 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2386 %
2387 %  PruneToCubeDepth() deletes any nodes at a depth greater than
2388 %  cube_info->depth while merging their color statistics into their parent
2389 %  node.
2390 %
2391 %  The format of the PruneToCubeDepth method is:
2392 %
2393 %      PruneToCubeDepth(const Image *image,CubeInfo *cube_info,
2394 %        const NodeInfo *node_info)
2395 %
2396 %  A description of each parameter follows.
2397 %
2398 %    o cube_info: A pointer to the Cube structure.
2399 %
2400 %    o node_info: pointer to node in color cube tree that is to be pruned.
2401 %
2402 */
2403 static void PruneToCubeDepth(const Image *image,CubeInfo *cube_info,
2404   const NodeInfo *node_info)
2405 {
2406   register ssize_t
2407     i;
2408
2409   size_t
2410     number_children;
2411
2412   /*
2413     Traverse any children.
2414   */
2415   number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2416   for (i=0; i < (ssize_t) number_children; i++)
2417     if (node_info->child[i] != (NodeInfo *) NULL)
2418       PruneToCubeDepth(image,cube_info,node_info->child[i]);
2419   if (node_info->level > cube_info->depth)
2420     PruneChild(image,cube_info,node_info);
2421 }
2422 \f
2423 /*
2424 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2425 %                                                                             %
2426 %                                                                             %
2427 %                                                                             %
2428 %  Q u a n t i z e I m a g e                                                  %
2429 %                                                                             %
2430 %                                                                             %
2431 %                                                                             %
2432 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2433 %
2434 %  QuantizeImage() analyzes the colors within a reference image and chooses a
2435 %  fixed number of colors to represent the image.  The goal of the algorithm
2436 %  is to minimize the color difference between the input and output image while
2437 %  minimizing the processing time.
2438 %
2439 %  The format of the QuantizeImage method is:
2440 %
2441 %      MagickBooleanType QuantizeImage(const QuantizeInfo *quantize_info,
2442 %        Image *image)
2443 %
2444 %  A description of each parameter follows:
2445 %
2446 %    o quantize_info: Specifies a pointer to an QuantizeInfo structure.
2447 %
2448 %    o image: the image.
2449 %
2450 */
2451 static MagickBooleanType DirectToColormapImage(Image *image,
2452   ExceptionInfo *exception)
2453 {
2454   CacheView
2455     *image_view;
2456
2457   ssize_t
2458     y;
2459
2460   MagickBooleanType
2461     status;
2462
2463   register ssize_t
2464     i;
2465
2466   size_t
2467     number_colors;
2468
2469   status=MagickTrue;
2470   number_colors=(size_t) (image->columns*image->rows);
2471   if (AcquireImageColormap(image,number_colors) == MagickFalse)
2472     ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
2473       image->filename);
2474   i=0;
2475   image_view=AcquireCacheView(image);
2476   for (y=0; y < (ssize_t) image->rows; y++)
2477   {
2478     MagickBooleanType
2479       proceed;
2480
2481     register IndexPacket
2482       *restrict indexes;
2483
2484     register PixelPacket
2485       *restrict q;
2486
2487     register ssize_t
2488       x;
2489
2490     q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
2491     if (q == (const PixelPacket *) NULL)
2492       break;
2493     indexes=GetCacheViewAuthenticIndexQueue(image_view);
2494     for (x=0; x < (ssize_t) image->columns; x++)
2495     {
2496       indexes[x]=(IndexPacket) i;
2497       image->colormap[i++]=(*q++);
2498     }
2499     if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
2500       break;
2501     proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) y,
2502       image->rows);
2503     if (proceed == MagickFalse)
2504       status=MagickFalse;
2505   }
2506   image_view=DestroyCacheView(image_view);
2507   return(status);
2508 }
2509
2510 MagickExport MagickBooleanType QuantizeImage(const QuantizeInfo *quantize_info,
2511   Image *image)
2512 {
2513   CubeInfo
2514     *cube_info;
2515
2516   MagickBooleanType
2517     status;
2518
2519   size_t
2520     depth,
2521     maximum_colors;
2522
2523   assert(quantize_info != (const QuantizeInfo *) NULL);
2524   assert(quantize_info->signature == MagickSignature);
2525   assert(image != (Image *) NULL);
2526   assert(image->signature == MagickSignature);
2527   if (image->debug != MagickFalse)
2528     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
2529   maximum_colors=quantize_info->number_colors;
2530   if (maximum_colors == 0)
2531     maximum_colors=MaxColormapSize;
2532   if (maximum_colors > MaxColormapSize)
2533     maximum_colors=MaxColormapSize;
2534   if ((image->columns*image->rows) <= maximum_colors)
2535     return(DirectToColormapImage(image,&image->exception));
2536   if ((IsGrayImage(image,&image->exception) != MagickFalse) &&
2537       (image->matte == MagickFalse))
2538     (void) SetGrayscaleImage(image);
2539   if ((image->storage_class == PseudoClass) &&
2540       (image->colors <= maximum_colors))
2541     return(MagickTrue);
2542   depth=quantize_info->tree_depth;
2543   if (depth == 0)
2544     {
2545       size_t
2546         colors;
2547
2548       /*
2549         Depth of color tree is: Log4(colormap size)+2.
2550       */
2551       colors=maximum_colors;
2552       for (depth=1; colors != 0; depth++)
2553         colors>>=2;
2554       if ((quantize_info->dither != MagickFalse) && (depth > 2))
2555         depth--;
2556       if ((image->matte != MagickFalse) && (depth > 5))
2557         depth--;
2558     }
2559   /*
2560     Initialize color cube.
2561   */
2562   cube_info=GetCubeInfo(quantize_info,depth,maximum_colors);
2563   if (cube_info == (CubeInfo *) NULL)
2564     ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
2565       image->filename);
2566   status=ClassifyImageColors(cube_info,image,&image->exception);
2567   if (status != MagickFalse)
2568     {
2569       /*
2570         Reduce the number of colors in the image.
2571       */
2572       ReduceImageColors(image,cube_info);
2573       status=AssignImageColors(image,cube_info);
2574     }
2575   DestroyCubeInfo(cube_info);
2576   return(status);
2577 }
2578 \f
2579 /*
2580 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2581 %                                                                             %
2582 %                                                                             %
2583 %                                                                             %
2584 %   Q u a n t i z e I m a g e s                                               %
2585 %                                                                             %
2586 %                                                                             %
2587 %                                                                             %
2588 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2589 %
2590 %  QuantizeImages() analyzes the colors within a set of reference images and
2591 %  chooses a fixed number of colors to represent the set.  The goal of the
2592 %  algorithm is to minimize the color difference between the input and output
2593 %  images while minimizing the processing time.
2594 %
2595 %  The format of the QuantizeImages method is:
2596 %
2597 %      MagickBooleanType QuantizeImages(const QuantizeInfo *quantize_info,
2598 %        Image *images)
2599 %
2600 %  A description of each parameter follows:
2601 %
2602 %    o quantize_info: Specifies a pointer to an QuantizeInfo structure.
2603 %
2604 %    o images: Specifies a pointer to a list of Image structures.
2605 %
2606 */
2607 MagickExport MagickBooleanType QuantizeImages(const QuantizeInfo *quantize_info,
2608   Image *images)
2609 {
2610   CubeInfo
2611     *cube_info;
2612
2613   Image
2614     *image;
2615
2616   MagickBooleanType
2617     proceed,
2618     status;
2619
2620   MagickProgressMonitor
2621     progress_monitor;
2622
2623   register ssize_t
2624     i;
2625
2626   size_t
2627     depth,
2628     maximum_colors,
2629     number_images;
2630
2631   assert(quantize_info != (const QuantizeInfo *) NULL);
2632   assert(quantize_info->signature == MagickSignature);
2633   assert(images != (Image *) NULL);
2634   assert(images->signature == MagickSignature);
2635   if (images->debug != MagickFalse)
2636     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",images->filename);
2637   if (GetNextImageInList(images) == (Image *) NULL)
2638     {
2639       /*
2640         Handle a single image with QuantizeImage.
2641       */
2642       status=QuantizeImage(quantize_info,images);
2643       return(status);
2644     }
2645   status=MagickFalse;
2646   maximum_colors=quantize_info->number_colors;
2647   if (maximum_colors == 0)
2648     maximum_colors=MaxColormapSize;
2649   if (maximum_colors > MaxColormapSize)
2650     maximum_colors=MaxColormapSize;
2651   depth=quantize_info->tree_depth;
2652   if (depth == 0)
2653     {
2654       size_t
2655         colors;
2656
2657       /*
2658         Depth of color tree is: Log4(colormap size)+2.
2659       */
2660       colors=maximum_colors;
2661       for (depth=1; colors != 0; depth++)
2662         colors>>=2;
2663       if (quantize_info->dither != MagickFalse)
2664         depth--;
2665     }
2666   /*
2667     Initialize color cube.
2668   */
2669   cube_info=GetCubeInfo(quantize_info,depth,maximum_colors);
2670   if (cube_info == (CubeInfo *) NULL)
2671     {
2672       (void) ThrowMagickException(&images->exception,GetMagickModule(),
2673         ResourceLimitError,"MemoryAllocationFailed","`%s'",images->filename);
2674       return(MagickFalse);
2675     }
2676   number_images=GetImageListLength(images);
2677   image=images;
2678   for (i=0; image != (Image *) NULL; i++)
2679   {
2680     progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor) NULL,
2681       image->client_data);
2682     status=ClassifyImageColors(cube_info,image,&image->exception);
2683     if (status == MagickFalse)
2684       break;
2685     (void) SetImageProgressMonitor(image,progress_monitor,image->client_data);
2686     proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i,
2687       number_images);
2688     if (proceed == MagickFalse)
2689       break;
2690     image=GetNextImageInList(image);
2691   }
2692   if (status != MagickFalse)
2693     {
2694       /*
2695         Reduce the number of colors in an image sequence.
2696       */
2697       ReduceImageColors(images,cube_info);
2698       image=images;
2699       for (i=0; image != (Image *) NULL; i++)
2700       {
2701         progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor)
2702           NULL,image->client_data);
2703         status=AssignImageColors(image,cube_info);
2704         if (status == MagickFalse)
2705           break;
2706         (void) SetImageProgressMonitor(image,progress_monitor,
2707           image->client_data);
2708         proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i,
2709           number_images);
2710         if (proceed == MagickFalse)
2711           break;
2712         image=GetNextImageInList(image);
2713       }
2714     }
2715   DestroyCubeInfo(cube_info);
2716   return(status);
2717 }
2718 \f
2719 /*
2720 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2721 %                                                                             %
2722 %                                                                             %
2723 %                                                                             %
2724 +   R e d u c e                                                               %
2725 %                                                                             %
2726 %                                                                             %
2727 %                                                                             %
2728 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2729 %
2730 %  Reduce() traverses the color cube tree and prunes any node whose
2731 %  quantization error falls below a particular threshold.
2732 %
2733 %  The format of the Reduce method is:
2734 %
2735 %      Reduce(const Image *image,CubeInfo *cube_info,const NodeInfo *node_info)
2736 %
2737 %  A description of each parameter follows.
2738 %
2739 %    o image: the image.
2740 %
2741 %    o cube_info: A pointer to the Cube structure.
2742 %
2743 %    o node_info: pointer to node in color cube tree that is to be pruned.
2744 %
2745 */
2746 static void Reduce(const Image *image,CubeInfo *cube_info,
2747   const NodeInfo *node_info)
2748 {
2749   register ssize_t
2750     i;
2751
2752   size_t
2753     number_children;
2754
2755   /*
2756     Traverse any children.
2757   */
2758   number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2759   for (i=0; i < (ssize_t) number_children; i++)
2760     if (node_info->child[i] != (NodeInfo *) NULL)
2761       Reduce(image,cube_info,node_info->child[i]);
2762   if (node_info->quantize_error <= cube_info->pruning_threshold)
2763     PruneChild(image,cube_info,node_info);
2764   else
2765     {
2766       /*
2767         Find minimum pruning threshold.
2768       */
2769       if (node_info->number_unique > 0)
2770         cube_info->colors++;
2771       if (node_info->quantize_error < cube_info->next_threshold)
2772         cube_info->next_threshold=node_info->quantize_error;
2773     }
2774 }
2775 \f
2776 /*
2777 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2778 %                                                                             %
2779 %                                                                             %
2780 %                                                                             %
2781 +   R e d u c e I m a g e C o l o r s                                         %
2782 %                                                                             %
2783 %                                                                             %
2784 %                                                                             %
2785 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2786 %
2787 %  ReduceImageColors() repeatedly prunes the tree until the number of nodes
2788 %  with n2 > 0 is less than or equal to the maximum number of colors allowed
2789 %  in the output image.  On any given iteration over the tree, it selects
2790 %  those nodes whose E value is minimal for pruning and merges their
2791 %  color statistics upward. It uses a pruning threshold, Ep, to govern
2792 %  node selection as follows:
2793 %
2794 %    Ep = 0
2795 %    while number of nodes with (n2 > 0) > required maximum number of colors
2796 %      prune all nodes such that E <= Ep
2797 %      Set Ep to minimum E in remaining nodes
2798 %
2799 %  This has the effect of minimizing any quantization error when merging
2800 %  two nodes together.
2801 %
2802 %  When a node to be pruned has offspring, the pruning procedure invokes
2803 %  itself recursively in order to prune the tree from the leaves upward.
2804 %  n2,  Sr, Sg,  and  Sb in a node being pruned are always added to the
2805 %  corresponding data in that node's parent.  This retains the pruned
2806 %  node's color characteristics for later averaging.
2807 %
2808 %  For each node, n2 pixels exist for which that node represents the
2809 %  smallest volume in RGB space containing those pixel's colors.  When n2
2810 %  > 0 the node will uniquely define a color in the output image. At the
2811 %  beginning of reduction,  n2 = 0  for all nodes except a the leaves of
2812 %  the tree which represent colors present in the input image.
2813 %
2814 %  The other pixel count, n1, indicates the total number of colors
2815 %  within the cubic volume which the node represents.  This includes n1 -
2816 %  n2  pixels whose colors should be defined by nodes at a lower level in
2817 %  the tree.
2818 %
2819 %  The format of the ReduceImageColors method is:
2820 %
2821 %      ReduceImageColors(const Image *image,CubeInfo *cube_info)
2822 %
2823 %  A description of each parameter follows.
2824 %
2825 %    o image: the image.
2826 %
2827 %    o cube_info: A pointer to the Cube structure.
2828 %
2829 */
2830 static void ReduceImageColors(const Image *image,CubeInfo *cube_info)
2831 {
2832 #define ReduceImageTag  "Reduce/Image"
2833
2834   MagickBooleanType
2835     proceed;
2836
2837   MagickOffsetType
2838     offset;
2839
2840   size_t
2841     span;
2842
2843   cube_info->next_threshold=0.0;
2844   for (span=cube_info->colors; cube_info->colors > cube_info->maximum_colors; )
2845   {
2846     cube_info->pruning_threshold=cube_info->next_threshold;
2847     cube_info->next_threshold=cube_info->root->quantize_error-1;
2848     cube_info->colors=0;
2849     Reduce(image,cube_info,cube_info->root);
2850     offset=(MagickOffsetType) span-cube_info->colors;
2851     proceed=SetImageProgress(image,ReduceImageTag,offset,span-
2852       cube_info->maximum_colors+1);
2853     if (proceed == MagickFalse)
2854       break;
2855   }
2856 }
2857 \f
2858 /*
2859 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2860 %                                                                             %
2861 %                                                                             %
2862 %                                                                             %
2863 %   R e m a p I m a g e                                                       %
2864 %                                                                             %
2865 %                                                                             %
2866 %                                                                             %
2867 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2868 %
2869 %  RemapImage() replaces the colors of an image with the closest color from
2870 %  a reference image.
2871 %
2872 %  The format of the RemapImage method is:
2873 %
2874 %      MagickBooleanType RemapImage(const QuantizeInfo *quantize_info,
2875 %        Image *image,const Image *remap_image)
2876 %
2877 %  A description of each parameter follows:
2878 %
2879 %    o quantize_info: Specifies a pointer to an QuantizeInfo structure.
2880 %
2881 %    o image: the image.
2882 %
2883 %    o remap_image: the reference image.
2884 %
2885 */
2886 MagickExport MagickBooleanType RemapImage(const QuantizeInfo *quantize_info,
2887   Image *image,const Image *remap_image)
2888 {
2889   CubeInfo
2890     *cube_info;
2891
2892   MagickBooleanType
2893     status;
2894
2895   /*
2896     Initialize color cube.
2897   */
2898   assert(image != (Image *) NULL);
2899   assert(image->signature == MagickSignature);
2900   if (image->debug != MagickFalse)
2901     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
2902   assert(remap_image != (Image *) NULL);
2903   assert(remap_image->signature == MagickSignature);
2904   cube_info=GetCubeInfo(quantize_info,MaxTreeDepth,
2905     quantize_info->number_colors);
2906   if (cube_info == (CubeInfo *) NULL)
2907     ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
2908       image->filename);
2909   status=ClassifyImageColors(cube_info,remap_image,&image->exception);
2910   if (status != MagickFalse)
2911     {
2912       /*
2913         Classify image colors from the reference image.
2914       */
2915       cube_info->quantize_info->number_colors=cube_info->colors;
2916       status=AssignImageColors(image,cube_info);
2917     }
2918   DestroyCubeInfo(cube_info);
2919   return(status);
2920 }
2921 \f
2922 /*
2923 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2924 %                                                                             %
2925 %                                                                             %
2926 %                                                                             %
2927 %   R e m a p I m a g e s                                                     %
2928 %                                                                             %
2929 %                                                                             %
2930 %                                                                             %
2931 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2932 %
2933 %  RemapImages() replaces the colors of a sequence of images with the
2934 %  closest color from a reference image.
2935 %
2936 %  The format of the RemapImage method is:
2937 %
2938 %      MagickBooleanType RemapImages(const QuantizeInfo *quantize_info,
2939 %        Image *images,Image *remap_image)
2940 %
2941 %  A description of each parameter follows:
2942 %
2943 %    o quantize_info: Specifies a pointer to an QuantizeInfo structure.
2944 %
2945 %    o images: the image sequence.
2946 %
2947 %    o remap_image: the reference image.
2948 %
2949 */
2950 MagickExport MagickBooleanType RemapImages(const QuantizeInfo *quantize_info,
2951   Image *images,const Image *remap_image)
2952 {
2953   CubeInfo
2954     *cube_info;
2955
2956   Image
2957     *image;
2958
2959   MagickBooleanType
2960     status;
2961
2962   assert(images != (Image *) NULL);
2963   assert(images->signature == MagickSignature);
2964   if (images->debug != MagickFalse)
2965     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",images->filename);
2966   image=images;
2967   if (remap_image == (Image *) NULL)
2968     {
2969       /*
2970         Create a global colormap for an image sequence.
2971       */
2972       status=QuantizeImages(quantize_info,images);
2973       return(status);
2974     }
2975   /*
2976     Classify image colors from the reference image.
2977   */
2978   cube_info=GetCubeInfo(quantize_info,MaxTreeDepth,
2979     quantize_info->number_colors);
2980   if (cube_info == (CubeInfo *) NULL)
2981     ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
2982       image->filename);
2983   status=ClassifyImageColors(cube_info,remap_image,&image->exception);
2984   if (status != MagickFalse)
2985     {
2986       /*
2987         Classify image colors from the reference image.
2988       */
2989       cube_info->quantize_info->number_colors=cube_info->colors;
2990       image=images;
2991       for ( ; image != (Image *) NULL; image=GetNextImageInList(image))
2992       {
2993         status=AssignImageColors(image,cube_info);
2994         if (status == MagickFalse)
2995           break;
2996       }
2997     }
2998   DestroyCubeInfo(cube_info);
2999   return(status);
3000 }
3001 \f
3002 /*
3003 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3004 %                                                                             %
3005 %                                                                             %
3006 %                                                                             %
3007 %   S e t G r a y s c a l e I m a g e                                         %
3008 %                                                                             %
3009 %                                                                             %
3010 %                                                                             %
3011 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3012 %
3013 %  SetGrayscaleImage() converts an image to a PseudoClass grayscale image.
3014 %
3015 %  The format of the SetGrayscaleImage method is:
3016 %
3017 %      MagickBooleanType SetGrayscaleImage(Image *image)
3018 %
3019 %  A description of each parameter follows:
3020 %
3021 %    o image: The image.
3022 %
3023 */
3024
3025 #if defined(__cplusplus) || defined(c_plusplus)
3026 extern "C" {
3027 #endif
3028
3029 static int IntensityCompare(const void *x,const void *y)
3030 {
3031   ssize_t
3032     intensity;
3033
3034   PixelPacket
3035     *color_1,
3036     *color_2;
3037
3038   color_1=(PixelPacket *) x;
3039   color_2=(PixelPacket *) y;
3040   intensity=PixelIntensityToQuantum(color_1)-(ssize_t)
3041     PixelIntensityToQuantum(color_2);
3042   return((int) intensity);
3043 }
3044
3045 #if defined(__cplusplus) || defined(c_plusplus)
3046 }
3047 #endif
3048
3049 static MagickBooleanType SetGrayscaleImage(Image *image)
3050 {
3051   CacheView
3052     *image_view;
3053
3054   ExceptionInfo
3055     *exception;
3056
3057   ssize_t
3058     j,
3059     y;
3060
3061   PixelPacket
3062     *colormap;
3063
3064   ssize_t
3065     *colormap_index;
3066
3067   register ssize_t
3068     i;
3069
3070   MagickBooleanType
3071     status;
3072
3073   assert(image != (Image *) NULL);
3074   assert(image->signature == MagickSignature);
3075   if (image->type != GrayscaleType)
3076     (void) TransformImageColorspace(image,GRAYColorspace);
3077   colormap_index=(ssize_t *) AcquireQuantumMemory(MaxMap+1,
3078     sizeof(*colormap_index));
3079   if (colormap_index == (ssize_t *) NULL)
3080     ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3081       image->filename);
3082   if (image->storage_class != PseudoClass)
3083     {
3084       ExceptionInfo
3085         *exception;
3086
3087       for (i=0; i <= (ssize_t) MaxMap; i++)
3088         colormap_index[i]=(-1);
3089       if (AcquireImageColormap(image,MaxMap+1) == MagickFalse)
3090         ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3091           image->filename);
3092       image->colors=0;
3093       status=MagickTrue;
3094       exception=(&image->exception);
3095       image_view=AcquireCacheView(image);
3096 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3097   #pragma omp parallel for schedule(dynamic,4) shared(status)
3098 #endif
3099       for (y=0; y < (ssize_t) image->rows; y++)
3100       {
3101         register IndexPacket
3102           *restrict indexes;
3103
3104         register ssize_t
3105           x;
3106
3107         register const PixelPacket
3108           *restrict q;
3109
3110         if (status == MagickFalse)
3111           continue;
3112         q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,
3113           exception);
3114         if (q == (PixelPacket *) NULL)
3115           {
3116             status=MagickFalse;
3117             continue;
3118           }
3119         indexes=GetCacheViewAuthenticIndexQueue(image_view);
3120         for (x=0; x < (ssize_t) image->columns; x++)
3121         {
3122           register size_t
3123             intensity;
3124
3125           intensity=ScaleQuantumToMap(q->red);
3126           if (colormap_index[intensity] < 0)
3127             {
3128 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3129     #pragma omp critical (MagickCore_SetGrayscaleImage)
3130 #endif
3131               if (colormap_index[intensity] < 0)
3132                 {
3133                   colormap_index[intensity]=(ssize_t) image->colors;
3134                   image->colormap[image->colors]=(*q);
3135                   image->colors++;
3136                }
3137             }
3138           indexes[x]=(IndexPacket) colormap_index[intensity];
3139           q++;
3140         }
3141         if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
3142           status=MagickFalse;
3143       }
3144       image_view=DestroyCacheView(image_view);
3145     }
3146   for (i=0; i < (ssize_t) image->colors; i++)
3147     image->colormap[i].opacity=(unsigned short) i;
3148   qsort((void *) image->colormap,image->colors,sizeof(PixelPacket),
3149     IntensityCompare);
3150   colormap=(PixelPacket *) AcquireQuantumMemory(image->colors,
3151     sizeof(*colormap));
3152   if (colormap == (PixelPacket *) NULL)
3153     ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3154       image->filename);
3155   j=0;
3156   colormap[j]=image->colormap[0];
3157   for (i=0; i < (ssize_t) image->colors; i++)
3158   {
3159     if (IsSameColor(image,&colormap[j],&image->colormap[i]) == MagickFalse)
3160       {
3161         j++;
3162         colormap[j]=image->colormap[i];
3163       }
3164     colormap_index[(ssize_t) image->colormap[i].opacity]=j;
3165   }
3166   image->colors=(size_t) (j+1);
3167   image->colormap=(PixelPacket *) RelinquishMagickMemory(image->colormap);
3168   image->colormap=colormap;
3169   status=MagickTrue;
3170   exception=(&image->exception);
3171   image_view=AcquireCacheView(image);
3172 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3173   #pragma omp parallel for schedule(dynamic,4) shared(status)
3174 #endif
3175   for (y=0; y < (ssize_t) image->rows; y++)
3176   {
3177     register IndexPacket
3178       *restrict indexes;
3179
3180     register ssize_t
3181       x;
3182
3183     register const PixelPacket
3184       *restrict q;
3185
3186     if (status == MagickFalse)
3187       continue;
3188     q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
3189     if (q == (PixelPacket *) NULL)
3190       {
3191         status=MagickFalse;
3192         continue;
3193       }
3194     indexes=GetCacheViewAuthenticIndexQueue(image_view);
3195     for (x=0; x < (ssize_t) image->columns; x++)
3196       indexes[x]=(IndexPacket) colormap_index[ScaleQuantumToMap(indexes[x])];
3197     if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
3198       status=MagickFalse;
3199   }
3200   image_view=DestroyCacheView(image_view);
3201   colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
3202   image->type=GrayscaleType;
3203   if (IsMonochromeImage(image,&image->exception) != MagickFalse)
3204     image->type=BilevelType;
3205   return(status);
3206 }