MagickCore  7.1.0
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-2021 ImageMagick Studio LLC, a non-profit organization %
21 % dedicated to making software imaging solutions freely available. %
22 % %
23 % You may not use this file except in compliance with the License. You may %
24 % obtain a copy of the License at %
25 % %
26 % https://imagemagick.org/script/license.php %
27 % %
28 % Unless required by applicable law or agreed to in writing, software %
29 % distributed under the License is distributed on an "AS IS" BASIS, %
30 % WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %
31 % See the License for the specific language governing permissions and %
32 % limitations under the License. %
33 % %
34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
35 %
36 % Realism in computer graphics typically requires using 24 bits/pixel to
37 % generate an image. Yet many graphic display devices do not contain the
38 % amount of memory necessary to match the spatial and color resolution of
39 % the human eye. The Quantize methods takes a 24 bit image and reduces
40 % the number of colors so it can be displayed on raster device with less
41 % bits per pixel. In most instances, the quantized image closely
42 % resembles the original reference image.
43 %
44 % A reduction of colors in an image is also desirable for image
45 % transmission and real-time animation.
46 %
47 % QuantizeImage() takes a standard RGB or monochrome images and quantizes
48 % them down to some fixed number of colors.
49 %
50 % For purposes of color allocation, an image is a set of n pixels, where
51 % each pixel is a point in RGB space. RGB space is a 3-dimensional
52 % vector space, and each pixel, Pi, is defined by an ordered triple of
53 % red, green, and blue coordinates, (Ri, Gi, Bi).
54 %
55 % Each primary color component (red, green, or blue) represents an
56 % intensity which varies linearly from 0 to a maximum value, Cmax, which
57 % corresponds to full saturation of that color. Color allocation is
58 % defined over a domain consisting of the cube in RGB space with opposite
59 % vertices at (0,0,0) and (Cmax, Cmax, Cmax). QUANTIZE requires Cmax =
60 % 255.
61 %
62 % The algorithm maps this domain onto a tree in which each node
63 % represents a cube within that domain. In the following discussion
64 % these cubes are defined by the coordinate of two opposite vertices (vertex
65 % nearest the origin in RGB space and the vertex farthest from the origin).
66 %
67 % The tree's root node represents the entire domain, (0,0,0) through
68 % (Cmax,Cmax,Cmax). Each lower level in the tree is generated by
69 % subdividing one node's cube into eight smaller cubes of equal size.
70 % This corresponds to bisecting the parent cube with planes passing
71 % through the midpoints of each edge.
72 %
73 % The basic algorithm operates in three phases: Classification,
74 % Reduction, and Assignment. Classification builds a color description
75 % tree for the image. Reduction collapses the tree until the number it
76 % represents, at most, the number of colors desired in the output image.
77 % Assignment defines the output image's color map and sets each pixel's
78 % color by restorage_class in the reduced tree. Our goal is to minimize
79 % the numerical discrepancies between the original colors and quantized
80 % colors (quantization error).
81 %
82 % Classification begins by initializing a color description tree of
83 % sufficient depth to represent each possible input color in a leaf.
84 % However, it is impractical to generate a fully-formed color description
85 % tree in the storage_class phase for realistic values of Cmax. If
86 % colors components in the input image are quantized to k-bit precision,
87 % so that Cmax= 2k-1, the tree would need k levels below the root node to
88 % allow representing each possible input color in a leaf. This becomes
89 % prohibitive because the tree's total number of nodes is 1 +
90 % sum(i=1, k, 8k).
91 %
92 % A complete tree would require 19,173,961 nodes for k = 8, Cmax = 255.
93 % Therefore, to avoid building a fully populated tree, QUANTIZE: (1)
94 % Initializes data structures for nodes only as they are needed; (2)
95 % Chooses a maximum depth for the tree as a function of the desired
96 % number of colors in the output image (currently log2(colormap size)).
97 %
98 % For each pixel in the input image, storage_class scans downward from
99 % the root of the color description tree. At each level of the tree it
100 % identifies the single node which represents a cube in RGB space
101 % containing the pixel's color. It updates the following data for each
102 % such node:
103 %
104 % n1: Number of pixels whose color is contained in the RGB cube which
105 % this node represents;
106 %
107 % n2: Number of pixels whose color is not represented in a node at
108 % lower depth in the tree; initially, n2 = 0 for all nodes except
109 % leaves of the tree.
110 %
111 % Sr, Sg, Sb: Sums of the red, green, and blue component values for all
112 % pixels not classified at a lower depth. The combination of these sums
113 % and n2 will ultimately characterize the mean color of a set of pixels
114 % represented by this node.
115 %
116 % E: the distance squared in RGB space between each pixel contained
117 % within a node and the nodes' center. This represents the
118 % quantization error for a node.
119 %
120 % Reduction repeatedly prunes the tree until the number of nodes with n2
121 % > 0 is less than or equal to the maximum number of colors allowed in
122 % the output image. On any given iteration over the tree, it selects
123 % those nodes whose E count is minimal for pruning and merges their color
124 % statistics upward. It uses a pruning threshold, Ep, to govern node
125 % selection as follows:
126 %
127 % Ep = 0
128 % while number of nodes with (n2 > 0) > required maximum number of colors
129 % prune all nodes such that E <= Ep
130 % Set Ep to minimum E in remaining nodes
131 %
132 % This has the effect of minimizing any quantization error when merging
133 % two nodes together.
134 %
135 % When a node to be pruned has offspring, the pruning procedure invokes
136 % itself recursively in order to prune the tree from the leaves upward.
137 % n2, Sr, Sg, and Sb in a node being pruned are always added to the
138 % corresponding data in that node's parent. This retains the pruned
139 % node's color characteristics for later averaging.
140 %
141 % For each node, n2 pixels exist for which that node represents the
142 % smallest volume in RGB space containing those pixel's colors. When n2
143 % > 0 the node will uniquely define a color in the output image. At the
144 % beginning of reduction, n2 = 0 for all nodes except a the leaves of
145 % the tree which represent colors present in the input image.
146 %
147 % The other pixel count, n1, indicates the total number of colors within
148 % the cubic volume which the node represents. This includes n1 - n2
149 % pixels whose colors should be defined by nodes at a lower level in the
150 % tree.
151 %
152 % Assignment generates the output image from the pruned tree. The output
153 % image consists of two parts: (1) A color map, which is an array of
154 % color descriptions (RGB triples) for each color present in the output
155 % image; (2) A pixel array, which represents each pixel as an index
156 % into the color map array.
157 %
158 % First, the assignment phase makes one pass over the pruned color
159 % description tree to establish the image's color map. For each node
160 % with n2 > 0, it divides Sr, Sg, and Sb by n2 . This produces the mean
161 % color of all pixels that classify no lower than this node. Each of
162 % these colors becomes an entry in the color map.
163 %
164 % Finally, the assignment phase reclassifies each pixel in the pruned
165 % tree to identify the deepest node containing the pixel's color. The
166 % pixel's value in the pixel array becomes the index of this node's mean
167 % color in the color map.
168 %
169 % This method is based on a similar algorithm written by Paul Raveling.
170 %
171 */
172 
173 /*
174  Include declarations.
175 */
176 #include "MagickCore/studio.h"
177 #include "MagickCore/artifact.h"
178 #include "MagickCore/attribute.h"
179 #include "MagickCore/cache-view.h"
180 #include "MagickCore/color.h"
182 #include "MagickCore/colormap.h"
183 #include "MagickCore/colorspace.h"
185 #include "MagickCore/compare.h"
186 #include "MagickCore/enhance.h"
187 #include "MagickCore/exception.h"
189 #include "MagickCore/histogram.h"
190 #include "MagickCore/image.h"
192 #include "MagickCore/list.h"
193 #include "MagickCore/memory_.h"
195 #include "MagickCore/monitor.h"
197 #include "MagickCore/option.h"
200 #include "MagickCore/quantize.h"
201 #include "MagickCore/quantum.h"
203 #include "MagickCore/random_.h"
204 #include "MagickCore/resource_.h"
205 #include "MagickCore/string_.h"
208 
209 /*
210  Define declarations.
211 */
212 #if !defined(__APPLE__) && !defined(TARGET_OS_IPHONE)
213 #define CacheShift 2
214 #else
215 #define CacheShift 3
216 #endif
217 #define ErrorQueueLength 16
218 #define ErrorRelativeWeight PerceptibleReciprocal(16)
219 #define MaxNodes 266817
220 #define MaxTreeDepth 8
221 #define NodesInAList 1920
222 
223 /*
224  Typdef declarations.
225 */
226 typedef struct _DoublePixelPacket
227 {
228  double
230  green,
231  blue,
232  alpha;
234 
235 typedef struct _NodeInfo
236 {
237  struct _NodeInfo
238  *parent,
239  *child[16];
240 
243 
246 
247  double
249 
250  size_t
252  id,
253  level;
254 } NodeInfo;
255 
256 typedef struct _Nodes
257 {
258  NodeInfo
260 
261  struct _Nodes
262  *next;
263 } Nodes;
264 
265 typedef struct _CubeInfo
266 {
267  NodeInfo
268  *root;
269 
270  size_t
273 
274  ssize_t
276 
279 
282 
283  double
287 
288  size_t
290  free_nodes,
291  color_number;
292 
293  NodeInfo
295 
296  Nodes
297  *node_queue;
298 
299  MemoryInfo
301 
302  ssize_t
304 
307 
308  double
311 
314 
317 
318  ssize_t
319  x,
320  y;
321 
322  size_t
324 
327 
330 } CubeInfo;
331 
332 /*
333  Method prototypes.
334 */
335 static CubeInfo
336  *GetCubeInfo(const QuantizeInfo *,const size_t,const size_t);
337 
338 static NodeInfo
339  *GetNodeInfo(CubeInfo *,const size_t,const size_t,NodeInfo *);
340 
341 static MagickBooleanType
347 
348 static void
349  ClosestColor(const Image *,CubeInfo *,const NodeInfo *),
352  PruneLevel(CubeInfo *,const NodeInfo *),
354  ReduceImageColors(const Image *,CubeInfo *);
355 
356 /*
357 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
358 % %
359 % %
360 % %
361 % A c q u i r e Q u a n t i z e I n f o %
362 % %
363 % %
364 % %
365 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
366 %
367 % AcquireQuantizeInfo() allocates the QuantizeInfo structure.
368 %
369 % The format of the AcquireQuantizeInfo method is:
370 %
371 % QuantizeInfo *AcquireQuantizeInfo(const ImageInfo *image_info)
372 %
373 % A description of each parameter follows:
374 %
375 % o image_info: the image info.
376 %
377 */
379 {
381  *quantize_info;
382 
383  quantize_info=(QuantizeInfo *) AcquireCriticalMemory(sizeof(*quantize_info));
384  GetQuantizeInfo(quantize_info);
385  if (image_info != (ImageInfo *) NULL)
386  {
387  const char
388  *option;
389 
390  quantize_info->dither_method=image_info->dither == MagickFalse ?
392  option=GetImageOption(image_info,"dither");
393  if (option != (const char *) NULL)
396  quantize_info->measure_error=image_info->verbose;
397  }
398  return(quantize_info);
399 }
400 
401 /*
402 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
403 % %
404 % %
405 % %
406 + A s s i g n I m a g e C o l o r s %
407 % %
408 % %
409 % %
410 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
411 %
412 % AssignImageColors() generates the output image from the pruned tree. The
413 % output image consists of two parts: (1) A color map, which is an array
414 % of color descriptions (RGB triples) for each color present in the
415 % output image; (2) A pixel array, which represents each pixel as an
416 % index into the color map array.
417 %
418 % First, the assignment phase makes one pass over the pruned color
419 % description tree to establish the image's color map. For each node
420 % with n2 > 0, it divides Sr, Sg, and Sb by n2 . This produces the mean
421 % color of all pixels that classify no lower than this node. Each of
422 % these colors becomes an entry in the color map.
423 %
424 % Finally, the assignment phase reclassifies each pixel in the pruned
425 % tree to identify the deepest node containing the pixel's color. The
426 % pixel's value in the pixel array becomes the index of this node's mean
427 % color in the color map.
428 %
429 % The format of the AssignImageColors() method is:
430 %
431 % MagickBooleanType AssignImageColors(Image *image,CubeInfo *cube_info)
432 %
433 % A description of each parameter follows.
434 %
435 % o image: the image.
436 %
437 % o cube_info: A pointer to the Cube structure.
438 %
439 */
440 
441 static inline void AssociateAlphaPixel(const Image *image,
442  const CubeInfo *cube_info,const Quantum *pixel,DoublePixelPacket *alpha_pixel)
443 {
444  double
445  alpha;
446 
447  if ((cube_info->associate_alpha == MagickFalse) ||
448  (GetPixelAlpha(image,pixel) == OpaqueAlpha))
449  {
450  alpha_pixel->red=(double) GetPixelRed(image,pixel);
451  alpha_pixel->green=(double) GetPixelGreen(image,pixel);
452  alpha_pixel->blue=(double) GetPixelBlue(image,pixel);
453  alpha_pixel->alpha=(double) GetPixelAlpha(image,pixel);
454  return;
455  }
456  alpha=(double) (QuantumScale*GetPixelAlpha(image,pixel));
457  alpha_pixel->red=alpha*GetPixelRed(image,pixel);
458  alpha_pixel->green=alpha*GetPixelGreen(image,pixel);
459  alpha_pixel->blue=alpha*GetPixelBlue(image,pixel);
460  alpha_pixel->alpha=(double) GetPixelAlpha(image,pixel);
461 }
462 
463 static inline void AssociateAlphaPixelInfo(const CubeInfo *cube_info,
464  const PixelInfo *pixel,DoublePixelPacket *alpha_pixel)
465 {
466  double
467  alpha;
468 
469  if ((cube_info->associate_alpha == MagickFalse) ||
470  (pixel->alpha == OpaqueAlpha))
471  {
472  alpha_pixel->red=(double) pixel->red;
473  alpha_pixel->green=(double) pixel->green;
474  alpha_pixel->blue=(double) pixel->blue;
475  alpha_pixel->alpha=(double) pixel->alpha;
476  return;
477  }
478  alpha=(double) (QuantumScale*pixel->alpha);
479  alpha_pixel->red=alpha*pixel->red;
480  alpha_pixel->green=alpha*pixel->green;
481  alpha_pixel->blue=alpha*pixel->blue;
482  alpha_pixel->alpha=(double) pixel->alpha;
483 }
484 
485 static inline size_t ColorToNodeId(const CubeInfo *cube_info,
486  const DoublePixelPacket *pixel,size_t index)
487 {
488  size_t
489  id;
490 
491  id=(size_t) (((ScaleQuantumToChar(ClampPixel(pixel->red)) >> index) & 0x01) |
492  ((ScaleQuantumToChar(ClampPixel(pixel->green)) >> index) & 0x01) << 1 |
493  ((ScaleQuantumToChar(ClampPixel(pixel->blue)) >> index) & 0x01) << 2);
494  if (cube_info->associate_alpha != MagickFalse)
495  id|=((ScaleQuantumToChar(ClampPixel(pixel->alpha)) >> index) & 0x1) << 3;
496  return(id);
497 }
498 
500  ExceptionInfo *exception)
501 {
502 #define AssignImageTag "Assign/Image"
503 
505  colorspace;
506 
507  ssize_t
508  y;
509 
510  /*
511  Allocate image colormap.
512  */
513  colorspace=image->colorspace;
514  if (cube_info->quantize_info->colorspace != UndefinedColorspace)
515  (void) TransformImageColorspace(image,cube_info->quantize_info->colorspace,
516  exception);
517  cube_info->transparent_pixels=0;
518  cube_info->transparent_index=(-1);
519  if (SetImageColormap(image,cube_info,exception) == MagickFalse)
520  return(MagickFalse);
521  /*
522  Create a reduced color image.
523  */
524  if (cube_info->quantize_info->dither_method != NoDitherMethod)
525  (void) DitherImage(image,cube_info,exception);
526  else
527  {
528  CacheView
529  *image_view;
530 
532  status;
533 
534  status=MagickTrue;
535  image_view=AcquireAuthenticCacheView(image,exception);
536 #if defined(MAGICKCORE_OPENMP_SUPPORT)
537  #pragma omp parallel for schedule(static) shared(status) \
538  magick_number_threads(image,image,image->rows,1)
539 #endif
540  for (y=0; y < (ssize_t) image->rows; y++)
541  {
542  CubeInfo
543  cube;
544 
545  Quantum
546  *magick_restrict q;
547 
548  ssize_t
549  count,
550  x;
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  const NodeInfo
568  *node_info;
569 
570  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 
633  image->rows);
634  if (proceed == MagickFalse)
635  status=MagickFalse;
636  }
637  }
638  image_view=DestroyCacheView(image_view);
639  }
640  if (cube_info->quantize_info->measure_error != MagickFalse)
641  (void) GetImageQuantizeError(image,exception);
642  if ((cube_info->quantize_info->number_colors == 2) &&
644  {
645  double
646  intensity;
647 
648  /*
649  Monochrome image.
650  */
651  intensity=GetPixelInfoLuma(image->colormap+0) < QuantumRange/2.0 ? 0.0 :
652  QuantumRange;
653  if (image->colors > 1)
654  {
655  intensity=0.0;
656  if (GetPixelInfoLuma(image->colormap+0) >
657  GetPixelInfoLuma(image->colormap+1))
658  intensity=(double) QuantumRange;
659  }
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  (IssRGBCompatibleColorspace(colorspace) == MagickFalse))
673  (void) TransformImageColorspace(image,colorspace,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 != UndefinedPixelTrait ? 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 
760  double
761  bisect;
762 
764  error,
765  mid,
766  midpoint,
767  pixel;
768 
770  proceed;
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 != image->colorspace)
789  {
790  if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
791  (cube_info->quantize_info->colorspace != CMYKColorspace))
792  (void) TransformImageColorspace((Image *) image,
793  cube_info->quantize_info->colorspace,exception);
794  else
797  exception);
798  }
799  midpoint.red=(double) QuantumRange/2.0;
800  midpoint.green=(double) QuantumRange/2.0;
801  midpoint.blue=(double) QuantumRange/2.0;
802  midpoint.alpha=(double) QuantumRange/2.0;
803  error.alpha=0.0;
804  image_view=AcquireVirtualCacheView(image,exception);
805  for (y=0; y < (ssize_t) image->rows; y++)
806  {
807  const Quantum
808  *magick_restrict p;
809 
810  ssize_t
811  x;
812 
813  p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
814  if (p == (const Quantum *) NULL)
815  break;
816  if (cube_info->nodes > MaxNodes)
817  {
818  /*
819  Prune one level if the color tree is too large.
820  */
821  PruneLevel(cube_info,cube_info->root);
822  cube_info->depth--;
823  }
824  for (x=0; x < (ssize_t) image->columns; x+=(ssize_t) count)
825  {
826  /*
827  Start at the root and descend the color cube tree.
828  */
829  for (count=1; (x+(ssize_t) count) < (ssize_t) image->columns; count++)
830  {
831  PixelInfo
832  packet;
833 
834  GetPixelInfoPixel(image,p+count*GetPixelChannels(image),&packet);
835  if (IsPixelEquivalent(image,p,&packet) == MagickFalse)
836  break;
837  }
838  AssociateAlphaPixel(image,cube_info,p,&pixel);
839  index=MaxTreeDepth-1;
840  bisect=((double) QuantumRange+1.0)/2.0;
841  mid=midpoint;
842  node_info=cube_info->root;
843  for (level=1; level <= MaxTreeDepth; level++)
844  {
845  double
846  distance;
847 
848  bisect*=0.5;
849  id=ColorToNodeId(cube_info,&pixel,index);
850  mid.red+=(id & 1) != 0 ? bisect : -bisect;
851  mid.green+=(id & 2) != 0 ? bisect : -bisect;
852  mid.blue+=(id & 4) != 0 ? bisect : -bisect;
853  mid.alpha+=(id & 8) != 0 ? bisect : -bisect;
854  if (node_info->child[id] == (NodeInfo *) NULL)
855  {
856  /*
857  Set colors of new node to contain pixel.
858  */
859  node_info->child[id]=GetNodeInfo(cube_info,id,level,node_info);
860  if (node_info->child[id] == (NodeInfo *) NULL)
861  {
862  (void) ThrowMagickException(exception,GetMagickModule(),
863  ResourceLimitError,"MemoryAllocationFailed","`%s'",
864  image->filename);
865  continue;
866  }
867  if (level == MaxTreeDepth)
868  cube_info->colors++;
869  }
870  /*
871  Approximate the quantization error represented by this node.
872  */
873  node_info=node_info->child[id];
874  error.red=QuantumScale*(pixel.red-mid.red);
875  error.green=QuantumScale*(pixel.green-mid.green);
876  error.blue=QuantumScale*(pixel.blue-mid.blue);
877  if (cube_info->associate_alpha != MagickFalse)
878  error.alpha=QuantumScale*(pixel.alpha-mid.alpha);
879  distance=(double) (error.red*error.red+error.green*error.green+
880  error.blue*error.blue+error.alpha*error.alpha);
881  if (IsNaN(distance) != 0)
882  distance=0.0;
883  node_info->quantize_error+=count*sqrt(distance);
884  cube_info->root->quantize_error+=node_info->quantize_error;
885  index--;
886  }
887  /*
888  Sum RGB for this leaf for later derivation of the mean cube color.
889  */
890  node_info->number_unique+=count;
891  node_info->total_color.red+=count*QuantumScale*ClampPixel(pixel.red);
892  node_info->total_color.green+=count*QuantumScale*ClampPixel(pixel.green);
893  node_info->total_color.blue+=count*QuantumScale*ClampPixel(pixel.blue);
894  if (cube_info->associate_alpha != MagickFalse)
895  node_info->total_color.alpha+=count*QuantumScale*
896  ClampPixel(pixel.alpha);
897  else
898  node_info->total_color.alpha+=count*QuantumScale*
900  p+=count*GetPixelChannels(image);
901  }
902  if (cube_info->colors > cube_info->maximum_colors)
903  {
904  PruneToCubeDepth(cube_info,cube_info->root);
905  break;
906  }
908  image->rows);
909  if (proceed == MagickFalse)
910  break;
911  }
912  for (y++; y < (ssize_t) image->rows; y++)
913  {
914  const Quantum
915  *magick_restrict p;
916 
917  ssize_t
918  x;
919 
920  p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
921  if (p == (const Quantum *) NULL)
922  break;
923  if (cube_info->nodes > MaxNodes)
924  {
925  /*
926  Prune one level if the color tree is too large.
927  */
928  PruneLevel(cube_info,cube_info->root);
929  cube_info->depth--;
930  }
931  for (x=0; x < (ssize_t) image->columns; x+=(ssize_t) count)
932  {
933  /*
934  Start at the root and descend the color cube tree.
935  */
936  for (count=1; (x+(ssize_t) count) < (ssize_t) image->columns; count++)
937  {
938  PixelInfo
939  packet;
940 
941  GetPixelInfoPixel(image,p+count*GetPixelChannels(image),&packet);
942  if (IsPixelEquivalent(image,p,&packet) == MagickFalse)
943  break;
944  }
945  AssociateAlphaPixel(image,cube_info,p,&pixel);
946  index=MaxTreeDepth-1;
947  bisect=((double) QuantumRange+1.0)/2.0;
948  mid=midpoint;
949  node_info=cube_info->root;
950  for (level=1; level <= cube_info->depth; level++)
951  {
952  double
953  distance;
954 
955  bisect*=0.5;
956  id=ColorToNodeId(cube_info,&pixel,index);
957  mid.red+=(id & 1) != 0 ? bisect : -bisect;
958  mid.green+=(id & 2) != 0 ? bisect : -bisect;
959  mid.blue+=(id & 4) != 0 ? bisect : -bisect;
960  mid.alpha+=(id & 8) != 0 ? bisect : -bisect;
961  if (node_info->child[id] == (NodeInfo *) NULL)
962  {
963  /*
964  Set colors of new node to contain pixel.
965  */
966  node_info->child[id]=GetNodeInfo(cube_info,id,level,node_info);
967  if (node_info->child[id] == (NodeInfo *) NULL)
968  {
969  (void) ThrowMagickException(exception,GetMagickModule(),
970  ResourceLimitError,"MemoryAllocationFailed","%s",
971  image->filename);
972  continue;
973  }
974  if (level == cube_info->depth)
975  cube_info->colors++;
976  }
977  /*
978  Approximate the quantization error represented by this node.
979  */
980  node_info=node_info->child[id];
981  error.red=QuantumScale*(pixel.red-mid.red);
982  error.green=QuantumScale*(pixel.green-mid.green);
983  error.blue=QuantumScale*(pixel.blue-mid.blue);
984  if (cube_info->associate_alpha != MagickFalse)
985  error.alpha=QuantumScale*(pixel.alpha-mid.alpha);
986  distance=(double) (error.red*error.red+error.green*error.green+
987  error.blue*error.blue+error.alpha*error.alpha);
988  if (IsNaN(distance) != 0)
989  distance=0.0;
990  node_info->quantize_error+=count*sqrt(distance);
991  cube_info->root->quantize_error+=node_info->quantize_error;
992  index--;
993  }
994  /*
995  Sum RGB for this leaf for later derivation of the mean cube color.
996  */
997  node_info->number_unique+=count;
998  node_info->total_color.red+=count*QuantumScale*ClampPixel(pixel.red);
999  node_info->total_color.green+=count*QuantumScale*ClampPixel(pixel.green);
1000  node_info->total_color.blue+=count*QuantumScale*ClampPixel(pixel.blue);
1001  if (cube_info->associate_alpha != MagickFalse)
1002  node_info->total_color.alpha+=count*QuantumScale*
1003  ClampPixel(pixel.alpha);
1004  else
1005  node_info->total_color.alpha+=count*QuantumScale*
1007  p+=count*GetPixelChannels(image);
1008  }
1010  image->rows);
1011  if (proceed == MagickFalse)
1012  break;
1013  }
1014  image_view=DestroyCacheView(image_view);
1015  if (cube_info->quantize_info->colorspace != image->colorspace)
1016  if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
1017  (cube_info->quantize_info->colorspace != CMYKColorspace))
1018  (void) TransformImageColorspace((Image *) image,sRGBColorspace,exception);
1019  return(y < (ssize_t) image->rows ? MagickFalse : MagickTrue);
1020 }
1021 
1022 /*
1023 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1024 % %
1025 % %
1026 % %
1027 % C l o n e Q u a n t i z e I n f o %
1028 % %
1029 % %
1030 % %
1031 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1032 %
1033 % CloneQuantizeInfo() makes a duplicate of the given quantize info structure,
1034 % or if quantize info is NULL, a new one.
1035 %
1036 % The format of the CloneQuantizeInfo method is:
1037 %
1038 % QuantizeInfo *CloneQuantizeInfo(const QuantizeInfo *quantize_info)
1039 %
1040 % A description of each parameter follows:
1041 %
1042 % o clone_info: Method CloneQuantizeInfo returns a duplicate of the given
1043 % quantize info, or if image info is NULL a new one.
1044 %
1045 % o quantize_info: a structure of type info.
1046 %
1047 */
1049 {
1050  QuantizeInfo
1051  *clone_info;
1052 
1053  clone_info=(QuantizeInfo *) AcquireCriticalMemory(sizeof(*clone_info));
1054  GetQuantizeInfo(clone_info);
1055  if (quantize_info == (QuantizeInfo *) NULL)
1056  return(clone_info);
1057  clone_info->number_colors=quantize_info->number_colors;
1058  clone_info->tree_depth=quantize_info->tree_depth;
1059  clone_info->dither_method=quantize_info->dither_method;
1060  clone_info->colorspace=quantize_info->colorspace;
1061  clone_info->measure_error=quantize_info->measure_error;
1062  return(clone_info);
1063 }
1064 
1065 /*
1066 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1067 % %
1068 % %
1069 % %
1070 + C l o s e s t C o l o r %
1071 % %
1072 % %
1073 % %
1074 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1075 %
1076 % ClosestColor() traverses the color cube tree at a particular node and
1077 % determines which colormap entry best represents the input color.
1078 %
1079 % The format of the ClosestColor method is:
1080 %
1081 % void ClosestColor(const Image *image,CubeInfo *cube_info,
1082 % const NodeInfo *node_info)
1083 %
1084 % A description of each parameter follows.
1085 %
1086 % o image: the image.
1087 %
1088 % o cube_info: A pointer to the Cube structure.
1089 %
1090 % o node_info: the address of a structure of type NodeInfo which points to a
1091 % node in the color cube tree that is to be pruned.
1092 %
1093 */
1094 static void ClosestColor(const Image *image,CubeInfo *cube_info,
1095  const NodeInfo *node_info)
1096 {
1097  size_t
1098  number_children;
1099 
1100  ssize_t
1101  i;
1102 
1103  /*
1104  Traverse any children.
1105  */
1106  number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
1107  for (i=0; i < (ssize_t) number_children; i++)
1108  if (node_info->child[i] != (NodeInfo *) NULL)
1109  ClosestColor(image,cube_info,node_info->child[i]);
1110  if (node_info->number_unique != 0)
1111  {
1112  double
1113  alpha,
1114  beta,
1115  distance,
1116  pixel;
1117 
1119  *magick_restrict q;
1120 
1121  PixelInfo
1122  *magick_restrict p;
1123 
1124  /*
1125  Determine if this color is "closest".
1126  */
1127  p=image->colormap+node_info->color_number;
1128  q=(&cube_info->target);
1129  alpha=1.0;
1130  beta=1.0;
1131  if (cube_info->associate_alpha != MagickFalse)
1132  {
1133  alpha=(MagickRealType) (QuantumScale*p->alpha);
1134  beta=(MagickRealType) (QuantumScale*q->alpha);
1135  }
1136  pixel=alpha*p->red-beta*q->red;
1137  distance=pixel*pixel;
1138  if (distance <= cube_info->distance)
1139  {
1140  pixel=alpha*p->green-beta*q->green;
1141  distance+=pixel*pixel;
1142  if (distance <= cube_info->distance)
1143  {
1144  pixel=alpha*p->blue-beta*q->blue;
1145  distance+=pixel*pixel;
1146  if (distance <= cube_info->distance)
1147  {
1148  if (cube_info->associate_alpha != MagickFalse)
1149  {
1150  pixel=p->alpha-q->alpha;
1151  distance+=pixel*pixel;
1152  }
1153  if (distance <= cube_info->distance)
1154  {
1155  cube_info->distance=distance;
1156  cube_info->color_number=node_info->color_number;
1157  }
1158  }
1159  }
1160  }
1161  }
1162 }
1163 
1164 /*
1165 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1166 % %
1167 % %
1168 % %
1169 % C o m p r e s s I m a g e C o l o r m a p %
1170 % %
1171 % %
1172 % %
1173 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1174 %
1175 % CompressImageColormap() compresses an image colormap by removing any
1176 % duplicate or unused color entries.
1177 %
1178 % The format of the CompressImageColormap method is:
1179 %
1180 % MagickBooleanType CompressImageColormap(Image *image,
1181 % ExceptionInfo *exception)
1182 %
1183 % A description of each parameter follows:
1184 %
1185 % o image: the image.
1186 %
1187 % o exception: return any errors or warnings in this structure.
1188 %
1189 */
1191  ExceptionInfo *exception)
1192 {
1193  QuantizeInfo
1194  quantize_info;
1195 
1196  assert(image != (Image *) NULL);
1197  assert(image->signature == MagickCoreSignature);
1198  if (image->debug != MagickFalse)
1199  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
1200  if (IsPaletteImage(image) == MagickFalse)
1201  return(MagickFalse);
1202  GetQuantizeInfo(&quantize_info);
1203  quantize_info.number_colors=image->colors;
1204  quantize_info.tree_depth=MaxTreeDepth;
1205  return(QuantizeImage(&quantize_info,image,exception));
1206 }
1207 
1208 /*
1209 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1210 % %
1211 % %
1212 % %
1213 + D e f i n e I m a g e C o l o r m a p %
1214 % %
1215 % %
1216 % %
1217 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1218 %
1219 % DefineImageColormap() traverses the color cube tree and notes each colormap
1220 % entry. A colormap entry is any node in the color cube tree where the
1221 % of unique colors is not zero.
1222 %
1223 % The format of the DefineImageColormap method is:
1224 %
1225 % void DefineImageColormap(Image *image,CubeInfo *cube_info,
1226 % NodeInfo *node_info)
1227 %
1228 % A description of each parameter follows.
1229 %
1230 % o image: the image.
1231 %
1232 % o cube_info: A pointer to the Cube structure.
1233 %
1234 % o node_info: the address of a structure of type NodeInfo which points to a
1235 % node in the color cube tree that is to be pruned.
1236 %
1237 */
1238 static void DefineImageColormap(Image *image,CubeInfo *cube_info,
1239  NodeInfo *node_info)
1240 {
1241  size_t
1242  number_children;
1243 
1244  ssize_t
1245  i;
1246 
1247  /*
1248  Traverse any children.
1249  */
1250  number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
1251  for (i=0; i < (ssize_t) number_children; i++)
1252  if (node_info->child[i] != (NodeInfo *) NULL)
1253  DefineImageColormap(image,cube_info,node_info->child[i]);
1254  if (node_info->number_unique != 0)
1255  {
1256  double
1257  alpha;
1258 
1259  PixelInfo
1260  *magick_restrict q;
1261 
1262  /*
1263  Colormap entry is defined by the mean color in this cube.
1264  */
1265  q=image->colormap+image->colors;
1266  alpha=(double) ((MagickOffsetType) node_info->number_unique);
1267  alpha=PerceptibleReciprocal(alpha);
1268  if (cube_info->associate_alpha == MagickFalse)
1269  {
1270  q->red=(double) ClampToQuantum(alpha*QuantumRange*
1271  node_info->total_color.red);
1272  q->green=(double) ClampToQuantum(alpha*QuantumRange*
1273  node_info->total_color.green);
1274  q->blue=(double) ClampToQuantum(alpha*QuantumRange*
1275  node_info->total_color.blue);
1276  q->alpha=(double) OpaqueAlpha;
1277  }
1278  else
1279  {
1280  double
1281  opacity;
1282 
1283  opacity=(double) (alpha*QuantumRange*node_info->total_color.alpha);
1284  q->alpha=(double) ClampToQuantum(opacity);
1285  if (q->alpha == OpaqueAlpha)
1286  {
1287  q->red=(double) ClampToQuantum(alpha*QuantumRange*
1288  node_info->total_color.red);
1289  q->green=(double) ClampToQuantum(alpha*QuantumRange*
1290  node_info->total_color.green);
1291  q->blue=(double) ClampToQuantum(alpha*QuantumRange*
1292  node_info->total_color.blue);
1293  }
1294  else
1295  {
1296  double
1297  gamma;
1298 
1299  gamma=(double) (QuantumScale*q->alpha);
1300  gamma=PerceptibleReciprocal(gamma);
1301  q->red=(double) ClampToQuantum(alpha*gamma*QuantumRange*
1302  node_info->total_color.red);
1303  q->green=(double) ClampToQuantum(alpha*gamma*QuantumRange*
1304  node_info->total_color.green);
1305  q->blue=(double) ClampToQuantum(alpha*gamma*QuantumRange*
1306  node_info->total_color.blue);
1307  if (node_info->number_unique > cube_info->transparent_pixels)
1308  {
1309  cube_info->transparent_pixels=node_info->number_unique;
1310  cube_info->transparent_index=(ssize_t) image->colors;
1311  }
1312  }
1313  }
1314  node_info->color_number=image->colors++;
1315  }
1316 }
1317 
1318 /*
1319 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1320 % %
1321 % %
1322 % %
1323 + D e s t r o y C u b e I n f o %
1324 % %
1325 % %
1326 % %
1327 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1328 %
1329 % DestroyCubeInfo() deallocates memory associated with an image.
1330 %
1331 % The format of the DestroyCubeInfo method is:
1332 %
1333 % DestroyCubeInfo(CubeInfo *cube_info)
1334 %
1335 % A description of each parameter follows:
1336 %
1337 % o cube_info: the address of a structure of type CubeInfo.
1338 %
1339 */
1340 static void DestroyCubeInfo(CubeInfo *cube_info)
1341 {
1342  Nodes
1343  *nodes;
1344 
1345  /*
1346  Release color cube tree storage.
1347  */
1348  do
1349  {
1350  nodes=cube_info->node_queue->next;
1352  cube_info->node_queue->nodes);
1353  cube_info->node_queue=(Nodes *) RelinquishMagickMemory(
1354  cube_info->node_queue);
1355  cube_info->node_queue=nodes;
1356  } while (cube_info->node_queue != (Nodes *) NULL);
1357  if (cube_info->memory_info != (MemoryInfo *) NULL)
1358  cube_info->memory_info=RelinquishVirtualMemory(cube_info->memory_info);
1359  cube_info->quantize_info=DestroyQuantizeInfo(cube_info->quantize_info);
1360  cube_info=(CubeInfo *) RelinquishMagickMemory(cube_info);
1361 }
1362 
1363 /*
1364 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1365 % %
1366 % %
1367 % %
1368 % D e s t r o y Q u a n t i z e I n f o %
1369 % %
1370 % %
1371 % %
1372 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1373 %
1374 % DestroyQuantizeInfo() deallocates memory associated with an QuantizeInfo
1375 % structure.
1376 %
1377 % The format of the DestroyQuantizeInfo method is:
1378 %
1379 % QuantizeInfo *DestroyQuantizeInfo(QuantizeInfo *quantize_info)
1380 %
1381 % A description of each parameter follows:
1382 %
1383 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
1384 %
1385 */
1387 {
1388  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1389  assert(quantize_info != (QuantizeInfo *) NULL);
1390  assert(quantize_info->signature == MagickCoreSignature);
1391  quantize_info->signature=(~MagickCoreSignature);
1392  quantize_info=(QuantizeInfo *) RelinquishMagickMemory(quantize_info);
1393  return(quantize_info);
1394 }
1395 
1396 /*
1397 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1398 % %
1399 % %
1400 % %
1401 + D i t h e r I m a g e %
1402 % %
1403 % %
1404 % %
1405 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1406 %
1407 % DitherImage() distributes the difference between an original image and
1408 % the corresponding color reduced algorithm to neighboring pixels using
1409 % serpentine-scan Floyd-Steinberg error diffusion. DitherImage returns
1410 % MagickTrue if the image is dithered otherwise MagickFalse.
1411 %
1412 % The format of the DitherImage method is:
1413 %
1414 % MagickBooleanType DitherImage(Image *image,CubeInfo *cube_info,
1415 % ExceptionInfo *exception)
1416 %
1417 % A description of each parameter follows.
1418 %
1419 % o image: the image.
1420 %
1421 % o cube_info: A pointer to the Cube structure.
1422 %
1423 % o exception: return any errors or warnings in this structure.
1424 %
1425 */
1426 
1428 {
1429  ssize_t
1430  i;
1431 
1432  assert(pixels != (DoublePixelPacket **) NULL);
1433  for (i=0; i < (ssize_t) GetMagickResourceLimit(ThreadResource); i++)
1434  if (pixels[i] != (DoublePixelPacket *) NULL)
1435  pixels[i]=(DoublePixelPacket *) RelinquishMagickMemory(pixels[i]);
1436  pixels=(DoublePixelPacket **) RelinquishMagickMemory(pixels);
1437  return(pixels);
1438 }
1439 
1440 static DoublePixelPacket **AcquirePixelThreadSet(const size_t count)
1441 {
1443  **pixels;
1444 
1445  size_t
1446  number_threads;
1447 
1448  ssize_t
1449  i;
1450 
1451  number_threads=(size_t) GetMagickResourceLimit(ThreadResource);
1452  pixels=(DoublePixelPacket **) AcquireQuantumMemory(number_threads,
1453  sizeof(*pixels));
1454  if (pixels == (DoublePixelPacket **) NULL)
1455  return((DoublePixelPacket **) NULL);
1456  (void) memset(pixels,0,number_threads*sizeof(*pixels));
1457  for (i=0; i < (ssize_t) number_threads; i++)
1458  {
1459  pixels[i]=(DoublePixelPacket *) AcquireQuantumMemory(count,2*
1460  sizeof(**pixels));
1461  if (pixels[i] == (DoublePixelPacket *) NULL)
1462  return(DestroyPixelThreadSet(pixels));
1463  }
1464  return(pixels);
1465 }
1466 
1467 static inline ssize_t CacheOffset(CubeInfo *cube_info,
1468  const DoublePixelPacket *pixel)
1469 {
1470 #define RedShift(pixel) (((pixel) >> CacheShift) << (0*(8-CacheShift)))
1471 #define GreenShift(pixel) (((pixel) >> CacheShift) << (1*(8-CacheShift)))
1472 #define BlueShift(pixel) (((pixel) >> CacheShift) << (2*(8-CacheShift)))
1473 #define AlphaShift(pixel) (((pixel) >> CacheShift) << (3*(8-CacheShift)))
1474 
1475  ssize_t
1476  offset;
1477 
1478  offset=(ssize_t) (RedShift(ScaleQuantumToChar(ClampPixel(pixel->red))) |
1479  GreenShift(ScaleQuantumToChar(ClampPixel(pixel->green))) |
1480  BlueShift(ScaleQuantumToChar(ClampPixel(pixel->blue))));
1481  if (cube_info->associate_alpha != MagickFalse)
1482  offset|=AlphaShift(ScaleQuantumToChar(ClampPixel(pixel->alpha)));
1483  return(offset);
1484 }
1485 
1487  ExceptionInfo *exception)
1488 {
1489 #define DitherImageTag "Dither/Image"
1490 
1491  CacheView
1492  *image_view;
1493 
1495  **pixels;
1496 
1498  status;
1499 
1500  ssize_t
1501  y;
1502 
1503  /*
1504  Distribute quantization error using Floyd-Steinberg.
1505  */
1506  pixels=AcquirePixelThreadSet(image->columns);
1507  if (pixels == (DoublePixelPacket **) NULL)
1508  return(MagickFalse);
1509  status=MagickTrue;
1510  image_view=AcquireAuthenticCacheView(image,exception);
1511  for (y=0; y < (ssize_t) image->rows; y++)
1512  {
1513  const int
1514  id = GetOpenMPThreadId();
1515 
1516  CubeInfo
1517  cube;
1518 
1520  *current,
1521  *previous;
1522 
1523  Quantum
1524  *magick_restrict q;
1525 
1526  size_t
1527  index;
1528 
1529  ssize_t
1530  x,
1531  v;
1532 
1533  if (status == MagickFalse)
1534  continue;
1535  q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
1536  if (q == (Quantum *) NULL)
1537  {
1538  status=MagickFalse;
1539  continue;
1540  }
1541  cube=(*cube_info);
1542  current=pixels[id]+(y & 0x01)*image->columns;
1543  previous=pixels[id]+((y+1) & 0x01)*image->columns;
1544  v=(ssize_t) ((y & 0x01) != 0 ? -1 : 1);
1545  for (x=0; x < (ssize_t) image->columns; x++)
1546  {
1548  color,
1549  pixel;
1550 
1551  ssize_t
1552  i;
1553 
1554  ssize_t
1555  u;
1556 
1557  u=(y & 0x01) != 0 ? (ssize_t) image->columns-1-x : x;
1558  AssociateAlphaPixel(image,&cube,q+u*GetPixelChannels(image),&pixel);
1559  if (x > 0)
1560  {
1561  pixel.red+=7.0*cube_info->diffusion*current[u-v].red/16;
1562  pixel.green+=7.0*cube_info->diffusion*current[u-v].green/16;
1563  pixel.blue+=7.0*cube_info->diffusion*current[u-v].blue/16;
1564  if (cube.associate_alpha != MagickFalse)
1565  pixel.alpha+=7.0*cube_info->diffusion*current[u-v].alpha/16;
1566  }
1567  if (y > 0)
1568  {
1569  if (x < (ssize_t) (image->columns-1))
1570  {
1571  pixel.red+=cube_info->diffusion*previous[u+v].red/16;
1572  pixel.green+=cube_info->diffusion*previous[u+v].green/16;
1573  pixel.blue+=cube_info->diffusion*previous[u+v].blue/16;
1574  if (cube.associate_alpha != MagickFalse)
1575  pixel.alpha+=cube_info->diffusion*previous[u+v].alpha/16;
1576  }
1577  pixel.red+=5.0*cube_info->diffusion*previous[u].red/16;
1578  pixel.green+=5.0*cube_info->diffusion*previous[u].green/16;
1579  pixel.blue+=5.0*cube_info->diffusion*previous[u].blue/16;
1580  if (cube.associate_alpha != MagickFalse)
1581  pixel.alpha+=5.0*cube_info->diffusion*previous[u].alpha/16;
1582  if (x > 0)
1583  {
1584  pixel.red+=3.0*cube_info->diffusion*previous[u-v].red/16;
1585  pixel.green+=3.0*cube_info->diffusion*previous[u-v].green/16;
1586  pixel.blue+=3.0*cube_info->diffusion*previous[u-v].blue/16;
1587  if (cube.associate_alpha != MagickFalse)
1588  pixel.alpha+=3.0*cube_info->diffusion*previous[u-v].alpha/16;
1589  }
1590  }
1591  pixel.red=(double) ClampPixel(pixel.red);
1592  pixel.green=(double) ClampPixel(pixel.green);
1593  pixel.blue=(double) ClampPixel(pixel.blue);
1594  if (cube.associate_alpha != MagickFalse)
1595  pixel.alpha=(double) ClampPixel(pixel.alpha);
1596  i=CacheOffset(&cube,&pixel);
1597  if (cube.cache[i] < 0)
1598  {
1599  NodeInfo
1600  *node_info;
1601 
1602  size_t
1603  node_id;
1604 
1605  /*
1606  Identify the deepest node containing the pixel's color.
1607  */
1608  node_info=cube.root;
1609  for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
1610  {
1611  node_id=ColorToNodeId(&cube,&pixel,index);
1612  if (node_info->child[node_id] == (NodeInfo *) NULL)
1613  break;
1614  node_info=node_info->child[node_id];
1615  }
1616  /*
1617  Find closest color among siblings and their children.
1618  */
1619  cube.target=pixel;
1620  cube.distance=(double) (4.0*(QuantumRange+1.0)*(QuantumRange+1.0)+
1621  1.0);
1622  ClosestColor(image,&cube,node_info->parent);
1623  cube.cache[i]=(ssize_t) cube.color_number;
1624  }
1625  /*
1626  Assign pixel to closest colormap entry.
1627  */
1628  index=(size_t) cube.cache[i];
1629  if (image->storage_class == PseudoClass)
1630  SetPixelIndex(image,(Quantum) index,q+u*GetPixelChannels(image));
1632  {
1633  SetPixelRed(image,ClampToQuantum(image->colormap[index].red),
1634  q+u*GetPixelChannels(image));
1635  SetPixelGreen(image,ClampToQuantum(image->colormap[index].green),
1636  q+u*GetPixelChannels(image));
1637  SetPixelBlue(image,ClampToQuantum(image->colormap[index].blue),
1638  q+u*GetPixelChannels(image));
1639  if (cube.associate_alpha != MagickFalse)
1640  SetPixelAlpha(image,ClampToQuantum(image->colormap[index].alpha),
1641  q+u*GetPixelChannels(image));
1642  }
1643  if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
1644  status=MagickFalse;
1645  /*
1646  Store the error.
1647  */
1648  AssociateAlphaPixelInfo(&cube,image->colormap+index,&color);
1649  current[u].red=pixel.red-color.red;
1650  current[u].green=pixel.green-color.green;
1651  current[u].blue=pixel.blue-color.blue;
1652  if (cube.associate_alpha != MagickFalse)
1653  current[u].alpha=pixel.alpha-color.alpha;
1654  if (image->progress_monitor != (MagickProgressMonitor) NULL)
1655  {
1657  proceed;
1658 
1660  image->rows);
1661  if (proceed == MagickFalse)
1662  status=MagickFalse;
1663  }
1664  }
1665  }
1666  image_view=DestroyCacheView(image_view);
1667  pixels=DestroyPixelThreadSet(pixels);
1668  return(MagickTrue);
1669 }
1670 
1672  CubeInfo *cube_info,const unsigned int direction,ExceptionInfo *exception)
1673 {
1674 #define DitherImageTag "Dither/Image"
1675 
1676  CubeInfo
1677  *p;
1678 
1680  color,
1681  pixel;
1682 
1684  proceed;
1685 
1686  size_t
1687  index;
1688 
1689  p=cube_info;
1690  if ((p->x >= 0) && (p->x < (ssize_t) image->columns) &&
1691  (p->y >= 0) && (p->y < (ssize_t) image->rows))
1692  {
1693  Quantum
1694  *magick_restrict q;
1695 
1696  ssize_t
1697  i;
1698 
1699  /*
1700  Distribute error.
1701  */
1702  q=GetCacheViewAuthenticPixels(image_view,p->x,p->y,1,1,exception);
1703  if (q == (Quantum *) NULL)
1704  return(MagickFalse);
1705  AssociateAlphaPixel(image,cube_info,q,&pixel);
1706  for (i=0; i < ErrorQueueLength; i++)
1707  {
1708  pixel.red+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1709  p->error[i].red;
1710  pixel.green+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1711  p->error[i].green;
1712  pixel.blue+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1713  p->error[i].blue;
1714  if (cube_info->associate_alpha != MagickFalse)
1715  pixel.alpha+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1716  p->error[i].alpha;
1717  }
1718  pixel.red=(double) ClampPixel(pixel.red);
1719  pixel.green=(double) ClampPixel(pixel.green);
1720  pixel.blue=(double) ClampPixel(pixel.blue);
1721  if (cube_info->associate_alpha != MagickFalse)
1722  pixel.alpha=(double) ClampPixel(pixel.alpha);
1723  i=CacheOffset(cube_info,&pixel);
1724  if (p->cache[i] < 0)
1725  {
1726  NodeInfo
1727  *node_info;
1728 
1729  size_t
1730  id;
1731 
1732  /*
1733  Identify the deepest node containing the pixel's color.
1734  */
1735  node_info=p->root;
1736  for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
1737  {
1738  id=ColorToNodeId(cube_info,&pixel,index);
1739  if (node_info->child[id] == (NodeInfo *) NULL)
1740  break;
1741  node_info=node_info->child[id];
1742  }
1743  /*
1744  Find closest color among siblings and their children.
1745  */
1746  p->target=pixel;
1747  p->distance=(double) (4.0*(QuantumRange+1.0)*((double)
1748  QuantumRange+1.0)+1.0);
1749  ClosestColor(image,p,node_info->parent);
1750  p->cache[i]=(ssize_t) p->color_number;
1751  }
1752  /*
1753  Assign pixel to closest colormap entry.
1754  */
1755  index=(size_t) p->cache[i];
1756  if (image->storage_class == PseudoClass)
1757  SetPixelIndex(image,(Quantum) index,q);
1758  if (cube_info->quantize_info->measure_error == MagickFalse)
1759  {
1760  SetPixelRed(image,ClampToQuantum(image->colormap[index].red),q);
1761  SetPixelGreen(image,ClampToQuantum(image->colormap[index].green),q);
1762  SetPixelBlue(image,ClampToQuantum(image->colormap[index].blue),q);
1763  if (cube_info->associate_alpha != MagickFalse)
1764  SetPixelAlpha(image,ClampToQuantum(image->colormap[index].alpha),q);
1765  }
1766  if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
1767  return(MagickFalse);
1768  /*
1769  Propagate the error as the last entry of the error queue.
1770  */
1771  (void) memmove(p->error,p->error+1,(ErrorQueueLength-1)*
1772  sizeof(p->error[0]));
1773  AssociateAlphaPixelInfo(cube_info,image->colormap+index,&color);
1774  p->error[ErrorQueueLength-1].red=pixel.red-color.red;
1775  p->error[ErrorQueueLength-1].green=pixel.green-color.green;
1776  p->error[ErrorQueueLength-1].blue=pixel.blue-color.blue;
1777  if (cube_info->associate_alpha != MagickFalse)
1778  p->error[ErrorQueueLength-1].alpha=pixel.alpha-color.alpha;
1779  proceed=SetImageProgress(image,DitherImageTag,p->offset,p->span);
1780  if (proceed == MagickFalse)
1781  return(MagickFalse);
1782  p->offset++;
1783  }
1784  switch (direction)
1785  {
1786  case WestGravity: p->x--; break;
1787  case EastGravity: p->x++; break;
1788  case NorthGravity: p->y--; break;
1789  case SouthGravity: p->y++; break;
1790  }
1791  return(MagickTrue);
1792 }
1793 
1794 static MagickBooleanType Riemersma(Image *image,CacheView *image_view,
1795  CubeInfo *cube_info,const size_t level,const unsigned int direction,
1796  ExceptionInfo *exception)
1797 {
1799  status;
1800 
1801  status=MagickTrue;
1802  if (level == 1)
1803  switch (direction)
1804  {
1805  case WestGravity:
1806  {
1807  status=RiemersmaDither(image,image_view,cube_info,EastGravity,
1808  exception);
1809  if (status != MagickFalse)
1810  status=RiemersmaDither(image,image_view,cube_info,SouthGravity,
1811  exception);
1812  if (status != MagickFalse)
1813  status=RiemersmaDither(image,image_view,cube_info,WestGravity,
1814  exception);
1815  break;
1816  }
1817  case EastGravity:
1818  {
1819  status=RiemersmaDither(image,image_view,cube_info,WestGravity,
1820  exception);
1821  if (status != MagickFalse)
1822  status=RiemersmaDither(image,image_view,cube_info,NorthGravity,
1823  exception);
1824  if (status != MagickFalse)
1825  status=RiemersmaDither(image,image_view,cube_info,EastGravity,
1826  exception);
1827  break;
1828  }
1829  case NorthGravity:
1830  {
1831  status=RiemersmaDither(image,image_view,cube_info,SouthGravity,
1832  exception);
1833  if (status != MagickFalse)
1834  status=RiemersmaDither(image,image_view,cube_info,EastGravity,
1835  exception);
1836  if (status != MagickFalse)
1837  status=RiemersmaDither(image,image_view,cube_info,NorthGravity,
1838  exception);
1839  break;
1840  }
1841  case SouthGravity:
1842  {
1843  status=RiemersmaDither(image,image_view,cube_info,NorthGravity,
1844  exception);
1845  if (status != MagickFalse)
1846  status=RiemersmaDither(image,image_view,cube_info,WestGravity,
1847  exception);
1848  if (status != MagickFalse)
1849  status=RiemersmaDither(image,image_view,cube_info,SouthGravity,
1850  exception);
1851  break;
1852  }
1853  default:
1854  break;
1855  }
1856  else
1857  switch (direction)
1858  {
1859  case WestGravity:
1860  {
1861  status=Riemersma(image,image_view,cube_info,level-1,NorthGravity,
1862  exception);
1863  if (status != MagickFalse)
1864  status=RiemersmaDither(image,image_view,cube_info,EastGravity,
1865  exception);
1866  if (status != MagickFalse)
1867  status=Riemersma(image,image_view,cube_info,level-1,WestGravity,
1868  exception);
1869  if (status != MagickFalse)
1870  status=RiemersmaDither(image,image_view,cube_info,SouthGravity,
1871  exception);
1872  if (status != MagickFalse)
1873  status=Riemersma(image,image_view,cube_info,level-1,WestGravity,
1874  exception);
1875  if (status != MagickFalse)
1876  status=RiemersmaDither(image,image_view,cube_info,WestGravity,
1877  exception);
1878  if (status != MagickFalse)
1879  status=Riemersma(image,image_view,cube_info,level-1,SouthGravity,
1880  exception);
1881  break;
1882  }
1883  case EastGravity:
1884  {
1885  status=Riemersma(image,image_view,cube_info,level-1,SouthGravity,
1886  exception);
1887  if (status != MagickFalse)
1888  status=RiemersmaDither(image,image_view,cube_info,WestGravity,
1889  exception);
1890  if (status != MagickFalse)
1891  status=Riemersma(image,image_view,cube_info,level-1,EastGravity,
1892  exception);
1893  if (status != MagickFalse)
1894  status=RiemersmaDither(image,image_view,cube_info,NorthGravity,
1895  exception);
1896  if (status != MagickFalse)
1897  status=Riemersma(image,image_view,cube_info,level-1,EastGravity,
1898  exception);
1899  if (status != MagickFalse)
1900  status=RiemersmaDither(image,image_view,cube_info,EastGravity,
1901  exception);
1902  if (status != MagickFalse)
1903  status=Riemersma(image,image_view,cube_info,level-1,NorthGravity,
1904  exception);
1905  break;
1906  }
1907  case NorthGravity:
1908  {
1909  status=Riemersma(image,image_view,cube_info,level-1,WestGravity,
1910  exception);
1911  if (status != MagickFalse)
1912  status=RiemersmaDither(image,image_view,cube_info,SouthGravity,
1913  exception);
1914  if (status != MagickFalse)
1915  status=Riemersma(image,image_view,cube_info,level-1,NorthGravity,
1916  exception);
1917  if (status != MagickFalse)
1918  status=RiemersmaDither(image,image_view,cube_info,EastGravity,
1919  exception);
1920  if (status != MagickFalse)
1921  status=Riemersma(image,image_view,cube_info,level-1,NorthGravity,
1922  exception);
1923  if (status != MagickFalse)
1924  status=RiemersmaDither(image,image_view,cube_info,NorthGravity,
1925  exception);
1926  if (status != MagickFalse)
1927  status=Riemersma(image,image_view,cube_info,level-1,EastGravity,
1928  exception);
1929  break;
1930  }
1931  case SouthGravity:
1932  {
1933  status=Riemersma(image,image_view,cube_info,level-1,EastGravity,
1934  exception);
1935  if (status != MagickFalse)
1936  status=RiemersmaDither(image,image_view,cube_info,NorthGravity,
1937  exception);
1938  if (status != MagickFalse)
1939  status=Riemersma(image,image_view,cube_info,level-1,SouthGravity,
1940  exception);
1941  if (status != MagickFalse)
1942  status=RiemersmaDither(image,image_view,cube_info,WestGravity,
1943  exception);
1944  if (status != MagickFalse)
1945  status=Riemersma(image,image_view,cube_info,level-1,SouthGravity,
1946  exception);
1947  if (status != MagickFalse)
1948  status=RiemersmaDither(image,image_view,cube_info,SouthGravity,
1949  exception);
1950  if (status != MagickFalse)
1951  status=Riemersma(image,image_view,cube_info,level-1,WestGravity,
1952  exception);
1953  break;
1954  }
1955  default:
1956  break;
1957  }
1958  return(status);
1959 }
1960 
1961 static MagickBooleanType DitherImage(Image *image,CubeInfo *cube_info,
1962  ExceptionInfo *exception)
1963 {
1964  CacheView
1965  *image_view;
1966 
1967  const char
1968  *artifact;
1969 
1971  status;
1972 
1973  size_t
1974  extent,
1975  level;
1976 
1977  artifact=GetImageArtifact(image,"dither:diffusion-amount");
1978  if (artifact != (const char *) NULL)
1979  cube_info->diffusion=StringToDoubleInterval(artifact,1.0);
1981  return(FloydSteinbergDither(image,cube_info,exception));
1982  /*
1983  Distribute quantization error along a Hilbert curve.
1984  */
1985  (void) memset(cube_info->error,0,ErrorQueueLength*sizeof(*cube_info->error));
1986  cube_info->x=0;
1987  cube_info->y=0;
1988  extent=MagickMax(image->columns,image->rows);
1989  level=(size_t) log2((double) extent);
1990  if (((size_t) 1UL << level) < extent)
1991  level++;
1992  cube_info->offset=0;
1993  cube_info->span=(MagickSizeType) image->columns*image->rows;
1994  image_view=AcquireAuthenticCacheView(image,exception);
1995  status=MagickTrue;
1996  if (level > 0)
1997  status=Riemersma(image,image_view,cube_info,level,NorthGravity,exception);
1998  if (status != MagickFalse)
1999  status=RiemersmaDither(image,image_view,cube_info,ForgetGravity,exception);
2000  image_view=DestroyCacheView(image_view);
2001  return(status);
2002 }
2003 
2004 /*
2005 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2006 % %
2007 % %
2008 % %
2009 + G e t C u b e I n f o %
2010 % %
2011 % %
2012 % %
2013 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2014 %
2015 % GetCubeInfo() initialize the Cube data structure.
2016 %
2017 % The format of the GetCubeInfo method is:
2018 %
2019 % CubeInfo GetCubeInfo(const QuantizeInfo *quantize_info,
2020 % const size_t depth,const size_t maximum_colors)
2021 %
2022 % A description of each parameter follows.
2023 %
2024 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
2025 %
2026 % o depth: Normally, this integer value is zero or one. A zero or
2027 % one tells Quantize to choose a optimal tree depth of Log4(number_colors).
2028 % A tree of this depth generally allows the best representation of the
2029 % reference image with the least amount of memory and the fastest
2030 % computational speed. In some cases, such as an image with low color
2031 % dispersion (a few number of colors), a value other than
2032 % Log4(number_colors) is required. To expand the color tree completely,
2033 % use a value of 8.
2034 %
2035 % o maximum_colors: maximum colors.
2036 %
2037 */
2038 static CubeInfo *GetCubeInfo(const QuantizeInfo *quantize_info,
2039  const size_t depth,const size_t maximum_colors)
2040 {
2041  CubeInfo
2042  *cube_info;
2043 
2044  double
2045  weight;
2046 
2047  size_t
2048  length;
2049 
2050  ssize_t
2051  i;
2052 
2053  /*
2054  Initialize tree to describe color cube_info.
2055  */
2056  cube_info=(CubeInfo *) AcquireMagickMemory(sizeof(*cube_info));
2057  if (cube_info == (CubeInfo *) NULL)
2058  return((CubeInfo *) NULL);
2059  (void) memset(cube_info,0,sizeof(*cube_info));
2060  cube_info->depth=depth;
2061  if (cube_info->depth > MaxTreeDepth)
2062  cube_info->depth=MaxTreeDepth;
2063  if (cube_info->depth < 2)
2064  cube_info->depth=2;
2065  cube_info->maximum_colors=maximum_colors;
2066  /*
2067  Initialize root node.
2068  */
2069  cube_info->root=GetNodeInfo(cube_info,0,0,(NodeInfo *) NULL);
2070  if (cube_info->root == (NodeInfo *) NULL)
2071  return((CubeInfo *) NULL);
2072  cube_info->root->parent=cube_info->root;
2073  cube_info->quantize_info=CloneQuantizeInfo(quantize_info);
2074  if (cube_info->quantize_info->dither_method == NoDitherMethod)
2075  return(cube_info);
2076  /*
2077  Initialize dither resources.
2078  */
2079  length=(size_t) (1UL << (4*(8-CacheShift)));
2080  cube_info->memory_info=AcquireVirtualMemory(length,sizeof(*cube_info->cache));
2081  if (cube_info->memory_info == (MemoryInfo *) NULL)
2082  return((CubeInfo *) NULL);
2083  cube_info->cache=(ssize_t *) GetVirtualMemoryBlob(cube_info->memory_info);
2084  /*
2085  Initialize color cache.
2086  */
2087  (void) memset(cube_info->cache,(-1),sizeof(*cube_info->cache)*length);
2088  /*
2089  Distribute weights along a curve of exponential decay.
2090  */
2091  weight=1.0;
2092  for (i=0; i < ErrorQueueLength; i++)
2093  {
2094  cube_info->weights[i]=PerceptibleReciprocal(weight);
2095  weight*=exp(log(1.0/ErrorRelativeWeight)/(ErrorQueueLength-1.0));
2096  }
2097  cube_info->diffusion=1.0;
2098  return(cube_info);
2099 }
2100 
2101 /*
2102 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2103 % %
2104 % %
2105 % %
2106 + G e t N o d e I n f o %
2107 % %
2108 % %
2109 % %
2110 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2111 %
2112 % GetNodeInfo() allocates memory for a new node in the color cube tree and
2113 % presets all fields to zero.
2114 %
2115 % The format of the GetNodeInfo method is:
2116 %
2117 % NodeInfo *GetNodeInfo(CubeInfo *cube_info,const size_t id,
2118 % const size_t level,NodeInfo *parent)
2119 %
2120 % A description of each parameter follows.
2121 %
2122 % o node: The GetNodeInfo method returns a pointer to a queue of nodes.
2123 %
2124 % o id: Specifies the child number of the node.
2125 %
2126 % o level: Specifies the level in the storage_class the node resides.
2127 %
2128 */
2129 static NodeInfo *GetNodeInfo(CubeInfo *cube_info,const size_t id,
2130  const size_t level,NodeInfo *parent)
2131 {
2132  NodeInfo
2133  *node_info;
2134 
2135  if (cube_info->free_nodes == 0)
2136  {
2137  Nodes
2138  *nodes;
2139 
2140  /*
2141  Allocate a new queue of nodes.
2142  */
2143  nodes=(Nodes *) AcquireMagickMemory(sizeof(*nodes));
2144  if (nodes == (Nodes *) NULL)
2145  return((NodeInfo *) NULL);
2147  sizeof(*nodes->nodes));
2148  if (nodes->nodes == (NodeInfo *) NULL)
2149  return((NodeInfo *) NULL);
2150  nodes->next=cube_info->node_queue;
2151  cube_info->node_queue=nodes;
2152  cube_info->next_node=nodes->nodes;
2153  cube_info->free_nodes=NodesInAList;
2154  }
2155  cube_info->nodes++;
2156  cube_info->free_nodes--;
2157  node_info=cube_info->next_node++;
2158  (void) memset(node_info,0,sizeof(*node_info));
2159  node_info->parent=parent;
2160  node_info->id=id;
2161  node_info->level=level;
2162  return(node_info);
2163 }
2164 
2165 /*
2166 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2167 % %
2168 % %
2169 % %
2170 % G e t I m a g e Q u a n t i z e E r r o r %
2171 % %
2172 % %
2173 % %
2174 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2175 %
2176 % GetImageQuantizeError() measures the difference between the original
2177 % and quantized images. This difference is the total quantization error.
2178 % The error is computed by summing over all pixels in an image the distance
2179 % squared in RGB space between each reference pixel value and its quantized
2180 % value. These values are computed:
2181 %
2182 % o mean_error_per_pixel: This value is the mean error for any single
2183 % pixel in the image.
2184 %
2185 % o normalized_mean_square_error: This value is the normalized mean
2186 % quantization error for any single pixel in the image. This distance
2187 % measure is normalized to a range between 0 and 1. It is independent
2188 % of the range of red, green, and blue values in the image.
2189 %
2190 % o normalized_maximum_square_error: Thsi value is the normalized
2191 % maximum quantization error for any single pixel in the image. This
2192 % distance measure is normalized to a range between 0 and 1. It is
2193 % independent of the range of red, green, and blue values in your image.
2194 %
2195 % The format of the GetImageQuantizeError method is:
2196 %
2197 % MagickBooleanType GetImageQuantizeError(Image *image,
2198 % ExceptionInfo *exception)
2199 %
2200 % A description of each parameter follows.
2201 %
2202 % o image: the image.
2203 %
2204 % o exception: return any errors or warnings in this structure.
2205 %
2206 */
2208  ExceptionInfo *exception)
2209 {
2210  CacheView
2211  *image_view;
2212 
2213  double
2214  alpha,
2215  area,
2216  beta,
2217  distance,
2218  maximum_error,
2219  mean_error,
2220  mean_error_per_pixel;
2221 
2222  ssize_t
2223  index,
2224  y;
2225 
2226  assert(image != (Image *) NULL);
2227  assert(image->signature == MagickCoreSignature);
2228  if (image->debug != MagickFalse)
2229  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
2230  image->total_colors=GetNumberColors(image,(FILE *) NULL,exception);
2231  (void) memset(&image->error,0,sizeof(image->error));
2232  if (image->storage_class == DirectClass)
2233  return(MagickTrue);
2234  alpha=1.0;
2235  beta=1.0;
2236  area=3.0*image->columns*image->rows;
2237  maximum_error=0.0;
2238  mean_error_per_pixel=0.0;
2239  mean_error=0.0;
2240  image_view=AcquireVirtualCacheView(image,exception);
2241  for (y=0; y < (ssize_t) image->rows; y++)
2242  {
2243  const Quantum
2244  *magick_restrict p;
2245 
2246  ssize_t
2247  x;
2248 
2249  p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
2250  if (p == (const Quantum *) NULL)
2251  break;
2252  for (x=0; x < (ssize_t) image->columns; x++)
2253  {
2254  index=(ssize_t) GetPixelIndex(image,p);
2255  if (image->alpha_trait != UndefinedPixelTrait)
2256  {
2257  alpha=(double) (QuantumScale*GetPixelAlpha(image,p));
2258  beta=(double) (QuantumScale*image->colormap[index].alpha);
2259  }
2260  distance=fabs((double) (alpha*GetPixelRed(image,p)-beta*
2261  image->colormap[index].red));
2262  mean_error_per_pixel+=distance;
2263  mean_error+=distance*distance;
2264  if (distance > maximum_error)
2265  maximum_error=distance;
2266  distance=fabs((double) (alpha*GetPixelGreen(image,p)-beta*
2267  image->colormap[index].green));
2268  mean_error_per_pixel+=distance;
2269  mean_error+=distance*distance;
2270  if (distance > maximum_error)
2271  maximum_error=distance;
2272  distance=fabs((double) (alpha*GetPixelBlue(image,p)-beta*
2273  image->colormap[index].blue));
2274  mean_error_per_pixel+=distance;
2275  mean_error+=distance*distance;
2276  if (distance > maximum_error)
2277  maximum_error=distance;
2278  p+=GetPixelChannels(image);
2279  }
2280  }
2281  image_view=DestroyCacheView(image_view);
2282  image->error.mean_error_per_pixel=(double) mean_error_per_pixel/area;
2284  mean_error/area;
2285  image->error.normalized_maximum_error=(double) QuantumScale*maximum_error;
2286  return(MagickTrue);
2287 }
2288 
2289 /*
2290 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2291 % %
2292 % %
2293 % %
2294 % G e t Q u a n t i z e I n f o %
2295 % %
2296 % %
2297 % %
2298 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2299 %
2300 % GetQuantizeInfo() initializes the QuantizeInfo structure.
2301 %
2302 % The format of the GetQuantizeInfo method is:
2303 %
2304 % GetQuantizeInfo(QuantizeInfo *quantize_info)
2305 %
2306 % A description of each parameter follows:
2307 %
2308 % o quantize_info: Specifies a pointer to a QuantizeInfo structure.
2309 %
2310 */
2312 {
2313  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
2314  assert(quantize_info != (QuantizeInfo *) NULL);
2315  (void) memset(quantize_info,0,sizeof(*quantize_info));
2316  quantize_info->number_colors=256;
2317  quantize_info->dither_method=RiemersmaDitherMethod;
2318  quantize_info->colorspace=UndefinedColorspace;
2319  quantize_info->measure_error=MagickFalse;
2320  quantize_info->signature=MagickCoreSignature;
2321 }
2322 
2323 /*
2324 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2325 % %
2326 % %
2327 % %
2328 % K m e a n s I m a g e %
2329 % %
2330 % %
2331 % %
2332 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2333 %
2334 % KmeansImage() applies k-means color reduction to an image. This is a
2335 % colorspace clustering or segmentation technique.
2336 %
2337 % The format of the KmeansImage method is:
2338 %
2339 % MagickBooleanType KmeansImage(Image *image,const size_t number_colors,
2340 % const size_t max_iterations,const double tolerance,
2341 % ExceptionInfo *exception)
2342 %
2343 % A description of each parameter follows:
2344 %
2345 % o image: the image.
2346 %
2347 % o number_colors: number of colors to use as seeds.
2348 %
2349 % o max_iterations: maximum number of iterations while converging.
2350 %
2351 % o tolerance: the maximum tolerance.
2352 %
2353 % o exception: return any errors or warnings in this structure.
2354 %
2355 */
2356 
2357 typedef struct _KmeansInfo
2358 {
2359  double
2361  green,
2362  blue,
2363  alpha,
2364  black,
2365  count,
2366  distortion;
2367 } KmeansInfo;
2368 
2370 {
2371  ssize_t
2372  i;
2373 
2374  assert(kmeans_info != (KmeansInfo **) NULL);
2375  for (i=0; i < (ssize_t) GetMagickResourceLimit(ThreadResource); i++)
2376  if (kmeans_info[i] != (KmeansInfo *) NULL)
2377  kmeans_info[i]=(KmeansInfo *) RelinquishMagickMemory(kmeans_info[i]);
2378  kmeans_info=(KmeansInfo **) RelinquishMagickMemory(kmeans_info);
2379  return(kmeans_info);
2380 }
2381 
2382 static KmeansInfo **AcquireKmeansThreadSet(const size_t number_colors)
2383 {
2384  KmeansInfo
2385  **kmeans_info;
2386 
2387  ssize_t
2388  i;
2389 
2390  size_t
2391  number_threads;
2392 
2393  number_threads=(size_t) GetMagickResourceLimit(ThreadResource);
2394  kmeans_info=(KmeansInfo **) AcquireQuantumMemory(number_threads,
2395  sizeof(*kmeans_info));
2396  if (kmeans_info == (KmeansInfo **) NULL)
2397  return((KmeansInfo **) NULL);
2398  (void) memset(kmeans_info,0,number_threads*sizeof(*kmeans_info));
2399  for (i=0; i < (ssize_t) number_threads; i++)
2400  {
2401  kmeans_info[i]=(KmeansInfo *) AcquireQuantumMemory(number_colors,
2402  sizeof(**kmeans_info));
2403  if (kmeans_info[i] == (KmeansInfo *) NULL)
2404  return(DestroyKmeansThreadSet(kmeans_info));
2405  }
2406  return(kmeans_info);
2407 }
2408 
2409 static inline double KmeansMetric(const Image *magick_restrict image,
2411 {
2412  double
2413  gamma,
2414  metric,
2415  pixel;
2416 
2417  gamma=1.0;
2418  metric=0.0;
2419  if ((image->alpha_trait != UndefinedPixelTrait) ||
2420  (q->alpha_trait != UndefinedPixelTrait))
2421  {
2422  pixel=GetPixelAlpha(image,p)-(q->alpha_trait != UndefinedPixelTrait ?
2423  q->alpha : OpaqueAlpha);
2424  metric+=pixel*pixel;
2425  if (image->alpha_trait != UndefinedPixelTrait)
2426  gamma*=QuantumScale*GetPixelAlpha(image,p);
2427  if (q->alpha_trait != UndefinedPixelTrait)
2428  gamma*=QuantumScale*q->alpha;
2429  }
2430  if (image->colorspace == CMYKColorspace)
2431  {
2432  pixel=QuantumScale*(GetPixelBlack(image,p)-q->black);
2433  metric+=gamma*pixel*pixel;
2434  gamma*=QuantumScale*(QuantumRange-GetPixelBlack(image,p));
2435  gamma*=QuantumScale*(QuantumRange-q->black);
2436  }
2437  metric*=3.0;
2438  pixel=QuantumScale*(GetPixelRed(image,p)-q->red);
2439  if (IsHueCompatibleColorspace(image->colorspace) != MagickFalse)
2440  {
2441  if (fabs((double) pixel) > 0.5)
2442  pixel-=0.5;
2443  pixel*=2.0;
2444  }
2445  metric+=gamma*pixel*pixel;
2446  pixel=QuantumScale*(GetPixelGreen(image,p)-q->green);
2447  metric+=gamma*pixel*pixel;
2448  pixel=QuantumScale*(GetPixelBlue(image,p)-q->blue);
2449  metric+=gamma*pixel*pixel;
2450  return(metric);
2451 }
2452 
2454  const size_t number_colors,const size_t max_iterations,const double tolerance,
2455  ExceptionInfo *exception)
2456 {
2457 #define KmeansImageTag "Kmeans/Image"
2458 #define RandomColorComponent(info) (QuantumRange*GetPseudoRandomValue(info))
2459 
2460  CacheView
2461  *image_view;
2462 
2463  const char
2464  *colors;
2465 
2466  double
2467  previous_tolerance;
2468 
2469  KmeansInfo
2470  **kmeans_pixels;
2471 
2473  verbose,
2474  status;
2475 
2476  ssize_t
2477  n;
2478 
2479  size_t
2480  number_threads;
2481 
2482  assert(image != (Image *) NULL);
2483  assert(image->signature == MagickCoreSignature);
2484  if (image->debug != MagickFalse)
2485  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
2486  assert(exception != (ExceptionInfo *) NULL);
2487  assert(exception->signature == MagickCoreSignature);
2488  colors=GetImageArtifact(image,"kmeans:seed-colors");
2489  if (colors == (const char *) NULL)
2490  {
2491  CubeInfo
2492  *cube_info;
2493 
2494  QuantizeInfo
2495  *quantize_info;
2496 
2497  size_t
2498  depth;
2499 
2500  /*
2501  Seed clusters from color quantization.
2502  */
2503  quantize_info=AcquireQuantizeInfo((ImageInfo *) NULL);
2504  quantize_info->colorspace=image->colorspace;
2505  quantize_info->number_colors=number_colors;
2506  quantize_info->dither_method=NoDitherMethod;
2507  n=number_colors;
2508  for (depth=1; n != 0; depth++)
2509  n>>=2;
2510  cube_info=GetCubeInfo(quantize_info,depth,number_colors);
2511  if (cube_info == (CubeInfo *) NULL)
2512  {
2513  quantize_info=DestroyQuantizeInfo(quantize_info);
2514  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
2515  image->filename);
2516  }
2517  status=ClassifyImageColors(cube_info,image,exception);
2518  if (status != MagickFalse)
2519  {
2520  if (cube_info->colors > cube_info->maximum_colors)
2521  ReduceImageColors(image,cube_info);
2522  status=SetImageColormap(image,cube_info,exception);
2523  }
2524  DestroyCubeInfo(cube_info);
2525  quantize_info=DestroyQuantizeInfo(quantize_info);
2526  if (status == MagickFalse)
2527  return(status);
2528  }
2529  else
2530  {
2531  char
2532  color[MagickPathExtent];
2533 
2534  const char
2535  *p;
2536 
2537  /*
2538  Seed clusters from color list (e.g. red;green;blue).
2539  */
2540  status=AcquireImageColormap(image,number_colors,exception);
2541  if (status == MagickFalse)
2542  return(status);
2543  for (n=0, p=colors; n < (ssize_t) image->colors; n++)
2544  {
2545  const char
2546  *q;
2547 
2548  for (q=p; *q != '\0'; q++)
2549  if (*q == ';')
2550  break;
2551  (void) CopyMagickString(color,p,(size_t) MagickMin(q-p+1,
2552  MagickPathExtent));
2553  (void) QueryColorCompliance(color,AllCompliance,image->colormap+n,
2554  exception);
2555  if (*q == '\0')
2556  {
2557  n++;
2558  break;
2559  }
2560  p=q+1;
2561  }
2562  if (n < (ssize_t) image->colors)
2563  {
2564  RandomInfo
2565  *random_info;
2566 
2567  /*
2568  Seed clusters from random values.
2569  */
2571  for ( ; n < (ssize_t) image->colors; n++)
2572  {
2573  (void) QueryColorCompliance("#000",AllCompliance,image->colormap+n,
2574  exception);
2578  if (image->alpha_trait != UndefinedPixelTrait)
2580  if (image->colorspace == CMYKColorspace)
2582  }
2584  }
2585  }
2586  /*
2587  Iterative refinement.
2588  */
2589  kmeans_pixels=AcquireKmeansThreadSet(number_colors);
2590  if (kmeans_pixels == (KmeansInfo **) NULL)
2591  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
2592  image->filename);
2593  previous_tolerance=0.0;
2594  verbose=IsStringTrue(GetImageArtifact(image,"debug"));
2595  number_threads=(size_t) GetMagickResourceLimit(ThreadResource);
2596  image_view=AcquireAuthenticCacheView(image,exception);
2597  for (n=0; n < (ssize_t) max_iterations; n++)
2598  {
2599  double
2600  distortion;
2601 
2602  ssize_t
2603  j,
2604  y;
2605 
2606  for (j=0; j < (ssize_t) number_threads; j++)
2607  (void) memset(kmeans_pixels[j],0,image->colors*sizeof(*kmeans_pixels[j]));
2608 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2609  #pragma omp parallel for schedule(dynamic) shared(status) \
2610  magick_number_threads(image,image,image->rows,1)
2611 #endif
2612  for (y=0; y < (ssize_t) image->rows; y++)
2613  {
2614  const int
2615  id = GetOpenMPThreadId();
2616 
2617  Quantum
2618  *magick_restrict q;
2619 
2620  ssize_t
2621  x;
2622 
2623  if (status == MagickFalse)
2624  continue;
2625  q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
2626  if (q == (Quantum *) NULL)
2627  {
2628  status=MagickFalse;
2629  continue;
2630  }
2631  for (x=0; x < (ssize_t) image->columns; x++)
2632  {
2633  double
2634  min_distance;
2635 
2636  ssize_t
2637  i,
2638  k;
2639 
2640  /*
2641  Assign each pixel whose mean has the least squared color distance.
2642  */
2643  k=0;
2644  min_distance=KmeansMetric(image,q,image->colormap+0);
2645  for (i=1; i < (ssize_t) image->colors; i++)
2646  {
2647  double
2648  distance;
2649 
2650  if (min_distance <= MagickEpsilon)
2651  break;
2652  distance=KmeansMetric(image,q,image->colormap+i);
2653  if (distance < min_distance)
2654  {
2655  min_distance=distance;
2656  k=i;
2657  }
2658  }
2659  kmeans_pixels[id][k].red+=QuantumScale*GetPixelRed(image,q);
2660  kmeans_pixels[id][k].green+=QuantumScale*GetPixelGreen(image,q);
2661  kmeans_pixels[id][k].blue+=QuantumScale*GetPixelBlue(image,q);
2662  if (image->alpha_trait != UndefinedPixelTrait)
2663  kmeans_pixels[id][k].alpha+=QuantumScale*GetPixelAlpha(image,q);
2664  if (image->colorspace == CMYKColorspace)
2665  kmeans_pixels[id][k].black+=QuantumScale*GetPixelBlack(image,q);
2666  kmeans_pixels[id][k].count++;
2667  kmeans_pixels[id][k].distortion+=min_distance;
2668  SetPixelIndex(image,(Quantum) k,q);
2669  q+=GetPixelChannels(image);
2670  }
2671  if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
2672  status=MagickFalse;
2673  }
2674  if (status == MagickFalse)
2675  break;
2676  /*
2677  Reduce sums to [0] entry.
2678  */
2679  for (j=1; j < (ssize_t) number_threads; j++)
2680  {
2681  ssize_t
2682  k;
2683 
2684  for (k=0; k < (ssize_t) image->colors; k++)
2685  {
2686  kmeans_pixels[0][k].red+=kmeans_pixels[j][k].red;
2687  kmeans_pixels[0][k].green+=kmeans_pixels[j][k].green;
2688  kmeans_pixels[0][k].blue+=kmeans_pixels[j][k].blue;
2689  if (image->alpha_trait != UndefinedPixelTrait)
2690  kmeans_pixels[0][k].alpha+=kmeans_pixels[j][k].alpha;
2691  if (image->colorspace == CMYKColorspace)
2692  kmeans_pixels[0][k].black+=kmeans_pixels[j][k].black;
2693  kmeans_pixels[0][k].count+=kmeans_pixels[j][k].count;
2694  kmeans_pixels[0][k].distortion+=kmeans_pixels[j][k].distortion;
2695  }
2696  }
2697  /*
2698  Calculate the new means (centroids) of the pixels in the new clusters.
2699  */
2700  distortion=0.0;
2701  for (j=0; j < (ssize_t) image->colors; j++)
2702  {
2703  double
2704  gamma;
2705 
2706  gamma=PerceptibleReciprocal((double) kmeans_pixels[0][j].count);
2707  image->colormap[j].red=gamma*QuantumRange*kmeans_pixels[0][j].red;
2708  image->colormap[j].green=gamma*QuantumRange*kmeans_pixels[0][j].green;
2709  image->colormap[j].blue=gamma*QuantumRange*kmeans_pixels[0][j].blue;
2710  if (image->alpha_trait != UndefinedPixelTrait)
2711  image->colormap[j].alpha=gamma*QuantumRange*kmeans_pixels[0][j].alpha;
2712  if (image->colorspace == CMYKColorspace)
2713  image->colormap[j].black=gamma*QuantumRange*kmeans_pixels[0][j].black;
2714  distortion+=kmeans_pixels[0][j].distortion;
2715  }
2716  if (verbose != MagickFalse)
2717  (void) FormatLocaleFile(stderr,"distortion[%.20g]: %*g %*g\n",(double) n,
2718  GetMagickPrecision(),distortion,GetMagickPrecision(),
2719  fabs(distortion-previous_tolerance));
2720  if (fabs(distortion-previous_tolerance) <= tolerance)
2721  break;
2722  previous_tolerance=distortion;
2723  if (image->progress_monitor != (MagickProgressMonitor) NULL)
2724  {
2726  proceed;
2727 
2729  max_iterations);
2730  if (proceed == MagickFalse)
2731  status=MagickFalse;
2732  }
2733  }
2734  image_view=DestroyCacheView(image_view);
2735  kmeans_pixels=DestroyKmeansThreadSet(kmeans_pixels);
2736  if (image->progress_monitor != (MagickProgressMonitor) NULL)
2738  max_iterations-1,max_iterations);
2739  if (status == MagickFalse)
2740  return(status);
2741  return(SyncImage(image,exception));
2742 }
2743 
2744 /*
2745 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2746 % %
2747 % %
2748 % %
2749 % P o s t e r i z e I m a g e %
2750 % %
2751 % %
2752 % %
2753 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2754 %
2755 % PosterizeImage() reduces the image to a limited number of colors for a
2756 % "poster" effect.
2757 %
2758 % The format of the PosterizeImage method is:
2759 %
2760 % MagickBooleanType PosterizeImage(Image *image,const size_t levels,
2761 % const DitherMethod dither_method,ExceptionInfo *exception)
2762 %
2763 % A description of each parameter follows:
2764 %
2765 % o image: Specifies a pointer to an Image structure.
2766 %
2767 % o levels: Number of color levels allowed in each channel. Very low values
2768 % (2, 3, or 4) have the most visible effect.
2769 %
2770 % o dither_method: choose from UndefinedDitherMethod, NoDitherMethod,
2771 % RiemersmaDitherMethod, FloydSteinbergDitherMethod.
2772 %
2773 % o exception: return any errors or warnings in this structure.
2774 %
2775 */
2776 
2777 static inline double MagickRound(double x)
2778 {
2779  /*
2780  Round the fraction to nearest integer.
2781  */
2782  if ((x-floor(x)) < (ceil(x)-x))
2783  return(floor(x));
2784  return(ceil(x));
2785 }
2786 
2788  const DitherMethod dither_method,ExceptionInfo *exception)
2789 {
2790 #define PosterizeImageTag "Posterize/Image"
2791 #define PosterizePixel(pixel) ClampToQuantum((MagickRealType) QuantumRange*( \
2792  MagickRound(QuantumScale*pixel*(levels-1)))/MagickMax((ssize_t) levels-1,1))
2793 
2794  CacheView
2795  *image_view;
2796 
2798  status;
2799 
2801  progress;
2802 
2803  QuantizeInfo
2804  *quantize_info;
2805 
2806  ssize_t
2807  i;
2808 
2809  ssize_t
2810  y;
2811 
2812  assert(image != (Image *) NULL);
2813  assert(image->signature == MagickCoreSignature);
2814  if (image->debug != MagickFalse)
2815  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
2816  assert(exception != (ExceptionInfo *) NULL);
2817  assert(exception->signature == MagickCoreSignature);
2818  if (image->storage_class == PseudoClass)
2819 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2820  #pragma omp parallel for schedule(static) shared(progress,status) \
2821  magick_number_threads(image,image,image->colors,1)
2822 #endif
2823  for (i=0; i < (ssize_t) image->colors; i++)
2824  {
2825  /*
2826  Posterize colormap.
2827  */
2828  if ((GetPixelRedTraits(image) & UpdatePixelTrait) != 0)
2829  image->colormap[i].red=(double)
2830  PosterizePixel(image->colormap[i].red);
2831  if ((GetPixelGreenTraits(image) & UpdatePixelTrait) != 0)
2832  image->colormap[i].green=(double)
2833  PosterizePixel(image->colormap[i].green);
2834  if ((GetPixelBlueTraits(image) & UpdatePixelTrait) != 0)
2835  image->colormap[i].blue=(double)
2836  PosterizePixel(image->colormap[i].blue);
2837  if ((GetPixelAlphaTraits(image) & UpdatePixelTrait) != 0)
2838  image->colormap[i].alpha=(double)
2839  PosterizePixel(image->colormap[i].alpha);
2840  }
2841  /*
2842  Posterize image.
2843  */
2844  status=MagickTrue;
2845  progress=0;
2846  image_view=AcquireAuthenticCacheView(image,exception);
2847 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2848  #pragma omp parallel for schedule(static) shared(progress,status) \
2849  magick_number_threads(image,image,image->rows,1)
2850 #endif
2851  for (y=0; y < (ssize_t) image->rows; y++)
2852  {
2853  Quantum
2854  *magick_restrict q;
2855 
2856  ssize_t
2857  x;
2858 
2859  if (status == MagickFalse)
2860  continue;
2861  q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
2862  if (q == (Quantum *) NULL)
2863  {
2864  status=MagickFalse;
2865  continue;
2866  }
2867  for (x=0; x < (ssize_t) image->columns; x++)
2868  {
2869  if ((GetPixelRedTraits(image) & UpdatePixelTrait) != 0)
2870  SetPixelRed(image,PosterizePixel(GetPixelRed(image,q)),q);
2871  if ((GetPixelGreenTraits(image) & UpdatePixelTrait) != 0)
2872  SetPixelGreen(image,PosterizePixel(GetPixelGreen(image,q)),q);
2873  if ((GetPixelBlueTraits(image) & UpdatePixelTrait) != 0)
2874  SetPixelBlue(image,PosterizePixel(GetPixelBlue(image,q)),q);
2875  if (((GetPixelBlackTraits(image) & UpdatePixelTrait) != 0) &&
2876  (image->colorspace == CMYKColorspace))
2877  SetPixelBlack(image,PosterizePixel(GetPixelBlack(image,q)),q);
2878  if (((GetPixelAlphaTraits(image) & UpdatePixelTrait) != 0) &&
2879  (image->alpha_trait != UndefinedPixelTrait))
2880  SetPixelAlpha(image,PosterizePixel(GetPixelAlpha(image,q)),q);
2881  q+=GetPixelChannels(image);
2882  }
2883  if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
2884  status=MagickFalse;
2885  if (image->progress_monitor != (MagickProgressMonitor) NULL)
2886  {
2888  proceed;
2889 
2890 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2891  #pragma omp atomic
2892 #endif
2893  progress++;
2894  proceed=SetImageProgress(image,PosterizeImageTag,progress,image->rows);
2895  if (proceed == MagickFalse)
2896  status=MagickFalse;
2897  }
2898  }
2899  image_view=DestroyCacheView(image_view);
2900  quantize_info=AcquireQuantizeInfo((ImageInfo *) NULL);
2901  quantize_info->number_colors=(size_t) MagickMin((ssize_t) levels*levels*
2902  levels,MaxColormapSize+1);
2903  quantize_info->dither_method=dither_method;
2904  quantize_info->tree_depth=MaxTreeDepth;
2905  status=QuantizeImage(quantize_info,image,exception);
2906  quantize_info=DestroyQuantizeInfo(quantize_info);
2907  return(status);
2908 }
2909 
2910 /*
2911 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2912 % %
2913 % %
2914 % %
2915 + P r u n e C h i l d %
2916 % %
2917 % %
2918 % %
2919 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2920 %
2921 % PruneChild() deletes the given node and merges its statistics into its
2922 % parent.
2923 %
2924 % The format of the PruneSubtree method is:
2925 %
2926 % PruneChild(CubeInfo *cube_info,const NodeInfo *node_info)
2927 %
2928 % A description of each parameter follows.
2929 %
2930 % o cube_info: A pointer to the Cube structure.
2931 %
2932 % o node_info: pointer to node in color cube tree that is to be pruned.
2933 %
2934 */
2935 static void PruneChild(CubeInfo *cube_info,const NodeInfo *node_info)
2936 {
2937  NodeInfo
2938  *parent;
2939 
2940  size_t
2941  number_children;
2942 
2943  ssize_t
2944  i;
2945 
2946  /*
2947  Traverse any children.
2948  */
2949  number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2950  for (i=0; i < (ssize_t) number_children; i++)
2951  if (node_info->child[i] != (NodeInfo *) NULL)
2952  PruneChild(cube_info,node_info->child[i]);
2953  if (cube_info->nodes > cube_info->maximum_colors)
2954  {
2955  /*
2956  Merge color statistics into parent.
2957  */
2958  parent=node_info->parent;
2959  parent->number_unique+=node_info->number_unique;
2960  parent->total_color.red+=node_info->total_color.red;
2961  parent->total_color.green+=node_info->total_color.green;
2962  parent->total_color.blue+=node_info->total_color.blue;
2963  parent->total_color.alpha+=node_info->total_color.alpha;
2964  parent->child[node_info->id]=(NodeInfo *) NULL;
2965  cube_info->nodes--;
2966  }
2967 }
2968 
2969 /*
2970 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2971 % %
2972 % %
2973 % %
2974 + P r u n e L e v e l %
2975 % %
2976 % %
2977 % %
2978 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2979 %
2980 % PruneLevel() deletes all nodes at the bottom level of the color tree merging
2981 % their color statistics into their parent node.
2982 %
2983 % The format of the PruneLevel method is:
2984 %
2985 % PruneLevel(CubeInfo *cube_info,const NodeInfo *node_info)
2986 %
2987 % A description of each parameter follows.
2988 %
2989 % o cube_info: A pointer to the Cube structure.
2990 %
2991 % o node_info: pointer to node in color cube tree that is to be pruned.
2992 %
2993 */
2994 static void PruneLevel(CubeInfo *cube_info,const NodeInfo *node_info)
2995 {
2996  size_t
2997  number_children;
2998 
2999  ssize_t
3000  i;
3001 
3002  /*
3003  Traverse any children.
3004  */
3005  number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
3006  for (i=0; i < (ssize_t) number_children; i++)
3007  if (node_info->child[i] != (NodeInfo *) NULL)
3008  PruneLevel(cube_info,node_info->child[i]);
3009  if (node_info->level == cube_info->depth)
3010  PruneChild(cube_info,node_info);
3011 }
3012 
3013 /*
3014 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3015 % %
3016 % %
3017 % %
3018 + P r u n e T o C u b e D e p t h %
3019 % %
3020 % %
3021 % %
3022 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3023 %
3024 % PruneToCubeDepth() deletes any nodes at a depth greater than
3025 % cube_info->depth while merging their color statistics into their parent
3026 % node.
3027 %
3028 % The format of the PruneToCubeDepth method is:
3029 %
3030 % PruneToCubeDepth(CubeInfo *cube_info,const NodeInfo *node_info)
3031 %
3032 % A description of each parameter follows.
3033 %
3034 % o cube_info: A pointer to the Cube structure.
3035 %
3036 % o node_info: pointer to node in color cube tree that is to be pruned.
3037 %
3038 */
3039 static void PruneToCubeDepth(CubeInfo *cube_info,const NodeInfo *node_info)
3040 {
3041  size_t
3042  number_children;
3043 
3044  ssize_t
3045  i;
3046 
3047  /*
3048  Traverse any children.
3049  */
3050  number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
3051  for (i=0; i < (ssize_t) number_children; i++)
3052  if (node_info->child[i] != (NodeInfo *) NULL)
3053  PruneToCubeDepth(cube_info,node_info->child[i]);
3054  if (node_info->level > cube_info->depth)
3055  PruneChild(cube_info,node_info);
3056 }
3057 
3058 /*
3059 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3060 % %
3061 % %
3062 % %
3063 % Q u a n t i z e I m a g e %
3064 % %
3065 % %
3066 % %
3067 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3068 %
3069 % QuantizeImage() analyzes the colors within a reference image and chooses a
3070 % fixed number of colors to represent the image. The goal of the algorithm
3071 % is to minimize the color difference between the input and output image while
3072 % minimizing the processing time.
3073 %
3074 % The format of the QuantizeImage method is:
3075 %
3076 % MagickBooleanType QuantizeImage(const QuantizeInfo *quantize_info,
3077 % Image *image,ExceptionInfo *exception)
3078 %
3079 % A description of each parameter follows:
3080 %
3081 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
3082 %
3083 % o image: the image.
3084 %
3085 % o exception: return any errors or warnings in this structure.
3086 %
3087 */
3089  Image *image,ExceptionInfo *exception)
3090 {
3091  CubeInfo
3092  *cube_info;
3093 
3094  ImageType
3095  type;
3096 
3098  status;
3099 
3100  size_t
3101  depth,
3102  maximum_colors;
3103 
3104  assert(quantize_info != (const QuantizeInfo *) NULL);
3105  assert(quantize_info->signature == MagickCoreSignature);
3106  assert(image != (Image *) NULL);
3107  assert(image->signature == MagickCoreSignature);
3108  if (image->debug != MagickFalse)
3109  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
3110  assert(exception != (ExceptionInfo *) NULL);
3111  assert(exception->signature == MagickCoreSignature);
3112  maximum_colors=quantize_info->number_colors;
3113  if (maximum_colors == 0)
3114  maximum_colors=MaxColormapSize;
3115  if (maximum_colors > MaxColormapSize)
3116  maximum_colors=MaxColormapSize;
3117  type=IdentifyImageType(image,exception);
3118  if (IsGrayImageType(type) != MagickFalse)
3119  (void) SetGrayscaleImage(image,exception);
3120  depth=quantize_info->tree_depth;
3121  if (depth == 0)
3122  {
3123  size_t
3124  colors;
3125 
3126  /*
3127  Depth of color tree is: Log4(colormap size)+2.
3128  */
3129  colors=maximum_colors;
3130  for (depth=1; colors != 0; depth++)
3131  colors>>=2;
3132  if ((quantize_info->dither_method != NoDitherMethod) && (depth > 2))
3133  depth--;
3134  if ((image->alpha_trait != UndefinedPixelTrait) && (depth > 5))
3135  depth--;
3136  if (IsGrayImageType(type) != MagickFalse)
3137  depth=MaxTreeDepth;
3138  }
3139  /*
3140  Initialize color cube.
3141  */
3142  cube_info=GetCubeInfo(quantize_info,depth,maximum_colors);
3143  if (cube_info == (CubeInfo *) NULL)
3144  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3145  image->filename);
3146  status=ClassifyImageColors(cube_info,image,exception);
3147  if (status != MagickFalse)
3148  {
3149  /*
3150  Reduce the number of colors in the image.
3151  */
3152  if (cube_info->colors > cube_info->maximum_colors)
3153  ReduceImageColors(image,cube_info);
3154  status=AssignImageColors(image,cube_info,exception);
3155  }
3156  DestroyCubeInfo(cube_info);
3157  return(status);
3158 }
3159 
3160 /*
3161 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3162 % %
3163 % %
3164 % %
3165 % Q u a n t i z e I m a g e s %
3166 % %
3167 % %
3168 % %
3169 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3170 %
3171 % QuantizeImages() analyzes the colors within a set of reference images and
3172 % chooses a fixed number of colors to represent the set. The goal of the
3173 % algorithm is to minimize the color difference between the input and output
3174 % images while minimizing the processing time.
3175 %
3176 % The format of the QuantizeImages method is:
3177 %
3178 % MagickBooleanType QuantizeImages(const QuantizeInfo *quantize_info,
3179 % Image *images,ExceptionInfo *exception)
3180 %
3181 % A description of each parameter follows:
3182 %
3183 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
3184 %
3185 % o images: Specifies a pointer to a list of Image structures.
3186 %
3187 % o exception: return any errors or warnings in this structure.
3188 %
3189 */
3191  Image *images,ExceptionInfo *exception)
3192 {
3193  CubeInfo
3194  *cube_info;
3195 
3196  Image
3197  *image;
3198 
3200  proceed,
3201  status;
3202 
3204  progress_monitor;
3205 
3206  size_t
3207  depth,
3208  maximum_colors,
3209  number_images;
3210 
3211  ssize_t
3212  i;
3213 
3214  assert(quantize_info != (const QuantizeInfo *) NULL);
3215  assert(quantize_info->signature == MagickCoreSignature);
3216  assert(images != (Image *) NULL);
3217  assert(images->signature == MagickCoreSignature);
3218  if (images->debug != MagickFalse)
3219  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",images->filename);
3220  assert(exception != (ExceptionInfo *) NULL);
3221  assert(exception->signature == MagickCoreSignature);
3222  if (GetNextImageInList(images) == (Image *) NULL)
3223  {
3224  /*
3225  Handle a single image with QuantizeImage.
3226  */
3227  status=QuantizeImage(quantize_info,images,exception);
3228  return(status);
3229  }
3230  status=MagickFalse;
3231  maximum_colors=quantize_info->number_colors;
3232  if (maximum_colors == 0)
3233  maximum_colors=MaxColormapSize;
3234  if (maximum_colors > MaxColormapSize)
3235  maximum_colors=MaxColormapSize;
3236  depth=quantize_info->tree_depth;
3237  if (depth == 0)
3238  {
3239  size_t
3240  colors;
3241 
3242  /*
3243  Depth of color tree is: Log4(colormap size)+2.
3244  */
3245  colors=maximum_colors;
3246  for (depth=1; colors != 0; depth++)
3247  colors>>=2;
3248  if (quantize_info->dither_method != NoDitherMethod)
3249  depth--;
3250  }
3251  /*
3252  Initialize color cube.
3253  */
3254  cube_info=GetCubeInfo(quantize_info,depth,maximum_colors);
3255  if (cube_info == (CubeInfo *) NULL)
3256  {
3257  (void) ThrowMagickException(exception,GetMagickModule(),
3258  ResourceLimitError,"MemoryAllocationFailed","`%s'",images->filename);
3259  return(MagickFalse);
3260  }
3261  number_images=GetImageListLength(images);
3262  image=images;
3263  for (i=0; image != (Image *) NULL; i++)
3264  {
3265  progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor) NULL,
3266  image->client_data);
3267  status=ClassifyImageColors(cube_info,image,exception);
3268  if (status == MagickFalse)
3269  break;
3270  (void) SetImageProgressMonitor(image,progress_monitor,image->client_data);
3272  number_images);
3273  if (proceed == MagickFalse)
3274  break;
3275  image=GetNextImageInList(image);
3276  }
3277  if (status != MagickFalse)
3278  {
3279  /*
3280  Reduce the number of colors in an image sequence.
3281  */
3282  ReduceImageColors(images,cube_info);
3283  image=images;
3284  for (i=0; image != (Image *) NULL; i++)
3285  {
3286  progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor)
3287  NULL,image->client_data);
3288  status=AssignImageColors(image,cube_info,exception);
3289  if (status == MagickFalse)
3290  break;
3291  (void) SetImageProgressMonitor(image,progress_monitor,
3292  image->client_data);
3294  number_images);
3295  if (proceed == MagickFalse)
3296  break;
3297  image=GetNextImageInList(image);
3298  }
3299  }
3300  DestroyCubeInfo(cube_info);
3301  return(status);
3302 }
3303 
3304 /*
3305 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3306 % %
3307 % %
3308 % %
3309 + Q u a n t i z e E r r o r F l a t t e n %
3310 % %
3311 % %
3312 % %
3313 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3314 %
3315 % QuantizeErrorFlatten() traverses the color cube and flattens the quantization
3316 % error into a sorted 1D array. This accelerates the color reduction process.
3317 %
3318 % Contributed by Yoya.
3319 %
3320 % The format of the QuantizeErrorFlatten method is:
3321 %
3322 % size_t QuantizeErrorFlatten(const CubeInfo *cube_info,
3323 % const NodeInfo *node_info,const ssize_t offset,
3324 % double *quantize_error)
3325 %
3326 % A description of each parameter follows.
3327 %
3328 % o cube_info: A pointer to the Cube structure.
3329 %
3330 % o node_info: pointer to node in color cube tree that is current pointer.
3331 %
3332 % o offset: quantize error offset.
3333 %
3334 % o quantize_error: the quantization error vector.
3335 %
3336 */
3337 static size_t QuantizeErrorFlatten(const CubeInfo *cube_info,
3338  const NodeInfo *node_info,const ssize_t offset,double *quantize_error)
3339 {
3340  size_t
3341  n,
3342  number_children;
3343 
3344  ssize_t
3345  i;
3346 
3347  if (offset >= (ssize_t) cube_info->nodes)
3348  return(0);
3349  quantize_error[offset]=node_info->quantize_error;
3350  n=1;
3351  number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
3352  for (i=0; i < (ssize_t) number_children ; i++)
3353  if (node_info->child[i] != (NodeInfo *) NULL)
3354  n+=QuantizeErrorFlatten(cube_info,node_info->child[i],offset+n,
3355  quantize_error);
3356  return(n);
3357 }
3358 
3359 /*
3360 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3361 % %
3362 % %
3363 % %
3364 + R e d u c e %
3365 % %
3366 % %
3367 % %
3368 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3369 %
3370 % Reduce() traverses the color cube tree and prunes any node whose
3371 % quantization error falls below a particular threshold.
3372 %
3373 % The format of the Reduce method is:
3374 %
3375 % Reduce(CubeInfo *cube_info,const NodeInfo *node_info)
3376 %
3377 % A description of each parameter follows.
3378 %
3379 % o cube_info: A pointer to the Cube structure.
3380 %
3381 % o node_info: pointer to node in color cube tree that is to be pruned.
3382 %
3383 */
3384 static void Reduce(CubeInfo *cube_info,const NodeInfo *node_info)
3385 {
3386  size_t
3387  number_children;
3388 
3389  ssize_t
3390  i;
3391 
3392  /*
3393  Traverse any children.
3394  */
3395  number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
3396  for (i=0; i < (ssize_t) number_children; i++)
3397  if (node_info->child[i] != (NodeInfo *) NULL)
3398  Reduce(cube_info,node_info->child[i]);
3399  if (node_info->quantize_error <= cube_info->pruning_threshold)
3400  PruneChild(cube_info,node_info);
3401  else
3402  {
3403  /*
3404  Find minimum pruning threshold.
3405  */
3406  if (node_info->number_unique > 0)
3407  cube_info->colors++;
3408  if (node_info->quantize_error < cube_info->next_threshold)
3409  cube_info->next_threshold=node_info->quantize_error;
3410  }
3411 }
3412 
3413 /*
3414 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3415 % %
3416 % %
3417 % %
3418 + R e d u c e I m a g e C o l o r s %
3419 % %
3420 % %
3421 % %
3422 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3423 %
3424 % ReduceImageColors() repeatedly prunes the tree until the number of nodes
3425 % with n2 > 0 is less than or equal to the maximum number of colors allowed
3426 % in the output image. On any given iteration over the tree, it selects
3427 % those nodes whose E value is minimal for pruning and merges their
3428 % color statistics upward. It uses a pruning threshold, Ep, to govern
3429 % node selection as follows:
3430 %
3431 % Ep = 0
3432 % while number of nodes with (n2 > 0) > required maximum number of colors
3433 % prune all nodes such that E <= Ep
3434 % Set Ep to minimum E in remaining nodes
3435 %
3436 % This has the effect of minimizing any quantization error when merging
3437 % two nodes together.
3438 %
3439 % When a node to be pruned has offspring, the pruning procedure invokes
3440 % itself recursively in order to prune the tree from the leaves upward.
3441 % n2, Sr, Sg, and Sb in a node being pruned are always added to the
3442 % corresponding data in that node's parent. This retains the pruned
3443 % node's color characteristics for later averaging.
3444 %
3445 % For each node, n2 pixels exist for which that node represents the
3446 % smallest volume in RGB space containing those pixel's colors. When n2
3447 % > 0 the node will uniquely define a color in the output image. At the
3448 % beginning of reduction, n2 = 0 for all nodes except a the leaves of
3449 % the tree which represent colors present in the input image.
3450 %
3451 % The other pixel count, n1, indicates the total number of colors
3452 % within the cubic volume which the node represents. This includes n1 -
3453 % n2 pixels whose colors should be defined by nodes at a lower level in
3454 % the tree.
3455 %
3456 % The format of the ReduceImageColors method is:
3457 %
3458 % ReduceImageColors(const Image *image,CubeInfo *cube_info)
3459 %
3460 % A description of each parameter follows.
3461 %
3462 % o image: the image.
3463 %
3464 % o cube_info: A pointer to the Cube structure.
3465 %
3466 */
3467 
3468 static int QuantizeErrorCompare(const void *error_p,const void *error_q)
3469 {
3470  double
3471  *p,
3472  *q;
3473 
3474  p=(double *) error_p;
3475  q=(double *) error_q;
3476  if (*p > *q)
3477  return(1);
3478  if (fabs(*q-*p) <= MagickEpsilon)
3479  return(0);
3480  return(-1);
3481 }
3482 
3483 static void ReduceImageColors(const Image *image,CubeInfo *cube_info)
3484 {
3485 #define ReduceImageTag "Reduce/Image"
3486 
3488  proceed;
3489 
3491  offset;
3492 
3493  size_t
3494  span;
3495 
3496  cube_info->next_threshold=0.0;
3497  if (cube_info->colors > cube_info->maximum_colors)
3498  {
3499  double
3500  *quantize_error;
3501 
3502  /*
3503  Enable rapid reduction of the number of unique colors.
3504  */
3505  quantize_error=(double *) AcquireQuantumMemory(cube_info->nodes,
3506  sizeof(*quantize_error));
3507  if (quantize_error != (double *) NULL)
3508  {
3509  (void) QuantizeErrorFlatten(cube_info,cube_info->root,0,
3510  quantize_error);
3511  qsort(quantize_error,cube_info->nodes,sizeof(double),
3513  if (cube_info->nodes > (110*(cube_info->maximum_colors+1)/100))
3514  cube_info->next_threshold=quantize_error[cube_info->nodes-110*
3515  (cube_info->maximum_colors+1)/100];
3516  quantize_error=(double *) RelinquishMagickMemory(quantize_error);
3517  }
3518  }
3519  for (span=cube_info->colors; cube_info->colors > cube_info->maximum_colors; )
3520  {
3521  cube_info->pruning_threshold=cube_info->next_threshold;
3522  cube_info->next_threshold=cube_info->root->quantize_error-1;
3523  cube_info->colors=0;
3524  Reduce(cube_info,cube_info->root);
3525  offset=(MagickOffsetType) span-cube_info->colors;
3526  proceed=SetImageProgress(image,ReduceImageTag,offset,span-
3527  cube_info->maximum_colors+1);
3528  if (proceed == MagickFalse)
3529  break;
3530  }
3531 }
3532 
3533 /*
3534 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3535 % %
3536 % %
3537 % %
3538 % R e m a p I m a g e %
3539 % %
3540 % %
3541 % %
3542 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3543 %
3544 % RemapImage() replaces the colors of an image with the closest of the colors
3545 % from the reference image.
3546 %
3547 % The format of the RemapImage method is:
3548 %
3549 % MagickBooleanType RemapImage(const QuantizeInfo *quantize_info,
3550 % Image *image,const Image *remap_image,ExceptionInfo *exception)
3551 %
3552 % A description of each parameter follows:
3553 %
3554 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
3555 %
3556 % o image: the image.
3557 %
3558 % o remap_image: the reference image.
3559 %
3560 % o exception: return any errors or warnings in this structure.
3561 %
3562 */
3564  Image *image,const Image *remap_image,ExceptionInfo *exception)
3565 {
3566  CubeInfo
3567  *cube_info;
3568 
3570  status;
3571 
3572  /*
3573  Initialize color cube.
3574  */
3575  assert(image != (Image *) NULL);
3576  assert(image->signature == MagickCoreSignature);
3577  if (image->debug != MagickFalse)
3578  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
3579  assert(remap_image != (Image *) NULL);
3580  assert(remap_image->signature == MagickCoreSignature);
3581  assert(exception != (ExceptionInfo *) NULL);
3582  assert(exception->signature == MagickCoreSignature);
3583  cube_info=GetCubeInfo(quantize_info,MaxTreeDepth,
3584  quantize_info->number_colors);
3585  if (cube_info == (CubeInfo *) NULL)
3586  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3587  image->filename);
3588  status=ClassifyImageColors(cube_info,remap_image,exception);
3589  if (status != MagickFalse)
3590  {
3591  /*
3592  Classify image colors from the reference image.
3593  */
3594  cube_info->quantize_info->number_colors=cube_info->colors;
3595  status=AssignImageColors(image,cube_info,exception);
3596  }
3597  DestroyCubeInfo(cube_info);
3598  return(status);
3599 }
3600 
3601 /*
3602 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3603 % %
3604 % %
3605 % %
3606 % R e m a p I m a g e s %
3607 % %
3608 % %
3609 % %
3610 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3611 %
3612 % RemapImages() replaces the colors of a sequence of images with the
3613 % closest color from a reference image.
3614 %
3615 % The format of the RemapImage method is:
3616 %
3617 % MagickBooleanType RemapImages(const QuantizeInfo *quantize_info,
3618 % Image *images,Image *remap_image,ExceptionInfo *exception)
3619 %
3620 % A description of each parameter follows:
3621 %
3622 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
3623 %
3624 % o images: the image sequence.
3625 %
3626 % o remap_image: the reference image.
3627 %
3628 % o exception: return any errors or warnings in this structure.
3629 %
3630 */
3632  Image *images,const Image *remap_image,ExceptionInfo *exception)
3633 {
3634  CubeInfo
3635  *cube_info;
3636 
3637  Image
3638  *image;
3639 
3641  status;
3642 
3643  assert(images != (Image *) NULL);
3644  assert(images->signature == MagickCoreSignature);
3645  if (images->debug != MagickFalse)
3646  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",images->filename);
3647  assert(exception != (ExceptionInfo *) NULL);
3648  assert(exception->signature == MagickCoreSignature);
3649  image=images;
3650  if (remap_image == (Image *) NULL)
3651  {
3652  /*
3653  Create a global colormap for an image sequence.
3654  */
3655  status=QuantizeImages(quantize_info,images,exception);
3656  return(status);
3657  }
3658  /*
3659  Classify image colors from the reference image.
3660  */
3661  cube_info=GetCubeInfo(quantize_info,MaxTreeDepth,
3662  quantize_info->number_colors);
3663  if (cube_info == (CubeInfo *) NULL)
3664  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3665  image->filename);
3666  status=ClassifyImageColors(cube_info,remap_image,exception);
3667  if (status != MagickFalse)
3668  {
3669  /*
3670  Classify image colors from the reference image.
3671  */
3672  cube_info->quantize_info->number_colors=cube_info->colors;
3673  image=images;
3674  for ( ; image != (Image *) NULL; image=GetNextImageInList(image))
3675  {
3676  status=AssignImageColors(image,cube_info,exception);
3677  if (status == MagickFalse)
3678  break;
3679  }
3680  }
3681  DestroyCubeInfo(cube_info);
3682  return(status);
3683 }
3684 
3685 /*
3686 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3687 % %
3688 % %
3689 % %
3690 % S e t G r a y s c a l e I m a g e %
3691 % %
3692 % %
3693 % %
3694 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3695 %
3696 % SetGrayscaleImage() converts an image to a PseudoClass grayscale image.
3697 %
3698 % The format of the SetGrayscaleImage method is:
3699 %
3700 % MagickBooleanType SetGrayscaleImage(Image *image,
3701 % ExceptionInfo *exception)
3702 %
3703 % A description of each parameter follows:
3704 %
3705 % o image: The image.
3706 %
3707 % o exception: return any errors or warnings in this structure.
3708 %
3709 */
3710 
3711 #if defined(__cplusplus) || defined(c_plusplus)
3712 extern "C" {
3713 #endif
3714 
3715 static int IntensityCompare(const void *x,const void *y)
3716 {
3717  double
3718  intensity;
3719 
3720  PixelInfo
3721  *color_1,
3722  *color_2;
3723 
3724  color_1=(PixelInfo *) x;
3725  color_2=(PixelInfo *) y;
3726  intensity=GetPixelInfoIntensity((const Image *) NULL,color_1)-
3727  GetPixelInfoIntensity((const Image *) NULL,color_2);
3728  if (intensity < (double) INT_MIN)
3729  intensity=(double) INT_MIN;
3730  if (intensity > (double) INT_MAX)
3731  intensity=(double) INT_MAX;
3732  return((int) intensity);
3733 }
3734 
3735 #if defined(__cplusplus) || defined(c_plusplus)
3736 }
3737 #endif
3738 
3740  ExceptionInfo *exception)
3741 {
3742  CacheView
3743  *image_view;
3744 
3746  status;
3747 
3748  PixelInfo
3749  *colormap;
3750 
3751  size_t
3752  extent;
3753 
3754  ssize_t
3755  *colormap_index,
3756  i,
3757  j,
3758  y;
3759 
3760  assert(image != (Image *) NULL);
3761  assert(image->signature == MagickCoreSignature);
3762  if (image->type != GrayscaleType)
3763  (void) TransformImageColorspace(image,GRAYColorspace,exception);
3764  extent=MagickMax(image->colors+1,MagickMax(MaxColormapSize,MaxMap+1));
3765  colormap_index=(ssize_t *) AcquireQuantumMemory(extent,
3766  sizeof(*colormap_index));
3767  if (colormap_index == (ssize_t *) NULL)
3768  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3769  image->filename);
3770  if (image->storage_class != PseudoClass)
3771  {
3772  (void) memset(colormap_index,(-1),extent*sizeof(*colormap_index));
3773  if (AcquireImageColormap(image,MaxColormapSize,exception) == MagickFalse)
3774  {
3775  colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
3776  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3777  image->filename);
3778  }
3779  image->colors=0;
3780  status=MagickTrue;
3781  image_view=AcquireAuthenticCacheView(image,exception);
3782 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3783  #pragma omp parallel for schedule(static) shared(status) \
3784  magick_number_threads(image,image,image->rows,1)
3785 #endif
3786  for (y=0; y < (ssize_t) image->rows; y++)
3787  {
3788  Quantum
3789  *magick_restrict q;
3790 
3791  ssize_t
3792  x;
3793 
3794  if (status == MagickFalse)
3795  continue;
3796  q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,
3797  exception);
3798  if (q == (Quantum *) NULL)
3799  {
3800  status=MagickFalse;
3801  continue;
3802  }
3803  for (x=0; x < (ssize_t) image->columns; x++)
3804  {
3805  size_t
3806  intensity;
3807 
3808  intensity=ScaleQuantumToMap(GetPixelRed(image,q));
3809  if (colormap_index[intensity] < 0)
3810  {
3811 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3812  #pragma omp critical (MagickCore_SetGrayscaleImage)
3813 #endif
3814  if (colormap_index[intensity] < 0)
3815  {
3816  colormap_index[intensity]=(ssize_t) image->colors;
3817  image->colormap[image->colors].red=(double)
3818  GetPixelRed(image,q);
3819  image->colormap[image->colors].green=(double)
3820  GetPixelGreen(image,q);
3821  image->colormap[image->colors].blue=(double)
3822  GetPixelBlue(image,q);
3823  image->colors++;
3824  }
3825  }
3826  SetPixelIndex(image,(Quantum) colormap_index[intensity],q);
3827  q+=GetPixelChannels(image);
3828  }
3829  if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
3830  status=MagickFalse;
3831  }
3832  image_view=DestroyCacheView(image_view);
3833  }
3834  (void) memset(colormap_index,0,extent*sizeof(*colormap_index));
3835  for (i=0; i < (ssize_t) image->colors; i++)
3836  image->colormap[i].alpha=(double) i;
3837  qsort((void *) image->colormap,image->colors,sizeof(PixelInfo),
3839  colormap=(PixelInfo *) AcquireQuantumMemory(image->colors,sizeof(*colormap));
3840  if (colormap == (PixelInfo *) NULL)
3841  {
3842  colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
3843  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3844  image->filename);
3845  }
3846  j=0;
3847  colormap[j]=image->colormap[0];
3848  for (i=0; i < (ssize_t) image->colors; i++)
3849  {
3850  if (IsPixelInfoEquivalent(&colormap[j],&image->colormap[i]) == MagickFalse)
3851  {
3852  j++;
3853  colormap[j]=image->colormap[i];
3854  }
3855  colormap_index[(ssize_t) image->colormap[i].alpha]=j;
3856  }
3857  image->colors=(size_t) (j+1);
3859  image->colormap=colormap;
3860  status=MagickTrue;
3861  image_view=AcquireAuthenticCacheView(image,exception);
3862 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3863  #pragma omp parallel for schedule(static) shared(status) \
3864  magick_number_threads(image,image,image->rows,1)
3865 #endif
3866  for (y=0; y < (ssize_t) image->rows; y++)
3867  {
3868  Quantum
3869  *magick_restrict q;
3870 
3871  ssize_t
3872  x;
3873 
3874  if (status == MagickFalse)
3875  continue;
3876  q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
3877  if (q == (Quantum *) NULL)
3878  {
3879  status=MagickFalse;
3880  continue;
3881  }
3882  for (x=0; x < (ssize_t) image->columns; x++)
3883  {
3884  SetPixelIndex(image,(Quantum) colormap_index[ScaleQuantumToMap(
3885  GetPixelIndex(image,q))],q);
3886  q+=GetPixelChannels(image);
3887  }
3888  if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
3889  status=MagickFalse;
3890  }
3891  image_view=DestroyCacheView(image_view);
3892  colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
3893  image->type=GrayscaleType;
3894  if (SetImageMonochrome(image,exception) != MagickFalse)
3895  image->type=BilevelType;
3896  return(status);
3897 }
3898 
3899 /*
3900 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3901 % %
3902 % %
3903 % %
3904 + S e t I m a g e C o l o r m a p %
3905 % %
3906 % %
3907 % %
3908 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3909 %
3910 % SetImageColormap() traverses the color cube tree and sets the colormap of
3911 % the image. A colormap entry is any node in the color cube tree where the
3912 % of unique colors is not zero.
3913 %
3914 % The format of the SetImageColormap method is:
3915 %
3916 % MagickBooleanType SetImageColormap(Image *image,CubeInfo *cube_info,
3917 % ExceptionInfo *node_info)
3918 %
3919 % A description of each parameter follows.
3920 %
3921 % o image: the image.
3922 %
3923 % o cube_info: A pointer to the Cube structure.
3924 %
3925 % o exception: return any errors or warnings in this structure.
3926 %
3927 */
3928 
3930  ExceptionInfo *exception)
3931 {
3932  size_t
3933  number_colors;
3934 
3935  number_colors=MagickMax(cube_info->maximum_colors,cube_info->colors);
3936  if (AcquireImageColormap(image,number_colors,exception) == MagickFalse)
3937  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3938  image->filename);
3939  image->colors=0;
3940  DefineImageColormap(image,cube_info,cube_info->root);
3941  if (image->colors != number_colors)
3942  {
3943  image->colormap=(PixelInfo *) ResizeQuantumMemory(image->colormap,
3944  image->colors+1,sizeof(*image->colormap));
3945  if (image->colormap == (PixelInfo *) NULL)
3946  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3947  image->filename);
3948  }
3949  return(MagickTrue);
3950 }
size_t rows
Definition: image.h:172
#define magick_restrict
Definition: MagickCore.h:41
MagickExport MagickBooleanType CompressImageColormap(Image *image, ExceptionInfo *exception)
Definition: quantize.c:1190
MagickBooleanType associate_alpha
Definition: quantize.c:316
MagickDoubleType MagickRealType
Definition: magick-type.h:124
MagickExport CacheView * DestroyCacheView(CacheView *cache_view)
Definition: cache-view.c:252
#define ErrorQueueLength
Definition: quantize.c:217
size_t colors
Definition: histogram.c:112
double black
Definition: quantize.c:2360
PixelInfo * colormap
Definition: image.h:179
MagickExport MemoryInfo * RelinquishVirtualMemory(MemoryInfo *memory_info)
Definition: memory.c:1229
NodeInfo * next_node
Definition: quantize.c:294
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:289
MagickExport MagickBooleanType SyncImage(Image *image, ExceptionInfo *exception)
Definition: image.c:3897
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:1609
double quantize_error
Definition: quantize.c:248
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:2787
static Quantum GetPixelRed(const Image *magick_restrict image, const Quantum *magick_restrict pixel)
ColorspaceType colorspace
Definition: quantize.h:44
#define RandomColorComponent(info)
MagickExport ssize_t ParseCommandOption(const CommandOption option, const MagickBooleanType list, const char *options)
Definition: option.c:3055
static size_t QuantizeErrorFlatten(const CubeInfo *cube_info, const NodeInfo *node_info, const ssize_t offset, double *quantize_error)
Definition: quantize.c:3337
#define ErrorRelativeWeight
Definition: quantize.c:218
#define CacheShift
Definition: quantize.c:213
MagickExport MemoryInfo * AcquireVirtualMemory(const size_t count, const size_t quantum)
Definition: memory.c:705
double alpha
Definition: quantize.c:2360
size_t signature
Definition: exception.h:123
size_t nodes
Definition: quantize.c:289
size_t tree_depth
Definition: quantize.h:41
static void DestroyCubeInfo(CubeInfo *)
Definition: quantize.c:1340
static MagickBooleanType DitherImage(Image *, CubeInfo *, ExceptionInfo *)
Definition: quantize.c:1961
#define OpaqueAlpha
Definition: image.h:25
MagickExport QuantizeInfo * DestroyQuantizeInfo(QuantizeInfo *quantize_info)
Definition: quantize.c:1386
MagickOffsetType offset
Definition: quantize.c:326
DitherMethod
Definition: quantize.h:27
MagickExport const char * GetImageArtifact(const Image *image, const char *artifact)
Definition: artifact.c:273
MagickRealType red
Definition: pixel.h:193
QuantizeInfo * quantize_info
Definition: quantize.c:313
#define MaxColormapSize
Definition: magick-type.h:78
#define RedShift(pixel)
double mean_error_per_pixel
Definition: color.h:79
static KmeansInfo ** AcquireKmeansThreadSet(const size_t number_colors)
Definition: quantize.c:2382
struct _CubeInfo CubeInfo
static MagickBooleanType IsGrayColorspace(const ColorspaceType colorspace)
double distance
Definition: quantize.c:284
MagickExport size_t CopyMagickString(char *magick_restrict destination, const char *magick_restrict source, const size_t length)
Definition: string.c:731
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:3384
MagickBooleanType verbose
Definition: image.h:445
MagickRealType alpha
Definition: pixel.h:193
MagickExport const char * GetImageOption(const ImageInfo *image_info, const char *option)
Definition: option.c:2383
#define PosterizeImageTag
double blue
Definition: quantize.c:2360
double red
Definition: quantize.c:2360
#define MagickEpsilon
Definition: magick-type.h:114
MagickExport void * ResizeQuantumMemory(void *memory, const size_t count, const size_t quantum)
Definition: memory.c:1457
size_t free_nodes
Definition: histogram.c:112
ClassType storage_class
Definition: image.h:154
static MagickBooleanType IsGrayImageType(const ImageType type)
static NodeInfo * GetNodeInfo(CubeInfo *, const size_t, const size_t, NodeInfo *)
Definition: quantize.c:2129
#define ThrowBinaryException(severity, tag, context)
Definition: log.h:52
ssize_t MagickOffsetType
Definition: magick-type.h:133
static Quantum ClampToQuantum(const MagickRealType quantum)
Definition: quantum.h:85
static MagickBooleanType IsPixelInfoEquivalent(const PixelInfo *magick_restrict p, const PixelInfo *magick_restrict q)
Definition: image.h:151
MagickExport RandomInfo * DestroyRandomInfo(RandomInfo *random_info)
Definition: random.c:274
struct _Nodes * next
Definition: histogram.c:96
size_t id
Definition: quantize.c:251
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:79
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 MagickBooleanType IsHueCompatibleColorspace(const ColorspaceType colorspace)
MagickExport MagickBooleanType RemapImages(const QuantizeInfo *quantize_info, Image *images, const Image *remap_image, ExceptionInfo *exception)
Definition: quantize.c:3631
static MagickBooleanType FloydSteinbergDither(Image *image, CubeInfo *cube_info, ExceptionInfo *exception)
Definition: quantize.c:1486
MagickExport ssize_t FormatLocaleFile(FILE *file, const char *magick_restrict format,...)
Definition: locale.c:368
MagickBooleanType
Definition: magick-type.h:165
static double PerceptibleReciprocal(const double x)
double weights[ErrorQueueLength]
Definition: quantize.c:309
DoublePixelPacket total_color
Definition: quantize.c:245
struct _KmeansInfo KmeansInfo
size_t signature
Definition: quantize.h:53
MagickSizeType span
Definition: quantize.c:329
static void PruneChild(CubeInfo *cube_info, const NodeInfo *node_info)
Definition: quantize.c:2935
MagickExport void * AcquireCriticalMemory(const size_t size)
Definition: memory.c:626
static MagickBooleanType RiemersmaDither(Image *image, CacheView *image_view, CubeInfo *cube_info, const unsigned int direction, ExceptionInfo *exception)
Definition: quantize.c:1671
static MagickBooleanType IssRGBCompatibleColorspace(const ColorspaceType colorspace)
MagickExport void * AcquireQuantumMemory(const size_t count, const size_t quantum)
Definition: memory.c:665
DoublePixelPacket target
Definition: quantize.c:281
MagickExport MagickBooleanType QuantizeImages(const QuantizeInfo *quantize_info, Image *images, ExceptionInfo *exception)
Definition: quantize.c:3190
static int GetOpenMPThreadId(void)
static CubeInfo * GetCubeInfo(const QuantizeInfo *, const size_t, const size_t)
Definition: quantize.c:2038
#define DitherImageTag
size_t number_colors
Definition: quantize.h:38
#define MaxNodes
Definition: quantize.c:219
size_t MagickSizeType
Definition: magick-type.h:134
#define MagickPathExtent
ssize_t y
Definition: quantize.c:319
static Quantum GetPixelGreen(const Image *magick_restrict image, const Quantum *magick_restrict pixel)
MagickExport MagickBooleanType IsStringTrue(const char *value)
Definition: string.c:1386
static void GetPixelInfoPixel(const Image *magick_restrict image, const Quantum *magick_restrict pixel, PixelInfo *magick_restrict pixel_info)
size_t maximum_colors
Definition: quantize.c:271
PixelTrait alpha_trait
Definition: image.h:280
MagickExport int GetMagickPrecision(void)
Definition: magick.c:942
MagickExport void GetQuantizeInfo(QuantizeInfo *quantize_info)
Definition: quantize.c:2311
MagickRealType blue
Definition: pixel.h:193
static Quantum GetPixelIndex(const Image *magick_restrict image, const Quantum *magick_restrict pixel)
MagickSizeType transparent_pixels
Definition: quantize.c:278
static double MagickRound(double x)
Definition: quantize.c:2777
static Quantum GetPixelBlack(const Image *magick_restrict image, const Quantum *magick_restrict pixel)
#define MaxTreeDepth
Definition: quantize.c:220
struct _NodeInfo * child[16]
Definition: histogram.c:75
MagickExport MagickRealType GetPixelInfoIntensity(const Image *magick_restrict image, const PixelInfo *magick_restrict pixel)
Definition: pixel.c:2224
double distortion
Definition: quantize.c:2360
MagickExport MagickBooleanType RemapImage(const QuantizeInfo *quantize_info, Image *image, const Image *remap_image, ExceptionInfo *exception)
Definition: quantize.c:3563
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:1145
static void AssociateAlphaPixelInfo(const CubeInfo *cube_info, const PixelInfo *pixel, DoublePixelPacket *alpha_pixel)
Definition: quantize.c:463
MagickExport MagickBooleanType LogMagickEvent(const LogEventType type, const char *module, const char *function, const size_t line, const char *format,...)
Definition: log.c:1660
MagickExport MagickBooleanType QuantizeImage(const QuantizeInfo *quantize_info, Image *image, ExceptionInfo *exception)
Definition: quantize.c:3088
#define BlueShift(pixel)
MagickExport MagickBooleanType GetImageQuantizeError(Image *image, ExceptionInfo *exception)
Definition: quantize.c:2207
ssize_t transparent_index
Definition: quantize.c:275
static void PruneLevel(CubeInfo *, const NodeInfo *)
Definition: quantize.c:2994
size_t signature
Definition: image.h:354
MagickExport RandomInfo * AcquireRandomInfo(void)
Definition: random.c:163
MagickExport MagickSizeType GetMagickResourceLimit(const ResourceType type)
Definition: resource.c:793
size_t columns
Definition: image.h:172
#define QuantumScale
Definition: magick-type.h:119
static DoublePixelPacket ** DestroyPixelThreadSet(DoublePixelPacket **pixels)
Definition: quantize.c:1427
MagickBooleanType(* MagickProgressMonitor)(const char *, const MagickOffsetType, const MagickSizeType, void *)
Definition: monitor.h:26
static DoublePixelPacket ** AcquirePixelThreadSet(const size_t count)
Definition: quantize.c:1440
struct _NodeInfo * parent
Definition: quantize.c:237
MagickExport ImageType IdentifyImageType(const Image *image, ExceptionInfo *exception)
Definition: attribute.c:1724
static PixelTrait GetPixelGreenTraits(const Image *magick_restrict image)
MagickExport MagickBooleanType QueryColorCompliance(const char *name, const ComplianceType compliance, PixelInfo *color, ExceptionInfo *exception)
Definition: color.c:2265
static void SetPixelBlue(const Image *magick_restrict image, const Quantum blue, Quantum *magick_restrict pixel)
#define NodesInAList
Definition: quantize.c:221
MagickExport MagickProgressMonitor SetImageProgressMonitor(Image *image, const MagickProgressMonitor progress_monitor, void *client_data)
Definition: monitor.c:194
#define KmeansImageTag
static MagickBooleanType Riemersma(Image *image, CacheView *image_view, CubeInfo *cube_info, const size_t level, const unsigned int direction, ExceptionInfo *exception)
Definition: quantize.c:1794
#define MaxMap
Definition: magick-type.h:79
MagickSizeType number_unique
Definition: histogram.c:85
#define MagickMax(x, y)
Definition: image-private.h:36
size_t colors
Definition: image.h:172
double diffusion
Definition: quantize.c:309
static size_t GetPixelChannels(const Image *magick_restrict image)
MagickExport MagickBooleanType AcquireImageColormap(Image *image, const size_t colors, ExceptionInfo *exception)
Definition: colormap.c:105
#define IsNaN(a)
Definition: magick-type.h:188
MagickExport MagickBooleanType IsPaletteImage(const Image *image)
Definition: histogram.c:867
MagickExport QuantizeInfo * AcquireQuantizeInfo(const ImageInfo *image_info)
Definition: quantize.c:378
static MagickBooleanType AssignImageColors(Image *, CubeInfo *, ExceptionInfo *)
Definition: quantize.c:499
#define ReduceImageTag
char filename[MagickPathExtent]
Definition: image.h:319
double next_threshold
Definition: quantize.c:284
#define GetMagickModule()
Definition: log.h:28
size_t color_number
Definition: quantize.c:251
NodeInfo nodes[NodesInAList]
Definition: histogram.c:94
struct _Nodes Nodes
MagickExport size_t GetNumberColors(const Image *image, FILE *file, ExceptionInfo *exception)
Definition: histogram.c:1029
MagickExport CacheView * AcquireVirtualCacheView(const Image *image, ExceptionInfo *exception)
Definition: cache-view.c:149
static double StringToDoubleInterval(const char *string, const double interval)
static int IntensityCompare(const void *x, const void *y)
Definition: quantize.c:3715
DitherMethod dither_method
Definition: quantize.h:47
size_t depth
Definition: quantize.c:323
double normalized_maximum_error
Definition: color.h:79
#define ClassifyImageTag
ErrorInfo error
Definition: image.h:297
struct _NodeInfo NodeInfo
unsigned short Quantum
Definition: magick-type.h:86
DoublePixelPacket error[ErrorQueueLength]
Definition: quantize.c:306
static size_t ColorToNodeId(const CubeInfo *cube_info, const DoublePixelPacket *pixel, size_t index)
Definition: quantize.c:485
#define AssignImageTag
double green
Definition: quantize.c:2360
MagickExport Image * GetNextImageInList(const Image *images)
Definition: list.c:786
MagickRealType black
Definition: pixel.h:193
Nodes * node_queue
Definition: histogram.c:119
MagickExport void * AcquireMagickMemory(const size_t size)
Definition: memory.c:552
NodeInfo * root
Definition: histogram.c:103
MagickExport QuantizeInfo * CloneQuantizeInfo(const QuantizeInfo *quantize_info)
Definition: quantize.c:1048
static void SetPixelIndex(const Image *magick_restrict image, const Quantum index, Quantum *magick_restrict pixel)
MagickBooleanType dither
Definition: image.h:432
static MagickBooleanType SetGrayscaleImage(Image *, ExceptionInfo *)
Definition: quantize.c:3739
static MagickBooleanType ClassifyImageColors(CubeInfo *, const Image *, ExceptionInfo *)
Definition: quantize.c:752
ssize_t * cache
Definition: quantize.c:303
MagickBooleanType measure_error
Definition: quantize.h:50
static int QuantizeErrorCompare(const void *error_p, const void *error_q)
Definition: quantize.c:3468
#define MagickMin(x, y)
Definition: image-private.h:37
static void SetPixelAlpha(const Image *magick_restrict image, const Quantum alpha, Quantum *magick_restrict pixel)
NodeInfo * nodes
Definition: quantize.c:259
ColorspaceType
Definition: colorspace.h:25
double pruning_threshold
Definition: quantize.c:284
double count
Definition: quantize.c:2360
static void DefineImageColormap(Image *, CubeInfo *, NodeInfo *)
Definition: quantize.c:1238
static RandomInfo * random_info
Definition: resource.c:113
MagickExport void * RelinquishMagickMemory(void *memory)
Definition: memory.c:1162
size_t total_colors
Definition: image.h:248
MagickRealType green
Definition: pixel.h:193
MagickExport MagickBooleanType KmeansImage(Image *image, const size_t number_colors, const size_t max_iterations, const double tolerance, ExceptionInfo *exception)
Definition: quantize.c:2453
static void AssociateAlphaPixel(const Image *image, const CubeInfo *cube_info, const Quantum *pixel, DoublePixelPacket *alpha_pixel)
Definition: quantize.c:441
ImageType
Definition: image.h:48
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:1467
static void ReduceImageColors(const Image *, CubeInfo *)
Definition: quantize.c:3483
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:300
MagickExport MagickBooleanType SetImageMonochrome(Image *image, ExceptionInfo *exception)
Definition: colorspace.c:1557
ssize_t x
Definition: histogram.c:106
static void PruneToCubeDepth(CubeInfo *, const NodeInfo *)
Definition: quantize.c:3039
static void SetPixelBlack(const Image *magick_restrict image, const Quantum black, Quantum *magick_restrict pixel)
static KmeansInfo ** DestroyKmeansThreadSet(KmeansInfo **kmeans_info)
Definition: quantize.c:2369
static Quantum GetPixelBlue(const Image *magick_restrict image, const Quantum *magick_restrict pixel)
static MagickBooleanType SetImageColormap(Image *, CubeInfo *, ExceptionInfo *)
Definition: quantize.c:3929
MagickExport void * GetVirtualMemoryBlob(const MemoryInfo *memory_info)
Definition: memory.c:1090
size_t level
Definition: histogram.c:88
#define PosterizePixel(pixel)
MagickExport size_t GetImageListLength(const Image *images)
Definition: list.c:711
struct _DoublePixelPacket DoublePixelPacket
static void SetAssociatedAlpha(const Image *image, CubeInfo *cube_info)
Definition: quantize.c:738
static double KmeansMetric(const Image *magick_restrict image, const Quantum *magick_restrict p, const PixelInfo *magick_restrict q)
Definition: quantize.c:2409
void * client_data
Definition: image.h:306
ColorspaceType colorspace
Definition: image.h:157
#define QuantumRange
Definition: magick-type.h:87
MagickExport MagickBooleanType SetImageProgress(const Image *image, const char *tag, const MagickOffsetType offset, const MagickSizeType extent)
Definition: monitor.c:136
static void ClosestColor(const Image *, CubeInfo *, const NodeInfo *)
Definition: quantize.c:1094
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)