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