MagickCore  6.9.12-94
Convert, Edit, Or Compose Bitmap Images
 All Data Structures
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 "magick/studio.h"
177 #include "magick/artifact.h"
178 #include "magick/attribute.h"
179 #include "magick/cache-view.h"
180 #include "magick/color.h"
181 #include "magick/color-private.h"
182 #include "magick/colormap.h"
183 #include "magick/colorspace.h"
184 #include "magick/colorspace-private.h"
185 #include "magick/enhance.h"
186 #include "magick/exception.h"
187 #include "magick/exception-private.h"
188 #include "magick/histogram.h"
189 #include "magick/image.h"
190 #include "magick/image-private.h"
191 #include "magick/list.h"
192 #include "magick/memory_.h"
193 #include "magick/monitor.h"
194 #include "magick/monitor-private.h"
195 #include "magick/option.h"
196 #include "magick/pixel-private.h"
197 #include "magick/quantize.h"
198 #include "magick/quantum.h"
199 #include "magick/resource_.h"
200 #include "magick/string_.h"
201 #include "magick/string-private.h"
202 #include "magick/thread-private.h"
203 
204 /*
205  Define declarations.
206 */
207 #if !defined(__APPLE__) && !defined(TARGET_OS_IPHONE)
208 #define CacheShift 2
209 #else
210 #define CacheShift 3
211 #endif
212 #define ErrorQueueLength 16
213 #define ErrorRelativeWeight PerceptibleReciprocal(16)
214 #define MaxNodes 266817
215 #define MaxTreeDepth 8
216 #define NodesInAList 1920
217 
218 /*
219  Typedef declarations.
220 */
221 typedef struct _NodeInfo
222 {
223  struct _NodeInfo
224  *parent,
225  *child[16];
226 
227  MagickSizeType
228  number_unique;
229 
231  total_color;
232 
233  MagickRealType
234  quantize_error;
235 
236  size_t
237  color_number,
238  id,
239  level;
240 } NodeInfo;
241 
242 typedef struct _Nodes
243 {
244  NodeInfo
245  *nodes;
246 
247  struct _Nodes
248  *next;
249 } Nodes;
250 
251 typedef struct _CubeInfo
252 {
253  NodeInfo
254  *root;
255 
256  size_t
257  colors,
258  maximum_colors;
259 
260  ssize_t
261  transparent_index;
262 
263  MagickSizeType
264  transparent_pixels;
265 
267  target;
268 
269  MagickRealType
270  distance,
271  pruning_threshold,
272  next_threshold;
273 
274  size_t
275  nodes,
276  free_nodes,
277  color_number;
278 
279  NodeInfo
280  *next_node;
281 
282  Nodes
283  *node_queue;
284 
285  MemoryInfo
286  *memory_info;
287 
288  ssize_t
289  *cache;
290 
292  error[ErrorQueueLength];
293 
294  MagickRealType
295  diffusion,
296  weights[ErrorQueueLength];
297 
299  *quantize_info;
300 
301  MagickBooleanType
302  associate_alpha;
303 
304  ssize_t
305  x,
306  y;
307 
308  size_t
309  depth;
310 
311  MagickOffsetType
312  offset;
313 
314  MagickSizeType
315  span;
316 } CubeInfo;
317 
318 /*
319  Method prototypes.
320 */
321 static CubeInfo
322  *GetCubeInfo(const QuantizeInfo *,const size_t,const size_t);
323 
324 static NodeInfo
325  *GetNodeInfo(CubeInfo *,const size_t,const size_t,NodeInfo *);
326 
327 static MagickBooleanType
328  AssignImageColors(Image *,CubeInfo *),
329  ClassifyImageColors(CubeInfo *,const Image *,ExceptionInfo *),
330  DitherImage(Image *,CubeInfo *),
331  SetGrayscaleImage(Image *);
332 
333 static void
334  ClosestColor(const Image *,CubeInfo *,const NodeInfo *),
335  DefineImageColormap(Image *,CubeInfo *,NodeInfo *),
336  DestroyCubeInfo(CubeInfo *),
337  PruneLevel(CubeInfo *,const NodeInfo *),
338  PruneToCubeDepth(CubeInfo *,const NodeInfo *),
339  ReduceImageColors(const Image *,CubeInfo *);
340 
341 /*
342 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
343 % %
344 % %
345 % %
346 % A c q u i r e Q u a n t i z e I n f o %
347 % %
348 % %
349 % %
350 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
351 %
352 % AcquireQuantizeInfo() allocates the QuantizeInfo structure.
353 %
354 % The format of the AcquireQuantizeInfo method is:
355 %
356 % QuantizeInfo *AcquireQuantizeInfo(const ImageInfo *image_info)
357 %
358 % A description of each parameter follows:
359 %
360 % o image_info: the image info.
361 %
362 */
363 MagickExport QuantizeInfo *AcquireQuantizeInfo(const ImageInfo *image_info)
364 {
366  *quantize_info;
367 
368  quantize_info=(QuantizeInfo *) AcquireMagickMemory(sizeof(*quantize_info));
369  if (quantize_info == (QuantizeInfo *) NULL)
370  ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
371  GetQuantizeInfo(quantize_info);
372  if (image_info != (ImageInfo *) NULL)
373  {
374  const char
375  *option;
376 
377  quantize_info->dither=image_info->dither;
378  option=GetImageOption(image_info,"dither");
379  if (option != (const char *) NULL)
380  quantize_info->dither_method=(DitherMethod) ParseCommandOption(
381  MagickDitherOptions,MagickFalse,option);
382  quantize_info->measure_error=image_info->verbose;
383  }
384  return(quantize_info);
385 }
386 
387 /*
388 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
389 % %
390 % %
391 % %
392 + A s s i g n I m a g e C o l o r s %
393 % %
394 % %
395 % %
396 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
397 %
398 % AssignImageColors() generates the output image from the pruned tree. The
399 % output image consists of two parts: (1) A color map, which is an array
400 % of color descriptions (RGB triples) for each color present in the
401 % output image; (2) A pixel array, which represents each pixel as an
402 % index into the color map array.
403 %
404 % First, the assignment phase makes one pass over the pruned color
405 % description tree to establish the image's color map. For each node
406 % with n2 > 0, it divides Sr, Sg, and Sb by n2 . This produces the mean
407 % color of all pixels that classify no lower than this node. Each of
408 % these colors becomes an entry in the color map.
409 %
410 % Finally, the assignment phase reclassifies each pixel in the pruned
411 % tree to identify the deepest node containing the pixel's color. The
412 % pixel's value in the pixel array becomes the index of this node's mean
413 % color in the color map.
414 %
415 % The format of the AssignImageColors() method is:
416 %
417 % MagickBooleanType AssignImageColors(Image *image,CubeInfo *cube_info)
418 %
419 % A description of each parameter follows.
420 %
421 % o image: the image.
422 %
423 % o cube_info: A pointer to the Cube structure.
424 %
425 */
426 
427 static inline void AssociateAlphaPixel(const CubeInfo *cube_info,
428  const PixelPacket *pixel,DoublePixelPacket *alpha_pixel)
429 {
430  MagickRealType
431  alpha;
432 
433  alpha_pixel->index=0;
434  if ((cube_info->associate_alpha == MagickFalse) ||
435  (pixel->opacity == OpaqueOpacity))
436  {
437  alpha_pixel->red=(MagickRealType) GetPixelRed(pixel);
438  alpha_pixel->green=(MagickRealType) GetPixelGreen(pixel);
439  alpha_pixel->blue=(MagickRealType) GetPixelBlue(pixel);
440  alpha_pixel->opacity=(MagickRealType) GetPixelOpacity(pixel);
441  return;
442  }
443  alpha=(MagickRealType) (QuantumScale*((MagickRealType) QuantumRange-
444  (MagickRealType) GetPixelOpacity(pixel)));
445  alpha_pixel->red=alpha*(MagickRealType) GetPixelRed(pixel);
446  alpha_pixel->green=alpha*(MagickRealType) GetPixelGreen(pixel);
447  alpha_pixel->blue=alpha*(MagickRealType) GetPixelBlue(pixel);
448  alpha_pixel->opacity=(MagickRealType) GetPixelOpacity(pixel);
449 }
450 
451 static inline size_t ColorToNodeId(const CubeInfo *cube_info,
452  const DoublePixelPacket *pixel,size_t index)
453 {
454  size_t
455  id;
456 
457  id=(size_t) (((ScaleQuantumToChar(ClampPixel(GetPixelRed(pixel))) >> index) &
458  0x01) | ((ScaleQuantumToChar(ClampPixel(GetPixelGreen(pixel))) >> index) &
459  0x01) << 1 | ((ScaleQuantumToChar(ClampPixel(GetPixelBlue(pixel))) >>
460  index) & 0x01) << 2);
461  if (cube_info->associate_alpha != MagickFalse)
462  id|=((ScaleQuantumToChar(ClampPixel(GetPixelOpacity(pixel))) >> index) &
463  0x1) << 3;
464  return(id);
465 }
466 
467 static inline MagickBooleanType IsSameColor(const Image *image,
468  const PixelPacket *p,const PixelPacket *q)
469 {
470  if ((GetPixelRed(p) != GetPixelRed(q)) ||
471  (GetPixelGreen(p) != GetPixelGreen(q)) ||
472  (GetPixelBlue(p) != GetPixelBlue(q)))
473  return(MagickFalse);
474  if ((image->matte != MagickFalse) &&
475  (GetPixelOpacity(p) != GetPixelOpacity(q)))
476  return(MagickFalse);
477  return(MagickTrue);
478 }
479 
480 static MagickBooleanType AssignImageColors(Image *image,CubeInfo *cube_info)
481 {
482 #define AssignImageTag "Assign/Image"
483 
484  ColorspaceType
485  colorspace;
486 
487  ssize_t
488  y;
489 
490  size_t
491  number_colors;
492 
493  /*
494  Allocate image colormap.
495  */
496  colorspace=image->colorspace;
497  if (cube_info->quantize_info->colorspace != UndefinedColorspace)
498  (void) TransformImageColorspace(image,cube_info->quantize_info->colorspace);
499  number_colors=MagickMax(cube_info->colors,cube_info->maximum_colors);
500  if (AcquireImageColormap(image,number_colors) == MagickFalse)
501  ThrowBinaryImageException(ResourceLimitError,"MemoryAllocationFailed",
502  image->filename);
503  image->colors=0;
504  cube_info->transparent_pixels=0;
505  cube_info->transparent_index=(-1);
506  DefineImageColormap(image,cube_info,cube_info->root);
507  /*
508  Create a reduced color image.
509  */
510  if ((cube_info->quantize_info->dither != MagickFalse) &&
511  (cube_info->quantize_info->dither_method != NoDitherMethod))
512  (void) DitherImage(image,cube_info);
513  else
514  {
515  CacheView
516  *image_view;
517 
519  *exception;
520 
521  MagickBooleanType
522  status;
523 
524  status=MagickTrue;
525  exception=(&image->exception);
526  image_view=AcquireAuthenticCacheView(image,exception);
527 #if defined(MAGICKCORE_OPENMP_SUPPORT)
528  #pragma omp parallel for schedule(static) shared(status) \
529  magick_number_threads(image,image,image->rows,1)
530 #endif
531  for (y=0; y < (ssize_t) image->rows; y++)
532  {
533  CubeInfo
534  cube;
535 
536  IndexPacket
537  *magick_restrict indexes;
538 
540  *magick_restrict q;
541 
542  ssize_t
543  x;
544 
545  ssize_t
546  count;
547 
548  if (status == MagickFalse)
549  continue;
550  q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,
551  exception);
552  if (q == (PixelPacket *) NULL)
553  {
554  status=MagickFalse;
555  continue;
556  }
557  indexes=GetCacheViewAuthenticIndexQueue(image_view);
558  cube=(*cube_info);
559  for (x=0; x < (ssize_t) image->columns; x+=count)
560  {
562  pixel;
563 
564  const NodeInfo
565  *node_info;
566 
567  ssize_t
568  i;
569 
570  size_t
571  id,
572  index;
573 
574  /*
575  Identify the deepest node containing the pixel's color.
576  */
577  for (count=1; (x+count) < (ssize_t) image->columns; count++)
578  if (IsSameColor(image,q,q+count) == MagickFalse)
579  break;
580  AssociateAlphaPixel(&cube,q,&pixel);
581  node_info=cube.root;
582  for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
583  {
584  id=ColorToNodeId(&cube,&pixel,index);
585  if (node_info->child[id] == (NodeInfo *) NULL)
586  break;
587  node_info=node_info->child[id];
588  }
589  /*
590  Find closest color among siblings and their children.
591  */
592  cube.target=pixel;
593  cube.distance=(MagickRealType) (4.0*((MagickRealType) QuantumRange+
594  1.0)*((MagickRealType) QuantumRange+1.0)+1.0);
595  ClosestColor(image,&cube,node_info->parent);
596  index=cube.color_number;
597  for (i=0; i < (ssize_t) count; i++)
598  {
599  if (image->storage_class == PseudoClass)
600  SetPixelIndex(indexes+x+i,index);
601  if (cube.quantize_info->measure_error == MagickFalse)
602  {
603  SetPixelRgb(q,image->colormap+index);
604  if (cube.associate_alpha != MagickFalse)
605  SetPixelOpacity(q,image->colormap[index].opacity);
606  }
607  q++;
608  }
609  }
610  if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
611  status=MagickFalse;
612  if (image->progress_monitor != (MagickProgressMonitor) NULL)
613  {
614  MagickBooleanType
615  proceed;
616 
617  proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) y,
618  image->rows);
619  if (proceed == MagickFalse)
620  status=MagickFalse;
621  }
622  }
623  image_view=DestroyCacheView(image_view);
624  }
625  if (cube_info->quantize_info->measure_error != MagickFalse)
626  (void) GetImageQuantizeError(image);
627  if ((cube_info->quantize_info->number_colors == 2) &&
628  (IsGrayColorspace(cube_info->quantize_info->colorspace)))
629  {
630  double
631  intensity;
632 
633  /*
634  Monochrome image.
635  */
636  intensity=GetPixelLuma(image,image->colormap+0) <
637  (MagickRealType) QuantumRange/2.0 ? 0.0 : (double) QuantumRange;
638  if ((image->colors > 1) &&
639  (GetPixelLuma(image,image->colormap+0) >
640  GetPixelLuma(image,image->colormap+1)))
641  intensity=(double) QuantumRange;
642  image->colormap[0].red=intensity;
643  image->colormap[0].green=intensity;
644  image->colormap[0].blue=intensity;
645  if (image->colors > 1)
646  {
647  image->colormap[1].red=(double) QuantumRange-intensity;
648  image->colormap[1].green=(double) QuantumRange-intensity;
649  image->colormap[1].blue=(double) QuantumRange-intensity;
650  }
651  }
652  (void) SyncImage(image);
653  if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
654  (IssRGBCompatibleColorspace(colorspace) == MagickFalse))
655  (void) TransformImageColorspace(image,colorspace);
656  return(MagickTrue);
657 }
658 
659 /*
660 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
661 % %
662 % %
663 % %
664 + C l a s s i f y I m a g e C o l o r s %
665 % %
666 % %
667 % %
668 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
669 %
670 % ClassifyImageColors() begins by initializing a color description tree
671 % of sufficient depth to represent each possible input color in a leaf.
672 % However, it is impractical to generate a fully-formed color
673 % description tree in the storage_class phase for realistic values of
674 % Cmax. If colors components in the input image are quantized to k-bit
675 % precision, so that Cmax= 2k-1, the tree would need k levels below the
676 % root node to allow representing each possible input color in a leaf.
677 % This becomes prohibitive because the tree's total number of nodes is
678 % 1 + sum(i=1,k,8k).
679 %
680 % A complete tree would require 19,173,961 nodes for k = 8, Cmax = 255.
681 % Therefore, to avoid building a fully populated tree, QUANTIZE: (1)
682 % Initializes data structures for nodes only as they are needed; (2)
683 % Chooses a maximum depth for the tree as a function of the desired
684 % number of colors in the output image (currently log2(colormap size)).
685 %
686 % For each pixel in the input image, storage_class scans downward from
687 % the root of the color description tree. At each level of the tree it
688 % identifies the single node which represents a cube in RGB space
689 % containing It updates the following data for each such node:
690 %
691 % n1 : Number of pixels whose color is contained in the RGB cube
692 % which this node represents;
693 %
694 % n2 : Number of pixels whose color is not represented in a node at
695 % lower depth in the tree; initially, n2 = 0 for all nodes except
696 % leaves of the tree.
697 %
698 % Sr, Sg, Sb : Sums of the red, green, and blue component values for
699 % all pixels not classified at a lower depth. The combination of
700 % these sums and n2 will ultimately characterize the mean color of a
701 % set of pixels represented by this node.
702 %
703 % E: the distance squared in RGB space between each pixel contained
704 % within a node and the nodes' center. This represents the quantization
705 % error for a node.
706 %
707 % The format of the ClassifyImageColors() method is:
708 %
709 % MagickBooleanType ClassifyImageColors(CubeInfo *cube_info,
710 % const Image *image,ExceptionInfo *exception)
711 %
712 % A description of each parameter follows.
713 %
714 % o cube_info: A pointer to the Cube structure.
715 %
716 % o image: the image.
717 %
718 */
719 
720 static inline void SetAssociatedAlpha(const Image *image,CubeInfo *cube_info)
721 {
722  MagickBooleanType
723  associate_alpha;
724 
725  associate_alpha=image->matte;
726  if ((cube_info->quantize_info->number_colors == 2) &&
727  ((cube_info->quantize_info->colorspace == LinearGRAYColorspace) ||
728  (cube_info->quantize_info->colorspace == GRAYColorspace)))
729  associate_alpha=MagickFalse;
730  cube_info->associate_alpha=associate_alpha;
731 }
732 
733 static MagickBooleanType ClassifyImageColors(CubeInfo *cube_info,
734  const Image *image,ExceptionInfo *exception)
735 {
736 #define ClassifyImageTag "Classify/Image"
737 
738  CacheView
739  *image_view;
740 
742  error,
743  mid,
744  midpoint,
745  pixel;
746 
747  MagickBooleanType
748  proceed;
749 
750  MagickRealType
751  bisect;
752 
753  NodeInfo
754  *node_info;
755 
756  size_t
757  count,
758  id,
759  index,
760  level;
761 
762  ssize_t
763  y;
764 
765  /*
766  Classify the first cube_info->maximum_colors colors to a tree depth of 8.
767  */
768  SetAssociatedAlpha(image,cube_info);
769  if (cube_info->quantize_info->colorspace != image->colorspace)
770  {
771  if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
772  (cube_info->quantize_info->colorspace != CMYKColorspace))
773  (void) TransformImageColorspace((Image *) image,
774  cube_info->quantize_info->colorspace);
775  else
776  if (IssRGBCompatibleColorspace(image->colorspace) == MagickFalse)
777  (void) TransformImageColorspace((Image *) image,sRGBColorspace);
778  }
779  midpoint.red=(MagickRealType) QuantumRange/2.0;
780  midpoint.green=(MagickRealType) QuantumRange/2.0;
781  midpoint.blue=(MagickRealType) QuantumRange/2.0;
782  midpoint.opacity=(MagickRealType) QuantumRange/2.0;
783  midpoint.index=(MagickRealType) QuantumRange/2.0;
784  error.opacity=0.0;
785  image_view=AcquireVirtualCacheView(image,exception);
786  for (y=0; y < (ssize_t) image->rows; y++)
787  {
788  const PixelPacket
789  *magick_restrict p;
790 
791  ssize_t
792  x;
793 
794  p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
795  if (p == (const PixelPacket *) NULL)
796  break;
797  if (cube_info->nodes > MaxNodes)
798  {
799  /*
800  Prune one level if the color tree is too large.
801  */
802  PruneLevel(cube_info,cube_info->root);
803  cube_info->depth--;
804  }
805  for (x=0; x < (ssize_t) image->columns; x+=(ssize_t) count)
806  {
807  /*
808  Start at the root and descend the color cube tree.
809  */
810  for (count=1; (x+(ssize_t) count) < (ssize_t) image->columns; count++)
811  if (IsSameColor(image,p,p+count) == MagickFalse)
812  break;
813  AssociateAlphaPixel(cube_info,p,&pixel);
814  index=MaxTreeDepth-1;
815  bisect=((MagickRealType) QuantumRange+1.0)/2.0;
816  mid=midpoint;
817  node_info=cube_info->root;
818  for (level=1; level <= MaxTreeDepth; level++)
819  {
820  double
821  distance;
822 
823  bisect*=0.5;
824  id=ColorToNodeId(cube_info,&pixel,index);
825  mid.red+=(id & 1) != 0 ? bisect : -bisect;
826  mid.green+=(id & 2) != 0 ? bisect : -bisect;
827  mid.blue+=(id & 4) != 0 ? bisect : -bisect;
828  mid.opacity+=(id & 8) != 0 ? bisect : -bisect;
829  if (node_info->child[id] == (NodeInfo *) NULL)
830  {
831  /*
832  Set colors of new node to contain pixel.
833  */
834  node_info->child[id]=GetNodeInfo(cube_info,id,level,node_info);
835  if (node_info->child[id] == (NodeInfo *) NULL)
836  {
837  (void) ThrowMagickException(exception,GetMagickModule(),
838  ResourceLimitError,"MemoryAllocationFailed","`%s'",
839  image->filename);
840  continue;
841  }
842  if (level == MaxTreeDepth)
843  cube_info->colors++;
844  }
845  /*
846  Approximate the quantization error represented by this node.
847  */
848  node_info=node_info->child[id];
849  error.red=QuantumScale*(pixel.red-mid.red);
850  error.green=QuantumScale*(pixel.green-mid.green);
851  error.blue=QuantumScale*(pixel.blue-mid.blue);
852  if (cube_info->associate_alpha != MagickFalse)
853  error.opacity=QuantumScale*(pixel.opacity-mid.opacity);
854  distance=(double) (error.red*error.red+error.green*error.green+
855  error.blue*error.blue+error.opacity*error.opacity);
856  if (IsNaN(distance) != 0)
857  distance=0.0;
858  node_info->quantize_error+=count*sqrt(distance);
859  cube_info->root->quantize_error+=node_info->quantize_error;
860  index--;
861  }
862  /*
863  Sum RGB for this leaf for later derivation of the mean cube color.
864  */
865  node_info->number_unique+=count;
866  node_info->total_color.red+=count*QuantumScale*(MagickRealType)
867  ClampPixel(pixel.red);
868  node_info->total_color.green+=count*QuantumScale*(MagickRealType)
869  ClampPixel(pixel.green);
870  node_info->total_color.blue+=count*QuantumScale*(MagickRealType)
871  ClampPixel(pixel.blue);
872  if (cube_info->associate_alpha != MagickFalse)
873  node_info->total_color.opacity+=count*QuantumScale*(MagickRealType)
874  ClampPixel(pixel.opacity);
875  else
876  node_info->total_color.opacity+=count*QuantumScale*(MagickRealType)
877  ClampPixel(OpaqueOpacity);
878  p+=count;
879  }
880  if (cube_info->colors > cube_info->maximum_colors)
881  {
882  PruneToCubeDepth(cube_info,cube_info->root);
883  break;
884  }
885  proceed=SetImageProgress(image,ClassifyImageTag,(MagickOffsetType) y,
886  image->rows);
887  if (proceed == MagickFalse)
888  break;
889  }
890  for (y++; y < (ssize_t) image->rows; y++)
891  {
892  const PixelPacket
893  *magick_restrict p;
894 
895  ssize_t
896  x;
897 
898  p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
899  if (p == (const PixelPacket *) NULL)
900  break;
901  if (cube_info->nodes > MaxNodes)
902  {
903  /*
904  Prune one level if the color tree is too large.
905  */
906  PruneLevel(cube_info,cube_info->root);
907  cube_info->depth--;
908  }
909  for (x=0; x < (ssize_t) image->columns; x+=(ssize_t) count)
910  {
911  /*
912  Start at the root and descend the color cube tree.
913  */
914  for (count=1; (x+(ssize_t) count) < (ssize_t) image->columns; count++)
915  if (IsSameColor(image,p,p+count) == MagickFalse)
916  break;
917  AssociateAlphaPixel(cube_info,p,&pixel);
918  index=MaxTreeDepth-1;
919  bisect=((MagickRealType) QuantumRange+1.0)/2.0;
920  mid=midpoint;
921  node_info=cube_info->root;
922  for (level=1; level <= cube_info->depth; level++)
923  {
924  double
925  distance;
926 
927  bisect*=0.5;
928  id=ColorToNodeId(cube_info,&pixel,index);
929  mid.red+=(id & 1) != 0 ? bisect : -bisect;
930  mid.green+=(id & 2) != 0 ? bisect : -bisect;
931  mid.blue+=(id & 4) != 0 ? bisect : -bisect;
932  mid.opacity+=(id & 8) != 0 ? bisect : -bisect;
933  if (node_info->child[id] == (NodeInfo *) NULL)
934  {
935  /*
936  Set colors of new node to contain pixel.
937  */
938  node_info->child[id]=GetNodeInfo(cube_info,id,level,node_info);
939  if (node_info->child[id] == (NodeInfo *) NULL)
940  {
941  (void) ThrowMagickException(exception,GetMagickModule(),
942  ResourceLimitError,"MemoryAllocationFailed","%s",
943  image->filename);
944  continue;
945  }
946  if (level == cube_info->depth)
947  cube_info->colors++;
948  }
949  /*
950  Approximate the quantization error represented by this node.
951  */
952  node_info=node_info->child[id];
953  error.red=QuantumScale*(pixel.red-mid.red);
954  error.green=QuantumScale*(pixel.green-mid.green);
955  error.blue=QuantumScale*(pixel.blue-mid.blue);
956  if (cube_info->associate_alpha != MagickFalse)
957  error.opacity=QuantumScale*(pixel.opacity-mid.opacity);
958  distance=(double) (error.red*error.red+error.green*error.green+
959  error.blue*error.blue+error.opacity*error.opacity);
960  if (IsNaN(distance) != 0)
961  distance=0.0;
962  node_info->quantize_error+=count*sqrt(distance);
963  cube_info->root->quantize_error+=node_info->quantize_error;
964  index--;
965  }
966  /*
967  Sum RGB for this leaf for later derivation of the mean cube color.
968  */
969  node_info->number_unique+=count;
970  node_info->total_color.red+=count*QuantumScale*(MagickRealType)
971  ClampPixel(pixel.red);
972  node_info->total_color.green+=count*QuantumScale*(MagickRealType)
973  ClampPixel(pixel.green);
974  node_info->total_color.blue+=count*QuantumScale*(MagickRealType)
975  ClampPixel(pixel.blue);
976  if (cube_info->associate_alpha != MagickFalse)
977  node_info->total_color.opacity+=count*QuantumScale*(MagickRealType)
978  ClampPixel(pixel.opacity);
979  else
980  node_info->total_color.opacity+=count*QuantumScale*(MagickRealType)
981  ClampPixel(OpaqueOpacity);
982  p+=count;
983  }
984  proceed=SetImageProgress(image,ClassifyImageTag,(MagickOffsetType) y,
985  image->rows);
986  if (proceed == MagickFalse)
987  break;
988  }
989  image_view=DestroyCacheView(image_view);
990  if (cube_info->quantize_info->colorspace != image->colorspace)
991  if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
992  (cube_info->quantize_info->colorspace != CMYKColorspace))
993  (void) TransformImageColorspace((Image *) image,sRGBColorspace);
994  return(y < (ssize_t) image->rows ? MagickFalse : MagickTrue);
995 }
996 
997 /*
998 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
999 % %
1000 % %
1001 % %
1002 % C l o n e Q u a n t i z e I n f o %
1003 % %
1004 % %
1005 % %
1006 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1007 %
1008 % CloneQuantizeInfo() makes a duplicate of the given quantize info structure,
1009 % or if quantize info is NULL, a new one.
1010 %
1011 % The format of the CloneQuantizeInfo method is:
1012 %
1013 % QuantizeInfo *CloneQuantizeInfo(const QuantizeInfo *quantize_info)
1014 %
1015 % A description of each parameter follows:
1016 %
1017 % o clone_info: Method CloneQuantizeInfo returns a duplicate of the given
1018 % quantize info, or if image info is NULL a new one.
1019 %
1020 % o quantize_info: a structure of type info.
1021 %
1022 */
1023 MagickExport QuantizeInfo *CloneQuantizeInfo(const QuantizeInfo *quantize_info)
1024 {
1025  QuantizeInfo
1026  *clone_info;
1027 
1028  clone_info=(QuantizeInfo *) AcquireMagickMemory(sizeof(*clone_info));
1029  if (clone_info == (QuantizeInfo *) NULL)
1030  ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
1031  GetQuantizeInfo(clone_info);
1032  if (quantize_info == (QuantizeInfo *) NULL)
1033  return(clone_info);
1034  clone_info->number_colors=quantize_info->number_colors;
1035  clone_info->tree_depth=quantize_info->tree_depth;
1036  clone_info->dither=quantize_info->dither;
1037  clone_info->dither_method=quantize_info->dither_method;
1038  clone_info->colorspace=quantize_info->colorspace;
1039  clone_info->measure_error=quantize_info->measure_error;
1040  return(clone_info);
1041 }
1042 
1043 /*
1044 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1045 % %
1046 % %
1047 % %
1048 + C l o s e s t C o l o r %
1049 % %
1050 % %
1051 % %
1052 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1053 %
1054 % ClosestColor() traverses the color cube tree at a particular node and
1055 % determines which colormap entry best represents the input color.
1056 %
1057 % The format of the ClosestColor method is:
1058 %
1059 % void ClosestColor(const Image *image,CubeInfo *cube_info,
1060 % const NodeInfo *node_info)
1061 %
1062 % A description of each parameter follows.
1063 %
1064 % o image: the image.
1065 %
1066 % o cube_info: A pointer to the Cube structure.
1067 %
1068 % o node_info: the address of a structure of type NodeInfo which points to a
1069 % node in the color cube tree that is to be pruned.
1070 %
1071 */
1072 static void ClosestColor(const Image *image,CubeInfo *cube_info,
1073  const NodeInfo *node_info)
1074 {
1075  ssize_t
1076  i;
1077 
1078  size_t
1079  number_children;
1080 
1081  /*
1082  Traverse any children.
1083  */
1084  number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
1085  for (i=0; i < (ssize_t) number_children; i++)
1086  if (node_info->child[i] != (NodeInfo *) NULL)
1087  ClosestColor(image,cube_info,node_info->child[i]);
1088  if (node_info->number_unique != 0)
1089  {
1090  MagickRealType
1091  alpha,
1092  beta,
1093  distance,
1094  pixel;
1095 
1097  *magick_restrict q;
1098 
1099  PixelPacket
1100  *magick_restrict p;
1101 
1102  /*
1103  Determine if this color is "closest".
1104  */
1105  p=image->colormap+node_info->color_number;
1106  q=(&cube_info->target);
1107  alpha=1.0;
1108  beta=1.0;
1109  if (cube_info->associate_alpha != MagickFalse)
1110  {
1111  alpha=(MagickRealType) QuantumScale*GetPixelAlpha(p);
1112  beta=(MagickRealType) QuantumScale*GetPixelAlpha(q);
1113  }
1114  pixel=alpha*GetPixelRed(p)-beta*GetPixelRed(q);
1115  distance=pixel*pixel;
1116  if (distance <= cube_info->distance)
1117  {
1118  pixel=(MagickRealType) alpha*GetPixelGreen(p)-beta*GetPixelGreen(q);
1119  distance+=pixel*pixel;
1120  if (distance <= cube_info->distance)
1121  {
1122  pixel=(MagickRealType) alpha*GetPixelBlue(p)-beta*GetPixelBlue(q);
1123  distance+=pixel*pixel;
1124  if (distance <= cube_info->distance)
1125  {
1126  if (cube_info->associate_alpha != MagickFalse)
1127  {
1128  pixel=(MagickRealType) GetPixelAlpha(p)-GetPixelAlpha(q);
1129  distance+=pixel*pixel;
1130  }
1131  if (distance <= cube_info->distance)
1132  {
1133  cube_info->distance=distance;
1134  cube_info->color_number=node_info->color_number;
1135  }
1136  }
1137  }
1138  }
1139  }
1140 }
1141 
1142 /*
1143 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1144 % %
1145 % %
1146 % %
1147 % C o m p r e s s I m a g e C o l o r m a p %
1148 % %
1149 % %
1150 % %
1151 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1152 %
1153 % CompressImageColormap() compresses an image colormap by removing any
1154 % duplicate or unused color entries.
1155 %
1156 % The format of the CompressImageColormap method is:
1157 %
1158 % MagickBooleanType CompressImageColormap(Image *image)
1159 %
1160 % A description of each parameter follows:
1161 %
1162 % o image: the image.
1163 %
1164 */
1165 MagickExport MagickBooleanType CompressImageColormap(Image *image)
1166 {
1167  QuantizeInfo
1168  quantize_info;
1169 
1170  assert(image != (Image *) NULL);
1171  assert(image->signature == MagickCoreSignature);
1172  if (IsEventLogging() != MagickFalse)
1173  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
1174  if (IsPaletteImage(image,&image->exception) == MagickFalse)
1175  return(MagickFalse);
1176  GetQuantizeInfo(&quantize_info);
1177  quantize_info.number_colors=image->colors;
1178  quantize_info.tree_depth=MaxTreeDepth;
1179  return(QuantizeImage(&quantize_info,image));
1180 }
1181 
1182 /*
1183 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1184 % %
1185 % %
1186 % %
1187 + D e f i n e I m a g e C o l o r m a p %
1188 % %
1189 % %
1190 % %
1191 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1192 %
1193 % DefineImageColormap() traverses the color cube tree and notes each colormap
1194 % entry. A colormap entry is any node in the color cube tree where the
1195 % of unique colors is not zero.
1196 %
1197 % The format of the DefineImageColormap method is:
1198 %
1199 % void DefineImageColormap(Image *image,CubeInfo *cube_info,
1200 % NodeInfo *node_info)
1201 %
1202 % A description of each parameter follows.
1203 %
1204 % o image: the image.
1205 %
1206 % o cube_info: A pointer to the Cube structure.
1207 %
1208 % o node_info: the address of a structure of type NodeInfo which points to a
1209 % node in the color cube tree that is to be pruned.
1210 %
1211 */
1212 static void DefineImageColormap(Image *image,CubeInfo *cube_info,
1213  NodeInfo *node_info)
1214 {
1215  size_t
1216  number_children;
1217 
1218  ssize_t
1219  i;
1220 
1221  /*
1222  Traverse any children.
1223  */
1224  number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
1225  for (i=0; i < (ssize_t) number_children; i++)
1226  if (node_info->child[i] != (NodeInfo *) NULL)
1227  DefineImageColormap(image,cube_info,node_info->child[i]);
1228  if (node_info->number_unique != 0)
1229  {
1230  MagickRealType
1231  alpha;
1232 
1233  PixelPacket
1234  *magick_restrict q;
1235 
1236  /*
1237  Colormap entry is defined by the mean color in this cube.
1238  */
1239  q=image->colormap+image->colors;
1240  alpha=(MagickRealType) ((MagickOffsetType) node_info->number_unique);
1241  alpha=PerceptibleReciprocal(alpha);
1242  if (cube_info->associate_alpha == MagickFalse)
1243  {
1244  SetPixelRed(q,ClampToQuantum(alpha*(MagickRealType) QuantumRange*
1245  node_info->total_color.red));
1246  SetPixelGreen(q,ClampToQuantum(alpha*(MagickRealType) QuantumRange*
1247  node_info->total_color.green));
1248  SetPixelBlue(q,ClampToQuantum(alpha*(MagickRealType) QuantumRange*
1249  node_info->total_color.blue));
1250  SetPixelOpacity(q,OpaqueOpacity);
1251  }
1252  else
1253  {
1254  MagickRealType
1255  opacity;
1256 
1257  opacity=(MagickRealType) (alpha*(MagickRealType) QuantumRange*
1258  node_info->total_color.opacity);
1259  SetPixelOpacity(q,ClampToQuantum(opacity));
1260  if (q->opacity == OpaqueOpacity)
1261  {
1262  SetPixelRed(q,ClampToQuantum(alpha*(MagickRealType)
1263  QuantumRange*node_info->total_color.red));
1264  SetPixelGreen(q,ClampToQuantum(alpha*(MagickRealType)
1265  QuantumRange*node_info->total_color.green));
1266  SetPixelBlue(q,ClampToQuantum(alpha*(MagickRealType)
1267  QuantumRange*node_info->total_color.blue));
1268  }
1269  else
1270  {
1271  double
1272  gamma;
1273 
1274  gamma=(double) (QuantumScale*((double) QuantumRange-(double)
1275  q->opacity));
1276  gamma=PerceptibleReciprocal(gamma);
1277  SetPixelRed(q,ClampToQuantum(alpha*gamma*(MagickRealType)
1278  QuantumRange*node_info->total_color.red));
1279  SetPixelGreen(q,ClampToQuantum(alpha*gamma*(MagickRealType)
1280  QuantumRange*node_info->total_color.green));
1281  SetPixelBlue(q,ClampToQuantum(alpha*gamma*(MagickRealType)
1282  QuantumRange*node_info->total_color.blue));
1283  if (node_info->number_unique > cube_info->transparent_pixels)
1284  {
1285  cube_info->transparent_pixels=node_info->number_unique;
1286  cube_info->transparent_index=(ssize_t) image->colors;
1287  }
1288  }
1289  }
1290  node_info->color_number=image->colors++;
1291  }
1292 }
1293 
1294 /*
1295 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1296 % %
1297 % %
1298 % %
1299 + D e s t r o y C u b e I n f o %
1300 % %
1301 % %
1302 % %
1303 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1304 %
1305 % DestroyCubeInfo() deallocates memory associated with an image.
1306 %
1307 % The format of the DestroyCubeInfo method is:
1308 %
1309 % DestroyCubeInfo(CubeInfo *cube_info)
1310 %
1311 % A description of each parameter follows:
1312 %
1313 % o cube_info: the address of a structure of type CubeInfo.
1314 %
1315 */
1316 static void DestroyCubeInfo(CubeInfo *cube_info)
1317 {
1318  Nodes
1319  *nodes;
1320 
1321  /*
1322  Release color cube tree storage.
1323  */
1324  do
1325  {
1326  nodes=cube_info->node_queue->next;
1327  cube_info->node_queue->nodes=(NodeInfo *) RelinquishMagickMemory(
1328  cube_info->node_queue->nodes);
1329  cube_info->node_queue=(Nodes *) RelinquishMagickMemory(
1330  cube_info->node_queue);
1331  cube_info->node_queue=nodes;
1332  } while (cube_info->node_queue != (Nodes *) NULL);
1333  if (cube_info->memory_info != (MemoryInfo *) NULL)
1334  cube_info->memory_info=RelinquishVirtualMemory(cube_info->memory_info);
1335  cube_info->quantize_info=DestroyQuantizeInfo(cube_info->quantize_info);
1336  cube_info=(CubeInfo *) RelinquishMagickMemory(cube_info);
1337 }
1338 
1339 /*
1340 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1341 % %
1342 % %
1343 % %
1344 % D e s t r o y Q u a n t i z e I n f o %
1345 % %
1346 % %
1347 % %
1348 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1349 %
1350 % DestroyQuantizeInfo() deallocates memory associated with an QuantizeInfo
1351 % structure.
1352 %
1353 % The format of the DestroyQuantizeInfo method is:
1354 %
1355 % QuantizeInfo *DestroyQuantizeInfo(QuantizeInfo *quantize_info)
1356 %
1357 % A description of each parameter follows:
1358 %
1359 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
1360 %
1361 */
1362 MagickExport QuantizeInfo *DestroyQuantizeInfo(QuantizeInfo *quantize_info)
1363 {
1364  assert(quantize_info != (QuantizeInfo *) NULL);
1365  assert(quantize_info->signature == MagickCoreSignature);
1366  if (IsEventLogging() != MagickFalse)
1367  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
1368  quantize_info->signature=(~MagickCoreSignature);
1369  quantize_info=(QuantizeInfo *) RelinquishMagickMemory(quantize_info);
1370  return(quantize_info);
1371 }
1372 
1373 /*
1374 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1375 % %
1376 % %
1377 % %
1378 + D i t h e r I m a g e %
1379 % %
1380 % %
1381 % %
1382 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1383 %
1384 % DitherImage() distributes the difference between an original image and
1385 % the corresponding color reduced algorithm to neighboring pixels using
1386 % serpentine-scan Floyd-Steinberg error diffusion. DitherImage returns
1387 % MagickTrue if the image is dithered otherwise MagickFalse.
1388 %
1389 % The format of the DitherImage method is:
1390 %
1391 % MagickBooleanType DitherImage(Image *image,CubeInfo *cube_info)
1392 %
1393 % A description of each parameter follows.
1394 %
1395 % o image: the image.
1396 %
1397 % o cube_info: A pointer to the Cube structure.
1398 %
1399 */
1400 
1401 static DoublePixelPacket **DestroyPixelTLS(DoublePixelPacket **pixels)
1402 {
1403  ssize_t
1404  i;
1405 
1406  assert(pixels != (DoublePixelPacket **) NULL);
1407  for (i=0; i < (ssize_t) GetMagickResourceLimit(ThreadResource); i++)
1408  if (pixels[i] != (DoublePixelPacket *) NULL)
1409  pixels[i]=(DoublePixelPacket *) RelinquishMagickMemory(pixels[i]);
1410  pixels=(DoublePixelPacket **) RelinquishMagickMemory(pixels);
1411  return(pixels);
1412 }
1413 
1414 static DoublePixelPacket **AcquirePixelTLS(const size_t count)
1415 {
1417  **pixels;
1418 
1419  size_t
1420  number_threads;
1421 
1422  ssize_t
1423  i;
1424 
1425  number_threads=(size_t) GetMagickResourceLimit(ThreadResource);
1426  pixels=(DoublePixelPacket **) AcquireQuantumMemory(number_threads,
1427  sizeof(*pixels));
1428  if (pixels == (DoublePixelPacket **) NULL)
1429  return((DoublePixelPacket **) NULL);
1430  (void) memset(pixels,0,number_threads*sizeof(*pixels));
1431  for (i=0; i < (ssize_t) number_threads; i++)
1432  {
1433  pixels[i]=(DoublePixelPacket *) AcquireQuantumMemory(count,
1434  2*sizeof(**pixels));
1435  if (pixels[i] == (DoublePixelPacket *) NULL)
1436  return(DestroyPixelTLS(pixels));
1437  }
1438  return(pixels);
1439 }
1440 
1441 static inline ssize_t CacheOffset(CubeInfo *cube_info,
1442  const DoublePixelPacket *pixel)
1443 {
1444 #define RedShift(pixel) (((pixel) >> CacheShift) << (0*(8-CacheShift)))
1445 #define GreenShift(pixel) (((pixel) >> CacheShift) << (1*(8-CacheShift)))
1446 #define BlueShift(pixel) (((pixel) >> CacheShift) << (2*(8-CacheShift)))
1447 #define AlphaShift(pixel) (((pixel) >> CacheShift) << (3*(8-CacheShift)))
1448 
1449  ssize_t
1450  offset;
1451 
1452  offset=(ssize_t) (RedShift(ScaleQuantumToChar(ClampPixel(pixel->red))) |
1453  GreenShift(ScaleQuantumToChar(ClampPixel(pixel->green))) |
1454  BlueShift(ScaleQuantumToChar(ClampPixel(pixel->blue))));
1455  if (cube_info->associate_alpha != MagickFalse)
1456  offset|=AlphaShift(ScaleQuantumToChar(ClampPixel(pixel->opacity)));
1457  return(offset);
1458 }
1459 
1460 static MagickBooleanType FloydSteinbergDither(Image *image,CubeInfo *cube_info)
1461 {
1462 #define DitherImageTag "Dither/Image"
1463 
1464  CacheView
1465  *image_view;
1466 
1468  **pixels;
1469 
1471  *exception;
1472 
1473  MagickBooleanType
1474  status;
1475 
1476  ssize_t
1477  y;
1478 
1479  /*
1480  Distribute quantization error using Floyd-Steinberg.
1481  */
1482  pixels=AcquirePixelTLS(image->columns);
1483  if (pixels == (DoublePixelPacket **) NULL)
1484  return(MagickFalse);
1485  exception=(&image->exception);
1486  status=MagickTrue;
1487  image_view=AcquireAuthenticCacheView(image,exception);
1488  for (y=0; y < (ssize_t) image->rows; y++)
1489  {
1490  const int
1491  id = GetOpenMPThreadId();
1492 
1493  CubeInfo
1494  cube;
1495 
1497  *current,
1498  *previous;
1499 
1500  IndexPacket
1501  *magick_restrict indexes;
1502 
1503  PixelPacket
1504  *magick_restrict q;
1505 
1506  size_t
1507  index;
1508 
1509  ssize_t
1510  x,
1511  v;
1512 
1513  if (status == MagickFalse)
1514  continue;
1515  q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
1516  if (q == (PixelPacket *) NULL)
1517  {
1518  status=MagickFalse;
1519  continue;
1520  }
1521  indexes=GetCacheViewAuthenticIndexQueue(image_view);
1522  cube=(*cube_info);
1523  current=pixels[id]+(y & 0x01)*image->columns;
1524  previous=pixels[id]+((y+1) & 0x01)*image->columns;
1525  v=(ssize_t) ((y & 0x01) ? -1 : 1);
1526  for (x=0; x < (ssize_t) image->columns; x++)
1527  {
1529  color,
1530  pixel;
1531 
1532  ssize_t
1533  i;
1534 
1535  ssize_t
1536  u;
1537 
1538  u=(y & 0x01) ? (ssize_t) image->columns-1-x : x;
1539  AssociateAlphaPixel(&cube,q+u,&pixel);
1540  if (x > 0)
1541  {
1542  pixel.red+=7.0*cube_info->diffusion*current[u-v].red/16;
1543  pixel.green+=7.0*cube_info->diffusion*current[u-v].green/16;
1544  pixel.blue+=7.0*cube_info->diffusion*current[u-v].blue/16;
1545  if (cube.associate_alpha != MagickFalse)
1546  pixel.opacity+=7.0*cube_info->diffusion*current[u-v].opacity/16;
1547  }
1548  if (y > 0)
1549  {
1550  if (x < (ssize_t) (image->columns-1))
1551  {
1552  pixel.red+=cube_info->diffusion*previous[u+v].red/16;
1553  pixel.green+=cube_info->diffusion*previous[u+v].green/16;
1554  pixel.blue+=cube_info->diffusion*previous[u+v].blue/16;
1555  if (cube.associate_alpha != MagickFalse)
1556  pixel.opacity+=cube_info->diffusion*previous[u+v].opacity/16;
1557  }
1558  pixel.red+=5.0*cube_info->diffusion*previous[u].red/16;
1559  pixel.green+=5.0*cube_info->diffusion*previous[u].green/16;
1560  pixel.blue+=5.0*cube_info->diffusion*previous[u].blue/16;
1561  if (cube.associate_alpha != MagickFalse)
1562  pixel.opacity+=5.0*cube_info->diffusion*previous[u].opacity/16;
1563  if (x > 0)
1564  {
1565  pixel.red+=3.0*cube_info->diffusion*previous[u-v].red/16;
1566  pixel.green+=3.0*cube_info->diffusion*previous[u-v].green/16;
1567  pixel.blue+=3.0*cube_info->diffusion*previous[u-v].blue/16;
1568  if (cube.associate_alpha != MagickFalse)
1569  pixel.opacity+=3.0*cube_info->diffusion*
1570  previous[u-v].opacity/16;
1571  }
1572  }
1573  pixel.red=(MagickRealType) ClampPixel(pixel.red);
1574  pixel.green=(MagickRealType) ClampPixel(pixel.green);
1575  pixel.blue=(MagickRealType) ClampPixel(pixel.blue);
1576  if (cube.associate_alpha != MagickFalse)
1577  pixel.opacity=(MagickRealType) ClampPixel(pixel.opacity);
1578  i=CacheOffset(&cube,&pixel);
1579  if (cube.cache[i] < 0)
1580  {
1581  NodeInfo
1582  *node_info;
1583 
1584  size_t
1585  id;
1586 
1587  /*
1588  Identify the deepest node containing the pixel's color.
1589  */
1590  node_info=cube.root;
1591  for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
1592  {
1593  id=ColorToNodeId(&cube,&pixel,index);
1594  if (node_info->child[id] == (NodeInfo *) NULL)
1595  break;
1596  node_info=node_info->child[id];
1597  }
1598  /*
1599  Find closest color among siblings and their children.
1600  */
1601  cube.target=pixel;
1602  cube.distance=(MagickRealType) (4.0*((MagickRealType) QuantumRange+
1603  1.0)*((MagickRealType) QuantumRange+1.0)+1.0);
1604  ClosestColor(image,&cube,node_info->parent);
1605  cube.cache[i]=(ssize_t) cube.color_number;
1606  }
1607  /*
1608  Assign pixel to closest colormap entry.
1609  */
1610  index=(size_t) cube.cache[i];
1611  if (image->storage_class == PseudoClass)
1612  SetPixelIndex(indexes+u,index);
1613  if (cube.quantize_info->measure_error == MagickFalse)
1614  {
1615  SetPixelRgb(q+u,image->colormap+index);
1616  if (cube.associate_alpha != MagickFalse)
1617  SetPixelOpacity(q+u,image->colormap[index].opacity);
1618  }
1619  if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
1620  status=MagickFalse;
1621  /*
1622  Store the error.
1623  */
1624  AssociateAlphaPixel(&cube,image->colormap+index,&color);
1625  current[u].red=pixel.red-color.red;
1626  current[u].green=pixel.green-color.green;
1627  current[u].blue=pixel.blue-color.blue;
1628  if (cube.associate_alpha != MagickFalse)
1629  current[u].opacity=pixel.opacity-color.opacity;
1630  if (image->progress_monitor != (MagickProgressMonitor) NULL)
1631  {
1632  MagickBooleanType
1633  proceed;
1634 
1635  proceed=SetImageProgress(image,DitherImageTag,(MagickOffsetType) y,
1636  image->rows);
1637  if (proceed == MagickFalse)
1638  status=MagickFalse;
1639  }
1640  }
1641  }
1642  image_view=DestroyCacheView(image_view);
1643  pixels=DestroyPixelTLS(pixels);
1644  return(MagickTrue);
1645 }
1646 
1647 static MagickBooleanType
1648  RiemersmaDither(Image *,CacheView *,CubeInfo *,const unsigned int);
1649 
1650 static MagickBooleanType Riemersma(Image *image,CacheView *image_view,
1651  CubeInfo *cube_info,const size_t level,const unsigned int direction)
1652 {
1653  MagickStatusType
1654  status;
1655 
1656  status=MagickTrue;
1657  if (level == 1)
1658  switch (direction)
1659  {
1660  case WestGravity:
1661  {
1662  status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1663  if (status != MagickFalse)
1664  status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1665  if (status != MagickFalse)
1666  status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1667  break;
1668  }
1669  case EastGravity:
1670  {
1671  status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1672  if (status != MagickFalse)
1673  status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1674  if (status != MagickFalse)
1675  status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1676  break;
1677  }
1678  case NorthGravity:
1679  {
1680  status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1681  if (status != MagickFalse)
1682  status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1683  if (status != MagickFalse)
1684  status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1685  break;
1686  }
1687  case SouthGravity:
1688  {
1689  status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1690  if (status != MagickFalse)
1691  status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1692  if (status != MagickFalse)
1693  status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1694  break;
1695  }
1696  default:
1697  break;
1698  }
1699  else
1700  switch (direction)
1701  {
1702  case WestGravity:
1703  {
1704  status=Riemersma(image,image_view,cube_info,level-1,NorthGravity);
1705  if (status != MagickFalse)
1706  status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1707  if (status != MagickFalse)
1708  status=Riemersma(image,image_view,cube_info,level-1,WestGravity);
1709  if (status != MagickFalse)
1710  status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1711  if (status != MagickFalse)
1712  status=Riemersma(image,image_view,cube_info,level-1,WestGravity);
1713  if (status != MagickFalse)
1714  status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1715  if (status != MagickFalse)
1716  status=Riemersma(image,image_view,cube_info,level-1,SouthGravity);
1717  break;
1718  }
1719  case EastGravity:
1720  {
1721  status=Riemersma(image,image_view,cube_info,level-1,SouthGravity);
1722  if (status != MagickFalse)
1723  status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1724  if (status != MagickFalse)
1725  status=Riemersma(image,image_view,cube_info,level-1,EastGravity);
1726  if (status != MagickFalse)
1727  status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1728  if (status != MagickFalse)
1729  status=Riemersma(image,image_view,cube_info,level-1,EastGravity);
1730  if (status != MagickFalse)
1731  status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1732  if (status != MagickFalse)
1733  status=Riemersma(image,image_view,cube_info,level-1,NorthGravity);
1734  break;
1735  }
1736  case NorthGravity:
1737  {
1738  status=Riemersma(image,image_view,cube_info,level-1,WestGravity);
1739  if (status != MagickFalse)
1740  status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1741  if (status != MagickFalse)
1742  status=Riemersma(image,image_view,cube_info,level-1,NorthGravity);
1743  if (status != MagickFalse)
1744  status=RiemersmaDither(image,image_view,cube_info,EastGravity);
1745  if (status != MagickFalse)
1746  status=Riemersma(image,image_view,cube_info,level-1,NorthGravity);
1747  if (status != MagickFalse)
1748  status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1749  if (status != MagickFalse)
1750  status=Riemersma(image,image_view,cube_info,level-1,EastGravity);
1751  break;
1752  }
1753  case SouthGravity:
1754  {
1755  status=Riemersma(image,image_view,cube_info,level-1,EastGravity);
1756  if (status != MagickFalse)
1757  status=RiemersmaDither(image,image_view,cube_info,NorthGravity);
1758  if (status != MagickFalse)
1759  status=Riemersma(image,image_view,cube_info,level-1,SouthGravity);
1760  if (status != MagickFalse)
1761  status=RiemersmaDither(image,image_view,cube_info,WestGravity);
1762  if (status != MagickFalse)
1763  status=Riemersma(image,image_view,cube_info,level-1,SouthGravity);
1764  if (status != MagickFalse)
1765  status=RiemersmaDither(image,image_view,cube_info,SouthGravity);
1766  if (status != MagickFalse)
1767  status=Riemersma(image,image_view,cube_info,level-1,WestGravity);
1768  break;
1769  }
1770  default:
1771  break;
1772  }
1773  return(status != 0 ? MagickTrue : MagickFalse);
1774 }
1775 
1776 static MagickBooleanType RiemersmaDither(Image *image,CacheView *image_view,
1777  CubeInfo *cube_info,const unsigned int direction)
1778 {
1779 #define DitherImageTag "Dither/Image"
1780 
1781  CubeInfo
1782  *p;
1783 
1785  color,
1786  pixel;
1787 
1788  MagickBooleanType
1789  proceed;
1790 
1791  size_t
1792  index;
1793 
1794  p=cube_info;
1795  if ((p->x >= 0) && (p->x < (ssize_t) image->columns) &&
1796  (p->y >= 0) && (p->y < (ssize_t) image->rows))
1797  {
1799  *exception;
1800 
1801  IndexPacket
1802  *magick_restrict indexes;
1803 
1804  PixelPacket
1805  *magick_restrict q;
1806 
1807  ssize_t
1808  i;
1809 
1810  /*
1811  Distribute error.
1812  */
1813  exception=(&image->exception);
1814  q=GetCacheViewAuthenticPixels(image_view,p->x,p->y,1,1,exception);
1815  if (q == (PixelPacket *) NULL)
1816  return(MagickFalse);
1817  indexes=GetCacheViewAuthenticIndexQueue(image_view);
1818  AssociateAlphaPixel(cube_info,q,&pixel);
1819  for (i=0; i < ErrorQueueLength; i++)
1820  {
1821  pixel.red+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1822  p->error[i].red;
1823  pixel.green+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1824  p->error[i].green;
1825  pixel.blue+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1826  p->error[i].blue;
1827  if (cube_info->associate_alpha != MagickFalse)
1828  pixel.opacity+=ErrorRelativeWeight*cube_info->diffusion*p->weights[i]*
1829  p->error[i].opacity;
1830  }
1831  pixel.red=(MagickRealType) ClampPixel(pixel.red);
1832  pixel.green=(MagickRealType) ClampPixel(pixel.green);
1833  pixel.blue=(MagickRealType) ClampPixel(pixel.blue);
1834  if (cube_info->associate_alpha != MagickFalse)
1835  pixel.opacity=(MagickRealType) ClampPixel(pixel.opacity);
1836  i=CacheOffset(cube_info,&pixel);
1837  if (p->cache[i] < 0)
1838  {
1839  NodeInfo
1840  *node_info;
1841 
1842  size_t
1843  id;
1844 
1845  /*
1846  Identify the deepest node containing the pixel's color.
1847  */
1848  node_info=p->root;
1849  for (index=MaxTreeDepth-1; (ssize_t) index > 0; index--)
1850  {
1851  id=ColorToNodeId(cube_info,&pixel,index);
1852  if (node_info->child[id] == (NodeInfo *) NULL)
1853  break;
1854  node_info=node_info->child[id];
1855  }
1856  /*
1857  Find closest color among siblings and their children.
1858  */
1859  p->target=pixel;
1860  p->distance=(MagickRealType) (4.0*((MagickRealType) QuantumRange+
1861  1.0)*((MagickRealType) QuantumRange+1.0)+1.0);
1862  ClosestColor(image,p,node_info->parent);
1863  p->cache[i]=(ssize_t) p->color_number;
1864  }
1865  /*
1866  Assign pixel to closest colormap entry.
1867  */
1868  index=(size_t) (1*p->cache[i]);
1869  if (image->storage_class == PseudoClass)
1870  *indexes=(IndexPacket) index;
1871  if (cube_info->quantize_info->measure_error == MagickFalse)
1872  {
1873  SetPixelRgb(q,image->colormap+index);
1874  if (cube_info->associate_alpha != MagickFalse)
1875  SetPixelOpacity(q,image->colormap[index].opacity);
1876  }
1877  if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
1878  return(MagickFalse);
1879  /*
1880  Propagate the error as the last entry of the error queue.
1881  */
1882  (void) memmove(p->error,p->error+1,(ErrorQueueLength-1)*
1883  sizeof(p->error[0]));
1884  AssociateAlphaPixel(cube_info,image->colormap+index,&color);
1885  p->error[ErrorQueueLength-1].red=pixel.red-color.red;
1886  p->error[ErrorQueueLength-1].green=pixel.green-color.green;
1887  p->error[ErrorQueueLength-1].blue=pixel.blue-color.blue;
1888  if (cube_info->associate_alpha != MagickFalse)
1889  p->error[ErrorQueueLength-1].opacity=pixel.opacity-color.opacity;
1890  proceed=SetImageProgress(image,DitherImageTag,p->offset,p->span);
1891  if (proceed == MagickFalse)
1892  return(MagickFalse);
1893  p->offset++;
1894  }
1895  switch (direction)
1896  {
1897  case WestGravity: p->x--; break;
1898  case EastGravity: p->x++; break;
1899  case NorthGravity: p->y--; break;
1900  case SouthGravity: p->y++; break;
1901  }
1902  return(MagickTrue);
1903 }
1904 
1905 static MagickBooleanType DitherImage(Image *image,CubeInfo *cube_info)
1906 {
1907  CacheView
1908  *image_view;
1909 
1910  const char
1911  *artifact;
1912 
1913  MagickBooleanType
1914  status;
1915 
1916  size_t
1917  extent,
1918  level;
1919 
1920  artifact=GetImageArtifact(image,"dither:diffusion-amount");
1921  if (artifact != (const char *) NULL)
1922  cube_info->diffusion=StringToDoubleInterval(artifact,1.0);
1923  if (cube_info->quantize_info->dither_method != RiemersmaDitherMethod)
1924  return(FloydSteinbergDither(image,cube_info));
1925  /*
1926  Distribute quantization error along a Hilbert curve.
1927  */
1928  (void) memset(cube_info->error,0,ErrorQueueLength*sizeof(*cube_info->error));
1929  cube_info->x=0;
1930  cube_info->y=0;
1931  extent=MagickMax(image->columns,image->rows);
1932  level=(size_t) log2((double) extent);
1933  if ((1UL << level) < extent)
1934  level++;
1935  cube_info->offset=0;
1936  cube_info->span=(MagickSizeType) image->columns*image->rows;
1937  image_view=AcquireAuthenticCacheView(image,&image->exception);
1938  status=MagickTrue;
1939  if (level > 0)
1940  status=Riemersma(image,image_view,cube_info,level,NorthGravity);
1941  if (status != MagickFalse)
1942  status=RiemersmaDither(image,image_view,cube_info,ForgetGravity);
1943  image_view=DestroyCacheView(image_view);
1944  return(status);
1945 }
1946 
1947 /*
1948 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1949 % %
1950 % %
1951 % %
1952 + G e t C u b e I n f o %
1953 % %
1954 % %
1955 % %
1956 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1957 %
1958 % GetCubeInfo() initialize the Cube data structure.
1959 %
1960 % The format of the GetCubeInfo method is:
1961 %
1962 % CubeInfo GetCubeInfo(const QuantizeInfo *quantize_info,
1963 % const size_t depth,const size_t maximum_colors)
1964 %
1965 % A description of each parameter follows.
1966 %
1967 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
1968 %
1969 % o depth: Normally, this integer value is zero or one. A zero or
1970 % one tells Quantize to choose a optimal tree depth of Log4(number_colors).
1971 % A tree of this depth generally allows the best representation of the
1972 % reference image with the least amount of memory and the fastest
1973 % computational speed. In some cases, such as an image with low color
1974 % dispersion (a few number of colors), a value other than
1975 % Log4(number_colors) is required. To expand the color tree completely,
1976 % use a value of 8.
1977 %
1978 % o maximum_colors: maximum colors.
1979 %
1980 */
1981 static CubeInfo *GetCubeInfo(const QuantizeInfo *quantize_info,
1982  const size_t depth,const size_t maximum_colors)
1983 {
1984  CubeInfo
1985  *cube_info;
1986 
1987  MagickRealType
1988  weight;
1989 
1990  size_t
1991  length;
1992 
1993  ssize_t
1994  i;
1995 
1996  /*
1997  Initialize tree to describe color cube_info.
1998  */
1999  cube_info=(CubeInfo *) AcquireMagickMemory(sizeof(*cube_info));
2000  if (cube_info == (CubeInfo *) NULL)
2001  return((CubeInfo *) NULL);
2002  (void) memset(cube_info,0,sizeof(*cube_info));
2003  cube_info->depth=depth;
2004  if (cube_info->depth > MaxTreeDepth)
2005  cube_info->depth=MaxTreeDepth;
2006  if (cube_info->depth < 2)
2007  cube_info->depth=2;
2008  cube_info->maximum_colors=maximum_colors;
2009  /*
2010  Initialize root node.
2011  */
2012  cube_info->root=GetNodeInfo(cube_info,0,0,(NodeInfo *) NULL);
2013  if (cube_info->root == (NodeInfo *) NULL)
2014  return((CubeInfo *) NULL);
2015  cube_info->root->parent=cube_info->root;
2016  cube_info->quantize_info=CloneQuantizeInfo(quantize_info);
2017  if (cube_info->quantize_info->dither == MagickFalse)
2018  return(cube_info);
2019  /*
2020  Initialize dither resources.
2021  */
2022  length=(size_t) (1UL << (4*(8-CacheShift)));
2023  cube_info->memory_info=AcquireVirtualMemory(length,sizeof(*cube_info->cache));
2024  if (cube_info->memory_info == (MemoryInfo *) NULL)
2025  return((CubeInfo *) NULL);
2026  cube_info->cache=(ssize_t *) GetVirtualMemoryBlob(cube_info->memory_info);
2027  /*
2028  Initialize color cache.
2029  */
2030  (void) memset(cube_info->cache,(-1),sizeof(*cube_info->cache)*length);
2031  /*
2032  Distribute weights along a curve of exponential decay.
2033  */
2034  weight=1.0;
2035  for (i=0; i < ErrorQueueLength; i++)
2036  {
2037  cube_info->weights[i]=PerceptibleReciprocal(weight);
2038  weight*=exp(log(1.0/ErrorRelativeWeight)/(ErrorQueueLength-1.0));
2039  }
2040  cube_info->diffusion=1.0;
2041  return(cube_info);
2042 }
2043 
2044 /*
2045 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2046 % %
2047 % %
2048 % %
2049 + G e t N o d e I n f o %
2050 % %
2051 % %
2052 % %
2053 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2054 %
2055 % GetNodeInfo() allocates memory for a new node in the color cube tree and
2056 % presets all fields to zero.
2057 %
2058 % The format of the GetNodeInfo method is:
2059 %
2060 % NodeInfo *GetNodeInfo(CubeInfo *cube_info,const size_t id,
2061 % const size_t level,NodeInfo *parent)
2062 %
2063 % A description of each parameter follows.
2064 %
2065 % o node: The GetNodeInfo method returns a pointer to a queue of nodes.
2066 %
2067 % o id: Specifies the child number of the node.
2068 %
2069 % o level: Specifies the level in the storage_class the node resides.
2070 %
2071 */
2072 static NodeInfo *GetNodeInfo(CubeInfo *cube_info,const size_t id,
2073  const size_t level,NodeInfo *parent)
2074 {
2075  NodeInfo
2076  *node_info;
2077 
2078  if (cube_info->free_nodes == 0)
2079  {
2080  Nodes
2081  *nodes;
2082 
2083  /*
2084  Allocate a new queue of nodes.
2085  */
2086  nodes=(Nodes *) AcquireMagickMemory(sizeof(*nodes));
2087  if (nodes == (Nodes *) NULL)
2088  return((NodeInfo *) NULL);
2089  nodes->nodes=(NodeInfo *) AcquireQuantumMemory(NodesInAList,
2090  sizeof(*nodes->nodes));
2091  if (nodes->nodes == (NodeInfo *) NULL)
2092  return((NodeInfo *) NULL);
2093  nodes->next=cube_info->node_queue;
2094  cube_info->node_queue=nodes;
2095  cube_info->next_node=nodes->nodes;
2096  cube_info->free_nodes=NodesInAList;
2097  }
2098  cube_info->nodes++;
2099  cube_info->free_nodes--;
2100  node_info=cube_info->next_node++;
2101  (void) memset(node_info,0,sizeof(*node_info));
2102  node_info->parent=parent;
2103  node_info->id=id;
2104  node_info->level=level;
2105  return(node_info);
2106 }
2107 
2108 /*
2109 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2110 % %
2111 % %
2112 % %
2113 % G e t I m a g e Q u a n t i z e E r r o r %
2114 % %
2115 % %
2116 % %
2117 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2118 %
2119 % GetImageQuantizeError() measures the difference between the original
2120 % and quantized images. This difference is the total quantization error.
2121 % The error is computed by summing over all pixels in an image the distance
2122 % squared in RGB space between each reference pixel value and its quantized
2123 % value. These values are computed:
2124 %
2125 % o mean_error_per_pixel: This value is the mean error for any single
2126 % pixel in the image.
2127 %
2128 % o normalized_mean_square_error: This value is the normalized mean
2129 % quantization error for any single pixel in the image. This distance
2130 % measure is normalized to a range between 0 and 1. It is independent
2131 % of the range of red, green, and blue values in the image.
2132 %
2133 % o normalized_maximum_square_error: This value is the normalized
2134 % maximum quantization error for any single pixel in the image. This
2135 % distance measure is normalized to a range between 0 and 1. It is
2136 % independent of the range of red, green, and blue values in your image.
2137 %
2138 % The format of the GetImageQuantizeError method is:
2139 %
2140 % MagickBooleanType GetImageQuantizeError(Image *image)
2141 %
2142 % A description of each parameter follows.
2143 %
2144 % o image: the image.
2145 %
2146 */
2147 MagickExport MagickBooleanType GetImageQuantizeError(Image *image)
2148 {
2149  CacheView
2150  *image_view;
2151 
2153  *exception;
2154 
2155  IndexPacket
2156  *indexes;
2157 
2158  MagickRealType
2159  alpha,
2160  area,
2161  beta,
2162  distance,
2163  gamma,
2164  maximum_error,
2165  mean_error,
2166  mean_error_per_pixel;
2167 
2168  ssize_t
2169  index,
2170  y;
2171 
2172  assert(image != (Image *) NULL);
2173  assert(image->signature == MagickCoreSignature);
2174  if (IsEventLogging() != MagickFalse)
2175  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
2176  image->total_colors=GetNumberColors(image,(FILE *) NULL,&image->exception);
2177  (void) memset(&image->error,0,sizeof(image->error));
2178  if (image->storage_class == DirectClass)
2179  return(MagickTrue);
2180  alpha=1.0;
2181  beta=1.0;
2182  area=3.0*image->columns*image->rows;
2183  maximum_error=0.0;
2184  mean_error_per_pixel=0.0;
2185  mean_error=0.0;
2186  exception=(&image->exception);
2187  image_view=AcquireVirtualCacheView(image,exception);
2188  for (y=0; y < (ssize_t) image->rows; y++)
2189  {
2190  const PixelPacket
2191  *magick_restrict p;
2192 
2193  ssize_t
2194  x;
2195 
2196  p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
2197  if (p == (const PixelPacket *) NULL)
2198  break;
2199  indexes=GetCacheViewAuthenticIndexQueue(image_view);
2200  for (x=0; x < (ssize_t) image->columns; x++)
2201  {
2202  index=(ssize_t) GetPixelIndex(indexes+x);
2203  if (image->matte != MagickFalse)
2204  {
2205  alpha=QuantumScale*(MagickRealType) GetPixelAlpha(p);
2206  beta=QuantumScale*((MagickRealType) QuantumRange-
2207  (MagickRealType) image->colormap[index].opacity);
2208  }
2209  distance=fabs((double) (alpha*(MagickRealType) GetPixelRed(p)-beta*
2210  (MagickRealType) image->colormap[index].red));
2211  mean_error_per_pixel+=distance;
2212  mean_error+=distance*distance;
2213  if (distance > maximum_error)
2214  maximum_error=distance;
2215  distance=fabs((double) (alpha*(MagickRealType) GetPixelGreen(p)-beta*
2216  (MagickRealType) image->colormap[index].green));
2217  mean_error_per_pixel+=distance;
2218  mean_error+=distance*distance;
2219  if (distance > maximum_error)
2220  maximum_error=distance;
2221  distance=fabs((double) (alpha*(MagickRealType) GetPixelBlue(p)-beta*
2222  (MagickRealType) image->colormap[index].blue));
2223  mean_error_per_pixel+=distance;
2224  mean_error+=distance*distance;
2225  if (distance > maximum_error)
2226  maximum_error=distance;
2227  p++;
2228  }
2229  }
2230  image_view=DestroyCacheView(image_view);
2231  gamma=PerceptibleReciprocal(area);
2232  image->error.mean_error_per_pixel=gamma*mean_error_per_pixel;
2233  image->error.normalized_mean_error=gamma*QuantumScale*QuantumScale*mean_error;
2234  image->error.normalized_maximum_error=QuantumScale*maximum_error;
2235  return(MagickTrue);
2236 }
2237 
2238 /*
2239 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2240 % %
2241 % %
2242 % %
2243 % G e t Q u a n t i z e I n f o %
2244 % %
2245 % %
2246 % %
2247 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2248 %
2249 % GetQuantizeInfo() initializes the QuantizeInfo structure.
2250 %
2251 % The format of the GetQuantizeInfo method is:
2252 %
2253 % GetQuantizeInfo(QuantizeInfo *quantize_info)
2254 %
2255 % A description of each parameter follows:
2256 %
2257 % o quantize_info: Specifies a pointer to a QuantizeInfo structure.
2258 %
2259 */
2260 MagickExport void GetQuantizeInfo(QuantizeInfo *quantize_info)
2261 {
2262  assert(quantize_info != (QuantizeInfo *) NULL);
2263  if (IsEventLogging() != MagickFalse)
2264  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
2265  (void) memset(quantize_info,0,sizeof(*quantize_info));
2266  quantize_info->number_colors=256;
2267  quantize_info->dither=MagickTrue;
2268  quantize_info->dither_method=RiemersmaDitherMethod;
2269  quantize_info->colorspace=UndefinedColorspace;
2270  quantize_info->measure_error=MagickFalse;
2271  quantize_info->signature=MagickCoreSignature;
2272 }
2273 
2274 /*
2275 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2276 % %
2277 % %
2278 % %
2279 % P o s t e r i z e I m a g e C h a n n e l %
2280 % %
2281 % %
2282 % %
2283 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2284 %
2285 % PosterizeImage() reduces the image to a limited number of colors for a
2286 % "poster" effect.
2287 %
2288 % The format of the PosterizeImage method is:
2289 %
2290 % MagickBooleanType PosterizeImage(Image *image,const size_t levels,
2291 % const MagickBooleanType dither)
2292 % MagickBooleanType PosterizeImageChannel(Image *image,
2293 % const ChannelType channel,const size_t levels,
2294 % const MagickBooleanType dither)
2295 %
2296 % A description of each parameter follows:
2297 %
2298 % o image: Specifies a pointer to an Image structure.
2299 %
2300 % o levels: Number of color levels allowed in each channel. Very low values
2301 % (2, 3, or 4) have the most visible effect.
2302 %
2303 % o dither: Set this integer value to something other than zero to dither
2304 % the mapped image.
2305 %
2306 */
2307 
2308 static inline double MagickRound(double x)
2309 {
2310  /*
2311  Round the fraction to nearest integer.
2312  */
2313  if ((x-floor(x)) < (ceil(x)-x))
2314  return(floor(x));
2315  return(ceil(x));
2316 }
2317 
2318 MagickExport MagickBooleanType PosterizeImage(Image *image,const size_t levels,
2319  const MagickBooleanType dither)
2320 {
2321  MagickBooleanType
2322  status;
2323 
2324  status=PosterizeImageChannel(image,DefaultChannels,levels,dither);
2325  return(status);
2326 }
2327 
2328 MagickExport MagickBooleanType PosterizeImageChannel(Image *image,
2329  const ChannelType channel,const size_t levels,const MagickBooleanType dither)
2330 {
2331 #define PosterizeImageTag "Posterize/Image"
2332 #define PosterizePixel(pixel) ClampToQuantum((MagickRealType) QuantumRange*( \
2333  MagickRound(QuantumScale*(MagickRealType) pixel*(levels-1)))/ \
2334  MagickMax((ssize_t) levels-1,1))
2335 
2336  CacheView
2337  *image_view;
2338 
2340  *exception;
2341 
2342  MagickBooleanType
2343  status;
2344 
2345  MagickOffsetType
2346  progress;
2347 
2348  QuantizeInfo
2349  *quantize_info;
2350 
2351  ssize_t
2352  i,
2353  y;
2354 
2355  assert(image != (Image *) NULL);
2356  assert(image->signature == MagickCoreSignature);
2357  if (IsEventLogging() != MagickFalse)
2358  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
2359  if (image->storage_class == PseudoClass)
2360 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2361  #pragma omp parallel for schedule(static) shared(progress,status) \
2362  magick_number_threads(image,image,image->colors,1)
2363 #endif
2364  for (i=0; i < (ssize_t) image->colors; i++)
2365  {
2366  /*
2367  Posterize colormap.
2368  */
2369  if ((channel & RedChannel) != 0)
2370  image->colormap[i].red=(MagickRealType)
2371  PosterizePixel(image->colormap[i].red);
2372  if ((channel & GreenChannel) != 0)
2373  image->colormap[i].green=(MagickRealType)
2374  PosterizePixel(image->colormap[i].green);
2375  if ((channel & BlueChannel) != 0)
2376  image->colormap[i].blue=(MagickRealType)
2377  PosterizePixel(image->colormap[i].blue);
2378  if ((channel & OpacityChannel) != 0)
2379  image->colormap[i].opacity=(MagickRealType)
2380  PosterizePixel(image->colormap[i].opacity);
2381  }
2382  /*
2383  Posterize image.
2384  */
2385  status=MagickTrue;
2386  progress=0;
2387  exception=(&image->exception);
2388  image_view=AcquireAuthenticCacheView(image,exception);
2389 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2390  #pragma omp parallel for schedule(static) shared(progress,status) \
2391  magick_number_threads(image,image,image->rows,1)
2392 #endif
2393  for (y=0; y < (ssize_t) image->rows; y++)
2394  {
2395  IndexPacket
2396  *magick_restrict indexes;
2397 
2398  PixelPacket
2399  *magick_restrict q;
2400 
2401  ssize_t
2402  x;
2403 
2404  if (status == MagickFalse)
2405  continue;
2406  q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
2407  if (q == (PixelPacket *) NULL)
2408  {
2409  status=MagickFalse;
2410  continue;
2411  }
2412  indexes=GetCacheViewAuthenticIndexQueue(image_view);
2413  for (x=0; x < (ssize_t) image->columns; x++)
2414  {
2415  if ((channel & RedChannel) != 0)
2416  SetPixelRed(q,PosterizePixel(GetPixelRed(q)));
2417  if ((channel & GreenChannel) != 0)
2418  SetPixelGreen(q,PosterizePixel(GetPixelGreen(q)));
2419  if ((channel & BlueChannel) != 0)
2420  SetPixelBlue(q,PosterizePixel(GetPixelBlue(q)));
2421  if (((channel & OpacityChannel) != 0) &&
2422  (image->matte != MagickFalse))
2423  SetPixelOpacity(q,PosterizePixel(GetPixelOpacity(q)));
2424  if (((channel & IndexChannel) != 0) &&
2425  (image->colorspace == CMYKColorspace))
2426  SetPixelIndex(indexes+x,PosterizePixel(GetPixelIndex(indexes+x)));
2427  q++;
2428  }
2429  if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
2430  status=MagickFalse;
2431  if (image->progress_monitor != (MagickProgressMonitor) NULL)
2432  {
2433  MagickBooleanType
2434  proceed;
2435 
2436 #if defined(MAGICKCORE_OPENMP_SUPPORT)
2437  #pragma omp atomic
2438 #endif
2439  progress++;
2440  proceed=SetImageProgress(image,PosterizeImageTag,progress,image->rows);
2441  if (proceed == MagickFalse)
2442  status=MagickFalse;
2443  }
2444  }
2445  image_view=DestroyCacheView(image_view);
2446  quantize_info=AcquireQuantizeInfo((ImageInfo *) NULL);
2447  quantize_info->number_colors=(size_t) MagickMin((ssize_t) levels*levels*
2448  levels,MaxColormapSize+1);
2449  quantize_info->dither=dither;
2450  quantize_info->tree_depth=MaxTreeDepth;
2451  status=QuantizeImage(quantize_info,image);
2452  quantize_info=DestroyQuantizeInfo(quantize_info);
2453  return(status);
2454 }
2455 
2456 /*
2457 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2458 % %
2459 % %
2460 % %
2461 + P r u n e C h i l d %
2462 % %
2463 % %
2464 % %
2465 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2466 %
2467 % PruneChild() deletes the given node and merges its statistics into its
2468 % parent.
2469 %
2470 % The format of the PruneSubtree method is:
2471 %
2472 % PruneChild(CubeInfo *cube_info,const NodeInfo *node_info)
2473 %
2474 % A description of each parameter follows.
2475 %
2476 % o cube_info: A pointer to the Cube structure.
2477 %
2478 % o node_info: pointer to node in color cube tree that is to be pruned.
2479 %
2480 */
2481 static void PruneChild(CubeInfo *cube_info,const NodeInfo *node_info)
2482 {
2483  NodeInfo
2484  *parent;
2485 
2486  size_t
2487  number_children;
2488 
2489  ssize_t
2490  i;
2491 
2492  /*
2493  Traverse any children.
2494  */
2495  number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2496  for (i=0; i < (ssize_t) number_children; i++)
2497  if (node_info->child[i] != (NodeInfo *) NULL)
2498  PruneChild(cube_info,node_info->child[i]);
2499  if (cube_info->nodes > cube_info->maximum_colors)
2500  {
2501  /*
2502  Merge color statistics into parent.
2503  */
2504  parent=node_info->parent;
2505  parent->number_unique+=node_info->number_unique;
2506  parent->total_color.red+=node_info->total_color.red;
2507  parent->total_color.green+=node_info->total_color.green;
2508  parent->total_color.blue+=node_info->total_color.blue;
2509  parent->total_color.opacity+=node_info->total_color.opacity;
2510  parent->child[node_info->id]=(NodeInfo *) NULL;
2511  cube_info->nodes--;
2512  }
2513 }
2514 
2515 /*
2516 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2517 % %
2518 % %
2519 % %
2520 + P r u n e L e v e l %
2521 % %
2522 % %
2523 % %
2524 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2525 %
2526 % PruneLevel() deletes all nodes at the bottom level of the color tree merging
2527 % their color statistics into their parent node.
2528 %
2529 % The format of the PruneLevel method is:
2530 %
2531 % PruneLevel(CubeInfo *cube_info,const NodeInfo *node_info)
2532 %
2533 % A description of each parameter follows.
2534 %
2535 % o cube_info: A pointer to the Cube structure.
2536 %
2537 % o node_info: pointer to node in color cube tree that is to be pruned.
2538 %
2539 */
2540 static void PruneLevel(CubeInfo *cube_info,const NodeInfo *node_info)
2541 {
2542  size_t
2543  number_children;
2544 
2545  ssize_t
2546  i;
2547 
2548  /*
2549  Traverse any children.
2550  */
2551  number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2552  for (i=0; i < (ssize_t) number_children; i++)
2553  if (node_info->child[i] != (NodeInfo *) NULL)
2554  PruneLevel(cube_info,node_info->child[i]);
2555  if (node_info->level == cube_info->depth)
2556  PruneChild(cube_info,node_info);
2557 }
2558 
2559 /*
2560 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2561 % %
2562 % %
2563 % %
2564 + P r u n e T o C u b e D e p t h %
2565 % %
2566 % %
2567 % %
2568 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2569 %
2570 % PruneToCubeDepth() deletes any nodes at a depth greater than
2571 % cube_info->depth while merging their color statistics into their parent
2572 % node.
2573 %
2574 % The format of the PruneToCubeDepth method is:
2575 %
2576 % PruneToCubeDepth(CubeInfo *cube_info,const NodeInfo *node_info)
2577 %
2578 % A description of each parameter follows.
2579 %
2580 % o cube_info: A pointer to the Cube structure.
2581 %
2582 % o node_info: pointer to node in color cube tree that is to be pruned.
2583 %
2584 */
2585 static void PruneToCubeDepth(CubeInfo *cube_info,const NodeInfo *node_info)
2586 {
2587  size_t
2588  number_children;
2589 
2590  ssize_t
2591  i;
2592 
2593  /*
2594  Traverse any children.
2595  */
2596  number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2597  for (i=0; i < (ssize_t) number_children; i++)
2598  if (node_info->child[i] != (NodeInfo *) NULL)
2599  PruneToCubeDepth(cube_info,node_info->child[i]);
2600  if (node_info->level > cube_info->depth)
2601  PruneChild(cube_info,node_info);
2602 }
2603 
2604 /*
2605 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2606 % %
2607 % %
2608 % %
2609 % Q u a n t i z e I m a g e %
2610 % %
2611 % %
2612 % %
2613 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2614 %
2615 % QuantizeImage() analyzes the colors within a reference image and chooses a
2616 % fixed number of colors to represent the image. The goal of the algorithm
2617 % is to minimize the color difference between the input and output image while
2618 % minimizing the processing time.
2619 %
2620 % The format of the QuantizeImage method is:
2621 %
2622 % MagickBooleanType QuantizeImage(const QuantizeInfo *quantize_info,
2623 % Image *image)
2624 %
2625 % A description of each parameter follows:
2626 %
2627 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
2628 %
2629 % o image: the image.
2630 %
2631 */
2632 MagickExport MagickBooleanType QuantizeImage(const QuantizeInfo *quantize_info,
2633  Image *image)
2634 {
2635  CubeInfo
2636  *cube_info;
2637 
2638  MagickBooleanType
2639  status;
2640 
2641  size_t
2642  depth,
2643  maximum_colors;
2644 
2645  assert(quantize_info != (const QuantizeInfo *) NULL);
2646  assert(quantize_info->signature == MagickCoreSignature);
2647  assert(image != (Image *) NULL);
2648  assert(image->signature == MagickCoreSignature);
2649  if (IsEventLogging() != MagickFalse)
2650  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
2651  maximum_colors=quantize_info->number_colors;
2652  if (maximum_colors == 0)
2653  maximum_colors=MaxColormapSize;
2654  if (maximum_colors > MaxColormapSize)
2655  maximum_colors=MaxColormapSize;
2656  if (image->matte == MagickFalse)
2657  {
2658  if (SetImageGray(image,&image->exception) != MagickFalse)
2659  (void) SetGrayscaleImage(image);
2660  }
2661  depth=quantize_info->tree_depth;
2662  if (depth == 0)
2663  {
2664  size_t
2665  colors;
2666 
2667  /*
2668  Depth of color tree is: Log4(colormap size)+2.
2669  */
2670  colors=maximum_colors;
2671  for (depth=1; colors != 0; depth++)
2672  colors>>=2;
2673  if ((quantize_info->dither != MagickFalse) && (depth > 2))
2674  depth--;
2675  if ((image->matte != MagickFalse) && (depth > 5))
2676  depth--;
2677  if (SetImageGray(image,&image->exception) != MagickFalse)
2678  depth=MaxTreeDepth;
2679  }
2680  /*
2681  Initialize color cube.
2682  */
2683  cube_info=GetCubeInfo(quantize_info,depth,maximum_colors);
2684  if (cube_info == (CubeInfo *) NULL)
2685  ThrowBinaryImageException(ResourceLimitError,"MemoryAllocationFailed",
2686  image->filename);
2687  status=ClassifyImageColors(cube_info,image,&image->exception);
2688  if (status != MagickFalse)
2689  {
2690  /*
2691  Reduce the number of colors in the image.
2692  */
2693  if (cube_info->colors > cube_info->maximum_colors)
2694  ReduceImageColors(image,cube_info);
2695  status=AssignImageColors(image,cube_info);
2696  }
2697  DestroyCubeInfo(cube_info);
2698  return(status);
2699 }
2700 
2701 /*
2702 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2703 % %
2704 % %
2705 % %
2706 % Q u a n t i z e I m a g e s %
2707 % %
2708 % %
2709 % %
2710 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2711 %
2712 % QuantizeImages() analyzes the colors within a set of reference images and
2713 % chooses a fixed number of colors to represent the set. The goal of the
2714 % algorithm is to minimize the color difference between the input and output
2715 % images while minimizing the processing time.
2716 %
2717 % The format of the QuantizeImages method is:
2718 %
2719 % MagickBooleanType QuantizeImages(const QuantizeInfo *quantize_info,
2720 % Image *images)
2721 %
2722 % A description of each parameter follows:
2723 %
2724 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
2725 %
2726 % o images: Specifies a pointer to a list of Image structures.
2727 %
2728 */
2729 MagickExport MagickBooleanType QuantizeImages(const QuantizeInfo *quantize_info,
2730  Image *images)
2731 {
2732  CubeInfo
2733  *cube_info;
2734 
2735  Image
2736  *image;
2737 
2738  MagickBooleanType
2739  proceed,
2740  status;
2741 
2742  MagickProgressMonitor
2743  progress_monitor;
2744 
2745  size_t
2746  depth,
2747  maximum_colors,
2748  number_images;
2749 
2750  ssize_t
2751  i;
2752 
2753  assert(quantize_info != (const QuantizeInfo *) NULL);
2754  assert(quantize_info->signature == MagickCoreSignature);
2755  assert(images != (Image *) NULL);
2756  assert(images->signature == MagickCoreSignature);
2757  if (IsEventLogging() != MagickFalse)
2758  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",images->filename);
2759  if (GetNextImageInList(images) == (Image *) NULL)
2760  {
2761  /*
2762  Handle a single image with QuantizeImage.
2763  */
2764  status=QuantizeImage(quantize_info,images);
2765  return(status);
2766  }
2767  status=MagickFalse;
2768  maximum_colors=quantize_info->number_colors;
2769  if (maximum_colors == 0)
2770  maximum_colors=MaxColormapSize;
2771  if (maximum_colors > MaxColormapSize)
2772  maximum_colors=MaxColormapSize;
2773  depth=quantize_info->tree_depth;
2774  if (depth == 0)
2775  {
2776  size_t
2777  colors;
2778 
2779  /*
2780  Depth of color tree is: Log4(colormap size)+2.
2781  */
2782  colors=maximum_colors;
2783  for (depth=1; colors != 0; depth++)
2784  colors>>=2;
2785  if (quantize_info->dither != MagickFalse)
2786  depth--;
2787  }
2788  /*
2789  Initialize color cube.
2790  */
2791  cube_info=GetCubeInfo(quantize_info,depth,maximum_colors);
2792  if (cube_info == (CubeInfo *) NULL)
2793  {
2794  (void) ThrowMagickException(&images->exception,GetMagickModule(),
2795  ResourceLimitError,"MemoryAllocationFailed","`%s'",images->filename);
2796  return(MagickFalse);
2797  }
2798  number_images=GetImageListLength(images);
2799  image=images;
2800  for (i=0; image != (Image *) NULL; i++)
2801  {
2802  progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor) NULL,
2803  image->client_data);
2804  status=ClassifyImageColors(cube_info,image,&image->exception);
2805  if (status == MagickFalse)
2806  break;
2807  (void) SetImageProgressMonitor(image,progress_monitor,image->client_data);
2808  proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i,
2809  number_images);
2810  if (proceed == MagickFalse)
2811  break;
2812  image=GetNextImageInList(image);
2813  }
2814  if (status != MagickFalse)
2815  {
2816  /*
2817  Reduce the number of colors in an image sequence.
2818  */
2819  ReduceImageColors(images,cube_info);
2820  image=images;
2821  for (i=0; image != (Image *) NULL; i++)
2822  {
2823  progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor)
2824  NULL,image->client_data);
2825  status=AssignImageColors(image,cube_info);
2826  if (status == MagickFalse)
2827  break;
2828  (void) SetImageProgressMonitor(image,progress_monitor,
2829  image->client_data);
2830  proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i,
2831  number_images);
2832  if (proceed == MagickFalse)
2833  break;
2834  image=GetNextImageInList(image);
2835  }
2836  }
2837  DestroyCubeInfo(cube_info);
2838  return(status);
2839 }
2840 
2841 /*
2842 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2843 % %
2844 % %
2845 % %
2846 + Q u a n t i z e E r r o r F l a t t e n %
2847 % %
2848 % %
2849 % %
2850 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2851 %
2852 % QuantizeErrorFlatten() traverses the color cube and flattens the quantization
2853 % error into a sorted 1D array. This accelerates the color reduction process.
2854 %
2855 % Contributed by Yoya.
2856 %
2857 % The format of the QuantizeErrorFlatten method is:
2858 %
2859 % size_t QuantizeErrorFlatten(const CubeInfo *cube_info,
2860 % const NodeInfo *node_info,const ssize_t offset,
2861 % MagickRealType *quantize_error)
2862 %
2863 % A description of each parameter follows.
2864 %
2865 % o cube_info: A pointer to the Cube structure.
2866 %
2867 % o node_info: pointer to node in color cube tree that is current pointer.
2868 %
2869 % o offset: quantize error offset.
2870 %
2871 % o quantize_error: the quantization error vector.
2872 %
2873 */
2874 static size_t QuantizeErrorFlatten(const CubeInfo *cube_info,
2875  const NodeInfo *node_info,const ssize_t offset,
2876  MagickRealType *quantize_error)
2877 {
2878  size_t
2879  n,
2880  number_children;
2881 
2882  ssize_t
2883  i;
2884 
2885  if (offset >= (ssize_t) cube_info->nodes)
2886  return(0);
2887  quantize_error[offset]=node_info->quantize_error;
2888  n=1;
2889  number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2890  for (i=0; i < (ssize_t) number_children ; i++)
2891  if (node_info->child[i] != (NodeInfo *) NULL)
2892  n+=QuantizeErrorFlatten(cube_info,node_info->child[i],offset+n,
2893  quantize_error);
2894  return(n);
2895 }
2896 
2897 /*
2898 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2899 % %
2900 % %
2901 % %
2902 + R e d u c e %
2903 % %
2904 % %
2905 % %
2906 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2907 %
2908 % Reduce() traverses the color cube tree and prunes any node whose
2909 % quantization error falls below a particular threshold.
2910 %
2911 % The format of the Reduce method is:
2912 %
2913 % Reduce(CubeInfo *cube_info,const NodeInfo *node_info)
2914 %
2915 % A description of each parameter follows.
2916 %
2917 % o cube_info: A pointer to the Cube structure.
2918 %
2919 % o node_info: pointer to node in color cube tree that is to be pruned.
2920 %
2921 */
2922 static void Reduce(CubeInfo *cube_info,const NodeInfo *node_info)
2923 {
2924  size_t
2925  number_children;
2926 
2927  ssize_t
2928  i;
2929 
2930  /*
2931  Traverse any children.
2932  */
2933  number_children=cube_info->associate_alpha == MagickFalse ? 8UL : 16UL;
2934  for (i=0; i < (ssize_t) number_children; i++)
2935  if (node_info->child[i] != (NodeInfo *) NULL)
2936  Reduce(cube_info,node_info->child[i]);
2937  if (node_info->quantize_error <= cube_info->pruning_threshold)
2938  PruneChild(cube_info,node_info);
2939  else
2940  {
2941  /*
2942  Find minimum pruning threshold.
2943  */
2944  if (node_info->number_unique > 0)
2945  cube_info->colors++;
2946  if (node_info->quantize_error < cube_info->next_threshold)
2947  cube_info->next_threshold=node_info->quantize_error;
2948  }
2949 }
2950 
2951 /*
2952 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2953 % %
2954 % %
2955 % %
2956 + R e d u c e I m a g e C o l o r s %
2957 % %
2958 % %
2959 % %
2960 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2961 %
2962 % ReduceImageColors() repeatedly prunes the tree until the number of nodes
2963 % with n2 > 0 is less than or equal to the maximum number of colors allowed
2964 % in the output image. On any given iteration over the tree, it selects
2965 % those nodes whose E value is minimal for pruning and merges their
2966 % color statistics upward. It uses a pruning threshold, Ep, to govern
2967 % node selection as follows:
2968 %
2969 % Ep = 0
2970 % while number of nodes with (n2 > 0) > required maximum number of colors
2971 % prune all nodes such that E <= Ep
2972 % Set Ep to minimum E in remaining nodes
2973 %
2974 % This has the effect of minimizing any quantization error when merging
2975 % two nodes together.
2976 %
2977 % When a node to be pruned has offspring, the pruning procedure invokes
2978 % itself recursively in order to prune the tree from the leaves upward.
2979 % n2, Sr, Sg, and Sb in a node being pruned are always added to the
2980 % corresponding data in that node's parent. This retains the pruned
2981 % node's color characteristics for later averaging.
2982 %
2983 % For each node, n2 pixels exist for which that node represents the
2984 % smallest volume in RGB space containing those pixel's colors. When n2
2985 % > 0 the node will uniquely define a color in the output image. At the
2986 % beginning of reduction, n2 = 0 for all nodes except a the leaves of
2987 % the tree which represent colors present in the input image.
2988 %
2989 % The other pixel count, n1, indicates the total number of colors
2990 % within the cubic volume which the node represents. This includes n1 -
2991 % n2 pixels whose colors should be defined by nodes at a lower level in
2992 % the tree.
2993 %
2994 % The format of the ReduceImageColors method is:
2995 %
2996 % ReduceImageColors(const Image *image,CubeInfo *cube_info)
2997 %
2998 % A description of each parameter follows.
2999 %
3000 % o image: the image.
3001 %
3002 % o cube_info: A pointer to the Cube structure.
3003 %
3004 */
3005 
3006 static int MagickRealTypeCompare(const void *error_p,const void *error_q)
3007 {
3008  MagickRealType
3009  *p,
3010  *q;
3011 
3012  p=(MagickRealType *) error_p;
3013  q=(MagickRealType *) error_q;
3014  if (*p > *q)
3015  return(1);
3016  if (fabs((double) (*q-*p)) <= MagickEpsilon)
3017  return(0);
3018  return(-1);
3019 }
3020 
3021 static void ReduceImageColors(const Image *image,CubeInfo *cube_info)
3022 {
3023 #define ReduceImageTag "Reduce/Image"
3024 
3025  MagickBooleanType
3026  proceed;
3027 
3028  MagickOffsetType
3029  offset;
3030 
3031  size_t
3032  span;
3033 
3034  cube_info->next_threshold=0.0;
3035  if (cube_info->colors > cube_info->maximum_colors)
3036  {
3037  MagickRealType
3038  *quantize_error;
3039 
3040  /*
3041  Enable rapid reduction of the number of unique colors.
3042  */
3043  quantize_error=(MagickRealType *) AcquireQuantumMemory(cube_info->nodes,
3044  sizeof(*quantize_error));
3045  if (quantize_error != (MagickRealType *) NULL)
3046  {
3047  (void) QuantizeErrorFlatten(cube_info,cube_info->root,0,
3048  quantize_error);
3049  qsort(quantize_error,cube_info->nodes,sizeof(MagickRealType),
3050  MagickRealTypeCompare);
3051  if (cube_info->nodes > (110*(cube_info->maximum_colors+1)/100))
3052  cube_info->next_threshold=quantize_error[cube_info->nodes-110*
3053  (cube_info->maximum_colors+1)/100];
3054  quantize_error=(MagickRealType *) RelinquishMagickMemory(
3055  quantize_error);
3056  }
3057  }
3058  for (span=cube_info->colors; cube_info->colors > cube_info->maximum_colors; )
3059  {
3060  cube_info->pruning_threshold=cube_info->next_threshold;
3061  cube_info->next_threshold=cube_info->root->quantize_error-1;
3062  cube_info->colors=0;
3063  Reduce(cube_info,cube_info->root);
3064  offset=(MagickOffsetType) span-cube_info->colors;
3065  proceed=SetImageProgress(image,ReduceImageTag,offset,span-
3066  cube_info->maximum_colors+1);
3067  if (proceed == MagickFalse)
3068  break;
3069  }
3070 }
3071 
3072 /*
3073 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3074 % %
3075 % %
3076 % %
3077 % R e m a p I m a g e %
3078 % %
3079 % %
3080 % %
3081 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3082 %
3083 % RemapImage() replaces the colors of an image with the closest color from
3084 % a reference image.
3085 %
3086 % The format of the RemapImage method is:
3087 %
3088 % MagickBooleanType RemapImage(const QuantizeInfo *quantize_info,
3089 % Image *image,const Image *remap_image)
3090 %
3091 % A description of each parameter follows:
3092 %
3093 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
3094 %
3095 % o image: the image.
3096 %
3097 % o remap_image: the reference image.
3098 %
3099 */
3100 MagickExport MagickBooleanType RemapImage(const QuantizeInfo *quantize_info,
3101  Image *image,const Image *remap_image)
3102 {
3103  CubeInfo
3104  *cube_info;
3105 
3106  MagickBooleanType
3107  status;
3108 
3109  /*
3110  Initialize color cube.
3111  */
3112  assert(image != (Image *) NULL);
3113  assert(image->signature == MagickCoreSignature);
3114  if (IsEventLogging() != MagickFalse)
3115  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
3116  assert(remap_image != (Image *) NULL);
3117  assert(remap_image->signature == MagickCoreSignature);
3118  cube_info=GetCubeInfo(quantize_info,MaxTreeDepth,
3119  quantize_info->number_colors);
3120  if (cube_info == (CubeInfo *) NULL)
3121  ThrowBinaryImageException(ResourceLimitError,"MemoryAllocationFailed",
3122  image->filename);
3123  cube_info->quantize_info->colorspace=remap_image->colorspace;
3124  status=ClassifyImageColors(cube_info,remap_image,&image->exception);
3125  if (status != MagickFalse)
3126  {
3127  /*
3128  Classify image colors from the reference image.
3129  */
3130  cube_info->quantize_info->number_colors=cube_info->colors;
3131  status=AssignImageColors(image,cube_info);
3132  }
3133  DestroyCubeInfo(cube_info);
3134  return(status);
3135 }
3136 
3137 /*
3138 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3139 % %
3140 % %
3141 % %
3142 % R e m a p I m a g e s %
3143 % %
3144 % %
3145 % %
3146 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3147 %
3148 % RemapImages() replaces the colors of a sequence of images with the
3149 % closest color from a reference image.
3150 %
3151 % The format of the RemapImage method is:
3152 %
3153 % MagickBooleanType RemapImages(const QuantizeInfo *quantize_info,
3154 % Image *images,Image *remap_image)
3155 %
3156 % A description of each parameter follows:
3157 %
3158 % o quantize_info: Specifies a pointer to an QuantizeInfo structure.
3159 %
3160 % o images: the image sequence.
3161 %
3162 % o remap_image: the reference image.
3163 %
3164 */
3165 MagickExport MagickBooleanType RemapImages(const QuantizeInfo *quantize_info,
3166  Image *images,const Image *remap_image)
3167 {
3168  CubeInfo
3169  *cube_info;
3170 
3171  Image
3172  *image;
3173 
3174  MagickBooleanType
3175  status;
3176 
3177  assert(images != (Image *) NULL);
3178  assert(images->signature == MagickCoreSignature);
3179  if (IsEventLogging() != MagickFalse)
3180  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",images->filename);
3181  image=images;
3182  if (remap_image == (Image *) NULL)
3183  {
3184  /*
3185  Create a global colormap for an image sequence.
3186  */
3187  status=QuantizeImages(quantize_info,images);
3188  return(status);
3189  }
3190  /*
3191  Classify image colors from the reference image.
3192  */
3193  cube_info=GetCubeInfo(quantize_info,MaxTreeDepth,
3194  quantize_info->number_colors);
3195  if (cube_info == (CubeInfo *) NULL)
3196  ThrowBinaryImageException(ResourceLimitError,"MemoryAllocationFailed",
3197  image->filename);
3198  status=ClassifyImageColors(cube_info,remap_image,&image->exception);
3199  if (status != MagickFalse)
3200  {
3201  /*
3202  Classify image colors from the reference image.
3203  */
3204  cube_info->quantize_info->number_colors=cube_info->colors;
3205  image=images;
3206  for ( ; image != (Image *) NULL; image=GetNextImageInList(image))
3207  {
3208  status=AssignImageColors(image,cube_info);
3209  if (status == MagickFalse)
3210  break;
3211  }
3212  }
3213  DestroyCubeInfo(cube_info);
3214  return(status);
3215 }
3216 
3217 /*
3218 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3219 % %
3220 % %
3221 % %
3222 % S e t G r a y s c a l e I m a g e %
3223 % %
3224 % %
3225 % %
3226 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3227 %
3228 % SetGrayscaleImage() converts an image to a PseudoClass grayscale image.
3229 %
3230 % The format of the SetGrayscaleImage method is:
3231 %
3232 % MagickBooleanType SetGrayscaleImage(Image *image)
3233 %
3234 % A description of each parameter follows:
3235 %
3236 % o image: The image.
3237 %
3238 */
3239 
3240 #if defined(__cplusplus) || defined(c_plusplus)
3241 extern "C" {
3242 #endif
3243 
3244 static int IntensityCompare(const void *x,const void *y)
3245 {
3246  double
3247  intensity;
3248 
3249  PixelPacket
3250  *color_1,
3251  *color_2;
3252 
3253  color_1=(PixelPacket *) x;
3254  color_2=(PixelPacket *) y;
3255  intensity=PixelPacketIntensity(color_1)-PixelPacketIntensity(color_2);
3256  if (intensity < (double) INT_MIN)
3257  intensity=(double) INT_MIN;
3258  if (intensity > (double) INT_MAX)
3259  intensity=(double) INT_MAX;
3260  return((int) intensity);
3261 }
3262 
3263 #if defined(__cplusplus) || defined(c_plusplus)
3264 }
3265 #endif
3266 
3267 static MagickBooleanType SetGrayscaleImage(Image *image)
3268 {
3269  CacheView
3270  *image_view;
3271 
3273  *exception;
3274 
3275  MagickBooleanType
3276  status;
3277 
3278  PixelPacket
3279  *colormap;
3280 
3281  size_t
3282  extent;
3283 
3284  ssize_t
3285  *colormap_index,
3286  i,
3287  j,
3288  y;
3289 
3290  assert(image != (Image *) NULL);
3291  assert(image->signature == MagickCoreSignature);
3292  exception=(&image->exception);
3293  if (image->type != GrayscaleType)
3294  (void) TransformImageColorspace(image,GRAYColorspace);
3295  extent=MagickMax(image->colors+1,MagickMax(MaxColormapSize,MaxMap+1));
3296  colormap_index=(ssize_t *) AcquireQuantumMemory(extent,
3297  sizeof(*colormap_index));
3298  if (colormap_index == (ssize_t *) NULL)
3299  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3300  image->filename);
3301  if (image->storage_class != PseudoClass)
3302  {
3303  (void) memset(colormap_index,(-1),extent*sizeof(*colormap_index));
3304  if (AcquireImageColormap(image,MaxColormapSize) == MagickFalse)
3305  {
3306  colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
3307  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3308  image->filename);
3309  }
3310  image->colors=0;
3311  status=MagickTrue;
3312  image_view=AcquireAuthenticCacheView(image,exception);
3313 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3314  #pragma omp parallel for schedule(static) shared(status) \
3315  magick_number_threads(image,image,image->rows,1)
3316 #endif
3317  for (y=0; y < (ssize_t) image->rows; y++)
3318  {
3319  IndexPacket
3320  *magick_restrict indexes;
3321 
3322  PixelPacket
3323  *magick_restrict q;
3324 
3325  ssize_t
3326  x;
3327 
3328  if (status == MagickFalse)
3329  continue;
3330  q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,
3331  exception);
3332  if (q == (PixelPacket *) NULL)
3333  {
3334  status=MagickFalse;
3335  continue;
3336  }
3337  indexes=GetCacheViewAuthenticIndexQueue(image_view);
3338  for (x=0; x < (ssize_t) image->columns; x++)
3339  {
3340  size_t
3341  intensity;
3342 
3343  intensity=ScaleQuantumToMap(GetPixelRed(q));
3344  if (colormap_index[intensity] < 0)
3345  {
3346 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3347  #pragma omp critical (MagickCore_SetGrayscaleImage)
3348 #endif
3349  if (colormap_index[intensity] < 0)
3350  {
3351  colormap_index[intensity]=(ssize_t) image->colors;
3352  image->colormap[image->colors].red=GetPixelRed(q);
3353  image->colormap[image->colors].green=GetPixelGreen(q);
3354  image->colormap[image->colors].blue=GetPixelBlue(q);
3355  image->colors++;
3356  }
3357  }
3358  SetPixelIndex(indexes+x,colormap_index[intensity]);
3359  q++;
3360  }
3361  if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
3362  status=MagickFalse;
3363  }
3364  image_view=DestroyCacheView(image_view);
3365  }
3366  (void) memset(colormap_index,0,extent*sizeof(*colormap_index));
3367  for (i=0; i < (ssize_t) image->colors; i++)
3368  image->colormap[i].opacity=(Quantum) i;
3369  qsort((void *) image->colormap,image->colors,sizeof(PixelPacket),
3370  IntensityCompare);
3371  colormap=(PixelPacket *) AcquireQuantumMemory(image->colors,
3372  sizeof(*colormap));
3373  if (colormap == (PixelPacket *) NULL)
3374  {
3375  colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
3376  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
3377  image->filename);
3378  }
3379  j=0;
3380  colormap[j]=image->colormap[0];
3381  for (i=0; i < (ssize_t) image->colors; i++)
3382  {
3383  if (IsSameColor(image,&colormap[j],&image->colormap[i]) == MagickFalse)
3384  {
3385  j++;
3386  colormap[j]=image->colormap[i];
3387  }
3388  colormap_index[(ssize_t) image->colormap[i].opacity]=j;
3389  }
3390  image->colors=(size_t) (j+1);
3391  image->colormap=(PixelPacket *) RelinquishMagickMemory(image->colormap);
3392  image->colormap=colormap;
3393  status=MagickTrue;
3394  image_view=AcquireAuthenticCacheView(image,exception);
3395 #if defined(MAGICKCORE_OPENMP_SUPPORT)
3396  #pragma omp parallel for schedule(static) shared(status) \
3397  magick_number_threads(image,image,image->rows,1)
3398 #endif
3399  for (y=0; y < (ssize_t) image->rows; y++)
3400  {
3401  IndexPacket
3402  *magick_restrict indexes;
3403 
3404  const PixelPacket
3405  *magick_restrict q;
3406 
3407  ssize_t
3408  x;
3409 
3410  if (status == MagickFalse)
3411  continue;
3412  q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
3413  if (q == (PixelPacket *) NULL)
3414  {
3415  status=MagickFalse;
3416  continue;
3417  }
3418  indexes=GetCacheViewAuthenticIndexQueue(image_view);
3419  for (x=0; x < (ssize_t) image->columns; x++)
3420  SetPixelIndex(indexes+x,colormap_index[ScaleQuantumToMap(GetPixelIndex(
3421  indexes+x))]);
3422  if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
3423  status=MagickFalse;
3424  }
3425  image_view=DestroyCacheView(image_view);
3426  colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
3427  image->type=GrayscaleType;
3428  if (SetImageMonochrome(image,&image->exception) != MagickFalse)
3429  image->type=BilevelType;
3430  return(status);
3431 }
Definition: image.h:152