MagickCore  7.1.0
Convert, Edit, Or Compose Bitmap Images
quantize.c
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 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"
181 #include "MagickCore/color-private.h"
182 #include "MagickCore/colormap.h"
183 #include "MagickCore/colorspace.h"
184 #include "MagickCore/colorspace-private.h"
185 #include "MagickCore/compare.h"
186 #include "MagickCore/enhance.h"
187 #include "MagickCore/exception.h"
188 #include "MagickCore/exception-private.h"
189 #include "MagickCore/histogram.h"
190 #include "MagickCore/image.h"
191 #include "MagickCore/image-private.h"
192 #include "MagickCore/list.h"
193 #include "MagickCore/memory_.h"
194 #include "MagickCore/memory-private.h"
195 #include "MagickCore/monitor.h"
196 #include "MagickCore/monitor-private.h"
197 #include "MagickCore/option.h"
198 #include "MagickCore/pixel-accessor.h"
199 #include "MagickCore/property.h"
200 #include "MagickCore/quantize.h"
201 #include "MagickCore/quantum.h"
202 #include "MagickCore/quantum-private.h"
203 #include "MagickCore/random_.h"
204 #include "MagickCore/resource_.h"
205 #include "MagickCore/string_.h"
206 #include "MagickCore/string-private.h"
207 #include "MagickCore/thread-private.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
229  red,
230  green,
231  blue,
232  alpha;
234 
235 typedef struct _NodeInfo
236 {
237  struct _NodeInfo
238  *parent,
239  *child[16];
240 
241  MagickSizeType
242  number_unique;
243 
245  total_color;
246 
247  double
248  quantize_error;
249 
250  size_t
251  color_number,
252  id,
253  level;
254 } NodeInfo;
255 
256 typedef struct _Nodes
257 {
258  NodeInfo
259  *nodes;
260 
261  struct _Nodes
262  *next;
263 } Nodes;
264 
265 typedef struct _CubeInfo
266 {
267  NodeInfo
268  *root;
269 
270  size_t
271  colors,
272  maximum_colors;
273 
274  ssize_t
275  transparent_index;
276 
277  MagickSizeType
278  transparent_pixels;
279 
281  target;
282 
283  double
284  distance,
285  pruning_threshold,
286  next_threshold;
287 
288  size_t
289  nodes,
290  free_nodes,
291  color_number;
292 
293  NodeInfo
294  *next_node;
295 
296  Nodes
297  *node_queue;
298 
299  MemoryInfo
300  *memory_info;
301 
302  ssize_t
303  *cache;
304 
306  error[ErrorQueueLength];
307 
308  double
309  diffusion,
310  weights[ErrorQueueLength];
311 
313  *quantize_info;
314 
315  MagickBooleanType
316  associate_alpha;
317 
318  ssize_t
319  x,
320  y;
321 
322  size_t
323  depth;
324 
325  MagickOffsetType
326  offset;
327 
328  MagickSizeType
329  span;
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
342  AssignImageColors(Image *,CubeInfo *,ExceptionInfo *),
343  ClassifyImageColors(CubeInfo *,const Image *,ExceptionInfo *),
344  DitherImage(Image *,CubeInfo *,ExceptionInfo *),
345  SetGrayscaleImage(Image *,ExceptionInfo *),
346  SetImageColormap(Image *,CubeInfo *,ExceptionInfo *);
347 
348 static void
349  ClosestColor(const Image *,CubeInfo *,const NodeInfo *),
350  DefineImageColormap(Image *,CubeInfo *,NodeInfo *),
351  DestroyCubeInfo(CubeInfo *),
352  PruneLevel(CubeInfo *,const NodeInfo *),
353  PruneToCubeDepth(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 */
378 MagickExport QuantizeInfo *AcquireQuantizeInfo(const ImageInfo *image_info)
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 ?
391  NoDitherMethod : RiemersmaDitherMethod;
392  option=GetImageOption(image_info,"dither");
393  if (option != (const char *) NULL)
394  quantize_info->dither_method=(DitherMethod) ParseCommandOption(
395  MagickDitherOptions,MagickFalse,option);
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 
499 static MagickBooleanType AssignImageColors(Image *image,CubeInfo *cube_info,
500  ExceptionInfo *exception)
501 {
502 #define AssignImageTag "Assign/Image"
503 
504  ColorspaceType
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 
531  MagickBooleanType
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);
610  if (cube.quantize_info->measure_error == MagickFalse)
611  {
612  SetPixelRed(image,ClampToQuantum(
613  image->colormap[index].red),q);
614  SetPixelGreen(image,ClampToQuantum(
615  image->colormap[index].green),q);
616  SetPixelBlue(image,ClampToQuantum(
617  image->colormap[index].blue),q);
618  if (cube.associate_alpha != MagickFalse)
619  SetPixelAlpha(image,ClampToQuantum(
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  {
629  MagickBooleanType
630  proceed;
631 
632  proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) y,
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  (IsGrayColorspace(cube_info->quantize_info->colorspace)))
644  {
645  double
646  intensity;
647 
648  /*
649  Monochrome image.
650  */
651  intensity=GetPixelInfoLuma(image->colormap+0) < QuantumRange/2.0 ? 0.0 :
652  QuantumRange;
653  if (image->colors > 1)
654  {
655  intensity=0.0;
656  if (GetPixelInfoLuma(image->colormap+0) >
657  GetPixelInfoLuma(image->colormap+1))
658  intensity=(double) QuantumRange;
659  }
660  image->colormap[0].red=intensity;
661  image->colormap[0].green=intensity;
662  image->colormap[0].blue=intensity;
663  if (image->colors > 1)
664  {
665  image->colormap[1].red=(double) QuantumRange-intensity;
666  image->colormap[1].green=(double) QuantumRange-intensity;
667  image->colormap[1].blue=(double) QuantumRange-intensity;
668  }
669  }
670  (void) SyncImage(image,exception);
671  if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
672  (IssRGBCompatibleColorspace(colorspace) == MagickFalse))
673  (void) TransformImageColorspace(image,colorspace,exception);
674  return(MagickTrue);
675 }
676 ␌
677 /*
678 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
679 % %
680 % %
681 % %
682 + C l a s s i f y I m a g e C o l o r s %
683 % %
684 % %
685 % %
686 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
687 %
688 % ClassifyImageColors() begins by initializing a color description tree
689 % of sufficient depth to represent each possible input color in a leaf.
690 % However, it is impractical to generate a fully-formed color
691 % description tree in the storage_class phase for realistic values of
692 % Cmax. If colors components in the input image are quantized to k-bit
693 % precision, so that Cmax= 2k-1, the tree would need k levels below the
694 % root node to allow representing each possible input color in a leaf.
695 % This becomes prohibitive because the tree's total number of nodes is
696 % 1 + sum(i=1,k,8k).
697 %
698 % A complete tree would require 19,173,961 nodes for k = 8, Cmax = 255.
699 % Therefore, to avoid building a fully populated tree, QUANTIZE: (1)
700 % Initializes data structures for nodes only as they are needed; (2)
701 % Chooses a maximum depth for the tree as a function of the desired
702 % number of colors in the output image (currently log2(colormap size)).
703 %
704 % For each pixel in the input image, storage_class scans downward from
705 % the root of the color description tree. At each level of the tree it
706 % identifies the single node which represents a cube in RGB space
707 % containing It updates the following data for each such node:
708 %
709 % n1 : Number of pixels whose color is contained in the RGB cube
710 % which this node represents;
711 %
712 % n2 : Number of pixels whose color is not represented in a node at
713 % lower depth in the tree; initially, n2 = 0 for all nodes except
714 % leaves of the tree.
715 %
716 % Sr, Sg, Sb : Sums of the red, green, and blue component values for
717 % all pixels not classified at a lower depth. The combination of
718 % these sums and n2 will ultimately characterize the mean color of a
719 % set of pixels represented by this node.
720 %
721 % E: the distance squared in RGB space between each pixel contained
722 % within a node and the nodes' center. This represents the quantization
723 % error for a node.
724 %
725 % The format of the ClassifyImageColors() method is:
726 %
727 % MagickBooleanType ClassifyImageColors(CubeInfo *cube_info,
728 % const Image *image,ExceptionInfo *exception)
729 %
730 % A description of each parameter follows.
731 %
732 % o cube_info: A pointer to the Cube structure.
733 %
734 % o image: the image.
735 %
736 */
737 
738 static inline void SetAssociatedAlpha(const Image *image,CubeInfo *cube_info)
739 {
740  MagickBooleanType
741  associate_alpha;
742 
743  associate_alpha=image->alpha_trait != UndefinedPixelTrait ? MagickTrue :
744  MagickFalse;
745  if ((cube_info->quantize_info->number_colors == 2) &&
746  ((cube_info->quantize_info->colorspace == LinearGRAYColorspace) ||
747  (cube_info->quantize_info->colorspace == GRAYColorspace)))
748  associate_alpha=MagickFalse;
749  cube_info->associate_alpha=associate_alpha;
750 }
751 
752 static MagickBooleanType ClassifyImageColors(CubeInfo *cube_info,
753  const Image *image,ExceptionInfo *exception)
754 {
755 #define ClassifyImageTag "Classify/Image"
756 
757  CacheView
758  *image_view;
759 
760  double
761  bisect;
762 
764  error,
765  mid,
766  midpoint,
767  pixel;
768 
769  MagickBooleanType
770  proceed;
771 
772  NodeInfo
773  *node_info;
774 
775  size_t
776  count,
777  id,
778  index,
779  level;
780 
781  ssize_t
782  y;
783 
784  /*
785  Classify the first cube_info->maximum_colors colors to a tree depth of 8.
786  */
787  SetAssociatedAlpha(image,cube_info);
788  if (cube_info->quantize_info->colorspace != image->colorspace)
789  {
790  if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
791  (cube_info->quantize_info->colorspace != CMYKColorspace))
792  (void) TransformImageColorspace((Image *) image,
793  cube_info->quantize_info->colorspace,exception);
794  else
795  if (IssRGBCompatibleColorspace(image->colorspace) == MagickFalse)
796  (void) TransformImageColorspace((Image *) image,sRGBColorspace,
797  exception);
798  }
799  midpoint.red=(double) QuantumRange/2.0;
800  midpoint.green=(double) QuantumRange/2.0;
801  midpoint.blue=(double) QuantumRange/2.0;
802  midpoint.alpha=(double) QuantumRange/2.0;
803  error.alpha=0.0;
804  image_view=AcquireVirtualCacheView(image,exception);
805  for (y=0; y < (ssize_t) image->rows; y++)
806  {
807  const Quantum
808  *magick_restrict p;
809 
810  ssize_t
811  x;
812 
813  p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
814  if (p == (const Quantum *) NULL)
815  break;
816  if (cube_info->nodes > MaxNodes)
817  {
818  /*
819  Prune one level if the color tree is too large.
820  */
821  PruneLevel(cube_info,cube_info->root);
822  cube_info->depth--;
823  }
824  for (x=0; x < (ssize_t) image->columns; x+=(ssize_t) count)
825  {
826  /*
827  Start at the root and descend the color cube tree.
828  */
829  for (count=1; (x+(ssize_t) count) < (ssize_t) image->columns; count++)
830  {
831  PixelInfo
832  packet;
833 
834  GetPixelInfoPixel(image,p+count*GetPixelChannels(image),&packet);
835  if (IsPixelEquivalent(image,p,&packet) == MagickFalse)
836  break;
837  }
838  AssociateAlphaPixel(image,cube_info,p,&pixel);
839  index=MaxTreeDepth-1;
840  bisect=((double) QuantumRange+1.0)/2.0;
841  mid=midpoint;
842  node_info=cube_info->root;
843  for (level=1; level <= MaxTreeDepth; level++)
844  {
845  double
846  distance;
847 
848  bisect*=0.5;
849  id=ColorToNodeId(cube_info,&pixel,index);
850  mid.red+=(id & 1) != 0 ? bisect : -bisect;
851  mid.green+=(id & 2) != 0 ? bisect : -bisect;
852  mid.blue+=(id & 4) != 0 ? bisect : -bisect;
853  mid.alpha+=(id & 8) != 0 ? bisect : -bisect;
854  if (node_info->child[id] == (NodeInfo *) NULL)
855  {
856  /*
857  Set colors of new node to contain pixel.
858  */
859  node_info->child[id]=GetNodeInfo(cube_info,id,level,node_info);
860  if (node_info->child[id] == (NodeInfo *) NULL)
861  {
862  (void) ThrowMagickException(exception,GetMagickModule(),
863  ResourceLimitError,"MemoryAllocationFailed","`%s'",
864  image->filename);
865  continue;
866  }
867  if (level == MaxTreeDepth)
868  cube_info->colors++;
869  }
870  /*
871  Approximate the quantization error represented by this node.
872  */
873  node_info=node_info->child[id];
874  error.red=QuantumScale*(pixel.red-mid.red);
875  error.green=QuantumScale*(pixel.green-mid.green);
876  error.blue=QuantumScale*(pixel.blue-mid.blue);
877  if (cube_info->associate_alpha != MagickFalse)
878  error.alpha=QuantumScale*(pixel.alpha-mid.alpha);
879  distance=(double) (error.red*error.red+error.green*error.green+
880  error.blue*error.blue+error.alpha*error.alpha);
881  if (IsNaN(distance) != 0)
882  distance=0.0;
883  node_info->quantize_error+=count*sqrt(distance);
884  cube_info->root->quantize_error+=node_info->quantize_error;
885  index--;
886  }
887  /*
888  Sum RGB for this leaf for later derivation of the mean cube color.
889  */
890  node_info->number_unique+=count;
891  node_info->total_color.red+=count*QuantumScale*ClampPixel(pixel.red);
892  node_info->total_color.green+=count*QuantumScale*ClampPixel(pixel.green);
893  node_info->total_color.blue+=count*QuantumScale*ClampPixel(pixel.blue);
894  if (cube_info->associate_alpha != MagickFalse)
895  node_info->total_color.alpha+=count*QuantumScale*
896  ClampPixel(pixel.alpha);
897  else
898  node_info->total_color.alpha+=count*QuantumScale*
899  ClampPixel((MagickRealType) OpaqueAlpha);
900  p+=count*GetPixelChannels(image);
901  }
902  if (cube_info->colors > cube_info->maximum_colors)
903  {
904  PruneToCubeDepth(cube_info,cube_info->root);
905  break;
906  }
907  proceed=SetImageProgress(image,ClassifyImageTag,(MagickOffsetType) y,
908  image->rows);
909  if (proceed == MagickFalse)
910  break;
911  }
912  for (y++; y < (ssize_t) image->rows; y++)
913  {
914  const Quantum
915  *magick_restrict p;
916 
917  ssize_t
918  x;
919 
920  p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
921  if (p == (const Quantum *) NULL)
922  break;
923  if (cube_info->nodes > MaxNodes)
924  {
925  /*
926  Prune one level if the color tree is too large.
927  */
928  PruneLevel(cube_info,cube_info->root);
929  cube_info->depth--;
930  }
931  for (x=0; x < (ssize_t) image->columns; x+=(ssize_t) count)
932  {
933  /*
934  Start at the root and descend the color cube tree.
935  */
936  for (count=1; (x+(ssize_t) count) < (ssize_t) image->columns; count++)
937  {
938  PixelInfo
939  packet;
940 
941  GetPixelInfoPixel(image,p+count*GetPixelChannels(image),&packet);
942  if (IsPixelEquivalent(image,p,&packet) == MagickFalse)
943  break;
944  }
945  AssociateAlphaPixel(image,cube_info,p,&pixel);
946  index=MaxTreeDepth-1;
947  bisect=((double) QuantumRange+1.0)/2.0;
948  mid=midpoint;
949  node_info=cube_info->root;
950  for (level=1; level <= cube_info->depth; level++)
951  {
952  double
953  distance;
954 
955  bisect*=0.5;
956  id=ColorToNodeId(cube_info,&pixel,index);
957  mid.red+=(id & 1) != 0 ? bisect : -bisect;
958  mid.green+=(id & 2) != 0 ? bisect : -bisect;
959  mid.blue+=(id & 4) != 0 ? bisect : -bisect;
960  mid.alpha+=(id & 8) != 0 ? bisect : -bisect;
961  if (node_info->child[id] == (NodeInfo *) NULL)
962  {
963  /*
964  Set colors of new node to contain pixel.
965  */
966  node_info->child[id]=GetNodeInfo(cube_info,id,level,node_info);
967  if (node_info->child[id] == (NodeInfo *) NULL)
968  {
969  (void) ThrowMagickException(exception,GetMagickModule(),
970  ResourceLimitError,"MemoryAllocationFailed","%s",
971  image->filename);
972  continue;
973  }
974  if (level == cube_info->depth)
975  cube_info->colors++;
976  }
977  /*
978  Approximate the quantization error represented by this node.
979  */
980  node_info=node_info->child[id];
981  error.red=QuantumScale*(pixel.red-mid.red);
982  error.green=QuantumScale*(pixel.green-mid.green);
983  error.blue=QuantumScale*(pixel.blue-mid.blue);
984  if (cube_info->associate_alpha != MagickFalse)
985  error.alpha=QuantumScale*(pixel.alpha-mid.alpha);
986  distance=(double) (error.red*error.red+error.green*error.green+
987  error.blue*error.blue+error.alpha*error.alpha);
988  if (IsNaN(distance) != 0)
989  distance=0.0;
990  node_info->quantize_error+=count*sqrt(distance);
991  cube_info->root->quantize_error+=node_info->quantize_error;
992  index--;
993  }
994  /*
995  Sum RGB for this leaf for later derivation of the mean cube color.
996  */
997  node_info->number_unique+=count;
998  node_info->total_color.red+=count*QuantumScale*ClampPixel(pixel.red);
999  node_info->total_color.green+=count*QuantumScale*ClampPixel(pixel.green);
1000  node_info->total_color.blue+=count*QuantumScale*ClampPixel(pixel.blue);
1001  if (cube_info->associate_alpha != MagickFalse)
1002  node_info->total_color.alpha+=count*QuantumScale*
1003  ClampPixel(pixel.alpha);
1004  else
1005  node_info->total_color.alpha+=count*QuantumScale*
1006  ClampPixel((MagickRealType) OpaqueAlpha);
1007  p+=count*GetPixelChannels(image);
1008  }
1009  proceed=SetImageProgress(image,ClassifyImageTag,(MagickOffsetType) y,
1010  image->rows);
1011  if (proceed == MagickFalse)
1012  break;
1013  }
1014  image_view=DestroyCacheView(image_view);
1015  if (cube_info->quantize_info->colorspace != image->colorspace)
1016  if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
1017  (cube_info->quantize_info->colorspace != CMYKColorspace))
1018  (void) TransformImageColorspace((Image *) image,sRGBColorspace,exception);
1019  return(y < (ssize_t) image->rows ? MagickFalse : MagickTrue);
1020 }
1021 ␌
1022 /*
1023 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1024 % %
1025 % %
1026 % %
1027 % C l o n e Q u a n t i z e I n f o %
1028 % %
1029 % %
1030 % %
1031 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1032 %
1033 % CloneQuantizeInfo() makes a duplicate of the given quantize info structure,
1034 % or if quantize info is NULL, a new one.
1035 %
1036 % The format of the CloneQuantizeInfo method is:
1037 %
1038 % QuantizeInfo *CloneQuantizeInfo(const QuantizeInfo *quantize_info)
1039 %
1040 % A description of each parameter follows:
1041 %
1042 % o clone_info: Method CloneQuantizeInfo returns a duplicate of the given
1043 % quantize info, or if image info is NULL a new one.
1044 %
1045 % o quantize_info: a structure of type info.
1046 %
1047 */
1048 MagickExport QuantizeInfo *CloneQuantizeInfo(const QuantizeInfo *quantize_info)
1049 {
1050  QuantizeInfo
1051  *clone_info;
1052 
1053  clone_info=(QuantizeInfo *) AcquireCriticalMemory(sizeof(*clone_info));
1054  GetQuantizeInfo(clone_info);
1055  if (quantize_info == (QuantizeInfo *) NULL)
1056  return(clone_info);
1057  clone_info->number_colors=quantize_info->number_colors;
1058  clone_info->tree_depth=quantize_info->tree_depth;
1059  clone_info->dither_method=quantize_info->dither_method;
1060  clone_info->colorspace=quantize_info->colorspace;
1061  clone_info->measure_error=quantize_info->measure_error;
1062  return(clone_info);
1063 }
1064 ␌
1065 /*
1066 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1067 % %
1068 % %
1069 % %
1070 + C l o s e s t C o l o r %
1071 % %
1072 % %
1073 % %
1074 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1075 %
1076 % ClosestColor() traverses the color cube tree at a particular node and
1077 % determines which colormap entry best represents the input color.
1078 %
1079 % The format of the ClosestColor method is:
1080 %
1081 % void ClosestColor(const Image *image,CubeInfo *cube_info,
1082 % const NodeInfo *node_info)
1083 %
1084 % A description of each parameter follows.
1085 %
1086 % o image: the image.
1087 %
1088 % o cube_info: A pointer to the Cube structure.
1089 %
1090 % o node_info: the address of a structure of type NodeInfo which points to a
1091 % node in the color cube tree that is to be pruned.
1092 %
1093 */
1094 static void ClosestColor(const Image *image,CubeInfo *cube_info,
1095  const NodeInfo *node_info)
1096 {
1097  size_t
1098  number_children;
1099 
1100  ssize_t
1101  i;
1102 
1103  /*
1104  Traverse any children.
1105  */
1106  number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
1107  for (i=0; i < (ssize_t) number_children; i++)
1108  if (node_info->child[i] != (NodeInfo *) NULL)
1109  ClosestColor(image,cube_info,node_info->child[i]);
1110  if (node_info->number_unique != 0)
1111  {
1112  double
1113  alpha,
1114  beta,
1115  distance,
1116  pixel;
1117 
1119  *magick_restrict q;
1120 
1121  PixelInfo
1122  *magick_restrict p;
1123 
1124  /*
1125  Determine if this color is "closest".
1126  */
1127  p=image->colormap+node_info->color_number;
1128  q=(&cube_info->target);
1129  alpha=1.0;
1130  beta=1.0;
1131  if (cube_info->associate_alpha != MagickFalse)
1132  {
1133  alpha=(MagickRealType) (QuantumScale*p->alpha);
1134  beta=(MagickRealType) (QuantumScale*q->alpha);
1135  }
1136  pixel=alpha*p->red-beta*q->red;
1137  distance=pixel*pixel;
1138  if (distance <= cube_info->distance)
1139  {
1140  pixel=alpha*p->green-beta*q->green;
1141  distance+=pixel*pixel;
1142  if (distance <= cube_info->distance)
1143  {
1144  pixel=alpha*p->blue-beta*q->blue;
1145  distance+=pixel*pixel;
1146  if (distance <= cube_info->distance)
1147  {
1148  if (cube_info->associate_alpha != MagickFalse)
1149  {
1150  pixel=p->alpha-q->alpha;
1151  distance+=pixel*pixel;
1152  }
1153  if (distance <= cube_info->distance)
1154  {
1155  cube_info->distance=distance;
1156  cube_info->color_number=node_info->color_number;
1157  }
1158  }
1159  }
1160  }
1161  }
1162 }
1163 ␌
1164 /*
1165 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1166 % %
1167 % %
1168 % %
1169 % C o m p r e s s I m a g e C o l o r m a p %
1170 % %
1171 % %
1172 % %
1173 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1174 %
1175 % CompressImageColormap() compresses an image colormap by removing any
1176 % duplicate or unused color entries.
1177 %
1178 % The format of the CompressImageColormap method is:
1179 %
1180 % MagickBooleanType CompressImageColormap(Image *image,
1181 % ExceptionInfo *exception)
1182 %
1183 % A description of each parameter follows:
1184 %
1185 % o image: the image.
1186 %
1187 % o exception: return any errors or warnings in this structure.
1188 %
1189 */
1190 MagickExport MagickBooleanType CompressImageColormap(Image *image,
1191  ExceptionInfo *exception)
1192 {
1193  QuantizeInfo
1194  quantize_info;
1195 
1196  assert(image != (Image *) NULL);
1197  assert(image->signature == MagickCoreSignature);
1198  if (IsEventLogging() != MagickFalse)
1199  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
1200  if (IsPaletteImage(image) == MagickFalse)
1201  return(MagickFalse);
1202  GetQuantizeInfo(&quantize_info);
1203  quantize_info.number_colors=image->colors;
1204  quantize_info.tree_depth=MaxTreeDepth;
1205  return(QuantizeImage(&quantize_info,image,exception));
1206 }
1207 ␌
1208 /*
1209 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1210 % %
1211 % %
1212 % %
1213 + D e f i n e I m a g e C o l o r m a p %
1214 % %
1215 % %
1216 % %
1217 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1218 %
1219 % DefineImageColormap() traverses the color cube tree and notes each colormap
1220 % entry. A colormap entry is any node in the color cube tree where the
1221 % of unique colors is not zero.
1222 %
1223 % The format of the DefineImageColormap method is:
1224 %
1225 % void DefineImageColormap(Image *image,CubeInfo *cube_info,
1226 % NodeInfo *node_info)
1227 %
1228 % A description of each parameter follows.
1229 %
1230 % o image: the image.
1231 %
1232 % o cube_info: A pointer to the Cube structure.
1233 %
1234 % o node_info: the address of a structure of type NodeInfo which points to a
1235 % node in the color cube tree that is to be pruned.
1236 %
1237 */
1238 static void DefineImageColormap(Image *image,CubeInfo *cube_info,
1239  NodeInfo *node_info)
1240 {
1241  size_t
1242  number_children;
1243 
1244  ssize_t
1245  i;
1246 
1247  /*
1248  Traverse any children.
1249  */
1250  number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
1251  for (i=0; i < (ssize_t) number_children; i++)
1252  if (node_info->child[i] != (NodeInfo *) NULL)
1253  DefineImageColormap(image,cube_info,node_info->child[i]);
1254  if (node_info->number_unique != 0)
1255  {
1256  double
1257  alpha;
1258 
1259  PixelInfo
1260  *magick_restrict q;
1261 
1262  /*
1263  Colormap entry is defined by the mean color in this cube.
1264  */
1265  q=image->colormap+image->colors;
1266  alpha=(double) ((MagickOffsetType) node_info->number_unique);
1267  alpha=PerceptibleReciprocal(alpha);
1268  if (cube_info->associate_alpha == MagickFalse)
1269  {
1270  q->red=(double) ClampToQuantum(alpha*QuantumRange*
1271  node_info->total_color.red);
1272  q->green=(double) ClampToQuantum(alpha*QuantumRange*
1273  node_info->total_color.green);
1274  q->blue=(double) ClampToQuantum(alpha*QuantumRange*
1275  node_info->total_color.blue);
1276  q->alpha=(double) OpaqueAlpha;
1277  }
1278  else
1279  {
1280  double
1281  opacity;
1282 
1283  opacity=(double) (alpha*QuantumRange*node_info->total_color.alpha);
1284  q->alpha=(double) ClampToQuantum(opacity);
1285  if (q->alpha == OpaqueAlpha)
1286  {
1287  q->red=(double) ClampToQuantum(alpha*QuantumRange*
1288  node_info->total_color.red);
1289  q->green=(double) ClampToQuantum(alpha*QuantumRange*
1290  node_info->total_color.green);
1291  q->blue=(double) ClampToQuantum(alpha*QuantumRange*
1292  node_info->total_color.blue);
1293  }
1294  else
1295  {
1296  double
1297  gamma;
1298 
1299  gamma=(double) (QuantumScale*q->alpha);
1300  gamma=PerceptibleReciprocal(gamma);
1301  q->red=(double) ClampToQuantum(alpha*gamma*QuantumRange*
1302  node_info->total_color.red);
1303  q->green=(double) ClampToQuantum(alpha*gamma*QuantumRange*
1304  node_info->total_color.green);
1305  q->blue=(double) ClampToQuantum(alpha*gamma*QuantumRange*
1306  node_info->total_color.blue);
1307  if (node_info->number_unique > cube_info->transparent_pixels)
1308  {
1309  cube_info->transparent_pixels=node_info->number_unique;
1310  cube_info->transparent_index=(ssize_t) image->colors;
1311  }
1312  }
1313  }
1314  node_info->color_number=image->colors++;
1315  }
1316 }
1317 ␌
1318 /*
1319 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1320 % %
1321 % %
1322 % %
1323 + D e s t r o y C u b e I n f o %
1324 % %
1325 % %
1326 % %
1327 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1328 %
1329 % DestroyCubeInfo() deallocates memory associated with an image.
1330 %
1331 % The format of the DestroyCubeInfo method is:
1332 %
1333 % DestroyCubeInfo(CubeInfo *cube_info)
1334 %
1335 % A description of each parameter follows:
1336 %
1337 % o cube_info: the address of a structure of type CubeInfo.
1338 %
1339 */
1340 static void DestroyCubeInfo(CubeInfo *cube_info)
1341 {
1342  Nodes
1343  *nodes;
1344 
1345  /*
1346  Release color cube tree storage.
1347  */
1348  do
1349  {
1350  nodes=cube_info->node_queue->next;
1351  cube_info->node_queue->nodes=(NodeInfo *) RelinquishMagickMemory(
1352  cube_info->node_queue->nodes);
1353  cube_info->node_queue=(Nodes *) RelinquishMagickMemory(
1354  cube_info->node_queue);
1355  cube_info->node_queue=nodes;
1356  } while (cube_info->node_queue != (Nodes *) NULL);
1357  if (cube_info->memory_info != (MemoryInfo *) NULL)
1358  cube_info->memory_info=RelinquishVirtualMemory(cube_info->memory_info);
1359  cube_info->quantize_info=DestroyQuantizeInfo(cube_info->quantize_info);
1360  cube_info=(CubeInfo *) RelinquishMagickMemory(cube_info);
1361 }
1362 ␌
1363 /*
1364 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1365 % %
1366 % %
1367 % %
1368 % D e s t r o y Q u a n t i z e I n f o %
1369 % %
1370 % %
1371 % %
1372 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1373 %
1374 % DestroyQuantizeInfo() deallocates memory associated with an QuantizeInfo
1375 % structure.
1376 %
1377 % The format of the DestroyQuantizeInfo method is:
1378 %
1379 % QuantizeInfo *DestroyQuantizeInfo(QuantizeInfo *quantize_info)
1380 %
1381 % A description of each parameter follows:
1382 %
1383 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
1384 %
1385 */
1386 MagickExport QuantizeInfo *DestroyQuantizeInfo(QuantizeInfo *quantize_info)
1387 {
1388  assert(quantize_info != (QuantizeInfo *) NULL);
1389  assert(quantize_info->signature == MagickCoreSignature);
1390  if (IsEventLogging() != MagickFalse)
1391  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
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 
1428 static DoublePixelPacket **DestroyPixelTLS(DoublePixelPacket **pixels)
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 **AcquirePixelTLS(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(DestroyPixelTLS(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 
1487 static MagickBooleanType FloydSteinbergDither(Image *image,CubeInfo *cube_info,
1488  ExceptionInfo *exception)
1489 {
1490 #define DitherImageTag "Dither/Image"
1491 
1492  CacheView
1493  *image_view;
1494 
1496  **pixels;
1497 
1498  MagickBooleanType
1499  status;
1500 
1501  ssize_t
1502  y;
1503 
1504  /*
1505  Distribute quantization error using Floyd-Steinberg.
1506  */
1507  pixels=AcquirePixelTLS(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));
1632  if (cube.quantize_info->measure_error == MagickFalse)
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  {
1657  MagickBooleanType
1658  proceed;
1659 
1660  proceed=SetImageProgress(image,DitherImageTag,(MagickOffsetType) y,
1661  image->rows);
1662  if (proceed == MagickFalse)
1663  status=MagickFalse;
1664  }
1665  }
1666  }
1667  image_view=DestroyCacheView(image_view);
1668  pixels=DestroyPixelTLS(pixels);
1669  return(MagickTrue);
1670 }
1671 
1672 static MagickBooleanType RiemersmaDither(Image *image,CacheView *image_view,
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 
1684  MagickBooleanType
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 {
1799  MagickBooleanType
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 
1971  MagickBooleanType
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);
1981  if (cube_info->quantize_info->dither_method != RiemersmaDitherMethod)
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 (((size_t) 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);
2147  nodes->nodes=(NodeInfo *) AcquireQuantumMemory(NodesInAList,
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 */
2208 MagickExport MagickBooleanType GetImageQuantizeError(Image *image,
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 (IsEventLogging() != 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;
2284  image->error.normalized_mean_error=(double) QuantumScale*QuantumScale*
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 */
2312 MagickExport void GetQuantizeInfo(QuantizeInfo *quantize_info)
2313 {
2314  assert(quantize_info != (QuantizeInfo *) NULL);
2315  if (IsEventLogging() != MagickFalse)
2316  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
2317  (void) memset(quantize_info,0,sizeof(*quantize_info));
2318  quantize_info->number_colors=256;
2319  quantize_info->dither_method=RiemersmaDitherMethod;
2320  quantize_info->colorspace=UndefinedColorspace;
2321  quantize_info->measure_error=MagickFalse;
2322  quantize_info->signature=MagickCoreSignature;
2323 }
2324 ␌
2325 /*
2326 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2327 % %
2328 % %
2329 % %
2330 % K m e a n s I m a g e %
2331 % %
2332 % %
2333 % %
2334 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2335 %
2336 % KmeansImage() applies k-means color reduction to an image. This is a
2337 % colorspace clustering or segmentation technique.
2338 %
2339 % The format of the KmeansImage method is:
2340 %
2341 % MagickBooleanType KmeansImage(Image *image,const size_t number_colors,
2342 % const size_t max_iterations,const double tolerance,
2343 % ExceptionInfo *exception)
2344 %
2345 % A description of each parameter follows:
2346 %
2347 % o image: the image.
2348 %
2349 % o number_colors: number of colors to use as seeds.
2350 %
2351 % o max_iterations: maximum number of iterations while converging.
2352 %
2353 % o tolerance: the maximum tolerance.
2354 %
2355 % o exception: return any errors or warnings in this structure.
2356 %
2357 */
2358 
2359 typedef struct _KmeansInfo
2360 {
2361  double
2362  red,
2363  green,
2364  blue,
2365  alpha,
2366  black,
2367  count,
2368  distortion;
2369 } KmeansInfo;
2370 
2371 static KmeansInfo **DestroyKmeansTLS(KmeansInfo **kmeans_info)
2372 {
2373  ssize_t
2374  i;
2375 
2376  assert(kmeans_info != (KmeansInfo **) NULL);
2377  for (i=0; i < (ssize_t) GetMagickResourceLimit(ThreadResource); i++)
2378  if (kmeans_info[i] != (KmeansInfo *) NULL)
2379  kmeans_info[i]=(KmeansInfo *) RelinquishMagickMemory(kmeans_info[i]);
2380  kmeans_info=(KmeansInfo **) RelinquishMagickMemory(kmeans_info);
2381  return(kmeans_info);
2382 }
2383 
2384 static int DominantColorCompare(const void *x,const void *y)
2385 {
2386  PixelInfo
2387  *pixel_1,
2388  *pixel_2;
2389 
2390  pixel_1=(PixelInfo *) x;
2391  pixel_2=(PixelInfo *) y;
2392  return((int) pixel_2->count-(int) pixel_1->count);
2393 }
2394 
2395 static KmeansInfo **AcquireKmeansTLS(const size_t number_colors)
2396 {
2397  KmeansInfo
2398  **kmeans_info;
2399 
2400  ssize_t
2401  i;
2402 
2403  size_t
2404  number_threads;
2405 
2406  number_threads=(size_t) GetMagickResourceLimit(ThreadResource);
2407  kmeans_info=(KmeansInfo **) AcquireQuantumMemory(number_threads,
2408  sizeof(*kmeans_info));
2409  if (kmeans_info == (KmeansInfo **) NULL)
2410  return((KmeansInfo **) NULL);
2411  (void) memset(kmeans_info,0,number_threads*sizeof(*kmeans_info));
2412  for (i=0; i < (ssize_t) number_threads; i++)
2413  {
2414  kmeans_info[i]=(KmeansInfo *) AcquireQuantumMemory(number_colors,
2415  sizeof(**kmeans_info));
2416  if (kmeans_info[i] == (KmeansInfo *) NULL)
2417  return(DestroyKmeansTLS(kmeans_info));
2418  }
2419  return(kmeans_info);
2420 }
2421 
2422 static inline double KmeansMetric(const Image *magick_restrict image,
2423  const Quantum *magick_restrict p,const PixelInfo *magick_restrict q)
2424 {
2425  double
2426  gamma,
2427  metric,
2428  pixel;
2429 
2430  gamma=1.0;
2431  metric=0.0;
2432  if ((image->alpha_trait != UndefinedPixelTrait) ||
2433  (q->alpha_trait != UndefinedPixelTrait))
2434  {
2435  pixel=GetPixelAlpha(image,p)-(q->alpha_trait != UndefinedPixelTrait ?
2436  q->alpha : OpaqueAlpha);
2437  metric+=pixel*pixel;
2438  if (image->alpha_trait != UndefinedPixelTrait)
2439  gamma*=QuantumScale*GetPixelAlpha(image,p);
2440  if (q->alpha_trait != UndefinedPixelTrait)
2441  gamma*=QuantumScale*q->alpha;
2442  }
2443  if (image->colorspace == CMYKColorspace)
2444  {
2445  pixel=QuantumScale*(GetPixelBlack(image,p)-q->black);
2446  metric+=gamma*pixel*pixel;
2447  gamma*=QuantumScale*(QuantumRange-GetPixelBlack(image,p));
2448  gamma*=QuantumScale*(QuantumRange-q->black);
2449  }
2450  metric*=3.0;
2451  pixel=QuantumScale*(GetPixelRed(image,p)-q->red);
2452  if (IsHueCompatibleColorspace(image->colorspace) != MagickFalse)
2453  {
2454  if (fabs((double) pixel) > 0.5)
2455  pixel-=0.5;
2456  pixel*=2.0;
2457  }
2458  metric+=gamma*pixel*pixel;
2459  pixel=QuantumScale*(GetPixelGreen(image,p)-q->green);
2460  metric+=gamma*pixel*pixel;
2461  pixel=QuantumScale*(GetPixelBlue(image,p)-q->blue);
2462  metric+=gamma*pixel*pixel;
2463  return(metric);
2464 }
2465 
2466 MagickExport MagickBooleanType KmeansImage(Image *image,
2467  const size_t number_colors,const size_t max_iterations,const double tolerance,
2468  ExceptionInfo *exception)
2469 {
2470 #define KmeansImageTag "Kmeans/Image"
2471 #define RandomColorComponent(info) (QuantumRange*GetPseudoRandomValue(info))
2472 
2473  CacheView
2474  *image_view;
2475 
2476  char
2477  tuple[MagickPathExtent];
2478 
2479  const char
2480  *colors;
2481 
2482  double
2483  previous_tolerance;
2484 
2485  Image
2486  *dominant_image;
2487 
2488  KmeansInfo
2489  **kmeans_pixels;
2490 
2491  MagickBooleanType
2492  verbose,
2493  status;
2494 
2495  size_t
2496  number_threads;
2497 
2498  ssize_t
2499  n;
2500 
2501  assert(image != (Image *) NULL);
2502  assert(image->signature == MagickCoreSignature);
2503  assert(exception != (ExceptionInfo *) NULL);
2504  assert(exception->signature == MagickCoreSignature);
2505  if (IsEventLogging() != MagickFalse)
2506  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
2507  if (max_iterations == 0)
2508  return(MagickFalse);
2509  colors=GetImageArtifact(image,"kmeans:seed-colors");
2510  if (colors == (const char *) NULL)
2511  {
2512  CubeInfo
2513  *cube_info;
2514 
2515  QuantizeInfo
2516  *quantize_info;
2517 
2518  size_t
2519  depth;
2520 
2521  /*
2522  Seed clusters from color quantization.
2523  */
2524  quantize_info=AcquireQuantizeInfo((ImageInfo *) NULL);
2525  quantize_info->colorspace=image->colorspace;
2526  quantize_info->number_colors=number_colors;
2527  quantize_info->dither_method=NoDitherMethod;
2528  n=(ssize_t) number_colors;
2529  for (depth=1; n != 0; depth++)
2530  n>>=2;
2531  cube_info=GetCubeInfo(quantize_info,depth,number_colors);
2532  if (cube_info == (CubeInfo *) NULL)
2533  {
2534  quantize_info=DestroyQuantizeInfo(quantize_info);
2535  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
2536  image->filename);
2537  }
2538  status=ClassifyImageColors(cube_info,image,exception);
2539  if (status != MagickFalse)
2540  {
2541  if (cube_info->colors > cube_info->maximum_colors)
2542  ReduceImageColors(image,cube_info);
2543  status=SetImageColormap(image,cube_info,exception);
2544  }
2545  DestroyCubeInfo(cube_info);
2546  quantize_info=DestroyQuantizeInfo(quantize_info);
2547  if (status == MagickFalse)
2548  return(status);
2549  }
2550  else
2551  {
2552  char
2553  color[MagickPathExtent];
2554 
2555  const char
2556  *p;
2557 
2558  /*
2559  Seed clusters from color list (e.g. red;green;blue).
2560  */
2561  status=AcquireImageColormap(image,number_colors,exception);
2562  if (status == MagickFalse)
2563  return(status);
2564  for (n=0, p=colors; n < (ssize_t) image->colors; n++)
2565  {
2566  const char
2567  *q;
2568 
2569  for (q=p; *q != '\0'; q++)
2570  if (*q == ';')
2571  break;
2572  (void) CopyMagickString(color,p,(size_t) MagickMin(q-p+1,
2573  MagickPathExtent));
2574  (void) QueryColorCompliance(color,AllCompliance,image->colormap+n,
2575  exception);
2576  if (*q == '\0')
2577  {
2578  n++;
2579  break;
2580  }
2581  p=q+1;
2582  }
2583  if (n < (ssize_t) image->colors)
2584  {
2585  RandomInfo
2586  *random_info;
2587 
2588  /*
2589  Seed clusters from random values.
2590  */
2591  random_info=AcquireRandomInfo();
2592  for ( ; n < (ssize_t) image->colors; n++)
2593  {
2594  (void) QueryColorCompliance("#000",AllCompliance,image->colormap+n,
2595  exception);
2596  image->colormap[n].red=RandomColorComponent(random_info);
2597  image->colormap[n].green=RandomColorComponent(random_info);
2598  image->colormap[n].blue=RandomColorComponent(random_info);
2599  if (image->alpha_trait != UndefinedPixelTrait)
2600  image->colormap[n].alpha=RandomColorComponent(random_info);
2601  if (image->colorspace == CMYKColorspace)
2602  image->colormap[n].black=RandomColorComponent(random_info);
2603  }
2604  random_info=DestroyRandomInfo(random_info);
2605  }
2606  }
2607  /*
2608  Iterative refinement.
2609  */
2610  kmeans_pixels=AcquireKmeansTLS(number_colors);
2611  if (kmeans_pixels == (KmeansInfo **) NULL)
2612  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
2613  image->filename);
2614  previous_tolerance=0.0;
2615  verbose=IsStringTrue(GetImageArtifact(image,"verbose"));
2616  number_threads=(size_t) GetMagickResourceLimit(ThreadResource);
2617  image_view=AcquireAuthenticCacheView(image,exception);
2618  for (n=0; n < (ssize_t) max_iterations; n++)
2619  {
2620  double
2621  distortion;
2622 
2623  ssize_t
2624  j,
2625  y;
2626 
2627  for (j=0; j < (ssize_t) number_threads; j++)
2628  (void) memset(kmeans_pixels[j],0,image->colors*sizeof(*kmeans_pixels[j]));
2629 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2630  #pragma omp parallel for schedule(dynamic) shared(status) \
2631  magick_number_threads(image,image,image->rows,1)
2632 #endif
2633  for (y=0; y < (ssize_t) image->rows; y++)
2634  {
2635  const int
2636  id = GetOpenMPThreadId();
2637 
2638  Quantum
2639  *magick_restrict q;
2640 
2641  ssize_t
2642  x;
2643 
2644  if (status == MagickFalse)
2645  continue;
2646  q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
2647  if (q == (Quantum *) NULL)
2648  {
2649  status=MagickFalse;
2650  continue;
2651  }
2652  for (x=0; x < (ssize_t) image->columns; x++)
2653  {
2654  double
2655  min_distance;
2656 
2657  ssize_t
2658  i,
2659  k;
2660 
2661  /*
2662  Assign each pixel whose mean has the least squared color distance.
2663  */
2664  k=0;
2665  min_distance=KmeansMetric(image,q,image->colormap+0);
2666  for (i=1; i < (ssize_t) image->colors; i++)
2667  {
2668  double
2669  distance;
2670 
2671  if (min_distance <= MagickEpsilon)
2672  break;
2673  distance=KmeansMetric(image,q,image->colormap+i);
2674  if (distance < min_distance)
2675  {
2676  min_distance=distance;
2677  k=i;
2678  }
2679  }
2680  kmeans_pixels[id][k].red+=QuantumScale*GetPixelRed(image,q);
2681  kmeans_pixels[id][k].green+=QuantumScale*GetPixelGreen(image,q);
2682  kmeans_pixels[id][k].blue+=QuantumScale*GetPixelBlue(image,q);
2683  if (image->alpha_trait != UndefinedPixelTrait)
2684  kmeans_pixels[id][k].alpha+=QuantumScale*GetPixelAlpha(image,q);
2685  if (image->colorspace == CMYKColorspace)
2686  kmeans_pixels[id][k].black+=QuantumScale*GetPixelBlack(image,q);
2687  kmeans_pixels[id][k].count++;
2688  kmeans_pixels[id][k].distortion+=min_distance;
2689  SetPixelIndex(image,(Quantum) k,q);
2690  q+=GetPixelChannels(image);
2691  }
2692  if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
2693  status=MagickFalse;
2694  }
2695  if (status == MagickFalse)
2696  break;
2697  /*
2698  Reduce sums to [0] entry.
2699  */
2700  for (j=1; j < (ssize_t) number_threads; j++)
2701  {
2702  ssize_t
2703  k;
2704 
2705  for (k=0; k < (ssize_t) image->colors; k++)
2706  {
2707  kmeans_pixels[0][k].red+=kmeans_pixels[j][k].red;
2708  kmeans_pixels[0][k].green+=kmeans_pixels[j][k].green;
2709  kmeans_pixels[0][k].blue+=kmeans_pixels[j][k].blue;
2710  if (image->alpha_trait != UndefinedPixelTrait)
2711  kmeans_pixels[0][k].alpha+=kmeans_pixels[j][k].alpha;
2712  if (image->colorspace == CMYKColorspace)
2713  kmeans_pixels[0][k].black+=kmeans_pixels[j][k].black;
2714  kmeans_pixels[0][k].count+=kmeans_pixels[j][k].count;
2715  kmeans_pixels[0][k].distortion+=kmeans_pixels[j][k].distortion;
2716  }
2717  }
2718  /*
2719  Calculate the new means (centroids) of the pixels in the new clusters.
2720  */
2721  distortion=0.0;
2722  for (j=0; j < (ssize_t) image->colors; j++)
2723  {
2724  double
2725  gamma;
2726 
2727  gamma=PerceptibleReciprocal((double) kmeans_pixels[0][j].count);
2728  image->colormap[j].red=gamma*QuantumRange*kmeans_pixels[0][j].red;
2729  image->colormap[j].green=gamma*QuantumRange*kmeans_pixels[0][j].green;
2730  image->colormap[j].blue=gamma*QuantumRange*kmeans_pixels[0][j].blue;
2731  if (image->alpha_trait != UndefinedPixelTrait)
2732  image->colormap[j].alpha=gamma*QuantumRange*kmeans_pixels[0][j].alpha;
2733  if (image->colorspace == CMYKColorspace)
2734  image->colormap[j].black=gamma*QuantumRange*kmeans_pixels[0][j].black;
2735  image->colormap[j].count=(MagickSizeType) kmeans_pixels[0][j].count;
2736  distortion+=kmeans_pixels[0][j].distortion;
2737  }
2738  if (image->debug != MagickFalse)
2739  (void) LogMagickEvent(ImageEvent,GetMagickModule(),
2740  "distortion[%.20g]: %*g %*g\n",(double) n,GetMagickPrecision(),
2741  distortion,GetMagickPrecision(),fabs(distortion-previous_tolerance));
2742  if (fabs(distortion-previous_tolerance) <= tolerance)
2743  break;
2744  previous_tolerance=distortion;
2745  if (image->progress_monitor != (MagickProgressMonitor) NULL)
2746  {
2747  MagickBooleanType
2748  proceed;
2749 
2750  proceed=SetImageProgress(image,KmeansImageTag,(MagickOffsetType) n,
2751  max_iterations);
2752  if (proceed == MagickFalse)
2753  status=MagickFalse;
2754  }
2755  }
2756  image_view=DestroyCacheView(image_view);
2757  if (verbose != MagickFalse)
2758  for (n=0; n < (ssize_t) image->colors; n++)
2759  {
2760  GetColorTuple(image->colormap+n,MagickTrue,tuple);
2761  (void) FormatLocaleFile(stderr,"%s %.20g\n",tuple,(double)
2762  image->colormap[n].count);
2763  }
2764  dominant_image=CloneImage(image,0,0,MagickTrue,exception);
2765  if (dominant_image != (Image *) NULL)
2766  {
2767  /*
2768  Note dominant color.
2769  */
2770  qsort((void *) dominant_image->colormap,dominant_image->colors,
2771  sizeof(*dominant_image->colormap),DominantColorCompare);
2772  GetColorTuple(dominant_image->colormap,MagickTrue,tuple);
2773  dominant_image=DestroyImage(dominant_image);
2774  (void) SetImageProperty(image,"dominant-color",tuple,exception);
2775  }
2776  kmeans_pixels=DestroyKmeansTLS(kmeans_pixels);
2777  if (image->progress_monitor != (MagickProgressMonitor) NULL)
2778  (void) SetImageProgress(image,KmeansImageTag,(MagickOffsetType)
2779  max_iterations-1,max_iterations);
2780  if (status == MagickFalse)
2781  return(status);
2782  return(SyncImage(image,exception));
2783 }
2784 ␌
2785 /*
2786 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2787 % %
2788 % %
2789 % %
2790 % P o s t e r i z e I m a g e %
2791 % %
2792 % %
2793 % %
2794 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2795 %
2796 % PosterizeImage() reduces the image to a limited number of colors for a
2797 % "poster" effect.
2798 %
2799 % The format of the PosterizeImage method is:
2800 %
2801 % MagickBooleanType PosterizeImage(Image *image,const size_t levels,
2802 % const DitherMethod dither_method,ExceptionInfo *exception)
2803 %
2804 % A description of each parameter follows:
2805 %
2806 % o image: Specifies a pointer to an Image structure.
2807 %
2808 % o levels: Number of color levels allowed in each channel. Very low values
2809 % (2, 3, or 4) have the most visible effect.
2810 %
2811 % o dither_method: choose from UndefinedDitherMethod, NoDitherMethod,
2812 % RiemersmaDitherMethod, FloydSteinbergDitherMethod.
2813 %
2814 % o exception: return any errors or warnings in this structure.
2815 %
2816 */
2817 
2818 static inline double MagickRound(double x)
2819 {
2820  /*
2821  Round the fraction to nearest integer.
2822  */
2823  if ((x-floor(x)) < (ceil(x)-x))
2824  return(floor(x));
2825  return(ceil(x));
2826 }
2827 
2828 MagickExport MagickBooleanType PosterizeImage(Image *image,const size_t levels,
2829  const DitherMethod dither_method,ExceptionInfo *exception)
2830 {
2831 #define PosterizeImageTag "Posterize/Image"
2832 #define PosterizePixel(pixel) ClampToQuantum((MagickRealType) QuantumRange*( \
2833  MagickRound(QuantumScale*pixel*(levels-1)))/MagickMax((ssize_t) levels-1,1))
2834 
2835  CacheView
2836  *image_view;
2837 
2838  MagickBooleanType
2839  status;
2840 
2841  MagickOffsetType
2842  progress;
2843 
2844  QuantizeInfo
2845  *quantize_info;
2846 
2847  ssize_t
2848  i;
2849 
2850  ssize_t
2851  y;
2852 
2853  assert(image != (Image *) NULL);
2854  assert(image->signature == MagickCoreSignature);
2855  assert(exception != (ExceptionInfo *) NULL);
2856  assert(exception->signature == MagickCoreSignature);
2857  if (IsEventLogging() != MagickFalse)
2858  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
2859  if (image->storage_class == PseudoClass)
2860 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2861  #pragma omp parallel for schedule(static) shared(progress,status) \
2862  magick_number_threads(image,image,image->colors,1)
2863 #endif
2864  for (i=0; i < (ssize_t) image->colors; i++)
2865  {
2866  /*
2867  Posterize colormap.
2868  */
2869  if ((GetPixelRedTraits(image) & UpdatePixelTrait) != 0)
2870  image->colormap[i].red=(double)
2871  PosterizePixel(image->colormap[i].red);
2872  if ((GetPixelGreenTraits(image) & UpdatePixelTrait) != 0)
2873  image->colormap[i].green=(double)
2874  PosterizePixel(image->colormap[i].green);
2875  if ((GetPixelBlueTraits(image) & UpdatePixelTrait) != 0)
2876  image->colormap[i].blue=(double)
2877  PosterizePixel(image->colormap[i].blue);
2878  if ((GetPixelAlphaTraits(image) & UpdatePixelTrait) != 0)
2879  image->colormap[i].alpha=(double)
2880  PosterizePixel(image->colormap[i].alpha);
2881  }
2882  /*
2883  Posterize image.
2884  */
2885  status=MagickTrue;
2886  progress=0;
2887  image_view=AcquireAuthenticCacheView(image,exception);
2888 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2889  #pragma omp parallel for schedule(static) shared(progress,status) \
2890  magick_number_threads(image,image,image->rows,1)
2891 #endif
2892  for (y=0; y < (ssize_t) image->rows; y++)
2893  {
2894  Quantum
2895  *magick_restrict q;
2896 
2897  ssize_t
2898  x;
2899 
2900  if (status == MagickFalse)
2901  continue;
2902  q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
2903  if (q == (Quantum *) NULL)
2904  {
2905  status=MagickFalse;
2906  continue;
2907  }
2908  for (x=0; x < (ssize_t) image->columns; x++)
2909  {
2910  if ((GetPixelRedTraits(image) & UpdatePixelTrait) != 0)
2911  SetPixelRed(image,PosterizePixel(GetPixelRed(image,q)),q);
2912  if ((GetPixelGreenTraits(image) & UpdatePixelTrait) != 0)
2913  SetPixelGreen(image,PosterizePixel(GetPixelGreen(image,q)),q);
2914  if ((GetPixelBlueTraits(image) & UpdatePixelTrait) != 0)
2915  SetPixelBlue(image,PosterizePixel(GetPixelBlue(image,q)),q);
2916  if (((GetPixelBlackTraits(image) & UpdatePixelTrait) != 0) &&
2917  (image->colorspace == CMYKColorspace))
2918  SetPixelBlack(image,PosterizePixel(GetPixelBlack(image,q)),q);
2919  if (((GetPixelAlphaTraits(image) & UpdatePixelTrait) != 0) &&
2920  (image->alpha_trait != UndefinedPixelTrait))
2921  SetPixelAlpha(image,PosterizePixel(GetPixelAlpha(image,q)),q);
2922  q+=GetPixelChannels(image);
2923  }
2924  if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
2925  status=MagickFalse;
2926  if (image->progress_monitor != (MagickProgressMonitor) NULL)
2927  {
2928  MagickBooleanType
2929  proceed;
2930 
2931 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2932  #pragma omp atomic
2933 #endif
2934  progress++;
2935  proceed=SetImageProgress(image,PosterizeImageTag,progress,image->rows);
2936  if (proceed == MagickFalse)
2937  status=MagickFalse;
2938  }
2939  }
2940  image_view=DestroyCacheView(image_view);
2941  quantize_info=AcquireQuantizeInfo((ImageInfo *) NULL);
2942  quantize_info->number_colors=(size_t) MagickMin((ssize_t) levels*levels*
2943  levels,MaxColormapSize+1);
2944  quantize_info->dither_method=dither_method;
2945  quantize_info->tree_depth=MaxTreeDepth;
2946  status=QuantizeImage(quantize_info,image,exception);
2947  quantize_info=DestroyQuantizeInfo(quantize_info);
2948  return(status);
2949 }
2950 ␌
2951 /*
2952 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2953 % %
2954 % %
2955 % %
2956 + P r u n e C h i l d %
2957 % %
2958 % %
2959 % %
2960 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2961 %
2962 % PruneChild() deletes the given node and merges its statistics into its
2963 % parent.
2964 %
2965 % The format of the PruneSubtree method is:
2966 %
2967 % PruneChild(CubeInfo *cube_info,const NodeInfo *node_info)
2968 %
2969 % A description of each parameter follows.
2970 %
2971 % o cube_info: A pointer to the Cube structure.
2972 %
2973 % o node_info: pointer to node in color cube tree that is to be pruned.
2974 %
2975 */
2976 static void PruneChild(CubeInfo *cube_info,const NodeInfo *node_info)
2977 {
2978  NodeInfo
2979  *parent;
2980 
2981  size_t
2982  number_children;
2983 
2984  ssize_t
2985  i;
2986 
2987  /*
2988  Traverse any children.
2989  */
2990  number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2991  for (i=0; i < (ssize_t) number_children; i++)
2992  if (node_info->child[i] != (NodeInfo *) NULL)
2993  PruneChild(cube_info,node_info->child[i]);
2994  if (cube_info->nodes > cube_info->maximum_colors)
2995  {
2996  /*
2997  Merge color statistics into parent.
2998  */
2999  parent=node_info->parent;
3000  parent->number_unique+=node_info->number_unique;
3001  parent->total_color.red+=node_info->total_color.red;
3002  parent->total_color.green+=node_info->total_color.green;
3003  parent->total_color.blue+=node_info->total_color.blue;
3004  parent->total_color.alpha+=node_info->total_color.alpha;
3005  parent->child[node_info->id]=(NodeInfo *) NULL;
3006  cube_info->nodes--;
3007  }
3008 }
3009 ␌
3010 /*
3011 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3012 % %
3013 % %
3014 % %
3015 + P r u n e L e v e l %
3016 % %
3017 % %
3018 % %
3019 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3020 %
3021 % PruneLevel() deletes all nodes at the bottom level of the color tree merging
3022 % their color statistics into their parent node.
3023 %
3024 % The format of the PruneLevel method is:
3025 %
3026 % PruneLevel(CubeInfo *cube_info,const NodeInfo *node_info)
3027 %
3028 % A description of each parameter follows.
3029 %
3030 % o cube_info: A pointer to the Cube structure.
3031 %
3032 % o node_info: pointer to node in color cube tree that is to be pruned.
3033 %
3034 */
3035 static void PruneLevel(CubeInfo *cube_info,const NodeInfo *node_info)
3036 {
3037  size_t
3038  number_children;
3039 
3040  ssize_t
3041  i;
3042 
3043  /*
3044  Traverse any children.
3045  */
3046  number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
3047  for (i=0; i < (ssize_t) number_children; i++)
3048  if (node_info->child[i] != (NodeInfo *) NULL)
3049  PruneLevel(cube_info,node_info->child[i]);
3050  if (node_info->level == cube_info->depth)
3051  PruneChild(cube_info,node_info);
3052 }
3053 ␌
3054 /*
3055 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3056 % %
3057 % %
3058 % %
3059 + P r u n e T o C u b e D e p t h %
3060 % %
3061 % %
3062 % %
3063 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3064 %
3065 % PruneToCubeDepth() deletes any nodes at a depth greater than
3066 % cube_info->depth while merging their color statistics into their parent
3067 % node.
3068 %
3069 % The format of the PruneToCubeDepth method is:
3070 %
3071 % PruneToCubeDepth(CubeInfo *cube_info,const NodeInfo *node_info)
3072 %
3073 % A description of each parameter follows.
3074 %
3075 % o cube_info: A pointer to the Cube structure.
3076 %
3077 % o node_info: pointer to node in color cube tree that is to be pruned.
3078 %
3079 */
3080 static void PruneToCubeDepth(CubeInfo *cube_info,const NodeInfo *node_info)
3081 {
3082  size_t
3083  number_children;
3084 
3085  ssize_t
3086  i;
3087 
3088  /*
3089  Traverse any children.
3090  */
3091  number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
3092  for (i=0; i < (ssize_t) number_children; i++)
3093  if (node_info->child[i] != (NodeInfo *) NULL)
3094  PruneToCubeDepth(cube_info,node_info->child[i]);
3095  if (node_info->level > cube_info->depth)
3096  PruneChild(cube_info,node_info);
3097 }
3098 ␌
3099 /*
3100 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3101 % %
3102 % %
3103 % %
3104 % Q u a n t i z e I m a g e %
3105 % %
3106 % %
3107 % %
3108 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3109 %
3110 % QuantizeImage() analyzes the colors within a reference image and chooses a
3111 % fixed number of colors to represent the image. The goal of the algorithm
3112 % is to minimize the color difference between the input and output image while
3113 % minimizing the processing time.
3114 %
3115 % The format of the QuantizeImage method is:
3116 %
3117 % MagickBooleanType QuantizeImage(const QuantizeInfo *quantize_info,
3118 % Image *image,ExceptionInfo *exception)
3119 %
3120 % A description of each parameter follows:
3121 %
3122 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
3123 %
3124 % o image: the image.
3125 %
3126 % o exception: return any errors or warnings in this structure.
3127 %
3128 */
3129 MagickExport MagickBooleanType QuantizeImage(const QuantizeInfo *quantize_info,
3130  Image *image,ExceptionInfo *exception)
3131 {
3132  CubeInfo
3133  *cube_info;
3134 
3135  ImageType
3136  type;
3137 
3138  MagickBooleanType
3139  status;
3140 
3141  size_t
3142  depth,
3143  maximum_colors;
3144 
3145  assert(quantize_info != (const QuantizeInfo *) NULL);
3146  assert(quantize_info->signature == MagickCoreSignature);
3147  assert(image != (Image *) NULL);
3148  assert(image->signature == MagickCoreSignature);
3149  assert(exception != (ExceptionInfo *) NULL);
3150  assert(exception->signature == MagickCoreSignature);
3151  if (IsEventLogging() != MagickFalse)
3152  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
3153  maximum_colors=quantize_info->number_colors;
3154  if (maximum_colors == 0)
3155  maximum_colors=MaxColormapSize;
3156  if (maximum_colors > MaxColormapSize)
3157  maximum_colors=MaxColormapSize;
3158  type=IdentifyImageGray(image,exception);
3159  if (IsGrayImageType(type) != MagickFalse)
3160  (void) SetGrayscaleImage(image,exception);
3161  depth=quantize_info->tree_depth;
3162  if (depth == 0)
3163  {
3164  size_t
3165  colors;
3166 
3167  /*
3168  Depth of color tree is: Log4(colormap size)+2.
3169  */
3170  colors=maximum_colors;
3171  for (depth=1; colors != 0; depth++)
3172  colors>>=2;
3173  if ((quantize_info->dither_method != NoDitherMethod) && (depth > 2))
3174  depth--;
3175  if ((image->alpha_trait != UndefinedPixelTrait) && (depth > 5))
3176  depth--;
3177  if (IsGrayImageType(type) != MagickFalse)
3178  depth=MaxTreeDepth;
3179  }
3180  /*
3181  Initialize color cube.
3182  */
3183  cube_info=GetCubeInfo(quantize_info,depth,maximum_colors);
3184  if (cube_info == (CubeInfo *) NULL)
3185  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3186  image->filename);
3187  status=ClassifyImageColors(cube_info,image,exception);
3188  if (status != MagickFalse)
3189  {
3190  /*
3191  Reduce the number of colors in the image.
3192  */
3193  if (cube_info->colors > cube_info->maximum_colors)
3194  ReduceImageColors(image,cube_info);
3195  status=AssignImageColors(image,cube_info,exception);
3196  }
3197  DestroyCubeInfo(cube_info);
3198  return(status);
3199 }
3200 ␌
3201 /*
3202 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3203 % %
3204 % %
3205 % %
3206 % Q u a n t i z e I m a g e s %
3207 % %
3208 % %
3209 % %
3210 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3211 %
3212 % QuantizeImages() analyzes the colors within a set of reference images and
3213 % chooses a fixed number of colors to represent the set. The goal of the
3214 % algorithm is to minimize the color difference between the input and output
3215 % images while minimizing the processing time.
3216 %
3217 % The format of the QuantizeImages method is:
3218 %
3219 % MagickBooleanType QuantizeImages(const QuantizeInfo *quantize_info,
3220 % Image *images,ExceptionInfo *exception)
3221 %
3222 % A description of each parameter follows:
3223 %
3224 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
3225 %
3226 % o images: Specifies a pointer to a list of Image structures.
3227 %
3228 % o exception: return any errors or warnings in this structure.
3229 %
3230 */
3231 MagickExport MagickBooleanType QuantizeImages(const QuantizeInfo *quantize_info,
3232  Image *images,ExceptionInfo *exception)
3233 {
3234  CubeInfo
3235  *cube_info;
3236 
3237  Image
3238  *image;
3239 
3240  MagickBooleanType
3241  proceed,
3242  status;
3243 
3244  MagickProgressMonitor
3245  progress_monitor;
3246 
3247  size_t
3248  depth,
3249  maximum_colors,
3250  number_images;
3251 
3252  ssize_t
3253  i;
3254 
3255  assert(quantize_info != (const QuantizeInfo *) NULL);
3256  assert(quantize_info->signature == MagickCoreSignature);
3257  assert(images != (Image *) NULL);
3258  assert(images->signature == MagickCoreSignature);
3259  assert(exception != (ExceptionInfo *) NULL);
3260  assert(exception->signature == MagickCoreSignature);
3261  if (IsEventLogging() != MagickFalse)
3262  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",images->filename);
3263  if (GetNextImageInList(images) == (Image *) NULL)
3264  {
3265  /*
3266  Handle a single image with QuantizeImage.
3267  */
3268  status=QuantizeImage(quantize_info,images,exception);
3269  return(status);
3270  }
3271  status=MagickFalse;
3272  maximum_colors=quantize_info->number_colors;
3273  if (maximum_colors == 0)
3274  maximum_colors=MaxColormapSize;
3275  if (maximum_colors > MaxColormapSize)
3276  maximum_colors=MaxColormapSize;
3277  depth=quantize_info->tree_depth;
3278  if (depth == 0)
3279  {
3280  size_t
3281  colors;
3282 
3283  /*
3284  Depth of color tree is: Log4(colormap size)+2.
3285  */
3286  colors=maximum_colors;
3287  for (depth=1; colors != 0; depth++)
3288  colors>>=2;
3289  if (quantize_info->dither_method != NoDitherMethod)
3290  depth--;
3291  }
3292  /*
3293  Initialize color cube.
3294  */
3295  cube_info=GetCubeInfo(quantize_info,depth,maximum_colors);
3296  if (cube_info == (CubeInfo *) NULL)
3297  {
3298  (void) ThrowMagickException(exception,GetMagickModule(),
3299  ResourceLimitError,"MemoryAllocationFailed","`%s'",images->filename);
3300  return(MagickFalse);
3301  }
3302  number_images=GetImageListLength(images);
3303  image=images;
3304  for (i=0; image != (Image *) NULL; i++)
3305  {
3306  progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor) NULL,
3307  image->client_data);
3308  status=ClassifyImageColors(cube_info,image,exception);
3309  if (status == MagickFalse)
3310  break;
3311  (void) SetImageProgressMonitor(image,progress_monitor,image->client_data);
3312  proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i,
3313  number_images);
3314  if (proceed == MagickFalse)
3315  break;
3316  image=GetNextImageInList(image);
3317  }
3318  if (status != MagickFalse)
3319  {
3320  /*
3321  Reduce the number of colors in an image sequence.
3322  */
3323  ReduceImageColors(images,cube_info);
3324  image=images;
3325  for (i=0; image != (Image *) NULL; i++)
3326  {
3327  progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor)
3328  NULL,image->client_data);
3329  status=AssignImageColors(image,cube_info,exception);
3330  if (status == MagickFalse)
3331  break;
3332  (void) SetImageProgressMonitor(image,progress_monitor,
3333  image->client_data);
3334  proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i,
3335  number_images);
3336  if (proceed == MagickFalse)
3337  break;
3338  image=GetNextImageInList(image);
3339  }
3340  }
3341  DestroyCubeInfo(cube_info);
3342  return(status);
3343 }
3344 ␌
3345 /*
3346 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3347 % %
3348 % %
3349 % %
3350 + Q u a n t i z e E r r o r F l a t t e n %
3351 % %
3352 % %
3353 % %
3354 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3355 %
3356 % QuantizeErrorFlatten() traverses the color cube and flattens the quantization
3357 % error into a sorted 1D array. This accelerates the color reduction process.
3358 %
3359 % Contributed by Yoya.
3360 %
3361 % The format of the QuantizeErrorFlatten method is:
3362 %
3363 % size_t QuantizeErrorFlatten(const CubeInfo *cube_info,
3364 % const NodeInfo *node_info,const ssize_t offset,
3365 % double *quantize_error)
3366 %
3367 % A description of each parameter follows.
3368 %
3369 % o cube_info: A pointer to the Cube structure.
3370 %
3371 % o node_info: pointer to node in color cube tree that is current pointer.
3372 %
3373 % o offset: quantize error offset.
3374 %
3375 % o quantize_error: the quantization error vector.
3376 %
3377 */
3378 static size_t QuantizeErrorFlatten(const CubeInfo *cube_info,
3379  const NodeInfo *node_info,const ssize_t offset,double *quantize_error)
3380 {
3381  size_t
3382  n,
3383  number_children;
3384 
3385  ssize_t
3386  i;
3387 
3388  if (offset >= (ssize_t) cube_info->nodes)
3389  return(0);
3390  quantize_error[offset]=node_info->quantize_error;
3391  n=1;
3392  number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
3393  for (i=0; i < (ssize_t) number_children ; i++)
3394  if (node_info->child[i] != (NodeInfo *) NULL)
3395  n+=QuantizeErrorFlatten(cube_info,node_info->child[i],offset+n,
3396  quantize_error);
3397  return(n);
3398 }
3399 ␌
3400 /*
3401 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3402 % %
3403 % %
3404 % %
3405 + R e d u c e %
3406 % %
3407 % %
3408 % %
3409 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3410 %
3411 % Reduce() traverses the color cube tree and prunes any node whose
3412 % quantization error falls below a particular threshold.
3413 %
3414 % The format of the Reduce method is:
3415 %
3416 % Reduce(CubeInfo *cube_info,const NodeInfo *node_info)
3417 %
3418 % A description of each parameter follows.
3419 %
3420 % o cube_info: A pointer to the Cube structure.
3421 %
3422 % o node_info: pointer to node in color cube tree that is to be pruned.
3423 %
3424 */
3425 static void Reduce(CubeInfo *cube_info,const NodeInfo *node_info)
3426 {
3427  size_t
3428  number_children;
3429 
3430  ssize_t
3431  i;
3432 
3433  /*
3434  Traverse any children.
3435  */
3436  number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
3437  for (i=0; i < (ssize_t) number_children; i++)
3438  if (node_info->child[i] != (NodeInfo *) NULL)
3439  Reduce(cube_info,node_info->child[i]);
3440  if (node_info->quantize_error <= cube_info->pruning_threshold)
3441  PruneChild(cube_info,node_info);
3442  else
3443  {
3444  /*
3445  Find minimum pruning threshold.
3446  */
3447  if (node_info->number_unique > 0)
3448  cube_info->colors++;
3449  if (node_info->quantize_error < cube_info->next_threshold)
3450  cube_info->next_threshold=node_info->quantize_error;
3451  }
3452 }
3453 ␌
3454 /*
3455 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3456 % %
3457 % %
3458 % %
3459 + R e d u c e I m a g e C o l o r s %
3460 % %
3461 % %
3462 % %
3463 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3464 %
3465 % ReduceImageColors() repeatedly prunes the tree until the number of nodes
3466 % with n2 > 0 is less than or equal to the maximum number of colors allowed
3467 % in the output image. On any given iteration over the tree, it selects
3468 % those nodes whose E value is minimal for pruning and merges their
3469 % color statistics upward. It uses a pruning threshold, Ep, to govern
3470 % node selection as follows:
3471 %
3472 % Ep = 0
3473 % while number of nodes with (n2 > 0) > required maximum number of colors
3474 % prune all nodes such that E <= Ep
3475 % Set Ep to minimum E in remaining nodes
3476 %
3477 % This has the effect of minimizing any quantization error when merging
3478 % two nodes together.
3479 %
3480 % When a node to be pruned has offspring, the pruning procedure invokes
3481 % itself recursively in order to prune the tree from the leaves upward.
3482 % n2, Sr, Sg, and Sb in a node being pruned are always added to the
3483 % corresponding data in that node's parent. This retains the pruned
3484 % node's color characteristics for later averaging.
3485 %
3486 % For each node, n2 pixels exist for which that node represents the
3487 % smallest volume in RGB space containing those pixel's colors. When n2
3488 % > 0 the node will uniquely define a color in the output image. At the
3489 % beginning of reduction, n2 = 0 for all nodes except a the leaves of
3490 % the tree which represent colors present in the input image.
3491 %
3492 % The other pixel count, n1, indicates the total number of colors
3493 % within the cubic volume which the node represents. This includes n1 -
3494 % n2 pixels whose colors should be defined by nodes at a lower level in
3495 % the tree.
3496 %
3497 % The format of the ReduceImageColors method is:
3498 %
3499 % ReduceImageColors(const Image *image,CubeInfo *cube_info)
3500 %
3501 % A description of each parameter follows.
3502 %
3503 % o image: the image.
3504 %
3505 % o cube_info: A pointer to the Cube structure.
3506 %
3507 */
3508 
3509 static int QuantizeErrorCompare(const void *error_p,const void *error_q)
3510 {
3511  double
3512  *p,
3513  *q;
3514 
3515  p=(double *) error_p;
3516  q=(double *) error_q;
3517  if (*p > *q)
3518  return(1);
3519  if (fabs(*q-*p) <= MagickEpsilon)
3520  return(0);
3521  return(-1);
3522 }
3523 
3524 static void ReduceImageColors(const Image *image,CubeInfo *cube_info)
3525 {
3526 #define ReduceImageTag "Reduce/Image"
3527 
3528  MagickBooleanType
3529  proceed;
3530 
3531  MagickOffsetType
3532  offset;
3533 
3534  size_t
3535  span;
3536 
3537  cube_info->next_threshold=0.0;
3538  if (cube_info->colors > cube_info->maximum_colors)
3539  {
3540  double
3541  *quantize_error;
3542 
3543  /*
3544  Enable rapid reduction of the number of unique colors.
3545  */
3546  quantize_error=(double *) AcquireQuantumMemory(cube_info->nodes,
3547  sizeof(*quantize_error));
3548  if (quantize_error != (double *) NULL)
3549  {
3550  (void) QuantizeErrorFlatten(cube_info,cube_info->root,0,
3551  quantize_error);
3552  qsort(quantize_error,cube_info->nodes,sizeof(double),
3553  QuantizeErrorCompare);
3554  if (cube_info->nodes > (110*(cube_info->maximum_colors+1)/100))
3555  cube_info->next_threshold=quantize_error[cube_info->nodes-110*
3556  (cube_info->maximum_colors+1)/100];
3557  quantize_error=(double *) RelinquishMagickMemory(quantize_error);
3558  }
3559  }
3560  for (span=cube_info->colors; cube_info->colors > cube_info->maximum_colors; )
3561  {
3562  cube_info->pruning_threshold=cube_info->next_threshold;
3563  cube_info->next_threshold=cube_info->root->quantize_error-1;
3564  cube_info->colors=0;
3565  Reduce(cube_info,cube_info->root);
3566  offset=(MagickOffsetType) span-cube_info->colors;
3567  proceed=SetImageProgress(image,ReduceImageTag,offset,span-
3568  cube_info->maximum_colors+1);
3569  if (proceed == MagickFalse)
3570  break;
3571  }
3572 }
3573 ␌
3574 /*
3575 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3576 % %
3577 % %
3578 % %
3579 % R e m a p I m a g e %
3580 % %
3581 % %
3582 % %
3583 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3584 %
3585 % RemapImage() replaces the colors of an image with the closest of the colors
3586 % from the reference image.
3587 %
3588 % The format of the RemapImage method is:
3589 %
3590 % MagickBooleanType RemapImage(const QuantizeInfo *quantize_info,
3591 % Image *image,const Image *remap_image,ExceptionInfo *exception)
3592 %
3593 % A description of each parameter follows:
3594 %
3595 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
3596 %
3597 % o image: the image.
3598 %
3599 % o remap_image: the reference image.
3600 %
3601 % o exception: return any errors or warnings in this structure.
3602 %
3603 */
3604 MagickExport MagickBooleanType RemapImage(const QuantizeInfo *quantize_info,
3605  Image *image,const Image *remap_image,ExceptionInfo *exception)
3606 {
3607  CubeInfo
3608  *cube_info;
3609 
3610  MagickBooleanType
3611  status;
3612 
3613  /*
3614  Initialize color cube.
3615  */
3616  assert(image != (Image *) NULL);
3617  assert(image->signature == MagickCoreSignature);
3618  assert(remap_image != (Image *) NULL);
3619  assert(remap_image->signature == MagickCoreSignature);
3620  assert(exception != (ExceptionInfo *) NULL);
3621  assert(exception->signature == MagickCoreSignature);
3622  if (IsEventLogging() != MagickFalse)
3623  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
3624  cube_info=GetCubeInfo(quantize_info,MaxTreeDepth,
3625  quantize_info->number_colors);
3626  if (cube_info == (CubeInfo *) NULL)
3627  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3628  image->filename);
3629  status=ClassifyImageColors(cube_info,remap_image,exception);
3630  if (status != MagickFalse)
3631  {
3632  /*
3633  Classify image colors from the reference image.
3634  */
3635  cube_info->quantize_info->number_colors=cube_info->colors;
3636  status=AssignImageColors(image,cube_info,exception);
3637  }
3638  DestroyCubeInfo(cube_info);
3639  return(status);
3640 }
3641 ␌
3642 /*
3643 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3644 % %
3645 % %
3646 % %
3647 % R e m a p I m a g e s %
3648 % %
3649 % %
3650 % %
3651 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3652 %
3653 % RemapImages() replaces the colors of a sequence of images with the
3654 % closest color from a reference image.
3655 %
3656 % The format of the RemapImage method is:
3657 %
3658 % MagickBooleanType RemapImages(const QuantizeInfo *quantize_info,
3659 % Image *images,Image *remap_image,ExceptionInfo *exception)
3660 %
3661 % A description of each parameter follows:
3662 %
3663 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
3664 %
3665 % o images: the image sequence.
3666 %
3667 % o remap_image: the reference image.
3668 %
3669 % o exception: return any errors or warnings in this structure.
3670 %
3671 */
3672 MagickExport MagickBooleanType RemapImages(const QuantizeInfo *quantize_info,
3673  Image *images,const Image *remap_image,ExceptionInfo *exception)
3674 {
3675  CubeInfo
3676  *cube_info;
3677 
3678  Image
3679  *image;
3680 
3681  MagickBooleanType
3682  status;
3683 
3684  assert(images != (Image *) NULL);
3685  assert(images->signature == MagickCoreSignature);
3686  assert(exception != (ExceptionInfo *) NULL);
3687  assert(exception->signature == MagickCoreSignature);
3688  if (IsEventLogging() != MagickFalse)
3689  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",images->filename);
3690  image=images;
3691  if (remap_image == (Image *) NULL)
3692  {
3693  /*
3694  Create a global colormap for an image sequence.
3695  */
3696  status=QuantizeImages(quantize_info,images,exception);
3697  return(status);
3698  }
3699  /*
3700  Classify image colors from the reference image.
3701  */
3702  cube_info=GetCubeInfo(quantize_info,MaxTreeDepth,
3703  quantize_info->number_colors);
3704  if (cube_info == (CubeInfo *) NULL)
3705  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3706  image->filename);
3707  status=ClassifyImageColors(cube_info,remap_image,exception);
3708  if (status != MagickFalse)
3709  {
3710  /*
3711  Classify image colors from the reference image.
3712  */
3713  cube_info->quantize_info->number_colors=cube_info->colors;
3714  image=images;
3715  for ( ; image != (Image *) NULL; image=GetNextImageInList(image))
3716  {
3717  status=AssignImageColors(image,cube_info,exception);
3718  if (status == MagickFalse)
3719  break;
3720  }
3721  }
3722  DestroyCubeInfo(cube_info);
3723  return(status);
3724 }
3725 ␌
3726 /*
3727 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3728 % %
3729 % %
3730 % %
3731 % S e t G r a y s c a l e I m a g e %
3732 % %
3733 % %
3734 % %
3735 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3736 %
3737 % SetGrayscaleImage() converts an image to a PseudoClass grayscale image.
3738 %
3739 % The format of the SetGrayscaleImage method is:
3740 %
3741 % MagickBooleanType SetGrayscaleImage(Image *image,
3742 % ExceptionInfo *exception)
3743 %
3744 % A description of each parameter follows:
3745 %
3746 % o image: The image.
3747 %
3748 % o exception: return any errors or warnings in this structure.
3749 %
3750 */
3751 
3752 #if defined(__cplusplus) || defined(c_plusplus)
3753 extern "C" {
3754 #endif
3755 
3756 static int IntensityCompare(const void *x,const void *y)
3757 {
3758  double
3759  intensity;
3760 
3761  PixelInfo
3762  *color_1,
3763  *color_2;
3764 
3765  color_1=(PixelInfo *) x;
3766  color_2=(PixelInfo *) y;
3767  intensity=GetPixelInfoIntensity((const Image *) NULL,color_1)-
3768  GetPixelInfoIntensity((const Image *) NULL,color_2);
3769  if (intensity < (double) INT_MIN)
3770  intensity=(double) INT_MIN;
3771  if (intensity > (double) INT_MAX)
3772  intensity=(double) INT_MAX;
3773  return((int) intensity);
3774 }
3775 
3776 #if defined(__cplusplus) || defined(c_plusplus)
3777 }
3778 #endif
3779 
3780 static MagickBooleanType SetGrayscaleImage(Image *image,
3781  ExceptionInfo *exception)
3782 {
3783  CacheView
3784  *image_view;
3785 
3786  MagickBooleanType
3787  status;
3788 
3789  PixelInfo
3790  *colormap;
3791 
3792  size_t
3793  extent;
3794 
3795  ssize_t
3796  *colormap_index,
3797  i,
3798  j,
3799  y;
3800 
3801  assert(image != (Image *) NULL);
3802  assert(image->signature == MagickCoreSignature);
3803  if (image->type != GrayscaleType)
3804  (void) TransformImageColorspace(image,GRAYColorspace,exception);
3805  extent=MagickMax(image->colors+1,MagickMax(MaxColormapSize,MaxMap+1));
3806  colormap_index=(ssize_t *) AcquireQuantumMemory(extent,
3807  sizeof(*colormap_index));
3808  if (colormap_index == (ssize_t *) NULL)
3809  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3810  image->filename);
3811  if (image->storage_class != PseudoClass)
3812  {
3813  (void) memset(colormap_index,(-1),extent*sizeof(*colormap_index));
3814  if (AcquireImageColormap(image,MaxColormapSize,exception) == MagickFalse)
3815  {
3816  colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
3817  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3818  image->filename);
3819  }
3820  image->colors=0;
3821  status=MagickTrue;
3822  image_view=AcquireAuthenticCacheView(image,exception);
3823 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3824  #pragma omp parallel for schedule(static) shared(status) \
3825  magick_number_threads(image,image,image->rows,1)
3826 #endif
3827  for (y=0; y < (ssize_t) image->rows; y++)
3828  {
3829  Quantum
3830  *magick_restrict q;
3831 
3832  ssize_t
3833  x;
3834 
3835  if (status == MagickFalse)
3836  continue;
3837  q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,
3838  exception);
3839  if (q == (Quantum *) NULL)
3840  {
3841  status=MagickFalse;
3842  continue;
3843  }
3844  for (x=0; x < (ssize_t) image->columns; x++)
3845  {
3846  size_t
3847  intensity;
3848 
3849  intensity=ScaleQuantumToMap(GetPixelRed(image,q));
3850  if (colormap_index[intensity] < 0)
3851  {
3852 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3853  #pragma omp critical (MagickCore_SetGrayscaleImage)
3854 #endif
3855  if (colormap_index[intensity] < 0)
3856  {
3857  colormap_index[intensity]=(ssize_t) image->colors;
3858  image->colormap[image->colors].red=(double)
3859  GetPixelRed(image,q);
3860  image->colormap[image->colors].green=(double)
3861  GetPixelGreen(image,q);
3862  image->colormap[image->colors].blue=(double)
3863  GetPixelBlue(image,q);
3864  image->colors++;
3865  }
3866  }
3867  SetPixelIndex(image,(Quantum) colormap_index[intensity],q);
3868  q+=GetPixelChannels(image);
3869  }
3870  if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
3871  status=MagickFalse;
3872  }
3873  image_view=DestroyCacheView(image_view);
3874  }
3875  (void) memset(colormap_index,0,extent*sizeof(*colormap_index));
3876  for (i=0; i < (ssize_t) image->colors; i++)
3877  image->colormap[i].alpha=(double) i;
3878  qsort((void *) image->colormap,image->colors,sizeof(PixelInfo),
3879  IntensityCompare);
3880  colormap=(PixelInfo *) AcquireQuantumMemory(image->colors,sizeof(*colormap));
3881  if (colormap == (PixelInfo *) NULL)
3882  {
3883  colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
3884  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3885  image->filename);
3886  }
3887  j=0;
3888  colormap[j]=image->colormap[0];
3889  for (i=0; i < (ssize_t) image->colors; i++)
3890  {
3891  if (IsPixelInfoEquivalent(&colormap[j],&image->colormap[i]) == MagickFalse)
3892  {
3893  j++;
3894  colormap[j]=image->colormap[i];
3895  }
3896  colormap_index[(ssize_t) image->colormap[i].alpha]=j;
3897  }
3898  image->colors=(size_t) (j+1);
3899  image->colormap=(PixelInfo *) RelinquishMagickMemory(image->colormap);
3900  image->colormap=colormap;
3901  status=MagickTrue;
3902  image_view=AcquireAuthenticCacheView(image,exception);
3903 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3904  #pragma omp parallel for schedule(static) shared(status) \
3905  magick_number_threads(image,image,image->rows,1)
3906 #endif
3907  for (y=0; y < (ssize_t) image->rows; y++)
3908  {
3909  Quantum
3910  *magick_restrict q;
3911 
3912  ssize_t
3913  x;
3914 
3915  if (status == MagickFalse)
3916  continue;
3917  q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
3918  if (q == (Quantum *) NULL)
3919  {
3920  status=MagickFalse;
3921  continue;
3922  }
3923  for (x=0; x < (ssize_t) image->columns; x++)
3924  {
3925  SetPixelIndex(image,(Quantum) colormap_index[ScaleQuantumToMap(
3926  GetPixelIndex(image,q))],q);
3927  q+=GetPixelChannels(image);
3928  }
3929  if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
3930  status=MagickFalse;
3931  }
3932  image_view=DestroyCacheView(image_view);
3933  colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
3934  image->type=GrayscaleType;
3935  if (SetImageMonochrome(image,exception) != MagickFalse)
3936  image->type=BilevelType;
3937  return(status);
3938 }
3939 ␌
3940 /*
3941 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3942 % %
3943 % %
3944 % %
3945 + S e t I m a g e C o l o r m a p %
3946 % %
3947 % %
3948 % %
3949 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3950 %
3951 % SetImageColormap() traverses the color cube tree and sets the colormap of
3952 % the image. A colormap entry is any node in the color cube tree where the
3953 % of unique colors is not zero.
3954 %
3955 % The format of the SetImageColormap method is:
3956 %
3957 % MagickBooleanType SetImageColormap(Image *image,CubeInfo *cube_info,
3958 % ExceptionInfo *node_info)
3959 %
3960 % A description of each parameter follows.
3961 %
3962 % o image: the image.
3963 %
3964 % o cube_info: A pointer to the Cube structure.
3965 %
3966 % o exception: return any errors or warnings in this structure.
3967 %
3968 */
3969 
3970 MagickBooleanType SetImageColormap(Image *image,CubeInfo *cube_info,
3971  ExceptionInfo *exception)
3972 {
3973  size_t
3974  number_colors;
3975 
3976  number_colors=MagickMax(cube_info->maximum_colors,cube_info->colors);
3977  if (AcquireImageColormap(image,number_colors,exception) == MagickFalse)
3978  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3979  image->filename);
3980  image->colors=0;
3981  DefineImageColormap(image,cube_info,cube_info->root);
3982  if (image->colors != number_colors)
3983  {
3984  image->colormap=(PixelInfo *) ResizeQuantumMemory(image->colormap,
3985  image->colors+1,sizeof(*image->colormap));
3986  if (image->colormap == (PixelInfo *) NULL)
3987  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3988  image->filename);
3989  }
3990  return(MagickTrue);
3991 }
Definition: image.h:152