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