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