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