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