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