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