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