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