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